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

We sincerely thank the reviewer for recognizing our framework as principled and for acknowledging our contribution in addressing a key gap in the theoretical foundations of Graph Foundation Models (GFMs). We greatly appreciate your thoughtful and encouraging feedback.

Q1: The current framework is restricted to node-level tasks and not extended to edge-level or graph-level tasks, which is explicitly acknowledged as a limitation, restricting its generality.

We fully agree that this is a limitation, and we explicitly acknowledge it in lines 346–347: “Future work could explore extending this recipe to edge-level or graph-level tasks as our recipe is currently limited to the node-level case.”

Our primary aim was to provide a principled approach to constructing GFMs, beginning with the node-level setting, which is foundational yet non-trivial and has been neglected in prior work. We view this paper as an important first step toward more general-purpose graph foundation models. Extending this framework to edge- and graph-level tasks is indeed part of our research vision, and we are actively exploring ways to build similarly principled models for these settings.

We hope the reviewer agrees that establishing a solid theoretical footing for node-based GFMs is a necessary milestone toward achieving broader generalization in graph learning.

Q2: Although the theory supports regression tasks, experiments only validate classification, lacking empirical support for regression scenarios, weakening the framework's comprehensiveness.

Our empirical evaluation is restricted to node classification – not by design, but due to a fundamental limitation in the current ecosystem of graph machine learning benchmarks. Specifically, while our experiments span 27 datasets sourced from major libraries (PyG, DGL, SNAP, OGB), we could not identify any node-level regression benchmark. This reflects a broader issue in the field: the lack of diverse and meaningful evaluation tasks for graph foundation models. As emphasized in [1], the progress of graph learning is increasingly bottlenecked not by model expressivity or compute, but by the lack of representative benchmarks.

We would be glad to conduct any further experiments that you believe could strengthen the paper and warrant a higher score.

L1: The feature-label mixing relies on least-squares projections, but its performance in scenarios with weak feature-label correlation (e.g., noisy features) is not discussed, potentially leading to generalization bottlenecks.

While we agree that weak feature-label correlation can present challenges, such scenarios are generally less problematic in node classification tasks compared to domains like spatio-temporal prediction (e.g., weather or traffic forecasting), where noisy or weakly informative features are more common.

It is also worth noting that when faced with noisy features, the mean aggregation step performed before the least-squares (LS) projection and the GNN’s aggregation helps mitigate noise and stabilise the signal in our framework. That said, we find your observation an exciting direction for future research. In particular, extending our framework to spatio-temporal graphs could pave the way toward a general-purpose spatio-temporal Graph Foundation Model (ST-GFM). We will include a discussion of this denoising effect in the revised manuscript for clarity.

We hope our responses address your concerns. We will include all the suggestions you've provided and experimental results in the camera-ready version with the appropriate discussion.

We thank the reviewer for their thorough review, for recognizing our theoretical contributions and rigour and for describing the paper as an “enjoyable read.”

W1: Insufficient Main Experiments: ... they only test when pretraining on one dataset (being Cora)... train 4 different versions of their model each on a different dataset...

Q1: Can you report the performance in the same manner to GraphAny ...

Thanks for this comment. As per your suggestion, we explore how sensitive our method is when a single dataset is used in training. In addition to Cora, we train TS-Mean on roman-empire, chameleon, and wiki-cs. All models are evaluated zero-shot on the same 27 test graphs. Due to space constraints, we report only the averages; full per-dataset results will be included in the camera-ready version.

These results further validate that TS-Mean and GraphAny are consistently competitive in the low-data regime.

This finding aligns with our last set of additional experiments, in which we vary the training set size, reinforcing that both methods are competitive in the low-data regime. However, the true advantage of TS-GNNs emerges in the foundation model setting, where multiple training graphs are introduced, instead of one. ​​We refer the reviewer to our response to W3/Q3, where we present further experiments demonstrating that TS-GNNs consistently outperform GraphAny in this more realistic high-data regime.

W2: Lack of Ablation Studies: ... (a) How important are the use of DSS? What if you replace them with a basic DeepSet? (b) Are each type of symmetry necessary, what if you remove one?

These are excellent points. Let us clarify: (a) The DSS architecture plays a fundamental role in generalizing to arbitrary features. Replacing DSS with a standard DeepSet would remove the feature equivariance, yielding a model that depends on the number of features and their order. This results in having a different model for each graph, preventing it from generalizing across different feature spaces -- a key limitation of current GNNs that our work seeks to address. (b) Removing any one of the symmetry constraints would disable generalization across arbitrary graphs. This is the core novelty of our work: we derive the linear layer that corresponds to the complete set of symmetries required for a GFM. Removing any symmetry would reduce the model to a task- or graph-specific learner rather than a foundation model.

That said, in response to your request for additional ablations, we have extended Table 1 in the main paper to include three additional GNN-based baselines: TS-SGC, TS-GCN and TS-GCNII. The updated table below reports the average accuracy across all 27 test graphs. Due to space constraints, we report only the averages; full per-dataset results will be included in the camera-ready version.

The results reveal an interesting trend: as the GNN architecture becomes more complex—from SGC to GCN to GCNII, performance degrades in the zero-shot with low training data setting. This supports a hypothesis that complex GNN architectures, while beneficial in fully supervised settings, may overfit to training distributions and generalize poorly in transfer scenarios when trained on a single graph.

(c) How important is the feature-label mixing?...

Q2: Can you run some ablation ... ablate some of the the feature-label mixing.

As suggested, we conduct an ablation study to isolate the effect of two key components in our TS-GNN architecture: (a) the feature-label mixing step via least squares (LS), and (b) the inclusion of a bias term. We first evaluate a non-parametric setup across our test set of 27 datasets. We compare the performance of LS alone, LS with a bias term, and LS with both a bias term and a subsequent local mean aggregation step (similar to MEAN-GNN), exhibiting similar performance.

We then assess the impact of these components on TS-Mean and TS-GAT, trained on Cora and evaluated on the 27 datasets. We assess three configurations: without LS and bias (plain), with LS only, and with both LS and bias.

These results show that the plain versions of TS-Mean and TS-GAT lag behind the LS. This outcome is expected as noted in lines 265–270: "...while such operations are theoretically sufficient for our universal approximation result (Section 4.2), they often suffer from practical limitations, because all feature or label information is compressed into a single global vector representation, creating a representational bottleneck.". Despite this limitation, the plain TS-GNN variants still perform substantially better than random guessing, indicating that it captures transferable structure even without the LS step or bias term.

Next, the inclusion of the LS step alone offers a performance boost, suggesting that LS and TS-GNNs capture complementary patterns. The combination of the two yields greater generalization than either alone. This analysis parallels GraphAny's, where entropy normalization and distance features improve over plain GraphAny.

We would like to emphasize that the central contribution of our work is theoretical and not in its performance: we provide a principled, symmetry-based recipe for constructing GFMs from GNNs.

W3: Lack of Clear Benefit over GraphAny: ... why should we use TSNet? ... it's really hard to argue without any tangible experimental results ...

Q3: ... What scenarios does TSNet outperform GraphAny? ...

This is an excellent point. Due to time constraints, we were unable to include experiments demonstrating that the benefits of TS-GNNs over GraphAny are evident in the high-data regime, where the model is trained on multiple graphs. That is because GraphAny can only mix a set of fixed patterns (the least squares solutions), whereas TS-GNNs can learn complex patterns that improve as more training graphs are introduced. Moreover, training on a single graph is not only limiting but also unrealistic for a foundation model setting.

We now train TS-Mean and GraphAny on increasingly larger subsets of a held-out training pool. We reserve 9 representative graphs for training and construct training subsets of sizes 1, 3, 5, 7, and 9, where each larger subset includes all datasets from the smaller trainsets. The remaining 19 datasets (plus the newly added wisconson dataset) are used for zero-shot evaluation. For each subset size, we report mean zero-shot accuracy, averaged over five random seeds.

Results show that the zero-shot accuracy of TS-Mean improves as more training graphs are introduced. This behavior aligns with the expected characteristics of a GFM – the ability to benefit from increased data diversity. In contrast, GraphAny’s performance remains unchanged as more training graphs are added. These results suggest that GraphAny is not well-suited for the foundation model setting, and may instead be better tailored to scenarios with limited training data.

Interestingly, both models perform similarly when trained on 1–3 graphs, indicating that TS-Mean is already competitive in the low-data regime. However, once the training set grows, TS-Mean consistently outperforms GraphAny, exhibiting the desired scailing law behavior, highlighting its superior scalability and generalization capability.

W4: Lack of Discussion on Model Complexity: ... some discussion on this .. would be appreciated...

Thank you for raising this important aspect. Given a graph, we first perform (a non-learnable, standard) local aggregation over each node’s neighborhood and then solve a least-squares (LS) problem as a one-time preprocessing step. The resulting features, along with the original inputs, are passed into the TS-GNN, which performs standard message-passing (MP) during the forward pass.

For a graph with $N$ nodes, $F$ features and $E$ edges, the local aggregation and message-passing steps each have time complexity $\mathcal{O}(EF)$, while the LS solution has complexity $\mathcal{O}(NF^2+F^3)$. Importantly, the LS computation is performed once per graph and does not scale with the number of layers or training epochs.

The only other zero-shot baseline, GraphAny, also uses a similar preprocessing pipeline involving multiple local aggregations and LS solutions for different neighborhood radii. It then applies a transformer over the resulting representations. Despite these differences, its overall computational cost is also on the order of $\mathcal{O}(E)$, comparable to our method and consistent with the standard complexity of message-passing neural networks.

We will include in the final version a comprehensive theoretical analysis of the runtime, comparing our method with GraphAny and classical GNNs.

W5: This is a small detail, but I'd recommend changing the title to ... "Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models for Node-Level Task"...

We appreciate your thorough review and will therefore change the title as per your suggestion for the camera-ready version.

We will include all the suggestions you've provided and experimental results in the camera-ready version with the appropriate discussion.

We hope our responses address your concerns and would greatly appreciate your reconsideration of the evaluation and increasing your score.

We sincerely thank the Reviewer for finding our paper “easy to follow” and the theoretical claims “well-supported by proofs.” We value your constructive and supportive comments. We provide below the answers to the main concerns raised:

W1: However, graph datasets for social media should be added to demonstrate the strength of TSNet.

Q2: The experiments currently lack graph datasets for social media...

We understand the reviewer's interest in evaluating our method on social media datasets, as this is a common and important application area for node-level prediction tasks.

Unfortunately, large-scale social media graphs such as Reddit or Instagram pose a significant computational challenge. Specifically, for a graph with $N$ nodes, $E$ edges, and $F$ features, our model produces intermediate node representations of size $N\times F\times K$, where $K$ is the number of channels—typically greater than 8, and the message-passing operation retains tensors of size $E\times F\times K$. For graphs of the scale seen in social media datasets, these tensor sizes exceed the memory capacity of non-industrial GPUs.

While we are unable to provide results on these datasets in this version due to resource limitations, this highlights an important direction for future research. Some potential strategies to improve scalability include tensor sparsification, subgraph sampling, and low-rank approximations.

That said, we remain committed to further validating our framework. As demonstrated throughout the rebuttal, we have added new baselines, conducted detailed ablations, and explored training on a broader range of datasets. We would be happy to carry out any additional experiments within our resource limits that the reviewer believes would strengthen the work or warrant a higher score.

We list the rest of the experiments performed in this rebuttal below, for the reviewer's convenience and interest:

(1) Evaluating TS-GNNs and GraphAny in the high-data regime by varying the number of training graphs (see Q1 below)

(2) Introducing three new TS-GNNs variants

We extended Table 1 in the main paper to include three more GNN variants: TS-SGC, TS-GCN, and TS-GCNII. Below is the average accuracy over 27 datasets:

The results reveal an interesting trend: as the GNN architecture becomes more complex -- from SGC to GCN to GCNII, performance degrades. This supports a hypothesis that complex GNN architectures, while beneficial in fully supervised settings, may overfit to training distributions and generalize poorly in transfer scenarios when trained on a single graph.

(3) Ablation over the least-Squares mixing and bias term

We isolate the effect of two key components in our TS-GNN architecture: (a) the feature-label mixing step via least squares (LS), and (b) the inclusion of a bias term. We first evaluate a non-parametric setup across our test set of 27 datasets. We compare the performance of LS alone, LS with a bias term, and LS with both a bias term and a subsequent local mean aggregation step (similar to MEAN-GNN), exhibiting similar performance.

We then assess the impact of these components on TS-Mean and TS-GAT, trained on Cora and evaluated on the 27 datasets. We assess three configurations: without LS and bias (plain), with LS only, and with both LS and bias.

These results show that the plain versions of TS-Mean and TS-GAT slightly lag behind the LS. This outcome is expected as the global pooling in plain TS-GNNs creates an information bottleneck that prevents feature-label mixing, as noted in lines 265–270. Despite this limitation, the plain TS-GNN variants still perform substantially better than random guessing, indicating that it captures transferable structure even without the LS step or bias term.

Next, the inclusion of the LS step alone offers a performance boost, suggesting that LS and TS-GNNs capture complementary patterns. The combination of the two yields greater generalization than either alone. This analysis parallels GraphAny's, where entropy normalization and distance features improve over plain GraphAny.

(4) Ablation over the pretraining dataset

We explore how sensitive our method is when a single dataset is used in training. In addition to Cora, we train TS-Mean on roman-empire, chameleon, and wiki-cs. All models are evaluated zero-shot on the same 27 test graphs.

These results further validate that TS-Mean and GraphAny are consistently competitive in the low-data regime.

This finding aligns with our experiments that vary the training set size, reinforcing that both methods are competitive in the low-data regime. However, the true advantage of TS-GNNs emerges in the foundation model setting—i.e., the high-data regime.

Q1: The average performance reported in Table 1 is comparable to the baseline method, GraphAny.

This is an excellent point. Due to time constraints, we were unable to include experiments demonstrating that the benefits of TS-GNNs over GraphAny are evident in the high-data regime, where the model is trained on multiple graphs. That is because GraphAny can only mix a set of fixed patterns (the least squares solutions), whereas TS-GNNs can learn complex patterns that improve as more training graphs are introduced. Moreover, training on a single graph is not only limiting but also unrealistic for a foundation model setting.

We now train TS-Mean and GraphAny on increasingly larger subsets of a held-out training pool. We reserve 9 representative graphs for training and construct training subsets of sizes 1, 3, 5, 7, and 9, where each larger subset includes all datasets from the smaller trainsets. The remaining 19 datasets (plus the newly added wisconson dataset) are used for zero-shot evaluation. For each subset size, we report mean zero-shot accuracy, averaged over five random seeds.

Results show that the zero-shot accuracy of TS-Mean improves as more training graphs are introduced. This behavior aligns with the expected characteristics of a GFM – the ability to benefit from increased data diversity. In contrast, GraphAny’s performance remains unchanged as more training graphs are added. These results suggest that GraphAny is not well-suited for the foundation model setting, and may instead be better tailored to scenarios with limited training data.

Interestingly, both models perform similarly when trained on 1–3 graphs, indicating that TS-Mean is already competitive in the low-data regime. However, once the training set grows, TS-Mean consistently outperforms GraphAny, exhibiting the desired scailing law behavior, highlighting its superior scalability and generalization capability.

Q3: The pseudo-code for the proposed method would greatly enhance clarity and understanding.

Thanks for this comment. We will include a detailed pseudo-code for TS-GNNs in the camera-ready version.

Q4: Please further discuss how this model could be applied to GFM when language serves as node or edge features.

Our model is designed to accommodate a wide variety of node features, including those derived from text. In fact, several of the datasets used in our experiments already incorporate textual embeddings. For example, in the citation networks Cora, Pubmed, and Citeseer, node features are constructed by applying a TF-IDF embedding to the titles and abstracts of papers. Similarly, in the OGB dataset arxiv, the textual content is embedded using a skip-gram language model. In the photo and computers datasets, nodes represent products, and the features are bag-of-words representations of product reviews, demonstrating our model’s ability to handle diverse textual node-features.

As for textual edge features, while our current formulation focuses on node features, the architecture can be extended to accommodate edge features by introducing permutation symmetry over the edge-feature space, analogous to how we treat node features. Although edge features are less common in node prediction tasks and more relevant for graph-level or edge-level tasks (e.g., in molecular property prediction), we agree that this is a valuable extension. Formalizing linear layers that are permutation-invariant over edge features is non-trivial and presents an interesting direction for future research. We appreciate the suggestion and plan to explore this as part of extending our framework toward more general-purpose GFMs.

We hope our responses address your concerns. We will include all the suggestions you've provided and experimental results in the camera-ready version with the appropriate discussion.

Thank you for the rebuttal, which addresses my concerns to some extent. The authors outline TSNet’s advantages over Graphany and explain current scalability limitations and edge-feature extensions. Given that I already provided a positive score, I will maintain it.

We thank the reviewer for their thoughtful feedback and for recognizing the novelty, ingenuity, and theoretical contributions of our approach.

W1: While the experiments are extensive... they are exclusively focused on node classification tasks...

We agree with this concern. Our evaluation is restricted to node classification – not by design, but due to the absence of public node-level regression benchmarks. We surveyed 27 datasets from PyG, DGL, SNAP, and OGB and found no such benchmarks, reflecting a broader issue in the field. As shown in [1], progress of graph learning is bottlenecked by the lack of representative benchmarks. Still, the purpose of our paper is to lay the groundwork for future GFMs that may perform node-level regression, with the hope that better benchmarks will be available in the future.

W2: The computational complexity of the algorithm is not thoroughly explained...

Thank you for raising this important aspect. Given a graph, we first perform (a non-learnable, standard) local aggregation over each node’s neighborhood and then solve a least-squares (LS) problem as a one-time preprocessing step. The resulting features, along with the original inputs, are passed into the TS-GNN, which performs standard message-passing (MP) during the forward pass.

For a graph with $N$ nodes, $E$ edges, and $F$-dimensional node features, the local aggregation and MP steps each have time complexity $\mathcal{O}(EF)$, while the LS solution has complexity $\mathcal{O}(NF^2+F^3)$. Importantly, the LS computation is performed once per graph and does not scale with the number of layers or training epochs.

GraphAny, the only other zero-shot baseline, also applies local aggregation and LS with varying neighborhood radii, followed by a transformer. Its complexity is also $\mathcal{O}(EF)$, comparable to our method.

We will include in the final version a comprehensive theoretical analysis of the runtime, comparing our method with GraphAny and classical GNNs.

W3: The experimental study is limited and only compared with very few baselines

Unfortunately, GraphAny is the only existing method that matches this setting. Due to the lack of baselines, we also compare with standard end-to-end GNNs, although they are not designed for zero-shot generalization and thus do not constitute a fair comparison.

That said, in response to your suggestion, we extended Table 1 to include three more GNN variants: TS-SGC, TS-GCN, and TS-GCNII. Below is the average accuracy over 27 datasets:

The results reveal that as GNNs become more complex -- from SGC to GCN to GCNII, performance degrades. This supports a hypothesis that complex GNNs, while beneficial when training and testing on the same graph, may overfit to training distributions and generalize poorly in transfer scenarios.

Moreover, the gains seem relatively small, which is hard to tell the exact benefits

This is an excellent point. Due to time constraints, we were unable to include experiments demonstrating that the benefits of TS-GNNs over GraphAny are evident in the high-data regime, where the model is trained on multiple graphs. That is because GraphAny can only mix a set of fixed patterns (the least squares solutions), whereas TS-GNNs can learn complex patterns that improve as more training graphs are introduced. Moreover, training on a single graph is not only limiting but also unrealistic for a foundation model setting.

We added a new experiment where TS-Mean and GraphAny are trained on increasingly larger subsets (1, 3, 5, 7, 9) of 9 held-out training graphs, with each subset nested within the next. Zero-shot evaluation is performed on the remaining 19 datasets plus the newly added wisconsin dataset.

Results show that TS-Mean’s accuracy increases with more training graphs, exhibiting the desired scaling law behavior. This behavior aligns with the expected characteristics of a GFM – the ability to benefit from increased data diversity. In contrast, GraphAny’s performance remains unchanged. This suggests that GraphAny is not a well-suited candidate for a foundation model, and may instead be better tailored only to scenarios with limited training data.

More ablation studies and sensitivity analysis could benefit the paper

We agree and have provided sensitivity analyses of two types:

(1) Least-Squares mixing and bias term

We isolate the effect of (a) the least squares (LS) feature-label mixing, and (b) the inclusion of a bias term. We first evaluate a non-parametric setup across our test set of 27 datasets. We compare the accuracy of LS alone, LS with a bias term, and LS with both a bias term and a subsequent local mean aggregation step (similar to MEAN-GNN), exhibiting similar performance.

We then assess the impact of these components on TS-Mean and TS-GAT, trained on Cora and evaluated on the 27 datasets. We assess three configurations: without LS and bias (plain), with LS only, and with both LS+bias.

These results show that the plain versions of TS-Mean and TS-GAT slightly lag behind the LS. This is expected, as the global pooling in plain TS-GNNs creates an information bottleneck that prevents feature-label mixing, as noted in lines 265–270. Despite this limitation, the plain TS-GNN variants still perform substantially better than random guessing, indicating that it captures transferable structure even without the LS step or bias term.

Next, the inclusion of the LS step alone offers a performance boost, suggesting that LS and TS-GNNs capture complementary patterns. The combination of the two yields greater generalization than either alone. This analysis parallels GraphAny's, where entropy normalization and distance features improve over plain GraphAny.

(2) Sensitivity to pretraining dataset

We explore how sensitive our method is when a single dataset is used in training. In addition to Cora, we train TS-Mean on roman-empire, chameleon, and wiki-cs. All models are evaluated zero-shot on the same 27 test graphs.

These results further validate that TS-Mean and GraphAny are consistently competitive in the low-data regime, aligning with our earlier results over varying training set size. However, as explained above, the true advantage of TS-GNNs emerges in the foundation model setting – the high-data regime.

Q1: Could the authors discuss potential future work on extending this recipe to more complex graph structures, such as heterogeneous graphs...

One route for extending TS-GNNs to heterogeneous is to incorporate the permutation symmetry $S_R$ over the set of relation types $R$. We derive theoretical guarantees over sets and transform the resulting global pooling to a local graph pooling, similar to the expressivity analysis of GIN. For heterogeneous graphs, we can adopt a strategy analogous to that of relational GCNs, treating each relation type as a distinct graph, where we enforce our existing symmetry $S_N\times S_F\times S_C$ for each graph. To handle relations in a principled way, we stack the relation-specific representations such that it is $S_R$-equivariant. This results in an intermediate tensor of size $N\times F\times R\times K$, which is independent of the graph-specific relation types. A similar approach can also handle multiple node types.

Another direction is to combine our principled approach with meta-graph-based foundation models such as ULTRA [2]. These models are not derived from Schur's Lemma and a universal approximation analysis, but may complement our method in practice.

Q2: What about the scalability of the proposed method?...compare this with large pre-trained language models or vision models...

First, we clarify that our method is not limited to small-scale graphs. In our experiments, we include large-scale datasets such as arxiv, which contains >150K nodes and >1M edges, demonstrating that our method scales to large graphs.

As noted in the paper, our approach is task-agnostic and applies to any node-level task, including node regression, node classification, and node ranking. We focus on classification due to dataset availability (see W1).

Regarding large pre-trained models in NLP/vision: our work shares the same philosophy—learning transferable representations across tasks and domains. Just as BERT/ViT is able to generalize across language/image data, TS-GNNs aim to learn generalized node-level representations across graphs. While the scale of pretraining in graph learning is in an early stage compared to NLP/vision, our results already show scaling behavior – performance improves with more training graphs (see W3). Due to the current limitations in large-scale node-based graph datasets [1], we are not yet able to assess our model’s behavior on large graph collections.

The paper does not include explicit limitation sections

We will include a dedicated limitations section.

[1] Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks, ICML25

[2] Towards Foundation Models for Knowledge Graph Reasoning, ICLR24

We will include all the experimental results and suggestions provided by the Reviewer in the final version with the appropriate discussion.

We hope our responses address your concerns and would greatly appreciate your reconsideration of the evaluation and increasing your score.