NeurIPS 2026 Papers

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.

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.

Message-passing graph neural networks (MPGNNs) dominate modern graph learning. Typical efforts enhance MPGNN's expressive power by enriching the adjacency-based aggregation. In contrast, we introduce a graph-level aggregation over walk incidence-based matrices that are constructed to deliberately trade off some expressivity for stronger and more structured inductive bias. This approach allows for gradual scaling between classical message-passing and simpler methods based on walks. Our second result characterizes the expressive power at each scale using homomorphism counts over a hierarchy of generalized caterpillar graphs. Based on these foundations, we propose Caterpillar GNNs that substantially reduce the number of nodes in the hidden layers of the computational graphs on real-world datasets. This gradual reduction does not obstruct learning, enabling a systematic study of lower-order expressivity. We further describe benchmark settings where a task-aligned expressivity supports learning.

Graph-structured data is crucial in various domains like biology and social networks. Comparing graphs, which is a fundamental problem in graph data analysis, is nonetheless highly challenging. Recently, the Gromov-Wasserstein (GW) distance has provided a principled way to compare two graphs. However, computing the GW distance involves solving a complex non-convex optimization problem, making it computationally expensive, especially when the graphs are large. In this work, we propose a neural approximation of the GW distance, called NeuralGW. In NeuralGW, we use a combination of a graph isomorphism network and a transformer to represent the nodes of two graphs as two sets of vectors, treated as two discrete distributions, on which we compute multiple maximum mean discrepancy values given by different kernels. We then use a multilayer perceptron to convert the vector formed by these values into a single value, which is the prediction of the GW distance. Once trained, the model allows for efficient inference, enabling fast structural comparisons between graphs across diverse domains. We also provide a theoretical guarantee for the generalization ability of NeuralGW. Experiments demonstrate the effectiveness and practical applicability of our approach on real-world datasets, in comparison to baselines.

Graph contrastive learning constructs augmented views and aligns corresponding instances across views to learn view-invariant representations. However, existing methods usually enforce cross-view consistency within a single representation space, lacking an explicit characterization of view-specific information. This may suppress task-relevant complementary information, reduce embedding diversity, and induce dimensional collapse. To this end, we propose Manifold-Guided Representation Disentanglement (MGRD), a plug-and-play framework for boosting graph contrastive learning. MGRD decomposes graph representations into shared and complementary subspaces. The shared subspace captures view-invariant semantics while preserving local graph structure through a graph-anchored manifold prior, whereas the complementary subspace captures residual view-specific information beyond the shared representation and is regularized by asymmetric consistency and subspace decorrelation. By jointly exploiting shared and complementary representations, MGRD balances cross-view invariance and representation diversity. Experiments on node-level and graph-level benchmarks show that MGRD consistently improves multiple GCL backbones, while theoretical and empirical analyses demonstrate its effectiveness in mitigating dimensional collapse.

Learning meaningful representations from cellular microscopy images remains a central challenge in computational biology and computer vision. Recent advances in self-supervised learning (SSL) have shown that scaling model and dataset size can improve the recovery of biological relationships such as gene–gene or compound–target associations. However, this progress has been driven primarily by scale rather than structure—requiring vast data and compute while offering no guarantee that the resulting embeddings capture underlying biology. We introduce NOVA, a structure-first framework for learning biologically aligned representations of cellular perturbations. NOVA integrates curated biological graphs directly into the training objective of a vector-quantised transformer, aligning embeddings of related genes and pathways through graph-based regularisation. By incorporating these relational priors during training, NOVA learns biologically faithful representations with orders of magnitude less data and compute than current state-of-the-art SSL models, while achieving superior performance on gene-gene retrieval benchmarks. This approach reframes representation learning for microscopy from a problem of scale to one of structure, offering a more systematic and efficient route toward biologically grounded embeddings.

Graph foundation models have emerged as a promising paradigm for generalizing across diverse structural tasks. Current approaches serialize graphs into node token sequences and apply autoregressive or masked prediction, yet this node sequential modeling disrupts the relation-centric nature of graphs and violates permutation equivariance. We propose **relational diffusion**, a framework that reconceptualizes graph modeling through edge co-occurrence modeling. By treating edges as fundamental modeling units and learning their joint distribution via discrete diffusion processes, our approach naturally respects the relational semantics of graphs while maintaining permutation equivariance. We introduce topological edge tokenization to enrich edge representations with multi-hop structural context, and relational prompt completion to unify node classification, link prediction, and graph classification as sequence completion problems over edge representations. Through extensive experiments, we demonstrate that relational diffusion achieves strong performance while providing a principled foundation aligned with the relational nature of graphs.

Understanding the reasoning behind deep learning model predictions is crucial in cheminformatics and drug discovery, where molecular design determines their properties. However, current evaluation frameworks for Explainable AI (XAI) in this domain often rely on artificial datasets or simplified tasks, employing data-derived metrics that fail to capture the complexity of real-world scenarios and lack a direct link to explanation faithfulness. To address this, we introduce B-XAIC, a novel benchmark constructed from real-world molecular data and diverse tasks with known ground-truth rationales for assigned labels. Through a comprehensive evaluation using B-XAIC, we reveal limitations of existing XAI methods for Graph Neural Networks (GNNs) in the molecular domain. This benchmark provides a valuable resource for gaining deeper insights into the faithfulness of XAI, facilitating the development of more reliable and interpretable models.

Graph neural ordinary differential equations provide continuous-time propagation on graphs, but their long-time behavior is largely determined by the asymptotic structure of the mixing operator. We show that diffusion-style Graph ODEs with positive irreducible mixing face a *monostability trap*, where node features converge to a rank-one consensus subspace. This reveals a structural limitation of positive diffusion-style continuous graph propagation: within this consensus class, exact long-time avoidance requires changing the effective support; otherwise, smooth suppression should be interpreted as finite-horizon or metastable mitigation. We address this by introducing a *hysteretic mechanism* for topology evolution, where candidate edges carry latent bistable potentials in a double-well landscape. A node-feature-conditioned force field evolves these potentials, and a smooth sigmoid gate converts them into differentiable propagation weights. We prove the consensus trap theoretically, show that idealized support separation yields block-wise rather than global consensus, and evaluate the framework on real-world benchmarks.

Operator learning has been highly successful for continuous mappings between infinite-dimensional spaces, such as PDE solution operators. However, many operators of interest—including differential operators—are discontinuous or set-valued, and lie outside classical approximation frameworks. We propose a paradigm shift by formulating approximation via graph convergence (Painlevé–Kuratowski convergence), which is well-suited for closed operators. We show that uniform and $L^p$ approximation are fundamentally inadequate in this setting. Focusing on maximally monotone operators, we prove that any such operator can be approximated in the sense of local graph convergence by continuous encoder–decoder architectures, and further construct structure-preserving approximations that retain maximal monotonicity via resolvent-based parameterizations.

Reliable deployment of graph neural networks requires calibration, out-of-distribution (OOD) detection, and robustness to distribution shift, yet existing methods typically address these requirements with separate models and objectives. A key obstacle is the lack of a single learned representation whose structure can serve all three tasks through different readouts. Inspired by spectral approaches in graph signal processing and polynomial chaos theory, we model uncertainty-bearing node embeddings as random graph signals: graph Fourier filters capture structural variation, while a scalar orthogonal-polynomial chaos coordinate captures latent stochastic variation. This yields a \emph{doubly-spectral stochastic} (DSS) expansion in which the mean coefficient carries evidence for classification and energy-based OOD scoring, higher-order coefficients encode structured logit variation, and quadrature averaging turns that variation into a calibration-sensitive predictive distribution. Calibration thus uses the quadrature-averaged predictive distribution, OOD detection uses the mean-logit energy score, and distribution-shift robustness uses the corresponding DSS branch as a regularized spectral residual when paired with a deterministic encoder. Under mild conditions this representation universally approximates Gaussian-latent random graph signals with exponentially decaying truncation error. The resulting model, \emph{DSS-GNN} (Doubly-Spectral Stochastic GNN), can be used standalone or as a residual branch alongside a deterministic encoder (\emph{DSS-Hybrid}). In standalone form, DSS-GNN achieves the lowest Brier score among the compared uncertainty-aware baselines on all 14 node classification benchmarks without post-hoc correction; in hybrid form, DSS-Hybrid achieves the best AUROC on most node-OOD settings, competitive cross-graph OOD performance, and the strongest shifted accuracy among compared baselines on all 7 GOOD concept-shift benchmarks under standard ERM training.

Most temporal graph learning methods reduce future prediction to discriminative inference over past interactions, focusing on edges or node labels for a largely persistent set of nodes. This view breaks down when new nodes and edges appear, since the future graph becomes a new object with changing size, composition, and structure. We address this gap by framing temporal graph prediction as an inverse topology problem. Instead of predicting edges directly, we first predict a multiscale topological descriptor of the future graph and then reconstruct a plausible future snapshot that realizes this descriptor under inductive constraints. This approach makes global structure and node churn explicit prediction targets and produces forecasted graphs on which downstream tasks can be evaluated without retraining. Across 14 temporal graph datasets, we evaluate TopoGED on node, link and graph property prediction and compare it against state-of-the-art temporal graph models. TopoGED achieves a significant improvement in node-level forecasting accuracy over the strongest baseline, with a macro average of 0.49 versus 0.05. It also outperforms baselines in 60% of graph-structure metric evaluations and yields a substantial increase in macro-average edge prediction metrics, from near-zero to 0.12. Our results show that topology-guided graph forecasting can predict inductive future snapshots whose structure supports multiple downstream evaluations.

3D scene graph prediction is commonly supervised with local object and predicate classification losses. Although effective for slot-wise label prediction, this formulation does not provide a graph-level semantic distance between a predicted scene graph and its ground truth: semantically mild label errors and structurally disruptive relational errors can be treated similarly, and subject-predicate-object facts are not compared as scene-level units. We propose Contextual Hellinger Triplet Geometry, a graph-level supervision objective that measures the semantic and structural discrepancy between 3D scene graphs. Our key idea is to reinterpret the conventional classifier outputs of a 3D scene graph predictor as an aligned probabilistic scene graph field, where object and predicate predictions jointly define contextual subject-predicate-object facts. This formulation yields a differentiable metric-based training objective with an efficient factorized implementation and can be applied to existing 3D scene graph prediction architectures without modifying their network design. Experiments on 3DSSG demonstrate that our supervision improves downstream graph-conditioned 3D scene generation, while ablation studies confirm the complementary roles of the proposed graph-level terms and user studies show better graph descriptiveness, relation plausibility, and structural preservation.