NeurIPS 2026 论文列表

The joint use of graph structure and node-specific information is central to transductive node classification, yet a fundamental theoretical question remains unanswered: when does graph structure actually help? We provide the first non-asymptotic, distribution-free answer to this question. We build on nuclear-norm graph clustering and classical convex clustering, generalizing the latter to incorporate node features, partial labels, and general convex loss functions, making it suitable for transductive node classification. We analyze each problem separately to characterize when graph structure alone, or node information alone, is sufficient for perfect recovery. We then formulate a unified convex optimization problem through a shared atomic norm representation, and prove that there exist conditions under which neither source alone achieves perfect recovery but using both jointly does, revealing a bidirectional synergy: node information improves clustering, while graph structure improves classification.

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.

Graph learning research has increasingly shifted toward continual graph learning (CGL), which better reflects real-world scenarios where graphs evolve over time. However, existing CGL methods largely assume clean supervision and overlook a critical challenge: the newly arriving portions of the graph are often noisy, due to annotation errors or adversarial corruption. This mismatch limits their applicability in practice. In this work, we study robust continual graph learning, where models must simultaneously handle catastrophic forgetting and noisy supervision in evolving graph data. We show that label noise introduces a new failure mode—catastrophic remembering, where models persistently reinforce corrupted knowledge across tasks. To address these challenges, we propose a Unified Flow-Oriented framework (UFO). First, UFO models conditional feature distributions via flow-based generative modeling and produces replay representations, mitigating forgetting without storing historical data. Second, UFO estimates instance-level reliability scores to distinguish clean from noisy nodes, reducing the impact of corrupted supervision and alleviating catastrophic remembering. Extensive experiments on four benchmark graph datasets under varying noise ratios demonstrate that UFO consistently outperforms existing methods in both accuracy and forgetting metrics. Code is available at: https://anonymous.4open.science/r/UFO.

Graph neural networks are widely deployed in real-world applications, where attackers often operate under strict black-box constraints, making effective graph black-box attacks particularly important. However, existing methods are fundamentally limited by poor universality, as attack strategies learned on specific graphs or model configurations fail to generalize across different graph datasets. Inspired by the unified representation principle of graph foundation models, we propose a universal black-box attack framework that learns transferable attack paradigms from multiple source graphs and generalizes directly to unseen target graphs. The framework incorporates a representation selection mechanism and a graph variational autoencoder based modeling strategy to ensure consistency and mappability between the unified semantic space and the original representation space, together with a structure–representation joint anchor node selection mechanism for effective attack construction. Extensive experiments on benchmark datasets show that our method achieves strong universality and consistently superior attack performance.

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.

Graph-level anomaly detection (GLAD) is a critical task in domains like social networks and bioinformatics. However, current unsupervised contrastive learning-based methods rely on semantically homogeneous augmentations, leading to catastrophic informational overlap that trivializes the learning objective and effectively masks anomalous signals in GLAD. To overcome this, we propose Sima (Semantically Complementary Spectral Views), a novel contrastive framework that learns from semantically complementary spectral views rather than redundant homogeneous views. Sima first constructs a pair of spectral views to separately capture global community structure and local heterophilous variations, which together cover the full graph spectrum of anomalous patterns. Inspired by the Multi-View Information Bottleneck principle, we further design a soft subgraph extraction module with Score Reconstruction Attention (SRA) and an anchor-guided condensation mechanism to distill the essential shared information from each view into a compact representation. We then optimize a contrastive objective across these distilled views to enforce cross-view alignment and amplify subtle structural deviations. Extensive experiments on challenging GLAD and graph-level out-of-distribution detection (GLOD) benchmarks demonstrate that Sima achieves substantial and consistent gains in average performance over state-of-the-art baselines.

Most graph neural networks propagate information through a fixed-coefficient polynomial filter applied uniformly across every node and every layer. However, the appropriate filter varies along two distinct axes that such a parameterization cannot accommodate. Within a single graph, different nodes benefit from different mixtures of low-pass smoothing, high-pass contrast, and pass-through behavior. Across graphs, signal propagation dynamics themselves differ, with some graphs benefiting from long-range propagation across many hops while others require damping to prevent over-smoothing. The appropriate filter is therefore not a single fixed object at all, but a state-dependent composition whose behavior changes according to a node's current representation and its propagation history. We propose Castor, a self-tuning graph filter that realizes this composition through state-dependent decisions made at every step of propagation. A router reads each node's current state together with its initial state, and emits per-node mixing weights over three primitives, namely low-pass smoothing, high-pass contrast, and identity. A learnable per-hop coefficient then determines how much of the most recent change in the propagation is carried forward, accelerating the iteration when positive and damping it when negative. Setting the coefficient to zero recovers standard first-order propagation. Across fourteen standard node-classification benchmarks spanning the full homophily spectrum, a single Castor instance ranks top-three on every dataset and achieves an average rank of $2.07$, more than $3.5$ ranks ahead of the next-best of fourteen baselines.

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), as representative deep models designed for graph data, effectively learn graph topological information and push the performance boundaries across various graph tasks. However, the computational and memory burden of GNNs poses significant challenges for scaling to large real-world graphs. Spiking Graph Neural Networks (SGNNs), which integrate biologically plausible learning via unique spike-based neurons, have emerged as a promising energy-efficient alternative. Different layers communicate with sparse and binary spikes, which facilitates computation and storage of intermediate graph representations. Despite the proliferation of SGNNs proposed in recent years, there is no systematic benchmark to explore the basic design principles of these brain-inspired networks on the graph data. To bridge this gap, we present **SGNNBench** to quantify progress in the field of SGNNs. Specifically, we elaborately investigate the design space of SGNNs to facilitate the development of a general SGNN paradigm. Regarding efficiency, we empirically compare these baselines w.r.t. model size, memory usage and theoretical energy consumption to reveal previously overlooked energy bottlenecks. Furthermore, SGNNBench establishes a unified and reliable benchmark to comprehensively evaluate 9 state-of-the-art SGNNs across 20 datasets covering diverse graph settings and tasks.

Graph Neural Networks (GNNs) face a fundamental dichotomy between expressiveness and scalability. Recent spectral and transformer-based models approach universal approximation capabilities but rely on computationally intensive global operators that scale poorly to large graphs. Conversely, scalable approaches often compromise structural fidelity through sampling or decoupling, resulting in incomplete structural acquisition. We identify that this trade-off stems from a homogeneous treatment of graph topology, where uniform computational complexity is applied to heterogeneous structures. We propose a paradigm shift towards Hierarchical Structural Acquisition and introduce S\&P (Scalable \& Powerful), a framework grounded in Fusion Frame Theory that aligns the operator with the intrinsic hierarchy of the data. S\&P decomposes the global operator into intra-component and inter-component, and we prove that this design preserves universal spectral filtering capacity for non-degenerate inputs while remaining numerically stable and linear in complexity. Experiments on 14 datasets show that S\&P achieves state-of-the-art accuracy, bridging the gap between scalability and expressiveness. Our code is available at https://anonymous.4open.science/r/HierarchicalSP.

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.

Anchor graphs are a standard route to scalable multi-view clustering, but most existing pipelines still depend on either a shared anchor set sampled from concatenated features or a separate anchor-alignment stage before fusion. Both choices are restrictive: the former hard-codes equal anchor budgets and importance at anchor-construction time, while the latter introduces a cumbersome correspondence problem and still struggles with unequal anchor numbers. We develop an alignment-free probabilistic formulation in which view-specific anchor graphs are noisy manifestations of a shared latent cluster identity rather than objects that require cross-view correspondence. Each view has its own anchor space, number of anchors and cluster prototypes; the only shared latent variable is the sample label. We instantiate this idea with a Gaussian latent-label model and a deterministic prototype M-step. The resulting variational EM algorithm admits closed-form updates with convergence guarantees, while experiments demonstrate competitive clustering performance and practical runtime on most datasets.

In recent years, large language models (LLMs) have demonstrated remarkable capability to generalize across diverse natural language processing tasks, inspiring the development of graph foundation models (GFMs) for large-scale pre-training. However, unlike language models with explicit token units, graphs lack a well-defined unit for generalization, making it challenging to design effective pre-training strategies. In this work, we propose REEF, a novel GFM framework that leverages relation tokens as the fundamental units. We construct a vocabulary of relation tokens to encode relational information within graphs. To accommodate diverse relations, we introduce two hypernetworks that adaptively generate the parameters of aggregators and classifiers in graph neural networks based on relation tokens. In addition, we design another hypernetwork to construct dataset-specific projectors and incorporate a dataset-level feature bias into the initial node representations, enhancing flexibility across different datasets with the same relation. Extensive experiments demonstrate that REEF consistently outperforms existing methods in both pre-training and transfer learning, highlighting its potential as a general-purpose graph foundation model. Our code is publicly available at https://anonymous.4open.science/r/REEF-16CF/.

Generative recommendation has recently emerged as a promising paradigm for large-scale recommendation by reformulating next-item prediction as discrete sequence generation. However, current SID-based models rely mainly on history-to-next-item supervision, leaving item--item collaborative topology only indirectly captured through sparse user sequences. To address this gap, we propose *R-GRec*, a graph-derived structural supervision framework for SID-based generative recommendation. From user interactions, *R-GRec* builds an item--item graph and derives three complementary auxiliary objectives---Neighbor Prediction, Topological Contrast, and Link Prediction --- to make collaborative topology explicit during generative training. Extensive experiments on the two public Amazon datasets demonstrate that R-GRec achieves state-of-the-art performance over representative traditional, generative, and LLM-based recommenders. Further ablation and analytical studies verify the contribution of each graph-derived objective and show that collaborative topology acts as a complementary supervision signal to Semantic ID generation, improving generative recommendation without adding inference-time graph computation.