NeurIPS 2026 Papers

Graph Neural Networks (GNNs) operate under the implicit assumption that the underlying data manifold is Riemannian, where the metric tensor is strictly positive-definite. While effective for homophilic graphs, this inductive bias creates a fundamental geometric mismatch for heterophilic graphs, where edges often signify dissimilarity or structural repulsion. In this work, we propose a paradigm shift from learning on fixed manifolds to learning the manifold itself. We postulate that heterophilic graphs are naturally embedded in pseudo Riemannian manifolds endowed with an indefinite metric, allowing for negative squared distances to model repulsive interactions. To formalize this, we introduce the Graph Signature Index, a spectral invariant that diagnoses the geometric nature of a graph. This index enables our proposed Pseudo-Riemannian Attention Network (PRAT) to dynamically learn an indefinite metric tensor, effectively capturing both attractive and repulsive interactions. By unifying these opposing forces within a single framework, PRAT demonstrates how a subtle shift in the metric signature yields substantial performance gains on heterophilic benchmarks. Our analysis reveals that PRAT’s learned geometry emergently aligns with the spectral signature of the graph, validating our geometric hypothesis.

GraphRAG enhances Large Language Model reasoning by organizing retrieved knowledge into structured evidence graphs, enabling inference over connected evidence rather than isolated text fragments. Yet, existing GraphRAG methods often either miss query-critical links or introduce noisy or conflicting evidence that distracts reasoning. We propose CONSIST, a Conflict-aware Nash-optimized Minimal Sufficient graph learning algorithm that regulates evidence graphs to resolve conflicts during reasoning. Specifically, we cast graph learning as an exploration–editing process, where a candidate graph is expanded via structural and semantic connections and then refined by pruning unreliable edges. We further introduce Gumbel-based edge editing, framing it as a Nash-guided bargaining process, where current and future players negotiate over a customized utility to determine reliable edits that improve both immediate answer support and long-term graph quality. Experiments on multi-hop question answering and conflict-aware benchmarks demonstrate that CONSIST consistently outperforms recent state-of-the-art baselines, achieving average performance gains up to 7.0% EM and 6.3% F1. Moreover, CONSIST also produces substantially more compact evidence graphs, reducing retained nodes by 42.9% and edges by 54.7% on average.

We study label-free, topology-conditioned zero-shot cross-graph link prediction: at test time the observed target topology is the input graph, but the model receives no target labels, no positive/negative context links, no target fine-tuning, no text attributes, and no post-hoc alignment. This setting is zero-shot with respect to target supervision and adaptation, but it is not topology-free inference. We identify a critical geometric barrier for hyperbolic transfer: radial non-identifiability. Hyperbolic graph learning is motivated by the intuition that radius encodes hierarchy or popularity and angle encodes similarity, yet standard HGNN objectives do not make radii semantically calibrated across disjoint graphs. The same structural role can therefore occupy incompatible radial scales on different target graphs. We propose Invariant Hyperbolic Unfolding (IHU), which restores the intended radial hierarchy channel through selective invariance: radii are fixed by graph-internal structural percentiles while angular representations remain learnable. Its core module, Invariant Structural Anchoring (ISA), rank-canonicalizes structural scores such as coreness into shared hyperbolic radii, producing a comparable radial skeleton without target supervision. In a controlled comparison among matched frozen learned encoders, IHU improves average HR@50 by 2.7 percentage points over the strongest learned hyperbolic baseline and by 7.6 percentage points over the mean of the learned hyperbolic baseline family. The gain amplifies under missing-edge and low-degree regimes, while hierarchy-gap analysis reveals a boundary condition for fixed radial shells: 50% edge sparsification causes 52.5% less degradation, and low-degree nodes show a 4.2× larger advantage. We further position IHU against recent universal link prediction and graph foundation methods through an access-aware taxonomy, showing that the closest recent LP methods use labeled target context links, whereas IHU isolates the geometric effect of fixed versus learned radii in frozen structural hyperbolic encoders.

Inferring latent interaction structures from observed dynamics is a fundamental inverse problem in many-body interacting systems. Most neural approaches rely on black-box surrogates over trainable graphs, achieving accuracy at the expense of mechanistic interpretability. Symbolic regression offers explicit dynamical equations and stronger inductive biases, but typically assumes known topology and a fixed function library. We propose $\textbf{COSINE}$ ($\textbf{C}$o-$\textbf{O}$ptimization of $\textbf{S}$ymbolic $\textbf{I}$nteractions and $\textbf{N}$etwork $\textbf{E}$dges), a differentiable framework that jointly discovers interaction graphs and sparse symbolic dynamics. To overcome the limitations of fixed symbolic libraries, COSINE further incorporates an outer-loop large language model that adaptively prunes and expands the hypothesis space using feedback from the inner optimization loop. Experiments on synthetic systems and large-scale real-world epidemic data demonstrate robust structural recovery and compact, mechanism-aligned dynamical expressions. Code: https://anonymous.4open.science/r/COSINE-6D43.

Existing research infrastructure is fundamentally document-centric, providing citation links between papers but lacking explicit representations of methodological evolution. In particular, it does not capture the structured relationships that explain how and why research methods emerge, adapt, and build upon one another. With the rise of AI-driven research agents as a new class of consumers of scientific knowledge, this limitation becomes increasingly consequential, as such agents cannot reliably reconstruct method evolution topologies from unstructured text. We introduce Intern-Atlas, a methodological evolution graph that automatically identifies method-level entities, infers lineage relationships among methodologies, and captures the bottlenecks that drive transitions between successive innovations. Built from $1{,}030{,}314$ papers spanning AI conferences, journals, and arXiv preprints, the resulting graph comprises $9{,}410{,}201$ semantically typed edges, forming a queryable causal network of methodological development. To operationalize this structure, we further propose a self-guided temporal tree search algorithm for constructing evolution chains that trace the progression of methods over time. We evaluate the quality of the resulting graph against expert-curated ground-truth evolution chains and observe strong alignment. In addition, we demonstrate that Intern-Atlas enables downstream applications in idea evaluation and automated idea generation. We position methodological evolution graphs as a foundational data layer for the emerging field of automated scientific discovery.

Scaling Graph Neural Network (GNN) training to large graphs commonly relies on mini-batch sampling, but incomplete neighborhoods can degrade approximation quality and training stability. Memory-enhanced methods mitigate this issue by reusing historical node embeddings to approximate full-neighborhood aggregation; however, they reconstruct pseudo full-neighborhood messages inside every training iteration, repeatedly fetching out-of-batch memories and aggregating over large neighborhoods. In this work, we identify this under-examined inner-loop bottleneck and propose IncAgg, an efficient memory-enhanced GNN training framework based on incremental aggregation. IncAgg periodically pre-aggregates historical embeddings into a global memory baseline, and during mini-batch training propagates only the current in-batch residual before fusing it with the stored global context. This design preserves historical full-neighborhood information at a configurable refresh frequency while avoiding per-iteration out-of-batch memory fetching and aggregation, without modifying the underlying GNN architecture. We provide theoretical analyses showing that IncAgg reduces gradient-carrying aggregation and memory-access costs while retaining the residual-based stability principle of memory-enhanced estimators. Extensive experiments on four large-scale benchmarks and four representative GNN backbones show that IncAgg matches or improves the accuracy of strong memory-enhanced baselines while achieving substantial training acceleration, with up to $18.6\times$ speedup in individual settings and up to $13.8\times$ geometric-mean speedup on large graphs.

For graph node classification, calibrated class probabilities are need when confidence scores, usually the maximum predicted class probability, are used to rank prediction, defer uncertain nodes to human review or control risk. Existing post-hoc calibrators either apply one global temperature or use graph-awared modules without a derived strctural form. We study node-level calibration for graph node-classification problem under structural heterogeneity. Our first results show that a logit-only temperature rule is insufficient when nodes with identical logits but different local homophily require different optimal temperatures. We then analyze a population-concentration contextual stochastic block model with Gaussian features and a one-layer linear GCN. Under equidistant class means, the Bayes posterior over class-template scores is a temperature-scaled softmax whose inverse temperature is governed by homophily-dependent signal strength. In the positive-signal homophilic regime, the resulting temperature decreases approximately with normalized local homophily. This law motivates Homophily-aware Temperature Scaling (HoTS), a simple post-hoc calibrator that assigns each node a positive scalar temperature from entropy-based logit concentration and estimated local homophily. HoTS has three parameters, preserving class, and learn the strength of the structural correction from calibraion data. Across 18 node-classification benchmarks, two GNN backbones, and eight calibration baselines, HoTS achieves the best mean Expected Calibration Error (ECE) of $4.66\%$, the best average rank, and the strongest confidence ranking in selective classification.

Forecasting the behavior of spatio-temporal systems often requires more than accurate predictions: models should uncover the dynamical modes governing future evolution. Existing temporal graph and latent dynamical models achieve strong forecasting performance, but their latent representations often entangle multiple dynamical patterns, limiting interpretability. Conversely, regime-inference methods explicitly model such modes but typically do not support generative forecasting over graph-structured systems. We introduce HERON, a self-supervised regime-aware generative framework that unifies graph-structured trajectory generation with regime identification. HERON factorizes the latent state into discrete system-level regimes, capturing global dynamical modes, and continuous entity-level dynamics, yielding a modular regime interface compatible with existing spatio-temporal backbones. Crucially, the inferred regime actively conditions system dynamics, enabling regime tracking and controlled simulations under alternative dynamical modes. Without regime annotations, HERON jointly learns forecasts and regime dynamics in a self-supervised manner, recovering meaningful modes across controlled synthetic and real-world datasets while maintaining competitive forecasting performance. These results open a path toward interpretable, controllable generative modeling of spatio-temporal dynamics.

Hierarchical graph-level tasks that require reasoning over substructures that extend beyond local neighborhoods are posing challenges for standard Graph Neural Networks (GNNs). While graph pooling aims to address this by coarsening graphs into hierarchical representations, existing methods often fail to explicitly preserve the substructures they induce, leading to inconsistent empirical performance. Moreover, the evaluation of such approaches has proved difficult due to the lack of benchmarks with explicit hierarchical structure. We propose Pooled-Substructure-Aware GNNs, an approach to graph pooling that explicitly preserves and processes substructures uncovered by structure-based pooling schemes. We show that this design strengthens pooling in terms of Weisfeiler-Lehman (WL) expressivity. To enable principled evaluation of pooling-based models, we introduce two new synthetic datasets with controllable hierarchical structure and propose a metric to characterize the extent of hierarchical patterns in real-world graph-level benchmarks. On tasks with relevant hierarchical structure, our approach outperforms matched pooling baselines, while remaining competitive on structurally simpler benchmarks.

Knowledge graph question answering (KGQA) systems are typically evaluated on questions whose surface tokens lexically expose the gold KG path. Real users, however, ask questions without knowing the underlying schema: "Which condition could Andrew have due to family history?" compresses a 4-hop chain (Andrew - father → father → medical condition → subclass of - hereditary disorder) into a single phrase (family history) whose tokens name none of those relations. We show that this collapse of path-question alignment is a blind spot of existing KGQA evaluation. The three dominant Large Language Model (LLM)-KG paradigms — hop-by-hop KG exploration, plan-then-retrieve, and similarity-based retrieval — all implicitly rely on the question's surface leaking the gold path, an assumption rarely tested in practice. We make three contributions. (i) HiddenPathQA, a human-validated KGQA benchmark of 1,055 multi-hop questions (2-6 hops, multiple domains) constructed so that the question surface does not leak the gold KG path's relations. (ii) Holistic Path Selection, a reasoning paradigm that exposes all candidate relation chains around the topic entity to the LLM at once, replacing per-hop relation scoring with question-against-full-chain alignment. Two implementations, TieredHolistic and FlatHolistic, outperform six strong baselines (ToG, PoG, FiDeLiS, R2-KG, KAPING, KARPA) on HiddenPathQA by +8.8 to +17.9 points over the strongest baseline across all four (backbone × split) settings. (iii) A pseudoword stress test that replaces entity surfaces with placeholder tokens. It both confirms HiddenPathQA items are solvable from KG structure alone — not from entity-level priors — and reveals that several baselines rely on entity memorization rather than KG-grounded reasoning.

The advancement of graph-based malware analysis is critically limited by the absence of large-scale datasets that capture the inherent hierarchical structure of software. Existing methods often oversimplify programs into single-level graphs, failing to model the crucial semantic relationship between high-level functional interactions and low-level instruction logic. To bridge this gap, we introduce HiGraph, the largest public hierarchical graph dataset for malware analysis, comprising over 200M Control Flow Graphs (CFGs) nested within 499K Function Call Graphs (FCGs). This two-level representation preserves structural semantics essential for building robust detectors resilient to code obfuscation and malware evolution. We demonstrate HiGraph’s utility through a large-scale analysis that reveals distinct structural properties of benign and malicious software, establishing it as a foundational benchmark for the community. The dataset and tools are publicly available at https://higraph.org.

Many real-world heterogeneous graphs exhibit pronounced heterophily, where connected nodes often have dissimilar labels or play different semantic roles. In such settings, standard heterogeneous graph neural networks that aggregate messages along metapaths or meta-relations primarily based on feature similarity can propagate misleading information, since feature similarity may be misaligned with underlying relational semantics. In this paper, we propose **HeterSEED**, a semantics–structure decoupling framework for heterogeneous graph learning under heterophily. HeterSEED decouples representation learning into a heterogeneous semantic channel that captures type- and relation-aware local semantics and a structure-aware heterophily channel that separates homophilic and heterophilic neighborhoods via pseudo-label-guided partitioning and aggregates them using metapath-based structural weights. A node-level adaptive fusion mechanism then combines the two channels to produce context-dependent node representations. Theoretically, we establish that, on heterogeneous graphs under heterophily, HeterSEED is strictly more expressive than standard heterogeneous graph neural networks that rely primarily on feature similarity and provably reduces the prediction bias introduced by heterophilic neighbors. Experiments on five real-world heterogeneous graphs, including two large-scale networks at the million-node and hundred-million-edge scale, demonstrate that HeterSEED consistently outperforms representative heterogeneous graph neural networks and recent heterophily-aware baselines, especially in strongly heterophilic regimes.

Models that recognize when their predictions are unreliable inspire greater trust than those that make confident but incorrect decisions. While recent advances enable uncertainty quantification in GNNs, understanding *why* a model is uncertain, whether due to noisy features, conflicting neighborhoods, or sparse training coverage, remains unsolved. We address this gap with GraphUAT, the first *uncertainty attribution* framework for GNNs, which identifies the sources of uncertainty rather than aiming to improve its quantification. GraphUAT employs a teacher-student paradigm, where the trained GNN's behavior is distilled into an uncertainty-aware student that disentangles aleatoric and epistemic uncertainties. We then use targeted probes to trace the student's uncertainty back to the responsible features and structural components. Experiments across benchmarks show that removing the identified elements consistently reduces the teacher's uncertainty, validating the faithfulness of our attributions.

Tree-based Monte-Carlo Tree Search (MCTS) duplicates the same state when it is reached through different trajectories, which can waste simulations in stochastic MDPs. We introduce Graph-Based Stochastic-Power-UCT (GS-Power-UCT), which shares states reached at the same planning depth while keeping separate values for states reached at different depths. This design applies to general stochastic MDPs, including problems with cycles. We prove that for a fixed planning horizon, the root estimate converges to the finite-horizon value at rate $O(n^{-1/2})$, matching tree-based Stochastic-Power-UCT while reusing samples across shared states. We also study two full-state variants: GS-Power-UCT-F, which stores one node per physical state to increase sample sharing but may mix values from different remaining horizons, and GS-Power-UCT-F$^+$, which uses an adaptive horizon to control this bias. The latter converges to $V^{\star}(s_0)$, the optimal infinite-horizon discounted value at the root state $s_0$, when the remaining cross-depth gap vanishes. Experiments on stochastic planning benchmarks show improved sample efficiency over tree-based and graph-based baselines.

Prioritized Sweeping (PS) accelerates model-based reinforcement learning by selecting backups according to residual magnitude. In nonstationary reward settings, however, the canonical priority score is shortsighted: after a localized reward shift, residuals propagate only through realized backups, so bottlenecked or topologically distant state estimates may remain static under a limited replanning budget. We introduce Graph Topology Augmentation for Prioritized Sweeping (GTA-PS), a concrete instance of a broader topology-augmentation principle for priority-based planning. GTA-PS constructs a policy-induced transition graph and augments the residual key with a mixing of regularized directed-Laplacian potentials that diffuses residual information through forward and backward graph structure. The topology weight is controlled by a scheduler based on the Second Largest Eigenvalue Modulus (SLEM), allowing the queue to adapt to the chain's mixing regime. We prove that the forward potential coincides with discounted residual propagation at a canonical regularization parameter and show that GTA-PS gives nonzero priority to states that standard PS can leave blocked after sparse reward shifts. Tabular experiments on FourRooms and GARNET domains demonstrate improved replanning efficiency over standard PS under both exact DP and Dyna-style host planners.

Modeling interacting dynamical systems requires capturing spatial interactions alongside long-range temporal dependencies. Graph neural networks (GNNs) provide a natural representation but typically rely on autoregressive rollouts and treat spatial and temporal dynamics separately, leading to error accumulation over long horizons. Existing approaches also focus on local interactions and short temporal contexts, limiting their ability to capture multi-hop dependencies and global structure. We introduce the Graph Mamba Operator (GraMO), a latent-space simulator that integrates state-space models with graph-based interaction learning. In contrast to prior work that sequences nodes or applies spatial and temporal updates in separate stages, GraMO couples graph-based interactions and temporal state updates within a single recurrence. The update is linear in the latent state, with input-dependent coefficients that adapt across regimes. We evaluate GraMO on N-body systems, motion capture, and robotics datasets, achieving the lowest error across benchmarks and the largest gains in long-horizon prediction.

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.