NeurIPS 2026 Papers

Graph classification benchmarks vary widely in difficulty: some are solved by simple pooled baselines, while others remain challenging for GNNs and graph transformers. We take a data-centric view and ask whether benchmark success is driven by genuine structure-feature reasoning or by label signal already accessible from restricted marginal views. We introduce **graph label alignment**, a lightweight diagnostic that measures label accessibility through two supervised probes computed without training a graph encoder: *structural label alignment* (SLA), based on permutation-invariant topological and spectral summaries, and *feature label alignment* (FLA), based on pooled node features with edges removed. Across real graph classification benchmarks and multiple pooled backbones, the resulting SLA-FLA plane strongly organizes test accuracy, with low-alignment datasets forming a consistent regime where standard pooled pipelines struggle. To probe what lies beyond marginal accessibility, we introduce controlled interaction-dominated stress tests, including heterophilic ego-graphs and synthetic *Twins* tasks whose structural and feature marginals are matched across classes but whose role-feature couplings differ. These results show that high alignment explains much of easy benchmark performance, while low alignment reveals regimes where success requires preserving structure-feature correspondence beyond standard pooled representations.

We introduce **Graph Cascades**, a mesoscopic rewiring strategy for Graph Neural Networks (GNNs) and Graph Transformers (GTs) that captures intermediate-scale graph structure beyond purely local edges or fully global attention. Using contagion-based diffusion processes, Graph Cascades constructs, in $\mathcal{O}(|V|+|E|)$ time, an auxiliary graph where node pairs supported by repeated multi-hop reinforcement are promoted to direct neighbors. We theoretically characterize when reinforcement-based rewiring helps: sufficient conditions under which a reinforcement-based edge-selection rule has higher label agreement than direct adjacency, an SBM witness in which two-hop reinforcement is perfectly homophilic, and formalizing mesoscopic connectivity via graph effective resistance. Empirically, across node-classification benchmarks, Graph Cascades improves multiple GNN and sparse-GT backbones, with the most reliable gains observed on heterophilic and moderate- to high-degree homophilic graphs. The theoretical conditions also identify regimes where mesoscopic rewiring is unlikely to be beneficial -- low-degree regular graphs and graphs with structural bottlenecks -- and these predictions match the observed failures. We additionally observe tight correlations between performance and structural properties in the rewired graphs.

Deployed Graph Neural Networks are increasingly subject to post-deployment interventions: a sensitive attribute is flagged for removal, or a spurious correlation is discovered after the model is already in production. In such scenarios, retraining is often infeasible due to a variety of reasons including scale of modern graphs, inaccessible training data, or strict privacy mandates. The challenge is further compounded in graph-structured data, where attribute dependencies propagate through message-passing, spreading unwanted correlations across the entire network. We propose a framework for surgical, post-hoc attribute invariance in GNNs via gradient-free model editing. Rather than retraining or fine-tuning, our method formulates the edit as a subspace-constrained, closed-form optimization: we identify structurally influential nodes that exhibit high attribute sensitivity, isolate the low-rank manifold in activation space where sensitive variation is concentrated, and solve directly for a weight update that decouples the model's decision logic from the target attribute. The update requires no access to original training labels, introduces no additional parameters, and is computed in a single pass. Empirical results demonstrate that our method enforces attribute invariance while preserving predictive utility, while offering 3 orders of magnitude speed-up over existing GNN editing approaches.

Finding frequently occurring subgraph patterns or network motifs in neural architectures is crucial for optimizing efficiency, accelerating design, and uncovering structural insights. However, as the subgraph size increases, enumeration-based methods are perfectly accurate but computationally prohibitive, while sampling-based methods are computationally tractable but suffer from a severe decline in discovery capability. To address these challenges, this paper proposes GraDE, a diffusion-guided search framework that ensures both computational feasibility and discovery capability. The key innovation is the $\underline{\textnormal{Gra}}\textnormal{ph}$ $\underline{\textnormal{D}}\textnormal{iffusion}$ $\underline{\textnormal{E}}\textnormal{stimator}$ (GraDE), which is the first to introduce graph diffusion models to identify frequent subgraphs by scoring their typicality within the learned distribution. Comprehensive experiments demonstrate that the estimator achieves superior ranking accuracy, with up to 114\% improvement compared to sampling-based baselines. Benefiting from this, the proposed framework successfully discovers large-scale frequent patterns, achieving up to 30$\times$ higher median frequency than sampling-based methods.

Existing Retrieval-Augmented Generation (RAG) systems struggle with multi-hop reasoning due to a fundamental inability to balance relevance and novelty. Traditional dense retrievers are constrained by surface-level matching, falling into a homogenized "Similarity Trap". Conversely, emerging Graph RAGs attempt to explore novel documents via heuristic entity extraction, but they introduce prohibitive Large Language Model (LLM) overhead and easily drift into off-topic "Novelty Traps". To fundamentally resolve this contradiction, we propose Geometric Gain Graph (G$^3$RAG), the novel zero-token graph construction paradigm for RAG. G$^3$RAG completely discards the expensive heuristic extraction by LLMs, aiming instead to directly quantify the information gain between nodes through the native document feature space. To this end, we designed a concise edge weight criterion, $\cos\theta \cdot \sin\theta$, which naturally maps the trade-off between relevance and novelty into a geometric measurement of directional consistency and orthogonality in the vector space, thereby driving the token-free topological construction of the graph. Furthermore, we introduce a topological penalty to suppress the excessive connectivity of high-frequency hubs, forcing the transient diffusion process toward long-tail peripheral nodes that carry critical indirect evidence. Extensive experiments demonstrate that, while entirely eliminating graph construction costs, G$^3$RAG significantly outperforms state-of-the-art Graph RAG baselines on complex multi-hop QA benchmarks.

Test-Time Scaling (TTS) improves large language models (LLMs) by allocating additional computation during inference, typically through parallel, sequential, or hybrid scaling. However, prior studies often assume fixed collaboration architectures (e.g., topologies) and single-model usage, overlooking that optimal architectures and model combinations can vary across tasks. Therefore, we study the novel problem of \textit{searching for compute-optimal model combinations and architectures in TTS under a fixed budget.} We formalize it as a multi-LLM collaboration graph, where nodes encode roles, and LLM model assignments, and edges capture information flow. This problem is challenging because (i) the combinatorial search space is prohibitively large, and (ii) task-specific requirements demand tailored designs. To this end, we formulate the problem as probabilistic graph optimization and, via pilot experiments, derive three empirical insights into TTS collaboration graphs. Guided by these insights, we propose Agent-REINFORCE, an LLM-agent-augmented framework that mirrors the REINFORCE pipeline by mapping \emph{sampling–gradient–update} to \emph{sampling–feedback–update}, where feedback serves as a textual gradient to update the probabilistic graph and efficiently search for optimal multi-LLM collaboration graphs. Experiments show that Agent-REINFORCE outperforms both traditional and LLM-based baselines in sample efficiency and search performance, and effectively identifies optimal graphs under joint objectives of accuracy and inference latency.

Neural operators on irregular meshes face a fundamental tension. Spectral positional encodings, the natural choice for capturing geometry, require cubic-complexity eigendecomposition and inadvertently break gauge invariance through numerical solver artifacts; existing efficient approximations sacrifice gauge symmetry by design. Both failure modes break discretization invariance: models fail to transfer across mesh resolutions of the same domain, and similarly across different graphs of related structure in inductive settings. We propose GIST (Gauge-Invariant Spectral Transformer), a scalable neural operator that resolves this tension by restricting attention to pairwise inner products of efficient approximate spectral embeddings. We prove these inner products estimate an exactly gauge-invariant graph kernel at end-to-end $\mathcal{O}(N)$ complexity, and establish a formal connection between gauge invariance and discretization-invariant learning with bounded mismatch error. To our knowledge, GIST is the first scalable graph neural operator with a provable discretization-mismatch bound. Empirically, GIST sets state-of-the-art on the AirfRANS, ShapeNet-Car, DrivAerNet, and DrivAerNet++ mesh benchmarks (up to 750K nodes), and additionally matches strong baselines on standard graph benchmarks (e.g., 99.50\% micro-F1 on PPI).

Real-world networks typically exhibit small-world properties: dense local clustering yet efficient global propagation. However, current methods struggle to reconcile this hierarchy: Graph Neural Networks (GNNs) suffer from over-smoothing in long-range modeling, while sequence/state-space models often lack the inductive bias to preserve complex graph topology. To bridge this gap, we propose Graph Encoding Mamba (GEM), a dual-scale architecture for graph-level hierarchical representation learning. First, GEM employs a dual-branch encoder that synergizes the local sensitivity of GNNs with the selective scanning of Mamba, effectively capturing both local topology and global shortcuts. Second, a modularity-aware hierarchical pooling mechanism is designed to retain salient community structures during graph coarsening. Crucially, to mitigate structural redundancy from multi-scale fusion, we incorporate an Information Bottleneck objective to distill task-relevant structural patterns from redundant features, encouraging compact, task-relevant representations and supporting intrinsic interpretability. Extensive experiments on graph-level benchmarks demonstrate that GEM improves performance across biological, social, and brain network datasets. We further provide a lightweight node-level adaptation on long-range benchmarks as a boundary analysis of GEM's transferability. Code is available at \url{https://anonymous.4open.science/r/GEM-C34D}.

Link prediction is a standard pretraining objective for graph neural networks: hide edges, train an encoder--decoder to predict them, and reuse the node embeddings for downstream node tasks. Despite its empirical success, there is little quantitative theory explaining why an edge-level objective should produce embeddings that are linearly useful for node classification.We study this question in the finite-sample stochastic block model (SBM). For any bounded GNN encoder paired with a symmetric bilinear decoder, we prove a conditional reduction: small population held-out LP excess risk implies small community-classification error for a transductive linear classifier on the learned embeddings.The bound decomposes into an optimization residual, an architectural approximation residual, and explicit statistical terms of order $\widetilde{O}(\sqrt{d/n})$ in bounded dense regimes. We further give a constructive few-label classifier: nearest-centroid classification under the PSD quadratic form $G = W Z^\top Z W$, whose label error is coupled to LP quality.The framework is architecture-agnostic through the approximation residual, and we instantiate this residual as $O(\log n / n)$ for a spectral-positional-encoding GIN with a bilinear decoder. Synthetic SBM experiments validate the theorem chain from LP risk to score error to classification error, and show when the worst-case constants become conservative.

Federated Graph Learning (FGL) aims to collaboratively train Graph Neural Networks (GNNs) across distributed subgraphs with a primary challenge of missing cross-client connections. Existing approaches predominantly rely on a retrieval-based paradigm, which reconstructs missing context by accessing external information across clients. However, such cross-client transmissions inevitably expand the attack surface for privacy inference and incur significant communication overhead. In this work, we propose \textbf{FedLMC}, a novel framework that eliminates the necessity of any node information sharing and prior global adjacency knowledge. FedLMC exploits a dual-stage message compensation mechanism to generate informative and expressive node representations. For the semantic information loss of external neighbors, we propose Local Semantic Compensation, which exploits semantic expansion via semantic surrogates to compensate for missing semantic context. For the structural information loss induced by semantic expansion, we propose Community Structural Compensation, which exploits structural anchoring via community anchors to compensate for underlying structural context. Extensive experiments on twelve datasets (both homophilic and heterophilic) demonstrate that FedLMC establishes a new state-of-the-art performance with superior generalization and robustness to highly fragmented graph data.

We study clustering algorithm for dynamic evolving graphs $\{ G_t\}$, in which new edges (and potentially new vertices) are added into a graph, and the underlying cluster structure of the graph gradually changes over time. By designing a hierarchical data structure for dynamically maintaining the cluster structure of $\{ G_t\}$, we prove that the cluster structure of $G_T$ can be maintained with $O(d)$ amortised update time and $\widetilde{O}\left(n_T^{1/d}\right)$ amortised query time, for an arbitrary large constant $d$. This significantly improves the previous state-of-the-art (Laenen and Sun, ICML~'24), which requires $O(1)$ update time and $O(n_T/\log n_T)$ amortised query time. We further demonstrate this improvement with experiments on both synthetic and real-world datasets.

The expressive limitations of message-passing Graph Neural Networks (GNNs) have motivated a wide range of more powerful graph learning architectures. We advocate Deep Homomorphism Networks (DHNs) as a model particularly well-suited for learning over relational databases, due to their close connection to important fragments of SQL such as conjunctive queries. We study the precise expressive power of DHNs by relating them to various natural fragments and extensions of first-order logic (FO). For DHNs with max, sum, and mean aggregations, we establish connections to the unary negation fragment (UNFO) and to the extensions of UNFO with counting quantifiers and with ratio quantifiers. We further relate sum-aggregation DHNs to the unary quantifier alternation fragment of FO and to an extension of FO with expressive counting. Through the classical correspondence between FO and SQL, these results also illuminate the relation between DHNs and SQL. They also enable us to study the decidability of two fundamental static analysis problems for DHNs, the emptiness problem and the subsumption problem. Finally, we confirm through experiments that the established differences in expressive power are reflected in the performance on suitable prediction tasks.

Federated graph clustering (FGC) aims to partition distributed graphs into different groups while preserving data privacy. Existing FGC methods focus on spatial-domain information aggregation, while how to use expressive spectral-domain signals of graphs for FGC still remains unexplored. Main challenges are twofold: (1) Collecting and integrating semantic signals that fully express the critical patterns of graphs; (2) Obtaining spectral consensus while preserving local properties of clients. To address these challenges, we propose dynamic spectral federated graph-level clustering (DySFGC). DySFGC designs learnable polynomial filters to capture abundant graph signals and employs spectral contrastive learning and reconstruction to explore the latent semantic information. Besides, DySFGC develops dynamic spectral consensus, which updates the consensus via frequency-specific channels and conducts the dynamic updating process by evaluating the discrepancies between the server and clients. Extensive experiments on fifteen datasets demonstrate the superiority of DySFGC over eleven baselines.

Existing graph neural network-based methods for Boolean satisfiability (SAT) solving are generally constrained by limited local receptive fields, making it difficult to adequately capture the long-range dependencies between variables and clauses in SAT instances. Moreover, these methods overlook the multi-solution nature of SAT instances. Consequently, their expressive power and generalization performance remain limited. To address these issues, we propose DualSAT, a novel neural framework for the SAT problem, designed to enhance the phase selection heuristic of SAT solvers. Specifically, DualSAT adopts a novel dual-branch graph neural network that separately encodes local structural information and global structural information in the graph, and then fuses them through an attention-based cross-branch feature fusion module. An assignment decision head is further introduced to generate the initial assignment prediction of variables. This prediction process requires only a single forward pass, achieving a favorable balance between expressive power and inference efficiency. Furthermore, to account for the multiple solutions nature of SAT instances, we design a two-stage training strategy that combines supervised and unsupervised learning to improve the generalization performance of the model. Experimental results on multiple datasets show that, as an end-to-end assignment prediction model, DualSAT significantly outperforms NeuroSAT and NeuroBack. In addition, we integrate DualSAT into the classical SAT solver CaDiCaL, where it increases the number of solved instances by up to 11.6% and reduces the number of conflicts by up to 9.21% on SAT competition problem sets.

We study the ability of graph neural networks (GNNs) to learn generalizable algorithms for graph clustering. While previous work has shown that GNNs can learn to cluster graphs in-distribution, it is unclear exactly what algorithms these networks are learning, or whether they generalize to unseen graphs that differ significantly from their training data. In this paper, we pick a standard cut-based clustering cost function and train GNNs of various types to minimize this function on a suite of training examples. We then test whether the resulting networks are able to generalize to much larger graphs, or other families of graphs. We complement our empirical findings with a host of theoretical results that illustrate the range of possible heuristics that these different GNNs could be implementing. Finally, we use probes on trained networks to narrow down the heuristics actually being learned. Our findings show that there is generalization across the board but that GNNs of different expressivity---MPNNs versus PPGNs, for instance---learn markedly different algorithms.

GNN-to-MLP distillation aims to retain the predictive accuracy of a message-passing teacher while deploying a graph-free MLP at inference. Existing methods mainly transfer node-wise predictions or use confidence-based reweighting, but they do not specify where the student should preserve the teacher's graph-induced geometry. We show that this omission leads to two spectral failure modes in the student's representation space. On sparse graphs, the student suffers from *spectral underfit*, missing high-energy teacher directions concentrated near boundary regions. On dense graphs, it suffers from *spectral overfit*, retaining spurious directions that the teacher has collapsed through aggregation. Motivated by an energy-weighted teacher--student alignment objective, we propose **Graph Geometry-aware MLP (G$^2$MLP)**, a training-time distillation framework guided by Ollivier--Ricci curvature. Curvature identifies where the two spectral errors concentrate and is used to allocate supervision between prediction-level and representation-level alignment. The deployed model remains a standard MLP and requires no graph access at inference. Across node-classification benchmarks, G$^2$MLP consistently improves over graph-free distillation baselines, reduces the teacher--student rank gap in both regimes, and transfers without architectural changes to Graph Transformer teachers and link prediction.

Architecture attribute predictors reduce the cost of neural architecture search by estimating accuracy or latency from a small set of evaluated candidates. The key difficulty is that neural architectures are operation-labeled DAGs: edge direction defines computational flow, but existing predictors often treat direction as a local structural cue. We propose DTA-GT, a Direction- and Topology-Aware Graph Transformer based on encoder-wide directional consistency, which preserves directed computational semantics across node initialization, global spectral encoding, pairwise interaction, and feature update. DTA-GT realizes this principle with direction- and topology-aware node initialization, Magnetic Laplacian spectral encoding, direction-dual structural attention, and a Direction-Sensitive MoE-FFN. Across accuracy and latency prediction on NAS-Bench-101 and NAS-Bench-201, DTA-GT consistently outperforms representative sequence-, GNN-, Transformer-, and hybrid predictors under limited-budget settings. Ablations and Magnetic spectral controls show that the improvements come from coordinated direction-aware stages and edge-orientation-sensitive spectral information, while mechanistic diagnostics confirm that the modules exhibit the intended directional behavior. These results support encoder-wide directional consistency as an effective design principle for architecture DAG representation.

Existing deep learning architectures for survival prediction from electronic health records (EHRs) largely assume unimodality, failing to capture the complex relational structure across diverse clinical modalities. Graph learning can allow us to robustly adapt to the underlying clinical structure of the data to have more predictive and interpretable representations for time-to-event analysis. However, unconstrained graph learning produces dense, bidirectional adjacencies that overfit. We introduce M-CADENCE, a multimodal survival model that integrates structured acyclic priors with attention-based propagation. Each modality has its own learnable adjacency, regularised toward acyclicity through a log-determinant characterisation and toward sparsity through soft thresholding. A cross-modal meta-adjacency keeps the cross-modal parameter count quadratic in the number of modalities rather than in their feature dimensions. Propagation is then performed by multi-head attention biased by the learnt structure. The propagation step degrades gracefully under sparse or misspecified structure, addressing a known weakness of hard-routing graph variants. We evaluate M-CADENCE on five EHR benchmarks covering intensive-care mortality, circulatory failure, and emergency-department competing risks, against multiple survival, graph, and structure learning baselines. M-CADENCE achieves the best concordance on all datasets, the best early-warning AUC on four of five, and competitive precision-recall against the strongest deep survival baselines. Removing the DAG bias lowers concordance, as does substitution with a density-matched random adjacency, which confirms that the specific learnt structure is required. Discrimination is stable across four orders of magnitude in regularisation strength, and evaluation by a panel of ten language models confirms M-CADENCE learns clinical edges that are more physiologically plausible than baseline structure-learning methods.

Graph matching aims to establish node correspondences while preserving both unary appearance compatibility and pairwise structural consistency. Recent deep graph matching methods have achieved strong empirical performance, but many of them either compress edge information into node embeddings before matching or rely on surrogate optimization signals for quadratic objectives. These design choices can weaken structural discrimination and may lead to optimization directions that are not aligned with the relaxed quadratic assignment problem (QAP). We propose Cross-order Consensus Graph Matching (CCGM), a framework that explicitly couples first-order node assignment and second-order edge assignment. CCGM constructs line graphs to convert edge matching into a node matching problem, learns node and edge affinities in parallel, and refines them through a Cross-order Consensus Solver motivated by the exact gradient of the factorized relaxed QAP. We further introduce Cross-order Alignment Regularization to encourage agreement between node-induced edge assignments and edge-induced node support during training. Experiments on standard visual graph matching benchmarks show that CCGM consistently improves matching accuracy over competitive baselines.