NeurIPS 2026 Papers

Training large language models at 4-bit precision is critical for efficiency. We show that nGPT, an architecture that constrains weights and hidden representations to the unit hypersphere, is inherently more robust to low-precision arithmetic. This removes the need for interventions—such as applying random Hadamard transforms and performing per-tensor scaling calculations—to preserve model quality, and it enables stable end-to-end NVFP4 training. We validate this approach on both a 1.2B dense model and hybrid (Mamba-Transformer) MoE models of up to 3B/30B parameters. We trace this robustness to the dot product: while quantization noise remains largely uncorrelated in both standard and normalized architectures, the signal behaves differently. In nGPT, the hypersphere constraint enhances weak positive correlations among the element-wise products, leading to a constructive accumulation of the signal across the hidden dimension while the noise continues to average out. This yields a higher effective signal-to-noise ratio and a flatter loss landscape, with the effect strengthening as the hidden dimension grows, suggesting increasing advantages at scale. A reference implementation is available at https://github.com/anonymous452026/ngpt-nvfp4.

Structural descriptors provide graph neural networks (GNNs) with positional and topological inductive biases. However, widely used classical encodings based on random walks or Laplacian spectra emphasize specific structural statistics of a graph, leaving room for alternative descriptors. Neutral-atom quantum processing units (QPUs) can realize graph-dependent Rydberg Hamiltonians, allowing graph topology to be probed through dynamical correlation measurements. In this work, we use these measurements as quantum graph features (QGFs), providing a complementary, hardware-derived family of structural encoding that --- as we demonstrate empirically --- is not accurately described by classical features derived from Laplacian or adjacency matrix. By appropriately selecting the quench parameters of the Hamiltonian, we access two characteristic correlation regimes with distinct structural signatures: antiferromagnetic-like and ferromagnetic-like. On an intrinsic information benchmark of 15 topological and spectral probing tasks, quantum and hybrid quantum-classical features match or surpass classical descriptors on local topological properties. When supplied to message-passing, attention, and graph-transformer backbones, hybrid quantum-classical features yield small improvements that are within cross-fold noise on most cells but sign-consistent across architectures. When comparing noiseless emulation-derived quantum features with an end-to-end neutral-atom QPU implementation, the downstream hybrid gain over the classical baseline persists on five out of six backbones.

We investigate the approximation capabilities of dense neural networks. While universal approximation theorems establish that sufficiently large architectures can approximate arbitrary continuous functions when there are no restrictions on the weights, we show that dense neural networks do not possess this universality. Our argument is based on a model compression approach, combining the weak regularity lemma with an interpretation of feedforward networks as message passing graph neural networks. We consider ReLU neural networks subject to natural constraints on weights and input and output dimensions, which model a notion of dense connectivity. Within this setting, we demonstrate the existence of Lipschitz continuous functions that cannot be approximated by such networks. This highlights intrinsic limitations of neural networks with dense layers and motivates the use of sparse connectivity as a necessary ingredient for achieving true universality.

Dynamic graph learning models the temporal evolution of structural interactions. Existing methods present a stark trade-off between performance and efficiency. Event-based models achieve strong accuracy because processing graphs edge-by-edge allows them to continuously update and leverage fine-grained joint neighborhood information. Conversely, snapshot-based methods offer high computational efficiency by processing entire snapshots simultaneously. However, updating neighborhood states for all nodes concurrently is computationally prohibitive. Consequently, current snapshot methods fail to utilize joint neighborhood information, leading to significantly weaker performance. To bridge this gap, we propose the Neighbor-Aware Graph Neural Network (NAGNN), a novel snapshot-based architecture that seamlessly integrates joint neighborhood information to achieve both strong performance and high efficiency. Specifically, NAGNN introduces a Locality-Sensitive Hashing (LSH)-based topology distiller to construct compact reservoirs that store neighborhood information efficiently. These reservoirs are further augmented with degree-scaled statistical moments to encode structural characteristics of local neighborhoods. A Gated Recurrent Unit (GRU) subsequently processes the distilled structural representations to model and capture their temporal dynamics. Extensive experiments demonstrate that NAGNN matches the predictive accuracy of computationally expensive event-based models with minimal overhead, establishing a highly scalable and effective paradigm for dynamic graph learning.

Trade flows are a central variable for studying international trade networks. Traditional economic models, grounded in economic theory and mathematical derivation, provide structured representations of bilateral trade flows. However, these representations often rely on fixed functional forms, have limited ability to incorporate high-dimensional features, do not directly capture trade inertia, and scale poorly to large and dynamic trade networks. In recent years, graph neural networks have been increasingly used to address some of these limitations because they are naturally compatible with networked trade data and offer strong scalability. However, the feature aggregation process in existing graph neural models remains weakly interpretable from an economic perspective. To address this limitation, we propose MRTGNN, a graph neural network model built on a theory-guided MRTGNN layer derived from the fixed-point equations of multilateral resistance in structural gravity. Theoretically, we prove that an $L$-layer MRTGNN can approximate $L$ iterations of a multilateral-resistance fixed-point operator on a compact domain, with an explicit bound on the iteration error. Empirically, we extensively evaluate MRTGNN on panel data covering 176 countries from 2002 to 2019 against various representative baselines. The full model achieves the best RMSE, $R^2$, and Spearman rank correlation across the reported baselines. Under counterfactual tariff shocks involving China, it produces a Network Spillover Ratio one order of magnitude higher than a generic graph-attention baseline. These results show that theory-guided message passing improves trade flow prediction while enabling more interpretable counterfactual reasoning in global trade networks.

Graph contrastive learning (GCL) typically maximizes cross-view agreement via an InfoNCE-based mutual-information (MI) surrogate, applying uniform alignment pressure across all anchors. Yet the reliability with which topology and attributes support cross-view agreement varies across nodes: strong pressure can benefit structurally consistent anchors but can harm boundary, low-agreement, or noisy anchors. We study this calibration problem in self-supervised node representation learning on small-to-medium attributed graphs. We propose MIRAGE, a hierarchical MI-surrogate regulation framework whose core consists of two components: anchor-wise MI setpoints that assign bounded alignment budgets to individual nodes, and dual-view MI stabilization that keeps branch-level surrogate estimates close to a target while limiting excessive anchor-wise dispersion. A label-free structure-reliability-gated hypergraph path serves only as conditional compensation for weak anchors when local structural signals are estimated to be reliable. On six node-classification benchmarks, MIRAGE achieves competitive accuracy, including 85.21% on Cora, 73.94% on Citeseer, and 92.57% on ACM. Beyond final accuracy, mechanism-level analyses show that MIRAGE tracks designated MI-surrogate targets during training and that changing the target level produces measurable downstream changes, indicating that target-tracked MI-surrogate regulation provides a practical optimization primitive for calibrating cross-view agreement in GCL.

Graph-based Approximate Nearest Neighbor (ANN) search often suffers from performance degradation in high-dimensional spaces due to the Euclidean-Geodesic mismatch, where greedy routing diverges from the underlying data manifold. To address this challenge, this paper presents Manifold-Consistent Graph Indexing (MCGI), a geometry-aware and disk-resident indexing method that leverages Local Intrinsic Dimensionality (LID) to dynamically adapt search strategies to the intrinsic geometry of data. Unlike conventional algorithms that treat dimensions uniformly, MCGI modulates its beam search budget based on in-situ geometric analysis, which reduces sensitivity to data-specific hyperparameters by replacing a single scalar with a geometry-informed range that remains stable across datasets of varying dimensionality. Theoretical analysis demonstrates that MCGI provides robust approximation by preserving manifold-consistent topological connectivity. Extensive evaluations against five industry-standard baselines across five datasets up to billion scales confirm the advantages of the proposed approach.

Graph Neural Networks (GNNs) are powerful tools for learning from spatio-temporal data, as interactions in space can be naturally described by a graph structure. However, capturing long-range dependencies becomes substantially harder when information must flow through space and time simultaneously. Most existing approaches extend GNNs from static graphs to temporal settings by alternating propagation between time and space. In this work, we introduce STORM, a differential-equation-inspired GNN that exploits oscillatory dynamics to propagate information effectively in the joint spatio-temporal domain. By combining a wave-equation update with dissipative and external forcing terms, STORM balances conservative and non-conservative dynamics. We provide a bottom-up analysis of the model, highlighting its propagation behavior and stability, and show that STORM is universal. We empirically validate our method on diverse benchmarks, including tasks designed for analyzing long-range spatio-temporal dependencies, real-world forecasting, and a new long-range task inspired by physical simulations. Across these settings, STORM consistently matches or outperforms strong baselines, establishing a new state of the art for long-range spatio-temporal graph learning.

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.

Large language models (LLMs) are increasingly used for knowledge base question answering (KBQA), where answering requires selecting entities from a question-specific knowledge-graph subgraph. Yet LLMs are known to hallucinate across tasks, and KBQA is no exception: even when we provide a graph as the knowledge source, the model may rely on parametric knowledge instead of graph evidence or perform invalid reasoning over the given relations. Such hallucinated answer nodes can limit the practical deployment of KBQA systems, especially in high-stakes domains such as healthcare. We formulate hallucination detection in KBQA as an answer-node classification problem and propose a lightweight graph-based framework that treats the answering LLM as a black box. KG-Guard represents each KBQA instance as an augmented graph. It initializes node features with semantic representations of KG entities, marks topic entities and LLM-proposed answer nodes with learned vectors, and connect a virtual question node to the topic entities. A graph encoder then produces verification-oriented node representations, and a small MLP classifies each proposed answer node using its graph representation together with the question embedding. Experiments on WebQSP, ComplexWebQuestions, and PUGG show that our detector achieves the highest F1 on all three benchmarks ($82.0$, $87.4$, and $84.3$), outperforming LLM-judge and sampling-based baselines, while having $\sim305\times$ fewer parameters than the reference approaches. Beyond detection, the node-level feedback is actionable: when flagged answers are fed back to the KBQA system for iterative refinement, downstream KBQA F1 improves by $13.0$-$14.5$ points and Exact Match by $16.9$-$17.6$ points.

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.

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.

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.