NeurIPS 2026 Papers

In many real-world applications, it is undesirable to drastically change the problem solution after a small perturbation in the input as unstable outputs can lead to costly transaction fees, privacy and security concerns, reduced user trust, and lack of replicability. Despite the widespread application of graph algorithms, many classical algorithms are not robust to small input disturbances. Towards addressing this issue, we study the pointwise Lipschitz continuity of graph algorithms, a notion of stability introduced by Kumabe and Yoshida (2023, FOCS’23) and further studied in related settings (Kumabe and Yoshida, 2024, ICALP’24), (Kumabe and Yoshida, 2025, SODA’25), (Gima et al., 2025, ESA’25). Our main result is a linear programming (LP) based minimum S-T cut algorithm with a provably optimal Lipschitz constant, as witnessed by an accompanying lower bound. As a direct corollary, we give the first dynamic minimum S-T cut algorithm with non-trivial recourse bound. At the core of our techniques is a novel framework for analyzing the Lipschitz constant of regularized LP relaxations. Our framework crucially unlocks the use of weighted regularizers, which could not be analyzed through previous methods and leads to polynomial improvements in the Lipschitz constant compared to what is achievable through previous techniques. To demonstrate the flexibility of our methods, we also design an LP-based b-matching algorithm that improves on the state-of- the-art Lipschitz constant in certain input regimes when b ≡ 1. Moreover, our algorithm cleanly extends to the general case when b ≥ 1, whereas prior works are specialized to the case of b ≡ 1.

Graph Network Simulators (GNS) have emerged as powerful surrogates for complex physics-based simulation, offering inherent differentiability and orders-of-magnitude speedups over traditional solvers. However, GNSs typically assume access to the underlying material parameters, such as stiffness or viscosity, severely limiting their utility in realistic experimental settings. While recent meta-learning approaches address the parameter dependency by inferring properties from mesh trajectories, reconstructing a mesh from an observed scene is difficult. In this work, we introduce Point Cloud Encoding for Accurate Context Handling (PEACH), a novel framework that applies in-context learning on point clouds to adapt a learned simulator to unseen physical properties during inference. Our approach relies on a novel spatio-temporal point cloud sequence encoder, as well as two forms of auxiliary supervision to help improve simulation fidelity. We demonstrate that PEACH is capable of accurate zero-shot sim-to-real transfer on a challenging, dynamic scene. Experiments on simulation scenes show that PEACH even outperforms mesh-based baselines on simulation accuracy, while being much more practical for real-world deployment.

This paper studies the problem of zero-shot text-attributed graph learning, which aims to generate high-quality node representations in unseen text-attributed graphs. Recent approaches usually utilize large language models (LLMs) instead of graph neural networks (GNNs) to extract semantics due to their strong generalization ability, which could neglect the intrinsic geometric structure. Towards this end, in this paper, we propose a novel approach named Prototypical Mutual Prompting Enhancement (PATH) for zero-shot text-attributed graph learning. The core of our PATH is to generate high-quality prompts using dual prototypical learning to combine the advantages of both language models and graph models. In particular, we first utilize dual graph pre-training from both instance and informativeness perspectives to generate a generalizable GNN. Then, we incorporate the frozen language and graph models into a mutual prompt learning framework. On the one hand, we extract node tokens with geometric relationships using the graph model, which will be sent to multiple prototypical projections to enhance the understanding of the language model. On the other hand, we extract graph information and task descriptions using the language model, which serves as instruction for the graph models. Extensive experiments on node classification and link prediction validate the effectiveness of the proposed PATH against strong baselines. Our code is available at [https://anonymous.4open.science/r/PATH](https://anonymous.4open.science/r/PATH).

Hypergraph Neural Networks (HNNs), designed to model higher-order relations beyond pairwise interactions, typically rely either on fixed structural weights or on normalized attention. Fixed weights can propagate misleading information in heterophilic settings, while normalization makes attention coefficients competitive, in the sense that, in a message-passing framework, increasing the weight of one sender must reduce the weight of others in the same aggregation set. Our main contribution is the introduction of PANDA (Prior-guided AttentioNal Dual-path Architecture), a plugin for two-stage message passing HNNs applicable to both undirected and directed settings. The *main path* interpolates between learned receiver-normalized attention and structural incidence priors, while a non-competitive (not normalized) *auxiliary path* lets each sender contribute its own transformed information. We also show that, with fixed structural coefficients, PANDA recovers a certain complex-valued, convolution operator adopted in previous works. Across four HNNs spanning spatial and spectral methods in both directed and undirected settings, plugging PANDA in yields an average improvement of $5.18$ percentage points across eight real-world benchmark datasets.

Neural Sheaf Diffusion (NSD) generalizes diffusion-based Graph Neural Networks by replacing scalar graph Laplacians with sheaf Laplacians whose learned restriction maps define a task-adapted geometry. While the diffusion limit of NSD is known to be the space of global sections, the representation-theoretic structure of this harmonic space remains largely implicit. In this paper, we develop a quiver-theoretic interpretation of NSD by identifying cellular sheaves on graphs with representations of the associated incidence quiver. Under this correspondence, learned sheaf geometries become points in a finite-dimensional representation space. We prove that direct-sum decompositions of the underlying incidence-quiver representation induce corresponding decompositions of the harmonic space reached in the diffusion limit. This provides an algebraic interpretation of oversmoothing as representation degeneration: a conceptual framing where learned sheaves collapse toward trivial or low-complexity summands whose global sections fail to preserve discriminative information. Building on this viewpoint, we connect sheaf diffusion to stability, moduli, and moment-map principles from Geometric Invariant Theory. We introduce moment-map-inspired regularizers that bias learned restriction maps toward more balanced representation geometries, and we identify a structural obstruction in standard equal-stalk architectures: when $d_v=d_e$, the admissibility condition for learnable stability parameters forces the trivial all-object summand onto a stability wall. We show that non-uniform stalk dimensions remove this obstruction, making adaptive stability meaningful in principle. Empirical evaluations on heterophilic benchmarks are consistent with this mechanism: breaking stalk symmetry can reduce variance or improve validation behavior on some datasets, and adaptive stability regularization becomes more effective in selected rectangular settings. These results support the view that moment-map regularization is a structured but dataset-dependent geometric bias rather than a universal performance booster. Overall, our framework interprets oversmoothing not only as a spectral pathology, but as a degeneration phenomenon in the underlying representation geometry.

We study the Sobolev IPM problem for probability measures supported on a graph metric space, where critic function is constrained to lie within the unit ball defined by Sobolev norm. Sobolev IPM is intrinsically coupled with $L^p$ geometric structure within its definition, limiting its ability to incorporate other prior geometry beyond the $L^p$ paradigm. Conversely, the classic optimal transport is flexible, easy to adapt to various geometric structures by simply changing its ground cost. An important example is Orlicz-Wasserstein (OW) which utilizes \emph{Orlicz} geometric structure to generalize the $L^p$ within the standard $p$-order Wasserstein, and remarkably play a vital role to advance machine learning methodologies. Inspired by recent advantages of OW, in this work, we leverage a specific class of convex functions for Orlicz geometry to mitigate such limitation for Sobolev IPM, and propose the generalized Sobolev IPM (GSI). Our GSI approach encompasses Sobolev IPM as a special case while accommodating diverse geometric priors beyond $L^p$. It however brings up significant computational hurdles that compound those already notoriously inherent in Sobolev IPM. To address these challenges, we theoretically establish a novel connection between \emph{Orlicz-Sobolev} norm and \emph{Musielak} norm which facilitates a novel efficient regularization for GSI. By further exploiting the underlying graph structure, we show that the regularized GSI reduces to a simple univariate optimization problem, achieving notably computational efficiency, enabling its usage in practical applications. We empirically illustrate that the regularized GSI is several-order faster than the popular OW in computation, and its performances compare favorably to other transport baselines for comparing graph-based measures in document classification and topological data analysis.

One-shot Federated Graph Learning (OFGL) has emerged as a communication-efficient paradigm for Federated Graph Learning (FGL) under strict bandwidth constraints, compressing collaboration into a single transmission round. Nevertheless, this extreme setting suffers from a fundamental **Single-Transmission Bottleneck**, which limits both the quality and utility of exchanged knowledge. First, while existing methods attempt to distill private graphs into shareable proxies, their aggressive one-shot compression inherently triggers a fidelity crisis. This compression distorts local graph topology and semantics across clients, leading to **externalized knowledge underexpression**. Second, although the server aggregates these proxies to update global models, current integration schemes suffer from transferability agnosticism. The server cannot reliably identify cross-client collaboration potential, resulting in **integrated knowledge underutilization**. To tackle these dual challenges, we propose FedHFT, an effective One-shot Personalized Federated Graph Learning (OPFGL) framework that addresses this bottleneck from two perspectives, namely High-Fidelity Knowledge Externalization and Transferability-Ware Knowledge Integration. We use Fidelity-Driven Proxy Refinement to preserve client-side knowledge fidelity, and Transferability-Steered Personalized Collaboration to enable adaptive server-side collaboration. The superiority of FedHFT is validated through extensive experiments on both homophilic and heterophilic graphs. The code is available at https://anonymous.4open.science/r/FedHFT-DC7F/.

Graph-based nearest neighbor search algorithms like HNSW, DiskANN, NSG, and others have surged in popularity in recent years due to their excellent empirical performance in comparison to previously successful ``space partitioning'' methods like IVF data structures and Locality Sensitive Hashing (LSH). However, in contrast to LSH and related methods, obtaining strong worst-case theoretical guarantees for graph-based search has remained a challenging open problem. In this paper, we prove a strong lower bound that helps explain the lack of progress towards such guarantees. In particular, we show that no standard graph-based method (i.e., any method that runs a variant of greedy search on a flat or hierarchical search graph) can achieve sublinear query time for approximate nearest neighbor search in Euclidean space, even for an arbitrarily large approximation factor. On the other hand, we prove that sublinear query time \emph{is possible} if we allow for the use of \emph{Steiner points} in the search graph. We obtain bounds comparable to LSH, showing e.g., that graph-based search with Steiner points can solve $c$-approximate nearest neighbor search in Euclidean space with query time $\tilde{O}\left(n^{1/c}\right)$. We complement this result with initial experiments exploring how Steiner points can be incorporated into practical graph-based methods, showing modest but meaningful improvements in recall versus query-time tradeoffs.

Graph Neural Networks (GNNs) have become the dominant framework for inductive graph-level learning. Yet most benchmarks focus on the regime $n \gg p$, where the number of graphs $n$ greatly exceeds the number of nodes per graph $p$. This overlooks biological domains such as omics, which operate in the opposite $n \ll p$ regime, characterized by large graphs of genes, transcripts, or proteins across few patient samples. This raises the question: \textit{how do GNNs perform in this low-sample, high-node omics setting?} We introduce \texttt{OgBench} (Omics-Graph Bench), the first benchmarking platform for graph-level prediction in the $n \ll p$ regime characteristic of omics data. We provide a standardized, end-to-end modular infrastructure from raw omics data to families of featured graphs with varied structural properties. We benchmark classical GNNs, as well as GNNs designed for large graphs and omics applications, alongside MLPs and machine learning baselines to establish reference performances. Our results show that widely used GNNs often do not outperform simple MLPs and classical baselines. These findings challenge the prevailing assumption that graph structure inherently adds value in this domain, fostering a critical reassessment of current learning paradigms. Ultimately, by exposing these limitations, OgBench provides the open-source ecosystem necessary for the community to develop and validate novel architectures explicitly tailored for biological graphs. The code is available at \url{https://anonymous.4open.science/r/ogbench-C1A9/README.md}.

Ocean dynamics are inherently chaotic, yet existing machine learning ocean models produce only deterministic forecasts. We introduce Njord, a probabilistic data-driven model for ocean forecasting, applicable to both global and regional domains. Njord combines a deep latent variable framework with a graph neural network architecture, enabling sampling each forecast step in a single forward pass. We apply Njord globally at 0.25° resolution and regionally to the Baltic Sea at 2 km resolution. To scale to these large ocean grids we introduce K-means cluster meshes that adapt to irregular sea surface geometry. Experiments demonstrate strong performance on both domains compared to deterministic machine learning baselines, while also providing uncertainty estimates from the sampled ensemble forecasts. On the global OceanBench benchmark, Njord achieves the lowest errors on average across upper-ocean variables when evaluated against real-world observations, with the largest improvements in surface temperature prediction.

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.

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.

Different optimizers impose different geometries on parameter updates. Adaptive methods such as Adam and AdamW use coordinate-wise updates, while matrix-aware optimizers such as Muon utilize weight-matrix structure through orthogonalized updates. For Graph Neural Networks (GNNs), however, the effective geometry of its weight matrices is shaped not only by its learned channel-mixing weights, but also by the graph-propagated representations it acts on. Thus, even if an update is well normalized as a matrix, its effect on the layer output can be amplified when applied to graph-propagated features. To address this gap, we introduce GraphMuon, a graph-aware optimizer that adapts Muon's matrix updates to the covariance structure of graph-propagated layer inputs. GraphMuon performs orthogonalization in a metric defined by these propagated representations and normalizes step sizes according to the update's induced effect on the layer representation. We show that theoretically, vanilla Muon can suffer from graph-induced update amplification, while our GraphMuon can mitigate this effect. As such, our GraphMuon yields a graph-metric analogue of Muon's polar update step. Empirically, we show that GraphMuon achieves $2.13\times$-$7.38\times$ speedups in time-to-target wall-clock runtime over AdamW across diverse graph-learning regimes, while maintaining competitive or superior predictive performance.

Predicting the olfactory perception of scent mixtures remains a fundamental challenge in computational neuroscience. Existing methods derive mixture-level features by encoding individual components with a single-molecule feature encoder pretrained on annotated olfactory data and aggregating these features via mean pooling, concatenation, or self-attention. This paradigm faces two critical limitations: the scarcity of annotated olfactory data and the inability to capture complex interactions among mixture components. We present MixScentNet, a multiscale graph neural network framework, to address these challenges with two key innovations. First, we introduce a self-supervised pretraining strategy that uses molecular graph structures with RDKit features to predict corresponding Mordred descriptors, enabling the model to learn rich physicochemical knowledge without relying on scarce annotated olfactory data. Second, we propose a novel mixture-as-graph paradigm to model the constituent molecules as nodes in the mixture-level graph, aligning with the fact that humans holistically perceive scent mixtures. We further process the graph via a graph attention network V2 (GATv2) to capture the high-order molecular interactions. MixScentNet differs from existing methods in terms of its pretraining strategy and ability to capture mixture-level features, achieving state-of-the-art performance on both mixture-level olfactory label prediction and perceptual distance estimation tasks. We also find that MixScentNet can reproduce olfactory white phenomena, indicating that the model enjoys clear interpretability grounded in psychophysics. The demo code is available in the Anonymous link \url{https://anonymous.4open.science/r/Odor-D2DB}

Multimodal large language models (MLLMs) show remarkable potential for scientific reasoning, yet their performance in specialized domains such as microscopy remains limited by the scarcity of domain-specific training data and the difficulty of encoding fine-grained expert knowledge into model parameters. To bridge the gap, we introduce MicroWorld, a framework that constructs a multimodal attributed property graph (MAPG) from large-scale scientific image-caption corpora and leverages it to augment MLLM reasoning at inference time without any domain-specific fine-tuning. MicroWorld extracts biomedical entities and relations via scispaCy or LLM-based triplet mining, aligns images and entities in a shared embedding space using Qwen3-VL-Embedding, and assembles a knowledge graph comprising approximately 111K nodes and 346K typed edges spanning eight relation categories. At inference time, a graph-augmented retrieval pipeline matches query entities to the MAPG and injects structured knowledge context into the MLLM prompt. On the MicroVQA benchmark, MicroWorld improves the reasoning performance of Qwen3-VL-8B-Instruct by 37.5%, outperforming GPT-5 by 13.0% to achieve a new state-of-the-art. Furthermore, it yields a 6.0% performance gain on the MicroBench benchmark. Extensive experiments demonstrate the enhanced generalization capability introduced by MicroWorld. A qualitative case study further reveals both the mechanisms through which structured knowledge improves reasoning and the failure modes that point to promising future directions. Code and data are available at anonymous GitHub.

Large-graph spectral learning promises global, trainable propagation beyond local neighborhoods, but explicit spectral layers remain difficult to use in stochastic large-graph training: their bases are commonly obtained by a full-graph spectralization step and their graph-wide contexts are naturally full-batch. Matrix-free polynomial filters avoid eigensolvers and train stochastically, but tie the response to finite propagation bases; explicit spectral-subspace models offer more flexible global responses, but usually pay for full-graph basis construction and context evaluation. We introduce Randomized Adaptive Spectral Estimation (RASE), a matrix-free stochastic training framework for explicit low-rank spectral-context layers. RASE constructs a refreshable randomized block-Krylov/Ritz basis from probe vectors and sparse matrix--vector products, reuses probe-derived summaries as control variates for mini-batch estimates of the spectral context, and keeps the response module replaceable across polynomial, Chebyshev, and transformer-style instantiations. We analyze Krylov/Ritz polynomial-action exactness for the probe-generated subspace and a control-variate variance identity that isolates when the mini-batch context estimator reduces variance. Across 14 node-classification benchmarks, RASE matches its eigenbasis-trained reference within seed noise where the eigensolver is feasible (${\sim}67{\times}$ faster basis on PubMed), and trains the same backbone on the largest graphs where eigensolver preprocessing exceeds a 30-minute budget. The contribution is therefore not a new spectral filter family, but a training route that makes explicit low-rank spectral-context layers matrix-free and mini-batch trainable.

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.