Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models

Ben Finkelshtein, İsmail İlkan Ceylan, Michael Bronstein, Ron Levie

TL;DR

This paper introduces a theoretically grounded framework for designing Graph Foundation Models (GFMs) capable of generalizing zero-shot across completely unseen graphs, feature dimensions, and label sets. By enforcing a "triple-symmetry" criterion—node and label permutation-equivariance alongside feature permutation-invariance—the authors create Triple-Symmetry GNNs (TS-GNNs) that act as universal approximators for cross-domain graph tasks. Crucially, the model demonstrates true foundation model behavior: its zero-shot performance consistently improves as it is trained on more diverse graph datasets.

What Problem Does This Paper Address?

In fields like Natural Language Processing (NLP) and Computer Vision (CV), foundation models excel because they operate on a universal vocabulary (tokens or pixels). Graph Machine Learning (GML), however, faces a fundamental obstacle: the lack of a shared feature space. A graph representing a social network might use text embeddings as node features, while a molecular graph uses atomic properties. Furthermore, the number of target classes or regression targets varies wildly between datasets.

Traditional Graph Neural Networks (GNNs) are rigidly tied to fixed feature dimensions and specific label sets, making them unable to transfer to new domains without complete retraining. The authors tackle a grand challenge in GML: How can we systematically design a graph foundation model from first principles that generalizes across arbitrary graph structures, feature spaces, and label domains?

Methods

The authors solve the cross-domain dilemma by identifying three essential symmetries that a graph foundation model must respect, termed the triple-symmetry criterion:

  1. Node Permutation-Equivariance ($S_N$): Permuting the input nodes must result in a matching permutation of the outputs (a standard requirement for graph isomorphism).
  2. Label Permutation-Equivariance ($S_C$): Changing the ordering of the target classes or multi-regression targets must consistently permute the predictions, ensuring semantic consistency.
  3. Feature Permutation-Invariance ($S_F$): The model's predictions must not rely on the arbitrary ordering or dimensionality of input features, allowing it to ingest features from entirely different domains.
The triple-symmetry network architecture and its required permutation behaviors.

The TS-GNN Recipe

The authors first mathematically characterize the space of all linear transformations that satisfy these three symmetries, creating a core block called TSNet, which they prove is a universal function approximator for triple-symmetric multisets.

To make this practical for graphs, they introduce Triple-Symmetry GNNs (TS-GNNs). This modular framework allows researchers to take any standard message-passing GNN aggregation function (such as GraphSAGE or GAT) and upgrade it into a GFM. Messages are passed not just between nodes, but also across feature and label channels via sum aggregation.

Rich Feature-Label Mixing

To prevent the model from hitting a representational bottleneck (which happens if you simply pool features and labels into single vectors), the authors introduce a feature-label mixing mechanism based on closed-form least-squares solutions. They dynamically solve linear projections ($T_F$ and $T_C$) at each layer to map features into the label space and vice versa. This process is entirely linear and preserves the triple-symmetry property while adapting dynamically to varying feature scales.

Illustration of feature and label embeddings across the layers of a TS-GNN.

Datasets

The framework was rigorously evaluated using an ensemble of 29 real-world node classification datasets spanning diverse domains, graph sizes, and feature types. These included classic benchmarks like Cora, Citeseer, and Pubmed, as well as heterophilous and large-scale datasets such as roman-empire, amazon-ratings, minesweeper, tolokers, co-cs, co-physics, and arxiv.

Key Insights and Ideas

  • Symmetry as a Substitute for Vocabulary: Instead of trying to project diverse features into a shared embedding space (which often fails across radically different domains), enforcing strict feature invariance allows the model to learn structural and relational invariants that transfer perfectly.
  • Fixing the Literature: The authors identify and correct a subtle but critical mathematical flaw in prior landmark equivariance literature (specifically, Theorem 3 in Maron et al., 2020 regarding $H$-equivariant networks), providing a corrected proof path specifically for the full feature permutation group ($H = S_F$).
  • Emergent Scaling Laws: A true foundation model should get better with more data. The authors discover that while prior methods like GraphAny plateau or degrade when given more training graphs, TS-GNNs exhibit clear scaling behavior—performance on unseen test graphs steadily climbs as the diversity of the pretraining pool increases.

Key Results

  • Zero-Shot Superiority: When trained on just a single dataset (Cora) and evaluated zero-shot on the remaining 28 datasets, TS-GNN variants (TS-Mean and TS-GAT) consistently outperformed their standard end-to-end counterparts and beat the prior state-of-the-art graph foundation model, GraphAny.
  • Data Scaling Performance: In multi-graph pretraining experiments, TS-Mean showed a steady upward trajectory in zero-shot accuracy as the training set size grew from 1 to 9 graphs, establishing it as a highly viable candidate for large-scale graph foundation modeling.

Limitations and Future Work

  • Task Scope: The current recipe is strictly limited to node-level classification and regression tasks. The authors note that extending this framework to edge-level (e.g., link prediction) and graph-level tasks is a crucial direction for future work.
  • Memory Complexity: Because TS-GNNs maintain intermediate node representations of size $N \times F \times K$ (where $K$ is the channel dimension), they suffer a $K$-fold increase in memory usage compared to standard MPNNs. This could create computational bottlenecks for massive graphs or exceptionally high-dimensional feature spaces.
  • Benchmark Gaps: The empirical evaluation was restricted to classification due to a total lack of standardized, diverse node-level regression benchmarks in the current graph machine learning ecosystem.

Summary updated

Abstract

Graph machine learning architectures are typically tailored to specific tasks on specific datasets, which hinders their broader applicability. This has led to a new quest in graph machine learning: how to build graph foundation models capable of generalizing across arbitrary graphs and features? In this work, we present a recipe for designing graph foundation models for node-level tasks from first principles. The key ingredient underpinning our study is a systematic investigation of the symmetries that a graph foundation model must respect. In a nutshell, we argue that label permutation-equivariance alongside feature permutation-invariance are necessary in addition to the common node permutation-equivariance on each local neighborhood of the graph. To this end, we first characterize the space of linear transformations that are equivariant to permutations of nodes and labels, and invariant to permutations of features. We then prove that the resulting network is a universal approximator on multisets that respect the aforementioned symmetries. Our recipe uses such layers on the multiset of features induced by the local neighborhood of the graph to obtain a class of graph foundation models for node property prediction. We validate our approach through extensive experiments on 29 real-world node classification datasets, demonstrating both strong zero-shot empirical performance and consistent improvement as the number of training graphs increases.
BibTeX
@inproceedings{finkelshtein2025equivariance,
  author = {Ben Finkelshtein and İsmail İlkan Ceylan and Michael Bronstein and Ron Levie},
  title = {{Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=d6wOZrzaWd},
}
Figure