Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Authors: Yangyi Shen
Jincheng Zhou
Beatrice Bevilacqua
Joshua Robinson
Charilaos Kanatsoulis
Jure Leskovec
Bruno Ribeiro
Venue: ICML 2025 poster (2025)
Keywords: GNN
zero-shot
graph foundation models
Primary area: deep_learning->graph_neural_networks
TL;DR: We propose a novel method that can zero-shot generalize to test attributed graphs with different node features than those seen in train.

Abstract: Traditional Graph Neural Networks (GNNs) cannot generalize to new graphs with node attributes different from the training ones, making zero-shot generalization across different node attribute domains an open challenge in graph machine learning. 
In this paper, we propose STAGE, which encodes *statistical dependencies* between attributes rather than individual attribute values, which may differ in test graphs. By assuming these dependencies remain invariant under changes in node attributes, STAGE achieves provable generalization guarantees for a family of domain shifts. Empirically, STAGE demonstrates strong zero-shot performance on medium-sized datasets: when trained on multiple graph datasets with different attribute spaces (varying in types and number) and evaluated on graphs with entirely new attributes, STAGE achieves a relative improvement in Hits@1 between 40% to 103% in link prediction and a 10% improvement in node classification compared to state-of-the-art baselines.

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Yangyi Shen! 1
Jincheng Zhou? Beatrice Bevilacqua 2 Joshua Robinson Charilaos Kanatsoulis'
Jure Leskovec'
Bruno Ribeiro?
Abstract
Node attributes in test graphs can differ from those in train- ing graphs in four key ways: (1) their types (e.g.. continuous vs, categorical variables); (2) their names (c.g., RAM spec- ifications in ecommerce graphs and clothing size in retail graphs, as illustrated in Figure I); (3) their semantics, where attributes with the same name can have different meanings across domains for instance, the meaning of size differs substantially between electronics and clothing domains; (4) their cardinality, as graphs may contain varying numbers of node attributes. These challenges make it difficult to define a unified input space that enables zero-shot generalization to unseen attributed graphs
Traditional Graph Neural Networks (GNNs) can- not generalize to new graphs with node attributes different from the training ones, making zero-shot generalization across different node attribute do- mains an open challenge in graph machine learn- ing. In this paper, we propose STAGE, which en- codes statistical dependencies between attributes rather than individual attribute values, which may differ in test graphs. By assuming these depen- dencies remain invariant under changes in node attributes, STAGE achieves provable generaliza- tion guarantees for a family of domain shifts. Em- pirically, STAGE demonstrates strong zero-shot performance on medium-sized datasets: when trained on multiple graph datasets with differ- ent attribute spaces (varying in types and num- ber) and evaluated on graphs with entirely new attributes, STAGE achieves relative improve- ment in Hits @ between 40% to 103% in link prediction and 10% improvement in node clas- sification compared to state-of-the-ar baselines.
For these reasons, training graph models that zero-shot generalize to new graphs with unseen attribute domains re- mains an open challenge. Recent approaches address this problem using various strategies. One approach is to ignore node attributes to focus solely on graph topology, but this strategy may be leaving valuable node attribute information unutilized. Another line of work seeks unify input spaces by converting graphs and attributes into text representations, which are then processed by pretrained text encoders (Chen et al., 2024a; Huang et al., 2023; Liu et al., 2024; Zhang et al., 2023). While promising, these approaches may strug- gle with numerical attributes (Collins et al., 2024; Gruver et al., 2024; Schwartz et al., 2024). Recently, Zhao et al. (2024b) proposed an analytical approach for making predic- tions on new graphs with potentially new attributes. How- ever, this approach sidesteps the fundamental challenge of creating a unified input space.
1. Introduction
Zero-shot generalization refers the ability of the model to handle unseen test data without additional training adap- tation (Larochelle et al., 2008; Xian et al., 2017; Wang et al., 2022). An essential prerequisite for zero-shot generalization is a unified input space where models can learn and transfer prediction patterns across domains. While this challenge has been addressed in areas like natural language through tokenization techniques that represent any text through fixed vocabulary (Samuel & Øvrelid, 2023), graphs present unique challenges in achieving such unified input space.
In this paper, we introduce STAGE (Statistical Transfer for Attributed Graph Embeddings), which transforms node attributes from their "absolute" natural space into a rela- tive space that captures statistical dependencies between attributes. For instance, as illustrated in Figure 1, these dependencies manifest themselves correlations driving purchases across domains, which remain invariant even when the purchased items and their attributes change. In practice, STAGE represents such statistical dependencies through a two-step process that transforms node attributes into -iee-diinnsional edge embeddings, achieving a uni- fied input space alongside provable invariance to changes in attribute values (including their types, names and semantics), as well as to permutations of attribute order and permuta-
Attributes in graphs can vary significantly across domains.
'Department of Computer Science, Stanford University, Stan- ford, USA *Department of Computer Science, Purdue Univer- sity, West Lafayette, USA. Correspondence to: Yangyi Shen <pyyshen soyyshe@@stanforddddur. stanford.edu>..
Proceedings of the 4rnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
30 $120K
age:
feshion news: regular club, stwa.s
feanioon, news: regular club status: active height
Ristme
Insome Jovel: STOK
activa GN8
(011 Jevel:
collage
Alice
jdu_levet high school
Bob
height
Civire
622
view
purchasa
vtaw
view
ViDw
purchasa
view
purchese
purchaso
Dei0e:
$1 1999
DRiGe:
$698
colour group: red
colourgroup black
sine:
XI
batlary:
27 18 mAh
bellery:
2500 mAh
product_ _yppe shorts
Ciothes
product typa:
jeans
Ciathic
Smartphone
Smartshane2
(a) Train
(b) Test
Figure 1: The task of zero-shot generalization attributed graphs with unseen attributes. Attributes test are different than those in train in types and semantics, but attributes associated with an edge are highly correlated in both train and test (e.g. income level is positively correlated to phone price in (a) and height is positively correlated to size in (b)). Our STAGE learns these statistical dependencies among attributes to perform zero-shot transfer across distinct attribute domains.
tions of node identities. Specifically, STAGE first constructs a weighted STAGE-edge--rappl for each edge in the input graph, where the nodes represent attributes of the edge end- points and the edge weights capture dependencies between the attributes. Then, STAGE uses an additional shallow GNN to generate embeddings for each STAGE-edge- graph. Finally, STAGE applies the original GNN to modified input graph, which contains only the newly generated edge embeddings but not the node attributes.
into a fixed-dimensional pairwise embedding
P : (x" """"""" +" IR 2
(I)
By using pairwise embeddings. STAGE can model relation- ships between attributes belonging different nodes. For instance, it can capture the relation between the attributes of the customer node Alice and the attributes of the product node Phonel in Figure 2(a), such as the correlation between income level and price. We design the mapping P by build- ing graph based on the pairwise pdf attribute descriptors. Viewing node attributes through their pdf's maps potentially non-aligned node attribute spaces into a universal space of densities, enabling consistency across diverse domains. The modeling of probabilities generalizes the learning of rules like "people with higher income level tend to buy expen- sive phones,' to abstract relationships like "high values in X1 correlate with high values in X2". enabling knowledge transfer across domains with different attributes.
The complexity of STAGE is linear in the size of the input graph and quadratic in the number of attributes, as it cap- tures pairwise statistical dependencies between attributes over the edges of the graph. This makes STAGE particu- larly well-suited for small to medium-sized datasets, where strikes a balance between computational feasibility and strong generalization performance.
We prove that STAGE can learn domain-independenn rep- resentations for certain types of domain shifts, enabling zero-shot generalization. Experimentally, for link prediction in e-commerce networks spanning six distinct product do- mains, STAGE achieves up to 103% improvement in Hits @ compared to the strongest baseline. node classification tasks on social networks, STAGE achieves approximately 10% better performance than the strongest baseline.
Concretely, let A and B be random pair of nodes jointly and uniformly sampled from the edge set, (A, Unif( E). Let x denote the random variable of the i-th attribute value of random node A, and x² the j-th attribute value of random node B. Given a specific pair of distinct nodes u, v E V and specific attribute values x/ and zj. we define p(x!'' (="))"")) from the conditional probabilities as fol- lows, accounting for mixture of totally ordered (e.g., scalar) and unordered (e.g., categorical) attributes
2. STAGE
Let G = (V, E)) an attributed graph, where V is the set of nodes, E the set of edges, and X = {x") Teev the set of node attributes " for each node v E V. We assume that all xx belong to some measurable space of dimension 2 1.
p(=)(=))) == P(x S < xx1x]] S 2))) if both attribute and j are totally ordered.
p(=;(=²)) := P(
a 1x1x < 2z). attribute i un- ordered and attribute j totally ordered.
To design model capable of generalizing to test graphs that may have node attributes living in different space than X, we propose a projection map that transforms the node attributes (x", x²) of the endpoints of an edge (u, v) E E
p(=:' [<)))>)]) = P(x < x |x 2²). ) if attribute is totally ordered and attribute j is unordered.
For brevity omit the distribution (A, B) Unif( writ- ing TP instead of P (ai) from now.
2

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
P Pincum
P Pinousssppia
Allce
30
Alice
Bob
income level: $120K
Alicw,Alioe Alice
Alllon,hone
Alce, Phonat
purchase view
view
Galeeo ind
M2 (G Ahon,,
Abon, Ahbon, Photel
Bob.Pbosc2
Bus Paunn
Plecannsiie
AkouPhonet
(AA Mirem X 120K x S 1299)
Phone K
RAM:
$1299
3GB
Phone2
P Prxceaa ape
AlesAlke
7 A--Tur (M (Nucoms 120K Xagee S 30)
( = (V E, (F" (6a))))
Phonet
Pocana
Aa- (X 120K)
(b) S grggg-hdge- G(grAiiePPuaz)) of the edge (Alice, Phone1)
(c) STAGE-edge-graph embedding as edge feature for GNN forward propagation
(a) Input attributed graph
Figure 2: Given an input attributed graph G (a), STAGE builds a STAGE-edge-graye (b) for every edge in G. Nodes in STAGE-edge- oodgegraphh correspond to attributes of the two edge endpoints, and the node and edge attributes the empirical marginal and conditional probabilities of attribute values (Equations (2) and (3)). STAGE applies the intra-edge GNN on STAGE--dge-gran (b) to obtain an edge embedding for each input graph edge, and then applies the inter-edge GNN on the modified graph containing these edge embeddings but not the node attributes (c). Details are provided in Algorithms and 2.
p(a"' [mj) = P(x; = xx|x]] = xz), both attribute and j are unordered.
Definition 2.1 TTrAGE-edge-gaappee Given a pair of nodes u, v E V, a STAGE-edge-grape for (u, v) is a fully con- nected, weighted, directed graph G(S")) with 2d nodes, where node i has scalar attribute S and edge (i,j) has scalar attribute Suy.
If u = v, we change the sampling distribution to (A) Unif(V)) and let B A so that STAGE can also model dependencies between attributes of the same node. i j. change the conditional probability to p(="") == P(x, rF") if attribute i is unordered and p(=;)) = (x < az)) if attribute is totally ordered. This allows STAGE to also
STAGE algorithm. As illustrated in Figures 2(b) and 2(c), STAGE uses a STAGE-edge-grren for each edge in the input graph a two-stage process to produce attribute-domann transferable representations. First, STAGE uses GNN to obtain embeddings for each STAGE-edge-grapp These edge embeddings replace the original node attributes, result- ing in modified graph which is fed into second GNN to solve the overall task, producing node, link, graph representation. The two steps of STAGE are as follows:
model each attribute independently through its pdf or cdf.
In practice, these probabilities can be empirically esti- mated from the input data. For the node-pair u, v we define conditional probability matrix Sue with indices i,j (L...., 2d), i j. organized such that indices to d correspond to attributes of node u and indices d + 1 to 2d correspond to attributes of node o:
1. (Intra-edge) Each G(S"))) is processed with a GNN Mi to produce edge-level embeddings "0 (G(((S
p(ay | xz)) S
if S d and j < d, if < i 2d and < $ 2d,
2. (Inter-edge) A second GNN M2 processes the modi- fied graph G' (V, E, (w.,)e))) i.c., the original graph without node attributes, but equipped with the learned edge embeddings to give final representation (GG) = M2(G').
p( x)-a) p(r x
if S and d < 2d, if Ed<ist 2d and s d.
and for the diagonal i j we define,
The two GNNs Mi and M2 are trained end-to-end on the task. Note that M1 can be any GNN designed to produce whole-graph embeddings and can take single-dmensionall edge attributes, whilst M2 can be any GNN that can take edge embeddings as input.
(p(af) p(xt)
ifi S d, ifi d.
STau kj
(3)
The matrix Swe is the core node-pair data representation STAGE uses. This matrix is used to define a graph struc- ture which we call a STAGG-edgge-rapp illustrated in Fig- ure 2(b), which captures, for the pair of nodes u and v. the interactions among all pairs of attributes.
Integration with language models. While STAGE can incorporate LLM embeddings for textual attributes, our ex- periments show STAGE-edge-grape numerical and categorical data (Section 4). The approaches can be complementary initialize node embeddings with
performs better on
3

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
LLM embeddings for textual attributes and edge embed- dings with STAGE=-ddge-raan for non-textual attributes.
Consider domain with m entities (e.g.. products in an appliance store), where each entity is characterized by d attributes. Specifically, an entity can be represented by (row) vector of random attribute variables, x" = where x describes the i-th attribute of entity u that takes on values from the i-th attribute space F, S R. With these variables, we define the (random) matrix X = [[x)", (x²)" ..... (x".,, (x""")" of shape m x d. A Alternaively, we can view X column-wise, where each at- tribute i corresponds to a (column) random vector X; [x], x,,x,.... xx,,...,x71? x.. Next, we introduce the order statistic for these attributes: let Xi(k) denote the k-th order statistic of (x!....,,x!) For instance, X(()) = .x.,f"""..."?"
Modelling pairwise relations. SSe is only computed for edges (u, v), and so can only model pairwise relations be- tween nodes connected by an edge. In some cases, such as bipartite graphs, we find beneficial to add extra edges be- tween nodes of the same type (see Section 4 for details). In general, higher-order relations could also be modelled simi- larly, albeit at increased complexity. We leave exploration of higher-order relations to future work.
[X), x....., xz),
3. Statistical Underpinnings of STAGE
This section explains how STAGE achieves domain transfer- ability. The central result is to show that STAGE generates representations capable of measuring dependencies among node attributes in graphs. This means that STAGE can ignore "absolute" attribute values, while still generalizing through analogous statistical dependencies of the attributes.
Given an input graph G = (V, F. X), we regard as a sample from some unknown distribution over all at- tributed graphs with m entities and d attributes, where X is random variable with X = [x1,..., F.)) Con- sider the edges in E as samples of pairs of nodes that give rise to the multiset of attributes of the endpoint nodes, E = ff(=", x²) | (u, v) E E}} Together with the order statistics, we now define the attribute hypergraph as follows:
Our first step (Section 3.1) connects measures of statistical dependencies with novel graph regression task. Then, Sec- tion 3.2 shows that our TTAGG-eddee-raphee (Definition 2.1) can lead to a compact model for this regression, with a vari- ant that is invariant to a class of shifts between train and test attribute domains. The following theoretical results are meant to provide insights and are restricted to domains with a fixed number of attributes to simplify the proofs, extending them to variable size spaces is left as future work. Detailed proof's are provided in Appendix B.
Definition 3.1 (Attribute hypergraph Fe). Given a multiset of attributes of the endpoint nodes E = (((x") (u, v) E F} of m entities with totally ordered attribute spaces, the feature hypergraph F& is defined as follows. First, we label the graph with m. Then,
For each order statistic T((a) of attribute i and order k (1 S. k S m). there are 2 nodes, namely (i, k, 1) and (i, 2,). In total, there are exactly 2md nodes in Fe (attribute values need not be unique). Nodes (f, k, 1) and (i, k, 2) store a single attribute mark their order: k.
3.1. Statistical Dependence as Graph Regression
We begin by introducing the framework for building what call feature hypergraphs. We will show that feature hypergraphs can sufficiently encapsulate the statistical de- pendencies between attributes, while only leveraging the relative orders rather than the numerical values of the at- tribute, enabling it to be invariant to order-preserving trans- formations (formally defined in Definition B.2) to achieve domain transferability. In the following, we assume one attribute space defined over totally ordered set (e.g., Rdd for d 2 1, where the total order < 7 is well defined), since the invariances of unordered sets are a special case (as these do not need order-preservee describe how feature hypergraphs are built, we start with the concept of order statistic, which captures the relative ordering of the attribute values.
Let (1)) be the order of the attribute value x.' i.e., (((o((u)) = x.. For each pair of attributes of endpoint nodes x²" E, there is a hyperedge Huv in Fg defined as
Hae == ((1,
(2), (2, 22) (d.), 1), (d, 2)), (4)
transformations). Before we
Our first observation is that the feature hypergraph in Defi- nition 3.1 perfectly captures the order statistics of the set E but discards the actual values of the attributes.
We now consider statistical tests that measure dependencies of the attributes of endpoint nodes. As an example, consider that if (x" x²) E E are samples (not necessarily indepen- dently sampled) from bivariate distribution (x, x') F, one may be interested in testing the hypothesis
Order statistic (David & Nagaraja, 2004). Let be a sequence of m 2 2 random variables
X1, x2...., Xm, from some unknown distribution F' over a totally ordered set (e.g.. a convex set F C R). Its order statistics are defined as the sorted values X(1) & X(2) S .... S [(m), where X(k) denotes the k-th smallest value in the m samples.
Ho: : F(x,x)) = (x)),,
4

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
i.e., that and x' are independent. Bell (1964); Berk & Bickel (1968) showed that over totally ordered sets, mea- sures (e.g.. p-values) of such hypothesis tests for pairwise independence (Ho above) and higher-order order conditional in- dependence between multiple variables, have invariances that simplify the data representation to such a degree that the original values are discarded, retaining only the order relationships between the variable values. Any such test is therefore a rank test, i.e., it relies only on indices of the order statistic, not on the numerical values of the attributes.
ages GNN on STAGE-edge-graphs obtain edge-level embeddings. However, the use of unique attribute identifiers in the STAGE-edge--rapbhe disrupts invariance to permuta- tions in attribute order (e.g., U.S. shoe size appearing as the first attribute in one dataset and U.K. shoe size as the last attribute in another), thereby limiting its domain transfer- ability. More broadly, we now describe all the invariances we want for STAGE to have in order to be robust to a class of attribute domain shifts.
COGG invariances. STAGE-edge-graphs facilitate domain transfer to distinct attribute domains. Intuitively. the full set of invariances required for domain transferability over G = (V, X) consists of: (1) invariance or equivariance to transformations of attribute values that preserve the order statistic, (2) invariance or equivariance to permutations of attribute orders (columns of X), and (3) invariance or equiv- ariance to permutations of nodes in the graph, affecting V (and consequently E) and the rows of X. These invariances are formalized in Definition B.5 in Appendix B.4 through the actions of component- wise order preservin groupoid for graphs (COGG). Importantly, groups are insufficient to capture these invariances because they assume transforma- tions act within a single attribute domain. However, we are interested in transformations across distinct attribute spaces. Groupoids generalize groups by allowing these transforma- tions between different domains, making them the natural choice for modeling the required invariances.
Our first theoretical contribution is the observation that any statistical test that focuses on measuring the (conditional) dependencies of attributes of endpoint nodes in E can be de- fined as a graph regression task over the feature hypergraph FE of Definition 3.1.
Theorem 3.2. Given multiset of attributes of the endpoint nodes& E, the corresponding feature hypergraph F& (Defini- tion 3.1) and a most-expressive hypergraph GNN encoder Mo- (Fg), then any test T(E) that focuses on measuring the dependence of the attributes of the endpoint nodes of E has an equivalent function h within the space of Multi- layer Perceptrons (MLPs) that depends solely on the graph representation Mc-(Fe) i.e., 3h E MLPss s. T(E)= h(Ma- (Fe)).
Next we show that the hypergraph Fe can be simplified with STAGE-edge--ee edge-gragg and that the ability to compute de- pendency measures can be made invariant to certain domain shifts between train and test.
We now introduce our final theoretical contribution which establishes that STAGE achieves invariance to COGGs by design. This result shows that STAGE can provably achieve the zero-shot transferability to the class of attribute domain shifts defined by COGGs-type transformations.
3.2. Transferability of STAGE
The feature hypergraph Fe in Definition 3.1 is used obtain maximal invariant graph representation via hypergraph GNN. This solution has a high computational cost from the use of hypergraph GNNs. Fortunately, we show that by assigning unique attribute identifiers to label the nodes of our STAGE-edge-graphee G(See)) (Definition 2.1), STAGE- edge-graphs are as informative as the corresponding feature hypergraphs, preserve the same invariances, while allowing the usage of (non-hypergraph) GNN encoders.
Theorem 3.4. STAGE is invariant to COGGs (Defini- tion B.5).
The proof sketch is as follows. From Theorem 3.3, STAGE achieves invariance to changes in attribute values, including their types, names, and semantics. Then, by dropping the attribute identifiers in STAGE-edge eage---dgg-rapphs, we sacrifice maximal expressivity but ensure that STAGE is invariant to permutations of the attribute order. Finally, since STAGE employs second GNN on the original input graph, using the emheddings of the STAGF--dgeegraphee while omitting the original node attributes, STAGE achieves invariance to node permutations. Thus, the method invariant to COGGs.
Theorem 3.3. Given the attributes of the endpoint nodes (Definition 3.1) of a graph G = (V, E, X). there ex- ists an optimal purameterization 0% 0z for a most ex- pressive GNN encoder M9 and a most-expressive mul- tiset encoder M respectively, such that Moy,0 (G) == Ma, 1 (([M), (G(S"))) (u, u) E F}]) such that any test TEE) that measures the dependence of E's attributes of the endpoint nodes has an equivalent function h within the space of Multilayer Perceptrons (MLPs) that depends solely on the graph representation May.o; (G), ie., 3h E MLPs s.t. T(E)= = h(Ma; 0; (G)).
4. Experiments
We demonstrate the effectiveness of STAGE across multiple experimental settings, focusing on small to medium- sized datasets. While the computational complexity scales lin- early with the graph size and quadratically with the number of attributes, training on these datasets introduces only mod-
Theorem 3.3 motivates the design of STAGE, which lever-
5

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Model random
NEFNet raw
gaussian
NBFNeel-stuccuu
NBFNet: lim
NEFNet nomalized
NBFNet STAGE
hits@@1
random
bed
desktop
refrigerators
smartphone
H&M
Test Graph Domain
Figure Zero-shot @its@1 performance (higher better) of STAGE and baselines, trained on four (or five) distinct E-Commerce Store domains and evaluated on the held-out domain (or H&M dataset). NBFNet-STAGE. consistently achieves the highest zero-shot accuracy across all test domains, with up to 103% improvement.
erate computational overhead (e.g., 7.83% slower than the fastest baseline in link prediction; see Appendix H). There- fore, STAGE is highly effective in these settings, achieving strong generalization performance. In the following, we present our main results and refer to Appendix D for details. Our code is available https: / /g thwb.com.////cc snap- stanford/ s stage-gnn/.
Social network datasets (node classification): Friendster and Pokec. We evaluate STAGE on two online social networks from different regions and user bases: Friend- ster (Teixeira et al., 2019) and Pokec (SNAP, 2012). Friend- ster nodes have attributes such as age, gender. interests, while Pokec nodes have public profile status, completion percentage, region, age, and gender. The task is predict node attribute common to both social networks using net- work structure and remaining node attributes. Since only age and gender are shared, we create two tasks: mask and predict gender (presented in this section), and mask and regress on age (discussed Appendix E).
Datasets. To evaluate zero-shot generalization to graphs with new attributes, we consider datasets with distinct domain-specifor attributes but a shared task. Our datasets contain graphs with up to nodes, 50k edges, 16 attributes, representing small to medium-size real-world scenarios where STAGE is particularly effective. Due space con- straints, introduce them below and refer to Appendix C.
Baselines. We compare STAGE to several baselines de- signed to handle new node attributes. (1) raw: Projects each raw node attribute into fixed-dimensional space with linear transformation, before summing across the projected dimensions. (2) gaussian: Use Gaussian noise as node attributes (Sato et al., 2021; Abboud et al., 2021). (3) struc- tural: Ignores node attributes entirely, using only the graph structure. (4) llm: Converts node attributes into textual descriptions and obtains embeddings using pretrained en- coder-only language model, taking only the node attributes as input (without graph structure) due to prompt length lim- itations, similar to PRODIGY (Huang et al., 2023). (5) nor- malized: Retains only continuous attributes and standardize them. For fair comparison, all methods utilize the same underlying GNN architecture, NBFNet (Zhu et al., 2021c) for link prediction and GINE (Hu et al., 2020) for node classification. In Appendix F,, report additional experi- ments with other architectures. In addition to these baselines, we evaluate our approach against GraphAny (Zhao et al., 2024b), a recent method for domain transferability in node
E-Commerce Stores dataset (link prediction). We use data from multi-category store (Kechinov, 2020) containing pustomer-proouet product interactions (purchases, cart additions, views) over time. To simulate distinct single-category retail- ers, we partition the dataset into five domains, each repre- senting specialized store: shoes, refrigerators, desktops, smartphones, and beds. Each domain has its own customer base and product-spedee specific attributes (e.g., smartphones have display type; shoes have ankle height). The task is to predict future customer- customer-product interactions from past actions.
customer-
H&M dataset (link prediction). We use the H&M Person- alized Fashion Recommendations dataset (Kaggle, 2021), which contains transactions from large fashion retailer, to evaluate the zero-shot performance of models trained E-Commerce Stores. All attributes. except for "price", dif- fer from those in E--ommerce Stores. The task remains to predict customer-product interactions from past actions.
6

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
classification tasks, but not applicable to link prediction.
of 99% in Hits@1 over Adamic Adar (0.466 0.2349), which performs the best among traditional heuristic meth- ods on the H&M dataset. Similarly, STAGE outperforms Adamic Adar by 48% in MRR (0.4703 vs. 0.3184) further confirming the its superiority over classical link prediction heuristics in zero-shot scenarios.
4.1. Zero-Shot Link Prediction on Unseen Domains
We evaluate the performance of all methods on zero-shot generalization on the E-Commerce Stores dataset, training on four categories, and testing on the held-out fifth category.
Results. As shown in Figure 3, STAGE consistently out- performs all baselines in zero-shot Hits @1 across all test domains. Notable improvements include: 103% gain when testing on the smartphone category (0.51 vs 0.25 Hits @ I), 40% on bed (0.44 vs 0.31), and 33% on desktop (0.59 vs 0.44) compared to the strongest baselines.
4.3. Zero-Shot Node Classification on Unseen Domains
To validate our approach beyond link prediction and E- Commerce scenarios, we benchmark on a node classification task using two social network datasets, where the goal is to predict user gender. We train models on Friendster and evaluate zero-shot Pokec.
In Table 1, we report the average performance of each model, calculated by taking the results in which each domain is held out once and averaging the scores. Our evaluation also in- cludes popular non- con-parametric link prediction approaches such as Common Neighbors, Adamic Adar, and Person- alized PageRank, with results showing that STAGE sub- stantially outperforms classical heuristic methods by 54%, 51%, and 3837% respectively on Hits @1 1, while maintaining similar performance advantages on MRR. Overall, STAGE achieves 41% % higher average Hits (0.46 vs 0.33) and 29% higher MRR (0.50 vs 0.38) against the strongest baseline (normalized), with lower variance across seeds. This empha- sizes the benefit of STAGE in transforming node attributes into a unified input space using learned edge embedding via including its stronger attribute repre- sentation capabilities than M-bsed encoding approaches in the medium-sized graphs considered in this work.
Table 2 shows that STAGE achieves a 10.3% improvement over the best baseline (and lower variance), also surpassing the task-specific model GnaphAny (Zhao et al., 2024b) and the cross-domain pretraining method GCOPE (Zhao et al., 2024a). This indicates that STAGE effectively captures attribute dependencies also in node classification tasks and outperforms all approaches by leveraging its unified input space obtained by the usage of the STAGE-edge-gran
4.4. Generalization When Training on Multiple Domains
We examine how the model performance varies with the number of training domains in E-Commerce Stores.
As shown in Figure 4, STAGE obtains improving zero-shot performance (both Hits@ and MRR) with more training domains. While not the only method showing improve- ment, STAGE exhibits notably tighter interquartile ranges compared to the only other method exhibiting better perfor- mance with increasing domain (gaussian) at higher domain counts. Additionally, STAGE's s lower whiskers consistently rise with more domains, showing also that its worst-case scenarios improve with more training data.
4.2. Cross-Dataset Zero-Shot Link Prediction
We evaluate models trained on E-Commerce Stores for zero- shot prediction on the H&M dataset, which has distinct customers, products, activity patterns and attributes.
Table shows that the performance on H&M of STAGE when trained on E-Commerce Stores is virtually identical to its performance on the held-out category in E-Commerce Stores (0.46 vs. 0.46 Hits@ 1). This highlights the robust- ness of STAGE to domain shifts, as it maintains similar performance when transitioning from E-Commerce Stores, which primarily feature household items, electronics, and shoes, to H&M, which focuses on clothing with minimal overlap in product types.
These results further validate that STAGE is capable of learning transferable patterns across domains through its defined unified input space. The consistent performance gains with additional training domains suggest that STAGE- edge-graph effectively captures generalizable dependencies between attributes, with more training domains enabling the learning of a broader range of dependencies. In contrast, baseline approaches that ignore attributes or use generic embeddings fail to leverage the additional training domains for improved cross-domain generalization.
In Hits 1, STAGE achieves relative improvement of 103% over the best parametric baseline (Ilm) (0.46 vs. 0.23). Moreover, STAGE obtains a relative improvement of 202% against a supervised structural method trained and tested on H&M (strucclvnlsupervvseed))).. In MRR, STAGE achieves the highest score, outperforming the best baseline by 99%. Moreover, STAGE demonstrates substantial improvement
5. Related Work
In this section, we present the most closely related works to our STAGE. A more in-depth comparison, along with additional related work, can be found in Appendix I.
7

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Table I: NBFNet-STAGE outperforms all baselines in zero-shot Hits@] and MRR (including supervised approaches) across the E- E-Commerce Stores and H&M datasets. For the E-Commerce Stores, results are averaged across models trained on all combinations of four graph domains and tested on the remaining domain. For zero-shot test on H&M, models are trained on the five E- E-Commerce Stores domains. % gain shows relative improvement of STAGE over each baseline.
Training: E-Commerce Stores
Test: Held-out E- E-Comm. Store
Test: H&M Dataset
Model
Hits@1 (t)
MRR % gain
% gain
Hits@ (1)
gain
MRR (1)
gain
random
0.0026 1: 00000
17615%
0.0006
0,000
77667%
Common Neighhors
0,2991 +: 00006
54%
0.3942 + 0.044
26%
0.2354
0,000
98%
0.3179
0.000
48%
Adamic Adar
0,3052 00007
51%
0,4001
0.0015
24%
0.2349
0,000
99%
0.3184
0,0000
48%
Personalized PageRank
0.0117 0,0000
3837%
0.0714
0.0001
596%
0.0105
0,0000
4344%
0.0717
0.0000
556%
NBFNet-raw
0,0000 00000
80
0.0032
15434%
0.0005
0,0004
93220%
0.0059
00011
7871%
NBFNet-gaussia
0,2101 + 8.428
119
= 0.2617
90%
0.0925
0.0708
404%
0.1176 + 0.0756
300%
NBFNNttsttuctuurg
0,3149 00253
46%
0.3721
1 0.0219
34%
0.2231
0,0060
109%
0.2302
1 0.0090
104%
NBFNeetIIIm
0,3226 000900
43%
0,3830
1 0.0145
30%
0.2302
0,0015
103%
0.2365
0.0021
99%
0,3269 + 00013
41%
0.3844
+ 0.0199
29%
0.2286
0.0010
104%
0.234
: 0.0018
101%
NBBFNce-structural-spccccce
N/A
N/A
N/A
N/A
0.1546
0,0084
202%
0.2103
0.0164
124%
NBFNet-STAGE (Ours)
0,4606
0.023
0%
0.4971
0%
0,4666
0,0000
0%
0.4703
0.0029
0%
Model
Model NBFNut-structur NBFNet-Il
NBPNat-raw
NBFNuttstructurll
NBFNuttnnamallzed NBFNet-STAAGE
NBFNet-raw
NBFNat-nomailiee NSF Net-NNAA-G
NoF susssian
NDF
Mean Reciprocal (MRR)
NBF Aer-tet-gaussia
0.6
0.6
Hiss@
0.4
0.4
0.2
8.
3
3
Number of Graph Domains
Number of Graph Domains
(a) Zero-shot Hits@1
(b) Zero-shot MRR
Figure 4: The performance (both Hits@1 and MRR) STAGE improves with more train domains, while this not the case for other methods. Box-plot distribution over all combinations of fixed number of graph domains in the E-Commerce Stores dataset and testing the held-out domain(s), averaged over random seeds.
Graphs Generalization under Distribution Shifts. Sev- eral works address distribution shifts between train and test graphs over the same attribute domain, such as Shen et al. (2023); Zhu et al. (2021b), which employ learned augmen- tations to mitigate the change in distribution in test. Mean- while, extensive research has focused on domain adaptation for GNNs (Dai et al., 2022; Li al., 2020; Kong et al., 2022; Pei et al., 2020; Veličković et al., 2019; Wiles al., 2022; Zhang et al., 2019; Zhu et al., 2021a), which typically assume access to data in both source and target domains. In contrast, our work tackles the more challenging scenario of zero-shot generalization to unseen attribute domains. To the best of our knowledge, all -fit--i-iiiitttionn graph meth- ods (Zhang al., 2024a) do not address the attribute domain shifts we consider, which include changes in the number of attributes between train and test.
to create versatile graph models capable of generalizing across different graphs and tasks (Mao et al., 2024). Initial efforts in this direction convert attributed graphs into texts and apply an LLM (Liu et al., 2024; Chen et al., 2024b;a; Tang et al., 2024; Zhao et al., 2023; He Hooi, 2024; Huang et al., 2023). However, while promising, this methodology risks information loss and may limit transferabilitty (Collins et al., 2024; Gruver et al., 2024; Schwartz al., 2024). In contrast, non-L.MM approaches attempt to directly address domain transferability in the attribute space (Xia & Huang, 2024; Lachi et al., 2024; Zhao et al., 2024b; Frasca et al., 2024; Yu et al., 2024; Zhao et al., 2024a), or by avoiding the use of node attributes entirely (Gao et al., 2023; Lee et al., 2023; Galkin al., 2024; Zhang al., 2024b). We provide details in Appendix I about why some of these approaches are not applicable as our baselines.
Foundation Models for Graphs. Developing foundation models for graph data is growing research interest, aiming
8

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Table 2: Zero-shot test accuracy of STAGE and baselines on the Pokec dataset, trained on Friendster. % gain shows relative improvement of STAGE over each baseline.
DMS-2327709 (THBEM), IIS-2403318 (III): Stanford Data Applications Initiative, Wu Tsai Neurosciences Institute, Stanford Institute for Human-Centered AI, Chan Zucker- berg Initiative, Amazon, Genentech, GSK. Hitachi, SAP, and UCB. The content is solely the responsibility of the authors and does not necessarily represent the official views of the funding entities.
Model
Accuracy (1)
% gain
random
0.500 i: 0.0000
30.4%
GINE-raw
0,558 1 0.0829
16.8%
GINE-gaussian
0,588 = 0.0250
10.9%
GINE-structura
0,564 = 0.0466
15.6%
GINE-IIm
0,550 = 0.0368
18.5%
Impact Statement
GINE-nommalized
0.541 1. 0,591 1 0.0083
20.5%
GraphAny
10.3%
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
GCOPE
0.535 + 0.0153
21.9%
GINE-STAGE (Ours)
0.652 + 0.0042
0%
6. Conclusion and Future Work
References
Abboud, R., Ceylan, i. I., Grohe, M., and Lukasiewicz, T. The surprising power of graph neural networks with ran- dom node initialization. In Proceedings of the Thirtieth International Joint Conference on Artifical Intelligence (IJCAI), 2021.
The challenge of learning universal graph representations that generalize across diverse attribute domains has limited progress in graph foundation models, mainly due to the lack of unified input space to represent node attributes, which may vary in test graphs. In this paper, we proposed STAGE, which addresses this limitation by transforming di- verse attribute spaces into a unified representation, learning statistical dependencies between attributes instead of rely- ing on their absolute values. By demonstrating that these dependencies remain invariant under certain domain shifts, STAGE provides theoretical foundations for zero-shot gen- cralization across graphs with differing attribute spaces. Our strong empirical results on medium-sized sized datasets demon- strate the practical effectiveness of this approach.
Bell, C. B. A characterization of multisample distribution- free statistics. Annals of Mathematical Statistics, 35(2): 735-738, 1964. doi:
Berk, R. and Bickel, P. On invariance and almost invari- ance. Annals of Mathematical Statistics, 1573) 1576, 1968. doi: 10. 2314//mm//117799333
Berk, R., Nogales, A., and Oyola, J. Some counterexamples concerning sufficiency and invariance. The Annals of Statistics, pp. 902-905, 1996.
While STAGE represents a meaningful step forward, it also highlights opportunities for future research. The unified input space we introduce could serve basis for devel- oping graph foundation models that can learn from diverse graph datasets at scale, reducing the quadratic complexity of STAGE. However, realizing this potential will require ad- dressing additional challenges, such as developing architec- tures to capture complex high-order attribute dependencies and scaling to large graph collections.
Berk, R. H. A remark on almost invariance. The Annals of Mathematical Statistics, pp. 733-735. 1970.
Bevilacqua, B., Robinson, J., Leskovec, J., and Ribeiro, B. Holographic node representations: Pre-training task- agnostic node embeddings. In The Thirteenth Interna- tional Conference on Learning Representations, 2025.
Chen, R., Zhao, T., Jaiswal, A. K., Shah, N., and Wang, Z. LLaGA: Large language and graph assistant. In Forty-first International Conference on Machine Learning, 2024a.
Acknowledgments
BR and BB acknowledge support from the National Science Foundation (NSF) awards CCF-1918483, CAREER IIS- 1943364 and CNS-2212166 an Amazon Research Award, and AnalytiXIN, Wabash Heartland Innovation Network (WHIN), Ford, NVidia, CISCO, and Amazon. Comput- ing infrastructure was supported in part by CNS-1925001 (CloudBank). This work was supported in part by AMD under the AMD HPC Fund program.
Chen, Z., Mao, H., Li, H., Jin, W., Wen, H., Wei, X., Wang, S., Yin, D., Fan, W., Liu, H., and Tang, Exploring the potential of large language models (1mms) in learning on graphs. ACM SIGKDD Explorations Newsletter, 25(2): 42-61, 2024b.
Collins, K. M., Jiang, A. Q., Frieder, S., Wong, L.,, Zilka, M., Bhatt, U., Lukasiewicz, T., Wu, Y., Tenenbaum, J. B., Hart, W., et al. Evaluating language models for mathe- matics through interactions. Proceedings of the National Academy of Sciences, 121(24)ee318124122) 2024.
JL gratefully acknowledges the support of NSF under Nos. 183-5885598 (CINES), CCF-1918944 (Expeditions),

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Dai, Q. Wu, X.-M., Xiao, J., Shen, X., and Wang. D. Graph transfer learning via adversarial domain adaptation with graph convolution. IEEE Transactions on Knowledge and Data Engineering. 35(5):4908 4492,,992222222 2022.
Kechinov, M. ecommerce behavior data from multi category
store, 2020. URL www.kaggle.com adtatstttss mkechinov/eccomeeree http:////eeecooeeeeeeeeeeevaoeoa behavior data- Erom-muuti-cateegrryyy
David, H. and Nagaraja, H. Order statisties. Encyclopedia of Statistical Sciences, 2004.
Kipf, T. and Welling, M. Semi-supervised classification with graph convolutional networks. ArXiv, 0w///6609029900 2016.
Erhan, D., Bengio, Y., Courville, A., and Vincent, P. Visual- izing higher-layer features of a deep network. Technical Report 1341, University of Montreal, June 2009. Also presented at the ICML 2009 Workshop on Learning Fea- ture Hierarchies, Montr'eal eal, Canada
Kong, K., Li, G., Ding, M., Wu, Z., Zhu, C., Ghanem, B., Taylor, G., and Goldstein, T. Flag: Adversarial data augmentation for graph neural networks. arXiv preprint arXiv:2010098911. 2022.
Fatemi, B., Halcrow, J., and Perozzi, B. Talk like graph: Encoding graphs for large language models. In The Twelfth International Conference Learning Represen- tations, 2024.
Koning, N. W. and Hemerik, J. More efficient exact
group invariance testing: using a representative subgroup. Biometrika, (112))441-4588 2024.
Lachi, D., Azabou, M., Arora, V., and Dyer, E. Graphfm: A scalable framework for multi-graph pretraining. arXiv preprint arXi:22407.11907 2024.
Frasca, F., Jogl, F., Eliasof, M., Ostrovsky, M., Schönlieb, C.-B., Gärtner, T., and Maron, H. Towards foundation models graphs: An analysis on cross-dataset transfer of pretrained gnns. arXiv preprint 1rXiv:2412.17609, 2024.
Larochelle, H., Erhan, D., and Bengio, Y. Zero-data learning of new tasks. In AAAI Conference on Artificial Intelli- gence, 2008
Galkin, M., Yuan, X., Mostafa, H., Tang, J., and Zhu, Z. Towards foundation models for knowledge graph reason- ing. In The Twelfth International Conference on Learning Representations, 2024.
Lee, J., Chung, C., and Whang, J. J. Ingram: Inductive knowledge graph embedding via relation graphs. In In- ternational Conference on Machine Learning pp. 18796- 18809, PMLR, 2023.
Gao, J., Zhou, Y., Zhou, J., and Ribeiro, B. Double equiy- ariance for inductive link prediction for both new nodes and new relation types. arXiv preprint arXiv:2302.01313. 2023.
Lehmann, E. L., Romano, J. P., and Casella, G. Testing statistical hypotheses, volume 3. Springer, 3rd edition, 2005.
Gruver, N., Finzi, M.. Qiu, S., and Wilson, A. G. Large language models are zero-shot time series forecasters. Advances in Neural Information Processing Systems, 36, 2024.
Leshno, M., Lin, V. Y., Pinkus, A., and Schocken, S. Mul- tilayer feedforward networks with nonpolynomial ac- tivation function can approximate any function. Neural Networks, 666):861-8677 1993. ISSN 0893-6080. doi: wtt.://ooo.gg/0..0010/////939330
He, Y. and Hooi, B. Unigraph: Learning a cross-domain graph foundation model from natural language. ArXiv, abs/2402. 13630, 2024.
Li, Y., Ma, T., Zhang, J., Ding, Y., Chen, Y., and Tang, J. Progressive graph learning for open-set domain adapta- tion. In International Conference on Machine Learning, pp. 5968-5977. PMLR, 2020.
Hu, W., Liu, B., Gomes, J., Zitmik, M., Liang, P., Pande, V., and Leskovec, Strategies for pre-training graph neu- ral networks. International Conference on Learning Representations, 2020.
Liu, H., Feng, Kong, L., Liang, N., Tao, D., Chen, Y., and Zhang, M. One for all: Towards training graph model for all classification tasks. In The Twelfth International Conference on Learning Representations, 2024.
Huang, Q., Ren, H., Chen, P., Kržmanc, G., Zeng, D., Liang, P. S., and Leskovee, J. Prodigy: Enabling in-context learning over graphs. Advances in Neural Information Processing Systems, 36, 2023.
Mao, H., Li, J., Shomer, H., Li, B., Fan, W., Ma, Y., Zhao, T., Shah, N., and Tang. J. Revisiting link prediction: A data perspective. arXiv preprint arXiv:2310.0079,, 2023.
Kaggle. H&m personalized fashion recommenda- tions, 2021. URL https://www.kgggl./
Mao, H., Chen, Z., Tang, W., Zhao J., Ma, Y., Zhao, T. Shah, N., Galkin, M., and Tang, J. Graph foundation models. In arXiv preprint 2rXiv:2402.022111 2024.
seaalioc-eeccommenattttosoevveee Ac- cessed: 2024-09-21.
10

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang, B. Domain adaptation on graphs by learning aligned graph bases. In Advances in Neural Information Processing Systems, volume 33, pp. 16735-16744 2020.
39th International Conference on Machine Learning, vol- ume 162 of Proceedings of Machine Learning Research, pp. 22964-22984, PMLR, 17-23 Jul 2022.
Wiles, O., Gowal, S., Stimberg, F., Rebuffi, S.-A., Ktena, I., Dvijotham, K., and Cemgil, T. A fine-grained analysis on distribution shift. In International Conference on Learning Representations (ICLR), 2022.
Perozzi, B., Fatemi, B., Zelle, D., Tsitsulin, A., Kazemi, M., Al-Rfou, R., and Halcrow, J. Let your graph do the talking: Encoding structured data for llms. arXiv preprint arXiv:2402.000 025.02.....2..... 2024.
Xia, L. and Huang, C. Anygraph: Graph foundation model in the wild. arXiv preprint arXiv:2408. 10700, 2024.
Samuel, D. and Øvrelid, L. Tokenization with factorized subword encoding. In Findings of the Association for Computational Linguistics: ACL 2023, Toronto, Canada, 2023. Association for Computational Linguistics.
Xian, Y.. Schiele, B.,, and Akata, Z. Zero-shot learning- the good, the bad and the ugly. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4582-4591, 2017.
Sato, R., Yamada, M., and Kashima, H. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining, SDM, 2021.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S, How powerful are graph neural networks? ArXiv, abs/1810.0086 2018.
Schwartz. E., Choshen, L., Shtok, J., Doveh, S., Karlinsky, L.,, and Arbelle, A. Numerologic: Number encoding for enhanced Ilms' numerical reasoning, arXiv preprint arXiv:2404.00455. 00459, 2024.
Yu, X., Zhou, C., Fang, Y., and Zhang, X. Text-free multi- domain graph pre-training: Toward graph foundation models. arXiv preprint arXiv:2405.13954 2024.
Zhang, K., Liu, S., Wang. S., Shi, W., Chen, C., Li, P., Li, S.,
Shen, X., Sun, D., Pan, S., Zhou, X., and Yang, L. T. Neigh- bor contrastive learning on learnable graph augmentation. In Proceedings of the AAAI conference on artificial intel- ligence, volume 37, pp.
Li, J., and Ding, K. A survey of deep graph learning under distribution shifts: from graph aut-of-distribution gener- alization to adaptation. arXiv preprint arXiv:2410. 19265, 2024a.
2023.
Simonyan, K., Vedaldi, A., and Zisserman, A. Deep inside convolutional networks: Visualising image classification models and saliency maps. CoRR, abs/1312.600 2013.
Zhang, Y., Song, G., Du, L., Yang, S., and Jin, Y. Dane: Domain adaptive network embedding. arXiv preprint arXiv: 1906.006664 2019.
SNAP, S. N. A. P. Pokec social network dataset, 2012. URL https:/ sentappstaaffrrd.... datt///aaa////aaaa/aaa soc- Pokec.html. Accessed: 2024-09-21.
Zhang, Y., Bevilacqua, B., Galkin, M., and Ribeiro, B. TRIX: A more expressive model for zero-shot domain transfer in knowledge graphs. In The Third Learning on Graphs Conference, 2024b.
Tang, J., Yang, Y., Wei, W., Shi, L., Su, L.,, Cheng, S., Yin, D., and Huang, C. Graphgpt: Graph instruction tuning for large language models. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 491-500, 2024.
Zhang, Z., Li, H., Zhang, Z., Qin, Y., Wang, X., and Zhu, W. Graph meets Ilms: Towards large graph models. In NeurIPS 2023 Workshop: New Frontiers in Graph Learn- ing, 2023.
Zhao, H., Chen, A., Sun, X., Cheng, H., and Li, J. All in one and one for all: A simple yet effective method towards cross-domain graph pretraining.
Teixeira, L., Jalaian, B. and Ribeiro, B. Are graph neural networks miscalibrated? arXiv preprint 1rXiv:1905.02296 2019.
Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 4443-4454 2024a.
Veličković, P., Fedus, W., Hamilton, W. L., Liò, P., Bengio, Y., and Hjelm, R. D. Deep graph infomax. In Interna- tional Conference on Learning Representattonss 2019.
Zhao, J., Zhuo, L., Shen, Y., Qu, M., Liu, K., Bronstein, M., Zhu, Z., and Tang, J. Graphtext: Graph reasoning in text space. arXiv preprint arXiv:2310.01088 2023.
Wang, T., Roberts, A., Hesslow, D., Scao, T. L., Chung, H. W., Beltagy, I., Launay, J., and Raffel, C. What lan- guage model architecture and pretraining objective works best for zero-shot generalization? In Proceedings of the
Zhao, J., Mostafa, H., Galkin, M., Bronstein, M., Zhu, Z., and Tang, J. Graphany: A foundation model for node clas- sification on any graph. ArXiv, abs/2405. 204445 2024b.

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Zhu, Q. Ponomareva, N., Han, J., and Perozzi, B. Shift- robust gnns: Overcoming the limitations of localized graph training data. In Advances in Neural Information Processing Systems (NeurlPS), volume 34, 2021a.
Zhu, Y., Xu, Y., Liu, Q. and Wu, S. An empirical study of graph contrastive learning. In Proceedings of the NeurlPS Track on Datasets and Benchmarks, 2021b.
Zhu, Z., Zhang, Z.., Xhonneux, I..P., and Tang, Neural bellman-ford networks: A general graph neural network framework for link prediction. Advances in Neural Infor- mation Processing Systems, 34:29476-2949,, 2021c.
12

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
A. Pseudocode of STAGE Algorithm
In this section, we present the detailed pseudocode for STAGE's two main components: (1) the STgGE--dge-rraphs construction algorithm (Algorithm 1) that captures statistical dependencies between attributes, and (2) the forward pass (Algorithm 2) that uses these -TAGE-edge-graphss to generate the final graph representation. The STAGE-cdge-graae -rregggpphh construction creates complete graph for each edge in the imput graph, where nodes represent attributes and edge weights capture conditional probabilities between attribute pairs. The algorithm handles both totally ordered and unordered attributes. using two GNNs one to generate edge embeddings from the
The forward pass then processes these STAGE-edge-grawe STAGE-edge-grapee and another to produce the final graph representation using these embeddings.
Algorithm 1 STAAGE-edge-graphh Construction
Input: Graph G (V, E, X) with node attributes X {x" JoEV
2: Output: STAGE-edge-grapel
(G(S"") (N.DEE (M.))E
3: for each (u,v) E E do
4: Initialize S E IR. 2d with zeros
5: for = d do
6: x; is totally ordered then
7: S P < )
8:
else
9:
S P( x!!)
10:
end if
11:
if a is totally ordered then
12:
S ((ta)(+d) - [x < xx))
13:
else
14:
Sue (++))++d) t P(x = x.¹)
end if
16:
end for
17:
for
1 to 2d do
18:
j 1 to 2d. + do
19:
(z;, + GetAttributPPair("""
x², i.j. ,"",""",""""""""""""""""""""""""
20:
T. are totally ordered then
21:
Sue
ij + IPx; S x;|x, S xz)
else I. unordered, 2, totally ordered then Sue + Pxx xg|x S x,) 3j
24:
else if totally ordered, 2, unordered then
25:
Su + Pxx < 4;|x; xr,)
26:
else
27:
S + Px, =,ix, = x.))
28:
end
29:
end for
end for
31: G(Suv) (reateCompleteennp((24)
32: for 1 to 2d do
33:
(etNodeAAtribute((((55))
34: end for
35: for = to 2d do
for j = 2d, j # do
Attribeet ((S")), (i.j), S 38: end for
39: end for
40: end for
13

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Algorithm 2 STAGE Forward Pass
Input: Graph G (V, X), GNNs M1 and M2
2: Output: Graph representation M(G)
3: (G(S")) (.. f- ConstrucllddgeGGaas((())
4: for each (u, v) E E do
5: puo & (I(G(("))
6: end for
7: G' + (V, E, (p=")(
8: M(G) t M2(G")
9: return M())
B. Proofs and Additional Theoretical Results
B.1. Groupoids
Definition B.1 (Groupoids). A groupoid 9 consists of the following elements:
1. collection distinct spaces, denoted as Sg)
2. A set of transformations (also called morphisms) between these spaces, denoted as Trans(G).
3. Each transformation f T9) maps one space in Spaces(G) another space (or potentially to itself), denoted as X Y, where X, Y Sgaces(G).
There a rule for combining transformations: for any two transformations f X - and g Y + Z, their composition results in a transformation g o f X Z.
5. Each space S E Sgaces(g) has an identity transformation idg : S S> S that maps S to itself, such that for any space
X Sg) and any transformation f1 S + X and f2 X S, guarantees fi idg fi and idg o f2 f2.
6. Every transformation X + Y has unique inverse transformation f-1: Y + X such that f-1 o -ix and
o f-1 = idy.
B.2. Statistical tests as graph regression on feature hypergraphs
To prove the result of Theorem 3.2, we will first show an intermediate result using the notion of maximal invariants. Let be a transformation group acting on space X. function M : X + Z is said to be maximal invariant if it is invariant to transformations of G and if Vz 22 X, ( M implies 22 g o 2 for some group action G, that is, if M is constant on the orbits but for each orbit, it takes on a different value (Lehmann et al., 2005, pp. 214). A maximal invariant is a representation theory counterpart of sufficient statistics.
Our intermediate result will show that the feature hypergraph admits a graph representation that is a maximal invariant. But first, we need to formally define the class of invariances, which we show later is essential for STAGE's domain transfcrability. Since we are interested in attribute spaces of distinct domains, rather than using groups (which involve automorphisms mapping a space onto itself), we will groupoids (Definition B. Groupoids generalize the concept of groups by allowing transformations between multiple spaces. In group, all transformations map space onto itself, while in groupoid, transformations can map between different spaces, but must still be invertible.
Definition B.2 (Component- wise order- pnder-preserving groupoids for attributes (COGF)). Let X1, be two attribute spaces, both with d attribute dimensions. An attribute transformation f X= + X2 is said to be component-wise order-preserving if it can be decomposed into a set of maps f1...., fa. where each fi maps the i-th dimension of X; to the i-th dimension of X2 and a homomorphism that preserves the total order in X,, and all dimensions of both X, and X2 have a mapping.
Given an attributes of the endpoint nodes & = (((x", (x") (u, v) E E}} and a groupoid action f from the COGF (Defini- tion B.2), we define how f acts on as follows:
((E)
(u, E F.]
14

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Now, we are ready establish the intermediate result follows.
Lemma B.3. Given a multiset of attributes of the endpoint nodes & and the feature hypergraph Fe (Definition 3.1). There exists parameterization l* for a maximally expressive hypergraph GNN encoder M such that Mo- (Fe) is maximal invariant under COGFs (Definition B.2)
Proof. Let V(Fs) be set of labeled nodes (labeled with the feature id and the order statistic position) of Fe. let H(FF)) be set of hyperedges of Fs, and let m(Fe) be the number of entities from E, which are labeled with the entire graph during creation. Given two hypergraphs Fe,, Feg. we define Fe₃ = Fez if and only if ((F&,) ) = v(Feg), H(FF,) = (F&g) and mFFs) = m(Fe). Note that since the node in the feature hypergraph are always labeled, a most expressive hypergraph GNN Mo- will ensure that Mg- (Fe,) = Mo- (Fe,) if and only if Fe, = Fé.-
Let G be the COGF (Definition B.2) and let J E be an arbitrary groupoid action of COFG. To show invariance, the goal is to show that Mg. (Fe)= = Me. (F)(E)) for any E. Because Mg. is most expressive, this is equivalent to showing F8 FF(E)
Let V(Fe) = ((i,k,)))) Ael.
We first observe that since f acts on individual feature values, it does not change the total number of entities. Hence, the set of hypergraph nodes remain unchanged, V(Fr(s)) V(Fe) = m.
For the edges, consider an arbitrary hyperedge H.n in Fe. Then, because f is a COGF, it preserves the order statistics of all feature values. Thus, the order of the feature value ou(u) from & remains the the same as (u) from f(E), for all and Hence, Huv is also a hyperedge in F())-- Similarly, because has an inverse f-1, we can show that for every edge H' in F(e)). it is also in FE under the transformation f-1,, Thus, H(FF) = H())(E)) and so Fe F((e), and therefore Ma = (F(E)))))
To show maximality, let Ma- (o( for some & and 8τ. Our goal is to show that & and E` are on the same orbit, iee there exists f' E 9 such that ((E)= E'
Because Mg. is most expressive, we know Feg = Fg. This implies that V(Fg) = VFF.)) and [H(Fe)] (H+)) First, Let m = (D(Fe)] () And since ((Fe) V(Fe),, we also know both & and E' must have the same number of features. Denote it d. In addition, because H(FF) H(FG)), we have EE| = |E", Second, pick any endpoint features (x" x²") E E, and let Huv E H((F)) be the corresponding hyperedge. We know that H.v H(FF.)) as well. Hence, there exists an counterpart endpoint features (x"
xx1 2')E EE' such that
Y1 U S (u) = oi, (u') and (1 = (o()')
where (-) is the order of values of i-th feature in Fe and d((-) the order of values of i-th feature in Fe. Thus, we can construct a COGF groupoid action f as follows:
Let f be decomposed into a set of maps fı,... fa for every feature dimension i. Each fi is a piecewise linear function fi defined as follows:
(z))(()) + (z))<(()
if a < (x))
(x ((())
if a = Ti(k)) for some k: 1 1 k S m
(x)) (skk)) + (o0 - (a (x)
fi(a) =
if (i(k)) < a < Ti(ka) for some
((0):
ko, k 1 - ko < kı S m if a > (z) ((m()
a a- (x)) + (xx) (e(m))
Since each fi is a piecewise linear function that strictly increases, each of them preserves the order of feature values. And since f can be decomposed into ft's. f is a COGF groupoid action.
Hence, we have showed that there exists a of such that f(E)= = E' which shows maximality. Hence completing the proof.
Based on Lemma B.3, we are ready to prove that measuring dependencies of the features (x",x") ) E E under COGF invariances can be defined as depending only on a most-expressive GNN encoding of the feature hypergraph Fg. In short, this is because any hypothesis test T(E) that can be expressed as rank test is invariant to COGF, and any invariant function can necessarily be expressed as depending only on a maximal invariant.
15

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Theorem 3.2. Given multiset of attributes of the endpoint nodes E, the corresponding feature hypergraph Fe (Def- inition 3.1) and a most-expressive hypergraph GNN encoder Ma- (Fe), then any test T(E) that focuses on measuring the dependence of the attributes of the endpoint nodes of & has equivalent function h within the space of Multilayer Perceptrons (MLPs) that depends solety on the graph representation Ma- (F&), i... 3h E MLPs s.t. T(E) = hhMM- (Fs)).
Proof. We first note that any test TEE) that focuses on measuring the dependence or independence of endpoint features of is necessarily a rank test that relies solely on the indices of the order statistics rather than the numerical values of the features (Bell, 1964; Berk & Bickel. 1968). As such, T(E) is invariant to COGFs (Definition B.2). Now, we show that given E. Fg, and a most expressive hypergraph GNN encoder My there exists an such that T(E) h(Mo- (F&)).
For any E E,, we know that if Mo- (Fe,) M (F&z), then f(E)) E2 for some groupoid action f in COGF (Lemma B.3). Then, because T' is invariant to f. we have that T(E)) ()) T(E2). Hence, each value of Ma- (Fx) is associated with no more than one value of TEE). In other words, there exists mapping h" such that h" (Mg- (Fx)) = T(E).
Since MIPs are universal function approximators (Leshno et al., 1993), there exists a MLP h that approximates h"," i.e. h(M (Fx)) = T()).
B.3. Correspondence between STAGE-edge-graphss and feature hypergraphs
For the proof of Theorem 3.3, we first prove an intermediate result, which establishes that there exists a bijective mapping between the feature hypergraph F& and the multiset of stage graphs, Sg = {[G(S"")) (u, v) E E}} where each STAGE- edge-graph equipped with unique feature ids. In the case of repeated feature values, we will show a bijective mapping to a collapsed feature hypergraph, where the nodes corresponding to the repeated feature values are collapsed into one single node, with its order & being the smallest order of these repeated values. We denote by n the number of unique feature values of feature i. We note that such collapsed feature hypergraph in the case of repeated feature values will provide a representation that is stabler than the traditional rank tests, as repeated values will translates into uncertainty or noise in the rank test results, whereas our feature hypergraph representation will remain stable.
Lemma B.4. There exists a bijective mapping I berween the multiset of STAGE-edge- graphs Sg = ([G(S")) 1 (u,v) v) E FB with unique feature ids and the feature hypergraph Fe (Definition 3.1).
(u, v) E E} be the corresponding multiset of attributes of the endpoint nodes. We assume that each stage graph G(Su)) E Sg has nodes labeled as follows: the node associated with i-th feature for the source node u is labeled with (i, 1). and the node associated with i-th feature for the target node v is labeled with (i, 2). for every feature i E [d]. Thus, given the graph G(S""", we can recover weighted adjacency matrix Sr and so there is a one-to-one mapping between them. Hence, for the following discussion, we refer to G(Su)) and Swe interchangeably.
Proof. Let G XX be an input graph and let & = {((=", x²) ((""","")""""""
We first show that, given S5. can construct Fe.
Construct I: I(SE)= Fs:
We first construct the set of feature hypergraph nodes. For every feature i, collect the multiset Qa = (SS a D (u,)eE and Q:2 {{ Sug ((itd((+d)) }} (u,w)e
and let Q; = Qn U Q12- In words, Qn collects the i-th feature's 's empirical c.d.f.,
S = - = Pxx, S xx of the source node of all edges. Similarly, Q12 collects the i-th feature's empirical c.d.f., ((+))++)) = -px;;) = PP(x S x;),, of the target node v of all edges. Note that Q is a multiset, so if there are multiple nodes u (or v) with the same i-th feature value x. (or o:"", they will have the same empirical c.d.f. p(x!)) (or p(x))), and thus Qi will record the multiplicity (number of occurrence) of such repeated c.d.f. values.
Sort the unique values in the multiset Q: in ascending order and denote the sorted sequence of unique values as S, (s1, , sm;) where 8 E Q, for each E [m]]] where m² & m is the total number of unique values for feature i (if all values have multiplicity of 1, then m² = m). Denote ny (st) the multiplicity of the value 8t in the multiset Q.. Then, we can recover the feature hypergraph's is nodes corresponding to the i-th feature as follows:
For the smallest feature value, Censtruct the two nodes labeled (t, 1, and (i, 1,2).
For I E {2,3, (2.,...., } and s E S,, construct the two nodes labeled as (i, 1+ (,(,nn(()))))))))))) and (i, (i,1-1 - + n +n ())-))). 1-1 1 + (=(-)) is the order of the feature value 81, accounting for multiplicity.
16

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Repeating the above process for all features i will recover the node set of the feature hypergraph.
Then, we reconstruct the multiset of hyperedges. Take any S E Sg. Again, for every feature i, we have S = p(x)) denoting the empirical c.d.f. of the i-th feature of the source node u. Let No. = {(i, ......, (i. ma, 1)), where the ......,,
ks,''s are the orders (I E [mz]) Na. then is the subset of hypernodes for feature i associated with the source node u in the original edge in the input graph. Now, let l' be the smallest integer in [m]]] such that kigr > S = p(x)), and let k.- = ki. - 1. Then, k is the order of the i-th feature of node u, i.e., k2 = (w))
Similarly, for every feature i, we have Suy (i+d)((i+d) = p(a,), the empirical marginal c.d.f. when node e is the target node of an edge. Let Nie = {(é, ks, 2)..... (f, ki,m 2)}. Let 1" be the smallest integer in [mm]] such that kyo > Si (i+d)(++d) = =p Then, let Ky = kt 1, and this is the order of the i-th feature of node v, i... k. = (,()).
Hence, we have recovered the hyperedge:
Huv = kY, 1))ett U ((,, 222)ee
where ke and kg" are defined as above.
Repeat the above process for every Suv E Sg. then we recover the entire multiset of hyperedges for the feature hypergraph.
Construct I-1 (Fe) Sg.
Given feature hypergraph F& with ((Fe) the set of nodes and H(FF) the multiset of hyperedges. Our goal is to reconstruct the multiset of STAGG--edge-raphss Sg ([G(S"") (u, E E}} for some underlying edge set E.
Pick any hyperedge H = ((i, k1 1) Neg U [(i, k2, kej E HFFe), where ki = (x()) is the order of i-th feature value for some unknown node u and A = (v) the order i-th feature value for some unknown node v. We first construct the corresponding TTAGE-edge-grappe adjacency matrix, which we denote S Once S is obtained, then we have the STAGE--dge-grapp G(
First, we construct the diagonal entries of S as follows. Note that the entire hypergraph is labeled with an integer m, which indicate the total number of entities (nodes) in the original input graph. Hence, we can recover the marginal empirical c.d.f. of the i-th feature value of each entity. Specifically, for every feature i, we have k from the hyperedge H, denoting the order of i-th feature value of the underlying source node u of an edge in the original input graph. If there is another Otherwise, let n. = m. Thus, nę indicates the
hypergraph node (i, k', 1) E V(Fe) such that k' >> ki, then let m k total number of nodes in the original input graph that have the i-th feature values smaller than or equal to the i-th feature value of the current node u. Note that mi accounts for multiplicity, if there were multiple nodes having the same i-th feature value this node. Hence, let ! n /m, which is equal to the marginal empirical c.d.f. of the i-th feature value of node
Similarly, for every feature i we have k.?. If there is another hypergraph node (i, k,, 2) E V(Fs) such that k' > k33, then let n = k - 1. Otherwise, let ni = m. Let S (1+d)(++d) = n2, /m. Hence, we have filled in the diagonal entries of S
Second, construct the off off-diagonal entries of S Recall that the off off-diagonal entries of STAGE-edge-grapp weighted adjacency matrices denote the empirical conditional probabilities between two different features (Equation (2)), either within the same source node, the same target node, or between the source and target node. Specifically, for any two features j E [d], i # j, the entry is
S = P PA-UMI((V) S x² و xÿ))
S ((++d) P(A.B)-UM((E)) (x S 2 x x5 x/)
S# (i+d); = P(A.B)-UMi E) (x $ of |x] s xz))
S ()) PB.UUMLLV (x x |x] s a())
where (u, u) is the edge in the input graph corresponding to the hyperedge H.
We can compute these entries of S as follows. First, given any hyperedge H' E V(Fz), denote Kd (i) for any i E [d] and r E (1,2} such that (i, K (i), r) E H¹. Then regarding our particular hyperedge H of interest, for every pair of features j E [d] with i # j. we can obtain n!. n). n,, and n? as defined previously. Recall that nı is the number of feature values of i-th feature that are smaller than or equal to the current i-th feature value captured by H, for both the source node (r = 1) or the target node (r = 2).
17

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
For the entry f and S# (i4d)i+d)) they capture inner-node feature dependencies, and we notice that the empirical conditional probabilities are defined w.r.t. random nodes sampled uniformly from the set of all nodes. Hence, we can compute these two entries as follows:
s = min (1, / S (++))+++) min(1,n
To compute the entries for S i(j+d) and S (i-d)j we note that the random nodes A, B are uniformly sampled from the set of edges E. To do so, we first define the two subsets of hyperedges Hj and H3 as follows:
H = ( (1) $ n H' E H(Fe)} H ( (1) S n² H' H(Fe)}-
In other words, H is the subset of hyperedges whose node, (i, Kr (i), 1), has an order (i) that is smaller than or equal to the order of the counterpart node of the current hyperedge H. Vice versa for HJ.. Hence, we have
[+)1))((FF)) = [7(] (+})) = ()A..B))UM))))()) S x3)).
( (a..)))tmi By) (x) S zz)
Then, define the next two subsets y 12 and Hel follows:
H (1) s H' (H}
1/ (1) nf H' E H.}
These two subsets help effectively computes the empirical conditional probabilities. Namely, now we have
n4 = P (A.,)) (x 2 x - x3)) | 1/ = ((AA.B)EUir (x S x x3 S x
Thus, we set the adjacency matrix entries for inter-node dependencies to
S d(f+d) 17 1/17331
sll (i+d); = |7 1/1731
Now that we have constructed a mapping I mapping Sg to F&, and another mapping Z-1 mapping Fs to Sg, we now want to check that they are valid bijections. To show this, we show that I-1 o I Identity, and I I-1 = Identity.
Show that o Identity
First, observe that the mapping I transforms each element G(Su))) Sg hyperedge H' E F'. Similarly, the mapping
Let Sg be an arbitrary multiset of STAGE-edge-rraphss Let F' I(Se) and S" -
I-1 transforms each hyperedge H' E F" to one STAGE-edge-grapp G" E S". Hence, as long as we show that, for any G(S")) E Sg, the composed transformation I I produces STAGE-edge-graae G" such that G(S"r) G" we can conclude I-1 o = Identity.
To observe this, we first note that G" has the same set of labeled nodes with G, and that each node (i,r), i E [d]. E {1, has the same empirical marginal c.d.f. values. Similarly, between any two nodes (11,r1) and (22, G and G" will have the same edge attribute for the edge ((11,71) (ig, r2)), which corresponds to the empirical conditional probabilities between features i and and between node placement in the original edge (source or target) r and r2. Thus, G G".
Show that ooZ I-1 = Identity
Let F& be an arbitrary feature hypergraph. Let =I- and F" = =ISS). Similarly, as long as we show that, for any hyperedge H E Fe, the composed transformation I produces a hypergraph H" such that = H", we can conclude that I I-1 Identity.
18

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
To observe this, we note that every hyperedge (i, r) E H, where E [d], S k S m4r E (1, will be recovered in H" This is because each (i, Rt r) E H corresponds to unique labeled node (i,r) in the STAGE--dge-graap G' which will be used to construct node (i, k" ,r) in H" under the mapping Z. In terms of the order k, the mapping I-1 will converts it into the marginal empirical c.d.f. value, which is treated as the attribute of node (i, r) in the BAAGE-edge-grappp G'. The mapping I, on the other hand, will convert this marginal empirical c.d.f. value into the order k" for the node (i, k,,r) r) in H1", guarantecing k" k. Thus, every node (i, k. r) that is in H is also in H", and there will be no additional nodes created for H". Hence, H- = H" for every hyperedge H E Fe. and thus o I = Identity.
In conclusion, we have shown two mappings, I and I--, and have shown that they are the inverse transformation of each other. Hence, I is a bijective mapping between the multiset of BaAGE--dggegrappee and feature hypergraph.
Given the bijective mapping in Lemma B.4 between the multiset of STAGE-edge- with unique feature identifiers and the feature hypergraph, and the fact that the feature hypergraph allows for maximal invariant graph representation (Lemma B.3), it follows that the set of STAGE-edgee-raphhe can also yield a maximal invariant representation of the original input graph. This observation is formalized as below, which is our second theoretical contribution:
Theorem 3.3. Given the altributes of the endpoint nodes& & (Definition 3. of graph G = E,), there exists an optimal parameterization 0g 0g for most expressive GNN encoder M9 and most-expressive multiset encoder M", respectively, such that Mor,3 (G) == Ma; (H{ (G(S"")) (u, v) E E}]) such that any test T(E) that measures the dependence of E's attributes of the endpoint nodes has an equivalent function h within the space of Multilayer Perceptrons (MLPs) that depends solely on the graph representation M g (G), i.e., 3h E MLPs s.I. T(E) = h(MMag.0g (G)).
Proof. To show invariance, let G1 = (V, X2) and G2 = (V, E, X2) be two graphs such that f(Xi) = X₂ for some groupoid action / in the COGF. Let &, and & be the corresponding attributes of the endpoint nodes respectively, from which we have f(E,) E. Let S ({ (u, v) E E}} and S ((()(S))) (u, v) E}} be the corresponding STAGE-edge-graphh respectively.
Since (() = Eg, and the attribute hypergraph is invariant to COGF (shown in the proof for Lemma B.3), we have Fe, Fēg- And since there is a one-to-one mapping between the multiset of T'AGE-edge-graphhe and the feature hypergraph, we have SIE= = -S2x. Hence,
(M I (u, E EE]] = {{ Mo; {5)}} SESIE
= {{ Moz (5)
}} SESGE
= -{f Mo; (52") ( E
As a result,
Mo 0y (G1) Mq; (f Ma (G(ST")) I uu) E E()))
Mag {{ Mg (G())")) (u, E {}}}) Me; 83 (G2).
To show maximality, Let G1 and G2 be two graphs such that Me; 0r (G1) MMo, 0z (G2). Then, because Mž, is most expressive multiset encoder, we have that
Mo; ((MM Mg (G((²")) | (u, E E}} Māy {f Ma (G(ST")) I E) E E}})
Again, since Ma. is most expressive GNN, we have 9
SIe = [[G((")) (u, v) E EB = - (u, b) E E}} = S25.
This implies that the feature hypergraphs F&, and Fe, are the same, Fs, = Fe, due to the bijective mapping between multisets of STAGE-edge -dgeggggg-- and feature hypergraphs. And as has been shown in the proof of Lemma B.3, this implies there exists a groupoid action f in COGF such that f(E) Ez. Hence, we have shown that Ma; .g (G) is maximal invariant representation w.r.t. COGF.
Thus, similar to the proof of Theorem 3.2, there exists MLP h such that for any test T(E), we have
T(E)= = h (Mp og (G)).
19

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
B.4. COGG Invariances
Definition B.5 (Component-wise order-preserving groupoid for graphs (COGG)). Denote X the space of node attributes with d 1 dimensions, and G(X) the space of attributed graphs with attribute space X and 2 entities. A graph transformation g (x)) ((x)) of two attribute spaces X1 and X2 is said to be a groupoid action of the component-wise order-preserving groupoid for graphs if it can be decomposed into a permutation of node identities Gnode .V + V and
a transformation of node attributes Jauribute X1 + X2 satisfying the following. Given Gi = (V, Ei, X1) I E ((1)) and
G2 = (V, Eg, X2) E (X2) with g(G1) = G2.
Vu, u E V. (u.o) E E1
(gmode (u), Inode (v) E Eg
Sattribute is a COGF (Definition B.2) except for any i E [d], the i-th component Jatribure,J may map the i-th dimension of X a different dimension of X2, while maintaining one-to-one correspondence between all dimensions of X₃ and X2.
B.5. STAGE COGG Invariant Representation
Theorem 3.4. STAGE is invariant to COGGs (Definition B.5).
Proof. Given graph G E, X), STAGE model M applies two instances of equivariant GNNs, intra-edge GNN and an inter-edge one, process the input graph. Denote the intra-edge GNN M1 and the inter-edge GNN M2. The intra-edge GNN M1 is applied onto Sg = ((G(( (u, v) E E)), the set of STAGB-edge-graphs, to produce edge-leve embeddings:
T Mv M1 Y(u, e)
and the inter-edge GNN M2 takes the edge-level embeddings as the edge attributes onto the original graph, i.e., making } to produce a final graph representation:
{{ yew (.))))))
G' = -V, E,
- M2((") M2((V, Hr" "rr""Hiuoo H(N,)E))
Now, consider a train graph Gu = (Vr, Eu. Xu) with Enr and a test graph Gue = (Vi, Eue Xw) such that there exists a groupoid action in the COGG (Definition B.5) satisfying g(G,) = Gie As per Definition B.5, is composed of a node identity permutation Gnode and attribute transformation Iatrribuee
We first note that the multiset ((r to the permutation of its elements. Since the inter-edge GNN M2 is equivariant GNN, have that
(U.))E invariant to node identity permutation Gaode because multiset invariant
M (guode (G)) = M ((gnodo (Vw), Gmode Eu), """")), (u, (B,)) (E.) M(z)).
Hence, as long as we can show that the graph representation given by M is also invariant under Gatribute then we together we can show that M is invariant to our groupoid action g. and that (G..) = (G,e).
To proceed, we first note that the groupoid action Jatributes when applied to an attributed graph G, can be expressed as Jauribane (G) = (V, E. Satribune (X)),
(X)). because the attribute transformation only acts on the node attributes but leaves the graph structure unchanged. Hence, when applying the inner-edge GNN Mj to the multiset of STAGE--dgee-raape of transformed input graph Gattribute (G), we write Mi (Jamribure (GammibneeG((Su (G(S))))) for all (u, v) E E.
Now, all we need to show is that the intra-edge GNN Mi produces a multiset of STAGE-edge- representations that invariant under the attribute transformation Jauribute. i.e., (( [M (G(S"))) (u,)) (G("")) = {{M 1 (gauribuee (G(S)))) ()) ( Since Gauribute is COGF (Definition B.2) except it may map different training attribute dimensions of X,, to different attribute dimensions of X1e, we can therefore further decompose into two different components: h and with = o f, where a mapping that permutes attribute dimensions, and f is COGF.
In Theorem 3.3, we have shown that most expressive GNN applied to a STAGE-edge TTAGE-edge-graph G(S equipped with attribute ids (which are the nodes ids in the STAGE--dge-graph because nodes correspond to attribute dimensions) produces maximal invariant representation under COGF. Hence, this implies that the intra-edge GNN M,, when applied to each STAGE-edge edge-ggag-,,,,h, without unique node ids, will produce an invariant representation to the COGF f. Namely, for all (u, v) e E.
M(((G((S")) Mi (G(((("))) M((G(S")))
20

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Note that ((G(S"))) (((()))) because / acts the node and edge attributes in G(Su)) (which are derived from the attribute values), but preserve the graph structure.
On the other hand, once the node ids in STAGE-edge- sege--dge-ggahh G(S5*)) is dropped, because Mi is an equivariant GNN, we also have that the M1 's output representations are invariant to permutations of the attribute dimensions, which corresponds to the permutations node ids the STAGE-edge-gran graph.. Namely, for all (u, v) E E.
(((H(((S))) M (G(()))))
Hence, together we have that for any (u,z) v) E E,
Mi (Jauribute (G(S")))) Mi(h f(G((")))) = =(((((((S"))) Mi(G")"))
Thus completing the proof.
C. Datasets
Here describe how construct the E-Commerce Category Dataset, the H&M Dataset, and the Social Network Datasets (Friendster and Pokec).
C.1. E-Commerce Category Dataset
To test the model's generalization to input attribute spaces, consider dataset of E- E-Commerce users and prod- uets (Kechinov, 2020). There are 29,228,88 8,9 different product categories, such as smartphones, shoes, and computers. We select subset of the most popular product categories and form an input graph from the products under each category and their respective connected users. At test time, we hold out an entirely different graph containing unseen products, from new unseen categories and associated users, and test the zero-shot (i.e., frozen model) performance on the test data. In this dataset, we focus on the single task of predicting links between users and products, with links indicating user beeehaiin/viewing/cattnn////////
product.
However, all categories originally share the same attributes. To ensure that the graph domains build have different attribute types, we use GPT-4 to retrieve information specific to each category. Specifically, the information retrieval process involves prompting GPT-4 with the following content:
"According the following information regarding an E-Commerce purchase, give information about the product in the following asked format." "First, the product is purchased at time: + row [""even__tti""" "." "Second, the category of the product is " row""eategory_ccde"" "," "third, the brand of the product is " row ["brand"]] "Last, the price of the product is str "price" "."
"Please provide information about the product in the following ison format." piison_prototype
The JSON prototype is different for different categories, and contains attributes that are specific for the category being prompted. That is, the JSON prototype for smartphones contains, for instance, attributes like display type, which is not a attribute for shoes, containing instead attributes such ankle height. In the following, we report the ISON prototype for all categories.
bed
"type": <select from l'Twin', "Twin XL', 'Full', 'Queen', 'King', 'California King' 1>,
"material"; <select from I' l'Wood', 'Mttal' 'Upholstered', 'Bamboo' 'Particle Board', 'omposite')>,
[ree__framm_incldeee <select from ('True', False' 1>,
21

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
tbeacboarro_incluuddd: <select from I' I'True', 'False' 1>, Trootboard_includee <select from ['True', 'False']> "mattresssincludee" <select from ('True', "False' [>, "box_spring_reepirrs"" <select from ["True', "False "weight_ eeeicihtccpacity lbs": <give int lbs?, sire__iizeee_etbbbbe_eeee length inches": <give float in inches>, "bed_size_
siee__siz__idhh incchh_nnchss <give flcat in inches>, "bed_size_heiiht__in
<give fleat in inches>
desktop
"processor_tae tyyee:: <select from I'Intel Core i3', 'Intel Core is', "Intel Core i7 "Iteel Core i9', 'AMD Ryzen 3", 'AND Ryzen 5 Ryzen 7', AMD Ryzen 9', 'Apple K1', 'ARM other']>, [>,
"ram_gb"; <give int>, astoragg_tvyo__hd__sss___.. <give int>, stgpragg__tye__ss_ssiee____e "storrae__tyee_yyrrrd_ssse setybbrrd_siie_pp_______ <give int>, "graphics_card". <select from ('NVIDIA GeForce GTX 1660', 'NVIDIA GeForce RTX 2060', 'NVIDIA GeForce RTX 2070', 'NVIDIA GeForce RIX 2080', 'ADD Radeon RX 570', AMD Radeon RX 580', 'AND Radeon RX 590", 'AND Radeon EX 5700', AADD Radeon ax 5700 J>,
<give int>,
operatiin "operating ingesttenns..,em <select from ['Windows 10', 'macos', LLinux Ubuntu', Linux Fedora', Linux Mint', 'Debian', "FreeRsI" 1>, "pover_supply_wattt":: <give int>,
bepoling_systens <select from l'Air cooling', 'Liquid cooling' 'Passive
cooling'12, 12,
"has blustooth" <select from ('True', 'False' }>
refrigerators
"energy "energy_rating": <select from l'At++', 'At+', 'A+', 'A' 'B', 'C' "capacity_ <give int>, "refrigerator type:: <select from I'Top Freezer', "Botten Freezer', SSide-by- Side', 'French Door', 'Mini Fridge', 'Comerccial'>>,
"dofrost_type": <select from ['Manual', 'Frost Free', 'Automatic Defrost']s, "has_ice_maker" <select from ('True', 'False']>, "has_wateerddssenner"" <select from ['True', 'False']>, "has "has_smart_eechnologgy. <select from ('True', 'False "is "is_ "is_energy_efficient" <select from ('True', "False' }>, "height_em": <give float>, "width_cm": <give float>, "depth_em"; <give float>
smartphone
"display_type" <select from I' I'OLED', 'ICD' }>, "display size": <give float in inches>, "display_resolution" <give int in pixels>, "processor_type"" <give string,,
22

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
"ram": <give int in GB>,
"storagge_ppioons" <give int in GH>, "rear Saraamerr__rimarrreesltttte "froom_caamera_resssltttooo <give int MP>, Sneeratingsysteens <select from l'Android', 'ios', 'HarmenyOs', 'KaiOs', 'Tizen 'Ubuntu Touch', 'PureOS', 'Sailfish os', 'Plasma Mobile' 1>, <give int in mAh?, "Has "Has_gps": <select from ['True', 'False "has_nfe"; <select from ['True', 'False'
<give int in MP>,
shoes
"type": <select from I' l'Running', 'Casual', 'Formal', 'Sports', 'Boots' Sandals 'slippers', Biking'' 'Dress', 'Work', , "Saeety' ]>, "material"; <select from L'Leather', 'Synthetic', "Textile', 'Rubber', Canvass' 'Mesh', 'Sudde' 'Patent Leather', 'Nubuck', 'Faux Leather' ]>, "color": <give string?,
"size": <give float in UK sizes>,
"gender": <select from ['Men', 'Women', 'Unisex', 'Children', 'Infants' [>, "closure_type": <select from L'Laces', 'Velcro', 'slip-on', 'Buckle', 'Zip', Hook and Leop', 'None'
"sole_mat scole_material"; <select from l'Rubber', 'Sytteetc'' 'eve', 'EVA' 'Leather', TPU (1hermoplastic Polyurethane)", TPRR ("hermoplastic Rubber) 1 "water_resistant"" <select from ['True', "Kalse']>, "ankle_height"" <select from ['Low-top', 'Mid-top', 'High-top', 'vver the ankle '12,
"breathability": <select from ('High', 'Medium' 'Low" }2,
"weight": <give float in grams>, "origin_countzy"; <give string?, "scasonaliy""; <selest from ('All-scason', Suumer'' Wiiner'' 'Rainy', 'Spring "Autun'')>,
"eco friendli: <select from ('True', "False
After extracting attributes of different numbers for all categories, we also append the original two shared attributes of all products (price, brand) that are considered to have a different distribution across categories, forming the following dataset statistics. Since the customer nodes lack attributes, we build edges between attributed nodes the same type (e.g., products) based on common connections, forming STAGE-eeggegeee
for these new edges. These edges are provided all baselines.
Table 3: Statistics of E-Commerce Categories
Category
Number of Nodes
Number of Edges
Average Degree
Num attributes
bed desktop
4044
25788
6.38
13
3011
37450
12.44
12
refrigerators
2985
33520
11.23
13
smartphone
3391
31970
9.43
14
shoes
4032
54890
13.62
16
C.2. H&M Dataset
H&M has 106K products, sharing the same 25 attributes, and 1.37M customers, sharing the same attributes. We sampled the interaction between the most popular 830 products and 830 customers based on their node degrees. We discarded 14 product attributes since 12 of them are repetitive (e.g. perceived_colour..ve value id is just a one-to-one mapping of perceived colour value name), 1 of them is the detail dese an English sentence that connects the other attributes, and
23

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Table 4: Comparison of statistics between the Pokec and Friendster social network datasets after filtering and sampling nodes.
Statistics
Pokec
Friendster
Number nodes
283 2084
1392
Number edges
3322
Number of node attributes
Attributes
public, completion percentage.regiin, age 7.363957597173145
age, interest, occupation,music, tv 2.3864942528735633
Average degree
Minimum degree
Maximum degree
29 [1, 2, 3, 4, 51 [35, 31, 25, 21, 141
12 [1, 2, 3, 4, 51 [516, 404, 213, 113, 62]
Lowest degrees
# Nodes with lowest degrees
Label 0 Ratio
50.88%
46.84%
Label Ratio
49.12%
53.16%
of them is the article id serving as the identifier of each product. We also discarded 4 user attributes: customer id as the identifier, FN and Active due to too many missing values (65% and 66% respectively), and postal that is overdispersed.
After picking the largest connected component of the graph formed by the 830 products and 830 users, we construct this dataset to have 77080 edges, 1580 nodes with an average degree 48.78, and 11 attributes for each product node and attributes for each user node. The product attributes are: product Hype name, product- group_name, name, graphical Lappearance graphical.appearacee name, colour group name, perceived colour name, perceived colour master name, department name, index name, in- tet-groupnnmee section_name, garment-group The user attributes are: club member mnmmberrstatus, fashion heseiiionnewssffequuneee age.
C.3. Social Network Datasets (Friendster and Pokec)
The original Pokec social network dataset contains 1632803 nodes and 30622564 edges and each node has 58 attributes. However, 54 of them are difficult to encode either because they are random texts input by the user or because there is no straightforward way to turn the attributes into totally ordered ones. We first filtered out the nodes that contain invalid attributes and then sample the most popular 150 female and male nodes each before picking the largest connected components of the graph formed by the popular nodes.
The original Friendster social network dataset contains 43880 nodes and 145407 edges and each node has 644 attributes. However, most of the attributes are binary, which is inefficient for STAGE encode (i.e. will need 644*2 nodes in each STAGG-edge-graphee We find out the attributes are in the format of a meta attribute (e.g. occupation) followed by more detailed attribute (e.g. writer). Therefore, we turned the binary attributes that share the same meta attribute into a multicategorical attribute. We then filtered out the nodes that have only one active binary attribute under each meta attribute (otherwise the multi-category does not make sense) and pick the largest connected components the graph formed by the these nodes.
In the end, the statistics of Pokec and Friendster datasets are available in Table
D. Experiment Details
For Figure 3, Table I, and Figure 4 We use the default NBFNet-Pa PyG configuration for the inductive WN18RR dataset (Zhu et al., 2021c), except for a few specific parameters. The input dimension for the node attribute is set to 256, and the model includes six hidden layers with dimensions [256, 256, 256, 256, 256, 256], making a total of seven layers. For STAGE, we use layer of GINEConv (Hu al., 2020) for the GNN on STAGE-edge-grann dimension 256. We also append an extra p_value each edge in the STAGE-edge-graee for expressivity, All model trained with batch size of 32 over 30 epochs.
which produces an edge representation of
For Figure 3, Figure 4, and the E- F-Commerce columns of Table I we average over seeds 0, 1, 2. For the H&M columns of Table 1, we average over seeds 1024, 1025, 1026.
For Table 2, we average over seeds 32, 33, and 34 using the following configuration. The input attribute dimension is set to 64, with 128 as the dimension of hidden channels. The model uses 2 layers of GINEConv (Hu et al., 2020). The learning
24

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Table 5: Zero-shot test Mean-Square Loss (lower is better) of STAGE and baselines on the Pokec dataset with regression tasks on predicting the user's s age. Models were trained on the same sample of the Friendster dataset in Section 4. All models show the same bad performance on doing this very challenging task because the root mean squared error (RMSE) of constantly predicting the mean of all age values is 10.7. We use the same configurations as Table 2. N/A means the model does not support node regression tasks.
Model
RMSE (1)
GINE Strruuttuttural
10.99 + 0.000
GaNE-gaussian
10.99 + 0.000
GiNE-normalized
10.99 + 0.000
GINE-IIm
10.99 + 0,000
GINE-age
10.99 + 0.000
GraphyAny
N/A
GCOPE
N/A
GINE-STAGE (Ours) 10.99 1 0.000
rate for the optimizer was set to 0.0001, with a dropout rate of 0.5 to mitigate overfitting. Training was carried out for 400 epochs. Additionally, STAGE deployed with layers of GNN on TTAGE-edge-grapee with GINEConv and an edge representation dimension 32. For GraphAny, we adopt the default configuration as preliminary experiments indicated that modifying hyperparameters yielded no significant performance improvements.
E. Age Regression Experiment Results
Table 5 shows that the zero-shot regression on age across different social networks is a challenging task, particularly when the age distributions of the datasets are drastically different. GraphAny and GCOPE are not included because they are designed for and only supports node classification tasks. Figure shows that the age distribution the Pokec dataset is skewed towards younger users, with notable frequencies for ages such as 0 (invalid data), 18, and 20, while ages above 42 are scarcely represented. In contrast, the Friendster dataset contains a much broader range of ages, including significant numbers of users aged in their mid-twenties, such as 25, with smaller frequencies for users up to age 91. This disparity in cerrbbuttonwwheeee Pokec's frequencies are centered around younger users and Friendster's are more spread across the adult age spectrum poses substantial difficulty for models attempting to generalize across the two networks.
F. Ablation Study
In this section, we provide ablation studies to further investigate the effectiveness and versatility of STAGE. Experiments in Appendix F.1 complement the main results in the paper by exploring whether STAGE is effective on alternative GNN backbones and configurations. Experiments in Appendix F.2 then study if STAGE can outperform model trained on the common attributes shared between train and test domain, validating whether STAGE truly leverages dependencies among unseen attributes at test time to make predictions.
F.1 Evaluating STAGE with GCN as the backhone GNN
In the main experiments, employed GINE NBFNet for link prediction and GINE + GINE for node classification as the backbone GNN configurations. A natural question arises: Can STAGE be effective when using other backbone GNN architectures? To address this, we propose GCN-STAGE (GINE GCN (Kipf & Welling, 2016)), where we replace the second GINE with a modified GCN to perform message passing on the original graph. We choose GCN as it a well-known baseline for node classification tasks. We modified GCN to process edge attributes by applying an MLP layer to edge attributes before incorporating them into the edge messages. The first GINE model operating on STAGE-edge-graphee remained unchanged.
Table 6 presents the results, which demonstrate that GCN-STAGE outperforms all baseline methods in terms of average accuracy. Comparing to the other GCN- -CN-bbacbonn models, GCN-STAGE outperforms with a 7.33% relative improvement, and achieves an across random seeds. Furthermore, same as GINE-STAGE, GCN-STAGE also outperforms GraphAny (Zhao et al., 2024b), demonstrating that STAGE is effective on both GCN and GINE, We note that, however, the gain observed with GCN-STAGE
smaller standard deviation, showcasing the stability and consistency of predictions
25

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Pokec Age Distribution
100
80
Frequency
20
Age
Friendster Age Distribution
300
200
100
60
Age
Figure 5: Comparison of Age Distributions in Pokec and Friendster Datasets. The top histogram shows the age distribution for the Pokec dataset, where a significant number of users have an age O, followed by noticeable peak around the age of 20. The bottom histogram illustrates the age distribution for the Friendster dataset, with a strong concentration users around the age of 25, and smaller presence of older individuals.
is slightly lower than that of GINE-STAGE as shown in Table 2. This is not surprising, GCN has been shown to have lesser expressivity than GINE (Xu et al., 2018).
These results demonstrate the effectiveness STAGE regardless of the backbone GNN architecture (GINE or GCN), reinforcing the versatility and general applicability of STAGE across tasks and architectures, further solidifying its strength robust framework.
F.2. Comparison with models trained on common attributes
In the second ablation study, we aim investigate whether STAGE truly leveraging dependencies among multiple unseen node attributes make zero-shot predictions on the test domain, rather than simply relying on the common attributes shared between train and test. In particular, the attribute "price" and "brand" shared between the E-commerce datasets (Appendix C. and the attribute "age" is shared between Friendster and Pokec (Appendix C.3). Hence, we compare STAGE to a model with the same backbone GNN trained to utilize the shared attribute to make predictions. We name these models NBFNet-price on E-commerce datasets for link prediction, and GINE-age on Friendster and Pokec for node classification. We do not experiment with training on the "brand" attribute because its values are distinct (or the distribution have different supports) in different product categories.
26

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Table 6: Zero-shot test accuracy (higher is better) of STAGE and baselines on the Pokec dataset. Models were trained on a sample of the Friendster dataset. GCN-STAGE demonstrates the best zero-shot test accuracy, surpassing all other methods in both average accuracy and stability.
Model
Accuracy (1)
GCN-structural
0.547 1 0.0658
CCN-gaussian
0.567 0.0382
GCN normalized
0,570 + 0.0315
GCN-IIN -Im
0,526 + 0.0300
GraphAny
0.591 = 0.0083
GCOPE
0.535 0.0153
GCN-STAGE (Ours)
0.593 + 0.0046
Table 7: Zero-shot Hits@I and MRR NBFNeI-STAGE and NBFNet-price on the E-Commerce dataset. Models are trained on all combinations of four graph domains and tested on the remaining domain. NBFNet-STAGE significantly outperforms NBFNet-price, demonstrating that STAGE effectively utilizes more information than common attribute (price) shared between attribute domains.
Model
Hits@ (1)
MRR (1)
NBFNet-price NBFNet-STAGE (Ours)
0.2713
0.0280
0.3263 1 0.0301
0.4606 0.0123
0.4971 1 0.0073
Tables 7 and 8 shows the results of this ablation study. NBFNet-STAGE outperforms NBFNet-price with relative improvement of 69.8% and GINE-STACE outperforms GINE-age with a relative improvement of 12.0%. These results corroborates our statement that STAGE is capable of leveraging complex dependencies among multiple attributes to make predictions, even when said attributes are unseen during training, as STAGE significantly outperforms the models relying only on shared attributes.
G. Interpreting STAGE
In Section 4, we demonstrated STAGE has a strong performance when zero-shotting to unknown attribute domains. A natural question arises: how does STAGE recognize unseen attributes during zero-shot testing, and which attributes are most relevant for making predictions? To address this, we conduct a qualitative analysis of STAGE's behavior using saliency maps (Erhan al., 2009; Simonyan al., 2013). This method computes the gradients of the model's outputs with respect to the input data, quantifying how much each input influences the model's prediction.
We train NBFNet-STAGE STAGE all 5 categories of the E-Commerce dataset. We then perform zero-shot inference the H&M dataset, obtaining triplet scores for missing edges. Let G = (V, E, X) be the input graph of the H&M dataset with d attributes, T be the set of ground-truth triplets in H&M, and M(t E T be the model's output triplet score. Recall Sue (f2+d)fi+d)) for each pair of attributes fi, f2 and every edge (u, v) E E. We compute the saliency of attribute pairs, E f2), follows:
that STAGE transforms raw attribute values into edge attributes Suv fi Sur (ff+d) Sh f1(s++d)-
aM(t)
@M
OM
@M
Eo.T(fi,.2) = Σ
aSu0 fif2
8S fi(fedd)
dSw
a5(h+4)(a+o))
1ET (a.))E
(f+t)(
0M(t)
@M())
@M
0M(t)
SSuv fafa
aSuv fa(h+d)
SSue fa(f++d)
0See
(12+0)(11a)))
Thus, (a, indicates how the pair of attributes f1. fa jointly influence the model's output predictions.
One of the most striking aspects of STAGE is its ability to recognize relevant attribute dependencies zero-stho at inference time (i.c., without requiring fine-tuning). To investigate this phenomenon, we examine the saliency values of every pair of product attributes f1, fa in the H&M dataset during zero-shot inference.
Figure presents a heatmap of these normalized saliency values FGGT (f1, f2). The color bar indicates that lighter shades
27

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Table 8: Zero-shot test accuracy of GINE-STAGE and GINE-age on the social network datasets. Models are trained on Friendster and zero-shot tested on Pokec. GINE-STAGE outperforms GINE-age, demonstrating that STAGE effectively utilizes more information than common attribute (age) shared between attribute domains.
Model
Accuracy (1)
GINE-price
0.582 + 0.0657
GINE-STAGE (Ours)
0.652 + 0.0042
1.0
product type
product group
0.8
graphical appearance
colour group
perceived colour value
0.6
percelved colour master
department
0.4
product index
product index group
section
garment group
product type
pimduct group
graphical appedrance
percelved colour value
colour group
percorved cobur mastor
dep department
producct on
product indor group sectron
garment group
0.0
Figure 6: Saliency heatmap of the product attribute pairs in the H&M dataset. A lighter color indicates a larger gradient of the model's outputs w.r.t. the pair of attributes, hence the attribute pair is more relevant to the model's predictions. attributes that describes the product's type and categories- "product type", "department", "section", "garment group" generally are more relevant, whereas product indexes- "product index", "product index group" - are least relevant to the model's predictions.
correspond to larger saliency values, signifying a greater impact on the model's output. Surprisingly, we find that certain attribute pairs exhibit high saliency values, such as "product type", "department", "section", and "garment group" because these attributes form a natural hierarchical taxonomy that effectively narrows down and defines specific products. product's 's identity is progressively constrained through this hierarchy, from department (e.g., Ladies), section (e.g.. Clothes), to garment group (e.g., Dresses), to specific product type (e.g., Cocktail Dress). Each level in this taxonomy provides increasingly specific product categorization, making these attribute pairs particularly informative for product identification and classification. This is notable because these attributes are not explicitly labeled or weighted in our dataset; instead, STAGE has learned to recognize their importance while pretained on the different attribute space of E-commerce.
In contrast, attribute pairs like "product index" and "product index group" demonstrate low saliency values. This makes sense, as these attributes are arbitrary numerical identifiers that carry no semantic meaning about the product's characteristics, intended use, or target demographic. Unlike meaningful attributes that describe product properties, these index values are simply database artifacts used for internal record- reeord-keeping.. However, the fact that STAGE can distinguish between relevant and irrelevant attributes without explicit guidance is testament to its ability to capture subtle patterns in the data.
These results are particularly remarkable because they emerge from zero-shot inference, where all attributes are unseen and no fine-tuning has been performed. This suggests that STAGE is capable of generalizing to new domains and tasks, even when faced with unfamiliar attribute sets. Our findings reinforce our main experimental results in Section 4, providing further evidence of STAGE's ability to capture pertinent attribute relationships for effective task performance zero-shot.
28

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Table 9: Average per-epoch training and inference time on E-Commerce dataset and zero-shot Hits@ performance of NBFNet-STAGE and baselines on H&M dataset. Time measured on an 80GB A100 GPU and averaged across 3 training epochs. NBFNet-STAGE is 7.83% % slower in training than the fastest baseline NBFNet-IIm and 17.02% slower in inference than the fastest baseline NBFNet-raw, while being respectively 103% and 933% better.
Model
Wall Time per Training Epoch (8)
Inference Time Test (8)
Zero-shot Hits@1 I on H&M
NBFNet-raw
318.65
66.
0.0005 + 0.0004
NBFNet-gaussia
322.13
69.04
0.0925 0.0708
NBFNet-structural
322.31
69.78
0.2231 + 0.0060
NBFNet-IIm
316.55
67.57
0.2302 + 0.0015
NBFNet-normalized
316.87
68.36
0.2286 + 0.0010
NBFNet-STAGE (Ours)
341.36
77.42
0.4666 1 0.0020
H. Complexity Analysis and Runtime Comparison
H.I. STAGE Time Complexity
Here analyze the time complexity of STAGE. In particular, analyze NBFNet-STAGE (used for link prediction) and GINE-STAGE (used for node classification).
Let be the number of attributes, the dimension of internal node and edge embeddings, | the number of edges, and [V] the number of nodes in the input graph. For all tasks, STAGE consists of three steps:
1. Fully Connected -TgGE-edge-raphh Construction: This step requires O(Eldd) operations because each fully connected STAGE-edge-gue graap has 2d nodes, and each edge in the original graph induces fully connected STAGE-edgg- graph.
2. Inference STAGE-edge-graphs:: We use 2 shared layers of GINE for all STAGE-edge- A single layer one fully connected STAGG--ddge-raag has complexity O(dh + dh = hd) since we have 2d h-dimensional nodes and (2d)² h-dimensional edges in each STAGE-edge-graph, Obtaining edge embeddings across all STAGE-edge-graphs takes O(E))hh)
Inference on the original graph: For link prediction tasks, we use NBFNet to perform message passing on the original graph, which requires O(E / + [V]A²) for one forward pass (where one forward pass gives representations conditioned on single source node and relation, therefore, predicting links (s. q. ?) for given source node s and relation q) (Zhu et al., 2021c). For node classification tasks, we use GINE again, which requires O(E))) time.
Hence, in total, running one forward pass has a complexity of O(IB)d))+ + |E/h + [V])2) for NBFNet-STAGE, and O(E)dhh + E)) for GINE-STAGE.
H.2. Training and inference time comparison
The analysis above shows the theoretical complexity of STAGE. Now we study the computational overhead when deployed in practice. To this end, we measured the average wall time per training epoch of NBFNet-STAGE and GINE-STAGE on respectively the E-Commerce Stores dataset and the Friendster dataset (see Appendix C) as well as their average inference time on the H&M dataset and the Pokec dataset using an 80GB A100 GPU.
Tables 9 and 10 displays the runtime comparison results. We observe that in train NBFNet-STAGH 7.83% slower than the fastest baseline (NBFNet-IIm) and GINE-STAGE 49.7% slower than the fastest baseline (GINE-gaussian), while being respectively 103% and 933% better in zero-shot Hit @ on H&M. During inference, NBFNEt-STAGEE is 17.02% slower than the fastest baseline (NBFNet-raw) and GINE-STAGE is 61.6 1..8% slower than the fastest baseline (GINE-stractural), while being respectively 1 11% and 16% better in zero-shot accuracy on Pokec. The additional time is due to computing STAGE- edge-grapt embeddings during each forward pass, while building the STAGE-edge TTAG--edgg-grappss is a one-time pre- pre-procsssing step. Moreover, Table 10 shows that GINE-STAGE achieves 1.74x speedup in training and 4.01 x speedup in inference than the best baseline GraphAny, which specifically designed for the same tasks.
29

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
Table 10: Average per-epoch training and inference time on Friendster and zero-shot accuracy of GINE-STAGE and baselines on Pokec. Time is measured on an 80GB A100 GPU and averaged across 20 training epochs. GINE-STAGE is 49.7% slower in training than the fastest baseline GaNssgaus and 61.8% slower in inference than the fastest baseline GINE-structural, while being respectively 11% and 16% better. Moreover, GINE-STAGE achieves 1.74x speedup in training and 4.01 x speedup in inference than the best baseline GraphAny.
Model
Wall Time per Training Epoch (s)
Inference Time on Test (s)
Zero-shot Accuracy on Pokec
GINE-raw
0.0313
0.0067
0.558 + 0.0829
HINE-gaussian
0,0296
0,0061
0.588 : 0.0250
SINEustructural
0,0292
0,0055
0,564 0,0466
GINE-IIm
0.0322
0.0064
0,550 0.0368
norm-norrl
0.0316
0.0072
0,541 + 0.0148
GnaphAny
0.0762
0.0357
0.591 + 0.0083
GCOPE
1.0524
0.3619
0.535 1 0.0153
GINE-STAGE (Ours)
0.0437
0.0089
0.652 + 0.0042
I. Additional Discussion of Related Work
Foundation Models for Graph Data. Foundation models for graph data aim to create versatile graph models capable of generalizing across different graphs and tasks. Despite growing interest, achieving truly universal graph foundation model remains challenging, especially due to the complexities in designing a suitable graph vocabulary that ensures transferability across datasets and tasks (Mao et al., 2024). Initial efforts in this direction convert attributed graphs into texts and apply an LLM, but this methodology, while promising, risks information loss and may limit transferability (Collins et al., 2024; Gruver et al., 2024; Schwartz et al., 2024). For instance, OFA (Liu et al., 2024) uses frozen LLMs to generate attributes, and then trains a GNN to perform multiple tasks, while Chen et al. (2024b); Fatemi et al. (2024); Perozzi et al. (2024) explores the potential of LLMs as predictors or enhancers of graph- predictions. Other methods, like LLaGA (Chen et al., 2024a) and GraphGPT (Tang et al., 2024), use instruction tuning to map graph data into the LLM embedding space. Similarly, Graphtext (Zhao et al., 2023) and Unigraph (He & Hooi, 2024) adopt NLP techniques, with Graphtext (Zhao et al., 2023) translating graphs into natural language via a syntax tree encapsulating node attributes and inter-node relationships, and Unigraph (He & Hooi, 2024) learning a unified graph tokenizer in a self-supervised fashion to generalize across different attribute domains. Prodigy (Huang et al., 2023) further encodes textual attributes with an LLM and leverages prompt-based graph representations for task generalization.
In contrast, recent approaches forgo LLMs entirely. For instance, Xia & Huang (2024) employs projections of the attribute matrix to handle shifts to new datasets. We exclude this method along with two similar recent approaches (Yu et al., 2024; Zhao et al., 2024a) from our baseline comparisons. This is because these methods' end-to-end architectures for crosi-domain graph pre-training employ SVD-based dimensionality reduction primarily as an input processing step, similar to our projection method for unified input space. Given our focus on understanding the effectiveness of input space unification techniques, we study this component in isolation (c.f. the baseline raw in Section 4) rather than comparing against their full architectures which include additional mechanisms like domain tokens and coordinators. Lachi et al. (2024) employs a Perceiver-based encoder compress domain-specitf attributes into shared latent space. However, since their method requires finetuning when adapting unseen out-of-distribution datasets, it falls outside our focus on zero-shot generalization capabilities without additional training. Zhao et al. (2024b) proposes GraphAny, specifically designed for node classification, which models inference on new graphs as an analytical solution to LinearGNNs. and addresses generalization by learning attention scores to fuse predictions from multiple I LinearGNNs. However, STAGE outperforms GraphAny in Table 2. Mao et al. (2023) introduces the concept of attribute proximity as a key factor in determining the likelihood of links forming between nodes. Unfortunately, the definition of proximity still depends on the attribute space, making the method unsuitable in our settings of interest. Frasca et al. (2024) proposes into additional nodes and edges in the graph structure itself. However, adapting this technique would require modification to handle continuous node attributes, making it not directly applicable as baseline for our work.
which converts categorical node features
Another line of work addresses zero-shot domain transferability on heterogeneous graphs such as knowledge graphs, where both the nodes (entities) and edge types (relations) may be new and unseen on the test-time graph. For instance, ISDEA+ (Gao et al., 2023) proposes a set aggregation layer over the set of edge-type- -ypessfi--ppccifccc graph representations to ensure equivariance to edge type permutations. Gao et al. (2023) also proposes a theoretical framework named double
30

---

Zero-Shot Generalization of GNNs over Distinct Attribute Domains
equivariance that underlies the necessary design principles of models capable of tackling such a task. In contrast, the theoretical framework of our work addresses transferability unseen attribute domains and proposes novel connection between statistical tests and the graph regression task. ULTRA (Galkin et al., 2024) and TRIX (Zhang et al., 2024b), on the other hand, build a relation graph that captures the interactions among different edge types, and apply pipelines based on NBFNet (Zhu et al., 2021c) to ensure equivariance to edge type permutations. Similarly, InGram (Lee et al., 2023) also builds a relation graph, but its relation graph differs from ULTRA's in that computes a set of affinity scores between pairs of relations and use them as edge weights on the relation graph. comparison, the STAGE-edge-grapeee built by our method captures the statistical dependencies among different attribute dimensions of node attributes the graph. However, all of these methods rely sorely graph structure and disregard attributes in nodes. In contrast, our work focus attributed graphs, which is capable of leveraging important information carried in the node attributes.
Finally, recently Bevilacqua et al. (2025) introduced HoloGNN, a framework that learns node representations transferable across diverse graph tasks. However, HoloGNN assumes a fixed attribute domain and does not address the challenge of generalizing to unseen datasets with differing attribute spaces, which is the focus of our setting.
Maximal Invariants and Statistical Testing, Bell (1964) first explored the relationship between invariant and almost- invariant tests in hypothesis testing. Berk & Bickel (1968) and Berk (1970) extended Bell's approach to show that almost-invars invariant tests are equivalent to invariant ones under certain conditions, which are those met in our work. Later, Berk et al. (1996) explored the interplay between sufficiency and invariance in hypothesis testing by providing counterexamples that demonstrate how these concepts can differ significantly in other scenarios. Recently, Koning & Hemerik (2024) improved the efficiency of hypothesis testing under invariances for large transformation groups such as rotation or sign-flipping without resorting to sampling.
31


Reviews:
[{"review_id": "GyS9jP7BrB", "reviewer": "Reviewer_fV8y", "summary": "The paper introduces STAGE (Statistical Transfer for Attributed Graph Embeddings) to enhance the zero-shot generalization capabilities of Graph Neural Networks (GNNs). It represents node attributes using order statistics, treating node features as random variables and reconstructing them into a STAGE-edge-graph based on the probability density functions between the attributes of two nodes connected by an edge. The method employs a two-stage GNN to obtain edge embeddings and graph representations, capturing statistical information while ignoring numerical attribute values. This approach enables zero-shot generalization across datasets with different categories, names, semantics, and cardinalities. Experiments focus on small-to-medium-sized GNNs, aiming to test generalization across different datasets within the same domain.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s recognition of STAGE as *“marking a significant step towards foundational graph models”* and their positive assessment of our theory and empirical results. We will incorporate their suggestions into the revised manuscript. Below, we address their remarks:\n\n**Q1.** Building each edge a STAGE-edge-graph “increases computational overhead, limiting experiments to small-to-medium-sized graphs and preventing scalability to larger graphs.”\n\n**A1:** The computational complexity of STAGE is linear with respect to the number of edges and quadratic with respect to the number of attributes, rendering it particularly suitable for small-to-medium datasets. While this characteristic may be perceived as a limitation, we argue that it does not substantially diminish the usefulness of STAGE. In fact, numerous popular machine learning algorithms exhibit similar complexity constraints, including the Transformer Attention mechanism, which has a quadratic constraint. In the domain of relational deep learning, methods designed for small data thrive and make huge impacts on the real world.  A recent example is TabPFN [1], a foundation model for tabular data that has found extensive scientific and business applications in real-world settings despite being designed for small datasets. Certain eigen-decomposition-based GNNs also have quadratic or cubic complexity.\n\nThe effectiveness of STAGE is evident in our experiments, for instance on the Ecommerce Stores dataset, where zero-shot learning achieves a Hits@1 score of nearly 0.6 when predicting user behavior from desktop configurations described by just 12 attributes. This result underscores that the computational trade-off enables substantial performance gains in settings where computational complexity is less of a constraint than model quality and expressiveness.\n\n[1] Hollmann et al., Nature 2025. Accurate predictions on small data with a tabular foundation model\n\n**Q2.** STAGE’s “effectiveness on text attribute graphs is very limited, as shown in Appendix C3, where STAGE performs no better than other baseline methods on social network graphs.”\n\n**A2:** We believe the reviewer is referring to Table 5, discussed in Appendix E, which presents an additional experiment focusing on zero-shot prediction of *age* on social networks. As explained in Appendix E, this experiment was designed to highlight the inherent difficulty of predicting age in a zero-shot setting, given that \"age\" and \"gender\" are the only shared attributes available for node labels. Our goal was to illustrate that age prediction is fundamentally challenging across models, justifying our focus on gender prediction (Table 2). Consistent with this, neither our STAGE nor text embeddings outperformed other approaches in age prediction. All models struggled due to the significant distributional shift between age attributes in the Friendster and Pokec networks, as visualized in Figure 5.\n\nNonetheless, we agree with the reviewer that STAGE is designed to handle non-text attributes, theoretically guaranteeing generalization when considering continuous and discrete, as well as ordered and unordered attributes. We believe that extending STAGE to handle text-attribute, for instance by coupling it with an initial text encoder, represents an interesting avenue for future research, although one that requires a separate effort.\n\n**Q3.** Minor suggestions\n\n**A3:** We thank the reviewer’s suggestion on manuscript change and will include it in the updated version.", "claims_and_evidence": "The claims made in the paper are supported by referenced literature and experimental data.", "methods_and_evaluation_criteria": "The STAGE method improves the generalization of GNNs across different datasets within the same domain (e.g., e-commerce, product recommendation), namely there is a shift in feature distributions between training and test sets, but the task objectives remain the same. Compared to baseline models, STAGE shows significant improvements. The evaluation criteria involve prediction Hits@1 and MRR metrics for link prediction and node prediction tasks, providing convincing evidence.", "theoretical_claims": "The paper models graph features using order statistics from statistics, with detailed theoretical derivations that do not appear to contain errors.", "experimental_designs_or_analyses": "The main experiment focuses on link prediction, training on the E-Commerce Stores dataset and testing on untrained domains (e.g., training on bed and desk domains, testing on refrigerators and smartphones) and the H&M Personalized Fashion Recommendations dataset. Comparisons are made against various baseline methods (linear mapping, Gaussian noise, pure structural modeling, textual modeling, normalized features, and supervised structural modeling) on a unified GNN (NBFNet), measuring Hits@1 and MRR metrics, which is reasonable.", "relation_to_broader_scientific_literature": "The proposed STAGE method models graph data from a non-parametric statistical perspective, seeking invariant statistical properties of graphs to improve cross-domain generalization of GNNs, marking a significant step towards foundational graph models.", "essential_references_not_discussed": "The paper does not omit any essential related references.", "other_strengths_and_weaknesses": "The core of the STAGE method involves modeling and reconstructing each edge in the original graph into a STAGE-edge-graph, which increases computational overhead, limiting experiments to small-to-medium-sized graphs and preventing scalability to larger graphs.\n\nThe modeling method requires graph attributes to be continuous values or discrete categories, so the main experiments focus on the e-commerce domain. However, its effectiveness on text attribute graphs is very limited, as shown in Appendix C3, where STAGE performs no better than other baseline methods on social network graphs.", "other_comments_or_suggestions": "In Section 3.1, the first paragraph, \"e.g., R^d for d ≥ 1, where the total order ≤ is well defined\" should have a letter after the ≤ symbol.", "questions_for_authors": "No questions at present.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NJADflPLDQ", "reviewer": "Reviewer_7ofD", "summary": "This paper studies the zero-shot generalization of GNNs under the shift in attribute domains. They propose the STAGE algorithm that aims to model the statistical dependencies between node attributes that can be invariant across domains instead of the original node attribute. Specifically, STAGE creates the edge graph for each edge that models the conditional probabilities between attribute pairs from each edge end points. Then, they use one GNN to generate edge embeddings based on edge graph probabilities and another GNN to output the embeddings for task. The paper also includes theoretical justification in terms of the expressiveness and transferability of STAGE. Lastly, the experiments on various node classification and link prediction tasks show the effectiveness of STAGE.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s recognition that STAGE “can be useful in many real-world adaptation scenarios,” and thank them for acknowledging STAGE’s versatility, as well as for their appreciation of our theoretical motivation and experiments. We now address their comments.\n\n**Q1:** “..It might still be interesting to compare to foundation models that claim to have zero-shot generalization ability.”\n\n**A1:** We already include GraphAny in Table 2, a baseline claimed to have zero-shot generalization ability. Per your suggestion, we include another foundation model, namely GCOPE [1] in Table 2 (reporting zero-shot test accuracy on Pokec, trained on Friendster), and report the results below. Notably, **STAGE outperforms the GCOPE foundation model by 21.9%.**\n\n| | **Accuracy** (↑) | **% gain** |\n|--|--|--|\n| GraphAny | 0.591 ± 0.0083 | 10.3% |\n| GCOPE | 0.535 ± 0.0153 | 21.9% |\n| STAGE | 0.652 ± 0.0042 | 0% |\n\n**Q2:** “How do you view the effectiveness of this method under the structure shift and will STAGE become problematic under the presence of structure shift?” And “Is it possible to compare with graph OOD works in the same settings?”\n\n**A2:** Our experiments account for substantial structural variation, as shown in Table 3 (Appendix C), where the number of nodes, edges, and average degrees often double from training to testing. Despite this, STAGE consistently outperforms other baselines in all zero-shot settings (Figure 3), demonstrating its effectiveness in scenarios where both the attribute domain and the structure shift.\n\nNonetheless, we acknowledge that STAGE does not make explicit assumptions about structural shifts, but it also does not impose constraints on them, and can be integrated with any GNN supporting input edge embeddings. We anticipate that integrating STAGE with existing graph-OOD GNNs, which are explicitly designed for structural shifts (e.g., varying graph sizes), could further enhance performance in these settings.\n\nFinally, to the best of our knowledge, existing graph OOD methods (e.g., those in [2]), focus on structural shifts but do not address the attribute space shifts we consider, which include changes in the number of attributes between train and test. As a result, **existing graph OOD methods cannot be evaluated in our setting**. We will clarify this distinction in our revision and include related works on graph OOD.\n\n**Q3:** “The complexity of creating edge graphs still remains concerning and limits the usage on large datasets.”\n\n**A3:** The computational complexity of STAGE is linear in the number of edges and quadratic in the number of attributes, rendering it particularly suitable for small-to-medium datasets. While this characteristic may be perceived as a limitation, we argue that it does not substantially diminish the usefulness of STAGE. In fact, numerous popular machine learning algorithms exhibit similar complexity constraints, including the Transformer Attention mechanism, which has a quadratic constraint. In the domain of relational deep learning, methods designed for small data thrive and make huge impacts on the real world.  A recent example is TabPFN [3], a foundation model for tabular data that has found extensive scientific and business applications in real-world settings despite being designed for small datasets. Certain eigen-decomposition-based GNNs also have quadratic or cubic complexity.\n\n**Q4:** “The current design only considers the pairwise relations, which is a rather simplified version of the attribute hypergraph”\n\n**A4:** Our STAGE-edge-graph captures marginal probabilities (e.g., P(A), P(B), P(C)) and pairwise conditional probabilities (e.g., P(A|B)) among attributes of node pairs. However, we agree that this representation requires additional assumptions about independence to recover joint probabilities of three or more attributes. While extending STAGE to incorporate these higher-order interactions is theoretically possible, it would result in increased complexity, whose exploration represents an important research direction on its own.\n\n**Q5:** “What design corresponds to assigning unique attribute identifiers to label the nodes of our STAGE-edge-graphs and what design corresponds to dropping the attribute identifiers?”\n\n**A5:** In a STAGE-edge-graph, labeling each node with the attribute ID of an endpoint node corresponds to assigning unique attribute identifiers. In contrast, our design of representing each node solely by its probability density function, without the attribute ID, corresponds to dropping the attribute identifiers. We will incorporate it in the next revision, thank you.\n\n[1] Zhao et al., 2024. All in One and One for All: A Simple yet Effective Method towards Cross-domain Graph Pretraining\n\n[2] Zhang et al., 2025. A Survey of Deep Graph Learning under Distribution Shifts: from Graph Out-of-Distribution Generalization to Adaptation\n\n[3] Hollmann et al., 2025. Accurate predictions on small data with a tabular foundation model", "claims_and_evidence": "**Strength:**\n- Investigating the change of attribute domains can be useful in many real world adaptation scenarios\n- The idea of statistical dependencies between attributes rather than raw features are interesting and novel\n\n**Weakness / Questions:**\n- This paper only focuses on the shift in attribute domains, but in reality it is rather rare that the graphs only shift in terms of the node attribute domains. How do you view the effectiveness of this method under the structure shift and will STAGE become problematic under the presence of structure shift?\n- The paper claims to work only for the small to medium datasets with controlled number of attributes, which limit the practical usage of the algorithm.", "methods_and_evaluation_criteria": "**Strength:**\n- Interesting idea and clear explanation in the methodology section. \n- The design is not restricted a specific type of shift in attribute domains and consider some detailed setting like unordered and ordered types of attributes.\n- Can be applicable to different types of tasks, e.g node classification and link prediction.\n\n**Weakness / Questions:**\n- The complexity of creating edge graphs still remain concerning and limit the usage to large datasets\n- The current design only considers the pairwise relations, which is a rather simplified version of the attribute hypergraph", "theoretical_claims": "**Strength:**\n- Detailed and extensive theoretical motivation of STAGE\n\n**Question:**\n- Potentially can have a better connection to the actual design of the STAGE algorithm more. For instance, what design corresponds to \"assigning unique attribute identifiers to label the nodes of our STAGE-edge-graphs\" and what design corresponds to \"dropping the attribute identifiers\".", "experimental_designs_or_analyses": "**Strength:**\n- The empirical improvements are significant\n- The datasets span different types of tasks and domains\n\n**Weakness:**\n- limited size of datasets as mentioned above\n- The baselines are rather simple and lack of potential related baselines. Even if this paper targets specifically attribute domain shift, it might still be interesting to compare to foundation model that claims to have zero-shot generalization ability. Also, is it possible to compare with graph OOD works in similar settings.", "relation_to_broader_scientific_literature": "The key contribution is the idea of statistical dependencies that might can be transferable under the change of attribute domains.", "essential_references_not_discussed": "It can be more comprehensive if you have a more in-depth discussions on graph generalization under distribution shifts, like graph OOD. Also, the works included in the discussion are rather outdated. Specifically, you can discuss the similarity and difference in the shifts considered and how your method compared to previous literatures.", "other_strengths_and_weaknesses": "Please refer to the above sections.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please refer to the above sections.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qsDYXYXrsB", "reviewer": "Reviewer_3CxP", "summary": "The paper introduces STAGE, a novel framework designed to overcome the challenge that traditional GNNs face when node attributes in test graphs differ from those seen during training. Rather than relying on raw attribute values, STAGE computes statistical dependencies between pairs of attributes by constructing a dedicated “STAGE-edge-graph” for each edge. A two-stage GNN approach is then applied: one GNN extracts edge embeddings from these graphs, and a second GNN uses these embeddings (while discarding the original node attributes) to produce the final graph representation. The method is underpinned by theoretical analysis and is validated through experiments across diverse datasets.\n\n## Update after Rebuttal\n\nMost of my concerns have been addressed, and I will maintain my current score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for recognizing our theory is “rigorous and well-founded.” We now address their comments.\n\n**Q1.** “The approach is quadratic in complexity concerning the number of attributes, which may limit its applicability to very large graphs or datasets with high-dimensional attribute spaces.”\n\n**A1:** While the quadratic complexity may be perceived as a limitation, we argue that it does not substantially diminish the usefulness of STAGE. In fact, numerous popular machine learning algorithms exhibit similar complexity constraints, including the Transformer Attention mechanism, which has a quadratic constraint. In the domain of relational deep learning, methods designed for small data thrive and make huge impacts on the real world. A recent example is TabPFN [1], a foundation model for tabular data that has found extensive scientific and business applications in real-world settings despite being designed for small datasets. Certain eigen-decomposition-based GNNs also have quadratic or cubic complexity. \n\n[1] Hollmann et al., 2025. Accurate predictions on small data with a tabular foundation model\n\n**Q2.** “Could the authors provide an empirical comparison or toy visual example that highlights how order statistics capture invariant relationships better than normalized raw values in Sec. 3.1? How does the use of order statistics handle outliers or tied values in attribute distributions?”\n\n**A2:** Thanks for the suggestion. Next, we present a toy example adapted from the Ecommerce dataset to illustrate why order statistics are superior to normalization for domain transfer. \n\nDomain 1 (Train - Computers have attribute power_supply_watts):\n\n- Computer A: 800 W\n- Computer B: 600 W\n- Computer C: 450 W\n- Computer D: 300 W\n\nDomain 2 (Test - Refrigerators have attribute energy_rating):\n\n- Refrigerator A: 4.0 [A] \n- Refrigerator B: 3.0 [B]\n- Refrigerator C: 2.0 [C]\n- Refrigerator D: 1.0 [D]\n\nNow assume there exists a correspondence between Computer A and Refrigerator A, Computer B and Refrigerator B, and so on. This correspondence arises because users who prefer high-powered computers tend to select refrigerators with better energy ratings. When encoding these attributes, we need a representation that preserves this user preference pattern across domains, despite the different attribute scales.\n\nWith z-score normalization, the values become different across domains:\n\n- Product A: 1.42 vs 1.34\n- Product B: 0.34 vs 0.45\n- Product C: -0.47 vs -0.45\n- Product D: -1.28 vs -1.34\n\nWith order statistics, namely STAGE, *the values remain identical* in both domains:\n\n- Product A: 0.25 (1/4 products)\n- Product B: 0.5 (2/4)\n- Product C: 0.75 (3/4)\n- Product D: 1.0 (4/4)\n\nTherefore, while normalization produces different values for the corresponding products, order statistics preserve consistency across domains by capturing ranking information, which is invariant to monotonic transformations. Additionally, by focusing on ranks, order statistics are inherently robust to outliers, and ties are handled by assigning the average rank to all tied items.\n\n**Q3.** “Could the authors provide more theoretical or experimental illustration on how this loss of identifiers affects model expressiveness, especially in cases where attribute order might carry implicit information?”\n\n**A3:** Without attribute identifiers, the model may lose the ability to distinguish attributes. For instance, consider two edges e1 and e2 in the original graph, and two features f1 and f2. If f1 has CDF value v1 in e1 and v2 in e2, while f2 has CDF value v2 in e1 and v1 in e2, with all other features having identical CDFs in both edges, then the two STAGE edge-graphs become isomorphic. In this case, STAGE produces identical edge embeddings for e1 and e2, even though the actual attribute distributions differ, limiting the model's expressivity and ability to distinguish them. However, our empirical analysis suggests this theoretical limitation has minimal practical impact. As shown in Figure 6, STAGE effectively captures meaningful attribute relationships even without explicit identifiers.\n\n**Q4.** “Could the authors discuss how sensitive STAGE is to the diversity of training domains theoretically or experimentally?”\n\n**A4:** Figure 4 shows that STAGE benefits from diverse training domains. STAGE’s performance consistently improves as we increase the number of training domains, with higher median values and tighter confidence intervals for both Hits@1 and MRR metrics. This suggests that STAGE effectively leverages the diversity in multiple graph domains to learn more robust and transferable representations. In contrast, the other baselines show minimal or inconsistent improvements with additional domains.\n\n**Q5.** “The limitation of STAGE seems not to be discussed in the manuscript.”\n\n**A5:** We acknowledge the limitations of STAGE on larger graphs in Sections 1 and 4. We appreciate the reviewer's suggestion and will further clarify them in the revision.", "claims_and_evidence": "The paper’s main claims—that STAGE can achieve zero-shot generalization by learning domain-independent statistical dependencies between node attributes—are supported by both rigorous theory and comprehensive experiments. The theoretical claims (e.g., Theorems 3.2–3.4) are backed by detailed proofs (in Appendix B) and the experimental results show significant improvements (up to 103% gain in Hits@1 for link prediction and improved node classification accuracy) compared to baselines. One minor concern is that the evidence is demonstrated on small to medium-sized datasets; thus, the scalability and robustness on very large graphs remain somewhat unverified.", "methods_and_evaluation_criteria": "The proposed method—constructing STAGE-edge graphs that capture pairwise statistical dependencies and using a two-stage GNN framework—is innovative and well aligned with the problem of handling distinct attribute domains. Overall, the methodological choices and evaluation setup are sensible, though the quadratic complexity for the number of attributes may limit its applicability in larger-scale settings.", "theoretical_claims": "I examined the theoretical contributions, particularly the proofs related to Theorems 3.2, 3.3, and 3.4. These proofs appear rigorous and well-founded.", "experimental_designs_or_analyses": "Yes, I checked the soundness of the experiment section.", "relation_to_broader_scientific_literature": "The paper is well-contextualized within the literature on graph neural networks, domain adaptation, and zero-shot learning.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "This paper’s strength lies in its innovative STAGE framework, which unifies heterogeneous node attributes via statistical dependencies backed by rigorous theory and extensive empirical validation across diverse datasets. For the weaknesses:\n1. The approach is quadratic in complexity concerning the number of attributes, which may limit its applicability to very large graphs or datasets with high-dimensional attribute spaces.\n2. While experiments on small to medium-sized datasets are promising, how well STAGE scales and performs on much larger real-world graphs remains to be seen.", "other_comments_or_suggestions": "No.", "questions_for_authors": "1. Could the authors provide an empirical comparison or toy visual example that highlights how order statistics capture invariant relationships better than normalized raw values in Sec. 3.1? How does the use of order statistics handle outliers or tied values in attribute distributions?\n\n2. \"Then, by dropping the attribute identifiers in STAGE-edge-graphs, we sacrifice maximal expressivity but ensure that STAGE is invariant to permutations of the attribute order. \"Could the authors provide more theoretical or experimental illustration on how this loss of identifiers affects model expressiveness, especially in cases where attribute order might carry implicit information?\n\n3. Could the authors discuss how sensitive STAGE is to the diversity of training domains theoretically or experimentally? \n\n4. The limitation of STAGE seems not to be discussed in the manuscript.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IRp9EAEvhO", "reviewer": "Reviewer_aT2i", "summary": "The authors study the problem of generalizing GNNs to new graphs that have distinct node/edge attributes. This is a very important problem when attempting to create graph foundation models, as different graphs will often have very different attributes. These attributes will differ not only in dimension size, but in semantic meaning as well. The authors propose a new technique, STAGE, to handle this problem. It first works by constructing a new graph for each node pair (u, v) based on the node attributes (i.e., a \"STAGE graph\"). Each node corresponds to one attribute and the graph is fully connected. The \"node attributes\" in the STAGE graph consider the pdf between node attributes. A GNN is run on the STAGE graph for each edge to produce an edge embedding. A second GNN is then run on the original graph where the edge weights are the edge-level embeddings from the previous stage (original attributes are discarded). The authors study the generalization ability of STAGE, showing that it can generalize to unseen node attributes better than baselines.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for recognizing that our paper “should hold great interest to many in the field of Graph ML” and that STAGE can help alleviate the significant “impediment to the creation of graph foundation models.” We now address their remarks.\n\n**Q1.** “There is still overlap in the semantic meaning of many node attributes.” \n\n**A1:** Our Ecommerce dataset comprises five product categories with semantically different attributes. Even when attributes appear semantically similar, they represent fundamentally different attribute domains with different values and distributions. For instance,\n\n- Bed material can be Wood, Metal, Composite\n- Shoe materials can be Leather, Synthetic, Canvas\n\nThis highlights STAGE’s ability to transfer across attribute domains that do not overlap in the semantic meaning, making it well-suited for diverse real-world applications.\n\n**Q2.** “Have you tested the ability of STAGE to generalize across graph domains (e.g., from E-commerce and social networks)? If not, would it be possible to test this using additional datasets? To be clear, this experiment isn't necessary.”\n\n**A2:** Our E-commerce datasets focus on temporal link prediction, while the social networks involve node classification. The social network data lacks edge creation times, so we cannot perform the same link prediction task. Additionally, the social network classification task is binary, while the E-commerce data does not have a directly comparable binary task. That said, we share the reviewer’s curiosity, and if they have suggestions for a suitable shared task on a different dataset, we would be happy to explore them.\n\n**Q3.** “The authors mention that NBFNet-Gaussian seems to plateau after 3 graphs. However, the same can be said for STAGE. In reality, the mean performance of STAGE when going from 3 to 4 graphs is barely different.”\n\n**A3:** Thank you, we will revise our statement to be more precise. While not the only method showing improvement, STAGE demonstrates particularly favorable scaling properties with additional graph domains. Specifically, STAGE exhibits notably tighter interquartile ranges compared to NBFNet-Gaussian at higher domain counts, suggesting more reliable performance across different domain combinations. Additionally, STAGE's lower whiskers consistently rise with more domains, showing that even its worst-case scenarios improve with more training data - a pattern less pronounced in NBFNet-Gaussian.\n\n**Q4.** “Would you be able to include the results when holding out each of the 5 E-Commerce dataset?”\n\n**A4:** We will include them in the revision.\n\n**Q5.** “STAGE is quadratic with regards to the number of node attributes” “This severely limits the real-world potential of STAGE, as it can only handle graphs with few attributes.”\n\n**A5:** While the quadratic complexity may be perceived as a limitation, we argue that it does not substantially diminish the usefulness of STAGE. In fact, numerous popular machine learning algorithms exhibit similar complexity constraints, including the Transformer Attention mechanism, which has a quadratic constraint. In relational deep learning, methods designed for small data thrive and make huge impacts on the real world. A recent example is TabPFN [1], a foundation model for tabular data that has found extensive scientific and business applications in real-world settings despite being designed for small datasets. Certain eigen-decomposition-based GNNs also have quadratic or cubic complexity. \n\n[1] Hollmann et al., 2025. Accurate predictions on small data with a tabular foundation model\n\n**Q6.** “STAGE requires separating attributes into those that are ordered and unordered. As such, some manual pre-processing must be done beforehand.” “This can further be quite tedious when many node attributes exist. However, this is a smaller weakness as it only needs to be done once.”\n\n**A6:** We agree that this step may require upfront effort. However, it's worth noting that for categorical attributes, this processing can be done in lieu of mapping them into one-hot encodings, which is a common practice in ML pipelines. Additionally, for unordered attributes that are not categorical, it is likely that a pipeline already exists and can be repurposed.\n\n**Q7.** “Some more intuitive explanation can be given for why STAGE considers the conditional probabilities of different node attribute types between nodes.”\n\n**A7:** Thank you, we will include it in the revision. The key intuition is that zero-shot generalization requires focusing on statistical relationships between attributes rather than absolute values. By modeling conditional probabilities, STAGE recognizes patterns across different attribute spaces. For instance, instead of learning specific rules like 'phones with 8GB RAM tend to be expensive,' STAGE learns abstract relationships such as 'high values in X_1 correlate with high values in X_2,' enabling knowledge transfer across domains with different attributes.", "claims_and_evidence": "Overall I believe the claims are well supported by evidence. Theoretically, they show that STAGE has good transferability potential. They further include experiments that seem to demonstrate empirically.\n\nHowever, currently the authors only show that can transfer models within **graph domains**. Note that this is distinct from attribute domains. For example, all the E-commerce datasets are E-commerce graphs (with the same being said for H&M). Furthermore, Pokec and Friendster are both social networks. As such, even though they contain distinct attributes there is still overlap in the semantic meaning of many node attributes. \n\nThis is perfectly fine, however I think it's worth emphasizing that the current results don't show the ability of STAGE to transfer across domains (e.g., train on E-commerce and test on a social network). If possible, I encourage the authors to add such results.", "methods_and_evaluation_criteria": "I think the GNNs used for STAGE and the baselines compared against are suitable. While other baselines exist, the authors choose those that are most common. Furthermore, the evaluation criteria is well aligned with common practice.", "theoretical_claims": "I read them, however, I didn't look at them in detail.", "experimental_designs_or_analyses": "Most of the experiments are well-designed with good analyses.\n\nHowever, I think it can be improved in a few instances:\n\n1. The authors argue that STAGE is the only method to consistently increase in performance when considering more graphs (Figure 4). However, this doesn't seem to be true, as NBFNet-Gaussian still increases. The authors mention that NBFNet-Gaussian seems to plateau after 3 graphs. However, the same can be said for STAGE. In reality, the mean performance of STAGE when going from 3 to 4 graphs is barely different.\n2. In Table 1 the authors only show the performance when holding out E-Commerce Store and H&M. It would be better if they can also include the raw results when holding out the other 4 E-Commerce datasets. It's fine if this is in the Appendix. I think it would be good to see how consistent this observation is across different hold-out datasets.", "relation_to_broader_scientific_literature": "This paper is well-situated in the current field of Graph ML. A big impediment to the creation of graph foundation models is that different graphs can contain wildly different node features/attributes. As such, a method that can help alleviate this problem is highly sought. As such, I believe this paper should hold great interest to many in the field of Graph ML.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "I include a few other weaknesses below:\n\n1. I think the current efficiency results (Tables 9 and 10) downplay the inefficiency of STAGE. As noted, STAGE is quadratic with regards to the number of node attributes (during graph construction and STAGE-edge inference). The current results only show a slight increase in runtime. However, this is mainly due to the fact that the current graphs tend to have very few node attributes (at most 16). However for graphs with more node attributes, STAGE will quickly become impractical to run. This can be seen by the fact that the authors reduce the number of attributes in the original Friendster dataset (644) to a much smaller number.\n\n   This isn't inherently a bad thing. However, this severely limits the real-world potential of STAGE, as it can only handle graphs with few attributes. For example, we can look at the OGB datasets [1], which are common graph datasets. ogbn-arxiv, which is used for node classification has 128 node features. For link prediction datasets, ogbl-collab and ogbl-citation2 have 128 features while ogbl-ppa has 58. It would be impractical to run STAGE on any of these methods (irrespective of graph size).\n\n2. Currently STAGE requires separating attributes into those that are ordered and unordered. As such, some manual pre-processing must be done beforehand. In fact, for some datasets it may not even be known whether some attributes are truely ordered or unordered. This can further be quite tedious when many node attributes exist. However, this is a smaller weakness as it only needs to be done once.\n\n[1] Hu, Weihua, et al. \"Open graph benchmark: Datasets for machine learning on graphs.\" Advances in neural information processing systems 33 (2020): 22118-22133.", "other_comments_or_suggestions": "1. I think some more intuitive explanation can be given for why STAGE considers the conditional probabilities of different node attribute types between nodes. It becomes clearer after reading Section 3. However, when reading Section 2, it's unclear why STAGE is designed in this manner. It may help if the authors can provide a brief intuitive explanation early in Section 2 to better motivate this design before jumping into the details.", "questions_for_authors": "1. Have you tested the ability of STAGE to generalize across *graph domains* (e.g., from E-commerce and social networks)? If not, would it be possible to test this using additional datasets? To be clear, this experiment isn't *necessary*. However, I think if STAGE can show such transferability, it would greatly enhance the utility of the method. As currently, the authors only show that STAGE can generalize across *attribute domains* among graphs in the same domain (e.g., E-Commerce).  \n\n2. Would you be able to include the results when holding out each of the 5 E-Commerce dataset?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents STAGE, a novel framework for enabling zero-shot generalization of GNNs across distinct node attribute domains. By modeling statistical dependencies between node attributes using order statistics and a two-stage GNN pipeline, STAGE effectively abstracts away from raw attribute values, allowing transfer across domains with mismatched attribute sets. The paper is well-motivated, theoretically grounded, and supported by strong empirical results on both link prediction and node classification tasks. Reviewers agree that the proposed approach addresses a relevant and challenging problem in graph learning. While concerns remain about STAGE's scalability due to its quadratic complexity with respect to the number of attributes, the authors provide a compelling case that the method is effective and practically useful for small to medium-scale graphs. The rebuttal thoroughly addresses reviewer questions, offering additional comparisons and clarifying theoretical design choices. Overall, this is a solid contribution that opens up a promising direction for domain-agnostic graph representation learning, and I recommend acceptance.
Decision: Accept (poster)