ICML 2026 Papers

Everyday tasks come with a target, and pretraining models around this target is what turns them into experts. In this paper, we study target-oriented language model (LM) pretraining by introducing ***N**euron-**A**ctivated **G**raph Ranking* (NAG-based Ranking), a training-free and interpretable framework for target pretraining data selection. Rather than using black-box representations, our approach directly characterizes each target input by a sparse set of high-impact neurons in any off-the-shelf LLMs. Concretely, we quantify neuron impact and select the most influential neurons across layers into a compact ***N**euron-**A**ctivated **G**raph* (NAG), and rank candidate data by NAG similarity to target examples. We conduct experiments across six benchmarks, where our NAG-based Ranking improves target-oriented pretraining by 4.9\% on average over random sampling, and also outperforms state-of-the-art baselines by 5.3\% accuracy on HellaSwag. It also remains effective under a more applicable multi-target setting, where our best setup surpasses two baselines by 1.1\% and 4.1\%, respectively. Furthermore, we provide a comprehensive analysis on *why* and *how* our NAG works, e.g., deactivating NAG-selected neurons (only 0.12\% of all) causes a 23.5\% performance collapse, and restricting NAG to the final layer incurs a 4.1\% average drop, indicating that NAG captures a sparse ``functional backbone'' for learning target features. We release the code at https://github.com/asillycat/NAG.

Graph Neural Networks (GNNs) are widely deployed in industry, making their intellectual property valuable. However, protecting GNNs from unauthorized use remains a challenge. Watermarking offers a solution by embedding ownership information into models. Existing watermarking methods have two limitations: First, they rarely focus on graph data or GNNs. Second, the \emph{de facto} backdoor-based method relies on manipulating training data, which can introduce ownership ambiguity through misclassification and vulnerability to data poisoning attacks that can interrupt the backdoor mechanism. Our explanation-based watermarking inherits the strengths of backdoor-based methods (e.g., black-box verification) without data manipulation, eliminating ownership ambiguity and data dependencies. In particular, we watermark GNN explanations such that these explanations are statistically distinct from others, so ownership claims must be verified through statistical significance. We theoretically prove that, even with full knowledge of our method, locating the watermark is NP-hard. Empirically, our method demonstrates robustness to fine-tuning and pruning attacks. By addressing these challenges, our approach significantly advances GNN intellectual property protection.

In recent years, there has been growing interest in understanding neural architectures' ability to learn to execute discrete algorithms, a line of work often referred to as neural algorithmic reasoning. The goal is to integrate algorithmic reasoning capabilities into larger neural pipelines. Many such architectures are based on (message-passing) graph neural networks (MPNNs), owing to their permutation equivariance and ability to deal with sparsity and variable-sized inputs. However, much existing work is either largely empirical and lacks formal guarantees or it focuses solely on expressivity, leaving open the question of when and how such architectures generalize beyond a finite training set. In this work, we propose a general theoretical framework that characterizes sufficient conditions under which MPNNs can learn an algorithm from a training set of small instances and provably approximate its behavior on inputs of arbitrary size with worst-case guarantees. Our framework applies to a broad class of algorithms, including single-source shortest paths, minimum spanning trees, and general dynamic programming problems, such as the $0$-$1$ knapsack problem. In addition, we establish impossibility results for a wide range of algorithmic tasks, showing that standard MPNNs cannot learn them and derive more expressive MPNN-like architectures that overcome these limitations. Finally, we refine our analysis for the Bellman–Ford algorithm, yielding substantially smaller required training sets and significantly extending the recent work of Nerem et al., 2025 by allowing for a differentiable regularization loss. Empirical results largely support our theoretical findings.

Representation learning is central to graph machine learning, powering tasks such as link prediction and node classification. However, most graph embeddings are hard to interpret, offering limited insight into how learned features relate to graph structure. Many networks naturally admit a role-mixture view, where nodes are best described as mixtures over latent archetypal factors. Motivated by this structure, we propose a compositional graph embedding framework grounded in Aitchison geometry, the canonical geometry for comparing mixtures. Nodes are represented as simplex-valued compositions and embedded via isometric log-ratio (ILR) coordinates, which preserve Aitchison distances while enabling unconstrained optimization in Euclidean space. This yields intrinsically interpretable embeddings whose geometry reflects relative trade-offs among archetypes and supports coherent behavior under component restriction; we consider both fixed and learnable ILR bases. Across node classification and link prediction, our method achieves competitive performance with strong baselines while providing explainability by construction rather than post hoc. Finally, subcompositional coherence enables principled component restriction: removing and renormalizing subsets preserves a well-defined geometry, which we exploit via subcompositional dimensionality removal to probe how archetype groups influence representations and predictions.

Large Language Models (LLMs) have significantly advanced code analysis tasks, yet they struggle to detect malicious behaviors fragmented across files, whose intricate dependencies easily get lost in the vast amount of benign code. We therefore propose a graph-centric attention acquisition pipeline that enhances LLMs' ability to localize malicious behavior. The approach parses a project into a code graph, uses an LLM to encode nodes with semantic and structural signals, and trains a Graph Neural Network (GNN) under sparse supervision. The GNN performs an initial detection, and by interpreting these predictions, identifies key code sections that are most likely to contain malicious behavior. These influential regions are then used to guide the LLM's attention for in-depth analysis. This strategy significantly reduces interference from irrelevant context while maintaining low annotation costs. Extensive experiments show that the method consistently outperforms existing approaches on multiple public and custom datasets, highlighting its potential for practical deployment in software security scenarios. Codes can be found in https://github.com/Epiphaniespt/GMLLM.git.

Relational deep learning (RDL) converts relational databases (RDBs) into heterogeneous graphs, but graphs derived directly from database schemas are often not well suited for how graph neural networks (GNNs) perform relational reasoning. We study what makes a relational graph suitable for deep learning and show that schema-derived graphs suffer from two systematic failures: information overload and semantic fragmentation. Through an empirical analysis on real-world databases, we find that effective graphs arise from a task-dependent balance between removing task-irrelevant structure and injecting task-aligned relational connectivity. Filtering exhibits a non-monotonic effect on performance, while structural injection is beneficial only when it reflects the logic of the downstream task. Based on these findings, we develop an end-to-end structural optimizer that applies both operations to adapt relational graphs automatically. Across 23 tasks spanning classification, regression, and recommendation, the optimized graphs consistently improve accuracy while often reducing inference cost.

By synergizing graph topology with the global expressive power of attention, Graph Transformers (GTs) have emerged as a powerful architecture for node classification. Existing GTs mainly focus on diverse topology injection paradigms, which fundamentally construct different propagation operators. However, a unified theoretical understanding of what constitutes a desirable propagation operator remains largely unexplored. To bridge this gap, this paper rethinks GTs from a graph signal denoising perspective, revealing that a block-diagonal structure is a desirable structural prior for graph denoising. To efficiently instantiate this prior, this paper introduces BDFormer, which imposes spectral block regularization on the affinity of a compact set of latent anchors. Furthermore, by introducing hard assignments between nodes and anchors, BDFormer establishes sparse, structured propagation that suppresses noisy cross-class propagation in linear time. Meanwhile, the learned global affinity guides the pruning of inter-class edges in the graph topology, enabling both global and local propagation to jointly adhere to the target block-diagonal structure. Extensive experiments on benchmark datasets demonstrate the superiority and scalability of BDFormer.

scRNA-seq clustering is a critical task for analyzing single-cell RNA sequencing (scRNA-seq) data, as it groups cells with similar gene expression profiles. Transformers, as powerful foundational models, have been applied to scRNA-seq clustering. Their self-attention mechanism automatically assigns higher attention weights to cells within the same cluster, enhancing the distinction between clusters. Existing methods for scRNA-seq clustering, such as graph transformer-based models, treat each cell as a token in a sequence. Their computational and space complexities are $\mathcal{O}(n^2)$ with respect to the number of cells, limiting their applicability to large-scale scRNA-seq datasets. To address this challenge, we propose a Bipartite Graph Transformer-based clustering model (BGFormer) for scRNA-seq data. We introduce a set of learnable anchor tokens as shared reference points to represent the entire dataset. A bipartite graph attention mechanism is introduced to learn the similarity between cells and anchor tokens, bringing cells of the same class closer together in the embedding space. BGFormer achieves linear computational complexity with respect to the number of cells, making it scalable to large datasets. Experimental results on multiple large-scale scRNA-seq datasets demonstrate the effectiveness and scalability of BGFormer.

Reliable uncertainty quantification (UQ) is crucial for deploying graph neural networks (GNNs) in safety-critical settings, yet dominant solutions either rely on costly multi-pass sampling or require retraining—often using *black-box auxiliary* models—to obtain evidential semantics. We propose **X-EviProbe**, a simple and parameter-free *post-hoc* framework that turns a *frozen* GNN into an evidential predictor with a decomposable view of epistemic vs. aleatoric uncertainty. X-EviProbe constructs class-wise Dirichlet evidence by probing the frozen latent space and the model’s native outputs, and incorporates graph structure via lightweight evidence-strength propagation. This yields a transparent evidential representation without retraining or additional neural components. Extensive experiments on seven benchmarks show that X-EviProbe consistently ranks among the top methods for both OOD detection and misclassification detection, improving AUROC by up to **33.4%** and **8.7%** over the strongest baselines.

Graph Neural Networks (GNNs) on meshes have emerged as promising surrogates for computational mechanics, but standard local message passing struggles to propagate information across unstructured meshes, leading to large errors in regions with complex physics (e.g., shocks, wakes, boundary layers). Existing approaches enlarge connectivity with long-range edges chosen *a priori* via geometric heuristics or random sampling, which lack a mechanism to prioritize high-error regions and often introduce redundant communication. We propose **MiSe-GNN**, a dual-head architecture that adaptively augments graph connectivity using model-predicted *a posteriori* errors. MiSe-GNN jointly predicts physical fields and a node-wise error indicator; the predicted error is periodically converted into a hierarchy of additional edges via an adaptive tree that links high-error nodes to spatial pivots at multiple scales. This error-guided connectivity concentrates message passing where the surrogate is uncertain while keeping the graph sparse elsewhere, yielding a transparent and physically interpretable graph-space analogue of adaptive mesh refinement. Across industrial CFD and CSD benchmarks, MiSe-GNN consistently improves accuracy and accuracy–compute trade-offs over strong baselines, and qualitative analyses show that it routes communication toward physically challenging regions. These results establish *error-guided edge augmentation* as a robust and general design principle for long-range message passing in physics-aware GNNs.

Spectral clustering is hindered by its $O(n^{3})$ time complexity, and although anchor-based approximations reduce this to $O(nm^{2})$ ($m \ll n$), they often yield degenerate or unbalanced partitions in the absence of explicit cluster-size control. To address this limitation, we propose \textbf{SC-FAGC (Size-Constrained Fast Anchor Graph Clustering)}, a unified formulation that integrates entropy regularization and bilateral cardinality constraints within an anchor-based spectral clustering framework, enforcing user-specified lower and upper bounds on anchor-level cluster sizes to avoid trivial or highly unbalanced solutions. To solve the resulting non-convex problem efficiently, we develop an \textbf{Iteratively Re-weighted (IRW)} optimization scheme that linearizes the objective and solves each subproblem via a \textbf{Double-Bounded Optimal Transport (DB-OT)} solver based on the \textbf{Sinkhorn--Knopp} algorithm, guaranteeing convergence while maintaining scalability. Extensive experiments on benchmark datasets demonstrate that SC-FAGC consistently achieves state-of-the-art performance across six standard clustering metrics while strictly enforcing the prescribed anchor-level constraints. Moreover, it induces effective data-level size control after label transmission, offering a principled and scalable solution for large-scale graph clustering with controllable partition structure.

Message-passing neural networks (MPNNs) often suffer from an information bottleneck when capturing long-range dependencies, leading to the oversquashing (OSQ) phenomenon. Alongside spatial connectivity enrichment (e.g., rewiring), recent studies have shown that spectral filtering can yield strong long-range learning outcomes, as spectral operators enable global information mixing that alleviates OSQ. These approaches achieve this either by stabilizing the Jacobian energies in deep propagation or by guaranteeing OSQ mitigation under strong theoretical assumptions. We examine the practical attainability of these guarantees and show that the associated Jacobian sensitivity lower bound is generally difficult to achieve in practice. We then propose S$^3$GNN, which mitigates OSQ without such restrictive assumptions by lightweightly reintroducing omitted components with substantially lower computational complexity, while standard stability constraints on feature transformations remain effective under our new dynamics. Extensive experiments across diverse domains (e.g., long-range benchmarks, KGQA, and mesh-based fluid dynamics) demonstrate that S$^3$GNN achieves up to an order-of-magnitude error reduction with up to 50\% fewer parameters. Our code can be found in https://github.com/EEthanShi/S3-GNN.git.

Graphs provide a natural representation of relational structure that arises across diverse domains. Despite this ubiquity, graph structure is typically learned in a modality- and task-isolated manner, where graph representations are constructed within individual task contexts and discarded thereafter. As a result, structural regularities across modalities and tasks are repeatedly reconstructed rather than accumulated at the level of intermediate graph representations. This motivates a representation-learning question: *how should graph structure be organized so that it can persist and accumulate across heterogeneous modalities and tasks?* We adopt a representation-centric perspective in which graph structure is treated as a structural substrate that persists across learning contexts. To instantiate this perspective, we propose **G-Substrate**, a **g**raph **substrate** framework that organizes learning around shared graph structures. G-Substrate comprises two complementary mechanisms: a unified structural schema that ensures compatibility among graph representations across heterogeneous modalities and tasks, and an interleaved role-based training strategy that exposes the same graph structure to multiple functional roles during learning. Experiments across multiple domains, modalities, and tasks show that G-Substrate outperforms task-isolated and naive multi-task learning methods. The codebase, model, and datasets are available at <https://github.com/zmli6/G-Substrate>.

Learning-based surrogates for partial differential equations have recently matched the accuracy of classical solvers while achieving orders-of-magnitude speedups, predominantly in fluid settings and structured geometries. In contrast, robust surrogates for deformable solids remain underexplored, despite the presence of nonlinear elasticity, plasticity, and transient behavior that challenge standard architectures. We introduce a multigrid graph neural network for solid mechanics that couples an *encoder-processor-decoder* backbone with a physics-informed coarsening strategy. Instead of downsampling via geometric heuristics, our method scores nodes using a residual-based measure of local physical activity and preferentially retains regions of high strain or stress concentration, allocating multiscale capacity where it is most needed. This preserves long-range interactions through hierarchical message passing while improving stability over long rollouts. We evaluate on multiple datasets covering linear, nonlinear, and transient regimes, and observe consistent gains in accuracy and rollout stability compared to standard sampling baselines. Our results highlight the importance of physics-informed coarsening for scalable surrogate modeling in solid mechanics.

Point forecasting for graph-structured multivariate time series is a fundamental problem, but rigorous uncertainty quantification for such predictions is still underexplored. Conformal prediction (CP) offers uncertainty estimation with a solid coverage guarantee under the exchangeability assumption, which requires the joint data distribution to be unchanged under permutation. However, in graph-structured time series, inherent cross-node coupling can violate the exchangeability condition, making direct application of CP unreliable. Inspired by the spectral graph theory, such coupling resides in global trends and can be characterized by the low-frequency components, while high-frequency components are nearly exchangeable. Therefore, we propose a novel concept named **S**pectral **G**raph **C**onditional **E**xchangeability (SGCE), which conditions exchangeable high-frequency components on low-frequency ones to preserve global trends and enable effective CP in the spectral domain. Based on SGCE, we further propose **S**pectral **C**onformal prediction via w**A**ve**LE**t transform (SCALE). SCALE uses graph wavelets to decompose low/high-frequency components and conformalizes high-frequency residuals via adaptive gating over a low-frequency embedding. Experimental results on real-world benchmark datasets across multiple application domains show that SCALE not only achieves valid coverage but also consistently improves the coverage-efficiency trade-off over the state-of-the-art CP methods.

Shapley additive explanations (SHAP) are widely recognised as computationally intractable for neural networks, since they induce an exponential search space over the input features. In this work, we take a first step towards scaling exact SHAP computation to larger search spaces by introducing an algorithm that leverages recent advances in neural network verification to compute arbitrarily tight exact lower and upper bounds on SHAP values for neural networks, ultimately recovering the exact SHAP values. We demonstrate that our approach scales to orders of magnitude larger search spaces than state-of-the-art exact methods. This provides an important first step towards exact SHAP computation and establishes a principled cornerstone for evaluating statistical approximation methods on larger search spaces.

We introduce NetDiff, a node-conditioned denoising diffusion model that generates directional link topologies and a two-slot transmit/receive parity for mobile ad hoc networks. Directional antennas can yield high throughput but require globally consistent link decisions under sector, interference, connectivity, and half-duplex constraints. NetDiff improves global coherence with Absolute Cross-Attentive Modulation (ACAM) tokens, which provide permutation-invariant global signals and help the model match graph-level counts (e.g., density and sector usage). We also propose partial diffusion to update an existing topology with a small number of denoising steps, enabling fast reconfiguration under mobility. NetDiff reaches over 95 \% of target performance with constant inference time, outperforms heuristic and omnidirectional baselines, and improves over a strong diffusion graph-transformer baseline on key metrics.

Handwritten Text Recognition (HTR) is computationally imbalanced in two ways: most image pixels are background, and many width-axis sequence positions are blank-dominated. This creates a mismatch for Spiking Neural Networks (SNNs): handwriting is observed as a static image, whereas spiking computation unfolds over timesteps. We propose Spike-HTR, a hybrid spiking recognizer that controls both the number of spiking steps and the number of width positions processed by the deep sequence mixer. To make a static image suitable for short-horizon spiking inference, InkCoder converts it into a coarse-to-fine input stream, where early steps cover broad stroke regions and later steps emphasize sharper stroke details. To reduce sequence computation, a CTC-guided length reducer keeps likely character or uncertain positions and compresses long blank-dominated stretches before deep mixing. With $T{=}2$, Spike-HTR trains only on target data, decodes without language models or lexicons, and reaches validation/test CERs of 3.5/5.4, 2.3/2.5, and 4.2/3.9 on IAM, LAM, and READ2016. Codes are available at https://github.com/QomolangmaH/SpikeHTR.

Federated Graph Learning (FGL) enables distributed clients to collaboratively train graph neural networks while strictly preserving data privacy. However, existing FGL methods implicitly assume the reliability of local graph structures and lack elastic awareness of parameter importance during model aggregation, leading to representation degradation under topological noise and catastrophic forgetting caused by model drift. To address these challenges, we propose GraphP-FL, a general personalized FGL framework. (1) Specifically, we design a self-supervised dynamic topology reconstruction mechanism on the client side. This mechanism mines implicit dependencies to adaptively rectify noisy topologies, effectively suppressing topological noise propagation and capturing precise structural relationships for high-quality representations. (2) Additionally, we introduce a Fisher-based Elastic Parameter Alignment (FRPA) algorithm. FRPA imposes anisotropic regularization constraints in the parameter space to precisely quantify parameter importance, enabling the model to strictly preserve critical local knowledge while flexibly aligning with the global model, thus effectively overcoming catastrophic forgetting. Extensive experiments on seven benchmarks (including biochemical molecules, social networks, and large-scale encrypted traffic) demonstrate that GraphP-FL significantly outperforms state-of-the-art methods, improving accuracy by up to 8.6% while exhibiting superior generalization and robustness.