ICML 2026 Papers

Dynamic graphs are pervasive in real-world systems, but their tightly entangled spatiotemporal evolution causes significant modeling challenges. Existing Dynamic Graph Neural Networks (DGNNs) lack a principled framework for systematically decoupling this multi-domain entanglement, raising two key problems: (i) representation drift caused by structural incompleteness, and (ii) signal distortion amplified by noise perturbation. These problems can accumulate over time, forming temporal redundancy that weakens robustness of DGNNs. In view of these, we propose DeR-Mamba(Decoupling for Robust Mamba), a multi-domain decoupling framework for robust DGNNs. To address (i), we develop the Multi-Particle Kernel Kalman observation field (MP-K$^2$alman), which achieves spatial decoupling by sampling latent evolution paths in kernel subspaces and performing Kalman-style updates to estimate structural states. To address (ii), we design the Adversarial-aware Frequency Decoupling Module (AFDM), which performs frequency-domain decoupling and dynamic cross-frequency modulation to purify spectral signals. Finally, a self-consistent dynamic graph state-space system performs temporal decoupling to control redundancy, suppressing residual disturbances through discretized cross-time modeling and selective snapshot scanning. Extensive experiments on benchmark datasets with adversarial attacks validate its superior robustness.

Graph neural networks (GNNs) are widely believed to excel at node representation learning through trainable neighborhood aggregations. We challenge this view by introducing Fixed Aggregation Features (FAFs), a training-free approach that transforms graph learning tasks into tabular problems. This simple shift enables the use of well-established tabular methods, offering strong interpretability and the flexibility to deploy diverse classifiers. Across 14 benchmarks, well-tuned multilayer perceptrons trained on FAFs rival or outperform state-of-the-art GNNs and graph transformers on 12 tasks—often using only mean aggregation. The only exceptions are the Roman Empire and Minesweeper datasets, which typically require unusually deep GNNs. To explain the theoretical possibility of non-trainable aggregations, we connect our findings to Kolmogorov–Arnold representations and discuss when mean aggregation can be sufficient. In conclusion, our results call for (i) richer benchmarks benefiting from learning diverse neighborhood aggregations, (ii) strong tabular baselines as standard, and (iii) employing and advancing tabular models for graph data to gain new insights into related tasks.

Training data plays a central role in large language models (LLMs) optimization, motivating extensive research on data scheduling strategies. Most existing approaches concentrate on adjusting the overall data distribution but neglect the underlying interactions between samples during training. However, we argue that such interactions cannot be overlooked, as real-world data samples frequently exhibit directional influences on each other, making the training order crucial. Intuitively, we can prioritize train-units with greater influence to improves learning efficiency. In this work, we propose $D^3$, a **D**ynamic, **D**irectional graph-constrained **D**ata scheduling framework. $D^3$ formulates the complex interactions among train-units as a dynamic influence graph, where edges represent loss-based dependencies. It then solves a constrained optimization problem over this graph to derive the training order, which ensures that the data sequence respects the evolving information flow throughout training. Our approach is theoretically motivated and yields consistent improvements over existing data scheduling methods across both pre-training and post-training phases. Furthermore, for scalability, $D^3$ also employs an efficient approximation algorithm that keeps the additional computational overhead within a manageable range. For future research, the code is available at https://github.com/xuyj233/D3.

Equivariant Graph Neural Networks (EGNNs) have become a widely used approach for modeling 3D atomistic systems. However, mainstream architectures face critical efficiency bottlenecks due to the explicit construction of geometric features or dense tensor products on \textit{every} edge. To overcome this, we introduce \textbf{E2Former-V2}, an efficient architecture that integrates algebraic sparsity with hardware-aware execution. We introduce \textbf{Equivariant Axis-Aligned Sparsification (EAAS)}, which leverages an $\mathrm{SO}(3)\!\rightarrow\!\mathrm{SO}(2)$ change of basis to convert dense Wigner-$6j$ tensor contractions into sparse, parity-based re-indexing operations. Building on this representation, we propose \textbf{On-the-Fly Equivariant Attention}, a fully node-centric mechanism implemented via a fused Triton kernel. By eliminating materialized edge tensors and maximizing SRAM utilization, our kernel achieves up to \textbf{20$\times$ higher TFLOPS} than standard implementations. Experiments on SPICE and OMol25 show that E2Former-V2 preserves predictive accuracy while substantially accelerating inference, demonstrating the practical feasibility of large equivariant transformers on commodity GPUs. Our released code can be found at \url{https://github.com/IQuestLab/UBio-MolFM/tree/main}

Graph structure learning is a core problem in graph-based machine learning, essential for uncovering latent relationships and ensuring model interpretability. However, most existing approaches are ill-suited for large-scale and dynamically evolving graphs, as they often require complete re-learning of the structure upon the arrival of new nodes and incur substantial computational and memory costs. In this work, we propose GraphFLEx—a unified and scalable framework for Graph Structure Learning in Large and Expanding Graphs. GraphFLEx mitigates the scalability bottlenecks by restricting edge formation to structurally relevant subsets of nodes identified through a combination of clustering and coarsening techniques. This dramatically reduces the search space and enables efficient, incremental graph updates. The framework supports 48 flexible configurations by integrating diverse choices of learning paradigms, coarsening strategies, and clustering methods, making it adaptable to a wide range of graph settings and learning objectives. Extensive experiments across 26 diverse datasets and graph neural network architectures demonstrate that GraphFLEx achieves state-of-the-art performance with significantly improved scalability. Our implementation is publicly available here: https://anonymous.4open.science/r/Scaling_Graph_Learning-CB67/README.md.

We introduce TANGO, a dynamical-systems-inspired framework for graph representation learning that governs node feature evolution through a learned energy landscape and its associated descent dynamics. At the core of our approach is a learnable Lyapunov function over node embeddings, whose gradient defines an energy non-increasing direction that guarantees stability. To enhance flexibility while preserving the benefits of energy-based dynamics, we incorporate a novel tangential component, learned via message passing, that evolves features while maintaining the energy value. This decomposition into orthogonal flows of energy gradient descent and tangential evolution yields a flexible form of graph dynamics, and enables effective signal propagation even in flat or ill-conditioned energy regions, that often appear in graph learning. Our method is designed to help alleviate oversquashing, and is compatible with different graph neural network backbones. Empirically, TANGO achieves strong performance across a diverse set of node and graph classification and regression benchmarks, demonstrating the effectiveness of jointly learned energy functions and tangential flows for graph neural networks.

In recent advances, to enable a fully data-driven learning paradigm on relational databases (RDB), relational deep learning (RDL) is proposed to structure the RDB as a heterogeneous entity graph and adopt the graph neural network (GNN) as the predictive model. However, existing RDL methods neglect the imbalance problem of relational data in RDBs and risk under-representing the minority entities, leading to an unusable model in practice. In this work, we investigate, for the first time, class imbalance problem in RDB entity classification and design the relation-centric minority synthetic over-sampling GNN (**Rel-MOSS**), in order to fill a critical void in the current literature. Specifically, to mitigate the issue of minority-related information being submerged by majority counterparts, we design the relation-wise gating controller to modulate neighborhood messages from each individual relation type. Based on the relational-gated representations, we further propose the relation-guided minority synthesizer for over-sampling, which integrates the entity relational signatures to maintain relational consistency. Extensive experiments on 12 entity classification datasets provide compelling evidence for the superiority of Rel-MOSS, yielding an average improvement of up to 2.46% and 4.00% in terms of *Balanced Accuracy* and *G-Mean*, compared with SOTA RDL methods and classic methods for handling class imbalance.

Dynamic graph anomaly detection is critical for many real-world applications but remains challenging due to the scarcity of labeled anomalies. Existing methods are either unsupervised or semi-supervised: unsupervised methods avoid the need for labeled anomalies but often produce ambiguous boundary, whereas semi-supervised methods can overfit to the limited labeled anomalies and generalize poorly to unseen anomalies. To address this gap, we consider a largely underexplored problem: learning a discriminative boundary from normal/unlabeled data, while leveraging limited labeled anomalies \textbf{when available} without sacrificing generalization to unseen anomalies. In this paper, we propose an effective, generalizable, and model-agnostic framework with three main components: (i) residual representation encoding that capture deviations between current interactions and their historical context, providing anomaly-relevant signals; (ii) a restriction loss that constrain the normal representations within an interval bounded by two co-centered hyperspheres, ensuring consistent scales while keeping anomalies separable; (iii) a bi-boundary optimization strategy that learns a discriminative and robust boundary using the log-likelihood distribution modeled by a normalizing flow. Extensive experiments demonstrate the superiority of our framework across diverse evaluation settings.

Explainability for graph neural networks (GNNs) aims to unveil the complex decision logic of learned models by identifying the most influential structures in the input graph, thereby improving transparency and trustworthiness. Existing post-hoc explainers typically extract a sparse key subgraph at a single scale as the explanation. However, a single-scale view often fails to capture multi-level semantics, and the optimization procedure may degenerate into a local search that is sensitive to initialization and noise, leading to unstable explanations and compromising their reliability. To address these issues, we propose MSExplainer, a multi-scale explainer for GNNs. MSExplainer couples multi-scale subgraph consistency guidance with single-scale adaptive subgraph learning under a parameter-sharing design. It simultaneously extracts multi-scale key subgraphs and complementary subgraphs, yielding a hierarchical decomposition of the original graph that covers semantics at different granularities and improves the stability of subgraph extraction. Experiments on six benchmark datasets show that MSExplainer generally outperforms prior methods in explanation accuracy and fidelity. Moreover, we theoretically prove the upper bound advantage of the multi-scale strategy in representation consistency, and derive that it achieves the same-order computational complexity as single-scale methods under the parameter-sharing mechanism, thus ensuring the high fidelity of key subgraphs while maintaining computational efficiency.

Dynamic graph learning, which focuses on modeling the merging, vanishing, and reconnection of nodes and edges, is crucial for real-world applications. In dynamic graphs, node neighborhoods often exhibit diverse and time-evolving topologies, including hierarchical, grid-like, and cyclic patterns. Existing methods typically embed graphs into a single curvature space, which limits the quality of node representations when the embedding geometry is not aligned well with the local graph topology. In this paper, we propose **DyGMoCE**, a **Dy**namic **G**raph Transformer with a **M**ixture **o**f **C**urvature-aware **E**xperts, which efficiently embeds each node at every timestamp into an adaptive curvature space. Specifically, DyGMoCE incorporates a mixture-of-experts framework to both the attention and feed-forward modules, where each expert operates on a Riemannian manifold with a distinct curvature. Then, motivated by the geometric continuity across the experts, we introduce a routing mechanism with a ranking constraint. To improve efficiency, we design a fast Riemannian attention module for DyGMoCE, achieving an average speedup of 27.5% and memory reduction of 52.6%. Notably, the fast Riemannian attention module is broadly applicable to Transformer models with sequence inputs. Extensive experimental results show that DyGMoCE significantly outperforms other state-of-the-art methods.

Real-world graph datasets often arise from mixtures of populations, where graphs are generated by multiple distinct underlying distributions. In this work, we propose a unified framework that explicitly models graph data as a mixture of probabilistic graph generative models represented by graphons. To characterize and estimate these graphons, we leverage graph moments (motif densities) to cluster graphs generated from the same underlying model. We establish a novel theoretical guarantee, deriving a tighter bound showing that graphs sampled from structurally similar graphons exhibit similar motif densities with high probability. This result enables principled estimation of graphon mixture components. We show how incorporating estimated graphon mixture components enhances two widely used downstream paradigms: graph data augmentation via mixup and graph contrastive learning. By conditioning these methods on the underlying generative models, we develop graphon-mixture-aware mixup (GMAM) and model-aware graph contrastive learning (MGCL). Extensive experiments on both simulated and real-world datasets demonstrate strong empirical performance. In supervised learning, GMAM outperforms existing augmentation strategies, achieving new state-of-the-art accuracy on 6 out of 7 datasets. In unsupervised learning, MGCL performs competitively across seven benchmark datasets and achieves the lowest average rank overall.

Oversmoothing has long been identified as a major limitation of Graph Neural Networks (GNNs): input node features are smoothed at each layer and converge to a constant non-informative representation, *if the weights of the GNN are sufficiently bounded*. This assumption is crucial: if, on the contrary, the weights are sufficiently large, then oversmoothing may be compensated. Theoretically, GNN could thus *learn* to not oversmooth. However, this does not really happen in practice, which prompts us to examine oversmoothing from an *optimization* point of view. In this paper, we analyze *backward oversmoothing*, that is, the notion that backpropagated errors are also subject to oversmoothing from output to input. With non-linearities, we outline the key role of the *interaction* between forward and backward smoothing. Moreover, we show that, due to backward oversmoothing, GNNs provably exhibit many *spurious stationary points*: as soon as the *last* layer is trained, the *whole* GNN is at a stationary point. As a result, we can exhibit regions where gradients are near-zero while the loss stays high. Additionally, we prove that this is *specific* to GNNs, and does not necessarily hold for Multi-Layer Perceptrons. This paper is a step toward a more complete comprehension of the optimization landscape of GNNs.

Vector Quantization (VQ) has recently emerged as a promising approach for learning compressed and discrete representations for graph-structured data. However, a fundamental challenge, i.e., codebook collapse, remains underexplored in the graph domain, significantly limiting the expressiveness and generalization of graph tokens. In this paper, we present an empirical study and observe that codebook collapse consistently occurs when training VQ jointly with Graph Neural Networks under graph reconstruction tasks, even with mitigation strategies proposed in vision or language domains. Moreover, we provide a diagnosis of collapse from data and optimization perspectives, showing that collapse is associated with graph data properties such as feature redundancy and connectivity density, and is further reinforced by the training dynamics of deterministic hard assignment. To address these issues, we propose RGVQ, a novel framework that integrates graph topology and feature similarity as explicit regularization signals to enhance codebook utilization and promote token diversity. RGVQ introduces soft assignments via Gumbel-Softmax reparameterization, ensuring that all codewords receive gradient updates. In addition, RGVQ incorporates a structure-aware contrastive regularization to penalize assigning the same token to dissimilar node pairs. Extensive experiments demonstrate that RGVQ substantially improves codebook utilization and consistently boosts the performance of state-of-the-art graph VQ backbones across multiple downstream tasks, enabling more expressive and transferable graph token representations.

Graph learning has been increasingly deployed in critical and sensitive domains, raising pressing demands for trustworthiness-robustness, fairness, and beyond. However, these properties are often undermined by various perturbations, which induce distributional uncertainty and compromise the trustworthiness of graph learning. To address this, we propose DICT, a novel framework that models distributional uncertainty to achieve trustworthy graph learning. Specifically, DICT formulates a unified optimization objective that captures perturbation-induced distributional shifts in graph topology, node features, and labels, and minimizes the worst-case risk over the uncertainty set. However, directly optimizing this objective in its primal form leads to an infinite-dimensional problem. To make this problem tractable, we integrate strong duality and local Lipschitz continuity of the loss, reformulating the objective as a finite-dimensional min-max problem. We focus on robustness and fairness as primary instantiations of DICT because they are not only critical in real-world applications, but also provide transferable modeling principles for broader trustworthiness objectives. By formulating fairness in the form of an uncertainty set, DICT pioneers unified robustness and fairness within a single optimization framework. Extensive experiments across diverse benchmarks and backbones demonstrate that DICT consistently improves both robustness and fairness, validating the effectiveness and adaptability of the DICT framework.

Semidefinite programs (SDPs) are a powerful framework for convex optimization and for constructing strong relaxations of hard combinatorial problems. However, solving large SDPs can be computationally expensive, motivating the use of machine learning models as fast computational surrogates. Graph neural networks (GNNs) are a natural candidate in this setting due to their sparsity-awareness and ability to model variable-constraint interactions. In this work, we study what expressive power is sufficient to recover optimal SDP solutions. We first prove negative results showing that standard GNN architectures fail on recovering linear SDP solutions. We then identify a more expressive architecture that captures the key structure of SDPs and can, in particular, emulate the updates of a standard first-order solver. Empirically, on both synthetic and SDPLIB benchmarks of various classes of SDPs, this more expressive architecture achieves consistently lower prediction error and objective gap than theoretically weaker baselines. Finally, using the learned high-quality predictions to warm-start the first-order solver yields practical speedups of up to 80%.

Hypergraph Neural Networks (HNNs) have emerged as powerful tools for modeling complex high-order correlations. Most existing HNNs adhere to a two-stage message passing paradigm, where node feature propagation is mediated by hyperedges. In this paper, we analyze two structural limitations of this paradigm, which we term rank collapse and hyperedge semantic dependency. To address these challenges, we propose the Multi-Channel Hypergraph Neural Network (MC-HNN). We design a multi-channel message passing mechanism to maintain high-rank representations, while simultaneously introducing a latent hyperedge type encoding mechanism to inject an independent degree of freedom into hyperedge representations. Our analysis and experiments suggest that MC-HNN alleviates these bottlenecks and achieves strong empirical performance.

Graph Masked Auto-Encoder (GMAE) has emerged as a prevalent self-supervised paradigm, showing superior performance in graph learning. However, existing methods mainly emphasize reconstruction outcomes and give limited specification to how neighborhood context is used for reconstruction. Our experimental investigation shows that, even when reconstruction outcomes are similar, the ways of using neighborhood context differ substantially, resulting in performance shifts. To address this issue, we propose Consistency- and Coverage-aware Graph Masked Auto-Encoder (C2-GMAE), which encourages more consistent use of neighborhood context and promotes broader training coverage in the graph. Specifically, C2-GMAE leverages positional encoding as an observable structural reference, introduces density-partitioned masking to improve coverage across regions, and amplifies heterophilic edges to reduce the attenuation of discriminative relational information during reconstruction. Extensive experiments on multiple benchmarks demonstrate that C2-GMAE improves downstream performance against GMAE baselines.

We propose a novel benchmarking methodology for graph neural networks (GNNs) based on the graph alignment problem, a combinatorial optimization task that generalizes graph isomorphism by aligning two unlabeled graphs to maximize overlapping edges. We frame this problem as a self-supervised learning task and present several methods to generate graph alignment datasets using synthetic random graphs and real-world graph datasets from multiple domains. For a given graph dataset, we generate a family of graph alignment datasets with increasing difficulty, allowing us to rank the performance of various architectures. Our experiments prove that there is an optimal task difficulty for having a statistically relevant ranking of different models and that, even on a structure-only task, anisotropic models perform better compared to isotropic ones. To further prove that our synthetic task capture meaningful information, we show its effectiveness for self-supervised GNN pre-training: the learned node embeddings can be leveraged as positional encodings by transformers for graph regression or can be used to reconstruct the full structure of the graph with $98\%$ accuracy. To support reproducibility and further research, we provide an open-source Python package to generate graph alignment datasets and benchmark new GNN architectures. The source code is available at [graph-alignment-benchmark](https://github.com/adrien-lagesse/graph-alignment-benchmark).

Graph Prompt Learning (GPL) has recently emerged as a promising paradigm for downstream adaptation of pre-trained graph models, mitigating the misalignment between pre-training objectives and downstream tasks. Recently, the focus of GPL has shifted from in-domain to cross-domain scenarios, which is closer to the real world applications, where the pre-training source and downstream target often differ substantially in data distribution. However, why GPLs remain effective under such domain shifts is still unexplored. Empirically, we observe that representative GPL methods are competitive with two simple baselines in cross-domain settings: full fine-tuning (FT) and linear probing (LP), motivating us to explore a deeper understanding of the prompting mechanism. We provide a theoretical analysis demonstrating that jointly leveraging these two complementary branches yields a smaller estimation error than using either branch alone, formally proving that cross-domain GPL benefits from the integration between pre-trained knowledge and task-specific adaptation. Based on this insight, we propose GP2F, a dual-branch GPL method that explicitly instantiates the two extremes: (1) a frozen branch that retains pre-trained knowledge, and (2) an adapted branch with lightweight adapters for task-specific adaptation. We then perform adaptive fusion under topology constraints via a contrastive loss and a topology-consistent loss. Extensive experiments on cross-domain few-shot node and graph classification demonstrate that our method outperforms existing methods.