NeurIPS 2026 Papers

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}.

Graph-level anomaly detection plays a critical role in a wide range of applications, such as fraud detection in financial networks and malicious program detection, yet it remains challenging in real-world scenarios where labeled anomalous graphs are extremely scarce and graph structures are highly diverse. Existing few-shot methods often suffer from severe performance degradation due to the effects of class imbalance and structural imbalance, and they struggle to generalize to structurally deviant or rare anomalies. In this paper, we propose an adaptive few-shot graph-level anomaly detection model with multi-view structure-aware prompting (GADMVP). To mitigate structural imbalance, we construct a graph-of-graphs representation that facilitates cross-graph message passing, capturing both intra-graph semantics and inter-graph dependencies. Building upon these priors, we introduce a structure-aware graph prompting mechanism that extracts and adaptively refines anomaly-relevant prompts from a small set of labeled graphs. Extensive experiments on multiple benchmark datasets demonstrate that the proposed method consistently outperforms state-of-the-art few-shot graph anomaly detection baselines, while exhibiting strong robustness under extremely limited labeled data. The code and implementation details are available at https://anonymous.4open.science/r/GLAD-3456543/.

The rapid deployment of generative AI has amplified the critical need for Training Data Attribution to ensure transparency and accountability. However, current parametric approaches require computationally prohibitive access to model weights, while similarity-based methods ignore deep structural context. We propose a novel probabilistic framework that operates entirely in a black-box setting. Our method fuses continuous feature similarities with discrete, domain-specific Knowledge Graphs (KGs). This approach ensures the attribution is grounded in structural reality, explicitly rewarding highly specific historical samples while preventing generic background data from dominating the results. We evaluate our framework across two distinct domains where linking outputs to data and domain context is inherently complex: abstract artistic image synthesis and high-dimensional physical weather forecasting. Extensive benchmarking demonstrates the robust efficacy of our approach. In the artistic domain, it achieves a strong Linear Datamodeling Score that exceeds standard black-box similarity baselines, while closing much of the gap to gradient-based estimators. We additionally present a cross domain feasibility case study in environmental forecasting, where we use domain KGs to retrieve physically consistent historical analogs for regional flood forecasts, improving geographic localisation over a latent-only baseline. Operating entirely without internal model access, our approach provides an efficient, interpretable mechanism for post-hoc influence analysis and domain-grounded retrieval.

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.

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.

Virtual spatial transcriptomics aims to predict spatial gene expression from histopathology images. However, gene expression is not governed by morphology alone; regulatory relationships are structured, context-dependent, and shaped by the local tissue microenvironment. Existing visual-to-expression models and fixed-prior graph methods struggle to align molecular dependencies with spatially varying histological contexts. We propose DragH2ST, a dual-stage retrieval-augmented dynamic regulatory graph learning framework that constructs task-specific regulatory manifolds and rewires them at the spot level according to local histology. During training, DragH2ST retrieves and integrates heterogeneous biomedical knowledge to build a task-specific regulatory prior, guiding gene representations toward biologically plausible and context-adaptive regulatory structures. To capture microenvironment-dependent regulation, context-gated graph rewiring performs spot-level soft rewiring of gene-regulatory edges conditioned on histology-derived context, enabling adaptive graph reasoning without dense graph reconstruction. At inference, DragH2ST retrieves morphologically similar historical spot prototypes as case-level references, providing evidence-based support for interpretation and biological plausibility assessment. Experiments on multiple benchmarks show that DragH2ST improves prediction accuracy, preserves gene-gene regulatory topology, and captures spatially heterogeneous expression patterns.

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.

Graph Domain Adaptation (GDA) aims to transfer graph classifiers across domains with both semantic and topological shifts. Existing Euclidean adversarial methods face two challenges: Structural Degeneration, where domain confusion entangles and suppresses label-relevant topology, and Optimization Instability, where minimax training induces oscillatory gradients under large structural shifts. We propose DisRFM, a geometry-aware GDA framework that addresses these challenges with Riemannian representation learning and flow-based transport. DisRFM embeds graph representations on a constant-curvature manifold and expresses them in geodesic polar coordinates. Polar endpoint regularization calibrates topologysensitive radial scales via univariate Wasserstein alignment and preserves scalenormalized class semantics through confidence-filtered angular alignment, with radial magnitude modulating pseudo-label reliability. DisRFM introduces topologyconditioned polar flow matching, which couples class-compatible source and target samples by a normalized polar transport cost and learns a metric-corrected vector field along geodesic interpolants. Theoretical analysis characterizes the structural risk of unconditional domain confusion and relates polar discrepancies and flow error to target risk. Extensive experiments under diverse domain shifts demonstrate that DisRFM consistently outperforms state-of-the-art methods.

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.

Although Vision-Language Models (VLMs) demonstrate impressive capabilities, their deployment in high-stakes domains is severely hindered by hallucinations. Existing detection methods mostly focus on static internal feature probing with coarse-grained annotations, failing to achieve fine-grained token-level localization without expensive dense labels. In this paper, we reconceptualize VLM hallucination detection as a dynamic graph learning task, identifying hallucinations as distinct *trajectory drifts* across network layers. Consequently, we propose **TRACE** (Token Representation Analysis with Cross-layer Evolution), a non-intrusive probing framework that models internal states as heterogeneous spatio-temporal graphs. By employing Graph Neural Networks (GNNs) to capture computational dynamics, TRACE effectively isolates hallucinatory signals. Furthermore, a token-first Multiple Instance Learning (MIL) readout elegantly bridges the granularity gap, distilling macroscopic sentence-level supervision into precise zero-shot token-level localization. Extensive evaluations on M-HalDetect, ViGoR, and HalLoc demonstrate that TRACE achieves state-of-the-art detection performance while being competitive in localization accuracy, offering an efficient and interpretable solution for trustworthy VLMs.

Graph Neural Networks (GNNs) are effective for modeling relational data but are vulnerable to label poisoning, where a small number of corrupted training labels can propagate errors across the graph via message-passing. Despite this risk, defenses against label poisoning remain underexplored: existing methods are primarily designed for label noise and often rely on robust losses or heuristic data cleaning that fail to distinguish adversarial poisoning from naturally hard examples. In this paper, we propose CoLAT (Contrastive Label-flipping for Adversarial Training), a novel contrastive adversarial training framework tailored for robust node classification on graphs. The core of our approach is a structure-aware detection model that uses contrastive learning to identify label–structure inconsistencies. Unlike prior contrastive methods that focus on representation learning, CoLAT leverages contrastive embeddings to select high-risk nodes that guide adversarial label-flipping during training. This alternating optimization not only performs structure-aware adversarial training but also implicitly sanitizes corrupted labels, improving robustness against diverse attacks from the literature. Extensive experiments on multiple benchmarks show that CoLAT consistently outperforms existing defenses under various poisoning intensities while scaling efficiently to large graphs.

Graph neural networks exhibit a fragile relationship with depth, as adding layers leads to rapid homogenization of node representations (over-smoothing). Recent manifold-constrained approaches using doubly stochastic matrices address this issue, but the fundamental principle underlying their success remains unclear. This study investigates whether doubly stochasticity is essential or exemplifies a broader geometric principle for stable residual propagation in deep GNNs.We formalize three axioms to define residual mixing matrices as contractive monoids. We instantiate this framework through three manifolds (Orthogonal Group, Diagonal Contraction Monoid, Spectral Norm Ball) and evaluate them across nine node-classification benchmarks using four GNN backbones. Results demonstrate that contractive-monoid constraints maintain stable accuracy and low representational collapse at extreme depths, while standard GNNs degrade sharply beyond moderate depth. This work establishes that stable residual propagation arises from contractive, compositional structure anchored at identity, revealing a significantly larger design space for deep GNN architectures while maintaining theoretical guarantees.

Scaling Transformers to long contexts is constrained by the quadratic cost of self-attention and the linear growth of key-value cache memory transfer. Sparse attention mitigates this by retrieving only relevant tokens, but current approaches either require large-scale training or, within the training-free regime, rely on semantically coarse heuristics or expensive clustering that is difficult to update efficiently during decoding. We introduce CommunityKV, a framework that formulates sparse attention as a community detection problem. CommunityKV constructs a token graph from the $QK^T$ scores already computed during standard prefill, and partitions the graph into communities to enable retrieval of semantically coherent token groups. A local update rule assigns newly generated tokens to communities in constant time, enabling sparse retrieval throughout streaming decoding without global re-partitioning. We evaluate CommunityKV on open weight models and long context benchmarks, demonstrating that our approach achieves up to $1.86\times$ higher decoding throughput than exact FlashAttention-2 with negligible accuracy degradation.

For the combinatorial graph alignment problem (GAP) --- finding the node correspondence that maximizes the number of common edges between two unlabeled graphs --- properly initialized FAQ remains a strong classical baseline, while existing GNN approaches struggle in the purely structural setting. We introduce a chaining procedure: a sequence of Folklore-type (2-FWL) GNNs in which each network is trained with cross-entropy after decoding the previous network's similarity matrix and ranking nodes by their current alignment quality. This non-differentiable ranking step injects discrete combinatorial feedback at every link; at inference, we iterate the final network and keep the candidate with highest observed nce. On sparse Erdos--Renyi graphs at noise level 0.25, chained FGNNs with FAQ post-processing reach $85\%$ accuracy versus 13% for FAQ initialized from the convex relaxation. On correlated regular graphs, where constant-feature MPNNs collapse to uninformative similarities and FAQ's convex initialization is degenerate, chaining recovers non-trivial alignments among the methods we evaluate. On three real-world benchmarks (yeast PPI, coauthorship, and road networks), dataset-specific chained FGNNs provide modest gains over a properly initialized FAQ baseline.