Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models
Authors: Ben Finkelshtein
Ismail Ilkan Ceylan
Michael M. Bronstein
Ron Levie
Venue: NeurIPS 2025 poster ()
Keywords: universal approximation
equivariance and invariance
graph foundation models
message passing
Primary area: deep_learning
TL;DR: We present a principled recipe for building graph foundation models that generalize across arbitrary graphs, features, and label spaces.

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: \emph{how to build graph foundation models (GFMs)} capable of generalizing across arbitrary graphs and features? In this work, we present a recipe for designing GFMs 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.

Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models
Ben Finkelshtein University of Oxford
ismail Îlkaa Ceylan
TU Wien / AITHYRA/ University of Oxford
Michael Bronstein University of Oxford AITHYRA
Ron Levie
Technion Israel Institute Technology
Abstract
Graph machine learning architectures are typically tailored to specific tasks on specific datasets, which hinders their broader applicability. This has led to new quest in graph machine learning: how to build graph foundation models (GFMs) capable of generalizing across arbitrary graphs and features? In this work, we present a recipe for designing GFMs for node-level tasks from first principles. The key ingredient underpinning our study is systematic investigation of the symme- tries that graph foundation model must respect. In nutshell, we argue that label permatationn-qquivviiann alongside feature permutation invariance are necessary in addition to the common node comutatton-equivaratee hood of the graph. To this end, we first characterize the space of linear transfor- mations that are equivariant to permutations of nodes and labels, and invariant to permutations of features. We then prove that the resulting network 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.
immutation-iivariance
on each local neighbor-
Introduction
Foundation models have shown remarkable success in diverse domains such as natural language
33
28
computer vision (8, 31 43 1. and audio processing (6 7 32). This success has
sparked interest building foundation models for graph machine learning (graph foundation models
(GFMs)) (24 52 2). raising a fundamental question: what are the key requirements for graph machine learning architecture to generalize across tasks, graph structures, and feature and label sets?
Significant progress has recently been made on link-level tasks in knowledge graphs 13] 21 12
[8), which typically do not involve node features. This success is partially due to the nature of knowledge graphs, where learning focuses on structured relational patterns rather than raw feature inputs. Unlike in knowledge graphs, natural language processing or computer vision, node-level tasks in general graphs face fundamental obstacle: the absence of a shared feature "vocabulary": Features may encode textual embeddings in dataset, molecular properties in another, social attributes in yet another. This semantic diversity makes it inherently difficult to define a unified feature space, posing major challenge to building graph foundation models that generalize across domains.
Classical graph neural networks (GNNs) 5 20
rely on fixed feature ordering and predefined feature sets, making them ill-equipped to generalize across arbitrary graphs with varying features.
47
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Sr
Sc
Sc
Sy
SN
Triplessymmetry network
Y
[p) X (ox.o0))
(aN, ac)
Figure I: The input to a triple-symmetry network a feature matrix X and (possibly masked) label matrix Y. The encoder must be equivariant element-wiss permutations ON E SN (affecting the rows of both X and Y), equivariant to class label permutations oc E Sc (affecting the columns of Y), and invariant to feature permutations o Sp (affecting the columns of X).
To date, the only architecture shown to generalize zero-shot across graphs with rich node features is that of Zhao al. [52), which represents promising step forward. However, their model offers specific empirical solution and does not address the deeper question: how can one systematically design generalizable node-level graph foundation models?
Contributions. In this paper, we directly address this challenge by introducing a theoretically- grounded recipe for designing GFMs for node-level classification and regression tasks. On the theoretical front, our starting point is identifying three symmetries that a GFM must respect:
1. Node cnmnuntaioo-qquivarrae is ensure that the predictions are invariant under isomorphisms. This is satisfied by design in peessage-psssigg GNNs through permutation-invarian permutation of input nodes would result in consistent permutation the node-level outputs.
(Sx in Figure 7.. The standard requirement in graph learning
local aggregation, which guarantees that
2. Label permutation-equiiariian regression), outputs should also respect permutations of class labels or multi-regression targets. Permuting the ground-truth should yield consistent permutation in the predictions, ensuring semantic consistency irrespective of the chosen ordering.
(Sc in Figure ! In node-level tasks (classification or
3. Feature permutution-inaarinnc (SF in Figure Z). Graph node features often represent different quantities from different domains and can vary substantially across different graphs, which poses challenges in identifying a shared feature vocabulary. Hence, GFM should not rely on feature ordering or dimensionality. This invariance ensures robust predictions irrespective of how the features arranged across different datasets and tasks.
Having established this symmery criterion, we then characterize the space of linear transfor- mations that are equivariant to permutations of nodes and labels, and invariant to permutations of features. We prove that the resulting triple-symmetry network (TSNet) (see Figure I is a universal approximator of functions that take multisets as inputs and respect the aforementioned symmetries. This is our key theoretical contribution, as allows us to apply TSNets on the neighborhoods the input graph to define symmetry preserving message passing scheme.
The resulting TSNet scheme can be interpreted as a message passing network in which messages are not only sent between nodes but also across feature and label channels via sum aggregation. We then extend this, introduce a more general GFM recipe: use any GNN aggregation pass messages between nodes, feature channels, and labels. Each such GNN yields a GFM which transfer across graphs of arbitrary sizes and with any number of feature and label channels, for both node classification and regression. The resulting GFM is trained on a given set of graphs with their node features and labels, and then transferred to new graphs with different types of features and labels, unseen during training. To summarize, we make the following contributions:
Universality results. We characterize the space of linear maps equivariant to permutations of nodes, features, and labels, and prove that the resulting multilayer architecture is universal approximator of functions that take multiset as inputs and respect nodes, features and label symmetries (Section 4
A general recipe for GFMs. We introduce triple-symmetry graph neural networks (TS-GNNs). a modular and practical method to transform any GNN aggregation into a GFM. This allows the GNN to operate on arbitrary graphs, feature, and label sets (Section

---

Empirical validation. We evaluate our framework on 29 real-world node classification datasets, showing consistent performance improvements over the corresponding standard GNN backbone that TS-GNN uses (e.g., GraphSAGE, GAT 14 42
We also establish TS-GNN as the first graph foundation model to show improved zero-shot accuracy with increasing training data (Section 6.2)
2 Background: Graphs, Groups, and Equivariance
Graphs and Vectors. Vectors, matrices and tensors are denoted in bold, and for any tensor Q, we denote its i-th row by Qia.. its j-th column by Q...: and its z-th slice by Q..... The vector of ones and the all-ones N x M matrix are denoted by 1 and 1 N,,M, respectively. Throughout the paper, N denotes the number of elements in a set or the number nodes in a graph; F denotes the number of input features per element; and C' denotes the number of output classes or regression targets. We focus on node-level tasks and consider an undirected, unweighted graph G = (V, E X, Y), where X E RNXF is a matrix of node features and Y E R xC is matrix encoding labels over C' classes (for classification) or C targets (for regression). We represent the topology of the graph (V, E) using an adjacency matrix A E 1J,
Groups, permutations and arrays. Let Sy be the group of permutations (i.e. the symmetric group) over the [AV] = 21. We define the action of SN SF Sc on RXXNx(F+C)) by
X 77
j (F),
((oN,or,Oc) x),s
[ Lo 10 otherwise
for all (o oc, ON) E SF x Sc x SN and X RRXXN((FC), That is, OF permutes the first F columns (features), oe permutes the last C' columns (labels), and on permutes the rows.
Equivariance and Invariance. We focus on functions that are equivariant or invariant under joint
node-, feature- and -ereutpermusatioons. Namely, function f RR - KRxx2xx is if f ((o..ap.od)
(SN Sp xS (-)))--quivariue
X)= = (aN, oF, f(X) for all op. E
Sy x SF x Se and for all X E RKIXNx(F+O) RKxxNXX is (SN -c)-equivariant and Sp-invariant if (( X)= = (aN, ((X)
Similarly, a function ʃ xXINN((F+C)
for all (aN,ar, Oc) SN x Sy x Sc and for all X E X &RKxXNX(P+O)
Graph neural networks (GNNs). Our framework provides a recipe for converting some GNNs into GFMs. In particular, we focus on message-passingg neural networks (MPNNs), subclass of GNNs that update the initial representations X, Rk( xN of each node for S f I. iterations based on its own state and the state of its neighbors No as
X ((++))= =o W X!!
{W x u Jue.N.))
where {-} denotes a multiset, a is nonlinearity, ( w(( E R p are weight matrices, K(O) is the dimensionality of node embeddings at layer e, M(RKXN)) denote the space of multiset of elements in K and si R x M(R R K is an aggregation function that is invariant to permutations of the elements in its multiset argument.
3 Related Work
Graph foundation models for node classification. Traditional graph neural networks (GNNs) assume fixed feature ordering and predefined feature sets. This mode of operation severely restricts their ability generalize across graphs with unknown or dynamically varying feature distributions. Unlike domains such as natural language processing, where pre-defined embeddings allow for shared vocabulary, this approach is unsuitable when dealing with entirely unknown dy- namic graph attributes. GraphAny [52] addresses this limitation by using a Transformer based mixer that dynamically combines predictions from multiple closed-form least-squares classifiers. Further- more, [52) is the first to introduce the necessary of node-equivariaace, label-equivariance and feature- invariance in fully inductive node classification. While empirically effective, GraphAny simply per- forms a learned average across the least-squares classifiers, which is very limiting for the model design space. contrast, we offer class of GFMs derived from first principles, offering theoretical guaran- tees. Existing pesssage-passing neural networks can be scamlessly integrated into recipe of GFMs.
20 47
3

---

Knowledge graph foundation models. There are recent graph foundation models dedicated for pre- diction with knowledge graphs (KGs). which can generalize to any KG, including novel entities and novel relation types (unseen during training), by learning transferrable relational invariants. Notable examples include RMPI 13. InGRAM 211, ULTRA [2], TRIX [5T], and MOTIF [8]. The expres- sive power of these knowledge graph foundation models has been recently investigated by Huang et al. [8]. Although these methods demonstrate promising generalization capabilities, they only apply to (knowledge) graphs without node features and lack any theoretical guarantees of universality. This lim- its their applicability to graphs with rich node features, which is critical for node-level prediction tasks.
Invariant and equivariant networks. Expressivity of equivariant and invariant neural networks well-studied within the graph machine learning community. In their seminal work on DeepSets, Zaheer et al. [50] established universality of Sy -yivvarriant networks over sets of size N. Subsequently, a universality result for permutation subgroups G < SN presented by Maron et al. [25) This uni- versality result is extended by Segol and Lipman [38 to show that DeepSets can approximate any SN- equivariant functions. Further advancements by Maron et 266 considered both SN -iinvariant and equivariant functions, where H < Sp and D denotes the number of input features. The proof techniques introduced Segol and Lipman [38] were partially adopted in Maron et al. (26) and also utilized to prove universality in other contexts. For example, universality for point-cloud-ccuuivrriaat functions with symmetry group SN x (O)3) and for higher-dimensional equivariant representations was established by Dym and Maron [9] and [11], respectively. Our work utilizes the proof techniques in [38 22 to extend the known universality guarantees to our hrple-symmetty GFM framework.
Scaling Laws in Graph Learning. Scaling laws have played central role in understanding and developing foundation models in domains such as natural language and computer vision, where performance is known to improve predictably with increased model and dataset size. Kaplan et al. [99 introduced the original scaling laws for language models, demonstrating that performance improves with larger models and more data. Hoffmann et al. [15] later refined this trend, showing that the models in [19] were under-trained and that slightly better performance could be achieved for smaller models. Similar scaling behaviors have been observed in vision, notably in Vision Transformers g
and large-scale contrastive models such as CLIP
B1.
In graph learning, scaling laws remain relatively underexplored. A first investigation is Liu et al. 23 which studies classical GNNs on graph-level classification tasks under varying model and dataset scales. However, this study is limited to traditional, task-specific architectures and does not address GFMs, which aim to generalize across diverse graphs, label spaces, or feature domains. remains un- clear whether scaling trends observed in narrowly-scoped GNNs also hold in this more challenging and general setting. Our framework is the first to demonstrate scaling-law behavior in GFMs, where per- formance improves consistently as the number of diverse training graphs increases (see Section 6.2
4 Universal Approximation of Functions With Triple-Symmetries
To derive a GFM that generalizes across arbitrary graphs and across feature and label sets, we first define universal approximators multiset functions that respect triple symmetries: permutations of nodes, features, and labels. In Section[4.1 these permutations and. By composing the linear layers with nonlinearities, we obtain a symmetry- preserving networks in Section 4.2 with universal approximation property. We later use these func- tions in Section onn on each node's 's neighborhood to obtain a message- -aasgggg-ssingg scheme for graph data.
characterize all linear maps that are equivariant to
4.1 Characterizing Equivariant Linear Layers
To define multilayer neural networks that respect triple-symmetries, we first characterize the linear layers that are equivariant to node-, label- and feature- permutations ("Equivariance Everywhere All At Once"). Our result builds on the rich literature on learning on sets [50] 38 26) and extends these techniques to our symmetry groups. To better locate our result, we first discuss existing characterizations for DeepSets (50] and for Deep Sets for Symmetric elements.
DeepSets. A seminal result for learning on sets is presented by Zaheer et al. [50], who characterize all linear maps of the form T ; NxF, + NxFs
Fas that are Sy-equivariant, as
T(X) XA, XA2, where A1, E R FixPs

---

Deep sets for symmetric elements (DSS). The characterization of Sy-equivariant functions intro- duced by Zaheer al. [50] extended by Maron et al. [26] to include an additional symmetry across the feature dimension. Specifically, they characterize all Sx x H H-equivariant linear maps, where H C Sp a subgroup of the feature permutation group Sp. Our interests lies in the simpler and more common case in which H = Sp, corresponding to the full feature permutation group. In this setting, Maron et al. [26] characterize all linear maps of the form T RNXPXX, + >RXxXxX that are (Sx x -qquivarri;; that is, for each k E [K2], the corresponding output T(X), Dank E ERN*A is
T(X) = N (1)
sake 1FF + INNN (2)
(() k2 1F + x(4
(I)
where Vi E
K1 X A. A &2 and A RK Note that symmetry across both axes of the feature matrix requires lifting the 2D function inputs used in DeepSets to 3D tensors in DSS and in our framework.
[4] X (0)
2,1k2 = -x
The limitations of semi-supervised node-clasiification Most existing GNNs and set-based archi- tectures, such as DeepSets or DSS, operate within the classical semi-supervised learning framework: each node in the input graph is associated with a feature vector, but only a subset of nodes have known labels during training. In this setup, the model learns to map node embeddings to the specific label set observed during training. Consequently, the model is inherently tied to this fixed label set and cannot generalize effectively to new or varying label sets encountered test time.
The label inpainting task. To enable generalization across label sets, we move beyond the classical semi-supervised regime and its dependence on the fixed set of training labels and feature, and fixed graph. In label inpainting, each datapoint is a graph G = (V, EV,E, X, Y) with node features [C]. The full graph and node features are given as inputs, along with the labels of a partial set of nodes L C [N]. The goal is to inpaint (predict) the labels of the remaining masked nodes R = [M] L. We consider supervised setting in which the dataset consists of many graphs, each with a different set of revealed label nodes. Each training graph has the ground-truth labels of the masked nodes available for supervision during training. but masked labels are hidden in test graphs. Note that difference data points, i.e. graphs at training or inference, may differ in their node features, label sets, and topology.
X RX and labels in
Our framework for triple-symmetry. To build a layered architecture consisting of equivariant linear layers and nonlinearities, we first find all linear alyers that respect triple-symmetries. The following proposition provides a complete characterization of the linear transformations T = (Ti, T2) R.N x(F+C) + R x(F+C) that are (Sx x SF x Sc)-equivariant. See Section C for more details.
Proposition 4.1. A linear function of the form T = (2); RNXFXK K2 NxFXX NXCxKa is (SN Sp X Sc) -equivarra if and only if there exist A(). .....
N
(12)
RK x K2 such that for every X E &NXFKK, Y E ER. & NxCxXK and k2 E [K2]. the corresponding NXC are given by
outputs Ti (X, Y) NXNxFX,, and
Ti(X, Y Y)nks
(INNN
1i likes
(1)
+ +x!11
(.ikaa) 1FF + +NNN (3)
+x(1)
SAk2
(IN,NY
(6)
+x
(2)
T2(X, Y)ank
(
+ +
10,0 + IN
L mink
(3)
+ +(())
line
midks
kikks
(IN.NX!
+ xx(() 1F
where for every i [6], we have x()
k2 Eki X iidh by and 1i.k2
(1)
= Eki X Ai Aaghy
((+6)
4.2 A Universal Approximation Theorem for Functions with Trimle-Symmetries
In this section, we introduce equivariant triple symmetry networks (TSNets), based on the (SN X SF x -quiiiarraa layers in Section 4.1 We prove universality for TSNeteq and then derive universality for the triple symmetry networks (TSNet) an (Sx x -cu-euuivrriant and Sp-invariant architecture that serves as the core building block of our GFM.
Triple-symmetry networks for multi-sets (TSNets). We define an equivaraint triple symmetry network (TSNetgg) FEq : N + R. (x(++C) as
FEq ( o (4-1)
5

---

where each 7()) RNX(P+C)XR(O) - BNX(++))xK((t) an (Sw x Sp x -c)-evvvvrriant linear layer, and o is a non-linearity.
We then define the space of TSNet label inpainters, TSNetLi as follows. Define the label projection map He by (X, Y) Y for all (X,Y) E RXXFxx x RRxxxx A triple symmetry network F R NxCxx in TSNet, if it is of the form F Πe FEq. where FEqq [RNX(F+ + [X is a TSNetEq.
Observe that Tec is Sy-invariant and each intermediate linear layer T()) is (SN SF Sc)- equivariant by construction. Since equivariance and invariance are preserved under compositions, it follows directly that the resulting network F is both (Sv -e)-evvivrr and Sy-invariant, as required. We set (0) ( 1 that the network
accept the initial feature and label matrices and outputs predictions with the same shape as the ground-truth labels.
We now state our main result: TSNets are not only approximators, i.c., capable of approximating any continuous function that respects the triple- symmetries. More accurately, this guarantee holds over any symmetric compact domain which is disjoint from some small set, called the exclusion set & (Definition D.20).
prreeerrin- but are also universal
Lemma 4.2. Let K C (FF+CC) be compact domain such that K. S 9 and KNn = 0. where & C CRN(((F+C) is the exclusion set corresponding to R.Nx(F+O) (Definition) D.20 Then, TSNetgq is universal approximator (i.e. in Log) of continuous K. -+ Nx(+FF) functions that are (SN X SF x -e)eevvvrriian..
Theorem 4.3. Let K C. (Nx(F+C) be compact domain such that K. X 9 and KNε = U. where& & C (x((FO) is the exclusion set corresponding to RNx((F+)) (Definition D.20 Then, T is a universal approximator of continuous K. - BR NxC functions that are (Sw Sc)- equivariant and Sp-invariant.
Relations to the literature. Our result is closely related to Theorem 3 of (26). which establishes a universality result for (Sv x -equivarri networks, where H Sr. Specifically, the theorem states that for any subgroup H C Sr and any compact domain K. C Nx that is closed under the action of (SN x H) and avoids the exception set E' (defined in Definition E.2 If H-equivariant networks are universal for H H-equivariant functions. Then, (SN x - networks are universal approximators (in the Los norm) for continuous NSN H))equivariant functions defined on K. However, their proof contains a subtle but important flaw. They introduce an H H-equivariant polynomial P1 : N + R. and write "If we fix X XN. then P1 (X1.... ........ XN) is an H- equivariant polynomial in X1" which does not hold generally. By definition, H -qquivaare of p1 requires the group action to be applied consistently across all arguments: applying the action to only one row while fixing the others violates equivariance. We refer the reader to Section F for a detailed discussion on this issue, why it invalidates the general universality claim for arbitrary subgroups H < Sr and how, by leveraging techniques from 38, the claim can still be upheld in the special case H- = Sp a key insight that allows us to show universality for TSNets in Theorem
5 A Recipe for Graph Foundation Models for Node Property Prediction
In this section, we build on the results from Section 4.1 derive a practical architecture for node property inpainting (see Figure 2}. Specifically, we construct a learnable layer that is equivariant to the symmetry group NS SF Sc) based on any aggregtion scheme. In the graph setting, this elevates the MPNN to a symmetry-aware foundation model that generalizes across diverse feature sets and labels, unlike traditional GNNs.
We start from Equation 2 which can be interpreted as passing messages by applying sum aggregation along the feature, label, and node axes. We generalize these sums arbitrary operators (e.g., mean, max, or attention style aggregations). Setting the operators to sums recovers the linear structure of Equation (2).
Triple-symmetry graph neural networks (TS-GNNs). Consider inputs of the form (X, Y, A) E (Fxx(++))x x (0, NJN, where X E N is feature matrix, Y E NxC is label matrix, and A E [0, No.. X is the graph adjacency matrix. Formally, define triple-symmetry graph

---

Y
Y a
X
X
K
KO)
K(L-1)
K(E)
Figure 2: An illustration of the feature and label embeddings across the layers of our triple-symmetric graph neural network architecture. The architecture is composed of feature-, label- and equiviauiva aggregation layers and final feature-invartn projection layer.
neural network F (BNx((+O) x [0, NJ RNXXX1 as
F= ToTOT 00 1ooOT--11 o0....o
T(0 CN x - BNN((FC))XXK)))) X 10,1
where a is non-linearity (e.g.. ReLU) and each (()) is an (SN x SF x Sc))-quivvriant layer with a general aggregation along the feature, label and node axes, that acts jointly on the node features and
node labels, while also using the adjacency matrix. Each (()) updates the feature x!!)) E R R xF and label ( RRK xC representations of node E V layer as
x e (w (
(W2 X (0) I (.E.
+ 1h (W
IIF ( uX a EEN
+ 2 (W! 1I. IY
vY 11 I -
(((+1) + (W;")
(w 10 (Y M
I (EN. Oc. ( (
where v is the node aggregation function, is the label/feature aggregation function, /
k x(()) E [12]. are learnable weight matrices (replacing the coefficients A,), and the terms OF and Oc are (SNv x SF x Sc) )e--euuivari feature- mixing terms (detailed below). Finally, the label projection map II is applied to obtain node-wise predictions. Similarly to TSNets, we also set (0) (L) = 1. It is easy to see that the architecture is (Sx x -eqiiiirrri and Si-invariamt, desired, In this formulation, the aggregations can be based on any MPNN, e.g., GAT,
GraphSAGE, or GCNII 42 [1.
How to mix features and labels? A key consideration in designing graph foundation models is determining the degree of interaction between feature and label embeddings. In the extreme, if we do not impose any such interactions then the model's 's predictions would be independent of the input features, leading to a degradation in model performance. Effective information flow between feature and label representations is thus essential for building strong graph foundation models. This raises central design question: To what extent should feature embeddings and label embeddings interact?
In TS-GNNs, we initially perform mixing by applying permutation permutation-invariint pooling operations (c.g.. fcature-wise or label-wise sum pooling) and appending the pooled representations to the opposing modality (fcature-to-labe) and label-toffcaturey While such operations are theoretically sufficient for our universal approximation result (Section 4.2), they often suffer from practical limitations, because all feature label information is compressed into single vector representation, creating representational bottleneck.
To overcome this issue and enable richer feature-label mixing, we introduce additional mixing operation based on least-squares solutions, which showed strong empirical results 52 Specifically, solve the following optimization problems:
TF arg min ||Y -AXTelle and To
X To CxF
arg min
AYTalk
Tp FxC
7

---

where A is random the label space and labels into the feature space, respectively. We incorporate these least-squares transformations into each layer follows:
sandom-walk walk normalized adjacency matrix. These projections transform features into
+ r v Y Te, HW
U
Te Toclluen ueN.B))
C &
Tr, WW T (
15
where W
w 16
R x are learnable weight matrices.
13
These terms share the same objective as our original mixing terms. but crucially avoid collapsing over feature or label dimensions. Instead, they introduce structured, linear mappings across modalities Tr and To, enabling localized mixing. Importantly, these least-squares transformations are linear and are equivariant node-, feature-, and label- permutations, allowing us to retain the triple-symmetry property at every layer. This design also lays foundation for future extensions involving more expressive mixing mechanisms.
How to incorporate bias terms? Another important design choice involves the integration of bias terms into a model that needs generalize to varying feature scales. Even after row-wise or global L1/L2 normalization, node features can differ both within a graph and across graphs. A bias vector learned on the set of training graphs may be much larger or much smaller than the features which are going to be observed at test time. This is clearly problematic for generalization, as the bias term may for instance dominate the actual input features in magnitute, leading to them being largely ignored. To avoid this, one option is to completely avoid using bias terms in the layers, but this is too restrictive. In our architecture, we solve the least-squares problem including an added bias term, and the bias terms obtained, are injected only through the feature-to-label and label-to-featur mixers (Op F and θc). Such biases are learned relative to the current feature scale, and thus remain scale-aware and adapt naturally to new graphs, offering better generalization.
6 Empirical Evaluation
We empirically validate the capabilities of TS-GNNs, addressing the core research questions:
Q1 Can the proposed graph foundation models effectively generalize unseen graphs with varying structures, feature configurations, and label semantics without retraining?
Q2 Does the zero-shot generalization ability of the proposed graph foundation models improve as the number of training graphs increases?
In Section G we additionally investigate supplementary questions:
Q3 How sensitive are TS-GNNs to the choice of pretraining dataset in low-data regimes?
Q4 What is the impact of least-squares mixing and the bias term on TS-GNNs' performance?
Q5 Is triple-symmetry necessary for graph foundation models?
To address these questions, we perform experiments across 29 real-world node classification datasets, covering diverse domains, graph sizes, and feature representations. Note that we focus on the node classification setting due to the lack of regersegrssioo datasets, and refer the reader the appropriate discussion in Section H We train TS-GNNs by randomly masking the labels of 50% of the labeled nodes at each epoch and optimizing the model to predict the masked labels from the node features and the remaining visible labels. We optimize all models using the Adam optimizer, with detailed hyperpa- rameter settings provided in Scction]
D Experiments are executed on a single NVIDIA L40 GPU, and publicly accessible at: https: / gi thub. www.coo//beeeeee benf//enfii inkelshtein. wttpssstteiinuiuiiieeeeee www.divaainnneveeree Eveeeweyeeer
Datasets. We use an ensemble of 29 node classification datasets and their respective official splits. Specifically, we use roman-empiree amazon ratiings, minesweeper, questions and tolokers from 30 cora, citeseer and pubmed from [49], chameleon and squirrel from (36). cornell, wisconsin, texas and actor from [29]. full-dblp and full-cora from
[3] wiki-attr and blogcatalog from [48), wiki-cs from
277, co-cs, co-physics, computers and photo from 339 brazil, usa and europe from 34 last-fm-asia and deezer from (35), and arxiv from [17. As full-Cora, co-cs, and co-physics, have an exceptionally large feature dimension, we first reduce their feature dimensionality with PCA 2048 components
before training. Lastly, apply L2 normalization to each node's 's feature vector.
8

---

Table 1: Test accuracy of the baselines MeanGNN and GAT and models GraphAny and our GFM variants, all trained on cora. Top three models are colored by First, Second, Third.
End-to-end
Zero-shot
McanGNN
GAT
GraphAny
TS-Mean
TS IS-GAT
32.03 + 0.29
32.59 + 0.83
27.54 + 0.20
28.09 0.93
28.80 +: 2.12
amazon-ratings
40.74 + 0.13
40.63 + 0.66
42.80 0.09
42.27
1.40
41.92 +
arxiv
50.94 + 0.38
57.93 3.44
58.85 = 0.03
56.33 1
53.13 + 2.04
blogcatalog
84.48 +: 0.74
78.20 7.23
71.54 3.04
76.30 :
78.44 : 5.18
brazil
$2.31:7.500
35.38 4.21
33.84 + 15.65
39.23 5.700
36.92 : 10.03
chameleon
61.75 0.94
58.46 6.23
63.64 1.48
60.4
54.65 4.58
citeseer
65.06 + 1.30
63.92 0.84
68.88 0.10
68.66
68.70 0.48
Co-cs
80.87 + 0.69
8
90.06 0.80
90.92
91.13 +.13+004
co-physics
79.05 1 1.13
1.10
91.85 0.34
92.61
92.23 1 0.61
computers
73.88 1 0.88
7..94
82.79 1.13
81.37
80.23 4
cornell
63.78 1:
69.73
63.24 1.32
68.65
71.35 4.52
deczer
54,91 = 1,81
5
51.82 2.49
2.52
52.88 + 2.86
europe
39.12 6.44
19.00+4.31
41.25 7.25
35.88
38.38 +
6.32 6.32
full-DBLP
65.01 2.40
2.75
71,48 1.44
3.65
04.30
full-cora
55.85 1.04
59.95
51.18 0.78
53.58
52.82 +
last-fm-asia
77.23 3:3 1.01
72.65 0.48
81.14 0.42
78.03 1.02
76.60 1.44
minesweeper
84.06 0.18
0.24
80.46 + 0.11
80.68 0.38
80.72 + 0.78
photo
88.95 + 1.08
80.78 3.59
89.91 0.88
90.18 1.30
89.66 + 1.23
pubmed
74.56 +: 0.13
75.12
76.46 1 0.08
74.98 - 0.56
75.46 + 0.86
questions
97.16 0.06
97.13
97.07 0.03
97.02 0.01
1
roman-empire
69.37 + 0.66
69.80
63.34 0.58
66.36 1.02
67.76 0.66
squirrl
43.32 0.66
38.16
49.74 0.47
41.81 0.80
38.29 4.29
texas
76.76 + 1,48
6.46
71.35 2.16
73.51 =
74.05 4.10
tolokers
78.59 1 0.66
1
78.20 0.03
78.12 0.09
78.01 1 0.23
usa
43.93 + 1.16
43.03 1 2.08
43.35 1 1.62
42.34 2.12
41.69 1 2.59
wiki-attr
74.23 + 0.89
68.91
60.27 + 3.06
69.89 1.31
72.53 1 1.59
wiki-cs
71.97 + 1.70
7 0.59
74.11 0.60
74.16 + 2.07
73.24 + 2,49
wisconsin
74.12 = 12.20
73.33 + 8.27
59.61 5.77
61.18 = 11.38
65.88 + 9.86
Average (28 graphs)
65.50 + 1.75
65.55 + 2.82
65.56 + 1.86
65.78 + 2.28
65.60 + 2.74
6.1 Do TS-GNNs Generalize Unseen Graphs?
Setup. To evaluate generalization (Q1), we design an experiment to assess how well each model performs after being trained on single graph (cora) - measuring how much transferable knowledge can be extracted from that graph. Our setup closely follows the setup introduced in GraphAny [52] We experiment with two widely-used baseline GNN architectures: MeanGNN and GAT 42 Since these models are inherently non non-transferable across datasets, we train and evaluate each baseline in an end-to-end fashion on every dataset. Further to this, we provide zero-shot experiments with TS-Mean and TS-GAT, which are TS-GNNs using MeanGNN and GAT, respectively (as their aggregation function). Additional GNN variants, such as TS-GCNII, are evaluated in Section G.4 We also experiment with the only other node-level graph foundation model GraphAny (52), which provides strong zero-shot prediction bascline. In the zero-shot setup, we train each model TS- Me-Mean, TS-GAT, and GraphAny the cora dataset and evaluate their performance the remaining 28 datasets. All reported results reflect the mean accuracy and standard deviation over five random seeds.
Results. Table T shows that both TS-Mean and TS- TS-GAT consistently outperform their respective base- lines, despite being trained in an end-to-end manner. This highlights the generalization capabilities of proposed framework and its compatibility with varying GNN architectures. Furthermore, both TS-Mean and TS-GAT outperform GraphAny on average across 28 datasets under its own evaluation protocol, further underscoring the strong generalization capabilities of our framework. These results directly address our initial research question (Q1) our proposed framework. that is also theoretically grounded, successfully generalizes across graphs, features, and label distributions without retraining.

---

6.2 Does More Training Data Improve Generalization?
Setup. To assess the impact of the amount of training data on zero-shot generalization (Q2), we 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 20 datasets are used for zero-shot evaluation. For each subset size, report mean zero-shot accuracy, averaged over five random seeds. Detailed per-dataset results are provided in Section G.5
TS-Mcan
68.4
GraphAny
Avg. Accuracy
08.2
67.6
Results. Figure 3 shows that the zero-shot accuracy of TS-Mean improves steadily as more training graphs are introduced. This behavior aligns with the expected characteristics of graph foundation model the ability to benefit from increased data diversity, directly addressing Q2. In contrast, GraphAny's performance remains unchanged as more training graphs are added. This counterintuitive result suggests 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 comparably when trained three graphs less, indicating that TS-Mean is competitive in the low-data regime. However, as the training set grows, TS-Mean increasingly outperforms GraphAny, highlighting the benefits of performance that scales with training data.
#Training Graphs
Figure Average zero-shot accuracy of TS-Mean and GraphAny across 20 datasets as a function the number of training graphs
While we do not claim to establish a formal "scaling law," this offers, to our knowledge, the first empirical indication that a GFM improves with more training data key property of foundation models in language and vision. These findings position TS-GNN as a strong and, present, the only viable candidate for node-level graph foundation modeling.
7 Conclusion
This work introduces a principled, peoretically-groundde framework for designing GFMs for node- level classification and regression tasks. At the heart of our approach lies the triple-symmetry criterion: a GFM must be equivariant to node and label permutations and invariant to permutations of input features. These symmetries capture the key inductive bias required for generalization across graphs with varying structures, feature spaces, and labels.
Building this, we propose triple-symmety neural network which is proven to bea universal approximator of triple-symmetry respecting functions. By applying TSNets to the multisets of features induced by the local graph neighborhoods, and by extending TSNet to general aggregation schemes, we derived triple-symment graph neural networks: a flexible framework that extends any GFM capable of zero-shot generalization.
standard GNN into hiill-syymetty-anvee
Our empirical study validates the effectiveness of this recipe. We train the GFM variations of the well-used models MeanGNN and GAT single dataset, achieving robust zero-shot generalization across 29 diverse node classification benchmarks, outperforming not only their original counterparts, but also the prior state-of-the-art GraphAny. Furthermore, we present the first empirical evidence that a graph foundation model can systematically benefit from increasing training data: TS-Meat exhibits steadily improving zero-shot performance as more training graphs are introduced, while GraphAny fails to do so. These findings underscore the strong generalization capabilities of our principled recipe.
Altogether, our work provides a unified theoretical and practical foundation for constructing gener- alizable GNNs. 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. As the landscape of graph learning moves toward more flexible and general architectures. our work offers a compelling blueprint for building robust, transferable and principled models.
10

---

Acknowledgments
We thank Yonatan Sverdlov for discussions regarding related literature and its theoretical relevance to this work. This research was supported by grant from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel, and the United States National Science Foundation (NSF), (NSF-BSE, grant No. 2024660), and by the Israel Science Foundation (ISF grant No. 1937/23). BF is funded by the Clarendon scholarship. MB is supported by EPSRC Turing AI World-Leading Research Fellowship No. EP/X040062/1 and EPSRC AI Hub Mathematical Foundations of Intelligence: An "Erlangen Programme" for AI No. EP/Y028872/1.
References
[1] Hangbo Bao. Li Dong, Songhao Piao, and Furu Wei. Beit: Bert pre-training of image trans- formers, 2022.
[2] Maya Bechler-Speicher, Ben Finkelshtein, Fabrizio Frasca, Luis Müller, Jan Tönshoff, Antoine Siraudin, Viktor Zaverkin, Michael M. Bronstein, Mathias Niepert, Bryan Perozzi, Mikhail Galkin, and Christopher Morris. Position: Graph learning will lose relevance due to poor benchmarks. In ICML, 2025.
[3] Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsu- pervised inductive learning via ranking, 2018.
[4] Emmanuel Briand. When is the algebra of multisymmetric polynomials generated by the elementary multisymmetric polynomials. Beiträge zur Algebra und Geometrie, 2004.
[5] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In ICML, 2020.
[6] Sanyuan Chen, Chengyi Wang, Zhengyang Chen, Yu Wu, Shujie Liu, Zhuo Chen, Jinyu Li, Naoyuki Kanda, Takuya Yoshioka, Xiong Xiao, Jian Wu, Long Zhou, Shuo Ren, Yanmin Qian, Yao Qian, Jian Wu, Michael Zeng, Xiangzhan Yu, and Furu Wei. Wavim: scree supe--uue pre-trac training for full stack speech processing. IEEE Journal of Selected Topics in Signal Processing, 2022.
[7] Sanyuan Chen, Yu Wu, Chengyi Wang, Shujie Liu, Daniel Tompkins, Zhuo Chen, and Furu Wei. Beats: Audio pre-training with acoustic tokenizers, 2022.
[8] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. 2021.
[9] Nadav Dym and Haggai Maron. On the universality of rotation equivariant point cloud networks, 2020.
[10] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[11] Ben Finkelshtein, Chaim Baskin, Haggai Maron, and Nadav Dym. A simple and universal rotation equivariant point-cloud network. In TAG Workshop ICML, 2022.
[12] Mikhail Galkin, Xinyu Yuan, Hesham Mostafa, Jian Tang, and Zhaocheng Zhu. Towards foundation models for knowledge graph reasoning. ICLR, 2024.
[13] Yuxia Geng, Jiaoyan Chen, Jeff Z. Pan, Mingyang Chen, Song Jiang, Wen Zhang, and Huajun Chen. Relational message passing for fully inductive knowledge graph completion. In ICDE, 2022.
[14] William I.. Hamilton, Rex Ying, and Jure Leskovee. Inductive representation learning on large graphs, 2018.

---

[15] Jordan Hoffmann. Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, al. Training compute-optimal large language models. arXiv, 2022.
[16] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. NeurlPS, 2020.
[17] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NewrIPS, 2021.
[18] Xingyue Huang. Pablo Barceló, Michael M. Bronstein, Ismail Ilkan Ceylan, Mikhail Galkin, Juan L Reutter, and Miguel Romero Orth. How expressive are knowledge graph foundation models? In ICML, 2025.
[19] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv, 2020.
[20] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[21] Jaejun Lee, Chanyoung Chung, and Joyce Jiyoung Whang. Ingram: Inductive knowledge graph embedding via relation graphs. In JCML, 2023.
[22] Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural Networks, 1993.
[23] Jingzhe Liu, Haitao Mao, Zhikai Chen, Tong Zhao, Neil Shah, and Jiliang Tang. Towards neural scaling laws graphs. arXiv, 2024.
[24] Haitao Mao, Zhikai Chen, Wenzhuo Tang, Jianan Zhao, Yao Ma, Tong Zhao, Neil Shah, Mikhail Galkin, and Jiliang Tang. Position: Graph foundation models are already here. In ICML, 2024.
[25] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality invariant networks. In /CML, 2019.
[26] Haggai Maron, Or Litany, Gal Chechik, and Ethan Fetaya. On learning sets of symmetric elements. In ICML, 2020.
[27] Péter Mernyei and Cätälina Cangea. Wiki-cs: wikipedia-based benchmark for graph neural networks, 2022.
[28] Gerhard Paaß and Sven Giesselbach. Foundation models for natural language processing pre-trained language models integrating media. Springer Nature, 2023.
[29] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks, 2020.
[30] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look the evaluation of gnns under heterophily: Are we really making progress?, 2024.
[31] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In ICMI., 2021.
[32] Alec Radford, Jong Wook Kim, Tao Xu, Greg Brockman, Christine McLeavey, and Ilya Sutskever. Robust speech recognition via large-scale weak supervision, 2022.
12

---

[33] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. JMIR, 2023.
[34] Leonardo F.R. Ribeiro, Pedro H.P. Saverese, and Daniel R. Figueiredo. struc2vec: Learning node representations from structural identity. In KDD, 2017.
[35] Benedek Rozemberczki and Rik Sarkar. Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models. In CIKM, 2020.
[36] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 2021.
[37] David Rydh. A minimal set of generators for the ring of multisymmetrri functions, In Annales de I' l'institut Fourier, 2007.
[38] Nimrod Segol and Yaron Lipman. On universal equivariant set networks. arXiv, 2019.
[39] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation, 2019.
[40] Karen E. Smith. Groups and their representations, 2017. Lecture notes, University of Michigan.
[41] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models, 2023.
[42] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. ICLR, 2018
[43] Jianfeng Wang, Zhengyuan Yang, Xiaowei Hu, Linjie Li, Kevin Lin, Zhe Gan, Zicheng Liu, Ce Liu, and Lijuan Wang. Git: A generative image-to-text transformer for vision and language, 2022.
[44] Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, et al. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv, 2019.
[45] Peter Woit. Topics in representation theory: Finite groups and character theory. https 2006.
7/www. wwwh.
[46] Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr., Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. In ICML, 2019.
[47] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[48] Renchi Yang, Jieming Shi, Xiaokui Xiao, Yin Yang, Sourav S. Bhowmick, and Juncheng Liu. Pane: scalable and effective attributed network embedding. The VLDB Journal, 2023.
[49] Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting cun--supervieed learning with graph embeddings. In ICML, 2016.
[50] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. In NeurlPS, 2017.
[51] Yucheng Zhang, Beatrice Bevilacqua, Mikhail Galkin, and Bruno Ribeiro. Trix: A more expressive model for zero-shot domain transfer in knowledge graphs, 2025.
[52] Jianan Zhao, Zhaocheng Zhu, Mikhail Galkin, Hesham Mostafa, Michael Bronstein, and Jian Tang, Fully-inductive node classification on arbitrary graphs. In ICLR, 2025.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the motivation, scope, and main contributions of the paper. These include the identification of necessary symmetries for graph foundation models (GFMs), the characterization of equivariant linear layers, universality theorem for multilayer architectures, and practical recipe for converting any GNN into a GFM.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We acknowledge several limitations of our study in the introduction and discussion. Specifically, we restrict our framework and experiments node-level tasks and do not evaluate regression, even though the theory supports it.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specifiiattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
14

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Our paper contains formal statements of the main theoretical results, including a characterization of all linear layers equivariant to SN x Sp x Sc actions, and a universality theorem for the resulting multilayer networks. The complete proofs are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide full details of the experimental setup, including dataset sources, evaluation metrics, training protocols, model architectures and hyperparameters.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
15

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We reference the sources of all datasets used in experiments. Further- more, we also provide our full codebase, along with detailed instructions to reproduce our experimental setup, including hyperparameters, model configurations, and random seed settings.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
siiiiioosssyyyyyy for more details. / //nips https/scccpullcguuddeeeeeeee http://oodubmisiiiiooo.oo
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: The paper provides a detailed description of the experimental protocol in both the main text and the appendix. We evaluate approach on 27 real-world node classification datasets, where models are trained on Cora and tested on all remaining datasets. Hyperparameters, optimizer choice (Adam), and evaluation procedure are described in the appendix, along with full dataset. Furthermore, we follow standard, commonly used splits and an a link the code-base is provided ensure full reproducibility.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
16

---

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All reported results accompanied by standard deviation error bars computed across the random seeds, 0,1,2,3 and 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots. The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We use single NVIDIA L40 GPU for all experiments, as reported in the experimental section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httppp///aerrrp...cccaaaaa////aa
Answer: [Yes]
Justification:
The research fully conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
17

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper focuses on the theoretical and empirical development of graph foundation models. As such, no meaningful societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymenn of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work poses no risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
18

---

Justification:
We cite the source/paper of each of the 28 datasets used throughout the work.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssii thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do note introduce any new assets in this work.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work does include crowdsoureing experiments or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
19

---

Answer: [NA]
Justification: Our work does not include crowdsourcing experiments or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: Our framework does not involve LLMs or their usage.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non standaadd components.
Please refer to our LLM policy hatts:://eurrips.cc//ffeeeeeeee for what should or should not be described.
20

---

A Groups, Permutations, and Symmetries
A.1 Primer on Representation Theory
We denote the identity element of any group by The notation H S G indicates that H is subgroup of the group G. Denote by GL (V) the general linear group of invertible linear transformations on the vector space V. Denote by idy the identity map vector space V.
Representation theory studies how abstract groups can be understood by expressing their elements as linear transformations on vector spaces. This is formalized by a group homomorphism from the group into the general linear group, called representation. We begin by recalling the notion of group homomorphism, which a structure-preserving map between groups.
Definition A.1 (Group Homomorphism), Let G and H be groups. A map group homomorphism if satisfies
is called
Vg 92 E G Φ(g1 - 92) x(91) -(9)).
Definition A.2 (Representations). Let G be group. A representation p: GL (V) of group G on a vector space V over a field F is group homomorphism p: p:G (V).
Next define group action, which generalizes group representation. We often want to describe how the elements of group can effect a set - transforming its elements in a way that reflects the group's algebraic structure. This idea is formalized through the concept of a group action.
Definition A.3 (Group Action). Let G be a group and X set. A group action of G on X is mapping G x X, denoted by ,, such that
9 (h (h-x) (gh)
. e..x=
for all g, h E G and all & E S.
We say that the group element E G acts the element X via g A representation p: GL (V) special case of a group action where the set X a vector space and the action of G on V is given by g p(g)v for V.
Given group action, is natural ask about the set of all elements that can be reached from a given one via the group action. This leads to the concept of an orbit.
Definition A.4 (Orbit). Let G a group acting on a set X. The orbit of x E XX defined to be
Og(x) (g G).
Given group representation, we often look for subspaces that are preserved by the action of all group elements. These subspaces are known G-invariant subspaces and the restricted representation to this subspace is called subrepresentation.
Definition A.5 (G-invariant Subspace). Let G GV) be a representation. linear subspace W C V is called (G-invariant if
Vg W E : p(g)w E W.
Definition A.6 (Subrepresentation) Let p: G GV) be representation. Let W S V be G-invariant subspace. The map plw G + GL (W) defined to be p(g) restricted to inputs from W, called the subrepresentation of p on W.
Some representations cannot be broken down into smaller, nontrivial subrepresentations. These are known irreducible representations.
Definition A.7 (Irreducible Representation). A representation p G + GL (V) is called irreducible if the only G-imvariant subspaces of V are the trivial subspaces {0) and V.
We next define symmetry preserving mappings. Such mappings are typically called intertwining operators in representation theory, but more common term for them in deep learning is equivariant mappings.
21

---

Definition A.8 (Equivariant Mapping between Representations). Let G - GL(V (V) and
Pw G - GL (W) be representations of a group G. A linear mapping f V W is called
G-equivariant (with respect to pV and pw) if it satisfies
g E G, U V f(pv(g)u) = pw(g))(v).
Next, we define which representations considered equivalent.
Definition A.9 (Isomorphic Representations), Let pv G - GL (V) and pw G G GL (W) be two representations. The representations are called isomorphic (denoted by pV E pw) ) there exists bijective linear map yp V W (i.e., isomorphism linear spaces V = Wuschh that
Y v E V. GEG: ((pv(g)u) = pw pw (g)
Such a is called a representation isomorphism.
classical result characterizing linear equivariant mappings between irreducible representations is Schur's lemma. Given two irreducible representations, one may anticipate that there could potentially be many Geeuiivrriant mappings between them. However, Schur's lemma states that is essentially either one or zero such mappings. The following is one variant of the lemma.
Lemma A.10 (Thcorem 2 in [45], Schur's Lemma). Let G be a finite group. Let pV : G GL (V) and pw G GL (W) be irreducible representations. Let be the space of G-equivariant linear mappings from V to W.
1. If pv and pw are not isomorphic, then O-dimensional (only 0 intertwines pv and pw)
2. If pv and pw are isomorphic, then L is 1-dimensional (up to multiplication by sealar, there is only one equivariant operator between pv and pw, which is representation isomorphism).
Part 2 of Schur's lemma means that if there exists an isomorphism between the irreducible representations PV G (V) and pw : G - GL (W) then any other isomorphism of these representations is scalar times yp Moreover, any linear G-equivariant mapping must be an isomorphism or the zero mapping.
For two representations PV - (V) and pw G - GL (W), we define the representation pv pw G GL (V e W), for V and W, by
(pv @ (g)( w) = (g)v, (g),, (g)w))
The tensor product of pv @ pw G - GL (V @ W) is defined on simple tensors v @ w (where E V and w W) by
(pv pw) w) (pv(g)u) @ (pw(g)w).
Since the linear closure of the simple tensors is the whole tensor product space V & W, the above definition uniquely extends from simple tensors w 2 to general elements in the tensor product space Z E V & W. For example, when V R and W = it we identify V & W with R. VxM and for
matrices (g) E RNNN and Pw (g) E R M we have for any E IR N
(pv & Pw (g) = pv (g) (W)
In this example, the simple tensors are rank-1 matrices, and the space of matrices is spanned by the rank-1 matrices.
From this point onward, when the representation of the group G is clear from context, use the shorthand notation g X instead of pv (g) X to denote the representation (g) acting on X E V.
A.2 Representation Theory of the Symmetric Group
Here, we present standard results the standard permutation representation of the symmetric group. Recall that Sx denotes the group of permutations, i.e. the symmetric group. Definition A.11 (The Symmetric Group). The symmetric group SN the group of all permutations of the set [N] N).
22

---

We denote by = (ij) E Sx the permutation that swaps the i-th and j-th elements, leaving the remaining elements fixed.
Definition A.12 (The Standard Permutation Representation). The standard permutation representation PN Sy + GL (R*) is given by
VaN E SN. PN(ON) (o)..
The following two subspaces of R,, denoted by VoN and Vi can be shown to be the only two irreducible subrepresentations of the standard permutation representation of S on I...
Definition A.13 (The standard subspace and representation). The space
VON {x EN 1 =0
is called the (N - 1}-ddmeensional S standard subspace. The standard representation of Sy. denoted by Pvg SN + GL (Vo*). ) is defined as
VoN E SN, E Vo Pva (oN)o= (3Oz'()) (1)""))...0000(11)
Row(N))
Definition A.14 (The trivial subspace and representation). The space
V/" {cIN |CER]
is called the 1-dimensional Sy-invariant trivial subspace. The trivial representation of SN, denoted by Pvp SN GL (V?*), is defined
YoN E SN (vp)(N)) =1 (where I the identity operator).
We adopt the names of the above two spaces from Chapter 3 in 40
can now be seen that E decomposes direct sum of the irreducible subspaces of S defined above. Moreover, the standard permutation representation also decomposes to the above two representations.
Lemma A.15. The subspaces V and Vi of RR are orthogonal, and R.N = V V.N. Moreover PN = Pvg @ pvp, and the representations pv and Pvv are the only two irreducible subrepresen- tations of px-
A.3 The Symmer-Sy Group
Let K,N,F,C E N. In the setting of the triple-symmetric group, we consider three copies of symmetric groups SN, Sp, and Sc, each acting on one dimension of the input tensor. Namely, each of the three groups acts on X E xxXxx((F+C) as follows.
Syy acts by permuting the second axis, i.c.
(oN X) X)km.
X X.o (m).s) VaN E SN, E E [F+ Cl.
SS acts by permuting the first F entries of the third axis, i.e.
(ōr X) X)s,n..= = X (am,o,"()) Yar E Sp, k E [K], [N]. e [F],
Sc acts by permuting the last C entries of the third axis, i.e.
(ar X D.n.Ftt X xgn Vac Sr, [K], (N], (C].
When K= 1, we simply consider the space R Nx++O), where, here, Sy acts of the first axis, and SF and Sc act on the second axis as above.
23

---

B Proof of Proposition 4.1
In this section we provide the proof for Proposition 4.1
Let G + GL (IR (R))((+))) be the representation defined by
X xx)())))
if E [F], otherwise
((oN.0r,oc..x) X)n.
-X) =
X (o)
Denote
Rº = (x E E RP+C #F+1F4C=0),
#1.F =0, RC = (a E RF
R (x R 1 ==0==
RS {a E RC 1 0), Rf [(0,clc) CR
R ((c1p,0) R),
Lemma B.1. The only irreducible subrepresentaions of p are on the following eight invariant subspaces
W = V @ Ri CRN(((FO))
for a, b (0,1) and L E (F,C), where V.N are defined in Definitions A.13 and A.14
Proof. By construction
R Nx(F+O) ~ RR
R
(R-V & RR) and p = (paN @ PRP) + (peN @ pro).
where PRD : G GL (RP) are the representations of G on IR for D E F,C
By Lemma A.15 the subspaces VP and ViP D @ Vi are orthogonal, and the represen- tations Pv: and PaP are the only two irreducible subrepresentations of pD = PvP + pvp, where (4). we get the eight invariant subspaces
D E (N, F, C). Thus, by substituting this into Equation
R (x(+CC (Vo" X R (V
+ (V & BB") + (Vi @ Rf @ (Vi @ RF) (VT (
R @
(VG do RI @ (VT 6o R
and the corrisponding eight irreducible representation
p = PvN P25) + (pvr @ P25) @ (Pvr 8 PBF) @ (pur @ PBF)
+ (Pv & PRO) + (pvp & Png @ (pvg & PRR) @ (pvp @ PRg)
Proposition 4.1 Let F #C C.E.NAA A linear function
T (T RIXNXF RIXNNC - RKKNNK RRXNNC
(SN x Sp x Sc) -e)-equivarian if and only there exist A A A E RRXK2 such that for every X E N Y E NxCC., and 2y E [K2), the corresponding outputs Ti(X, Y) Nx and (x ((,Y) Y) E NxCKKa are given by
TX Y) )ink = (IN
+ xx(1)
LFF +IF+IN.NXC bi.k2 + (4)
like
Likk
(INNN
(())
+x(0)
LCFF
liikg
T2(X, Y).nks = YIN
(I)
+ (2)
l + INNNY like + (
tike
ki
(1N.N
+ xx( (6)
1Fc.
for every 12 E [K2), where for every i (()
[6], we define (i)
Eki X.nkk (1)
bi and
20.k2
Links Ik: Yunk, A Aki
(6+6)
24

---

Proof. For i E {1,2}, consider the representation P: :G - GL (R (RM((P+))XRi) where G :=
Sy Sp x Sç is defined in Section A.3 by
j E [F],
((ON,OF,OC) X) ))ss
(5)
X (w)
otherwise
for all (ON, Op..Op,0)) E SN x SF x Se and X (Rx((+C)XK,, Similarly, denote by p : G GL (RA)x(FOO) the representation as (5) with K,
+
Let i E {1,2]. For each & E [K,], let Vž C (FX((F)) be the subspace vectors X such that Xnj.k/ = O for every + k. Note that Vi an invariant subspace. The subrepresentation pilve
isomorphic to (FF+CC) via the isomorphism ot. (Nx(FF)) - Vi defined by ri( X S.
By Lemma B.I the only irreducible subspaces of pı are ReiKaaaaaaDD
(V.. = (m²) (V." @
By dimensionality consideration, the only pairs of subrepresentations of and P2 that can be isomorphic are pilvz, k... and م lvz 2...... for any kn [Ki], li2 E [K2] and a, E {0, 1], L E bgaaa for any such k h2 a, b, L. Indeed, representation isomorphism is given by "ka (T )-
{F, C). Moreover, it is easy to verify that pilvg a...b.
Note that we have the direct sum decomposition into orthogonal subspaces
R (F++C)) kE(Ki,,,,bE (..(......))..F...))
V
Let Pk k.o.b.L be the orthogonal projection upon V k.a.bLL Let T be an intertwining operator between Pi and p2. We can decompose T into the direct sum
T
E
a &n T PP k.a.bLL.
(6)
R.K' aa,a" "',',, L.,LL
By Schur's 's lemma (Lemma A. 10). the only nonzero components of (6) are those with a = d', = 6', L L'. Moreover, by Schur's lemma, the operator T a, == Pr only come from
k.a.b. Tp
k.a.b.L T.P.abb T Pr k.a.b.L
dimensional space of operators.
Next, we find these one dimensional spaces explicitly:
T1 V.,. u.u.F V......UFFFF
Ti(X) X IN.N X 1FF
T2: : V... + V.N.O.FFFF.
T2(X) = (x - -1NNN x) 1FF
T3 VEN.LOFF VENLLO.FF
Tx(X) = IN.N (X x x1
TA: VEM VELLLF,
T((X) IN.N X1FF
T3. V.N.D,CCC V.K.OOC
7:(Y) Y - INNN Y IcC.
To: V.N.IIC + V.K.D,1CC
To(Y) = (Y -INN Y) Ic.0
T: V.N.LO.. VEK.LOC.
T+YY) = IN.N (Y- -Y1c.)
Ts VEMLIC VEHLICC
TYY): = INNNYY.
Ta: V.N.DI,F VAK.OOCCC
Tx(X) X XIC
Tio: VEN.O.CCC + VE.KOLFF
TYo(Y) = Y
TE: V.M.L.IF + V.K.LLICC.
(x(() = 1N. X 1F.
Ti2: V.LLLICC + V.LFLLFFF
Ti2(Y) = 1N.N Y 11.F
It is easy see that each of the above transformation is representation isomorphism. Lastly, the set of transformations from Proposition 4.1 is a reparameterization of the above isomorphisms.
25

---

C Extended notations of TSNets
Definition C.I. Let state1, state2 {self, pool} and D, L (F.C). For bn S K1 N and
22 S K2 E N, denote by [Dstato Natutez, L)(() [NN((+C) 7 BNX(F+C)xK the operator, defined for (x, Y) E (XX(FFC)X by
K2
K1
(3) 11 (Dsater(())
Natataz(s)
((i)](61
T
and for any M/) + (k1, k2)
Natuce2 L ka) (x, Yega = (0,0).
[Dtatee
This is exactly the form stated in Proposition
in particular,
(X,, Y Yank
(IN.NX(
+ +x :.iks)
1FF + IN.N +x(1) widh
like
IN,N
(5)
IC,F,
minds
T2(,, Y) Dinka
(1) (1NNY
+ +x(2)
10c + +1N.N + ( kiikk
hike
Gink
[1NNN (6)
+ x 1
where for each i [6), x(1)
ki.k2 = 2ki=1
K1
X X
All ka and (1)
- Y Y. A(tt)) (646) k1.
For (X, Y) E ERNX(F+C) (i.e., Ki K2 1), the twelve building blocks read
[Faelf
Nocie FI(X, (X,0),
PPoOo Nouul,
Nosté,
(x
[Fselt Npool,
F](X, YY = (1N.NX,0))
[ pool
F)(X,Y) = (1N.N
[Cpoo)
Nealt,
F](X, Y) (Y VII,F,))
(Cpool
Nponl
FI(X, Y) M.N.NYIC,FF.
[Csell
Nacit,
C)(X,Y) Y),
[Cpool
Nocir, C)(X, y)= =00,000 1c,0),
Npaol
Npaol
[Cself
CI(X, = -0, -0,1,,,
[Cponl
C1(X,Y) (0,,l
[F /Pooo
Nanlt,
CI(X, (0, 1F.)),
F Pooo
Mpool
CI(X,Y) =N,,NN,N11.))
Interpretation of self and pool.
Self along an axis means "no aggregation" on that axis (identity action). E.g., Fsett keeps per-fcature structure; Neel keeps per-node structure.
Pool along axis means cuun-and-broadcan 1N.N pools over nodes and copies the node-sum to every node; right multiplication by 1 (resp. 1c,c) pools over features (resp. labels) and broadcasts to all features (resp. labels).
on that axis via 1: left multiplication by
*
-Cross-famill maps (F C or C' + F) necessarily use the corresponding all-ones bridge 1F,0 or 1c,F, hence require the source to be the "pool" state.
D Proof of Theorem
This section presents the proof of Theorem We describe relevant background and definitions in
Section D.I We then review results on symmetric polynomials in Section D.3 and extend them to
our setting triple symmetry Section D.4 The subsequent Section D.6 Section D.10 D.10 provides
supporting lemmas and approximation properties that play role in Theorem 4.3 In Sections D.11
D.12 we discuss properties of topological spaces required for the proof of Theorem Finally,
complete the proof of Theorem 4.3 in SectionD.iI D.13
26

---

Proof strategy. We prove Theorem 4.3 while avoiding the aforementioned caveat by closely utilizing the proof techniques introduced in 38] and [26]. Specifically, our proof idea can be decomposed into four high-level steps: (i) Characterization of (Sr x Sc)-invariant polynomials. is well established that any Sx-invariant polynomial can be represented as polynomials in the multisymmetric power-sum polynomials A 38 37]. We provide a non-trivial extension to richer symmetry setting by defining the doubly-symmetric polynomials (DMPs) (see Definition (e.in and showing that any p x --i-invariant polynomial, can be represented as polynomials in the DMPS (see Lemma D.S). (ii) Expressing (SN-1 x SF-1 x Sc)-invariant polynomials using DMPs. We adapt the techniques from Theorem of [26] and Lemma of [38] to use the DMPs introduced in (i) and the (SN x SF X Sc)-equivariant linear maps we derived in Equation (2) to express (Sx-1 X Sp-1 x )c) or (SN-1 Sp x (SN x Sp x -e)-eiiivrri polynomials. We extend Lemmas from [38] to show that the outputs of an (SN x Sy -equivvrra polynomial are (S x S Sc)- (Sx-1 X Sr Sc-1)- invariant. By leveraging the stronger symmetry structure provided by the permutation groups rather than their subgroups, we avoid the pitfall in Theorem 3 by [26] enabling the composition of cquivariant functions via invariant ones, which was also the goal of the flawed transition in [26]. as discussed above. (iv) Approximating (SN x Sc) Sc)-eqvivarian and Sp-invariant functions using TSNets. We replicate each intermediate step from (ii) and (iii), constructing approximators for the corresponding polynomial spaces using the (SN SF X Sc)-equivariant linear maps derived in Equation (2). and multi-layer perceptrons instantiated from the Universal Approximation Theorem (D.12) Finally, by incorporating the label projection map π as the final layer of our architecture, we enforce Sy-invariance and yield an approximator for the desired class of (Sw x -c)-eqvivarian and Sy-invariant functions, completing our construction for the riple-symmetry setting. A more detailed illustration, incorporating additional steps, is provided in Figure 4 with the complete proof detailed in Section D
polynomials. (iii) Composition of
Note that when labels are removed (i.e., C = 0), steps (ii) and (iii) recover a corrected but less general version of Theorem in 26 for H Sr, using techniques from 33 26
D.1 Background and Definitions
Norms. The Lso norm of a vector x E R- is defined to be ||~|| = max [æs]. The Loo (K)
norm of continuous function f K.- + RR.L over compact topological space K. is defined to be
|f = max [f=))
øek
We often denote in short Lo instead of (KC). Note that any continuous function over a compact domain I. has finite Loo (K) norm. We denote the space of all continuous functions over K. by Lo (IC)
Multivariate functions. Let X (X++C), We denote the first F columns by ( NXF and the last C' columns by (C) RNC and write X (X)F), (0)).
Let E NxD and let p : NND + RL For any / E [L].k E []], we denote by Pi, + R the (I, k) element of p(X). For any I E [L]. we denote by pt ::: NxD + R K the 1-th
N NND
XD
row of p( p(X). We call pr the K-dimensional feature vector corresponding to the i-th row of p(X), and write
(x( (p(X)) ((.)....))) p(()),,k) R
D.2 Restrictions of the triple-symmetric group representation
Consider the subgroup SN-1 x Sp-1 X Sc of the triplc-symmetric group. We define the action of Sw-1 X SF-1 x Sc on R (FF+CC by restricting the permutation OF E Sp-1 i to act only on the second to the F-th columns, and restricting the permutation N E Sy-1 1 to act only on last
In the literature the space of continuous functions over IC with the infinity norm is typically denoted by C(C).
27

---

(N 1)-th rows, keeping element (1,1) fixed. Namely,
X1,1
if 1 and 1,
X x11+0 111-11)
if 1 and j [F] [1].
X 1PPo0 ((-FF (j-F)
if 1 and [ [4],
((0x-1,0F1,,00) x)
X Itay's ( (n-1))11
if [N]] [1] and j 1,
X 1tay's (00-1),+o0++ 10-1)
if [N] [1] and j [F] [4],
X 1tay's (l--1),f-c (j-F) otherwise.
for all (0N-1, E SN-1 x Sr-1 Sc and X E ((((FF))
Similarly, the action of SN-1 SF Sc-1 R (x(4CC) is defined as follows. The permutation aC-1 E Sc-1 acts only on the last C - 1 label columns and the permutation 0N-1 E SN-1 acts act only last N - 1-th rows, keeping element (1, + +1) fixed. Namely,
((ON-1.0p.0--1) - X)n
X1,++1
if = and = -F+ 1, if n 1 and E [F+ +1,
X 11F+1toc-1U--e
X 11,0'00
if n 1 and E [4]]
X1to5' (nn (1+1)
if E [A] \ [1] and j j= F =F+1 1,
X 1toy' (m=1))P+1+dd (i-F-1)
if E [A] \ [4] and j [F + C] \ [F 1].
X 1tow' (m-1)),77())
otherwise,
for all (0N-1-09,0C-1) E SN x SF x Sc-1 and X E NN((FO)
By abuse of notation, for (aN, e) E SN Sr Sc, often denote in short ON (aN, e,e), and similarly denote or = (e, e), and oc = (c).
D.3 Symmetrie Polynomials
This subsection introduces key definitions and lemmas from symmetric polynomials and invariant theory that will be extended our setting of triple-symmetry in Section D.4
multi-index a with D E components is an element of No. where No is the set of non-negative integers. Given multi-index monomial xa == _ x.. and call ||a|]| == Σx Ond the degree of the monomial.
Polynomials.
No and (I1,' .D) E RD, define the
Definition D.1 (Polynomial Ring). A polynomial ring is set R of polynomials from IR_ to R invariant to the following operations: for all p,g E R and E IR
Addition. p + q E R,
Multiplication. pq E R.
Scalar multiplication. E R.
Equivalently, set A of polynomials R- - IR is ring if for every D E N, every Pl. PI.....P R. and every polynomial q R IR, we have ((pt,....pp) R.
Let R be ring of polynomials. A finite set of polynomials Pi.....PL C. Rs called a generating set for R if every polynomial in R can be expressed as a polynomial in Pi....,Pt PL with real coefficients.
Symmetry preserving polynomials.
Definition D.2 (Invariant functions). Let G be group that acts on R2d. A function p RR. DR. is called G-invariant if
plg x) p(x), Vg E G.
Definition D.3 (Equivariant functions). Let G be a group that acts on RRL, function p RLL RL is called G-equivariant if
p(g x) g p(x),
Vg G
28

---

We now define the power-sum multi- symmerrc polynomials, which form generating set for the ring of invariant polynomials to permutations.
Definition D.4 (Power-sum Multi-symmn symmetric Polynomials). Let M, Let T = (M+
and The
D
let {< be enumeration of all
(*) E No such that ||a power-sum multi-symmetric polynomials (PMP) {st)(=1 RN + R are defined by
M
N
(X)
X
The following well-known result from invariant theory shows that the PMPs are generating set for the ring of Sy invariant polynomials.
Lemma D.5 (Corollary 8.4 in B7) Letp: NND - be an Sy-livariannollynmiiaa with degree
M. Then, it can be written as a polynomial in the PMPs
p xX) = q((1 (.).......... ST (x)),
for some polynomial I8T + IR, where T (MM (MP)).
The following lemma enables the decomposition of polynomials that are Sx-r-invarian into combination of polynomials that are Sx-invariant. The lemma, originally stated as Lemma 2 in [38] had minor error in the summation index bounds, which we correct.
Lemma D.6 (Lemma 2 in (38). Let p: RNXD R be an S 18h--immu --invariant polynomial of degree M. Then, there exist S -ivvariann polynomials {ga RRDD + E SM such that
p(x)
Σ X Xa)
Here, runs over all multi-indices in No. of degree less equal to M.
D.4 Triple-yymmetric Polynomials
In this subsection, we extend the results on symmetric polynomials to our triple-symmetry setting. This extension provides us with the mathematical tools needed to show that: (1) any symmetry preserving continuous function over symmetric compact domains can be approximated by triple- symmetry preserving polynomials. (2) any symmetry preserving polynomial over symmetric compact domains can be approximated by TSNets. Together, these results establish the universality of TSNets under triple symmetry.
We now define the doubly power-sum multi-symmetric polynomials, which form a generating set for the ring (Sp x Scn-irrara polynomials g x(F+C) + R.
Definition D.7 (Doubly power-sum Multi symmetric Polynomials). Let M,N E N. Let (M+N)
and let (t) )T be an enumeration of all multi-indices (1)) E NN such that ||a (1) ||, S M. The
doubly power-sum multi-symmetric polynomials (DMPs) {s} Nx(FCC) RIT (0) Nx(+CF) R) are the polynomials
C
(X)
X of
and 8, (c) (X)
(a
F+c.
f=1
We next show that the DMPs form a generating set for the ring of (SF x -ivvarrt polynomials R. (CF+C) Theorem R. This is later employed the construction of the approximating neural networks in
We count the number of possible values by introducing slack variable aD+1 M -M O.. that E as M. The number of such non-negative integer solutions is cquivalent distributing M indistinguishable balls into D distinguishable bins, which yields (M+D) possibilities.
29

---

Lemma D.8. Letp RNX(FFC) + R be an SF x Sc-invariant polynomial of degree M. Then, can be written as a polynomial in the DMPs
p q(51 (X).
(F)
ST (F)
(X), (C) (X), (C)
) (X)).
for some polynomial q: R + R. where T N
Proof. Let p be an invariant polynomial of degree M as stated the lemma. Using the notation X PX x() E Nx(4C)) for a point in the domain of p. we freeze X(C) as a fixed parameter, and treat function only of (FF,, denoted by p x XN i.e.
p X
(X))
Note that xx is Sp-invariant polynomial RNXP R for every X ERNx.
The space of Sp-invariant polynomials over RNx of bounded degree is finite dimensional linear space, and therefore has a basis (bi with degree for each by at most M. Hence, we can write
( (X Σ ((
(8)
where the coefficients (c(()())) E R depend on X(O), By Equations and 88. we get
( Σ (x (C) (x((
(9)
1=1
where the coefficients {ai]==
R NxC + R must be polynomials of degree at most M in (C).
Let dg Sc. Since p is Sc-invariant, get
p(X) = ploc-pp000 X).
Namely,
L
Σ
cx (b) = Σ ciaac x(0))((X(())
1=1
1=1
Now, due to the fact that basis expansions unique, must have
WE [M), a (xx()))
aaca x(O)).
Hence, each {/ is an Sc-invariant polynomial.
As a result, by Lemma D.5 each {cr)/z can be written as polynomial v RT - in the multi-symmetric power-sum polynomials (PMPs) {silT= NNC - RR i.e.,
(O))) VI [L], where 7' = (M+N) Moreover, since by are Sf-invariant, by Lemma
a x (x) ur(s1 (()s1((X()) (X )
(10)
D.5 each {br) can also be i.c.
written as polynomial ii RTT + IR in the same PMPs {siTT
R
by x (F)) = in (x (x
ST (x
E [L].
(11)
By substituting Equations (10) and multi-symmetric polynomial.
into Equation
9 we deduce that p is doubly power-sum
Similarly to Lemma D.6. which enables the decomposition of Sy-r-invariant polynomials into combination of polynomials that are (Sp -ivvairai, the following lemma enables the decomposition of (Sp-1 x -in-iivriiant polynomials into a combination of polynomials that are (Sp -Sc)) -invariant.
30

---

Lemma D.9. Let (Nx((F+) + R be an (SF-1 ) invariint polynomial of degree M. Then, there exist Se x Sc-invariant polynomials {qx- : BR (FF+() + }1 such that
p(X)
Σ X (xx(
KI
Here, K. are multi-indeces in No.
Proof. Following Definition D.7 with respect to the the domain R [Nx((F-1)+C) we denote the doubly multi-symmetrie power-sum polynomials (DMPs) [Nx((F-1)+0) + R, taking the the variable Z E (RNxx((-1)-C),, by
F-1
C
(Z)
Σ F=1
Zo Sf
10
and
$ (0)
(2)
= Σ
F-1+e
c=1
where these polynomials are parameterized by t E T for T (M
Similarly, following Definition D.7 with respect to the the domain Nx++O)) we denote the DMPs which take the variable Y (xP+CC by
(Y) Σ
Y
to of and St (Y = Σ
yalt) F4
where these polynomials are parameterized by the same enumeration a1 No. f E [T]. as the R (x(((F-))+C) + IR DMPs. Now, note that for each t [T] we have
(F x+,+ (F) (X) x and ((0) (X 2..... X. x,c) = (0)
((0)(()) (X). (12)
Observe that we can expand the polynomial p(X) in X as
p(X) Σ
2 .......,,,,,,,,) X.r))),
(13)
where each Py: R NN + R is polynomial of degree at most M || Since derivatives commute with permutations, and specifically with the representation of Sp X Sc, any partial derivative of an (Sr-1 Sc)-invariant polynomial is also (Sr-1 -in--rrariant polynomial. Moreover, plugging X., = O into an (Sr-1 x Sc Ji)--nvariant polynomial u F + IR gives an (Sp-1 x Sc) -invariaaa polynomial u|x IR (F 1+C) + lR Hence, the polynomials
albil
2 x = H 7 ax, P) (0,0 2 X. 1l S M
are (Sp-1 x Sc)-invariant. Therefore, by Lemma D.8 each py can be expressed as a polynomial
ty 22T + IR in the DMPs (BNx((F-1)4C) + RR, i.c.
P- X ..... X x4c) &z (5(--1) ( 2, X xFC) ...,, (F-1) (X 2, x,
( 2, ... X ...,, (X x.o+)).
(C)
By Equation 12 Pry can be written as
Py (x- &z ( (7) 3
X
(s
x (x)())
ST
(F) (X) -x3
(14)
(x)))
We can now expand i in the right-hand-side of Equation
(4 in monomials of X and write
X. =
Σ
X.
17,6
ST (X),
(15)
[181|, ---1-wlll. lblll
88 (x)
(C)
31

---

where 9y,5 is an SF x Sc-invariant polynomial as it is polynomial in the Sp x Sc-invariant DMPs. When substituting Equation (15) into Equation
13
obtain
p(X)= Σ E
X1 By (8) (1
(F)
(X) 81
(0) (X)
1..,,1188 (x))
(0)
SM SMIIMMII Irll,
Now, by performing the change of variables 8 8= = K - 7,, have that
p(X) Σ
X
Σ Ibl ||--7ll No-7l1. SMM 1r1l
T (51 (x) -.. 8T (X),
(F)
(x)
(c)
M
(16)
Lastly, by denoting
(x(X)=
Σ
( T- 11 (1)
(X)... (P) (x), 10) (x) (C)
88
(x))
1b MM
1 7l1 SM 1.M--yll 7/h
Equation (66 can be written as
p(X) Σ X |I
Here, note that gre (X) are defined as linear combinations of the (Sp Sc)-invariant polynomials fy.n-7, so qre (X) are also (Sp x Sc)-invariant, concluding the proof.
Analogously, a similar lemma holds for (Sr Sc-n)-invariant polynomials.
Lemma D.10. Let p (xx+CCC) - IR be an (Sr x Sc Sc-1)-invariant polynomial with degree M. Then, there exist SF x Se-invariant polynomials {9x: NX(4FF) + +R]i S. such that
p(X)
Σ X (x
|Kl
D.5 Supporting Universal Approximation Properties
In this subsection, we present universal approximation properties that support the proof of the universal approximation result Theorem 4.3
First, we extend Lemma 4 from 338 which shows that continuous equivariant functions can be uniformly approximated by equivariant polynomials. Specifically, our extension generalizes the result from functions defined on the cube functions defined on arbitrary compact G-invariant subsets.
Lemma D.11. Let G S₁. Let K. C RL be compact domain such that K. UgeagK. Then the space of G-equivariant polynomials K. + R!, is dense in the space of continuous G-equivariant functions f K. + Re (X..
Proof. Let c > and let f K R be a continuous G-equivariant function. For each output coordinate fi IC + R, the classical Stone Weierstrass theorem guarantees the existence of polynomial pr R >> such that
If(() (X() S, for all X K.
Define the polynomial p R - R by
p x (x
VX ERR
To construct a G-equivariant approximating polynomial, introduce symmetrization of Define p: RL - R by
((X)
Σ
g p(g x).
G
gEG
32

---

Let X E R., Now, since f is G-equivariant, we have
llf(x) - x =
Σ g
(x) .X))
G
9EG
f(g p'g 1 xx S.
SEG
Thus, p is G-equivariant polynomial that uniformly approximates f. concluding the proof.
We mention the classical Universal Approximation Theorem (UAT) is later employed show universality in Lemma 4.2 which has a central role in the proof of Theorem D.14
Theorem D.12 (Universal Approximation Theorem (UAT) (22)). Let a R R be a continuous, non-polynomial function. Then, for every M, L N. compact K. S RRM continuous function
f RRL, and > O, there exist E N, W1 E RDM by E RDD and W2 E RLXD such that
sup ΦEK
W20 Wix+b:)ll
(17)
Note that since all finite dimensional norms equivalent, one can take any norm in
We next study universality with respect composition of functions. For that, first define universal approximation rigorously.
Definition D.13 (Universal Approximator). Let D1, D2 E A space of continuous functions N from a domain Q1 C Ps to domain Q2 C Ra is said be universal approximator another space of continuous functions B from Qı to Q2 ifr every f E B, every compact domain C. C IR such that C Q1, and every > there is function q E N such that for every C
[l((z) - q<x)le> <.
The following theorem is simple upproximation theoretic result.
Theorem D.14. Let L E N, and Dı.... DL+1 N. Let Ni be universal approximator of Bı for I E [L]. Let the domain of the functions B, be Qi C D: and the range be Q1+1 C. IR for E [L]. Consider the function spaces
N: = 10 o0..0..0 00 0 e E [4]}
and
: (fr of..... fi B, le [4]].
Then N is a universal approximator of B.
Proof. We prove this by induction on L.
Base case = 1. In this case N = Ni and B = Bi, so the claim follows directly from the assumption that Ni is universal approximator of B,.
Inductive Step. Assume the result holds for and consider a function
f= ft. ft-1
E B,
where fi E Bi. Let C1 C Q1 be compact and let E > 0. Define the compact set
Cy == (f--ff---... .... fi) C QL-
By continuity of fr on Qr and compactness of Cz, ft. is uniformly continuous Cz. Thus, there exists > 0 such that for all y, y' C₁ with [| - y'1l < 8, we have
llfz( - fo (v')l S 2
(18)
By the induction hypothesis, there exist 0 E N 01-1 E NN-1 such that sup [1 fi)(2) (0 0 8, =EC;
33

---

and by Equation 18
we get
[I (fr o 01. - zEC1
sup
(19)
Define the compact set Č₁ o.... 0, (C)). Define the compact set := := Cz. U Qr.
Since fg E B2 and N₂ a universal approximator of BL, there exists 02 E N2 such that
sup (y) (z)il E #EC
2'
which implies
(I o 0 o.... o() (02 o - o o... 01)(())] 8 2
sup #EC1
(20)
Define
= 01 f1-11111111111 o... 01. 01 By the triangle inequality
sup llf(x) ( 0(z)|1 sECi
sup [x (fL of 2..01 o.... 0.)((()) + (fz 0..
..... 0 0(x)l
zEć;
sup []((z) o1.0011-1 10..0-11........... 0.))
sup =ec
[l(fr o 00 0
(z) 0(x)
=ec;
and by Equations
19 and 220).
we get
sup ((z))-((=]]] - E + = E.
sEC;
2
This completes the induction step and the proof.
D.6 Supporting Lemmas for G-descriptors
In this subsection, we introduce a special class of G-invariant polynomials, which are called G- descriptors. These polynomials are designed to distinguish between different orbits under the action of subgroup s S of the symmetric group. We establish the existence of (Sp-1 Sc deeecriiptss and -1 -eeccripoos which we later use to express (Sx-1 X SF-1 Sc) -in-irvarinnt polynomials defined over a symmetric compact domain.
Given a subgroup of the symmetric group, we next define the notion of G-descriptor. Roughly speaking, G-descriptor is polynomial that maps different orbits under the representation of G to different values.
Definition D.15 (G-descriptor). Let G S. SM act on MD be changing the order of the rows, and let K. C MXD such that K. UgEagK, We call G-invariant function K.C. + R& G-descriptor,
it satisfies
XX, Y E K, g(X) qY) + 3g G: = X.
Next, we cite Lemma 3 from 226 which shows the existence of descriptor given subgroup of the symmetric group
Lemma D.16 (Lemma 3 in (26).. Let G < SM act MDD by changing the order of the rows. Then, there exists N and a polynomial G-descriptor u. MxD + R..
D.7 Expressing G-Polynomial Descriptors Using Symmetric Polynomials
In the proof of Lemma D.24 we define polynomial descriptors. We then show that these descriptors can be written using symmetric polynomials, which then allows approximating them by TSNets. In this subsection, we show how certain polynomials descriptors can be written using symmetric polynomials.
We first define basic operations related to the constriction of symmetric polynomials.
Definition D.17. Let K. M, D E N, let T = TM.D = -M++) (i.e., the number of monomials in RD up to degree M), and let {a!0 Ji= be enumeration of all multi-indices (!) E No such that [0( < M.
34

---

The mapping clM.D) :RD - R. is the function that calculates all monomials up to degree T, namely, for D R
(...)) = (Da Da ,...,Daar))
(21)
The mapping b(K,M.D) RR R is defined by
vj E
[ V VER TxRD B(K.M.D) (V),; = M.. (V,))
(22)
The mapping (KK.M.D) TPM
RxTT - R is defined, for E E RRXXT by
(KM,D)) PMP
E
Ek:-.
(23)
For F,C. N such that F + C K, the mapping DMP
(F-C.M.D)
((F+C)T
RTT is
defined, for H E (IF+0)XT, by
F
C
DMP
(F+C,M.D)
(H) (H)
Σ
#tta).
(24)
f=1
Remark D.18. Note that IMP
(K. (.K.M. is the mapping that computes the sequence of all (FDC, M,D, computes the sequence of all DMPs up
PMPs up degree M. Similarly, DMP degree M.
Lemma D.19. Let K, M, MEDENN and TMr -M
1. Let q: KXD R be an Sk-1--olynomial descriptor of degree M, namely,
VZ,Y K (1(Z)= = -x())) = ( SK-1 Z =K--1 r).
Then, there exist polynomials Ug RT - RR,, parameterized by B E Zg, such that for V E RRXD
((V) = Σ Vi.Wa(V),
11811,5M
where
(K.MD)) ((K.M.D) pPm
Wa Ug
2. Let F,C E such that + +C = K. Let (F+0)D + Rs be (Sp-1 x Sc)- polynomial descriptor of degree M, namely, VZ, Y E (((+C))D
((Z)=1(X))
$
(3(FF-1,00) SF-1 Sc Z (0F-1,00). -Y)
Then, there exist polynomials U3 22 + RL, parameterized by B 2g such that for V E (F+C))D
q(V) Σ vf.Wo(V).
|M
where
(F+C.M.D) W3 Ug & (tl.ii).__PPP... ((F+C,M,D)
The result is also immediately true when transposing the order of F and C.
35

---

Proof. We prove 1, and note that 2 is shown analogously.
Recall the property defining the polynomial q: RRXD - RL
Z2 Y E
((z))=(()) = (JøK-1 : OK-1.
Fix / E [L] and consider the (-th output dimension of q. namely RXxD - R. By Lemma D.6
the SK -nnvariant polynomial qi can be expressed
(v)
Σ VL. VV,,,,(V),
(25)
|| ISM
where Wr, R + IR are Sx-invariant polynomials with degree most M, and / E No are multi-indices with || S M. Next, we express (5) using PMPs (Definition D.4). The power-sum
multi-symmetric polynomials (PMPs) 8 : RKXD
map the variable V E RRXD
K
V
R
k=1
where these polynomials are indexed by E [T], in order to enumerate all multi-indices (!) E No such that (*)] < MM Fix B No with || I M. By Lemma the Sx-invariant polynomial 3 of 25) can be expressed polynomial Wr R + R in the PMPs {st) by
mn V) u1 (81 (V) .....,., ST()).
(26)
By Remark D.18 we can write wr. as a composition of the three mappings
(K,,D)) ((K,M.D) PPP
(27)
(K.M.D) ((K.M.D) is the mapping that computes the sequence all PMPs (see Definition where 4PP
D.17p.
We next express q via the above construction.
Define U3 R - RR,, by
VI [Z]
(Us), = 41,9
(28)
and similarly define Wa RRXD
R4 by
Vl E [L]
(Ws); w1,9-
(29)
Now, using Equations 27 to 29
that Wa can be written as the composition
Wi Ug 1PMP
(K.M.) ((K,M.))
and by Equation 25 we have
(VV) Σ VV,,,(V),
|M
which shows 1. To prove 2, we use Lemma instead of Lemma D.6 and follow an analogous construction.
D.8
The Exclusion Set
As part of the proof that TSNets are universal approximators continuous functions over symmetric compact domains (see Theorem 4.3 we need to define a descriptor that is injective on group orbits descriptor should assign same value to inputs in the same orbit and different values otherwise. However, this injectivity can fail on small subset of the domain. To still guarantee injectivity, we exclude this small subset from the domain of definition and refer to as the exclusion set. This exclusion set has specific form, as defined next.
36

---

Definition D.20 (The exclusion set), The set
N
N
3 U
E (FF4C)
Xnnii
Xn,fa U
n=1
N
X Xn, JU
U
XERNX(FOC)
X xF,F+a = Σ
R=1
n=1
F+C
F+C
U
X XERNX(FFC)
Σ
Xmij
X
1smi 1gni<nash S
j=1
is called the exclusion set corresponding to R (X(F4C)
The exclusion set a finite union of linear subspaces of co-dimension one. We consider input matrices X E (R+*x(FO),, where (F) correspond to continuous real-valued features and X()) encode one-hot vectors with entries in {0, 1). assigning probability one to exactly to the others in each row. The real-valued features (F) vary continuously in E The set of features that lie inside the exclusion set & is meagre with respect to the standard topology of the feature space (more specifically, it is nowhere dense). Hence, being outside & is the generic case in the topological sense. From a probabilistic perspective, if the features are sampled from a joint distribution that is continuous with respect to the Lebesgue measure (in the Madon-Nikodym sense), then the features belong to (X(F) X E E in probability zero. Hence, for the features to belong to is an event that almost surely does not occur. With regard to the labels, the exclusion set & rules out the special scenario in which multiple classes have exactly the same number of examples. If labels are samples from a reasonable joint probability space, where labels are not constrained to be exactly balanced, such an typically occurs in low probability. To summarize, from both the feature and label perspectives, the data typically lies outside the exclusion set ε, and hence considering a domain IC disjoint from & is reasonable. A similar philosophy regarding exclusion set is adopted by (26].
class and zero
D.9 TSNets With Output Projected to 11, and (L, 1)
To prove that our invariant neural networks TSNet1 are universal approximators of symmetry pre- serving continuous functions, we first prove that TSNetg, is universal approximator of equivariant continuous function. For that, we first define spaces neural network which are TSNeteq with outputs restricted to the entries (1, and (1, + 1).
Definition D.21 (The (F) TSNett (NF) and TSNe Architectures).
(F) is any MLP 8 : (KTN(((FC)) BNK of the following form. There exists a TSNefg & (FGXN + RRINNX(F+O) such that for every (X,Y) R KKXXXX(F+C)
0X,Y) (6(X,Y))
TSNe is any MLP XNX(P()+ + N such that there exists a TSNetEa Φ RKIXX((F+C) - (K such that
0 (X (6(X))) 1..F1
Similarly, TSNet (NF) is any MLP 0 (RINX((FFO) K2 such that
0 Y) = (o(X,
and [SNe (C)) is any MLP 0 xKXXX((FFC + Kz such that
0XX ()((x 1.
Note that (F) are invariant to (aN X xac), (F) to (aN X xoc-1), (NF) to (aN-1 OF-1 oc), and (NC) to (oN-1 oF oc-1).
37

---

Remark D.22. The entries [:, 1, are special for F)) and break the SN and Sy symmetries. Indeed, all "self" transformations in the last linear layer of a TSNeilNr) can be written in terms of [:, 1, 11, e.g,,
FI 11,1= 1111. Similarly, the entires 1, + 1] are special for (S) li,i for TSNetlF), and [i F + 1] for (S)
Naait
Given two networks, ((NF) E (SNN((NF) and ((NC) E TSNet (NC), one can recover a corresponding TSNeteq as follows.
Lemma D.23.
The MLP is a TSNeTEa if and only if there is a FFN ((F) and a TSNe( g(C) such that
[F] ((X = ((NF) (e, (1f),e) (x,)))))))X))))
and
Vc E [C]: 0(X, ) F4. = (lNO) (e, (le)) (x, Y)),
for (1f) E SF (the permutation that swaps only with f) and (1c) E Sc.
The MLP is a TSNetgg if and only if there a (F) g(NF) and a NC) g(nc) such that
Vn
) ((NF) ((N)) (X, Y))
and
Vn E [N] [C]:
Fn. im, ((1 .
for (Im) E Sx. (Lf) Sp, and (1c) E Sc.
Proof. We prove 2, and note that I is analogous. Suppose that 0 is defined via the above formulas given ((NF) (Ø(-))., 1,1 in (NN and ((NC) = (1+-)) in (NC) For any n E [N]
and f E [P] we have
0(X, ((X,)),, y) ((NF) ((In)) (x, ((((())))(1))) (X, (x, Y))
:111
= -((In), 5 Y) 1,1,1 = o(X Y) wn.f
Hence, 8(-)..1:F = .(-)..1::: (X + R. so .(.......F is equivariant to ON x OF x (e} 1
and invariant to {e} x {e} x oc. Similarly, 0()...411:4C = v)..... Nxx + NxF is equivariant to ON x fet x op and invariant to {e} x SF x {e). Together, 0 is equivariant to Sy x Sp Sc.
The other direction is trivial by taking ((NF) = (0(-) TSNNe (NF) and ((NC) = =((()) 11,44 E (NC).
D.10 Existence of Nx(4CC) E descriptors that can be approximated by (SNett(NF)) and (NC)
The key step in the proof of the universal approximation theorem Lemma 4.2 is constructing polynomial descriptor that can be approximated by TSNets. The following lemma established this.
Lemma D.24. Let N, F, C N and consider the triple-symmetric group SN x SP x Se and its standard representation in (FF+C) and restrictions to SN-1 x SN-1xSF-1X Sc and S x Sc_ (see Subsecction D.2). Let E be the exclusion set corresponding to ((F+C) (Definition D.20 Then, there exist E and two spaces B(NF) F) and B(NC) of polynomials from N
to TR. such that FF is a universal approximator of B(NF) and (NC) approximator of B(C), with the following two properties.
universal
38

---

1. There exists an in B(NF).
descriptor Q(NF), ( (BMX(P-()()) + +R.
2. There exists an Sx-1XSp x 1 descriptor Q(NC), (RNx(P-0) : +R in B(NC).
Note that, for example, 1. of Lemma D.24 means that VZ,Y E \E:
Q(NF) ( (Y)
$
(30)
((NN-1,0F-1,0) E SN-1 x Sr-1 Sc: Y (0-N,11,0--1,00 Z.
Proof of of Lemma D.24 We prove 1. of Lemma D.24 and note that the proof of 2. is analogous.
(1) A (Sp-1 x -c)-descriptor Q(7). By Lemma D.16 there exists an SF-1 x Sc-polynomial descriptor (see Definition D.15) ol ((++))x + Le with degree Mp, namely, a polynomial such that
AZ,Y Y (F(4)))2
(31)
(Z) = (3() E Sp-1 x So Z = (0F-1100) x).
We define polynomial Q(=); ( 1 E R-NLE follows. Given X E RNNX(F+C) E
the polynomial is defined by taking the row vector ΣN X,, E PRCC and appending it to each row of X forming a new dimension and creating the intermediate tensor
x= X,1N Σ ENX
(32)
To define Q(F), the function (F) then applied on X via
Vn E [N], (X) )n = (F) (F Σx.I)
(33)
By construction, this makes ((F) an SN-equivariant polynomial. Note that given a permutation (ar-1.0c) E S x Sc, for every Z,Y Y E (F+(CF we have
Vn Zn, = (OF-1,0C) Ym.))
N Z, 1N Σ
N
+ (vn:
Zs:
(OF-1,0)). Y. (OF-1,00) 1y
Σ
Y.:
i=1
ni::
1=1
VYn Znait (0F-1.0C) Pmni))
Thus, obtained that
(Vn: Zn, = (OF-1, .Y..) + (Vn: En,, = (oF-1,0)) -opooc--iiiii Knai).
(34)
We now prove that ((F) is an Sx-equivariant polynomial that satisfies
Yz,Y E R. Nx(+F() E
(35)
(Z()(2)= = (F(o--1, E Sp-1 Se Y = (or-1, .z)
Assume there exists (0F-1,0c) E Sp-1 x Sc, such that Y = (aF-1.0c) Z E (F+ By definition, the action of (oF-1, permutes the columns of Z identically across all rows, namely,
Direction + of Equation
35
Vn [N] Yn.: = =0F=1,,0)) Zn.:
39

---

and by Equation 34
Vn [N]
Yu..: :0.=00r0 -00-1,,00)) Zmn..
(36)
By Equations and 36) we obtain
Vn E [N]
- and by the definition of Q(F) ) in Equation 33p. we have that (X)
Direction = of Equation (35). We now show the opposite direction. Assume that Q)) =
()) (Z) for some Y,Z (xx((+)) &. By the definition of Q(F) Equation 33 we have that
Vn E E [N]: qIP) q ( (n..)))
and by Equation 31, the equality implies the existence a permutation (o for each n [M]. such that
(0F-1:0))) (m)) E SF-1 x Sc
Yn..: F0 Zmaan
(16) (x))
(x))
(37)
Next, we would like to show that
Vn,, n2 [N]
FFF-1. 0c
(mx)
(ma) ((n))) (0
For that, consider two indices Ii * n2 E [N]. By Equation (37) and the definition of 2 and Y (Equation (32). we get
N 1N Y = (0p-1: (n1)) 1N
N D
N
(1x)
Σ i=1
Zt and 1N
Yr. = (op-1. ((m))))))))) 1N > Z. (38)
(o())
(2s) (maa)
i=1
i=1
Since 1N > Zi has equal rows (and so does 1N Em Yo ) and SF-1 x Sc permutes all
columns simultaneously, Equation 38 can be written as
N
(m) (o 1oF-1: of (mi))
(ma) (12) Zz - (o (OF-1:0
Σ Zs:
(39)
Recall that Y. Z E NX(+CO) \ E. Hence the first F entries of Σ Y,. and Σ Z each have F distinct elements. Moreover, the last entries of N distinct elements. Therefore, the only way that Equation (39 holds is when OF Op and
Li Y., and Σ Ze each have C
(mi) (mz)
(m1) (m2) Thus, all row-wise permutations coincide, i.e.
(0)-n,oc) E SF-1 Sc, Vi [N]:
(o2_1110) (ar-noo))
and consequently by Equations
34 and 37
Vi E []
Y, (oF-1, Zi:-
Thus, Q(P): : NX(4F) R NxLe is an Sy equeiivrri polynomial that satisfies Equation (35).
Similarly, by Lemma D.16 there exists an SF x Sc-r-polynomial descriptor (()), (BF+C))2 +
Ree with degree Mc. namely, a polynomial such that
VZ,Y Y E (F+C)x2
- (3(0F)0c-1) E Sc-1: Z = (OF, -Y).
We define a polynomial (()) Nx(++O) E NxLe similarly to Q(0). Given X
Nx(+FC) E, form the intermediate tensor, in Equation 32
x X,1N Cx..EEMXXPHXX
1=1
To define Q19), the function (0) is then applied on X via
N
En [N], (1)) == & (0) (X.,.). (0) (()) Σ X..)).
(40)
i=1
40

---

Then Q( is an SN equivvarii polynomial that satisfies the analogue of Equation (35
AZ, Y R RRNx(F+)) : (0))=000010 + (3(0F, E Sp Sc-1: Y (cF, -2))
(2) A (SN-1 x SF-1 x -c)-drrcriptor Q(NF), By Lemma D.16 there exists an Sx-1 innvarian polynomial (M)) I x3 + LN of degree My. such that
YZ,Y
(2) = (v)) = E Z == (41)
We define polynomial Q(NF); (RNX((+O) 1 RLNXLr where Lp is the output dimension of the polynomial descriptor (1)) given in Equation (1), p. as follows. Given an input X E (=Nx(F+O)) (E,
the output ((NF)((())))))) (X) is defined via the following composition of computations.
(i Compute
E RXLFF as defined in Equation 33
(ii) Consider the column vectors Σラ X, E R.W and De vectors to QF forming new dimension. Namely, construct the intermediate tensor
ccml F RRV Append these
C l
x = (x), Σ
1 L.p
(42)
f=1
(iii) Apply the function (N) X to define ((NF) (X) via
e [Lp]: (NF)) X) ) = (N) (..).))
(43)
(IQ (X)
X
X roo) ER'x.
By construction, Q(NF) a polynomial from R Nx(++)) \ to RLNXLE We now prove that Q(NF)
satisfies Y E (N((FF)) \E
QINF) Q((NF)
(44)
F(oN-1,FF-1,0)) SN-1 x SF So: Y 00 Z.
Direction of Equation 44 Let Y. E Nx(+FO) E. Suppose there exists
(0N-1.0F-1.08 oc) E SN-1 x SF-1 So such that Y = (0N-1. Z. Recall that
QLF) is Sx-equivariant. This, together with Equation 35 gives
vi E [Tr]:
())) (ONN (e. Z)
(45)
= ON-- ((e 2) = ON-1 (Z),.
(Z)...
Substituting Equation (45) into the definition of Y Equation (42). we get
F I Ex.ll
Y = -ON-1 (Z)
f=1
Since Y (ax (0N-1,0F_1,00) Z, and by the fact that summation is invariant the permutations OF-1 and ac, we obtain
F
C 1 LE Σ
Y = = (C
Σ
Z
T. ON-1 Z.
f=1 c=l
41

---

Hence, by Equation 41
VI [LF]
q ( 1.) q (/) a.))) (Y) - (I)
and by the definition of Q(NF) in Equation (43 we obtain Q(PP))))))))))))
Direction I of Equation 44 We now show the opposite direction. Let Y, Z E RNx(F+C) \ E,
and assume that Q that
Z (()
By the definition of Q(NF) in Equation (3). we have
vl E [Lp]:
g
(Z..)) q¹ (N) (Y...).
By Equation (1). , this equality implies the existence of permutation (1) I E [Tp)), such that
N-1 SN-1, for each
Y. = NN1 Z...-
(46)
Next, we would like to show that
11, E [Lr]]
(12) NN = o --
(11)
For that, consider two indices 1 * l/ E [L ]. By Equation (46). and by the definition of Ž and Y (Equation (42) ) get, for j = 1,2,
Σ I = -N (1)) 1=1
I. and EX. - ZZ (47)
/=1
Note that Σ/=1 1, has equal columns (or rows consisting of scalar times 1 1.g)) and so (1))
does 2 Z, F Lp The same property holds also for (1)) ON Σ5m Z. and ON
DE 1 hpp for = 1,2. Moreover, since SF x Sc permutes all rows simultaneously,
Equation (47) is equivalent to
C Σ
NN-
(1))
Σ Z o
(22 N-1
(1) Σ Z and 0N 1=1
Z. -o
ON-1
(12)
Z
F+c
(48)
1=1
c=1
Recall that Y, E &RAX(EFC))E Hence E/E Y.
Ep= Z c=1 Y.r+c and EC Z.r+e.
each have N distinct elements. Therefore the only way that Equation (48) holds when all col- min-wise permutations coincide, i.e.,
N 1--1ESN-- SN-1 [
x = ON-1
and by Equation (46)
W (T), = - ( (Z))
Recall that (PF) is SN Sx-equivariant, so
( = -0x-1-(((Z( (2) (())) (aN- Z).
Hence, by Equation 35
A(F-11,0C) SF-1 Sc: Y = (0x-1;0r-1,0c) 2.
Thus, Q(NF), (N(+F)) A Ly Ly satisfies Equation 44
Similarly, we define a polynomial Q( RN NX(+F)) \ E R x follows. Given input
X R x the output Q (x) is defined via the following composition of computations.
(i) Compute (X) E PBNxLe Lo as defined in Equation 440
(ii Consider the column vectors Σラ=1 - E R and EC X. RV Append these vectors to (X( forming new dimension. Namely, construct the intermediate tensor
C T.. Σ x == (X), Σ x
(X),
X g. xLxx3
f=1
42

---

(iii) Apply the function gN on X to define Q(NC)) (X) via
E [Lc]: Q(NC) (X):11 = 9 g(x) (X.1.:)
d = (IQ
X x ER E
f=1
Then Q(NC) satisfies the analogue of Equation
(44 i.e. AZ, Y E ERAX(PHO) E
Q Q 2 (Y)
OF,, E SN-1 x SF x Sc-1: Y = 00,-,1)))) Z.
(3) Expressing o (F), (0) and q(N) using DMPs and PMPs.
Let TF TM = ( Since g(F), g( + RLr is an (SF-1 -oolnooyol de- scriptor of degree Mr, by Lemma D.19 there exist polynomials U/² g RLr, parameterized
by B E zg. such that for V E RFFFC
(V)
E V. (V),
(49)
MM
where
w (/ (F+ b ((F+t.
(50)
Similarly, there exist polynomials U/ 2T +R RLy such that
(V)= Σ (
B
SMP
where
W : v/ (F+C. b (FF+,,M..2)
DMP
Lastly, for Tv ( (M++3) there exist polynomials U!N) RN RM parameterized by such that for V E IR Nx
Z
(V) Σ
Vi. W (N) (V), B
(51)
|1 SM
where
W B
U(N)
PMP o (N,,,,
(N.
(52)
(4) Approximating (FF) using (F), Next, we show how to approximate ((F) by (FN via a composition of approximations of the components of QIF)
(4.1) The space of polynomials B1 and MIPPs Mi. Note that (M, :R + TF of Definition D.17 belongs to the space B, of all polynomials from R2 to RTr By the Universal Approximation Theorem (Theorem 12 the space M1 of multilayer perceptrons (MLPs) from R RT is universal approximator of B).
(4.2) The space of polynomials By, The polynomial (F++C, .2) applies (MF))) row-wise (see Definition D.17 and belongs to the space B, of all polynomials = (R(F-C)2 + R(F+C)XTr of the form
v(VP.((.) for arbitrary polynomial y E B1.
The space of MLPs Ag. We define corresponding space Nr, of MLPs from (F+CC)x2 to xF++C)xTF in which each function E N₁ is of the form 2(V) := (V(V..).... e (VF+c.)) where i E AG as defined in (4.1). It easy to see that N₁ is a universal approximator of B,, Indeed, let <VV) = (v(V..))..... VF++..)) be a polynomial in B, restricted to a compact domain C' C IR( x and let e > O. The domain C is contained in a larger compact domain of the form
= C' x....Xx CC,
43

---

where C" C 2 is compact. Now, note that y is extended uniquely to a polynomial C' - R Hence, since Ni is a universal approximator of B y can be uniformly approximated by some E Ni over the compact domain C", up to error As result, is uniformly approximated by (VV ii........... ................................ (.(.))......((((C(...... (VF+c.,)) up to enror over Ć. Lastly, since C' C C. is uniformly approximated by 2 up to also in C.
(M (( + RRT of (4.3) The space of linear mappings N₁. The transformation DMP
Definition D.17 belongs the space NG of linear mappings spanned by the two linear mappings
[F [Fum]]
IR [
+ R [Fum (X, Y)- (X1F,0)
(53)
and
[Csum]
R (F+0))TT= - RTT,, [Csum] (x, = (0, Y1c).
(54)
Trivially, N₁ is a universal approximator of itself.
(4.4) The space of polynomials B,, and MLPs No. Consider the polynomial U(F), R2Tr RTExLE defined by
U(F) = -U) 22 + +RL MM,
(55)
The mapping U(F) belongs to the space B, of all polynomials from R to R2xL,, By the Universal Approximation Theorem (Theorem D.12) the space Na of multilayer perceptrons (MLPs) from 22 to TR is a universal approximator of Bu-
(4.5) The space of polynomials B and MLPs Wa. Define the polynomial W(F), (FF4))x2 Te by
W -WW()) 11
and note that by (50) we have
((F) (FF) (F+C.Mp.2) ((F+C,M..))
DMP
(56)
Define the space of MLPs 0)2- RT
N (0. 00 0g, 02 No, 02 NN, NN).
By Theorem D.14 and the above derivation, the space of MLPs No is a universal approximator of the space of polynomial R (F+0)x2 + R
B == (fo o Sa E Bu, E No, E B.}.
Moreover, by (56) have ((F) Bw
(4.6) The space of polynomials Bp. Next, we construct a space By of polynomials from (NF(F-)) to NxLF and show that Q(F) E BF. A general function from the space By is defined constructively as follows. Given an input X E Nx(+FF) E, we first compute its row-wise sum ΣN X and append it to new dimension of X, creating tensor V E (x(+C)) via
Vn E [N] Vn,..
nL. Σ X..).
Note that this step is a TSNetEş. Next, for some Y N (which can be any value from N), we define for each multi-index B with || < Y, polynomial Rg E B,, (Rig can be any function from B..)) We then apply Rg row-wise on each Vn.... and multiply it by V Vaja to create the following array in Le
Σ
Re(V...))
NE(N]
| SY
Consequently, by Equations (32) and
33
and
49
((F) E BF.
The space of MIPs Ng. We now define a corresponding space of MLPs from R Nx(+OO) \ R NN I. that we denote by Nrr, as follows. Given an input X E IR (F++C), first compute its row- wise sum Σi= X,, and append it to new dimension of X, creating the tensor V Nx defined by
Vn E [N] VALL
X
44

---

This step is TSNetEq. Next, we apply on Va.ja. for each n E [N] and j E [F + C.. any sequence of general MLPs 02 IR² + IR, E [L] for some I. E N. Again, this computation still a TSNetEq Then, apply the same general MLP Ç E No on Vn,,, for all MLP K R + R on each (0r v.......)... S(..)) and sum over / to obtain
[N]. Lastly, we apply any general
(VV. nE[N]
n,1,: and RØ( Vna:)) by an MLP x. : I2 + E, since we can approximate monomials V.l by MLPs R² + R. and since we can approximate polynomials from B by MLPs from Nw, the above space WE is universal approximator of Bp. Moreover, by construction, the space WF consists only of (SN
Since we can approximate the function that takes the product of two imput numbers (for us V
(5) Approximating ((FF) using TSNet". Next, we show how approximate ((NF) by (N) via composition of approximations of the components of Q(NE).
(5.1) The space of polynomials B Note that c(M,,3)) R + RTx of Definition D.17 belongs
to the space B B(N) of all polynomials from R to RT,,, By the Universal Approximation Theorem (Theorem D.12p. , the space M/(A) of multilayer perceptrons (MLPs) from RR to RTv is a universal approximator of B(7)
(5.2) The space of polynomials B/ The polynomial (NN.Mx.3 3) applies e! Mx. row-wise (see Definition D.17 and belongs the space BB of all polynomials RR-x3 R.NTTN of the form 2(V) =
(VN..)) for an arbitrary polynomial B(()
The space of MLPs M/M We define corresponding space No of MLPs from RNx3 to R NXTTN in which each function & E A, is of the form =(V) == (O(V..), i (V...)) where ÿ E A((A) as defined in (5.1). It is easy to see that N,(,) is a universal approximator of B( Indeed, let z(V)= = (v(V,.)...... (VV,.))) (T be polynomial in ( restricted to a compact domain C' c IR xx3 and let e >> O. The domain C is contained in larger compact domain of the form
Ò C ...... C
where C C 123 is compact. Now, note that y is extended uniquely to a polynomial y C' - IRT. Hence, since x(()) is universal approximator of B(A², can be uniformly approximated by some y A/(N) over the compact domain C", up to error e. As result, = is uniformly approximated by =(V) = (V(V.,),... j( ((vx.)) up to error c over Ć. Lastly, since C c Ć. z is uniformly approximated by à up to also in C.
(5.3) The space of linear mappings AN(N). The transformation (N. NxTx TR of
(PMP Definition D.17 belongs to the space (N) of linear mappings spanned by the linear mapping
[Naum] R NxTx RR,,, [Noum] (XX X1N.
(57)
Trivially, !! is universal approximator of itself.
(5.4) The space polynomials B and MIPs AdN) Consider the polynomial U(N) Rx - Lx defined by
(NN) (U(N) RTv RL a
(58)
The mapping (N) belongs to the space B. B(N) of all polynomials from TT to RTvLL,, By the Universal Approximation Theorem (Theorem D.12 the space MV) of multilayer perceptrons (MLPs)
from TN to RXXXLN is universal approximator of B!N)
(5.5) The space of polynomials B and MILPs.CCM Define the polynomial W(N) Nx3 R xN by
(N) h
45

---

and note that by (22 we have
W(N) U(M)
(N. bb(N.Mx..). PMP
(59)
Define the space of MLPs R Nx3 - RUNNLY
M(N) (On 0g 0s On EN 0s E NNT 00 E N
By Theorem D.14 and the above derivation, the space MLPs ( universal approximator for the space of polynomial R xx R x
B (fu fo fo fa B , e B, fo e }.
Moreover, by (59 we have W(N) E (N)
(5.6) The space of polynomials BNF. Next, construct space By of polynomials from R (NX(F+C) \ & to R1xxLr and show that Q(NF) BNF. A general function from the space BNF defined constructively as follows. Given an input X E R ERN ((F+C) E, we first apply polynomial E Bp on and compute the sums Σ X., and E X.F++. The sums Σド=1 X and E F.t then appended new dimension of E(X), creating tensor Z R via
WI E [Tr]: Z,, (X 1,
X [x+te)
Note that this step is TSNe Next, for some Y E N (which can be any value from N), define for each multi-index ,3 with || < Y, a polynomial G3 E B! (Gg can be any function from B)) We then apply Gg column-wiss wise on each Z.,., and multiply by z ".d.:" create the following array in RLxxLe
Σ
|| SY
Consequently, by Equations (42) and 43 and
51
Q(FF) BNF.
The space of MIPs NN... We now define corresponding space of MLPs from R RNx(FFC) \ to TR. LF that we denote by NNF, as follows. Given an input X E Nx((FF) E, we first apply a polynomials E E Bp X and compute the sums Σ/= X and DE F.F The sums Σ f=1 X. and >e F+c then appended
dimension of E(X), creating tensor
Z E x via
AI WE [ Z.I. = (E(X) J.
Σ X X. x+c]-
This step is TSNetEqui- Next, we apply on Zn,t.; for each n E [N] and E [Lp], any sequence of general MLPs 0, IR3 + TR, i [7] for some I E N. Again, this computation is still TSNet
Then, apply the same general MLP Č E (())) on Z.,, for all | E [Lg]. Lastly, we apply any general MLP R R + R on each (2. (Z...) and sum over to obtain
Σ R(0 (VV. LeeLL)
Since we can approximate the function that takes the product of two input numbers (for us Z and Eg (.))) by an MLP R I22 since we can approximate monomials Vi. by MLPs g R. and since we can approximate polynomials from ((x) by MLPs from Av((), the above space N
is universal approximator of Byg. Moreover, by construction, the space Wyp consists only of (NN)ts(NF))
46

---

D.11 Topological Spaces
In mathematics, one often formulates the most general setting under which certain property can be analyzed. The most general setting for defining and analyzing continuous functions is (point-ser) topology. In topology, all notions related to continuity are defined by axiomatically formulating the notion of open sets. This generalizes the concept of continuity metric spaces. A topological space is a set B with a set of subsets B C 2 called the open sets, or the topology, which satisfy some list of axioms: the empty set is open (0 E B), any finite infinite union of open sets in open, and the intersection of any finite number of open sets in open. The complement of an open set is called closed.
defined for functions between
mapping f B + R. between two topologiaal spaces B and R called continuous if the preimage [R) == {b E B l(b) RJ C B of every open set R C R. is open. Equivalently, f is continuous if and only if (R) is closed whenever R C R is closed. The mapping f is called open if fBB) C R is open whenever B C B is open. A continuous open bijection is called homeomorphism. Two topological spaces are called homcomorphic there is a homeomorphism between them. Two homeomorphie spaces are interpreted "essentially the same" in the context of topology, as they share all topological properties, like continuity of functions and compactness.
In the standard topology of IR D, the open sets are exactly those sets B C R such that for every E there is an open ball C C RB" (with respect to the standard Euclidean metric) such that E C C B. Under this topology. the classical notion of continuity from calculus is equivalent to the topological notion of continuity. More generally, every metric space has a canonical topology associated with it, defined as above, with the open balls defined with respect to the metric.
subset B of a topological space B is called compact if every open covering of C has a finite sub-covering. The topological space B is called compact if it is compact as a subset B C B. One can show that every closed set in a compact space is compact. In general, a compact set need not be closed. However, one can show that when the space B is metric space, then every compact subset is closed. One can also show that continuous functions map compact sets to compact sets.
D.12 Quotient Spaces
In the proof of Theorem 4.3 we consider the quotient space of ((Nx((+C) \ E with respect to orbits of the triple-symmetric group. Roughly speaking, quotient space of topological space R. is another topological space R/ obtained from R by declaring that certain sets of points R C R. should be treated as points and not sets. We will develop quotient spaces only in our setting of interest, by declaring that orbits in RR (for us D = [ + C²)) under the action of a subgroup of the symmetric group Sp (for us triple-symmetrie group) should be treated as points (see Definition A.4 for the notion of orbit).
Let D N. Consider a subgroup G of the symmetric group Sp, acting on IR in the standard way.
Let R C D be an invariant set, i.e., g R R for every 9 E Consider the subspace topology on R, namely, a set is open in R if and only if it is of the form R n B where B is open in R Consider the equivalence relation R D 3 x ~ y E RRD if and only if there exists g E G such that x = g y. The equivalence class of y E R is defined to be
[0] = vggyyg
Note that [y) is nothing else but the orbit of y under G. For set 5 R, we denote [$] = (1y 1 E S}. We defined the quotient space R/ as follows. As a set, R/ ~ is the set of equivalence classes, i..
R/~:= [1y) y R..
Define the canonical projection R + (R/ ~)R/~)tM to be (ty) = [y] for y R. The quotient space is equipped with the finest topology that makes the canonical projection continuous. This topology is called the quotient topology. More explicitly, the open sets in R/ ~ are all sets ß c R/ ~ such that x (B) := {y E IR D m(y) E B} is open in RDD We can also derive a more explicit characterization of the open sets of R\/ ~.
Lemma D.25. Consider the above setting. A set B is open in R/ ~ if and only if there exists an open set B in R such that B g B for every g E G and B [B].
47

---

Proof. For the first direction, let B be open in R/ Note that π TBB) [B] for
B =
U l [
Moreover, since π is continuous and B is open in R// ~ we must have that B is open in R. Lastly, since B is a union of orbits, we must have B g B for every g E G,
For the other direction, let B R/ satisfy B [B] where B is open in R and satisfy B g B for every E G. Note that the invariance of B to G can be written as
B = Ul1 BEB
U y = ty E R (t) E [B]] [
Since B = [B], this is equivalent to B π (B). Since, by definition, the open sets in R/ are exactly those sets R// such that x x-1(B (B) are open in R, and xB) is open in R, B must be open in R/ m..
We next prove simple lemma about continuous symmetry preserving functions. Lemma D.26. Let D N. and let G s. Sp act on R in the standard way. Let R C. RR be compact and satisfy g- R = R for every g E G.
1. Let q R LR be continuous G-invariant function. Then, there exists unique continuous function q R/ ~ R. such that q q n.
2. Let q: R - RL be a continuous G-descriptor (Definition D.15). Then, there exists a unique continuous and open injective function q: R/ ~ R= such that q = q 9 π. Namely, q is homeomorphism between R/ ~ and RRR).
Proof. By the definition of G-invariant function, have (xx) q(y) whenever and y belong to the same orbit. As a result, there exists unique function q R/ ~~ IR such that 7 T. Next, we show that is continuous. Let B invariant to G. i.e., 9 q- (B) = a (B) for every g E G. Moreover, 9 (B) is open in R by
R be open set. By invariance of q the action of G, q (B)
continuity of q. Hence, by Lemma D.25 l (B)] is open R/ ~. Note that (q (B) = q (B).
This shows that (B) is open whenever B is open.
When is continuous G-descriptor, 7 is continuous bijection. By continuity, g maps compact sets to compact, and since it is a mapping between a compact metric space to a metric space, maps closed to closed sets. Indeed, every closed set in compact space is compact, and every compact set in metric space is closed. Let Č' be closed in R/ ~ Then, by continuity of π, π (C)) is closed. Hence, (C)) is closed. Now. by the fact that is constant orbits and by the definition of q. q- (()) = g(C), so q also maps closed closed sets. Since q invertible, q = (a- maps closed to closed sets, which is equivalent to the pre-images of all closed sets under q being closed. Namely, (i-1)--((' C IR& is closed whenever Ö C R// ~ is closed. This is equivalent to continuity of q-1 is an open mapping, and together with injectivity and continuity of this makes q R/ ~ (R) a homeomorphism.
D.13 The Proof of Theorem 4.3
The following universal approximation theorem (Lemma 4.2 follows the same proof strategy as Theorem 3 of [26) with added elements from (38] to correct the issue detailed in Section 4.2 The lemma modifies Thcorem 3 of [26) to accommodate our triplc-symmetry. For high-level overview of the proof of Lemma 4.2 and its connection to [38 26),, we refer the reader to the flow chart in Figure which outlines the main steps, the key lemmas and their dependencies.
Lemma 4.2
Let K. C (x(+C) be compact domain such that K. = UgES S8xXS 9IC and Knn = 0. where& & c (x(+C) is the exclusion set corresponding to (FF+) (Definition) D.20
Then, TSNetpq a universal upproximator (i.e. Tooa) of continuous K. + (F functions that are (SN X SF x -c)-equivariant.
48

---

Lemma D0A
Lemma IITT
Lemma DIT
Lemma D1
(Sp-1 x Sc) -dc-cricrp ((9) over R(Poctaa
descriptor R
Reduction polynomial
Lemma
Lomma
D9
Lemma DDG
DE
Lemma
Lemma
D.19
Definition D.20
Definition
(i) Reduction the polynomials Pt.1 and Pr,++1
(1) (Sp-r x deseriittr Q over RAXUP o))
(2) (8N 1 x Sp Sc)
deserrptoe ((00))
over & (CF
Expressing gfF), gf using PMPs and DMPs
Thearem D Theorem DE
Theorem D Theorem D 1.44
Theorem D
Theorem D.
(iiiv) Approximating P using TSNelp,
(4) Approximating Q(F) using TSNe
(5) Approximating QLNP) using TNNet NF)
Theorem 0.14
Lemmas
3.25 and D
Figure 4: Flow chart illustrating the main steps in the proof of Lemmas 4.2 and D.23 which are the key lemmas used establishing Theorem 4.3 Each box represents logical step, and arrows indicate the lemmas, arguments, and dependencies connecting them. Blue and green boxes denote steps that extend techniques similar to, or inspired by, (38] and (66. The proof steps of Lemma D.23 and Lemma 4.2 are labeled (1-5) and (i-iv), respectively, with the final step (iii,iv) highlighted with thicker outline.
Proof. (i) Reduction to polynomials. Let (x++0) be a continuous (S SF Sc)- equivariant function, and let 0. By Lemma D.11 there exists (Sw Sp -eeeevvivariant polynomial (RNx((+CC (x(+CC) of some degree M, such that
sup [Ip(X) ((X) 2
(60)
x
For the remainder of the proof, show how to approximate the (SN Sp x -quivvaivariant polynomial p R NXF+C) Nx(+CC) using TSNetgq
(ii) Reduction to P1,1 and P+. Recall that we denote by Pt. (X) the (i.j)-th entry of p(X).
Note that the polynomial p is (S x SF x -quivvarrri, meaning that
((X) OF, oc) (((NN,OP,OC) X);
(61)
for every ow.apraa SN Sf Sc. By choosing oN the identity ON (1n) and or = (1f) in (61. we obtain
Pa, X) = pl, (laN, X). Vn E [N], E [F].
(62)
Moreover, by choosing NN (1m), or as the identity e, and oc = (1c), we obtain
Pn,F+e X) = (l..i((
X). Vn E [N] E [C].
(63)
Thus, every entry in the output of p can be recovered from P1,1 or Pl, F-1 reducing the problem to the approximation of P1,1 and P1,F+1- In fact, we will approximate P1, and P1,F+1 by two MLPs g(NF) E (NF) and NCNC) E (NC) respectively, and Lemma D.23 will allow to reconstruct TSNetgo from ((NF) and ((NC) which approximates
49

---

The symmetries of P1.1 and P1.F+1- The output element in the first row and column P1,1 can be viewed as the composition of with the projection map 11,1 RNNx(FCC) - RR defined by
( 1,1
which extracts the (1, 1)-st element of X (R Namely, P1,1 = =1, The projection map #1,1 is invariant to the representation of SN-1 x SF-1 x Sc. as such permutations leave the (1, (1.t) element unaffected. Now, since p an (SN SF x Se)-eqvivariant map, it is also an (Sx-1 x Sp-1 x Sc) -equivariant map. Thus, P1.1 is a composition of an (SN-1 x Sp-1 Sc)- equivariant map/ p and an (Sx-1 S ) -invariant map 111 making P1.1 an (S SF-1 X Se) Snn-invariant polynomial. By the same reasoning, P1,++1 is an (SN-1 x SF x Sc-1)-invarti invariant polynomial.
(iii) Approximating P1,1 by INN For Y.Z E K C RNX(F+C), define the equiv- alence relation Y ~ if there exists OF E SN-1 x Sp-1 x Se such that Y (F1-1. Z. Consider the quotient space K/ and the canonical projection K (K/ ) n (Y) [Y] (see Subsection D.12). Recall that AC C (Nx((++)) is compact, invariant to SN x SF Sc, and ICn (C
E) O. Consider well the Sy SF-1 X Sc- polynomial descriptor (NP)) IC + R from the space of polynomials (NN)) mapping K. R', guaranteed by Lemma D.24 Here, by the lemma, the space (SNet(N of MLPs from K. to R4 is universal approximator of B B.FF), Since Q(NF)) is continuous (Sx-1 S -deedrrcriptoor and P1,1 : K. > IR is continuous and (SN-1 x Sp-1 x Scn--nvariant, by Lemma D.26 there exist home- omorphism ((NF) (K/ ~) ((NF)((C and continuous function P1,1 (K// ~) - (K.) such that
P1,1 P1.1 and Q(NF)= Q(NF)
Thus, we can now write Pı,1 as
P1.1 P1 = ( ( (Q(NF))-1) 2 (P)
o - ( (Q (MM
where r = $1,1 1 (Q ((N))( - IR belongs to the space B, of all continuous mappings from (KC) to R. Since K. is compact and Q(NF) is continuous, the set (X))) C R is compact. By the Universal Approximation Theorem (Theorem D.12p, the space N, of multilayer perceptrons (MLPs) from (K)) to a universal approximator of B,. Define
:= {0, ON 0, Nr.0N E (N)
By Theorem D.14 the function space N a universal approximator for the class
B = { o fN f, E JN E B(NF)
noting that Pt,1 = r (NF) E B by the above construction.
This shows that we can approximate PI, by a TSNe((NF) ((NF) up to error e/2. Similarly, we can approximate F1,F+1 by a (NC)((NC) g(NC) up to error c/2.
(iv) Approximating p using TSNetgg: Define an (SN x Sp x -e)-evrivaai network 0 Nx(+FCC) (xF+() via
nn (X) g
((N ((NF) ((ON, X), Vn [N], e [F],
(64)
and
0n, Pn X) BINC)((xx, -X), Vn E [N],c E [C].
(65)
Lemma D.23 and
62 63
is TSNetgq which approximates to error c/2 in Loge This, together
with (60). finally gives
10 - 0l - 1 - 1ploc + 1lp - glo S.
Let K C (F++F) be compact domain such that K. = UgESx SSe gK and Knn = 0, where & c (X(+F) is the exclusion set corresponding to (Nx((+O) (Definition) D.20 Then, TSNetsIA a universal approximator of continuous K. R functions that are (Sx x Sc)- equivariant and S Spiinvariant.
Theorem 4.3
50

---

Proof. Let K. + I NxC be continuous SN x Sc-equivariant and Sp-invariant continuous function and let e > O. We define the lifted function q" K. + (NF(()C) by
(x) = (ONxF XF q(X)) E (Nx(++)),
where we pad g(X) with zeros in the first F columns. easy to verify that q" (Sp Sc SN)- equivariant, as the Sy part of the group action acts only on the zero vero-padded section, and thus does affect (X)).
By Lemma 4.2 there exists network TSNetgq denoted by :NX(FFO) +B RNX(F+C), such that
(x² (X) (X) < for all XeK.
Consider the label projection map p defined by
p(X,)) Y, V(X,Y) NNP R
Notice that q= = o o q² and that fc == p f is TS architecture. Thus, we get || fo (Z) |l (q" (Z) 1 (Z)) /o I ll) 5 (z) <
for all K. Hence, there exists TSNet,,1 that approximates q on K. up to error c.
E Theorem 3 in [26
In this section, we present the (SN x H) equivariant DSS layers and the corresponding DSSNet architecture, along with their universality result, as introduced [26), for an arbitrary subgroup H C Sp. We then explain why the issue discussed in Section 4.2 invalidates the general universality claim for arbitrary subgroups H C SF and how, by drawing on techniques from [38,, the claim can still be upheld in the special case H Sp - key insight that enables us to extend the revised Theorem by [26] to the triple-symmetry setting.
We begin by restating Theorem 4 from [26). which characterizes the (Sx x H) -qquivarrai linear layers over NxF for any subgroup H SF.
Theorem E.1 (Theorem 4 in (26)). Let H S Sp. Any linear (SN x H -))-quivariian layer L RK X p x is of the form
L(X).n:: LI(X mn:) + La E X.)),, Vn E [N]
where L1, La RRIIF R2XF linear H-equivarian functions.
Deep sets for symmetric elements networks (DSSNets). Given H Sp. (26 define DSS network F: RIxNxF RIxNxF
F= F()) (L) o0o oo...... o
(66)
where each ( R x k xNF an (SN x eqqivvaiia linear layer as in Equation 66 a is a non-linearity and k()) k(L) 1.
The universality claim in [26] uses a different exclusion set than our Theorem 4.3 but serves the same purpose- to enable the composition descriptors while preserving our triple symmetry.
Definition F.2 (The DSSNet exclusion set). The set
N Σ nzl
E' = c'
(ERNN
X =
Σ X nith
called the DSSNet exclusion set corresponding to NNF.
Theorem E.3 (Theorem 3 in (26).. Let C Sp. Let C. NXF be compact domain such that
K. UneSs gK and Kn = 6, where E' C NXF is the exclusion set corresponding to RN x
(Definition E.2). Then, DSSNet are universal approximators Toge of continuous K. R F functions that are (Sx H -eqeuivaarinn..
51

---

Discussion on universality in the general subgroup case (H S Sp), The issue identified in Theorem E.3 discussed earlier in Section
4.2 stems from an attempt to span the space of (5x-1 x H):
equivariant polynomials IR IR. i.e.
P1 (h x) h PI vh E H.
(67)
26 expand pi (X) using the polynomial basis {hr TR RR in X1,
Pi(X) = Σ
(x X2 2............................... (x..)(X1.).
i=0
where {a) (N + R are the base coefficients and by Equation 67 we have
Σa an X h NN. xI.) = h Σ 1=0
o X22 2... X (oX
(68)
The misstep arises in their assertion that 'If' we fix X2. XN, then pl (X
X N is H--
equivariant polynomial in Xi". which does not hold generally as explained in Section 4.2 The goal of this step was to express the equivariant function in terms of invariant functions to later leverage the richer approximation theory for invariant functions.
We avoid the aforementioned pitfall for the special case H = Sp by exploiting the stronger symmetry structure provided by the permutation groups rather than their subgroups. Following similar reasoning to Lemma 1 of (38] we show in step (2) of the proof of Lemma
4.2 that the first component
P1,1 N IR of the (SN-1 x 1 eequivariin polynomial p1
T XxF
F ( SS--1)=
invariant and fully determines the remaining components (see Equation
(62)) This step corrects the flawed transition in name-n,, the decomposition of an equivariant polynomial into invariant components-allowing us to recover corrected (though less general) version of their Theorem 3 for H Sp, and to extend the result to our triple-symmetry setting in Theorem 4.3
F Time and Memory Complexity of TS-GNNS
Time complexity. Given a graph with N nodes, F features, and E edges, TS-GNNs operate in three main stages:
Local aggregation: A non-learnable, standard aggregation over each node's neighborhood. This step has time complexity of OEEF).
Least-squares (LS) preprocessing: A one-time LS problem is solved using the aggregated features. This step has a complexity of O(N 122 + 1²)). Importantly, this computation performed once per graph and does not scale with the number of layers or training epochs.
Message-passing (MP); During the forward pass, standard MP operations are performed for each layer, with time complexity of O (FFF) per layer.
For comparison, GraphAny, the only other zero-shot baseline, uses a similar preprocessing pipeline. It performs multiple local aggregations and L.S solutions over different neighborhood radii, followed by a transformer over the resulting representations. Despite these architectural differences, its overall computational cost remains on the order of OEE). making it comparable TS-GNN and consistent with the standard complexity of message-passing neural networks (MPNNs).
Memory complexity. The intermediate node representations produced by TS-GNN have size N Fx x K, where K is the number of channels in the model. During message- message-passing, tensors of size E x F x K must also be kept in memory. Compared to standard message- passing neural networks, this represents a K-fold increase in memory usage.
Although the asymptotic memory complexity remains the same in O-notation with K = 0(1), in practice the additional factor K increases memory usage, which can reduce efficiency and potentially create bottlenecks for very large graphs high-dimensional feature spaces.
52

---

Table Zero-shot per-dataset accuracy TS-Mean and average accuracy of GraphAny.
com
chameleon
roman-empire
wiki-es
average
actor
28.25 + 1.28
31.62 + 1.04
29.91 + 0.91
26,66 = 0.67
28.98 + 0.98
amazon-ratings
42.03
1.44
44.31
= 1.19
38.42 + 1.26
41.99 = 0.53
41.69 + 1.10
arxiv
55.78
2.02
54,01
+ 5.35
48.98
1: 5.01
56.46 2.38
53.81 +: 3.69
blogcatalog
76.70 3.48
73.89
1: 3.85
67.30
11.46
73.59 1: 2.57
72.87 1: 5.34
brazil
38.46
9.99
32.31 6.99
29.23 8.85
34.81
-: 7.81
citesoor
68.66
68.14
66.62 + 2.07
70.84 = 0.23
68.56 + 0.80
co-physics
0.772
91.36 1.74
92.92 + 0.48
91.67 = 0.87
92.12 + 0.95
computers
0.97
76.76 2,08
76.73 +: 6.50
78.42 = 2.13
78.27 + 2.92
cornell
70.27 4.68
62.16 1. 3.31
74.05 1: 4.10
48.65 10.98
63.78 1: 5.77
deever
52.46 22.46:2:.57
52.29 1: 2.15
51.95 2.40
50.87 2.18
$1.89 + 2.33
curope
6.70
39.12 5.41
31.25 4.57
30,88 3.44
34.
full-DBLP
66.31
66.55 + 1.97
67.06 + 4.38
67.09 = 5.09
66.75 + 3.72
last-fm-asiia
77.69
78.11 + 0.93
76.71 + 1.96
78.57 0.93
77.77 + 1.19
minesweeper
80.71 +.55
80.03 0.05
81.00 + 0.84
80.03 0.05
80.44 + 0.37
photo
90.09 1.20
87.05 1.61
88.51 4.38
89.61 1.96
SX. 82 2.29
pubmed
75.18 0.54
75.28 + 1.13
75 48 0.45
76.44
1.00
75 60 + 0.78
questions
0.01
0.01
squirel
41.10
49.38 2.82
40.37 + 1.24
35.43 = 3.07
41.57 + 2.14
72.30
tolokers
78.16 1.66000000
78.16 + 0.00
76.89 + 2.83
78.16 0.00
77.84 + 0.72
usa
42.38 1.99
39.03 1: 8.37
40.32 1: 7.36
41.37 1 2.11
40.78 1 4.96
wiki-attr
70.40 1.63
71.23 1: 2.27
70.36 +: 1.69
71.91 1,21
70.97 + 1,70
wisconsin
61.63 = 10.11
60.44 = 11:39
62.67 + 9.49
62.82 = 9.38
61.89 = 10.09
TS-Mean average (25 graphs)
63.69 2.25
65.29 + 2.97
64.22 + 3.77
63.50 = 2.62
64.67 + 2.90
GraphAny average (25 graphs)
64.23 1.47
65.40 1.63
64.60 1: 1.69
64,30 + 1.64
64.63 +: 1.61
G Additional Experiments
In this section, we address the following questions introduced in Section 6
Q3 How sensitive are TS-GNNs to the choice of pretraining dataset in low-data regimes?
Q4 What is the impact of least- least-squares mixing and the bias term on TS-GNNs generalization
performance?
Q5 Is triple-symmetry necessary for graph foundation models?
Specifically, we answer Q3, Q4, and QS in Sections G.1 to G.3 respectively. Additionally, in Section G.4, we extend the experiments from Section 6.1 to include more GNN variants and in
Section G.5 we provide the full per-dataset results for Figure
G.1 Sensitivity of TS-GNNs to Pretraining Data
we explore how sensitive method is when single dataset is used in training. In addition to cora, train TS-Mean on roman-empire, chameleon, and wiki-cs. All models are evaluated zero-shot on the remaining 25 test graphs.
Setup.
We answer Q3 by repeating the same experimental setup in Section 6.1
Results. Table-demoostraall that both TS-Mean and GraphAny maintain strong performance across different pretraining sources in the low-data regime, indicating that TS-GNNs are largely insensitive to the choice pretraining data. While all pretraining datasets lead to comparable zero-shot accuracy, TS-Mean slightly outperforms GraphAny average.
These observations are consistent with the results shown in Figure 3 which illustrate that across varying training set sizes, both approaches remain competitive in the low data regime when labeled examples are scarce. Notably, the true strength of TS-GNNS becomes apparent in the foundation model scenario, that is, the high data regime.
G.2 The Importance of the Least-Squares Mixing and the Bias Term
Setup. To address Q4, we isolate the contributions (a) the least-squares (I.S) feature-label mixing and (b) the inclusion of bias term. First, we evaluate non-parametric setup across our test set of
53

---

Table Accuracy of non-patne non-parametric squures variants with and without bias and mean aggregation.
random
LS
LS+bias
LS+bias+mean
Average
20.98
58.39 + 1.24
58.75 + 1.58 59.00 + 2.11
Table 4: Zero-shot accuracy of TS-Mean and TS- TST with and without the least-squares mixing and the bias term.
plain
+LS
+LS+bias
TS- TS-Mean
55,43 + 1.12
63.21 + 2.08
66.21 + 1.93
TS-GAT
55.19 + 1.54
62.66 + 2.20
65.85 + 2.38
27 datasets. We compare four configurations: LS alone, LS with a bias term, LS with bias term followed by a local mean aggregation step (analogous to MEAN-GNN, and a random baseline. Next, we assess the impact of these components on TS-Mean and TS-GAT, trained on Cora and evaluated zero-shot on the 28 datasets. We consider three configurations: plain (no LS, no bias), LS only, and LS plus bias. This allows us to understand how each component contributes to generalization in parametric TS-GNNs.
Results. As shown in Table 3 the plain TS-GNN variants slightly lag behind the LS baseline. This behavior expected, since global pooling plain TS-GNN creates an information bottleneck that limits feature-label mixing. Nevertheless. even without LS or bias term, plain TS-GNNs perform substantially above random guessing. indicating that the model captures transferable graph structure on its own.
Table 4 highlights that including LS alone provides notable performance boost, demonstrating that LS and TS-GNNs capture complementary patterns. Adding a bias term further improves generalization, with the combination of LS and bias yielding the best performance across both TS-Mean and TS-GAT. The combination of the two yields greater generalization than either alone.
G.3 Necessity of Triple-Symmetry in GFMs
Setup. To investigate Q5, examine the importance of feature and label symmetries in graph foundation models. We consider three architectures with varying symmetries: (i) MeanGNN, which permuuttnn equivariant; (ii) DSS with local mean aggregation, denoted as DSS-Mean which is node-equivariant and feature-permutation invariant; and (iii) TS-Mean, which is fully symmetric node, feature, and label permutations (triple-symmetric). Following the setup in Section G. each model is trained on a single dataset, choosing from cora, roman-empire, chameleon, or wiki-cs, and evaluated zero-shot the remaining 25 test graphs. To handle varying input and output dimensions across datasets, we pad or truncate features and labels when necessary.
Results. As shown in Table performance increases with the inclusion of additional symmetries. MeanGNN achieves the lowest accuracy, DSS-Mean improves by incorporating feature symmetry, and TS-Meam attains the highest zero-shot accuracy by aligning with all three symmetries that are required of a GFM. This provides concrete empirical evidence that both feature and label symmetries (the symme-yy criteria) is crucial for strong generalization in GFMs.
G.4 TS-GNNs variants
We extend Table include zero-shot experiments for TS-SGC, TS-GCN, and TS-GCNII, which TS-GNN variants employing SGC [46), GCN (20], and GCNII [5] their respective aggregation functions. Each model is trained on the cora dataset and evaluated on the remaining 28 datasets. All reported results reflect the mean accuracy and standard deviation
five random seeds.
Results. revelss a interesting trend: as the GNN architecture becomes more complex-from SGC to GCN to GCNII, the zero-shot performance degrades in the low-data regime. This supports hypothesis that complex GNN architectures, while beneficial fully supervised settings, may overfit to training distributions and generalize poorly in transfer scenarios (when trained single graph).
54

---

Table 5: Zero-shot accuracy of models with varying symmetries.
roman-empire
chameleon
wiki-cs
average
MeanGNN
23.30 + 5.12
21.78 6.76
23.11 + 4.52
22.28 6.01
22.62
5.60
DSS-Mean
28.30 + 4.97
23.69 + 6.33
27.06 = 3.70
24.22 = 4.81
25.82 + 4,95
TS-Mean
65.69 = 2.25
65.29 2.97
64.22 + 3.77
63.50 2.62
64.67 2.90
Table 6: Zero-shot accuracy TS-SGC, TS-GCN and TS-GCNII, all trained on cora.
TS-SGC
TS-GCN
TS-GCNII
actor
30.24 + 0.56
29.59 + 1.07
26.95 + 1.81
amazon-ratings
41.24 + 1.62
40.78 + 1.71
38.10 + 1.94
arxiv
54.79 + 1.80
53.2
54.53 2.13
blogcatalog
78.94 = 9.06
7..1
brazil
30.00 9.58
2.
44.62 + 17.54
chameleon
48.86 5.53
4..29
52.59
4.56
citeseer
1..4=0.8.
69.70
65.90 + 0.27
co-cs
91.75 + 0.41
91.65
89.30 + 0.54
co-physics
92.76 + 0.70
92.54 0.72
90.98 1.71
computers
80.63 = 1.43
80.01-11 1.59
cornell
69.19 4.52
5.05
3.088
deezer
52.61 2.91
52.94
40.91
europe
32.38 5.60
31.75
35.25
full-DBLP
68.01 + 2.49
6 1.49
2.446
full-cora
53.01 + 1.64
last-fm-asia
76.23 + 1.06
75.79
1.17
78.22 0.76
minesweeper
80.47 + 0.47
80.38
10.00
photo
10.49:0.00 0.94
90.23 0.98
1.35
pubmed
77.32 0.69
+
76.98
questions
97.08 0.07
9.00
9..04
roman-empire
66.99 + 1.40
66.13
52.58 1.72
squirrel
33.22 + 1.93
3.79
texas
72.97 + 10.64
5.6886.0
82.70
tolokers
72.38 + 8.62
78.24
usa
38.81 = 3.08
4.18
31.32 6.26
wiki-attr
74.60 + 1.65
74.85 1.25
69.70 + 1.62
wiki-cs
72.62 = 0.80
18.00
65.05 + 10.78
wisconsin
64.40 + 2.22
62.85 + 1.97
60.18 2.59
Average (28 graphs)
64.70 + 2.94
64.34 + 2.57
62.01 + 4.00
G.5 Per-dataset Results for TS-Mean Figure
In Section 6.2 we studied how the size of the training affects zero-shot generalization by training
TS-Mean and GraphAny on progressively larger subsets of held-out training pool. Table 7 reports the per-dataset zero-shot accuracy of Mé-Mean for training subset sizes of 3, 5, 7, and 9. Each larger subset includes all datasets from the smaller subsets and is sampled from a held-out pool of datasets. Zero-shot evaluation is performed on the remaining 20 datasets, following the protocol described in Section 6.2
55

---

Table Zero-shot accuracy of TS-Mean across datasets when trained on 3, and 9 held-out graphs.
Training Graphs
3
amazon-ratings
42.16 + 1.41
41.93 +: 2.20
39.92 +: 1.30
39.79 +: 0.79
42.20 +: 0.72
arxiv
56.20 2.50
55.47 + 4.24
57.28 + 1.91
56.88
1.53
56.13 +
blogcatalog
76.22 2.90
76.39
77.82 + 5.19
77.01 + 2.87
77.90 =
brazil
39.23 + 5.70
38,46
36.15 + 5,83
33.08 7.98
40.77 = 14.80
chameleon
60.83 5.53
58.01
53.86 5.60
55.88 2.82
56.97
citeseer
68.66 0.18
67.80 0.55
67.88
68.14
co-cs
90.89 0.44
9..94
91.52 0.39
91.45
91.36 1.36 0.36
co-physics
92.56 0.71
92.75
92.83
0.34
92.97 0.33
92.80 1 0.54
cornell
68.65 2.42
77.84 1.9
78.38 4.27
74.59 1 4.91
deezer
52.31 1.31:2..
51.70
5
52.06 2.22
51.88 2.85
full-DBLP
2.95
66.94
2.82
66.64 + 3.55
full-cora
53.57 0.76
51.04
51.45 + 1.52
53.39 + 1.43
53.20 + 1.70
last-fi--ssia
78.01 1.01
77.40 0.73
78.72 0.87
78.07 = 0.76
minesweeper
80.65 0.38
#.41
60.86
80.98 0.34
80.05
pubmed
75.06 0.52
1.19
16.60=0.0
7..92
77.82 = 0.56
questions
97.02 0.01
9.002
96.91 - 0.39
97.18 0.02
97.03 0.02
squirrel
41.61 1.25
4
37.29 2,41
37.89 0.67
37.25
wiki-attr
69.84 1.23
73.03 + 1.63
74.73 +
73.71 1.61
wiki-es
73.89 + 2.22
73.13
73.37 + 1.40
74.31 + 0
wisconsin
60.78 + 11.76
72.55 + 6.93
76.08 + 2.56
80.39 2.77
80.47 6.04
Average (20 graphs)
67.23 + 2.35
67.36 2.65
67.82 + 2.33
68.42 + 1.87
68.57 + 2.52
H Lack of Node-regression Benchmarks
Our proposed architecture is designed handle both node classification and regression tasks, as its theoretical derivation imposes no assumptions on label semantics. However, our empirical evaluation restricted node classification ecosystem of graph machine learning benchmarks.
by design, but due to fundamental limitation the current
In experiments, evaluated performance across 28 node classification datasets sourced from the major graph learning libraries such as PyG [0], DGL [4], or [GB[ Yet, not a single node-level an isolated gap but reflects a broader issue in
regression benchmark was available. This absence the field: the lack of standardized, diverse, and meaningful benchmarks. As recently emphasized by Bechler-Speicte
al. (2). the progress of graph foundation models is increasingly bottlenecked not by modeling capacity or computational resources, but by the lack of representative evaluation tasks.
We strongly encourage future works develop standardized benchmarks for node-level regression. In the absence of such benchmarks, our results in Section (6 on node classification serve as a strong indicator of the method's potential for more general node-level prediction tasks.
I Dataset Statistics
The statistics of the 29 node classification datasets used in Table 1 can be found in Table 8 The node classification datasets used for training in Figure are detailed in Table
Hyperparameters
We adopt the hyperparameters from 152 for the experiments in Table I over the MeanGNN, GAT and GraphAny architectures. The complete hyperparameter configurations, including those used for TS-Mean and TS-GATT is provided in Table 10
The same hyperparameters detailed in Table 10 are also used for the experiment in Figure when
training on a single graph. Hyperparameters used for training on more than one graph in Figure are
reported in Table
56

---

Table 8: Statistics of the 28 node node classification datasets.
Dataset
#Nodes
#Edges
#Feature
#Classes
Train/Val/Test Ratios (%)
actor
7600
30019
932
48.0//2.0/20.0
amazon-ratings
24492
186100
300
50.0/25.0/25.0
Arxiv
169343
1166243
128
40
53.7/17 6/28..7
blogcatalog
5196
343486
8189
2.3/48. 8/48. 8
brazil
131
1074
131
61.1/19. 1/19.8
chamelcon
2277
36101
2325
48.0/32.0/20.0
citeseer
3327
9104
3703
3.6/15.0/30.1
co-CS
18333
163788
6805
15
20/49./449.2
co-physics
34493
495924
8415
5
0.3/49 9/49.9
computers
13752
491722
767
10
1/3/99
cora
2708
10556
1433
5.2/18.5/36.
cornell
183
554
1703
1T.5/3.2//0..
deezer
28281
185504
128
0.1/49 9/49.9 9
europe
399
5995
399
20. 20.1/39.MM 8/40.1
full-DBLP
17716
105734
1639
0.5/49.8/49.8 8/49.8
full-cora
19793
126842
8710
70
7.1/46.5/41
last-fm-asia
7624
55612
128
18
4.7/47. 6/47.6
minesweeper
10000
78804
7
2
50.0/25 00/25.0
photo
7650
238162
745
2.1/49
2.1/49.0/49.0 0/49.0
pubmed
19717
88648
500
0.3/2.5/5.1
questions
48921
307080
301
50.0/25. 50.0/25.0/25.0
roman-empire
22662
65854
300
18
50.0/25 00/25.0
squirrel
5201
217073
2089
48.0/32.0/20.0
texas
183
558
1703
5
47.5/31.7/20.2
tolokers
11758
1038000
10
1190
13599
1190
4
6.7/46.6/46.
wiki
2405
17981
4973
14.1/42.9/43.0
wiki-cs
11701
431206
300
10
5.0/15. 1/49.9
wisconsin
251
900
1703
Table 9: Datasets used for training in Figure
Train-set size
Graphs
cora
cora, texas, tolokers
5
cora, texas, tolokers, photo, roman-empire
cora, texas, tolokers, photo, roman-empire, usa, actor
9
cora, texas, tolokers, photo, roman-empire, usa, actor, computers, europe
Table 10: Hyperparameters used in Table
MeanGNN
GAT
GraphAny
TS-Mean
TS-GAT
2 10
9.10-
0.01
10-4
0.01
5 10
5 10-4
0.03
hidden dimension
64, 128
64, 128
32, 64, 128
16
16
# layers
2
2
# batch
128
0.25, 0.3,
0.25, 0.3,
visible train labels (%)
0.5
0.35, 0.4
0.35, 0.4
# epochs
400
400
1000
2000
2000
Entropy
1,2
# ML. layers
0
1,2
57

---

Table Hyperparameters used Figure
GraphAny
TS-Mean
3
10-0
5 10-3 3 16
hidden dimension
32, 64, 128
# layers
2
# batch
128
1
visible train labels (%)
0.5
0.6, 0.7, 0.8
# epochs
500, 1000
50, 100, 300, 500
Entropy
1,2
# MLP layers
1,2
0
58


Reviews:
[{"review_id": "eT45LCVzzn", "reviewer": "Reviewer_KTq8", "summary": "This paper proposes a theoretically-grounded recipe for designing Graph Foundation Models (GFMs) for node-level classification and regression tasks. The central idea is to identify and enforce three key symmetries: node permutation-equivariance, label permutation-equivariance, and feature permutation-invariance. The authors characterize the space of linear transformations that respect these \"triple-symmetries\" and prove that the resulting \"Triple-Symmetry Network\" (TSNet) is a universal approximator on multisets. This theoretical foundation is then used to develop Triple-Symmetry Graph Neural Networks (TS-GNNs), a modular framework that can transform any standard GNN into a GFM capable of zero-shot generalization across graphs with varying structures, feature configurations, and label semantics. Extensive experiments on 27 real-world node classification datasets demonstrate that TS-GNNs (TS-Mean and TS-GAT) consistently outperform their non-transferable baselines and also improve upon the prior state-of-the-art GraphAny in a zero-shot setting.", "questions": "See weaknesses.\n\nAnd:\n- Could the authors discuss potential future work on extending this recipe to more complex graph structures, such as heterogeneous graphs with multiple node and edge types, or dynamic graphs where the topology changes over time?\n\n- What about the scalability of the proposed method? When talking about pre-training the graph neural network, what scale and computational cost and downstream task coverage is being discussed? Conceptually compare this with large pre-trained language models or vision models. Can the experiments go beyond the small simple node classification tasks?", "limitations": "The paper does not include explicit limitation sections. Although in the checklist limitations were briefly mentioned, I would encourage the authors to include an explicit limitations section.", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n- The paper's primary strength lies in its rigorous theoretical analysis. The identification of the \"triple-symmetry\" criterion and the subsequent characterization of equivariant linear layers, culminating in the universality proof for TSNets, provides a robust mathematical underpinning for the proposed GFMs. This distinguishes the work from many empirically-driven approaches.\n\n- The TS-GNN framework offers a practical and modular way to convert existing GNN architectures into GFMs. This approach allows for leveraging the strengths of diverse GNN designs while enabling zero-shot generalization.\n\n- The extensive experiments on 27 diverse node classification datasets provide evidence for the effectiveness of TS-GNNs in a zero-shot setting.\n\n\nWeaknesses\n\n- While the experiments are extensive in terms of the number of datasets, they are exclusively focused on node classification tasks. The paper states that the theory supports node regression as well, but no empirical validation is provided for this. This limits the empirical scope of the claims.\n\n- The computational complexity of the algorithm is not thoroughly explained. For example, it involves solving the least square transformations into each layer which might be expensive for large graphs. The scalability aspect and computational cost should be discussed more, both theoretically and empirically in experiments. This shed light on the practicability of the proposed algorithm.\n\n- The experimental study is limited and only compared with very few baselines. Moreover, the gains seem relatively small, which is hard to tell the exact benefits. More ablation studies and sensitivity analysis could benefit the paper.", "was_revised": true, "final_justification": "Many of the experimental concerns were resolved, but there are some remaining concerns of generalizability and scale of the approach (empirically), which the authors acknowledge. While I keep my original rating, I would not object if the paper gets accepted. I will leave the other reviewers and AC on the final recommendation, as I do not have a good grasp of the theoretic vs. empirical importance in this work.", "rebuttal": "We thank the reviewer for their thoughtful feedback and for recognizing the novelty, ingenuity, and theoretical contributions of our approach.\n\n> W1: While the experiments are extensive... they are exclusively focused on node classification tasks...\n\nWe 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.\n\n> W2: The computational complexity of the algorithm is not thoroughly explained...\n\nThank 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.\n\nFor 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.\n\nGraphAny, 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.\n\nWe will include in the final version a comprehensive theoretical analysis of the runtime, comparing our method with GraphAny and classical GNNs.\n\n> W3: The experimental study is limited and only compared with very few baselines \n\nUnfortunately, 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.\n\nThat 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:\n\n||GraphAny|TS-Mean|TS-GAT|TS-SGC|TS-GCN|TS-GCNII|\n|-|-|-|-|-|-|-|\n|Average|65.83±1.66|**66.21±1.93**|65.85±2.38|64.71±3.06 |64.39±2.61|62.45±3.43|\n\nThe 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. \n\n> Moreover, the gains seem relatively small, which is hard to tell the exact benefits\n\nThis 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. \n\nWe 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.\n\n|#Train graphs|1|3|5|7|9|\n|-|-|-|-|-|-|\n|GraphAny|66.62|**67.34**|67.29|67.28|67.22|\n|TS-Mean|67.23|67.36|67.82|68.42|**68.57**|\n\nResults 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. \n\n> More ablation studies and sensitivity analysis could benefit the paper\n\nWe agree and have provided sensitivity analyses of two types:\n\n**(1) Least-Squares mixing and bias term**\n\nWe 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.\n\n||random|LS|LS+bias|LS+bias+mean|\n|-|-|-|-|-|\n|Average|20.98|58.39±1.24|58.75±1.58|59.00±2.11|\n\nWe 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. \n\n||plain|+LS|+LS+bias|\n|-|-|-|-|\n|TS-Mean|55.43±1.12|63.21±2.08|**66.21±1.93**|\n|TS-GAT|55.19±1.54|62.66±2.20|**65.85±2.38**|\n\nThese 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.\n\nNext, 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.\n\n**(2) Sensitivity to pretraining dataset**\n\nWe 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. \n\n||cora|roman-empire|chameleon|wiki-cs|average|\n|-|-|-|-|-|-|\n|TS-Mean|65.96±1.90|64.63±1.33|65.66±2.60|64.52±2.34|65.19±2.04|\n|GraphAny|64.63±1.42|65.15±1.61|65.80±1.55|65.11±1.53|65.17±1.53|\n\nThese 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.\n\n> Q1: Could the authors discuss potential future work on extending this recipe to more complex graph structures, such as heterogeneous graphs...\n\nOne 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.\n\nAnother 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.\n\n> Q2: What about the scalability of the proposed method?...compare this with large pre-trained language models or vision models...\n\nFirst, 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.\n\nAs 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).\n\nRegarding 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.\n\n> The paper does not include explicit limitation sections\n\nWe will include a dedicated limitations section.\n\n[1] Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks, ICML25\n\n[2] Towards Foundation Models for Knowledge Graph Reasoning, ICLR24\n\n**We will include all the experimental results and suggestions provided by the Reviewer in the final version with the appropriate discussion.** \n\nWe hope our responses address your concerns and would greatly appreciate your reconsideration of the evaluation and increasing your score."}, {"review_id": "tBmkmv1Wpw", "reviewer": "Reviewer_pt6w", "summary": "This paper investigates two important properties for graph learning: label permutation-equivariance and feature permutation-invariance, in addition to node permutation-equivariance. The authors propose a novel model, the Triple-Symmetry Network (TSNet), building on the prior work \"On Learning Sets of Symmetric Elements.\"", "questions": "1. The average performance reported in Table 1 is comparable to the baseline method, GraphAny. \n\n2. The experiments currently lack graph datasets for social media, such as Instagram and Reddit, to analyze user properties. Please include these datasets during the rebuttal phase.\n\n3. The pseudo-code for the proposed method would greatly enhance clarity and understanding.\n\n4. Please further discuss how this model could be applied to GFM when language serves as node or edge features.", "limitations": "The authors write down the limitations in the introduction and discussion, noting that it is designed for node-level tasks.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is generally easy to follow, and the theoretical claims are well-supported by proofs provided in the supplementary materials. However, graph datasets for social media should be added to demonstrate the strength of TSNet.", "was_revised": true, "final_justification": "maintain my original score of 5", "rebuttal": "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:\n\n> W1: However, graph datasets for social media should be added to demonstrate the strength of TSNet.\n\n> Q2: The experiments currently lack graph datasets for social media...\n\nWe 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.\n\nUnfortunately, 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.\n\nWhile 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.\n\nThat 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.\n\nWe list the rest of the experiments performed in this rebuttal below, for the reviewer's convenience and interest:\n\n**(1) Evaluating TS-GNNs and GraphAny in the high-data regime** by varying the number of training graphs (see Q1 below)\n\n**(2) Introducing three new TS-GNNs variants**\n\nWe 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:\n\n||GraphAny|TS-Mean|TS-GAT|TS-SGC|TS-GCN|TS-GCNII|\n|-|-|-|-|-|-|-|\n|Average|65.83±1.66|**66.21±1.93**|65.85±2.38|64.71±3.06 |64.39±2.61|62.45±3.43|\n\nThe 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.\n\n**(3) Ablation over the least-Squares mixing and bias term**\n\nWe 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.\n\n||random|LS|LS+bias|LS+bias+mean|\n|-|-|-|-|-|\n|Average|20.98|58.39±1.24|58.75±1.58|59.00±2.11|\n\nWe 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. \n\n||plain|+LS|+LS+bias|\n|-|-|-|-|\n|TS-Mean|55.43±1.12|63.21±2.08|**66.21±1.93**|\n|TS-GAT|55.19±1.54|62.66±2.20|**65.85±2.38**|\n\nThese 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.\n\nNext, 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.\n\n**(4) Ablation over the pretraining dataset**\n\nWe 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. \n\n||cora|roman-empire|chameleon|wiki-cs|average|\n|-|-|-|-|-|-|\n|TS-Mean|65.96±1.90|64.63±1.33|65.66±2.60|64.52±2.34|65.19±2.04|\n|GraphAny|64.63±1.42|65.15±1.61|65.80±1.55|65.11±1.53|65.17±1.53|\n\nThese results further validate that TS-Mean and GraphAny are consistently competitive in the low-data regime.\n\nThis 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.\n\n> Q1: The average performance reported in Table 1 is comparable to the baseline method, GraphAny.\n\nThis 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. \n\nWe 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. \n\n|#Train graphs|1|3|5|7|9|\n|-|-|-|-|-|-|\n|GraphAny|66.62|**67.34**|67.29|67.28|67.22|\n|TS-Mean|67.23|67.36|67.82|68.42|**68.57**|\n\nResults 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. \n\nInterestingly, 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.\n\n> Q3: The pseudo-code for the proposed method would greatly enhance clarity and understanding.\n\nThanks for this comment. We will include a detailed pseudo-code for TS-GNNs in the camera-ready version.\n\n> Q4: Please further discuss how this model could be applied to GFM when language serves as node or edge features.\n\nOur 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.\n\nAs 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.\n\nWe 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.**"}, {"review_id": "Oof0uN8idB", "reviewer": "Reviewer_HcMt", "summary": "This paper focuses on the design of Graph Foundation Models (GFMs), aiming to address the issue that traditional Graph Neural Networks (GNNs) struggle to generalize across different graph structures, feature sets, and tasks. Its core contribution is proposing a theoretical framework based on \"triple-symmetry\": node permutation-equivariance (predictions change consistently with the permutation of node indices), label permutation-equivariance (predictions change consistently with the permutation of labels/targets), and feature permutation-invariance (predictions are unaffected by the ordering of features).\nTheoretically, the authors characterize the space of linear transformations that satisfy these triple symmetries and prove that the resulting Triple-Symmetry Network (TSNet) is a universal approximator for set functions that respect these symmetries. In practice, by applying TSNet to the local neighborhood aggregation of graphs, they propose Triple-Symmetry Graph Neural Networks (TS-GNN), which can convert any GNN into a GFM and achieve zero-shot generalization. Experimentally, the performance of TS-GNN (based on MeanGNN and GAT) is validated on 27 real-world node classification datasets, and its zero-shot performance outperforms traditional GNNs and the existing method GraphAny.", "questions": "1. 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.\n2. Although the theory supports regression tasks, experiments only validate classification, lacking empirical support for regression scenarios, weakening the framework's comprehensiveness.", "limitations": "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.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "1. Proposes \"triple symmetry\" (node permutation-equivariance, label permutation-equivariance, feature permutation-invariance) as the core design criterion for graph foundation models (GFMs), providing a principled framework to address the cross-graph generalization issue of traditional GNNs and filling the gap in the theoretical foundation of graph foundation models.\n2. Proves that Triple-Symmetry Networks (TSNets) are universal approximators for set functions respecting the triple symmetry, providing mathematical guarantees for the model's effectiveness.\n3. Validates the model on 27 real-world datasets, showing that its zero-shot performance outperforms baselines, providing sufficient empirical support.\n4. Open-sources code and detailed experimental settings (e.g., datasets, hyperparameters), ensuring the reproducibility of results.", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> 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.\n\nWe 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.”\n\nOur 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.\n\nWe 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.\n\n> Q2: Although the theory supports regression tasks, experiments only validate classification, lacking empirical support for regression scenarios, weakening the framework's comprehensiveness.\n\nOur 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.\n\nWe would be glad to conduct any further experiments that you believe could strengthen the paper and warrant a higher score.\n\n> 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.\n\nWhile 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. \n\nIt 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.\n\nWe 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.**"}, {"review_id": "Jwar7Z988t", "reviewer": "Reviewer_Yes9", "summary": "This paper focuses on designing a graph foundation model (GFM) for node tasks. The authors approach this problem from the viewpoint of equivariance, where they argue that three main types of symmetries are necessary for proper generalization: (a) Node permutation-equivariance, (b) Label permutation-equivariance, (c) Feature permutation-invariance. For example, the labels can of course differ based on the graph and task at hand. Also the node features can vary considerably by both semantic meaning and dimension. As such, respecting these symmetries are helpful to learning a GNN that are general and not specific to the graph itself (thus improving generalization). The authors propose a new model, TSNet, that respects these symmetries. The authors detail some experiments that show promising performance of their method.", "questions": "1. Can you report the performance in the same manner to GraphAny or a similar setting (as noted in Weakness 1). Then for each, test them on the holdout datasets and average the results. This will form a much more comprehensive set of results.\n\n2. Can you run some ablation studies on the framework. Specifically, as noted in Weakness 2, it would be interesting to ablate some of the symmetries and the feature-label mixing.\n\n3. This is fairly open-ended, but I'd appreciate some insight (preferably empirical) as to why one should choose TSNet over GraphAny (assuming the performance is still essentially the same as in the paper). What scenarios does TSNet outperform GraphAny? One suggestion may be to check few-shot scenarios, where GraphAny may struggle (this is just an idea).  \n\n4. Additional runtime/complexity results would be appreciated but are not necessary.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n---------\n\n1. I really like the motivation behind this work. Graphs can vary wildly in their properties, node features, and the downstream labels. Because of that, it makes sense to design a method that respects fundamental symmetries that help create a moe *general* GNN. As the authors note, this is a good way of learning a \"general graph vocabulary\", since respecting these symmetries help learn information that are more high-level and not too specific to each graph. I therefore think the approach introduced by the authors is really promising and intuitive.\n\n2. The paper is written and explained quite well. It makes reading the paper very easy and quite enjoyable. \n\n3. The theoretical proof in Theorem 4.2, that shows TSNet is symmetry preserving, is appreciated. I also find it's interesting that they find a mistake in the universality proof from *Maron et al. [2020]*, and show that the proof is true under certain conditions ($H = S_D$).\n\n\nWeaknesses:\n----------------\n\n1. **Insufficient Main Experiments**: I don't think the authors provide enough experiments for their *main results*. The authors test when training on Cora and performing zero-shot classification on the other 27 datasets. However, an issue I have is that they only test when pretraining on one dataset (being Cora). However, why should we choose Cora? Why not another dataset? My point being, while the results may be good when training on Cora, maybe they won't be when training on other datasets. It's the same logic as running an experiment over $k$ random seeds, maybe Cora is just a \"lucky seed\". An alternative, used by GraphAny, is to instead train 4 different versions of their model each on a different dataset (i.e., Cora, Wisconsin, Arxiv, and Products). I recommend the authors either use this approach or a similar type of approach for a fairer and more robust comparison.\n\n2. **Lack of Ablation Studies**: The authors introduce many components in their framework. However, no ablation study is given. This is important, as it's unclear of the benefit of various components. This is very important for some cases as it's unclear what is really driving the performance. For example, (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? (c) How important is the feature-label mixing?. This last one is very important to me, as the authors adopt the approach from GraphAny by solving the least squares problem. If this is a big reason for the high performance, then it could suggest that many of the claims about the importance of symmetry for this problem may not be true (to an extent). Without any of these studies, I'm unsure how to practically evaluate the proposed framework.\n\n\n3. **Lack of Clear Benefit over GraphAny**: I'm not arguing that SOTA performance isn't necessary for a framework/paper to be good. Furthermore, I think the proposed method is interesting on its own merits. However, the performance compared to GraphAny is nearly identical and nonetheless perfectly within variance. This raises an obvious question which is, *why should we use TSNet*? The authors don't really answer this. The authors say, on line 111, that as opposed to their proposed framework, the design of GraphAny is \"very limiting for the model design space\". I understand their point, but it's really hard to argue without any tangible experimental results that show when TSNet can outperform GraphAny. I strongly encourage the authors to try to find some empirical evidence as to when/why their method is better and preferred. \n\n\n4. **Lack of Discussion on Model Complexity**: This is a fairly minor weakness and has little effect on my score. But I thought I'd mention it since including it would, imo, strengthen the paper. Basically, some discussion on this or some efficiency experiments would be appreciated. It's not necessary, but TSNet does introduce a little more overhead when preserving symmetry, so it'll be useful to see how this effects runtime for practical usage.\n \n\nOther:\n-----\n\n1. This is a small detail, but I'd recommend changing the title to reflect that the model is only designed for node-level tasks. As of now, I think the title slightly oversells the model to be more encompassing than it actually is. A good change would be \"Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models for **Node-Level Task**\". This is just my opinion.", "was_revised": true, "final_justification": "Overall, I like this paper a lot and the authors did a great job during the rebuttal. To me it's a clear accept.", "rebuttal": "We thank the reviewer for their thorough review, for recognizing our theoretical contributions and rigour and for describing the paper as an “enjoyable read.”\n\n> 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...\n\n> Q1: Can you report the performance in the same manner to GraphAny ...\n\nThanks 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.\n\n||cora|roman-empire|chameleon|wiki-cs|average|\n|-|-|-|-|-|-|\n|TS-Mean|65.96±1.90|64.63±1.33|65.66±2.60|64.52±2.34|65.19±2.04|\n|GraphAny|64.63±1.42|65.15±1.61|65.80±1.55|65.11±1.53|65.17±1.53|\n\nThese results further validate that TS-Mean and GraphAny are consistently competitive in the low-data regime.\n\nThis 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.\n\n> 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?\n\nThese 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.\n\nThat 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.\n\n||GraphAny|TS-Mean|TS-GAT|TS-SGC|TS-GCN|TS-GCNII|\n|-|-|-|-|-|-|-|\n|Average|65.83±1.66|**66.21±1.93**|65.85±2.38|64.71±3.06 |64.39±2.61|62.45±3.43|\n\nThe 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. \n\n> (c) How important is the feature-label mixing?...\n\n> Q2: Can you run some ablation ... ablate some of the the feature-label mixing.\n\nAs 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.\n\n||random|LS|LS+bias|LS+bias+mean|\n|-|-|-|-|-|\n|Average|20.98|58.39±1.24|58.75±1.58|59.00±2.11|\n\nWe 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. \n\n||plain|+LS|+LS+bias|\n|-|-|-|-|\n|TS-Mean|55.43±1.12|63.21±2.08|**66.21±1.93**|\n|TS-GAT|55.19±1.54|62.66±2.20|**65.85±2.38**|\n\nThese 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.\n\nNext, 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.\n\nWe 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. \n\n> W3: Lack of Clear Benefit over GraphAny: ... why should we use TSNet? ... it's really hard to argue without any tangible experimental results ...\n\n> Q3: ... What scenarios does TSNet outperform GraphAny? ...\n\nThis 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. \n\nWe 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. \n\n|#Train graphs|1|3|5|7|9|\n|-|-|-|-|-|-|\n|GraphAny|66.62|**67.34**|67.29|67.28|67.22|\n|TS-Mean|67.23|67.36|67.82|68.42|**68.57**|\n\nResults 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. \n\nInterestingly, 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.\n\n> W4: Lack of Discussion on Model Complexity: ... some discussion on this .. would be appreciated...\n\nThank 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.\n\nFor 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.\n\nThe 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.\n\nWe will include in the final version a comprehensive theoretical analysis of the runtime, comparing our method with GraphAny and classical GNNs.\n\n> 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\"...\n\nWe appreciate your thorough review and will therefore change the title as per your suggestion for the camera-ready version.\n\n**We will include all the suggestions you've provided and experimental results in the camera-ready version with the appropriate discussion.** \n\nWe hope our responses address your concerns and would greatly appreciate your reconsideration of the evaluation and increasing your score."}]

Author rebuttal:

Meta-review: This paper proposes a method  for designing graph foundation models (GFMs) for node classification and regression tasks. The paper argues that a GFM must respect three symmetries: it must be equivariant to node and label permutations and invariant to permutations of input features. The TSNet model is then introduced, a universal approximator on multisets that respect the aforementioned symmetries. The proposed method is applied to the multisets of features induced by the local graph aggregation and can be used to transform any GNN model into a GFM. The proposed method is evaluated on a large number of real-world node classification datasets.

The reviewers agree that the development of GFMs is an important topic, and this paper makes a significant contribution in this direction. One of the strengths of the proposed method is that it is very general since it can transform any GNN model into a GFM. TSNet's expressive power is supported by theoretical guarantees, as it is proven to be a universal approximator on multisets that respect the considered symmetries. The reviewers appreciate the breadth of the experiments, which cover 27 node classification datasets. They also acknowledged that the paper is generally well-written and easy to follow. The main weakness of the paper is that it can currently deal only with node-level tasks. The reviewers also raised concerns about the computational complexity of the proposed method, the marginal improvements over GraphAny and the empirical validation of the method. Specifically, the method was not evaluated on any node regression dataset, no social media datasets were considered, the method was compared against a single baseline, while the different methods were trained only on the Cora dataset which raises questions about the significance of the results. Moreover, no ablation study was conducted to assess the contribution of the different components to the method's performance.

During the rebuttal, the authors conducted further experiments and addressed most of the raised concerns. For instance, they conducted experiments in which the different methods were trained on datasets other than Cora, as well as on subsets of the full dataset collection to demonstrate that the proposed method achieves greater performance gains over GraphAny when trained on multiple graphs. They also introduced three new variants of the proposed method. They claimed that there is a lack of node regression datasets, while they also conducted an ablation study to isolate the effect of the proposed method's key components. Finally, the authors acknowledged that the method cannot be applied to graphs of the scale seen in social media datasets. 

To summarize, the problem addressed in this paper is highly relevant. The paper offers a novel solution for the development of GFMs. As already discussed, one of the main limitations of the proposed method is that it can only deal with node-level tasks. However, given that many problems can be framed as node-level tasks, it is likely that the method can have significant practical relevance. While the proposed method is evaluated on a large number of datasets, I believe that the evaluation of the method could be further improved. GFMs are expected to be trained on large amounts of data and subsequently employed for inference on new, unseen data. This paper follows the opposite direction. The model is trained on a single dataset and is evaluated on a very large number of datasets. In their response, the authors reported new experiments where the models were trained on increasingly larger subsets of datasets. However, further experiments are necessary to fully evaluate the model's potential, and I would suggest the authors conduct these experiments and report them in the next version of the paper. Based on the above, I am leaning towards acceptance. I strongly suggest the authors incorporate reviewer feedback into the next version of the paper.
Decision: Accept (poster)