NeurIPS 2026 Papers

Discrete graph diffusion models corrupt graph structure through independent edge updates with a Markovian noise model. Combined with the exchangeability requirement on the output distribution, the terminal prior is necessarily an Erd\H{o}s--R\'enyi (E-R) random graph. This has a fundamental consequence for unconditional graph generation without node features: in the large graph limit, any GNN denoiser applied to an E-R graph approximately outputs an E-R graph, making effective denoising difficult. In practice, generated graphs fail to recover meaningful node heterogeneity and higher-order structure. Previous models introduced specialized node features to compensate, framing this as an expressivity problem, while the role of the prior remained unexamined. We instead address the root cause by introducing the \emph{Latent Sociability Prior} (LSP) and a \emph{joint} diffusion process that co-evolves latent node sociability variables and graph structure, removing edge independence while preserving exchangeability. Unlike existing latent graph diffusion methods, the sociability mechanism requires no complex encoder: its sole role is to guide edge updates and preserve node heterogeneity throughout the trajectory. We validate our approach on multiple graph generation datasets and show that the proposed framework more accurately captures graph distributions than baseline methods without node features.

Transfer-based black-box adversarial attacks provide a practical way to evaluate the robustness of Vision-Language Pre-training (VLP) models, which remain vulnerable to adversarial perturbations that mislead cross-modal matching and downstream predictions. For strong transfer against VLP models, attacks should depend on prediction-relevant evidence localization and model-agnostic perturbation design. Existing methods fall short in both aspects, typically perturbing images broadly or relying on raw attention maps, which imprecisely localize decisive patches and derive perturbation patterns from the surrogate model's own representations, hindering transfer across VLP architectures. In this paper, we propose Graph-Guided Transferable (GGT) attack, a transferable multimodal adversarial attack that decouples what to perturb from how to propagate: the former by cross-modal sensitivity, the latter guided by intrinsic image structure. This separation enables better localization by capturing VLP-specific cross-modal evidence, while enforcing perturbation propagation through model-agnostic image structure, thereby improving transfer across unseen architectures. GGT first identifies crux patches decisive for cross-modal prediction by combining gradient-weighted attention and attention entropy, which capture how indispensable and how broadly influential each patch is. It then propagates perturbations from these crux patches through a model-agnostic graph constructed from spatial adjacency and vision-only patch similarity, with hop-wise attenuation. Extensive experiments demonstrate that GGT consistently outperforms strong baselines in black-box transfer success rate across diverse VLP architectures, improving over the strongest baseline by up to 23.66\% in text retrieval and 16.06\% in image retrieval.

Graphs with a simple spectrum admit cubic-time isomorphism testing, yet we prove that for every natural number $k$, the $k$-Weisfeiler-Leman ($k$-WL) test cannot distinguish all non-isomorphic graphs with a simple spectrum. As the WL hierarchy upper-bounds the distinguishing power of widely-used Graph Neural Networks (GNNs), this incompleteness applies to all such GNNs, ruling out completeness for every $k$-WL-aligned GNN family. To close this gap, we introduce PRiSM (Partition, Refine, Solve, Match), the first provably complete canonicalization of simple-spectrum eigendecompositions. PRiSM obtains the completeness guarantee that prior canonicalizations provably lack, and resolves the open problem of achieving complete expressivity on simple-spectrum graphs. When composed with DeepSets or a Transformer, PRiSM achieves universal approximation on simple-spectrum graphs, justifying the use of canonicalized Laplacian positional encodings. Empirically, PRiSM performs comparably to or outperforms existing spectral canonicalizations on graph regression, classification, and expressivity benchmarks.

Dynamic Graph Neural Networks (DyGNNs) demonstrate powerful representation capabilities in crucial time-series systems by leveraging graph structure and temporal dynamics. However, existing dynamic graph models often suffer from unpredictable distribution shifts induced by complex time-varying factors such as emergency incidents, leading to severe performance degradation due to their low out-of-distribution (OOD) generalization. Graph invariant learning has been extensively studied to solve this problem through feature disentanglement in the time or spectral domain. Despite recent advances, existing methods suffer from critical limitations in practice: Temporal-based methods struggle to disentangle transient perturbations and stable patterns that are highly overlapping and entangled within the same period. While spectral-based methods attempt spectral-domain disentanglement via the global Fourier transform, these methods inherently lose temporal localization and fail to effectively characterize distribution shifts driven by time-varying factors. To this end, in this paper, we propose **Wav**elet **C**oefficient-Domain **I**nvariant **L**earning **(WavCIL)**, a novel framework for resolving distribution shifts by conducting disentanglement within a wavelet coefficient domain endowed with time-frequency localization capabilities. Specifically, WavCIL consists of two key components: (i) a wavelet transform module, which leverages a set of wavelet bases to map the input temporal signals into wavelet coefficient domain, simultaneously capturing frequency components and localizing their temporal occurrences; and (ii) a coefficient domain invariant learning module, which utilizes an adaptive mask mechanism to disentangle stable causal patterns invariant to time-varying factors from spurious patterns driven by time-varying factors in the coefficient domain, guiding the prediction process to rely more on the causal patterns. Extensive experiments on several benchmark datasets demonstrate that WavCIL achieves state-of-the-art generalization performance when handling distribution shifts. Our code is released at https://anonymous.4open.science/r/WavCIL-4B8C.

Graph Contrastive Learning (GCL) is an effective approach for learning node representations. However, the intrinsic uncertainty of real-world graph data introduces significant challenges, as GCL relies on crisp deterministic representations that struggle to capture such ambiguity. To model graph uncertainty, fuzzy logic has attracted increasing attention due to its mathematical rigor. Existing methods, however, simply inject fuzzy modeling into the contrastive framework without tailoring data augmentation to the needs of fuzzy representations, resulting in limited discriminability and suboptimal downstream performance. To address these limitations, we propose a novel Fuzzy Graph Contrastive Learning (FGCL) framework for uncertainty-aware node representation learning. It adopts a vertex entanglement-based augmentation strategy to generate tailored multi-views with controlled perturbations while preserving core graph topology and semantics, mitigating semantic corruption. We also design a Deep Weighted Fuzzy Graph Convolutional Neural Network (DWFGCNN) encoder, which maps crisp features to fuzzy representations via learnable membership functions, explicitly models uncertainty, and resolves the core contradiction that traditional encoders cannot balance discriminability and robustness simultaneously. Extensive experiments on multiple datasets demonstrate that FGCL consistently outperforms baselines in node classification, community detection, and link prediction tasks, validating its effectiveness in handling uncertainty in graph representation learning.

Strain engineering for industrial fermentation faces a structural design-test scale gap: combinatorial pathway perturbations of $2$–$3$ enzymes already span $10^4$–$10^6$ candidate strains, while bench-scale fermentation throughput remains on the order of $10^2$ runs per laboratory per year. One way to narrow this gap is in silico evaluation by perturbing a learned gene-expression $\to$ phenotype mapping (conditioned on process state); the precondition is that such a mapping can be learned from bench-scale-sized datasets. As a proof-of-concept, we ask whether a genome-scale metabolic model (GEM)-graph mechanistic prior supports learning such a mapping from $\sim44$ bioreactor runs of an engineered Yarrowia lipolytica astaxanthin-producing strain. We propose a spatio-temporal GNN encoder structured as a Mass Flow Graph over the GEM, paired with a multimodal input head over gene-expression snapshots, sensor streams, time-series assays, and run-level metadata. The encoder is pretrained by masked-flux prediction on Flux Balance Analysis (FBA) samples, distilling the GEM's stoichiometric and mass-balance constraints into it before fermentation data are seen. Under $5$-fold cross-validation across $5$ seeds, the surrogate attains the lowest mean composite test RMSE among the baselines we compare against. Structural ablations show that the GEM-graph prior is necessary—an order-of-magnitude RMSE divergence when removed—while pretraining together with the gene-expression modality make a significant joint contribution, supporting the proof-of-concept claim.

Spiking Neural Networks (SNNs) offer a distinctive paradigm for temporal modeling through their intrinsic membrane potential dynamics. However, existing SNN-based forecasting methods focus exclusively on temporal processing, lacking mechanisms to capture spatial dependencies among variables. To bridge this gap, we propose SpikeSTAG, a neuromorphic spatiotemporal architecture that integrates graph-based spatial reasoning into spike-driven temporal computation. Central to our approach is the Dendritic Graph Module, which reinterprets spectral graph convolutions as biological dendritic integration -- coupling multi-scale spatial aggregation with the temporal dynamics of spiking neurons within a single computational unit. To adaptively fuse the resulting spatial and temporal representations, we further introduce a Dual-Stream Integration Module that employs competitive gating and coincidence-based amplification, selectively enhancing consistent spatiotemporal patterns while suppressing conflicting noise. Extensive experiments demonstrate that SpikeSTAG establishes a new state-of-the-art among SNN-based models and surpasses representative ANN baselines, while reducing theoretical energy consumption by approximately 33.3\% compared to Transformer architectures.

Pre-training Graph Neural Networks (GNNs) via self-supervised learning has become a dominant paradigm, yet efficiently adapting frozen encoders remains a challenge. Graph prompting offers a parameter-efficient alternative to fine-tuning, but existing methods largely treat pre-trained models as opaque feature extractors, ignoring their internal spectral structure. In this work, we identify a systematic phenomenon in pre-trained GNNs, which we term spectral bias: optimization during pre-training disproportionately aligns representations with directions associated with large singular values, leaving low-energy directions under-explored. We show that these underutilized directions can encode complementary information that is beneficial for downstream adaptation, especially under distribution shift. To leverage this insight, we propose Spectral Reverse Prompt (SRP), a prompting framework that rebalances the spectral contributions of frozen GNN encoders. SRP applies a learnable soft-thresholding mask in the spectral domain to down-weight dominant directions while amplifying weaker ones. In addition, SRP incorporates a null-space augmentation module that captures variation in directions with minimal activation under the frozen encoder. Extensive experiments across multiple benchmarks demonstrate that SRP achieves state-of-the-art performance with minimal additional parameters, highlighting that reweighting spectral components is a principled and effective strategy for parameter-efficient graph adaptation.

Exact solution of hard combinatorial optimization problems often relies on strong convex relaxations, but solving these relaxations repeatedly inside a branch-and-bound algorithm can be prohibitively expensive. Hence, we consider this challenge for \new{Max-Cut problem} (Max-Cut), where branch and bound commonly uses semidefinite programming (SDP) relaxations to bound subproblems. We propose a Max-Cut-specific \new{graph neural network} that serves as a principled, lightweight neural proxy for these SDP solvers and can be plugged directly into an exact branch-and-bound framework. The proposed architecture has update steps of complexity $\mathcal{O}(n^2 + ne)$, and predicts both primal- and dual-feasible SDP solutions. The primal SDP solutions yield feasible Max-Cut solutions via the Goemans--Williamson algorithm. In addition, it is trained in a self-supervised fashion without requiring solved SDP relaxations as labels. Empirically, we show that our architecture can substantially reduce the cost of bounding in exact Max-Cut solving by up to $10.6 \times$ compared with using the state-of-the-art SDP solver Mosek. Our work highlights the potential of learned, validity-preserving surrogates for accelerating exact optimization over structured convex relaxations.

Post-hoc Graph Neural Networks (GNN) explainers typically extract a compact subgraph to preserve the model’s decision rationale. However, this extraction breaks topological integrity and induces a distribution shift, making predictions on subgraphs unreliable and consequently misleading explainer optimization under OOD settings. Existing attempts to build in-distribution proxy graphs often assume independence between explanation and background subgraphs and rely on hard splicing, which causes semantic mismatch and boundary discontinuities that degrade explanation reliability. We propose SSDGExplainer, a Structure–Semantic Dual-Guided explainer that formulates proxy-graph generation as conditional modeling under semantic consistency constraints to achieve deep semantic alignment between the explanation subgraph and the generated background, introduces a topology boundary optimization network to smooth structural fractures at the explanation–background interface, and enforces contrastive semantic constraints to prevent semantic drift. Extensive experiments on synthetic and real-world benchmarks demonstrate consistent improvements over state-of-the-art methods in both explanation quality and fidelity.

Graph Neural Networks (GNNs) have achieved remarkable performance in a wide range of graph-related learning tasks. However, explaining their predictions remains a challenging problem, especially due to the mismatch between the graphs used during training and those encountered during explanation. Most existing methods optimize soft edge masks on weighted graphs to highlight important substructures, but these graphs differ from the unweighted graphs on which GNNs are trained. This distributional shift leads to unreliable gradients and degraded explanation quality, especially when generating small, sparse subgraphs. To address this issue, we propose explaining a robust surrogate whose explanations provide a faithful proxy for those of the original model. Specifically, we train this surrogate model through an iterative re-weighting strategy that alternates between identifying explanation subgraphs and adapting the model to the resulting weighted graph distribution, supporting stable explanation refinement while preserving the validity of the soft-mask relaxation. We evaluate our method on multiple benchmark datasets using different GNN backbones and explanation methods. Experimental results show that our method consistently improves explanation quality and can be flexibly integrated with different architectures.

Diffusion models represent a powerful class of generative models known for their solid theoretical foundations and remarkable performance across diverse tasks and domains. While diffusion models have been extensively utilized for generating entire graphs or small-scale graphs, no diffusion-based approaches have been developed to synthesize graph structures within an existing graph, including synthetic nodes and their associated edges. In this study, we introduce the Robust Graph Diffusion Model (RGDM), designed to generate labeled synthetic graph structures consisting of nodes and edges that integrate seamlessly into a given graph. The RGDM consists of a Robust Graph Autoencoder (RGAE) and a Latent Diffusion Model (LDM). Leveraging an edge selection mechanism and an innovative low-rank regularization on the latent feature, the RGDM produces clean and high-quality synthetic graph structures, even when trained on graphs subject to adversarial attacks. Comprehensive experimental evaluations reveal that Graph Neural Networks (GNNs) trained on the augmented graph, which is formed by merging the original attacked graph with the synthetic graph structures, exhibit significantly improved robustness against various graph adversarial attacks in the context of semi-supervised node classification. The code of the RGDM is available at \url{https://anonymous.4open.science/r/RGDM}.

Graph Contrastive Learning (GCL) has shown strong promise for unsupervised graph representation learning, yet its effectiveness remains limited on heterophilic graphs, where connected nodes often belong to different classes. Existing methods rely on complex augmentation schemes, intricate encoders, or negative sampling, which raises the question of whether such complexity is truly necessary in this challenging setting. In this work, we revisit the foundations of supervised and unsupervised learning on graphs and uncover a simple yet effective principle for GCL: mitigating node feature noise by aggregating it with structural features derived from the graph topology. This phenomenological study suggests that the original node features and the graph structure naturally provide two complementary views for contrastive learning. Building on this insight, we propose an embarrassingly simple GCL model that uses a GCN encoder to capture structural features and an MLP encoder to isolate node feature noise. Our design requires neither data augmentation nor negative sampling, yet achieves state-of-the-art results on heterophilic benchmarks with minimal computational and memory overhead, while offering advantages in homophilic graphs in terms of complexity, scalability, and robustness. Moreover, a variant of GCN-MLP based on the same principle also achieves SOTA performance on homophilic datasets. We provide theoretical justification for our approach and validate its effectiveness through extensive experiments.

Matern Gaussian processes offer a principled framework for learning and uncertainty quantification on graphs. However, they struggle with heterogeneous networks. A central challenge is that variance at a node can represent genuine signal that should strongly propagate (diffuse) to neighbors, mere noise that should be isolated, or a mixture of both. While this problem has been studied in continuous spatial domains, directly translating those approaches to graphs leaves a free parameter per node, causing extreme over-parameterization. To resolve this, we introduce non-stationary Variance-Coupled Gaussian Processes (VCGPs). These models use an auxiliary signal (often easily derived from historical data) to determine relative diffusivity between nodes, tied to the regression data via a single learned hyperparameter, $\gamma$. The sign of $\gamma$ captures whether the auxiliary signal is directly or inversely proportional to node diffusivity, while its magnitude calibrates this relationship.We formally prove that $\gamma = 1$ is the unique point where VCGPs are stationary up to rescaling, ensuring that varying $\gamma$ results in genuinely non-stationary correlations. Across five real-world datasets, our VCGPs match or outperform both stationary and heavily parameterized non-stationary baselines.

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.

Physics-based digital twins aim to predict the dynamics of real-world objects under interaction, enabling real-to-sim-to-real applications in robotics. Current approaches reconstruct such twins as explicit physical models (such as spring-mass systems) to predict the dynamics, but the resulting models often inherit the resolution of the visual reconstruction rather than being reduced to the physical complexity required to reproduce task-relevant dynamics. This mismatch introduces redundant topology, making repeated forward-dynamics rollouts unnecessarily expensive. To address this challenge, we present PhySPRING, an fully differentiable GNN-based method to reduce complexity in spring--mass digital twins. PhySPRING jointly learns a hierarchy of coarsened graph topologies and their mechanical parameters from observations. At each reduction level, PhySPRING merges nodes with similar learned dynamic responses to optimize the topology, while maintaining every reduced layer as an explicit spring--mass system. On the PhysTwin benchmark, PhySPRING improves dense reconstruction and prediction accuracy over PhysTwin, while reduced models retain stable physical and visual fidelity with up to a 2.30$\times$ speed-up. We further demonstrate the effectiveness of PhySPRING in a Real2Sim robot policy-evaluation pipeline, where the reduced models are substituted zero-shot into ACT and $\pi_0$ evaluations, maintaining comparable manipulation success rates across downsampling levels while improving action-sampling effectiveness. Together, PhySPRING enables efficient and structure-preserving spring--mass reduction without sacrificing fidelity or robotic utility.

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

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.

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.