Invariant-Based Diagnostics for Graph Benchmarks

• URL: http://arxiv.org/abs/2605.06462v1
• Date: Thu, 07 May 2026 15:51:43 GMT
• Title: Invariant-Based Diagnostics for Graph Benchmarks
• Abstract summary: We propose graph invariants as a diagnostic framework for graph benchmarks.<n>We show that (i) invariants are more expressive than standard GNNs, (ii) invariants characterize structural heterogeneity within and across benchmark datasets, (iii) invariants predict multi-task performance, and (iv) simple invariant-based models are competitive with, and sometimes exceed, transformer and message-passing baselines.
• Score: 16.239542747309727
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Progress on graph foundation models is hindered by benchmark practices that conflate the contributions of node features and graph structure, making it hard to tell whether a model actually learns from connectivity, or whether it even needs to. We propose addressing this using graph invariants, i.e., permutation-invariant, task-agnostic structural descriptors that serve as a diagnostic framework for graph benchmarks. We show that (i) invariants are more expressive than standard GNNs, (ii) invariants characterize structural heterogeneity within and across benchmark datasets, (iii) invariants predict multi-task performance, and (iv) simple invariant-based models are competitive with, and sometimes exceed, transformer and message-passing baselines across 26 datasets. Our results suggest that expressivity is not the main driver of predictive performance, and that on tasks where structure matters, a non-trainable structural proxy often matches trained message-passing models. We thus posit that invariant baselines should become a standard for evaluating whether structure is required for a task and whether a model picks up on it, serving as a stepping stone towards graph foundation models.

Related papers

• DARTS-GT: Differentiable Architecture Search for Graph Transformers with Quantifiable Instance-Specific Interpretability Analysis [0.0]
  Graph Transformers (GTs) have emerged as powerful architectures for graph-structured data, yet remain constrained by rigid designs and lack quantifiable interpretability.<n>We develop the first quantitative interpretability framework for GTs through causal ablation.<n>Experiments show DARTS-GT achieves state-of-the-art redesigns on four datasets while remaining competitive on others.<n>Our interpretability analysis reveals that visual attention salience and causal importance do not always correlate, indicating widely used visualization approaches may miss components that actually matter.
  arXiv  Detail & Related papers  (2025-10-16T06:15:42Z)
• Invariant Graph Transformer for Out-of-Distribution Generalization [21.60139614144787]
  We introduce Graph Out-Of-Distribution generalized Transformer (GOODFormer)<n>It aims to learn generalized graph representations by capturing invariant relationships between predictive graph structures and labels.<n>We design an evolving subgraph positional and structural encoder to effectively and efficiently capture the encoding information of dynamically changing subgraphs.
  arXiv  Detail & Related papers  (2025-08-01T04:11:53Z)
• EquiTabPFN: A Target-Permutation Equivariant Prior Fitted Networks [55.214444066134114]
  We design a fully target-equivariant architecture-ensuring permutation invariance via equivariant encoders, decoders, and a bi-attention mechanism.<n> Empirical evaluation on standard classification benchmarks shows that, on datasets with more classes than those seen during pre-training, our model matches or surpasses existing methods while incurring lower computational overhead.
  arXiv  Detail & Related papers  (2025-02-10T17:11:20Z)
• Leveraging Invariant Principle for Heterophilic Graph Structure Distribution Shifts [42.77503881972965]
  Heterophilic Graph Neural Networks (HGNNs) have shown promising results for semi-supervised learning tasks on graphs.<n>We propose a framework capable of generating invariant node representations through incorporating heterophily information.<n>Our proposed method can achieve guaranteed performance under heterophilic graph structure distribution shifts.
  arXiv  Detail & Related papers  (2024-08-18T14:10:34Z)
• A Pure Transformer Pretraining Framework on Text-attributed Graphs [50.833130854272774]
  We introduce a feature-centric pretraining perspective by treating graph structure as a prior. Our framework, Graph Sequence Pretraining with Transformer (GSPT), samples node contexts through random walks. GSPT can be easily adapted to both node classification and link prediction, demonstrating promising empirical success on various datasets.
  arXiv  Detail & Related papers  (2024-06-19T22:30:08Z)
• Challenging the Myth of Graph Collaborative Filtering: a Reasoned and Reproducibility-driven Analysis [50.972595036856035]
  We present a code that successfully replicates results from six popular and recent graph recommendation models. We compare these graph models with traditional collaborative filtering models that historically performed well in offline evaluations. By investigating the information flow from users' neighborhoods, we aim to identify which models are influenced by intrinsic features in the dataset structure.
  arXiv  Detail & Related papers  (2023-08-01T09:31:44Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  We introduce a new framework named Discrete Graph Auto-Encoder (DGAE) We first use a permutation-equivariant auto-encoder to convert graphs into sets of discrete latent node representations. In the second step, we sort the sets of discrete latent representations and learn their distribution with a specifically designed auto-regressive model.
  arXiv  Detail & Related papers  (2023-06-13T12:40:39Z)
• Evaluating Robustness and Uncertainty of Graph Models Under Structural Distributional Shifts [43.40315460712298]
  In node-level problems of graph learning, distributional shifts can be especially complex. We propose a general approach for inducing diverse distributional shifts based on graph structure. We show that simple models often outperform more sophisticated methods on the considered structural shifts.
  arXiv  Detail & Related papers  (2023-02-27T15:25:21Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  We consider the problem of modelling high-dimensional distributions and generating new examples of data with complex relational feature structure coherent with a graph skeleton. The model we propose tackles the problem of generating the data features constrained by the specific graph structure of each data point by splitting the task into two phases. In the first it models the distribution of features associated with the nodes of the given graph, in the second it complements the edge features conditionally on the node features.
  arXiv  Detail & Related papers  (2022-12-01T11:49:07Z)
• Deformable Graph Transformer [31.254872949603982]
  We propose Deformable Graph Transformer (DGT) that performs sparse attention with dynamically sampled key and value pairs. Experiments demonstrate that our novel graph Transformer consistently outperforms existing Transformer-based models.
  arXiv  Detail & Related papers  (2022-06-29T00:23:25Z)
• Beyond permutation equivariance in graph networks [1.713291434132985]
  We introduce a novel architecture for graph networks which is equivariant to the Euclidean group in $n$-dimensions. Our model is designed to work with graph networks in their most general form, thus including particular variants as special cases.
  arXiv  Detail & Related papers  (2021-03-25T18:36:09Z)
• Permutation Invariant Graph Generation via Score-Based Generative Modeling [114.12935776726606]
  We propose a permutation invariant approach to modeling graphs, using the recent framework of score-based generative modeling. In particular, we design a permutation equivariant, multi-channel graph neural network to model the gradient of the data distribution at the input graph. For graph generation, we find that our learning approach achieves better or comparable results to existing models on benchmark datasets.
  arXiv  Detail & Related papers  (2020-03-02T03:06:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.