Invariant-Based Diagnostics for Graph Benchmarks

Technical Summary: Invariant-Based Diagnostics for Graph Benchmarks

Problem Statement
Progress in developing Graph Foundation Models (GFMs) is currently hindered by benchmarking practices that conflate the contributions of node features and graph structure. This conflation makes it difficult to determine whether a model truly learns from connectivity or merely exploits feature correlations. Furthermore, existing evaluation practices suffer from small dataset sizes, a lack of structural diversity within datasets, and an excessive emphasis on theoretical expressivity (e.g., the ability to distinguish non-isomorphic graphs), which may not align with actual predictive performance on specific tasks. The authors argue that standard Graph Neural Networks (GNNs) are unsuitable for isolating the influence of structure, as they entangle structural and feature-related information during the message-passing process.

Methodology
The authors propose a diagnostic framework based on Graph Invariants: permutation-invariant, task-agnostic structural descriptors that serve as "structural fingerprints" for graphs. These invariants are computable proxies for graph structure that require no trainable parameters.

• Invariant Construction: The study employs a diverse set of invariants, including fundamental graph-theoretic measures (e.g., diameter, cycle rank), entropy-based metrics (e.g., von Neumann entropy), geometric and topological invariants (e.g., analytic torsion, homomorphism counts), and molecular indices (e.g., Wiener index, Balaban index). These are concatenated into a single feature vector per graph.
• Models: The authors utilize two primary model families:
  1. Gradient-Boosted Tree Ensembles (XGBoost): Used as the primary classifier for invariant-based baselines. This choice is made deliberately to ensure computational efficiency and straightforward hyperparameter optimization across 26 diverse datasets.
  2. Graph Neural Networks (GIN): Employed in multi-task learning experiments to analyze gradient alignment and structural heterogeneity.
• Experimental Scenarios: The methodology is applied in four distinct experimental setups:
  1. Expressivity Analysis: Testing the ability of invariants to distinguish non-isomorphic graph pairs in the BREC dataset (graphs indistinguishable by the 1-Weisfeiler-Lehman test).
  2. Dataset Characterization: Treating dataset membership as a "meta-classification" task to quantify structural heterogeneity within and across domains.
  3. Predicting Multi-Task Performance: Investigating the correlation between structural differences (measured by invariant-based meta-classification accuracy) and gradient alignment/downstream performance in multi-task learning setups.
  4. Benchmarking: Evaluating four input configurations—sum-based features, aggregation-based features, full invariants, and a minimally expressive subset of invariants—across 26 datasets to disentangle the roles of features, message passing, expressivity, and global structure.

Main Contributions and Results

1. Expressivity of Invariants:

   • It is demonstrated that invariants are more expressive than standard GNNs in the context of the BREC dataset. A simple combination of invariants (specifically a subset of four) achieves 73% accuracy in distinguishing non-isomorphic pairs, outperforming most GNN-based methods and matching the performance of more complex architectures like N2.
   • The authors show that high expressivity does not require the full set of invariants; a greedy selection reveals that a small subset suffices to capture the same discriminatory power.

2. Characterization of Structural Heterogeneity:

   • Invariants effectively characterize existing benchmark datasets. A meta-classifier using invariants achieves approximately 56% accuracy in distinguishing 23 datasets from different domains and approximately 93% accuracy in distinguishing datasets within the same domain.
   • This indicates a pronounced "dataset shift," where graphs within the same domain still exhibit distinct structural signatures, suggesting that current benchmarks lack the homogeneity required for robust generalization.

3. Predicting Multi-Task Performance:

   • There is a consistent negative correlation between the structural dissimilarity of two datasets (measured by meta-classification accuracy) and their performance in a multi-task learning setup.
   • Higher structural dissimilarity leads to lower gradient alignment and reduced downstream performance, indicating that structural shifts are a primary obstacle to effective pretraining and transfer learning across domains.

4. Competitiveness of Invariant-Based Models:

   • Simple invariant-based models (XGBoost trained on invariant vectors) are competitive with state-of-the-art transformer and message-passing baselines across 26 datasets, and outperform them in some cases.
   • Notably, invariant-based models on "Flow" datasets have surpassed the best reported results with a significant margin.
   • The study shows that expressivity is not the primary driver of predictive performance. A subset of invariants with the same expressivity as the full set often leads to lower predictive performance, suggesting that task-specific relevance of structure is more important than raw discriminatory power.
   • In many cases, adding invariants to feature-based baselines improves performance, but for some tasks (e.g., CIFAR10, represented as pixel grids), invariants yield no gain, indicating that structure plays a marginal role.

Significance and Claims
The work posits that invariant-based baselines should become the standard for evaluating graph benchmarks. The authors argue that these baselines fulfill two critical functions:

1. Diagnostic Tool: They help determine whether a specific task truly requires graph structure. If a simple invariant-based model performs as well as a complex GNN, the task may not rely on structural information.
2. Alignment Check: They provide a "reality check" to detect misalignment between model and task. If a complex model does not substantially outperform an invariant-based baseline model, the deficit likely reflects insufficient fine-tuning or a failure to extract meaningful structure, rather than a fundamental limitation of the architecture.

The authors conclude that the current emphasis on expressivity as a primary design goal requires re-evaluation. Instead, the field should focus on understanding the relevance of structure for specific tasks. Invariant-based diagnostics offer a necessary checkpoint to ensure datasets are suitable for graph learning before pursuing more ambitious goals like Graph Foundation Models. The work does not claim that invariants replace GNNs, but rather that they provide a necessary, minimal baseline to validate whether structure is effectively learned.