Holographic Node Representations: Pre-training Task-Agnostic Node Embeddings
Authors: Beatrice Bevilacqua
Joshua Robinson
Jure Leskovec
Bruno Ribeiro
Venue: ICLR 2025 Poster (2025)
Keywords: GNN
symmetries
pretraining
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose holographic node representations, a new blueprint for node representations capable of solving graph tasks of any order.

Abstract: Large general purpose pre-trained models have revolutionized computer vision and natural language understanding. However, the development of general purpose pre-trained Graph Neural Networks (GNNs) lags behind other domains due to the lack of suitable generalist node representations. Existing GNN architectures are often tailored to specific task orders, such as node-level, link-level, or higher-order tasks, because different tasks require distinct permutation symmetries, which are difficult to reconcile within a single model. In this paper, we propose _holographic node representations_, a new blueprint for node representations capable of solving tasks of any order. Holographic node representations have two key components: (1) a task-agnostic expansion map, which produces highly expressive, high-dimensional embeddings, free from node-permutation symmetries, to be fed into (2) a reduction map that carefully reintroduces the relevant permutation symmetries to produce low-dimensional, task-specific embeddings. We show that well-constructed expansion maps enable simple and efficient reduction maps, which can be adapted for any task order. Empirical results show that holographic node representations can be effectively pre-trained and reused across tasks of varying orders, yielding up to 100% relative performance improvement, including in cases where prior methods fail entirely.

Published as a conference paper at ICLR 2025
HOLOGRAPHIC NODE REPRESENTATIONS:
TRAIIINGN TASK-AGNOSTIC NODE EMBEDDINGS
Beatrice Bevilacqua
Joshua Robinson
Purdue University
Stanford University
bbevilac@purdue. edu
joshrob8cs joshro0@ss.staaford.eee wtw.ssrd.aaooddooooooooooo
Jure Leskovec
Bruno Ribeiro
Stanford University
Purdue University
jure@stanford.edd
ribei bibeirobb@puddee.ed edu
ABSTRACT
Large general purpose pre-trained models have revolutionized computer vision and natural language understanding. However, the development of general pur- pose pre-trained Graph Neural Networks (GNNs) lags behind other domains due to the lack of suitable generalist node representations. Existing GNN architec- tures are often tailored to specific task orders, such as node-level, link-level, higher-order tasks, because different tasks require distinet permutation symme- tries, which difficult reconcile within single model. In this paper, we propose holographic node representations, a new blueprint for node representa- tions capable of solving tasks of any order. Holographic node representations have two key components: (1) task-agnostic expansion map, which produces highly expressive, high-dimensional embeddings, free from gode-permutation symme- tries, to be fed into (2) a reduction map that carefully reintroduces the relevant permutation symmetries to produce now-dimensional, task-specific embeddings. We show that well- well-constructed expansion maps enable simple and efficient reduc- tion maps, which can be adapted for any task order. Empirical results show that holographic node representations can be effectively pre-trained and reused across tasks of varying orders, yielding up to 100% relative performance improvement, including in cases where prior methods fail entirely.
INTRODUCTION
The development of node embeddings capable of effectively solving multiple tasks remains an un- solved problem in graph learning (Mao et al., 2024). Just LLMs have demonstrated the ability to generate versatile representations that can be adapted for a variety of downstream tasks (Radford al., 2019; Gemini Team al., 2023; OpenAI, 2023), there is growing need for graph models that can produce embeddings versatile enough to solve new tasks not foreseen at train time. Despite sig- nificant advancements in Graph Neural Networks (GNNss, most existing approaches remain highly specialized, which limits their broader applicability across diverse graph tasks.
Existing embeddings are typically designed for specific types of tasks, or "task orders", and often struggle with others. For example, embeddings optimized for node classification (an order-1 task) may not work well for link prediction (an order-2 task) (You al., 2019; Srinivasan & Ribeiro, 2020; Zhang et al., 2021), and vice-versa This challenge extends to higher-order tasks, and embeddings intended handle various tasks generally fail to perform well on any task. A crucial yet often over- looked reason for this failure is that different task orders possess different permutation symmetries, which are difficult to program into a single model. This specifiiyy of existing models hinders the development of general pre- trained node representations that can be adapted any graph task.
In this work, we revisit the notion of node embeddings to create holographic node representations, a new type of node representations specifically designed to be pre-trained and then adapted to any task order. The key innovation is a new treatment of node permutation symmetries. Instead of immedi- ately introducing potentially undesirable symmetries, is commonly done with standard permuta-

---

Published as a conference paper at ICLR 2025
tion equivariant GNNs (Bronstein et al., 2021), holographic node representations the majority of their computation to learn an expansion map which produces deserrddee symmetry- representations. These are then fed into reduction map, which introduces task-specific symmetries to produce embeddings tailored for the task. The reduction map is lightweight, allowing it to be efficiently adapted and learned for each new task order. The core idea is that, regardless of the pre- training task order, a suitable reduction map can always be constructed and learned anew for new tasks of any order, leveraging the output of the expansion map the pre-trained node embeddings.
In addition to introducing a suitable notion of representations for order-agnostic embeddings, we present the first practical instantiation of this concept, which we call HoloGNN. The key technical challenge we address is how to add and remove permutation symmetries. For the symmetry freee expansion map, we combine standard message passing model with repeated symmetry breaking by perturbing node features, producing sequence of flat embeddings for each node, each able to capture different information fragments. We demonstrate that this design provably able to express eigenvectors without sign basis ambiguities, which ensures HoloGNN is able to capture rich graph features (Belkin Niyogi, 2003). The reduction map fuses together the sequence of representations for task task-specific groups of nodes to output any-order (node-, link-, and higher-orden representations. We also prove that our combination of expansion and reduction maps produces maximally-expressive representations from permutation symmetry perspective.
We experimentally validate our approach, showing that HoloGNN is able to learn representations that transfer between task orders consistently and significantly outperforming the baselines. For instance, on the CORA dataset, the performance of HoloGNN decreases by only 1.5% when pre- trained on link prediction and adapted to node classification, while standard GNNs show a 7% performance drop, and link-prediction models such as NBFNet (Zhu et al., 2021) and SEAL (Zhang & Chen, 2018), experience a significantly larger drop of up to 41%.
In summary, our key contributions are:
(1) Introducing holographic node representations, a novel approach that allows node embeddings to be pre-trained tasks of any order and then be efficiently adapted to solve new tasks of new orders by respecting the task-specific permutation symmetries;
(2) Presenting HoloGNN, the first practical architecture for learning holographic node representa- tions, addressing the technical challenge of adding and removing permutation symmetries;
(3) Theoretically and empirically demonstrating that holographic node representations offer signif- icant improvements in generalization to new tasks, providing highly expressive representations that consistently outperform existing methods, irrespective the pre- pre-training task order.
Notation. Let G (A, be graph, where A {0, 1 jaxn is the adjacency matrix and X Baxds the node features. We write v E [n] = {l..... n to denote a node in G, or equivalently V. For node embeddings F(A,))
IRd of node E [n]. Similarly, for f(A, X) E RaxTxd, f(A. X), denotes the R'xd slice. We denote the permutation group on [n] by S.,, which is the collection of all bijective maps [M] + [n]] In general,
Rad f(A.X) X)u denotes the embedding
for tensors X E IR x2)xdz, we write Xs E Rdd for set S C [r]] of cardinality For S, we define t o = (i) i E 5), and write π o X to denote the permutation of the rows of X by applying a to set S indexing them, with the permutation action. Finally, 2 denotes the power set of [n].
2 PERMUTATION SYMMETRIES AND TASK GENERALIZATION
An often overlooked aspect of graph learning is the task-specific nature of existing embeddings, typically designed for a particular task "order", which is the size of the set of nodes involved in the predictions. For example, node classification involves predictions for individual nodes (order- I), while link prediction for pairs of nodes (order-2). Since there are many important graph tasks of different orders, there is need for powerful models producing embeddings suitable for all orders.
However current embeddings are task-order specific. One reason for this is that many existing embeddings are structural, meaning that the embeddings do not depend the IDs of each node. Crucially, the exact permutation group describing this invariance is not universal, but is inherently dependent on the task order. This is clearly reflected in the fact that the cardinality of the required
2

---

Published as a conference paper at ICLR 2025
embeddings for structural representations is determined by the task order itself, as can be seen in the definition of structural representations.
Definition 2.1 (Structural Representations), Let S be a set of r nodes of a graph G = (A, X). A function f : {0, wrnl x Raxd, x())xd returns structural representations of order if f is equivariant to permutations of the nodes, that is if (A, = f( ( π X) TOS, for any π E Sn
In other words, a function returns structural representations if it produces embeddings that are equiv- ariant under any permutation of the node ordering. Within this class, there is clean notion of most- expressive representation, which occurs when isomorphic node sets share the same representation (necessitated by Definition 2) and all non-isomorphic sets have distinct representations.
Definition 2.2 (Most-Expressive Structural Representations), A function f : {0, 1|mxx x xR"xdz RR()) xd returns most-expressive structural representations of order r if for every graphs G X), G' = (') and sets of nodes S, S' of cardinality r, f(A, = f(A', X')ss iff 3n E S,, such that A = π A', X = क o X', S S'.
A most-expressivv structural representation is sufficient to solve any task of that order (Srinivasan & Ribeiro, 2020). However, in general, the most expressive struc- tural representation of one order is not also the most ex- pressive structural representation of another order. For instance, Srinivasan & Ribeiro (2020) and Zhang et al. (2021) prove that a most-expressive structural represen- tation of order-1 I tasks cannot serve as most-expressive structural representation for order-2 tasks, as show in Fig- ure 1. Because of this, it is not possible to pre-train sin- gle structural representation that is most-expressive and therefore able to solve tasks of any order.
Figure I: Nodes U2 and v3 are isomor- phic; links (v), U2) and (M44, 0a) are iso- morphie; links U2) and (U1, Us) are not isomorphic. However, if we aggre- gate most-cxpressive node representa- tions as the link representation, (#1, 02) and (v1, 02) will get the same predic- tion. Example from Zhang et al. (2021).
In addition to structural representations, positional ones, such those derived from eigenvectors (Belkin & Niyogi, 2003; Dwivedi et al., 2023), play im- portant role in graph learning. Unlike structural embeddings, positional embeddings assign distinct embeddings to isomorphic node sets. While positional embeddings can be highly effective for tasks requiring the unique placement of nodes within a graph, they tend to underperform on others (Srini- vasan & Ribeiro, 2020). For instance, positional embeddings often perform well in link prediction tasks, where the relative positions of the node endpoints are critical (Lim et al., 2023). However, they are less effective for node tasks, where node similarity should reflect structural similarity rather than positional proximity. In other words, current positional representations are also task specific.
Challenges for learning a single embedding for different tasks. Because structural and positional representations are task specific, they are unsuitable output candidates for pre-training a single model that produces representations capable of solving tasks of different orders. This claim can be formu- lated precisely for node embeddings, which are perhaps the most important class of embeddings due to their linear scalability in the graph size, which is essential when scaling to large graphs.
Proposition 2.3 (Informal). For any node embedding model J, there exists two tasks of different orders for which at least one is not solvable using f-
The formal version of Proposition 2.3 is presented in Appendix B.1 as Proposition B.I. This im- possibility result highlights why graph machine learning has continued to rely specialized ar- chitectures tailored for specific tasks, unlike the more generalized pre-trained models seen in NLP and computer vision. It also clarifies that there is need for novel node representations that extend beyond conventional node embeddings. In the next section, we present our approach bypassing this impossibility result by representing nodes with sequences of (flat) node embeddings.
HOLOGRAPHIC NODE REPRESENTATIONS
The previous section demonstrated the need for a new notion of node representations beyond the typical single "flat" embedding vector per node. Our proposal is to use holographic node represen- tations. Holographic representations have existed outside of the graph learning context since the
3

---

Published as a conference paper at ICLR 2025
Trains from scratch representations for each task
Falls generaliza higher-arder
Sh+
X
f
Stum
Ntee
Link Task Head
Node Task
Link Task Hoad
Node Task Head
Task
Head
Plge
Model
Node Model
h
A VIA
Reduction Map
A
Foode Rediuttion Map
AY Vil.
B(A, VJ)s
Order-specific models
Pre-trained node embeddings
Pre-trained holographic node representations
While order-specific models must be retrained for each new task, holographic node rep- resentations can be adapted to new tasks. Pre-trained (structural) node embeddings cannot solve high-order tasks since isomorphic nodes get the same representation, making it impossible to differ- entiate non-isomorphic links. Instead, holographic node representations generate 2D node represen- tations (T de), where the additional T dimension captures multiple symmetry-free graph views (so isomorphic nodes can be distinguished in least one view). The reduction map reduces these representations back to ID, using A to re-introduce the correct permutation symmetries for the task.
Figure 2:
work of Feldman (1 (1986) and Hinton (1990), which studied how to store complex concepts in neural networks. At one extreme was the one-concept, one-neuron idea, and at the other was holographic representations which distributed individual concepts across neurons. These holographic represen- tations worked by producing representations conditional on different views of the data, rather than relying on single "absolute" representation. In this section, we adapt this principle to graph data, proposing holographic node representations, which produce representations conditioned on differ- ent nodes. These conditional representations overcome the impossibility result in Proposition 2.3.
Holographic node representations are defined through an expansion map and a reduction map (Fig- ure 2). The expansion map produces task-agnostic high-dimensional representations of the individ- projections of these projections is designed in way that we can
ual units of interest (in our case each node) that capture different permutation-sensine of the object. The permutation-sensitive always create a reduction map (a light-weight task-speeific map) that reintroduces the relevant sym- metries for the task at hand, producing structural representations that match the task order. In this way, regardless of the pre- pre-training task order, a suitable reduction map can always be learned for any new task of any order, using the output of the expansion map as the pre-trained node embeddings.
Holographic node representations start with structural node representations,
Garme (A, X)= Baxd,
where Jarue a learnable function returning structural node representations. This function can be as simple as a single-layer GNN or even the identity function (V1 = X). Importantly, the expres- siveness of our approach is not limited by that of garme since lost distinctions between nodes can be reintroduced in the expansion map. But formulating V1 as a general structural representation has the benefit of allowing the forthcoming expansion map to use prior efforts to obtain rich representations.
Definition 3.1 (Holographic Node Representations). Holographic node representations consist of two learnable, parameterized maps:
(1) Expansion Map:
Eg {0, 13 x xx - IR xxx x (2 x NT
(2) The expansion map, parameterized by 0, takes input the adjacency matrix and the initial structural representations, and it outputs: (a) A (T x de))-dmmesiinnal representation for each of the nodes (2D representation), denoted by Vo V1); (b) A sequence of L lists of node IDs, where nodes within each list share the same role, and nodes in different lists have distinct roles; (c) A sequence of integers, indicating how the T node representations should be grouped.
4

---

Published as a conference paper at ICLR 2025
(2) Reduction Map:
R R x (21 x NT - +R(()xdd
(3)
The reduction map, parameterized by e), takes the output of the expansion map and produces ID representations for any set of r nodes.
The mappings satisfy the following properties:
Property (1): The composition Rs o E.g produces (:) structural representations (one for each set of nodes), i.e., o Ry (Es A, Vi)) = Ry (Eo(T o A, π Vi)) for any π E Sn.
Property (2): For any undirected graph G (A, X) and isomorphic nodes u, U. G, with o v and having different neighborhoods, there exists a such that, Vo (A, Vi). * Vo Vi)u. That is, the expansion map Eg can distinguish isomorphic nodes.
Note that both Eg and Rg are neural networks, with parameters 0, th for which we introduce explicit designs in Section 4. From now on, will write E and R instead of Eg and Ry for simplicity when is unambiguous. Additionally, we denote the three outputs of the expansion map as Eg (A, V1) = (V, Vi), (/x(A, v))) E Rax x (2/m))² x N
3.1 INTERPRETING THE DEFINITION
A visual overview of holographic node representations is in Figure 2. The expansion map introduces dimension T. yielding node-level representations V(A, V1). E IR xd. for each node v, instead of the typical "flat" embeddings in Idd. This T dimension encodes positional information (Property (2)) through T distinct "views" of the graph, as shown by different colored vectors in Figure 2, addressing the impossibility result for "flat" embeddings in Proposition 2.3.
Whilst expressive, the expansion map alone does not give suitable node representations since in- formation is distributed along the T dimension, and does not respect any permutation symmetries. Property (I) ensures that the reduction map It combines the information across the T views, to out- put structural representations for any set of nodes. Since the reduction map depends on r it is order specific (r 1 for node, adapt to. The partition A is crucial in this process, as it specifies how the T representations should be grouped to obtain suitable structural representations.
for link, and on), and it is learned anew for each task aim to
While any expansion map can trivially lead to valid holographic node representations by choosing constant reduction map (e.g., R returning 0), the challenge lies in designing reduction map that generates expressive representations. We address this in Section 4, proving the expressivity of our approach by leveraging the link between positional and structural representations, building on the existence result from Srinivasan & Ribeiro (2020). A key contribution of our work is advancing this theoretical result by designing practical architectures that efficiently perform this operation.
AN ARCHITECTURE FOR HOLOGRAPHIC NODE REPRESENTATIONS
This section presents HoloGNN, architecture for learning holographic node representations, We begin by outlining how the symmetry-free expansion map is obtained through symmetry breakings, achieved by perturbing node features for selected nodes. Then, we propose two breaking methods. In Section 4.2, we describe sequential breaking, a general design inspired by numerical linear algebra methods, such as the Lanezos algorithm for computing eigenvectors (Lanczos, 1950). We formalize this connection, showing that sequential breaking generalizes eigenvector methods in learnable and canonical way. In Section 4.3, we propose a faster, special case called parallel breaking.
4.1 OVERVIEW OF SYMMETRY BREAKINGS
The intuition behind HoloGNN is to obtain the symmetry-free expansion map E through "symmetry breakings". This process breaks isomorphisms between nodes by perturbing the features of selected nodes, and then passing these modified features through structural model. The perturbed features act as node identifiers, enabling the model to learn distinct representations for isomorphic nodes, which structural model cannot do.
5

---

Published as a conference paper at ICLR 2025
The idea of injecting unique features to obtain positional representations is well-established in pre- vious work (You et al., 2019; Murphy et al., 2019; Abboud et al., 2021; Sato et al., 2021; Puny et al,, 2020: Eliasof et al., 2023). HoloGNN distinguishes itself by carefully injecting identifiers in way that a reduction map can later he designed to reintroduce order-specific permutation symmetries.
Precisely, step t initializes V1 in Equation (1). At step > 1, new node representations V2 E Raxd are produced by injecting a unique identifier, such as the standard basis vector 1,, E IR", for the breaking node v, into structural model fa (e.g., permutation equivariant GNN). The role of the breaking node e is to obtain an embedding for that distinguishes it from other nodes, which structural models cannot achieve. The breaking nodes are selected based on predefined functions known as node- wade-breaking selectors, which deterministically return lists of nodes. As we will see, the partition A is uniquely determined by the breaking nodes, and the final structural representations are produced by combining all Vi generated by breaking nodes returned by the same breaking selector.
The node- breaking selectors are defined as (hx))=1- Each selector h2 returns list of breaking nodes and must satisfy several properties:
Definition 4.1 (Breaking selector hx). For I.
(1A,1...., UAAs,) (A,
(4)
denote the X-th list of breaking nodes, sorted by node IDD. The selector hy is permutation-equiiariann meaning that if a node u is in (A, Vi), then all nodes isomorphic to e in G = (A, V/) are also included. Additionally, (hx) are disjoint, ensuring that no node is included in more than one list.
The breaking selectors can be either pre-defined or learnable functions of the input graphs. Valid choices include having each hy return all nodes with the same degree, expressive choices where each f1 returns list of all (and only) isomorphic nodes. Appendix A. expands on practical choices.
Validity of Symmetry Breakings. It may seem unclear if symmetry breaking generates E(A, Vi) satisfying Definition 3.1. In particular, one might question whether perturbing features for a single node at time is enough to produce different embeddings for all nodes in the graph. In principle it may be necessary to perturb multiple nodes at once, which would require at least quadratic number of forward passes through the structural models. Fortunately, we prove that this is not the case, and symmetry breaking with hingle-node perturbations produces valid expansion maps.
Theorem 4.2 (Sufficiency of single-node breakings for holographic representations). For any G (A, X) and isomorphic nodes u, U E G, with u. * v and having different neighhorhoods, there exists E. obtained by single-node symmetry breakings such that (A,V)) # ((A, Vi)u.
4.2 SEQUENTIAL BREAKING ALGORITHM
The sequential breaking algorithm introduces breeainy perturbations iteratively, where each new symmetry is broken on the
Algorithm Sequential Breaking
1: A = 2: x=2 3: 2
output of previous symmetry breakings. At new node embeddings V. E Raxd, are generated by a structural model fa which takes as input: (I) the adjacency A. (2) the embeddings produced in earlier steps Vi-1...., V1, and (3) perturbation 1, on the breaking node v. The breaking node v is the next node in the sequence returned by the cur- rent breaking selector h2, with the index X in- cremented when the end of the list is reached. The pscudocode is detailed in Algorithm 1.
each step
4: while
t S T do
5:
for E hx(A Vi) do
6:
V, S((A, Ve-1.... Vi, 1.)
7:
t=t 1=t+1 A -== X end for
8:
9:
10:
11: end while
12:
T
The algorithm runs until a specified maximum number of iterations, T*, However, the total number of steps T may exceed T* to ensure that the current breaking selector's list is fully exhausted. This guarantees that all nodes having the same role, and therefore in the same list, are used as breaking nodes, preventing any improper selection that could differ for isomorphic graphs, and hinder the reduction map from constructing structural representations. The expansion map is defined as:
E(A Vi) (Conca(VV Vr,..., (hx Vi)) A) Ruxxxx x (2 x N", (5)

---

Published as a conference paper at ICLR 2025
with Concat concatenating along dimension, and (A, v1)) and A saved for use in the reduction map. The reduction map uses this information to appropriately combine the embeddings V, to reintroduce permutation symmetries, adapting the representations to the task order at hand.
Expressivity of sequential breaking. Algorithm describes a very general class of representations, as evidenced by several well-known models that special cases. First, all structural models, such as GIN (Xu et al., 2019) and GCN (Kipf & Welling, 2017), are special cases by setting fi = GIN/GCN, ft Identity for & > 1, and ignoring breaking nodes entirely. Another important special case, which we prove next, is that sequential breaking can compute eigenvectors (and functions thereof). Even more importantly, sequential breaking resolves sign and basis ambiguities inherent in eigenvectors, eliminating the need for additional techniques like sign flipping (Dwivedi et al., 2023; Kreuzer et al., 2021; Kim al., 2022; Dwivedi et al., 2021) or invariant (Wang al., 2022; Lim et al., 2022; Huang et al., 2024b) and equivariant (Lim et al., 2023) networks to account for them.
Theorem 4.3 (Expansion Map can express canonical cigenvectors). For any symmetric matrix A, there exists expansion map F(A, V1) obtained by sequential breaking which can express eigen- vectors with no sign or basis ambiguity, and identical for isomorphic graphs up to permutations.
The proof is constructive, manually instantiating expansion maps that exactly correspond popular algorithms for computing eigenvectors, such as the Lanczos algorithm. Because the proof is con- structive, we are also able to prove that sequential breaking removes sign/basis ambiguities, which has practical advantages over explicit canonicalization (Kaba et al., 2023; Ma et al., 2023; 2024).
Having constructed an expressive expansion map, we are left to design appropriate reduction maps. Given two isomorphic graphs G1 and G2, there exists permutation matrix BG.+Ga such that, VC = B V. Vt E [T] (c.f., Remark B.8). A natural way to construct structural represen- tations of order r is to treat the representations of the r nodes across these isomorphic graphs as part of set. Specifically, the structural representation of {UI,.... U,} is obtained by first computing an intermediate representation at each step t, using a learnable set function Φi, which takes as input the representations of { (Ui...., .,....... 22 step t in graph G₁, i.e.,
UR = o: (( Grou Vue
(6)
Then, another learnable set function Pt aggregates the intermediate representations Uk,t for all G3.
U ( Po (UUw.) )
Finally, the reduction map can be obtained as the list of such representations for each t,
R(F(A, Vi))
(Us.fr....e))) tE(T]
key limitation of this approach is that it requires iterating over all possible n! isomorphic graphs to construct BG1-Gi, Appendix A.2 discusses practical approaches that use the breaking selectors to construct structural representations of order r, instead of iterating over isomorphic graphs.
4.3 PARALLEL BREAKING ALGORITIIM
Algorithm 2 Parallel Breaking
In practice, breaking symmetries sequentially can be slow. To address this, we introduce par- allel breaking, faster variant of the sequential approach. Parallel breaking generates embed- dings V, using structural model fx that, in addition to A, takes only perturbed version of V1 for all t, rather than all prior embeddings V Ve-....., V. In this case, the embeddings Vi for different t are only differentiated by break- ing different nodes, with perturbations obtained as Vi where O denotes concatenation. We remark here that: (1) the structural model fx is the same for all breaking nodes belonging to the same hx (as opposed differing for each in
I: A A
2: t 2=
3: 2=2
4: while t < T* do
5:
for E (A, Vi) do
6:
V, (A e 1,))
7:
t=t+1 A end for
8:
9:
10:
>=
11:
end while
12: =
7

---

for Published as a conference paper at ICLR 2025
the sequential breaking, because it does not see previous breakings); (2) since there is no dependency on the step t, all Vi can be computed in parallel. The pseudocode is shown in Algorithm 2.
Identically to sequential breaking, the maximum number of iterations is T but the total number of steps T may exceed T to ensure that the current breaking selector's list h (A, V1) is exhausted. The expansion map is defined by concatenating the embeddings Vr,..., V1 along a new dimension, while also collecting the breaking selectors (h^(4 (A, Vi)) and the partition A (c.f., Equation (5)).
For parallel breaking, the reduction map be constructed in simpler way, by aggregating repre- sentations V, obtained from breaking nodes returned by the same /t,, Specifically, for the structural representation of {v1,....: ] (i.e., of order r). we first compute an intermediate representation for each step t, using learnable set function Φx. taking the representations of {uI...., Uy at step t,
Ux = Φx ( (te
Then, another learnable set function PA aggregates the intermediate representations Ux for all obtained by breaking nodes returned by the same breaking selector, and therefore such that A X,
U U. px (1UA.)) vIe(T)
( A==))
(10)
Finally, the reduction map can be obtained as the list such representations for each X,
R(E Vi))
(Ux.(e1)..:1)))) xE(Li
(11)
The subtlety of this formulation is in which groups of representations the reduction map must be invariant to the ordering, and which groups it is beneficial to be sensitive to the order. Specifically, the bithin-breaking-ee set representations being order-invariant (Equation (10)) is essential for Ro E to representations (Equation (11)) is necessary for the representations to be expressive. Next, we show that these choices return holo- graphic node representations, and are maximally expressive in the sense of Definition 2.2.
be structural, Distinguishing the ordering of between-breade
4.4 HOLOGNN GIVES EXPRESSIVE HOLOGRAPHIC NODE REPRESENTATIONS
In the previous subsections, we introduced two designs for expansion and reduction maps: sequen- tial breaking (Section 4.2) and parallel breaking (Section 4.3). Sequential breaking enables the computation of canonical eigenvectors, while parallel breaking provides more scalable solution. Importantly, both choices define holographic node representations, as the next result shows.
Theorem 4.4 (Sufficiency of single-node symmetry breakings for structural of any order). Let R be the reduction map as defined in Equations (8) and (11). When combined with its corresponding expansion mup E, then R ((A, Vi)) is a structural representation of (vi...., Ur).
The significance of Theorem 4.4 lies in the sufficiency of single-node symmetry breakings, which are highly efficient, to generate structural representations. Moreover, we show that these breakings produce most-expressive link structural representations (per Definition 2.2) for the parallel breaking algorithm, with corresponding result for the sequential breaking algorithm in Appendix B.3.
Theorem 4.5 (Sufficiency of single-node breakings for most-expressive link structural). Let E be the parallel breaking expansion map in Equation (5) with T and let R be the reduction map as defined in Equation
(11) with r = 2. Assume Px and Φx injective, and fx node-most-exprestte structural representation of (v1, 02).
every X E [L]. Then, R(E(A, V1)) (v..2)) is a mosst-xxprsssee
While maximal expressivity can be achieved for links with single-node breakings, this result can be extended by considering multi-node symmetry breakings. Theorem B.4 in Appendix B.3 shows that breaking 1 nodes is sufficient to obtain expresxxpeesivve structural representations of order
EXPERIMENTS
We empirically study the generalization of HoloGNN between tasks of different orders performed on the same dataset. We consider a typical pre-train-adapl protocol, where HoloGNN is pre-trained on task of one order, e.g., link-prediction, and adapted to solve new task of potentially different
8

---

Published as a conference paper at ICLR 2025
CORA
Citeseer
Puttmed
Movielens
Test Metric
60
30
SEAU Low
Har Mdt
SEA
nor Nee
Gn
Holo GHE
SEAu
har nattees
SEAL
nartee
Hoto CHOOHI
SEAL
cht
SEAL
cate
Wala GRE
SEAL
ner nartes
Hoto ctN
SEAL
Halo COOGMIA
Goay
Nole GeN
SEAL
chi
Holo ann
Hoto
Wale
Pretrain on (for pretrained)
Lin
Node
Link
Node
Link
Node
Werst Fretraining Task
Test
Node
Figure 3: Performance (the higher the better) of each model when trained on one task (yellow bar) and when pre-trained on different task and adapted the task (blue bar). For each model, the more yellow visible, the larger the performance loss from using pre-trained embeddings. HoloGNN shows more consistent performance and thus smaller performance loss across all datasets and tasks.
order, e.g., node-classification. During adaptation, the expansion map remains fixed, with the pre- trained node embeddings retrieved from storage, while only the light-weight reduction map and task-specific output head are trained on the new task. The protocol for other models is the same, with an MLP output head re- re-trained on the downstream test task on fixed pre-trained node embeddings.
We implement HoloGNN using the parallel breaking algorithm with number of symmetry breakings T < 10 nn. Next we present our main results and refer to Appendix E for additional experiments.
Planetoid and MovieLens (Sen et al., 2008; Fey & Lenssen, 2019). We compare HoloGNN against SEAL (Zhang & Chen, 2018; 1: Li et al., 2020), NBFNet (Zhu et al., 2021), and standard GNN with SAGE (Hamilton et al., 2017) GCN (Kipf & Welling, 2017) layers, depending on the dataset. Notably, while both standard GNNs and HoloGNN produce pre-training node embeddings regard- less the pre-training task order, SEAL and NBFNet generate pre-training embeddings that match the order of the pre-training task, leading to significantly higher storage requirements for high-order tasks. Figure (and Tables and 4) shows the performance of each model when trained on partic- ular task (yellow bar) and when pre- pre-trained model, the more yellow visible, the larger the performance loss from using pre-trained embeddings.
different task and adapted to it (blue bar). For each
HoloGNN demonstrates significantly more consistent performance when compared to other meth- ods. For instance, in the CORA dataset, the difference in performance between HoloGNN when trained on Node Classification (81.6%) and its performance when pre-trained on Link Prediction and adapted to Node Classification (80.2%) results in a performance drop of less than 1.5%. On the contrary. SAGE suffers from a loss of 7%, while NBFNet and SEAL show a more dramatic drop of 41%. Similarly, in the MovieLens dataset, when considering the order-3 task UserMovieUsser the difference performance between HoloGNN pre-trained on the task (81.1%) and its worst perfor- mance when pre-trained in any other task (72.1%, obtained pre-training on the order-2 MovieMovie) results in a performance drop of 9%. In comparison, SAGE suffers more pronounced 22% drop, SEAL runs out of memory (OOM), and NBFNet is unable to manage tasks of order-3 (NA).
We evaluate HoloGNN on RelBench (Robinson et al., 2024), recently proposed bench- mark of graph datasets derived from relational databases. We use the rel-steaaee dataset, which is obtained from several years of activity on the Stack Exchange Q&A website. We evaluate HoloGNN on (i) two node level tasks: user eser-engagement and user-badge, where the task is to predict if a user will be active and if a user will earn a badge (community aware) in the next 3 months, and (ii) where the goal is to predict if user will comment a given post in the next 3 months. Following Robinson et al. (2024) our implementation is based on SAGE (Hamilton al., 2017), and we include task-agnostic non-learnable baselines.
RelBench.
one link-level task: user-post-comme
Results are shown in Table 1. Notably, when pre-training on node-level tasks (user-engagemeen and user-baddaee and adapting link-level (user-post -ot--pooottocccc)p)oooo-- SAGE completely fails
Our code is available at httptttt///// http///gtttttttttte wtt.:/ooobbbeeeeee /holognn

---

Published as a conference paper at ICLR 2025
Evaluation on the rel-stack dataset from RelBench. The user-post-commee task is link prediction (order-2), and the other two are node classification (order-1) tasks. HoloGNN achieves superior performance when adapted to tasks of different order than the pre-training one. Results in blue indicate cases where pre-train and test tasks are the same (i.e., supervised learning).
Table 1:
TEST TASK
comment
engagement (AUROC 7)
user badge (AUROC f>
(MAP 1)
Global Popularity
0.03+0.00 00
NA
NA
Visil
2.05++.00
TASK- AGNOSTIC
Random
NA
50.71:0.20
50.1 =0.100.00
Majority
NA
1.0.90
50.0g0.00
PRE TRAININO TASK
SAGE
0.11 05
88,2100.05
84.6=0.05
naer-post-oomment
HoloGNN
3.20++0.20
88,8+0.10
0.00: 00
90.71:0001
86.0=0.04
user-engagement
HoloGNN
2.38 33
90.61.0.01 01
87.0m0.03
SAGE
0.00
89.2t:0.01
89.0=6.00
usdr-badge
HoloGNN
1.02 21
89.42.0.05
89.0=o.05
Table 2: Link prediction AUC and runtime per epoch in the tasks of Lim et al. (2023). We show that eigenvectors obtained output of the expansion map (Algorithm 1) results in comparable or better performance than the best performing Sign Equivariant, while being significantly faster.
Erdds-Rééni
Barabdsi-Albert
Model
Test AUC
Runtime (6)
Test AUC
Runtime (5)
GCN (constant input)
.497
.0582..0
.705..01
.048 .00
SignNet (Lim et al., 2022)
.498 00
.120
.7074.00
095 00
U, Uy
.570: 01
.010:.01
.597:.01
.0881 .0
MLP(U, @ U..) Sign Equivariant (Lim et al., 2023)
.644+.02
.050+.00
.651+.00
.040+.00 .00
.75 00
.063
.7734.01
.054 .00
Eigenvectors via Expansion Map
750+.00 -00
.50++000
.816+.00
.040+000
to generalize, achieving 0.0 MAP. HoloGNN, on the other hand, successfully transfers from node- to link-level tasks. Similarly, when pre-training on the link-level and adapting node-level tasks, HoloGNN suffers a smaller drop in performance than SAGE, For instance, when transferring user-badge from user- weee--enggmment, SAGE suffers 3% drop in performance, whilst HoloGNN suffers only 2%. Note that the improved performance of HoloGNN is not simply due to being a stronger base model. When directly training on task, HoloGNN achieves identical perfor- mance to SAGE. This shows that the key differentiator between them is in their transfer properties.
Eigenvectors. To demonstrate the generality of holographic node representations, we employ the sequential breaking algorithm (c.f., Algorithm 1) to obtain eigenvectors, which we use in the link prediction task of Lim et al. (2022). Table shows that the eigenvectors returned by holographic node representations outperform the best performing methods in fraction of the time. Our approach surpasses the performance of eigenvectors obtained by conventional eigensolvers (MLP(U,,.CU with Uj. the eigenvector embedding of node i). We attribute this improvement to eigenvectors being derived from V1 (Equation (1)) which is learned on the task. That is, holographic node repre- sentations structural features to select the combination of sign and basis, resulting in represen- tations that facilitate learning rather than relying on arbitrary choices of conventional eigensolvers.
6 CONCLUSION
In this work, we study the ability of node embeddings to solve different lask orders, such as pre- dictions about single nodes, pairs of nodes, or larger Our first insight is that no existing model able to solve different task orders simultaneously. We trace the source this limitation back to the permutations symmetries possessed by different embeddings, which are task-order dependent, and therefore no single choice of symmetries suffices. To address this challenge, we propose holo- node representations, but done carefully
graphic node representations, which learn symmetry-free so that the appropriate task-order symmetries can be re- re-introduced when adapting to new task or- ders. We propose HoloGNN, the first practical model for learning holographic node representations, and show that HoloGNN leads to significant improvements when adapting to new task orders.
10

---

Published as a conference paper at ICLR 2025
Reproducibility Statement. The assumptions for theoretical results can be found in Ap- pendix B. The experimental details are outlined Appendix E. Detailed steps of the method are shown in Algorithms 1 and 2, with remarks in Appendix A.
ACKNOWLEDGMENTS
BR acknowledges support from the National Science Foundation (NSF) awards CCF-1918483, CA- REER IIS- ISS-193336 and CNS-2212166 an Amazon Research Award, and AnalytiXIN, Wabash Heartland Innovation Network (WHIN), Ford, NVidia, CISCO, and Amazon. Computing infras- tructure was supported in part by LNS-1925001 (CloudBank). This work was supported in part by AMD under the AMD HPC Fund program.
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth Inter- national Joint Conference on Artifical Intelligence (IJCAI), 2021. 6, 30
Michael O Albertson and Karen L Collins. Symmetry breaking in graphs. the electronic journal of combinatorics, 3(1):R18 18, 1996. 30
Walter Edwin Arnllii. The principle of minimized iterations in the solution of the matrix eigenvalue problem. Quarterly of applied mathematics, 911::17-2, 1951. 30
Guy Bar-Shalom, Beatrice Bevilacqua, and Haggai Maron. Subgraphormer: Unilying subgraph gnns and graph transformers via graph products. In Forty-first International Conference Ma- chine Learning, 2024a. 30
Guy Bar-Shalom, Yam Eitan, Fabrizio Frasca, and Haggai Maron. A flexible, equivariant framework for subgraph gnns via graph products and graph coarsening. arXiv preprint arXiv:2406.09291, 2024b. 30
Dominique Beaini, Shenyang Huang. Joao Alex Cunha, Zhiyi Li, Gabriela Moisescu-Pareja, Oleksandr Dymov, Samuel Maddrell-Mander, Callum Mcl.ea, Frederik Wenkel, Luis Müller, Jama Hussein Mohamud, Ali Parviz, Michael Craig. Michal Koziarski, Jiarui Lu, Zhaocheng Zhu, Cristian Gabellini, Kerstin Klaser, Josef Dean, Cas Wognum, Maciej Sypetkowski, Guillaume Rabusseau, Reihaneh Rabbany, Jian Tang. Christopher Morris, Mirco Ravanelli, Guy Wolf, Pru- dencio Tossou, Hadrien Mary, Therence Bois, Andrew W Fitzgibbon, Blazej Banaszewski, Chad Martin, and Dominic Masters. Towards foundational models for molecular learning on large-scale multi-task datasets. In The Twelfth International Conference on Learning Representations, 2024. 29
Mikhail Belkin and Partha Niyogi. Laplacian eigemmaps for dimensionality reduction and data representation. Neural compulation, 15(6)) 2003. 2,
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation net- works. In International Conference on Learning Representations, 2022. 30
Beatrice Bevilacqua, Moshe Eliasof, Eli Meirom, Bruno Ribeiro, and Haggai Maron. Efficient subgraph gnns by learning effective selection policies. In The Twelfth International Conference on Learning Representations, 2024. 30
Lukas Biewald, Experiment tracking with weights and biases, 2020. Software available from wandb.com. 34
Michael Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2 104.. 13478, 2021. 2
Runjin Chen, Tong Zhao, Ajay Kumar Jaiswal, Neil Shah, and Zhangyang Wang. LLaGA: Large language and graph assistant. In Forty-first International Conference on Machine Learning, 2024a. 29
11

---

Published as a conference paper at ICLR 2025
Zhikai Chen, Haitao Mao, Hang Li. Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, et al. Exploring the potential of large language models (Ilms) in learning graphs. ACM SIGKDD Explorations Newsletter, 25(2):42 61, 2024b. 29
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph repre- sentations. In Advances in Neural Information Processing Systems, volume 34, 2021. 30
Leonardo Cotta, Beatrice Bevilacqua, Nesreen Ahmed, and Bruno Ribeiro. Causal lifting and link prediction, In Proceedings of the Royal Society A: Mathematical, Physical, and Engineering Sciences, 2023. 17
Hejie Cui, Zijie Lu, Pan Li, and Carl Yang. On positional and structural node features for graph neu- ral networks on non-attributed graphs. In Proceedings of the s1 ACM International Conference Information & Knowledge Management, pp. 3898 3902, 2022. 30
Jan JM Cuppen. A divide and conquer method for the symmetric tridiagonal eigenproblem. Nu- merische Mathematik, 36:1 77-1 1980. 22, 23
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pp. 2126-11222111 2132, 2021. 18
Inderjit Singh Dhillon. A new O(n²) algorithm for the symmetric tridiagonal eigenvalue/eigemeector problem. University of California, Berkeley, 1997. 23
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs.
AAAI Workshop Deep Learning on Graphs: Methods and Applications, 2021. 30
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations, 2021. 7
Vijay Prakash Dwivedi, Chaitanya Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1-48, 2023. 3, 7, 30, 31
Nelson Elhage, Tristan Hume, Catherine Olsson, Nicholas Schiefer, Tom Henighan, Shauna Kravec, Zac Hatfield-oodss Robert Lasenby, Dawn Drain, Carol Chen, et al. Toy models of superposi- tion. arXiv preprint arXiv:2209. /0652, 2022. 29
Moshe Eliasof, Fabrizio Frasca, Beatrice Bevilacqua, Eran Treister, Gal Chechik, and Haggai Maron. Graph positional encoding via random feature propagation. In International Conference on Machine Learning, pp. 9202-9223, PMLR, 2023. 6
Torsten Fahle, Stefan Schamberger, and Meinolf Sellmann. Symmetry breaking. In Principles and
Practice of Constraint Programming- CP 2001: 7th International Conference, CP 2001 Paphos, Cyprus, November 26-December 1, 2001 Proceedings 7, pp. 93-107. Springer, 2001. 30
Jerome Feldman. Neural representation of conceptual knowledge. 1986. 4
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 1rXiv:9903.02228, 2019. 9, 34
Fabrizio Frasca, Beatrice Bevilacqua, Michael M Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. In Advances in Neural Information
Processing Systems, 2022. 30
Mikhail Galkin, Xinyu Yuan, Hesham Mostafa, Jian Tang, and Zhaocheng Zhu. Towards foundation models for knowledge graph reasoning. In The Twelfth International Conference on Learning Representations, 2024. 29
Jianfei Gao, Yangze Zhou, Jincheng Zhou, and Bruno Ribeiro. Double equivariance for inductive link prediction for both new nodes and new relation types. arXiv preprint arXiv:2302.011: 01313, 2023. 29
12

---

Published as a conference paper at ICLR 2025
Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew Dai, Anja Hauth, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805, 2023.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017. 9, 35
Yufei He and Bryan Hooi. Unigraph: Learning cross-domain graph foundation model from natural language. arXiv preprint MrXXi::4022116630 2024. 29
Geoffrey E Hinton. Mapping whrle hierarchies into connectionist networks. Artificial Intelli-
MaaaaMaaapin gence, 46(1-2):47-75, 1990. 4
Zhenyu Hou, Haozhan Li, Yukuo Cen, Jie Tang, and Yuxiao Dong. Graphalign: Pretraining one graph neural network on multiple graphs via feature alignment. arXiv preprint arXiv:2406.02955. 2024. 29
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint Nww:20055006877 2020. 33, 36
Qian Huang, Hongyu Ren, Peng Chen, Gregor Kržmanc, Daniel Zeng, Percy Liang, and Jure Leskovec. Prodigy: Enabling in-context learning over graphs. Advances in Neural Information Processing Systems, 36, 2024a. 29
Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, and Pan Li. On the stability expressive positional encodings for graphs. In The Twelfth International Conference Learning Representations, 2024b. 7
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In International Conference Learning Representations, 2017. 18
Gekou-Oumar Kaba, Arnab Kumar Mondal, Yan Zhang, Yoshua Bengio, and Siamak Ravanbakhsh. Equivariance with learned canonicalization functions. In International Conference on Machine Learning. pp. 15546 15566. PMLR, 2023.
Jinwoo Kim, Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners. Advances in Neural Information Processing Systems, 35: 45:14582-14595, 2022. 7, 30
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017. 7, 9, 35, 36
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 3422668-21169,, 2021. 7, 30
Alex Krizhevsky, Iya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. Advances in neural information processing systems, 25, 2012. 29
Divyansha Lachi, Mehdi Azabou, Vinam Arora, and Eva Dyer. Graphfm: A scalable framework for multi-graph pretraining. arXiv preprint arXiv:2407.11907, 2024. 29
Comelius Lanczos. An iteration method for the solution of the eigenvalue problem of linear differ-
ential and integral operators. 1950. 5, 30
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding-design provably more powerful gnns for structural representation learning. arXiv preprini 4rX1v:2009.00142, pp- 61, 2020. 30
Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. In The Eleventh International Conference Learning Representations, 2022. 7, 10
13

---

Published as a conference paper at ICLR 2025
Derek Lim, Joshua Robinson, Stefanie Jegelka, and Haggai Maron. Expressive sign equivariant networks for spectral geometric learning. In Advances in Neural Information Processing Systems, 2023. 3, 7, 10, 35
Hao Liu, Jiarui Feng, Lecheng Kong, Ningyue Liang, Dacheng Tao, Yixin Chen, and Muhan Zhang. One for all: Towards training one graph model for all classification tasks. In The Twelfth Interna- tional Conference on Learning Representations, 2024. 29
George Ma, Yifei Wang, and Yisen Wang. Laplacian canonization: A minimalist approach to sign and basis invariant spectral embedding. Advances in Neural Information Processing Systems, 36, 2023.7 7
George Ma, Yifei Wang, Derek Lim, Stefanie Jegelka, and Yisen Wang. A canonization perspective on invariant and equivariant learning. arXiv preprint arXiv:2405. 18378, 2024. 7
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: continuous re- laxation of discrete random variables. In International Conference on Learning Representations, 2017. 18
Haitao Mao, Zhikai Chen, Wenzhuo Tang, Jianan Zhao, Yao Ma, Tong Zhao, Neil Shah, Mikhail Galkin, and Jiliang Tang. Position: Graph foundation models are already here. In Forty-first International Conference on Machine Learning, 2024. 1,
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Ricck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. The Journal of Machine Learning Research, 24(1), 2023. 18, 29
Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampášek. Attending graph transformers. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. 30
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference Machine Learning. 2019. 6, 18, 30
OpenAL. Gpt-4 technical report. arXiv preprint 2rXiv:2303.08774, 2023. 1
Pál András Papp and Roger Wattenhofer. A theoretical comparison of graph neural network exten-
sions. In International Conference on Machine Learning. 2022. 30
Pál András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random
dropouts increase the expressiveness of graph neural networks. Advances in Neural Information 220099 2021. 30
Processing Systems,
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Veto,o Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, nigh-performance deep learning library. Advances in Neural Information Processing Systems, volume 32, 2019. 34
Omri Puny, Heli Ben-Hamu, and Yaron Lipman. Global attention improves graph networks gener- alization. arXiv preprint arXiv:2006.07844 077466 2020. 6, 30
Chendi Qian, Gaurav Rattan, Floris Geerts, Christopher Morris, and Mathias Niepert. Ordered sub- graph aggregation networks. In Advances in Neural Information Processing Systems, volume 35, 2022. 30
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8);9 2019. 1, 29
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for a General, Powerful, Scalable Graph Transformer. Advances in Neural Information Processing Systems, 35, 2022. 30, 34
Joshua Robinson, Rishabh Ranjan, Weihua Hu, Kexin Huang. Jiaqi Han, Alejandro Dobles, Matthias Fey, Jan E Lenssen, Yiwen Yuan, Zecheng Zhang, et al. Relbench: A benchmark for deep learning relational databases. arXiv preprint 2407 2024.
14

---

Published as a conference paper at ICLR 2025
Yousef Saad. Numerical methods for large eigenvalue problems: revised edition. SIAM, 2011. 35
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM international conference on data mining (SDM), pp- 333-341. SIAM, 2021. 6, 30
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008
Yangyi Shen, Beatrice Bevilacqua, Joshua Robinson, Charilaos Kanatsoulis, Jure Leskovec, and Bruno Ribeiro. Zero-shot generalization of gnns over distinct attribute domains. In ICML 2024 Workshop on Theoretical Foundations of Foundation Models, 2024. 29
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node em- beddings and structural graph representations. In Proceedings of the International Conference on Learning Representations, 2020. 1, 3, 5, 17, 20, 25
Maciej Sypetkowski, Frederik Wenkel, Farimah Poursafaei, Nia Dickson, Karush Suri, Philip Frad- kin, and Dominique Beaini. On the scalability of gnns for molecular graphs. In ICLR 2024 Workshop on Navigating and Addressing Data Problems for Foundation Models, 2024. 29
Jiabin Tang, Yuhao Yang, Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin, and Chao Huang. Graphgpt: Graph instruction tuning for large language models. In Proceedings of the 47th In- ternational ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 491-500, 2024.7 29
Adly Templeton, Tom Conerly, Jonathan Marcus, Jack Lindsey, Trenton Bricken, Brian Chen, Adam Pearce, Craig Citro, Emmanuel Ameisen, Andy Jones, et al. Scaling monosemanticity: Extracting interpretable features from claude 3 sonnet. Transformer Circuits Thread, 2024. 29
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. International Conference on Learning Representa- tions, 2022. 7
Lianghao Xia and Chao Huang. Anygraph: Graph foundation model in the wild. arXiv preprint arXiv:2408. 10700, 2024. 29
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019. 7
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. International conference on machine learning, pp. 40-48. PMLR, 2016.
35
Haoteng Yin, Yanbang Wang, and Pan Li. Revisiting graph neural networks and distance encoding from practical view. arXiv preprint arXiv:2011.1222. 2020. 30
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877-28888 2021. 30
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In International conference on machine learning, pp. 7134-7143. PMLR, 2019. 6, 30
Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. In International Conference on Machine Learning, 2023. 30
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018. 2,
Muhan Zhang and Pan Li. Nested graph neural networks. In Advances in Neural Information Processing Systems, volume 34, 2021. 30
15

---

Published as a conference paper at ICLR 2025
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34:9061-9073, 2021. 1, 20
Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael Bronstein, Zhaocheng Zhu, and Jian Tang. Graphtext: Graph reasoning in text space. arXiv preprini arXiv:2310.0108% 2023. 29
Jianan Zhao, Hesham Mostafa, Michael Galkin, Michael Bronstein, Zhaocheng Zhu, and Jian Tang. Graphany: foundation model for node classification on any graph. arXiv preprint 2005:22405.20445, 2024. 29
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference on Learning Representations, 2022. 30
Shuxin Zheng, Jiyan He, Chang Liu, Yu Shi, Ziheng Lu, Weitao Feng, Fusong Ju, Jiaxi Wang, Jianwei Zhu, Yaosen Min, et al. Predicting equilibrium distributions for molecular systems with deep learning. Nature Machine Intelligence, pp. 1-10, 2024. 29
Jincheng Zhou, Beatrice Bevilacqua, and Bruno Ribeiro. multi-task perspective for link prediction with new relation types and nodes. In NeurIPS 2023 Workshop: New Frontiers in Graph Learning, 2023. 29
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford net- works: general graph neural network framework for link prediction. Advances in Neural Infor- mation Processing Systems, 34:29476-29490, 2021. 2, 9, 35
16

---

Published as a conference paper at ICLR 2025
A ADDITIONAL REMARKS AND TECHNICAL DETAILS ON HOLOGRAPHIC NODE REPRESENTATIONS
In this section, we provide supplementary information, technical clarifications, and remarks on holo- graphic node representations and its practical instantiation with HoloGNN. We start by discussing in detail the definition of holographic node representations (c.f. Definition 3.1).
Properties (1) and (2) are essential to ensuring that holographic node representations can be trained in task-order agnostic way, whilst still being able map representations back to order-specific representations. Property (1) guarantees final task-specific representations are structural of order r; and Property (2) ensures that the output of the expansion map consists of T positional, and thus symmetry-free, representations, which are necessary for task-agnostic node representations due to the impossibility result from Proposition 2.3.
We further remark that Property (1) in Definition 3.1 ensures that the reduction map returns struc- tural representations for sets rather than tuples of r nodes, aligning with the observation made by Srinivasan & Ribeiro (2020) that structural representations should be defined for sets of nodes. The rationale behind this is that is not possible to distinguish between isomorphic nodes² that occupy different positions within a tuple, i.c. (01, U2, U,) and (V2, Ui.... U2) if 12 and U/ are isomorphic. Therefore all tuples containing the same nodes should be considered as the same set.
Property (2) in Definition 3.1 ensures that the expansion map E returns T positional representa- tions for each node, where each positional representation correspond "view" of the graph. Im- portantly, in the case of sequential breaking, these positional representations can be TT' (canonical) eigenvectors of any symmetric matrix of the graph (Theorem 4.3). Notably, encompassing eigen- vectors has additional implication, which is made clear in Definition 3.1 (Property 2). Specif- ically, since returning eigenvectors of AA" and A" A represents a valid expansion map output, for any undirected graph, if u and v, F v. are isomorphic nodes with the same neighborhood, then (A, Vi). = (AA, V1) (Cotta et al., 2023, Theorem 4). Therefore, we exclude this case by requiring Property (2) to hold for isomorphic nodes that do not have the same neighborhood.
While Definition 3.1 provides a general definition, HoloGNN represents a practical instantiation, which obtains the symmetry-free expansion map by breaking symmetries for selected nodes chosen by breaking selectors. Intuitively, the role of the node breaking selectors is to determine the breaking nodes to be used in the expansion map, ensuring that positional representations are constructed in a way that allows the reduction map to generate structural representations. In other words, the final structural representations are produced by combining positional representations generated by breaking nodes returned by the same breaking selector (see e.g., Equation (10)). This ensures that the final representations are the same for isomorphic node sets (and therefore they are structural). In contrast, randomly selecting breaking nodes without node breaking selectors would not ensure the same final representations for isomorphic sets, nor would provide the same representations across different runs or isomorphic graphs
Definition 4.1 outlines the properties of the breaking selectors, which are necessary for designing an appropriate reduction map capable of returning structural representations. Importantly, Defini- tion 4.1 can be specialized to define most-expressive selectors, as we present next. These most- expressive selectors are important because are those employed in the sequential breaking algorithm for obtaining eigenvectors, as we shall see in Appendix B.2.
Definition A.1 (Most-expressive breaking selector hT). A most-expressive selector is selector, as defined in Definition 1. that is most-cxpressive based on the graph topology. That is, for any two nodes u. v E G = (A, Vi), then u, V E (A, Vi) + u, u isomorphic in G based only on the graph topology A.
In other words, when using h then U1 UX,4; are isomorphic nodes in A. Importantly, each hy returns a different list (a different group of isomorphic nodes). This is always possible as non- isomorphic nodes can be distinguished by structural properties (c.g., differing degrees) other- wise they would be isomorphic which a most-expressive selector is able to capture by definition.
Two nodes u and are isomorphic if there exists a permutation of nodes that swaps and v such that the permuted adjacency and feature matrices remain identical.
17

---

Published as a conference paper at ICLR 2025
A.1 NODE BREAKING SELECTORS
Having established that the expansion map produces highly expressive symmetry-free representa- tions, we now specify how the breaking nodes are chosen. In principle any structural rule may be used to construct the breaking selectors (Definition 4.1), as long as the choice is appropriately coupled with the definition of A recover from these choices when constructing structural repre- sentations (Definition 3.1). In the following, we discuss the breaking rules we consider:
(1) Node degree. Each breaking selector h2 returns all nodes that share the same degree?. That is, we consider f2 return all nodes with the highest degree, fig to return nodes with the second- highest degree, and so forth (inverse sorting is also a possibility). Nodes returned by the same breaking selector are sorted by node ids, as per Definition 4.1. In this case, ensures that A, remains identical across all t for breaking nodes with the same degree.
(2) Learned structural distribution. Given V/, define a node-wise score - VIW E R" with learnable weights w R Then, sample I n nodes without replacement according to the distribution Softmax(ss) (s). For the learned distribution we need to compute gradients through the random sample. For this we use the thiighttthrough Gunbel-SSfttaa estimator (Jang et al., 2017; Maddison et al., 2017), to allow differentiable sampling (of k: nodes) from the distribution. This rule results in a single breaking selector h1 containing all i sampled nodes. While this rule is not permutation-eqqiiaatti usually are no isomorphic nodes. During inference, instead of sampling, we directly select the top k nodes based on their scores. If there is tie at the end (i.e., the k-th and the k + 1-th nodes have the same score), we include all nodes with the tied score, resulting in a list of at least nodes returned by hi In this way. hn is permutation equivariant in test.
in general, it can still be useful for large graphs, where there
(3) Node ids, when T n. The simplest rule involves single breaking selector, h1, that returns all nodes, sorted by their IDs. In this case, T = n because the algorithm requires iterating through the entire list of nodes before termination, making this choice less scalable than others. Furthermore, A, = 1 for all f, reflecting the uniform treatment of all nodes.
(4) Most expressive. Each breaking selector hΛ returns a list of nodes that are isomorphic to each other (Definition A. Recall that each hy must return a different list (a different group of isomorphic nodes), which is always possible as non-isomorphic nodes can be distinguished by structural properties. Practical choices include employing most-expressive GNNs, such as Murphy et al. (2019); Dasoulas et al. (2021), or also expressive GNNs whose expressivity level is sufficient to distinguish all graphs in the family of graphs considered in the tasks of interest. We refer the reader to Morris et al. (2023) for a review of expressive methods.
Finally, we remark here that there are many other valid rules for selecting breaking nodes, whose exploration we leave for future work.
A.2 A PRACTICAL SEQUENTIAL BREAKING REDUCTION MAP
Section 4.2 in the main paper presents an instantiation of the reduction map for the sequential break- ing algorithm, which leverages the representations of (vi,..., } in all graphs isomorphic to the input one. A key limitation of this approach is that it requires iterating over each possible isomor- phic graph G& to construct BC*, which is then used in Equation (6) to get the representation of (ui,..., } in Gg. An alternative strategy is consider the representations of all r sets isomorphic to fv1..... v, instead of the representations of (vI..... } for all possible Gg. However, identi- fying all isomorphic sets can be computationally intensive. A reasonable compromise is consider all sets of nodes where each node is isomorphic to a different node in {VI,.... .,,.. These in- clude the sets isomorphic to {ui...., Uy one-to-one mapping.
as well as those that are not, even if their nodes are in a
Specifically, these sets can be obtained from our breaking selectors (Ax VOD Each set Sey, is generated by replacing node v; in {UI,..., } with another node taken from the same breaking selector list, i.c.,
8 (UI,... Ut Wi, Us-1,... )r)
Any other structural property can be used in this case, e.g., betweenness centrality.
18

---

Published as a conference paper at ICLR 2025
where fui,.... ) and Ve, hx(A, V1) for some À E [L]. We denote the collection of these sets as S n... that is,
(v) = {S Veee (ML.....)) w.,,
Since (A, vi)) is structural by definition (c.f., Definition 4.1), the above strategy allows us to construct the set of sets still containing all isomorphic sets to {ui,..., Jr although ((.).......) also contains more sets not isomorphic to {ui...., }. To obtain a structural representation of {Ui,..., 3r we first obtain an intermediate representation for each set 80,,0s
U Ux Φx ((V..u) v
(12)
Then, we aggregate these intermediate representations for all sets in S (v that is
U <'x = ((UX. Ve e
(13)
Next, aggregate these intermediate representations for all t generated by breaking nodes returned by the same breaking selector,
Ux pa (1Ux.t )
(14)
Finally, the reduction map can then be expressed
()) = (Ux, 1,
(15)
B PROOFS
This appendix includes the proofs for the theoretical results presented in Sections 2 and 4. We start by formally proving the impossibility of having single embedding capable of solving different task orders, particularly node and link predictions. Then, we discuss the results related to the expansion map, including connection to canonical eigenvectors. Lastly, we present the proofs concerning the reduction map.
B. SECTION 2 PROOFS
We begin by formalizing the challenges related to node embeddings and their use for solving dif- ferent tasks. Let f(A, X) Raad denote node embeddings. We define node-level task predictor and link-level task predictor, respectively, as
Y(A, MLP Bode (f(A,X),))
(A, X) uu MLP (f X).: f(A,
In practice, MLP node and MLPPink correspond
different heads on top of the single embeddings
(). This implies that f(A, X) is used for solving two different tasks, a node-level task, which we denote by Taodes and link- level task, which we denote by Tink. We define the respective test errors as:
DiaN T (D munee) = E(A,,),,, Dunk (T (Y Y.)l.
C (Diin) ((A.)).Y.. -.. Dan 14 (A, X) Yu.),,
with &Trw TTe appropriate loss functions, and denoting the test minima Ci... and Di In the following, formally prove that ((A Bax is not sufficient to accurately solve both tasks. Proposition B.1 (Impossibilityy of accurate any-order task learning from node embeddings). Con- sider simultaneously performing two tasks, Taade and Thoks using node embeddings f(A, X) E gaxd, There exist Trodte and Thnk such that, for any MLPnode node and MLP achieving the training minima, no f that produces either positional or structural representations can simultaneously sat- isfy the following two conditions: (1) L (Dnode) L (2) L (Dink) L That is. when using standard (flat) node embeddings, the predictions cannot simultaneously accurate (in test) for both tasks.
19

---

Published as a conference paper at ICLR 2025
Proof. The proof proceeds by showing that, for any f. it is always possible construct either Taede or Thnk. such that one of the conditions does not hold. Note that f returns node embeddings, which can either be equivariant node permutations, i.e., structural, not, i... positional. In the following, we will prove the theorem for these two cases separately.
Assume that f is equivariant to node permutations, and therefore structural. Then, by definition, P, and You are also invariant to node permutations. follows from Srinivasan & Ribeiro (2020); Zhang et al. (2021) that there exists a link-level task Trink such that LT.. (Dink) * L Specifically, consider the link-level task consisting in predicting in test the two non-isomorphic links (v1, u2) and (U1, 03) in Figure I, and assume that those have different labels. Since is equivariant permutations, the isomorphic nodes 1/2 and 2iy will have the same representation, and therefore (V), 02) and (o), v2)) will receive the same prediction, despite having different labels. This implies that Tia (Diin) o C since the test error can be reduced with correct predictions for these two links.
node
Assume that f' is not equivariant to node permutations, and therefore positional. Consider node- level task Thede on a training graph and consider node u. Now, assume that the test graph is composed of two disconnected copies to the training graph. This means that there are two nodes isomorphic to u in the test graph. However their representations will be different by definition of positional encoding. Since the representation seen in training for u will correspond to only of two representations seen in test, the representation of one of the test nodes may lead to incorrect predictions. Therefore CT.we (Drode) + C
Therefore, we have proved that for any I returning node embeddings, there exists a task such that one condition does not hold, which concludes our proof.
The above result justifies the need for our holographic node representations (Definition 3.1), as simply using node embeddings, coupled with different heads for different task orders, cannot result in accurate predictions for different task orders.
B.2 SECTION 4 EXPANSION MAP PROOFS
In the following, we present the theoretical results related to the expansion map, as introduced in Section 4.
We start by proving that single-node breakings are sufficient for obtaining the expansion mappings within holographic node representations.
Theorem 4.2 (Sufficiency of single-node breakings for holographic representations). For any (A, X) and isomorphic nodes u, v E G. with u * v and having different neighborhoods, there exists E obtained by single-node symmetry breakings such that VI), *
Proof. To prove the sufficiency of single-node breakings for a valid expansion map, we consider E to be the expansion map of the sequential breaking algorithm. Since the parallel breaking algorithm represents a special case of the sequential algorithm, the result will naturally extend to the parallel case as well.
By assumption, and v have different neighborhoods, and therefore there exists least one node w E G' that is neighbor of but not of (or vice-versa). Additionally, since the breaking selectors are non-overlapping (Definition 4.1) and assuming T* n. there exists a step such that the breaking node is w. Then, it is sufficient to consider the structurally invariant model fa to perform one message passing step (with identity weights) using the perturbation 1. in which case u will obtain different representation than v, is connected to w. that had perturbed features. Therefore, there exists a in which (A, V,-1...., V1, 11 1w * f( V.-i...., V1, 1 Since E is obtained by concatenating the outputs of the different fa (Equation (5)), then V(A, Vi). # V(A, Vi).. which concludes our proof.
Next, we discuss one of the main results of this section, which is to show that there exists a sequential-breakin expansion map that can express eigenvectors with no sign basis ambigui- ties. We consider symmetric matrices, which includes the normalized Laplacian matrix and the undirected adjacency matrix.
20

---

Published as a conference paper at ICLR 2025
Theorem 4.3 (Expansion Map express canonical eigenvectors). For any symmetric matrix A, there exists an expansion map EA V1) obtained by sequential breaking which can express eigen- vectors with sign basis ambiguity, and identical for isomorphic graphs up to permutations.
We prove this result by constructing explicit expansion map with T for which the embed- dings Vi...., V2 _2x1 correspond to full set of n Lanczos vectors of the symmetric matrix A (which can be the Laplacian). We then show how these Lanezos vectors can be used to obtain the full set of n eigenvectors. Crucially, we demonstrate that both the Lanczos vectors and the eigenvectors free of sign and basis ambiguities and permutation equivariant.
important to note that, while the expansion map may return Vi..... 1 the set of Lanczos vectors corresponds to Vi,-.., Vn. This is because the initial Vi is also one of the vectors (al- though obtained without breaking any node), and Vn+1 will be the zero vector (as there are only n orthogonal vectors I.").
A key intermediate step is to prove that sequential breaking can express the Lanczos algorithm, which computes the Lanczos vectors. We then demonstrate how derive the symmetric tridiagonal matrix, that is one of the terms of the Lanezos algorithm, from the Lanczos vectors and the original matrix A using simple permutation-equiias matrix shares the same eigenvalues as the original matrix A, and the eigenvectors of the original matrix can obtained from those of the tridiagonal matrix through simple matrix multiplication. Once the tridiagonal matrix is constructed, many efficient eigensolvers can be applied to produce its cigenvectors, and consequently those of the original matrix.
function. This step is crucial, as the tridiagonal
Before stating the intermediate Lanczos result, we first introduce Lanczos' algorithm in detail.
B.2.1 LANCZOS ALGORITHM
Lanczos Algorithm takes input symmetric matrix A R and returns matrix V of orthog- onal columns (the Lanczos vectors) and symmetric tridiagonal matrix T with the same eigenvalues A. Lanezos has four main steps:
1. Select an initial arbitrary vector V1 E R" with unit Euclidean norm.
2. Initial iteration:
(a) Let w1 = Avi.
(b) Let a₃ =wf V1.
(c) Let Wi = w/ a
3. For / 2,..., do:
(a) Let 3r = ||we- (also Euclidean norm).
(b) If 3t * O, then let v w
else pick as v, an arbitrary vector with Euclidean norm that is orthogonal all of Vi...., Vi-1-
(c) Let w/ Av
(d) Let a₁ = w/
(e) Let Le, w a. - B
4. Let V be the matrix with columns Vi.... Vn. Let
01
82
0
83
02
T
B3
ag
Bx-1
B
an-1
On
3n
an
Note that it is easy to obtain the tridiagonal matrix from the matrix of Lanczos vectors V, as T V AV.
21

---

Published as a conference paper at ICLR 2025
Because it is easy to obtain the tridiagonal matrix T (from which it is easy obtain eigenvectors, see Cuppen (1980)) from the Lanczos vectors, the precise statement of our intermediate result is return the Lanczos vectors. The proof of the full result (Theorem 4.3) then simply extends this by constructing a function of the Lanczos vectors and the matrix A to additionally compute T, compute the eigenvectors of T, and derive those of A. We will show that all these steps are free from sign and basis ambiguities, and additionally prove that the Lanczos vectors (and consequently the tridiagonal and the eigenvectors) are permutation equivariant.
that sequential breaking
Theorem B.2 (Sequential breaking can implement Lanczos Algorithm), For any symmetric matrix A E (0, 1 there exists an n-step expansion map E. A, X)= = .V...., Vil, where Vj is the jth Lanczos vector of A.
Proof. To prove that the sequential breaking algorithm can implement the Lanczos algorithm, we need to define the functions (= and fort E [m]] in a way that matches the steps of the Lanczos algorithm. Let's break this down step by step:
For 511 consider most-expressive breaking selectors (Definition A.I), which partition the set of nodes into isomorphism equivalence classes. We denote the breaking node of the t-step as Ut-
Additionally, take the embedding dimension d 1, want each Vi to correspond Lanczos vector.
Now, we ready define V, [A(AVV. V1, l,),, follows:
For / = 1: Vi - Gsme A, X) E R", the (normalized) vector obtained from structural function (Equation (1)). In this particular case, we assume that V1 has norm (as required by the Lanczos algorithm), and we further assume that Jstre discards node features X, because eigenvector methods do not node features but only the matrix A.
2. For l 2:
(a) w| AVI
(b) ai V w
(c) W1 w/ aa V1
(d) 32 ||]]
(e) 32 + 0: V22 W1
Bz
(f) Else: V2 1. pmiy (I,,)
E Rn where proj denotes the Gram-Schmidt projection
I| pmivy
operator of 1,, onto the span of Vi. Since V1 is a single vector, this simply V22 1., -1,, Vi
1,, (1,, V.JVi
3. Ift > 2:
(a) W/_1 = AV
(b) at-1 = VIT w
(c) Wi-1 = W/-1- - at-1 Vo-1 - Bc-1 V--2
(d) 3: |W-1ll
(e) If 1r + 0: V
W
Bi
1., pooj
vi (1,,)
(f) Else: V, Th. priy..... (T E RR, the orthonormalization of 1,, with respect
to the span of V1 V
Note that in each case this definition of ft is a composition the following permutation equiv- ariant functions: linear transformations. dot products, norms, linear combinations, and conditional statements. Because of this, ft is also permutation equivariant as required in Section 4.2.
is not at first clear that this choice of fa is well defined. The danger comes from the Gram-Schhidt orthogonal projection 1,, proj (1,,),, which must be non-zero so that it can be normalized. For now let us assume that this ft is well defined in order to show that the rest of the proof goes through. Then, the end of the proof will return to this matter.
22

---

Published as a conference paper at ICLR 2025
With these choices the sequential breaking algorithm (Algorithm 1) becomes step-by-step identical to the Lanczos algorithm, with a particular instantiation of the "arbitrary" breaking vectors, which in the sequential breaking algorithm
not random vectors in Lanczos, but are instead defined as V1 = Jamee A, x) E R and as I v, with U, the breaking node.
This formulation of the sequential breaking algorithm matches the Lanczos algorithm step by step. The key points to note are:
1. The function ft is defined to perform the exact same operations as the Lanczos algorithm for each t.
1., projy Vi- (1vg)
2. When B = 0, we choose Vi || proyy v.-1 (In,)) which for appropriate choices of
most-expressive breaking selectors is guaranteed to be unit vector orthogonal to previ- ous vectors due to the Gram-Schmidt orthonormalization projection map, as we show in Theorem B.6. This underscores that this choice of fa is well defined.
3. The output V is constructed the same way as in the Lanczos algorithm.
This demonstrates that with the given definitions of (hx)k=1 and fo for t E [n]] the sequential breaking algorithm exactly replicates the Lanezos algorithm.
We have seen that the sequential breaking algorithm can implement the Lanezos algorithm. Impor- tantly, since all choices are deterministic, with both the initial vector V1 and the arbitrary vectors determined by the most-expressive breaking selectors and therefore by the graph structure, the ob- tained I. Lanczos vectors do not have any ambiguity, with both sign and basis exactly determined by Istrue and ( Furthermore, Theorem B.7 shows that the Lanczos vectors are identical up to permutation for isomorphic graphs.
Given these results we are now ready to prove Theorem 4.3.
Proof of Theorem 4.3. Let fi..... fo and (hx) be in Theorem B.2. We construct an addi- tional function I' that, given the original matrix A and the Lanczos vectors, returns the eigenvectors of A,
U= -=r(AAV) E R
with V = [V...... Vx] and U denoting the full set of eigenvectors of A.
Specifically we define to be factorized into two steps r = T2 o Fı, corresponding to the two remaining steps required compute cigenvectors from A and Vi...., V,. which we have seen do not have sign/basis ambiguities and are identical up to permutations for isomorphic graphs.
First, 11 represents the map (A, (T, V) R.x", returning the tridiagonal matrix of the Lanczos algorithm, as well as the Lanczos vectors (this last output is included for later usage in Ig, but simply corresponds the input). Note that this I1 be written
Ti AVTAV,
since T = VT AV. Since I simply consists of two matrix multiplications, it is permutation equivariant.
Then, I2 Rax= x R + R can be any of the (fast) specialized eigensolvers for symmetric tridiagonal matrices, followed by a matrix multiplication recover the eigenvectors A from those of T'. For concreteness, we may take I2 to first perform the divide-and-conguer algorithm proposed by Cuppen (1980), which computes the eigendecomposition of in (n²) steps. Importantly, was shown by Dhillon (1997) that this divide-and-comee "twisted factorization" (see Section 3. therein) to initialize, and so the resulting eigenvectors do not have sign/basis ambiguities. Then, given the eigenvectors Umn of T, the eigenvectors U of A can be obtained as U = VÜ Importantly, since it only involves a decomposition (without ambiguities) and matrix multiplication, I2 is also permutation equivariant.
can be done deterministically using
Thus, we have shown that it is possible to recover the eigenvectors of A from the Lanczos vectors. Since both the Lanczos vectors and the mappings used to obtain the eigenvectors are free of sign
23

---

Published as a conference paper at ICLR 2025
and basis ambiguities, and are permutation equivariant, the resulting eigenvectors will also be free of these ambiguities and permutation equivariant, concluding our proof.
B.3 SECTION 4 REDUCTION MAP PROOFS
In the following, present the theoretical results related to the reduction map, introduced in Section 4. We start by showing that the reduction map designs introduced for the sequential and parallel breaking algorithms are valid, as they return structural representations of order (Property (1) in Definition 3.1).
Theorem 4.4 (Sufficiency of single-node symmetry breakings for structural of any order). Let R be the reduction map as defined in Equations (8) and (11). When combined with its corresponding expansion map E, then R (AE (r.....)) is structural representation of {vI...., U.
Proof. We will show this result for the sequential breaking algorithm and for the parallel breaking algorithm separately.
Sequential Breaking. Equation (8) trivially satisfies the definition of structural representation (Def- inition 2.1), as it returns the representation of the set (vi,..., 2r by averaging its representations across all isomorphic graphs.
Parallel Breaking. We need to show that Equation (11) satisfies the definition of structural represen-
tation (Definition 2.1). Specifically, we show that if {v1,..., ] {ui....; ]. A A', V1 V' then R(E(A, (i)) = R (EAE,,, (()..u........... Since the output of R is concate- nation of intermediate representations, it is sufficient to show that UX.(va....e.>> = U X. a.
This is trivially true because: (I) the breaking selectors are structural, and therefore breaking nodes belonging to the same selector in (A1, V1)
are isomorphic breaking nodes belonging to the same selector in (Ai, Vi), (2) ft for t E [T] is structural. Therefore the reduction map in Equation (11) returns structural representations.
Note that while we have proven the above result for Equation (8) for the sequential breaking al- gorithm, easy see that it extends also to Equation (15), by following the same proof steps used for parallel breaking. Indeed, Equation (15) similarly considers the concatenation of interme- diate representations, each obtained by aggregating representations obtained by structural models and structural selectors.
Next, we prove that the representations returned by the reduction map are nost-expressive for links. We start by showing that this is case for Equation (11).
Theorem 4.5 (Sufficiency of single-node breakings for most-cxpressive link structural). Let E be the parallel breaking expansion map in Equation (5) with = n and let R be the reduction map as defined in Equation
(11) with 2. Assume px and 6x injective, and fx dede-mostt-eppreste for every X E [L]. Then, R(E(A, (()) is a most-expressive structural representation of (Ur, v2).
Proof. Let {u,, (2) be another set of two nodes, which is different from {01, 22 We will show that Ri R(EAA, (o)))e) = R(E Vi)) [=z) iff {2) 22} ~ {ur u2). therefore satisfying the definition of most-expressive structural representations (Definition 2.2).
Recall that, since T* = n we have T = n because we need to break all the n nodes, and therefore the equations can be rewritten as
U = 6x (IVi.s Viezt)
Ux(o1.z2) PA (UUs sa N
R(E(A, (1))))))2) (aatsa))UUUUuuuuu (Ux.tu,)a)) xE|L)
For simplicity, let further denote by Se,(m,,) the set of the representations of (UI, U2 at time t, i.e., (e,(er.2) (Vi,y V.
24

---

Published as a conference paper at ICLR 2025
(=) We will show that (AE (1))(z1.zz) R(E(A, Vi)) (ur.az) fui, 02) {ui, uz). Since
PA and ox are injective, we have
(A (v1 = R(E(A, (m1,02)
+ AA E [4] (St,(ur,e)) hreen+ st. Ar=A = (St.(nnez) [ve5(1+1] at Arm
vj E in + 11,3k E [n + 1] such that (Vie V3222 = (Voos Vksuz)
which means that Vj E [n+ 1 E [n + 1] such that
{fxA V1 @ ), fx Vi 2 11 )e.) } = (fA(A,V, @
@ 1,0)
Since the above means that vj E [n + 11, 3k E [n + 1] where the sets are the same, then without loss of generality we have that
AA V1 1,)), [A @ 1
fx V1 1.,) fA 1
Consider the first equation. Since f3 is node-most-ext node-most-expressive then tn u1. which implies 3P permuting U/ with up and U1 with 1/1 such that A = PAP and V1 @ L., = P(V ① 11y)) This implies that (vy, vi) ~ (ve, u1). Similarly, for the second equation we have that (Vz, 02) (Uk, U2). Consequently, it must be (11, ~ (ui, U2) (cause if they were not, then either (rj, 0n of (Uk, u1) or (2),0)) b (Uk, U2), reaching a contradiction).
(+) We will show that {er, ]2) {u, u2) Suppose by contradiction that (AE,A, (1)))))))) & R(E(A, Vi (()) which means that there
R(E(A, (or R(E(A, V1)) fu..a>>
exist À E [Z] such that Ux # Uxderaa)) Since Φx,Pa Px are injective, this implies that
Ej E [n 1] such that
AA + Lo # fA(A e Ak [n 1 such that
= =
However, since {V1, 02) ~ {ui, 22) ) 3k [n + 1] with A À such that considering P permuting
2y with UA and Un with in is such that A = PAP and V1 + Im = P(Vi @ 1,,). Since fx is structural, then
A I.,).. SAA 1
reaching a contradiction.
Next, we show that maximal expressivity also be achieved by Equation (8).
Proposition B.3 (Sufficiency of single-node sequential breakings for most-expressive link struc- tural). Let E be the sequential breaking expansion map in Equation (5) with T = n and let be the reduction map defined in Equation (8) with = 2. Assume Pt and di are injective, and fo defined as in Theorem B.2 (that is, returning the Lanczos vectors). Then, R R(E(A, V1)) (vioo)) is a eoot-expresssive structural representation of {vi, v2)
Proof. From the proof of Theorem 4.4 we already know that R(E(A, (vr is structural. We now only need to show it is most expressive, that is R(E Vi)) V1))((,(z) (m),2)) R(E(A', (4))) * 3π S, A = A, V1 V1 and {el, 02 {0/, 2 This follows from Srinivasan & Ribeiro (2020, Theorem 2) as the Lanczos vectors are most expressive positional representations.
Li
While maximal expressivity can be achieved only for links in the case of ningle-node breakings, for the parallel breaking algorithm case, it is possible extend the result when considering molti-node breakings. Specifically, we next show that breaking r - nodes at a time is sufficient to obtain most-expressive structural representation of order
An alternative equivalent relation would be swap with us the equation.
Note that can also be equal to Uk. and in such case P permutes only vi with un. We alternatively swap Ui with vy and/or uy with Mg, without loss of generality.
25

---

Published as a conference paper at ICLR 2025
Theorem B.4 (Sufficiency of (r ( 1) -node joint breakings for most-expressive structural). Let E be the parallel breaking expansion mapping obtained by perturbing (r - 1)-nodes at a time, and let T = (- Let be the reduction mapping as defined Equation (11). Assume ps and Φx injective, and fx most-expressive structural representation of {vi....
for every X E [L]. Then, Vi)) ( is a
Proof. The proof is step-by-step identical to the proof of Theorem 4.5, with the only difference being that we break r nodes at a time to obtain most-expressive structural representations of order Let fui.... ) be another set of nodes, which is different from {ei,..., Ur). We will show that (EE (, (m..nn)..... = (A, (MI iff {u,...., 2, ~ (ui...., U ) therefore satisfying the definition of most-expressive structural representations (Definition 2.2).
Recall that, since T = (--1)) we have 7 = (--1) + because we need to break all the (.m1) set of r - nodes, and therefore the equations can be rewritten as
.x = Φx (VVie ViSTo
UN = PN (UX,evvet sa A==)) s
REE(A, Vi)) (er) (Us.t xeeo
For simplicity, let us further denote by Se.err..eer the set of the representations of {mi...., .r] at time t, i.e., St.(er........> = (Vi,e1.... Ve
(+) We will show that R(E(A,
R(E(A, Vi)) (M) = (Ui....,,,)
........ 3. Since PA and Φa are injective, we have
R(E(A, Vi)) (mr...er) = R(E(A, VI))
AY E [L] {St.(m......)) hree(T) st. A,= = {Se, (M.,(u)....,,)))) IVEE(T] st A,=
Vjj E [T], 3k [T] such that (Vam..... Vis,, (Ve,u)...., VR,,,,
which means that Vj E [7]. 3k E [T] such that [fx(A, V12 @ L., .... L.,)........
(A(A, V1 Le) (fx(A, V1 @ Ioc fA V1 1ex).. where La, (and similarly 1,,) ) is the vector with exactly r 1 ones (and n - (r - 1) zeros), at the positions specified by 82 (ji,...,fel Jr). with ji,... Jr node ids.
Since the above means that Vj E [7], EK E (T) where the sets are the same, then without loss of generality we have that
A V1 + 1111,,,) = fA(A, 11
VA = =
Consider the first equation. Since fx is node-most-expressie then 01 ~ U1, which implies 3P per- muting nodes in sj with nodes in sh and 0i with in such that A PAP and Vi $ 11, P(V + 1,y). This implies that (sj. v1) ~ (sk, u1) or, equivalently, (J1,... Jr. v1) ~ (kI,.... kr, U1 u.). Jr. 0T (ki....,hi, ),
Similarly, for all equations until the r-th equation have that Consequently, it must be (UI,...,
(u,,... ),).
(+) We will show that {UI...., J. R(E(A, (us....r
(u....., 4 + R(E(A, Vi)) (1) (e).....))
Suppose by contradiction that R(E(A, Vi Vi)) (ui R(E(A, Vi)) (w.......)) which means that there exist À [L] such that U (V.(vi....7))) Ux.(uu.... Since ox, PA are injective, without loss of generality this implies that 3j E [T] such that
X
AA LayRe # SA(AV @ LNy Vk E [n +1] such that A A = However, since (e.....,y7] fui.... ) 3k E [T] with A > such that considering P permuting 8y with sy and 01 with uj is such that A = PAP and V0l, P(V, + 1,,)) Since fA structural, then
A V + 1., = fA V + 1 11
reaching a contradiction.
26

---

Published as a conference paper at ICLR 2025
B.4 AUXILIARY THEOREMS AND PROOFS
Lemma B.5. Consider the specialization of our sequential breaking algorithm to the Lanczos al-
gorithm (c.f., Appendix B.2.1). For every step such that Br 0, if U2 is such that it exists another
Do pmm/y. Vv (1.,)
node with Vi.,, Vi, for all i < then V1 [ pmoly ..... (1. E R unit vector
orthogonal to previous vectors.
Proof. First, note that for every step t, if Be 0, then?
W = W/-1 at-1 Vi-1 - -1-1
which implies
W AV span V2-1, V1-2).
Now we only need show that 1,, $ span(Vp- V....... Vi). Assume by contradiction that instead 1n E span( Vi....... V1), and therefore it can be obtained as a linear combination of V.-....., V1. However, since by assumption Bu such that V V for all t. then the linear combination of Vi. V1 will necessarily result in a vector having the same entry for es and u, and therefore cannot be b, which in v, and 0 in u, leading to our contradiction.
Theorem B.6. Consider the specialization of our sequential breaking algorithm to the Lanczos algorithm (c.f., Appendix B.2.1). There exist most-expressive breaking selectors (bz) (c.f., Def- inition A.1) which are sufficient to always obtain breaking nodes vt such that, when Br then
Tu he.-pmyyy,.. pmiv.....VV.. (1vg)
V. [1 pmiy (l,)] E B is unit vector orthogonal to previous vectors.
Proof. The proof follows directly from Lemma B.5 by showing that there exist most-cxpressive (1 satisfying its assumptions. These breaking selectors can be easily constructed in the fol- lowing way:
(1) For the first such that 3, O, we need the corresponding h return an isomorphism class that contains more than one node. other words, the length of the list must be greater than (ke 1). Since this is the first time break symmetries, this ensure that there exists another u satisfying Lemma B.5.
(2) For any other such that 3 = 0, we also need h3 to be returning non-singleton isomorphism class. This class must be such that it exists another node isomorphic to i such that V.,,, Vr, for all < t, so that the assumptions of Lemma B.5 are met. Note that there always exist such hz, as we show next.
Assume by contradiction that there isn't I any such that Eu with Vi., = Vi, for all i < t. Then is always possible to obtain a new orthogonal vector using the Lanezos algorithm (by propagating the unique features), which implies that 3: o O reaching a contradiction.
Finally, note that such (hī) are non overlapping: whenever an h chosen to obtain corresponding uy, then the symmetry is broken and therefore using again the isomorphism class as output of another h with X' X, will not result in additional symmetry breakings, implying we need to use different non-singleton isomorphism class for later t' >> I such that Bp = 0.
Theorem B.7. Let G1 (AI, G2 (A2, X2) be two isomorphic graphs, iee, A PA, PT X, = PX,, for some permutation matrix P. Denote the Lanczos vectors of G1 as V VG,, and the Lanezos vectors of G2 as VC,,..., VC²², obtained by our sequential breaking algorithm with V,G. and Vi the normalized outputs of the structural function Jsnuc (Equation (1)) and (hx)k=1 the most-expressive breaking selectors (Definition A.I). There exists a permutation matrix B such that
VG2 BVG
(16)
Note that if
then wi w| a. Vi and the equation is valid by assuming V,-2
27

---

Published as a conference paper at ICLR 2025
Proof. For simplicity of notation, let b1
Co V1))&=n) and b2
Concat((Ix) (A2, 12))=z) be the two lists of breakings. Since b1. by are simply orderings of node ids, they can equivalently be represented by permutation matrices, which we will denote by Pb, and Po.. Let B the permutation matrix transforming b into b2, that is:
B = P..
(17)
We will prove the result by induction by showing that Equation (16) is true with B as in Equa- tion (17).
Base case. Consider t = 1. Since (hx) are most-expressive and structural, the breaking nodes in the same position in b and b2 are isomorphic. Therefore, B maps each node in G₁ node in G2 isomorphic to it, which implies
BV V/G².
Consider 2.
We distinguish two cases: (1) 82 # 0 and 0 0 (2) 3 0 and 0 0. Indeed, it is not possible have 8 # _88 as they are obtained from V, and v. using structural function.
If 32 A O, since the steps of the Lanczos algorithm outside the else-statement are all structural, since VGaa is simply permutation of VGG, and since B maps each node in G₁ to node in G2 isomorphic to it, then again
BV G. V2
If, instead, /350 = B 0, then, for each graph G i (1, given breaking node 02 we first construct the breaking vector U.C. 1 gg and then orthonormalize it using Gram-Schmin Note that since U.L1 U are standard basis vectors, which differ in that they are obtained by potentially different breaking nodes 122 G1 and G2 we have BU = U by definition of B (which indeed maps 1/2
G. into ) Therefore, denoting by VT.C the unnormalized version of V.G. we have
BVG B(U projpe (U?
BU Bproj G1 (U
BUS B(U T V
BU U T B" BV
BUG proj B (BU
U proj oo (U.
Since we have just shown that Equation (16) is true for the unnormalized vectors, then dividing both sides by the norm preserves the relationship, and therefore
BV V
Inductive step. Consider a step t - 1 < and suppose
V. G2 BVC G1
vist-
(18)
We next show that V.C² BV. We distinguish again two cases, 33 + and B, = 0.
3e # O, then the step to obtain the next Lanczos vector a structural function, and since B maps each node in G node in G2 isomorphic it, then again
BVC G1 - VVC.
If 3. = 0. then U.".UUC potentially different breaking nodes u and , and again we have BU U by definition of B. Therefore, denoting by V.G. the unnormalized version of G.
U.S² are standard basis vectors, which differ in that they are obtained by
BVC B(U
Σ proj e, (U, (U,
28

---

Published as a conference paper at ICLR 2025
i -BY
BU
proj projy
(U (U
-U
B
( V
i=1
-BU
(UG T B" BV. BV
BUC
proj proj BV (
U
proj v co (U
V,
which implies that
BVC v
since we are simply dividing both sides by the norm.
Remark B.8 (Equivariance of Vr...., VI). Theorem B.7 demonstrates that the vectors Vr...., V/ produced by the expansion map permute with the input graph. In other words, for any two isomor- phic graphs G1. G2. there exists permutation matrix B such that V.C² B BV for all t < T. This property holds for both the Lanczos vectors and any other structural function fi. In the latter case, the proof follows from Theorem B.7 by simply disregarding the 3 0 case.
C RELATED WORK
Towards Graph Foundation Models. Unlike vision and language, graph machine learning does yet have standard recipe for training general purpose models. Because of this, there is active debate on what ingredients are needed (Mao et al., 2024). Some requirements are clear, such as the need for single input feature space common to all graphs, akin a language model tokenizer (Rad- ford et al., 2019). Initial approaches include "textifying" all node features and using pre-trained text encoders to produce feature vectors (Chen al., 2024b; Liu et al., 2024), while recent works have proposed different solutions for addressing the problem of differing features across graphs (Zhao et al., 2023; Lachi et al., 2024; Zhao et al., 2024; Xia & Huang, 2024; He Hooi, 2024; Shen et al., 2024; Hou et al., 2024), including for cases where the differences are only the relation identi- fiers (Gao et al., 2023; Zhou et al., 2023; Galkin et al., 2024). Our work focuses on another crucial need: developing general- purepae- representations capable of performing multiple tasks. To best of our knowledge, there is no existing GNN-based model capable of learning representations that are suitable for different tasks. Existing effort either domain-specific (Zheng al., 2024; Beaini et al., 2024; Sypetkowski et al., 2024), or heavily rely on L.MSs (Huang et al., 2024a; Liu et al., 2024: Chen et al., 2024a; Tang al., 2024), which can present efficiency challenges (Mao al., 2024). Perhaps more crucially, no existing method offers guarantees on the expressiveness of the learned representations. Our work builds on this growing understanding of GNN expressive power (Morris et al., 2023), moving from expressivity for single task to expressivity across many tasks.
Associative Memories and Distributed Representations. Earlier neural network blueprints broadly fell into one of two extreme camps: "one concept one neuron", or distributed (holographic) representations, where an individual concept spread across many neurons. Arguments for either side were advanced partially through appeal neuroscience's 's understanding the animal brains. The deep learning era triggered by AlexNet (Krizhevsky et al., 2012) largely set this debate to one side, as modern neural networks tended to exhibit properties somewhere in the middle, with neuron-level concepts recoverable in startling detail in some cases (Templeton et al., 2024) and superimposed in other cases (Elhage al., 2022). Our effort to explicitly reintroduce holographic representations for graphs is response to the different structural properties (namely symmetries) of graph data compared to vision, language and other modalities.
29

---

Published as a conference paper at ICLR 2025
Symmetry Breaking Algorithms. The expansion map in HoloGNN uses symmetry breakings as key subroutine to produce general and expressive representations. Symmetry breakings is often used in GNNs that "color" or "mark" individual nodes in order to distinguish them, common form of positional encoding (You et al., 2019; Cui et al., 2022), oftentimes also obtained by sampling random features for each node (You et al., 2019; Murphy et al., 2019; Abboud et al., 2021; Sato al., 2021; Puny et al., 2020). Symmetry breakings has also been used as a form of distance encoding, which can be specialized for predictions of different tasks (Li et al., 2020; Yin et al., 2020). In contrast, our approach uses the same symmetry breaking for all tasks, with task specialization occurring only in the (lightway) reduction map. But symmetry breaking has been used more broadly in the analysis of graphs. Examples include in algebraic combinatorics to study the automorphism groups of different graph classes (Albertson
Collins, 1996), and in combinatorial optimization, where symmetry breaking is used to simplify complex combinatorial constraint sets (Fahle et al., 2001). Moreover, symmetry breaking is also used in gold-standare linear algebra algorithms, such as Lanczos and Arnoldi iterations for computing cigendecompositions (Lanczos, 1950; Arnoldi, 1951). In this casc, symmetry breaking is used to (randomly) resolve ambiguities in eigenspaces for eigenvalues with repeated roots. Stepping back, although symmetry breaking is a known concept in graph learning, our approach distinguishes itself by ensuring that symmetry breaking is performed in such a way that it is possible re-introduce the lost permutation symmetries and produce structural representations.
Subgraph GNNs. The concept of symmetry breaking, particularly through our parallel breaking algorithm, shares similarities with the recent works on Subgraph GNNs (Zhang & Li, 2021; Cotta et al., 2021; Papp et al., 2021; Bevilacqua et al., 2022; Zhao et al., 2022; Papp & Wattenhofer, 2022; Frasca et al., 2022: Qian et al., 2022; Zhang et al., 2023; Bevilacqua et al., 2024; Bar-Shalom et al., 2024a;b). which also break symmetries by marking nodes to enhance the expressive power of GNNs, originally proposed in Li al. (2020). However, our approach significantly differs from Subgraph GNNs in that our aim is not to produce expressive representations for a single task, but rather to pre-train models returning representations that can be used for any task. To this end, we introduce the concept of reduction map, which generates structural representations suitable for any task order. In contrast, Subgraph GNNs use their representations to revert structural node or graph-level representation. Additionally, while Subgraph GNNs generally break symmetries for all nodes in the graph, our expansion map can leverage T < n, significantly improving efficiency.
Graph Transformers. Finally, we acknowledge the growing interest in graph transformer mod- els (Kreuzer et al., 2021; Dwivedi & Bresson, 2021; Ying et al., 2021; Rampášek et al., 2022: Kim et al., 2022; Müller et al., 2024), driven by their strong performance especially on graph classifica- tion tasks. However, graph transformers rely positional encodings (Dwivedi al., 2023), which make their learned representations inherently positional. As discussed in Section 2, positional rep- resentations are task-order specific. This task-order specificity makes graph transformers unsuitable for pre-training a single model that can generate flexible representations capable of adapting to tasks of varying orders. In contrast, HoloGNN focuses on producing task task-agnostic symmetry-free repre- sentations that can efficiently adapt to different task orders.
D COMPLEXITY ANALYSIS
In this section, we analyze the complexity of the bymmetry- algorithms (Algorithm 1 and Algorithm 2), which represent the foundation of our HoloGNN.
The complexity of the algorithms determined by the complexity of ft (for sequential breaking) and fa (for parallel breaking). Suppose ft and fa are Message Passing Neural Networks (MPNNs), which have linear complexity the number of nodes n and edges m. On + m), where the feature dimension d is considered constant. Since both sequential and parallel breaking perform T calls to the corresponding MPNNs, each time by passing a new breaking node, the complexity is (T + m)) in both cases. Note that in our experiments T < n and T < m. For instance, in the Pubmed dataset, T = 8, n = 19717, m = 886448 Finally, we note that in the parallel breaking algorithm, the additional T factor in the complexity parallel. This is because each breaking is applied to V1. and fx does not take all prior embeddings.
effectively be mitigated, as all T calls can be done in
30

---

Published as a conference paper at ICLR 2025
Table 3: Performance on the Moviel dataset in each task (column), when pre-trained in each of the four tasks (row block). The diagonal (light blue) contains the performance of the models when trained and tested on the same task. "OOM" indicates out of RAM, and "NA" indicates that either the task could not be performed due to out-of-memory issues or because the model cannot perform that task order. Each column illustrates the performance drop when comparing the results of pre- training the target lask with pre-training all other lasks, with HoloGNN variants exhibiting significantly smaller drops.
MOVIELENS
UserMovic (RMSE U)
MovieMovie (Acc. f)
Movi (Acc. f
UserMovieMovie (Acc. 1)
SEAL
0.960=0.0o
0.81541..002
0OM NA
OOM NA
NBENet (oo feat)
1.011=00004
0.981+0.000
UserMowie
NBFNeet
0.967:20.00s
0.892:10.00
SAGE
0.943
0.657:10.008
0.596 002
0.589 001
SAGE LapPE
0.94920.011
0.765410.044
0.593 002
0.59240 801
HoloGNN (MP)
0.919=0.002
0.921#0.001
0.708++0,00
0.808 002
HoloGNN (GIN)
0.943=0.00m
0.918++0.00
0.741 003
0.810
SEAL
1.011=0.007
1,981+0000
0OM
OOM
MovisMosie
NBENet feat)
1.053=0.00r
0.989++0.01
NA
PRE- TRAINING TASK
NBFNet
1.050=0.007
0.089:10.001
NA 0.635 005
NA 0.667 1:.0 002 0.675+00.00 001
SAGE
1.052 004
0.977 002
SAGE & LapPE
1.015=0.008
0.975=+0.003
0.6:66+0.08
HoloGNN (MP)
1.01 1.01920.000
0.98410.00
0.6944..00 001
0.8 1.81010.000 D01
HoloGNN (GNN)
1.020=0.086
0. 0.986:10.00
0.721
0.810 004
SEAL
0OM
NA NA
NBFNet (no feat)
NA
NA
NA
NBFNer
SAGE
1.014
0.733=90.002
0.816:20.0m
0.646
SAGE & LapPE
1.01220.0m
0.793:10.00 002
0.812.1.00 006
0.647 1..77.0.000 n01
HoloGNN (MP)
1.005
0.93611..00
0.79440.00
0.779
HoloGNN (GNN)
0.991=0.on0
0.972+00.00
0.811+0.000
0.795 +0.001000
SEAL
NA
NA
NA
OOM
NBFNet (no feat)
NA
NA
NA
NBENet
NA
NA
NA
NA
SAGE
1.007
0.930.20.003
0.721 200
0.890.10.0m 007
SAGE & LapPE
0.995
0.900
0.719
0.885 008
HoloGNN (MP)
0.982=0.00
0.97:4#0.002
0.756+#0. 002
0.9041+0. D09
HeloGNN (GNN)
0.989-0.00
0.974+0.002
0.769++0.00
0.905
E ADDITIONAL EXPERIMENTS AND DETAILS
E ADDITIONAL EXPERIMENTS
In this section, we provide additional insights and results on the experiments. We also introduce additional baseline, created by concatenating structural and positional sesoodings-efeerre as SAGE& & LapPE for MovieLens and GCN & LapPE for Planetoid, using SAGE or GCN for structural encodings and Laplacian eigenvectors for positional encodings (Dwivedi al., 2023). This baseline demonstrates that simple concatenation does not achieve the performance of HoloGNN.
E.1.1 MOVIELENS
Table 3 compares the performance of HoloGNN in the MovieLens dataset. Each column represents a different task test on, namely UserMovie, MovieMovie, UserMovie MserMovieMovie. Each row block corresponds to a pre-training task, with each row being one model. This implies that each entry in the table corresponds to the performance of model (row) when pre-trained on one task (row block) and adapted to potentially different task (column). The diagonals, colored in light blue, contain the performance of each model when pre-trained and tested on the same task; in other words, each diagonal shows the performance of the supervised version of each model.
We consider four tasks, UserMovie, MovieMovie which are order-2 tasks, and Msei User, UserMovveMovii which are order-3 tasks. In particular, the UserMovie task, the standard task for this dataset, predicts a user's 's rating of a movie, MovieMovie predicts the existence of a metapath between two movies, UserMovieUser predicts if two users will both watch a particular movie,
31

---

Published as a conference paper at ICLR 2025
Table 4: Performance on the Planetoid datasets in each of the two tasks (column), when pre-trained in either of the two tasks (row block). For each dataset, the diagonal (light blue) shows the per- formance of the models when trained and tested on the same task. Each column illustrates the performance drop when comparing the results of pre-training on the target task with pre-training on the other task, HoloGNN variants demonstrate more consistent performance, with significantly smaller drops than all other methods especially when pre-trained on link prediction and tested on node classification.
CORA
CITESEER
PUBMED
Node Class.
Link Pred. (AUROC 1)
Node Class. (Acc. f)
Link Pred.
Node Class. (Acc, f)
Link Pred. (AUROC 1)
(Ace. 1>
(AUROC 1)
SEAL
77. 17.11
85.9 16.9
G4. G4.5.0.5
88.8
75.0#1.1
93.3+0.0
Node Class.
NBENet (no Teat)
31.3++1
82. 1+0.9
25.7+1..
89.6 1..
40.5+0.6
92.5+0.3
NBFNet
8..
87.5+118
50.4+2.8
88.8
71.4+2.1
95.7
GCN
81.411.0
80.910.2
70.1
89.510.s
79.011.22
93.21.0.1
GCN LapPE
81.5.0.s
90.220.5
70.0
88.520.5
78.940.3
93.5
PRE-TRA TRAINING
HoloGNN (MP)
81.5+0..
91.0+0.3
70,0+0.2
93.7+0.11
78,7+0.2
93.5+0.2
HoloGNN (GNN)
81.6 31.6-+0.7
91.1++0.4
70.1++0.
94.0++0.
78.7+0.8
93.8+00.1
SEAL
35. G+226
93. 93.5+005
31. 6
90.6+1.1
41.++111
97,8+0.2
NBFNet Teat)
33.33
94.8+0.7
222.8
92.4+1.6
40.5+0.3
98.3++0.2
Link Pood.
NBUNet
27.826.1
89.0
25.0+1.0
85.2
56.7 36.72:0.2
98.210.2
GCN
74.220.2
80.0 20.6....
68.310.2
91.410.2
76.8
96.010.7
GCN & LapPE
73.1=0.6
89.3+1.8
68. 08.14..5
91.1#0.7
75.3+0.6
95.8+0.4
HoloGNN (MP)
80.520.5
92.5.005
69.020.8
94.910.5
79.729.4
96.719.4
HoloGNN (GNN)
80.2=0.5
93.920.1
09.0+0.9
95.0+0.5
79.8
97.240.8
Move if user will watch two particular movies. For SEAL, we OOM denote that the model went out of RAM memory in the preprocessing phase, when constructing the subgraphs. We then use NA in the other tasks as the embeddings cannot be adapted to any other tasks, since they could not be learned. For NBFNet and NFBNet (no feat) (the variant that does not use node features) use NA in the order-3 tasks NBFNet cannot handle tasks of order greater than 2.
As can be seen from Table 3, HoloGNN (GNN) and its variant HoloGNN (MP), which uses simple message passing propagations as fx instead of GNN network, exhibit a significantly smaller gap in the performance when pre-trained on the task and when adapted from a different one. For ex- ample, when considering the order-3 task User the difference in performance between HoloGNN (GNN) when pre- pre-trained on the task (0.811) and its worst performance when praitrained any other task (0. (21, obtained pre-training on the order-2 MovieMovie) results in a performance drop of around 9%. SAGE shows much larger drop of around 22%, with its accuracy dropping from 0.816 when pre-trained on UserMovieessrr to 0.595 when pre-trained on the order-2 User- Movie (worst performance when pre-trained in any other task). For the order-2 task MovieMovie, HoloGNN exhibits a drop of 7%, while SAGE's drop becomes 32%. Note that this trend also holds true for all other methods, with SEAL and NBFNet consistently showing larger performance gaps than HoloGNN. The only exception is NBFNet (no feat) in the MovieMovie dataset when pre- trained on UserMovie; however, this is due to NBFNet underperforming on the pre-training task, suggesting it is merely capturing node distances rather than learning the task, which happens to suffice for Movie
E.1.2 PLANETOID
Table 4 compares the performance of HoloGNN in the Planetoid datasets Cora, Citeseer and Pubmed. Each column block represents a different dataset, and each column corresponds to a differ- ent task we test on, namely Node Classification and Link Prediction. Each row block corresponds to a pre-training task, with each row being one of the models. This implies that each entry in the table corresponds to the performance of model (row) when pre- pre-trained and adapted to a potentially different task (column), with both tasks from the same dataset. The diagonal for each dataset, which is colored in light blue, contains the performance of each model when pra-tedined and tested on the same task; in other words, it contains to the performance of the supervised version of each model in that dataset.
task (row block)
For each dataset, we consider the order-1 I task Node Classification and the order-2 task Link Pre- diction. As can be seen from Table 4, HoloGNN (GNN) and its variant HoloGNN (MP), which uses
32

---

Published as a conference paper at ICLR 2025
simple message passing propagations as fx instead than shallow GNN network, demonstrate sig- nificantly more consistent performance compared to other methods. While all other models exhibit significant performance loss when pre-trained Link Prediction and adapted to Node Classifi- cation, this is not the case for HoloGNN and HoloGNN (MP). For instance, in the CORA dataset, the difference in performance between HoloGNN (GNN) when pre-trained Node Classification (81.6%) and its performance when pre-trained on Link Prediction and adapted to Node Classiti- cation (80.2% 2%) results in a performance drop of around 1%. On the contrary, SAGE suffers from performance drop of 7%, while NBFNet and SEAL show more dramatic drop of 41%. Pre- training on Node Classification results less dramatic drops, especially for SAGE which obtains node representation (structural of order 1) both for node- and link-level tasks, which therefore tend to yield similar performances. Nonetheless, HoloGNN still demonstrate smaller performance drops, and overall better performances.
1.1 MOLHIV
We conduct an additional experiment to evalu- ate the performance of HoloGNN when adapted to different task order, namely the order-n task graph classification. Since there currently no standard dataset that includes both graph clas- sification and another type of task, we consid- ered the molhiv dataset from the OGB bench-
Table 5: Performance on molhiv on the graph classification task, when pre-trained in either graph classification or link prediction. HoloGNN demonstrates more consistent performance, with significantly smaller drops than GCN.
mark (Hu et al., 2020), which is designed for graph classification (an order-n task) and created link prediction task (an order-2 task) on the dataset. We evaluated the performance of both GCN and HoloGNN when pre-trained on link prediction and adapted to graph classi- fication and compare them to their performance when directly trained and evaluated on the graph classification task.
Graph Class. (ROC-AUC 1)
GCN (Pretrain on Graph Class) HoloGNN (GNN) (Pretrain Graph Class)
76. 08.00620.97
78. 19
GCN (Pretrain Link Pred)
70.29
HoloGNN (GNN) (Pretrain on Link Pred)
76.43=1.22
Results are reported in Table 5. The key observation is that the difference in performance between HoloGNN trained on graph classification (78.19%) vs pre-trained on link prediction and adapted to graph classification (76.43%) results in a performance drop of only 1.76%. while GCN suffers more pronounced drop 5. 77%. These results further showease the ability of HoloGNN to pre-train on one task order and adapt effectively to other task orders.
1. ABLATION STUDY ON THE NUMBER OF BREAKINGS
We additionally evaluate the impact of the number of breakings T. We con- sider the Cora dataset and report results of HoloGNN for different values of T on the node classification task, both when trained on it and when pre-trained on link prediction and adapted to node classifi- cation. Table 6 shows that small T val- ues are sufficient for obtaining represen- tations that can effectively adapt to dif- ferent tasks, and increasing T results marginal improvements. Indeed, regard- less of the value of T, the performance drop of HoloGNN when trained on node classification and when trained on link prediction and adapted to node classifica- tion is significantly smaller than the per- formance drop suffered by GCN.
Table 6: Impact of the number of breakings T in HoloGNN. Regardless of the value of T, the perfor- mance drop of HoloGNN when trained on node clas- sification and when trained on link prediction and adapted to node classification is significantly smaller than the performance drop suffered by GCN, with larger values of T yielding marginal improvements.
CORA Node Class. (Acc. f
GCN (Pretrain on Node Class) HoloGNN (GNN)
81.4+1.0
(Pretrain Node Class)
80.9
HoloGNN (GNN) T 8 (Pretrain on Node Class)
81.6++077
HoloGNN (GNN) 64 (Pretrain on Node Class)
82.1 10.01
GCN (Pretrain on Link Prod) HoloGNN (GNN)
71.2+0.2
(Pretrain on Link Predi
79.4+0.7
HoloGNN (GNN) T = 8 (Pretrain on Link Pred)
80.210.5
HoloGNN (GNN)
(Pretrain on Pred)
80.54..77
33

---

Published as a conference paper at ICLR 2025
Table Comparison with GPS (Rampásek al., 2022) on CORA in each of the two tasks (column), when pre-trained in either of the two tasks. HoloGNN demonstrates more consistent performance, with significantly smaller drops than GPS when pre-trained on link prediction and adapted to node classification.
CoRA
Node Class.
Link Pred. (AUROC t)
(Acc. t)
GCN (Pretrain on Node Class)
81.++1.0
89. 89.9+
GPS (Pretrain on Node Class)
78.3+1.0
98.0+0.1
HoloCiNN (GNN) (Pretrain on Node Class)
81.621..7
91.110.1
GCN (Pretruin Link Pred)
74.2+0.2
89.6+0.5
GPS (Pretrain on Link Pred)
36 2...8-22..
92.71:0.4
HoloGNN (GNN) (Pretrain on Link Pred)
80.210.5
93.910.1
E.1.5 COMPARISON WITH GPS GRAPH TRANSFORMER
We additionally compare the performance of the GPS graph transformer (Rampášek al., 2022) baseline with HoloGNN when adapted to a different task order than the one used for pre-training, using the CORA dataset.
Results are reported in Table 7, where each column represents different task (Node Classification or Link Prediction). For each task, we evaluate the performance of the models when trained directly on that task (shown in light blue) and when pre-trained on the other task and adapted to the target task. While GPS performs well when adapted to Link Prediction, suffers from a dramatic per- formance drop of 41.5% when pre-trained on Link Prediction and adapted to Node Classification, while HoloGNN results in a performance drop only around 1%.
E.2 EXPERIMENTAL DETAILS
We implemented HoloGNN using Pytorch (Paszke et al., 2019) and Pytorch Geometric (Fey & Lenssen, 2019), and performed hyperparameter tuning using the Weight and Biases frame- work (Biewald, 2020). We ran our experiments on NVIDIA A100 and GeForce RTX 4090 GPUs.
In all our experiments except the eigenvector task, implemented the parallel breaking algorithm. We use feature-marking technique to break nodes, adding an additional dimension to the embed- dings with value if that node is selected be broken, and 0 otherwise. Note that we break nodes one at a time, so there are T distinct forward passes, as described in the paraliel breaking algorithm (Algorithm 2). We use shallow structural model as fx. Specifically. for HoloGNN (MP). fa sim- ply performs A (V1 @ 1.). for l set to 2. Note that this variant does not have any extra parameters with respect to standard GNN. For HoloGNN (GNN). fx consists of a shallow GNN network, with 2 layers and hidden dimension equal to its input dimension. The GNN layer type depends on the dataset, as we will see next. In both cases, we set T for Planetoid and MovieLens datasets, and T = 10 for RelBench.
We further defined Φx to be elementwise multiplication and implemented A> to average over all steps t. This means do not concatenate the Ux Ux. for different À values; instead, we treat all UL.V as part of the same partition. This decision aims to reduce the dimension d, of R(E(A, Vi)) (Equation (11)) to match d, aligning it to the dimension of other methods.
For NBFNet, we included initial node features by concatenating them in the initial (boundary) con- dition. We denote the variant that does not include node features as NBFNet (no feat).
Notably, while standard GNN returns node embeddings, SEAL and NBFNet do not return node embeddings when pre-trained on tasks of order greater than 1. SEAL produces pre-trained embed- dings corresponding to the order of the task, which can scale up to (nn²) in our experiments when pre-trained on order-3 tasks. Similarly, NBFNet returns order-2 embeddings when pre-trained on tasks of that order and is unable to extend to higher-order tasks. In contrast, HoloGNN remains linear in the number of nodes and can handle tasks of any order, providing a scalable and flexible solution across task complexities.
34

---

Published as a conference paper at ICLR 2025
We train all models using the Adam optimizer, and report the test for the configuration achieving the best validation metric. Each experiment is repeated for different seeds. Details of hyperparameter grid for each dataset can be found in the following paragraphs.
MovieLens. For all models except NBFNet, we use a Bipartite- SAGE GNN Network (Hamilton et al., 2017) with hidden dimension 64 and 3 SAGE layers. For SAGE & LapPE we tuned the number of eigenvectors in {8. 16). We tuned the learning rate in {0.01, 0.001 J. For HoloGNN (MP) and HoloGNN (GNN), we use the Bipartite- SAGE GNN Network as Jarue (Equation (1)) and use node degree as the breaking rule to construct breaking selectors (Appendix A.I). We employed GCN layers in the GNN used as fx for HoloGNN (GNN) for all datasets except UserMovveeseer where we instead used SAGE layers. We generate train validation and test splits for each task by randomly splicting the edges with ratio of 80: 10:10:10, 10. We run our experiments for 1 epochs, and return the test at the epoch achieving the best validation results. For NBFNet and SEAL we run for 50 epochs, due to the significant and intractable increase in running time, We remark that the number of epochs for these models is similar to the number of epochs used in the corresponding original papers on their datasets. Notably, on Userr and MsieMovieMovie, preprocessing for SEAL construct the subgraphs exceeds the RAM capacity of our A 100 GPUs (528 GB), resulting in out-of-memory (OOM) errors reported in the table. Finally, since NBFNet is not designed for triplet predictions, we report NA in the corresponding entries for UserMovieUser and MoveMovieMovie.
Planetoid. For all models except NBFNet, we use GNN Network with hidden dimension 64 and 2 GCN layers (Kipf & Welling, 2017). For GCN & LapPE we tuned the number of eigenvectors in {8, 16}. For the node-level tasks, we employ the widely used choices, including the final classifier being a linear layer, dropout of 0.5 and weight decay of 5e 4. For HoloGNN (MP) and HoloGNN (GNN), we use the GCN network as farme (Equation (1)), node degree as the breaking rule to con- struct breaking selectors (Appendix A. and we further employed GCN layers the GNN used as fx for HoloGNN (GNN). For node classification, while for link prediction, following Zhu et al. (2021), we generate train validation and test splits by randomly splitting the edges with a ratio of 85:5:10. We our experiments for 500 epochs, and return the test at the epoch achieving the best validation results. Due to the significant increase in running times, for NBFNet we run for 100 epochs for the node-level tasks, and for 20 epochs for the link-level tasks, while for SEAL we run for 500 and 50, respectively.
employ the standard splits (Yang et al., 2016),
RelBench. The rel-stack graph is a large and realistic graph containing over 38M nodes. Because of this, our models use subgraph-based sampling as proposed by Hamilton et al. (2017). This means that the symmetry breaking approaches based on global structural properties, such as choosing nodes of highest-degree, are not possible in this case. Instead, we use mini-batch based breaking method, which takes the embeddings of each node given by the initial structural model Istree and passes them through a learnable linear layer to produce a single scalar logic for each node. These are then passed as input to a Gumbel-SSffmax computation block as described in Appendix 1. which selects T* = 10 < 38M distinct nodes to be used as breaking nodes in a fully differentiable way. We adapt the GNN training code from the RelBench repository found at wttp://wwwooooosassssssotooooeee
We adopt many default hyperparameters from the repos- itory, including 10 epochs training for node-level tasks, and 20 for link prediction, 2 GNN message passing layers for fi with sum aggregation, and Adam optimizer with learning rate 0,005 for node- level and 0.001 for link-level tasks. The exception is that we shrunk the network so as fit 24G GPU. Namely we used batch size 128, hidden dimension 64, and sampled 64 neighbors per node.
Eigenvector Task. We use the GCN model implemented in Lim et al. (2023), denoted by GCN (constant input) Table 2, as Jaru (Equation (1)). Rather than training Jane together with our expansion map and the classifier, we utilize the pre-trained Jamu to obtain V, Then, we use Vi to derive the eigenvectors as per Algorithm 1, thereby only training the final classifier. We obtained the eigenvectors using the Subspace Iteration (Saad, 201 generalization of the power iteration method for computing several dominant eigenvectors simultaneously. using node degrees to obtain breaking selectors (Appendix A.1). Given the cigenvectors matrix U R we obtain the final prediction as MLP(U,,, @ U,.)). with @ denoting element-wiss product. We set l to be the same as the number of eigenvectors used by the other methods, namely 16.
35

---

Published as a conference paper at ICLR 2025
Molhiv. We consider GNN Network with hidden dimension 64 and 2 GCN layers (Kipf & Welling, 2017) as the baseline. For HoloGNN, We use the identity as 9sme (Equation (I)), and choose T breakings for each graph in the dataset. We further employ 2 GCN layers with hidden dimension 64 in the GNN used as fx- For both models, we tuned the learning rate in {0.01, 0.001 ). For graph classification, employ the standard splits (Hu al., 2020), while for link prediction, we generate train validation and test splits by randomly splitting the edges with a ratio of 85:5:10.
36


Reviews:
[{"review_id": "AtVrjk1HEI", "reviewer": "Reviewer_BWdZ", "summary": "The paper proposes holographic node representations that are capable of solving tasks of any order (node: 1st order and edge: 2nd order, etc). The proposed holographic node representations consist of two components: (1) a task-agnostic expansion map, which produces highly expressive, high-dimensional embeddings, and (2) a reduction map, which introduces the relevant permutation symmetries. The experimental results show that the holographic node representations show the best performance across tasks of varying order.", "questions": "Please refer to the weaknesses section.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed paper is well-written.\n- The research question of the paper is really interesting.\n- The proposed approach is novel and interesting.", "weaknesses": "- It would be better if the paper included experimental results on graph classification. This paper shows the effectiveness of the holistic node representations using node classification, link prediction, and meta-path prediction (UserMovieUser). But I wonder if the proposed representations perform well on graph classification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "n6WVTKSoMk", "reviewer": "Reviewer_3vdB", "summary": "The paper aims to learn node embeddings capable of solving multiple graph learning tasks. It first presents the challenge of existing node embedding models in solving multiple tasks. To address this challenge, the paper proposes a holographic node representation model named HoloGNN. HoloGNN consists of two components: an expansion map that produces descriptive symmetry-free representations, and a reduction map that introduces task-specific symmetries to obtain embeddings tailored for a specific task. Experimental results on four graph datasets show that compared with baselines, the HoloGNN is more effective in adapting GNN pre-trained on one task to other tasks.", "questions": "Please see the questions in the Weaknesses section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The idea of generating holographic node embeddings to address multiple graph learning tasks seems novel and interesting. The paper provides theoretical analyses to justify the validity of the proposed method. Experimental results show that the proposed HoloGNN can effectively adapt GNN trained on one task to other tasks.", "weaknesses": "1. There is no justification for Property (1) and Property (2). \n\n2. Section 4.1 is difficult to follow as it lacks sufficient details on the node-breaking selectors. More elaborations about node-breaking selectors and why these selectos are needed in the expansion map should be provided to enhance clarity. \n\n3. The proposed HoloGNN is quite complicated since it requires breaking symmetries using either sequential breaking or parallel breaking algorithms. Complexity analyses should be provided to understand the additional computational cost introduced by these algorithms and to clarify whether the parallel breaking algorithm can effectively reduce the cost. \n\n4. The paper lacks discussions and comparisons with the graph transformer models. What are the advantages of the proposed HoloGNN model compared with graph transformer models?\n\n5. I have some major concerns regarding the experiments: \n\n(1) The HoloGNN is designed to be pre-trained and then adapted to any graph learning tasks (line 46-47). However, in the experiments, the paper only shows the results of HoloGNN when it is pre-trained on a single task (e.g., node classification) within a single dataset and then adapted to another task (e.g., link prediction) on the same dataset. This evaluation is insufficient to validate the generalisation of HoloGNN across different datasets and tasks. A potential solution is to pre-train HoloGNN on one task across all the datasets and then evaluate its performance across different datasets and tasks, including the pre-training task.  \n\n(2) The results in Figure 3 show that the performance of pre-trained HoloGNN is worse than that of HoloGNN trained from scratch. Is pre-training still necessary in these scenarios?\n\n(3) The results and analyses on the MovieLens dataset are difficult to understand. More explanations should be provided to enhance the clarity. \n\n(4) The paper lacks analyses of the impacts of some hyperparameters in the HoloGNN model, such as $T$ and $L$ in equation (2).\n\n6. The paper mainly focuses on the node classification and link prediction tasks. I would if the proposed HoloGNN model can be applied to the graph classification task and how it might perform in that task. \n\n7. The code is not available, which makes it difficult to reproduce the results given the proposed model is rather complicated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "lT8AZ4uJMQ", "reviewer": "Reviewer_Nt1U", "summary": "The paper propose a new approach that allows node embeddings to be trained on any task (e.g. link prediction) and then easily adapted to other tasks (e.g. node classifcation).", "questions": "1. Does the authors regard the HoloGNN as a pretraining approach? If so, it would be better if they could provide comparison analysis against other pretraining methods, e.g. [1][2]. However, from my point view, the paper is more about 'transfer learning' which learns from one downstream task and adapt to another. From this perspective, a thorough refinement of the paper is necessary.\n\n[1] Hu, Weihua, et al. \"Strategies for pre-training graph neural networks.\" _arXiv preprint arXiv:1905.12265_ (2019).\n[2] Hu, Ziniu, et al. \"Gpt-gnn: Generative pre-training of graph neural networks.\" Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 2020.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper proposed an interesting approach by learning a 'holographic' node representation that contains multiple view of representations and utilized a reduce map to produce a specific embedding for specific task.\n2. The authors provide thorough and interesting analysis for holoGNN from the perspective of canonical eigenvectors.", "weaknesses": "1. My major concern is about the 'pretraining' term used in the work, as it is biased from the widely accepted perspective. For the community, pretraining usually refers to an unsupervised task, e.g. language modeling or predicting next token in language models (LM); or graph reconstruction tasks in [1]. However, the proposed method and experiment setting in this paper is more like 'traditional transfer learning' which learn representations from one downstream task (task labels are necessary, e.g. node classification) and adapt them to another task (e.g. link prediction). From the perspecctive of pretraining, the experiment setting is not suitable since it solely evals one downstream task. As a result, I would like to advise the author revise the term to make this part consistent.\n\n[1] Hu, Weihua, et al. \"Strategies for pre-training graph neural networks.\" _arXiv preprint arXiv:1905.12265_ (2019).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "L1fx2T0hgc", "reviewer": "Reviewer_uQxW", "summary": "This work investigates the ability of node embeddings to solve various graph tasks. From the preliminary results that no existing node embeddings could solve all the tasks, it proposes holographic node representations to learn symmetry-free embeddings and reintroduce the task-specific symmetries back to the model. Both theoretical analysis and empirical results are provided.", "questions": "1. Line 43: It needs more explanation about \"different permutation symmetries with respect to different task orders\"? Same question for the first paragraph of the second section.\n2. Why do the links in Figure 1 not preserve isomorphism?\n3. It's kinda hard for me to understand lines 137-141. If the extra task-specific embeddings don't negatively affect the performance of another task, then what's the difference between the proposal and naively concatenating all task-specific embeddings?\n4. Can you briefly explain/show what the 'single node permutation' is?\n5. The isomorphism in this paper refers to the one defined by first-order neighbor?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper is generally well structured and easy to follow.\n2. In addition to extensive empirical verification, most of the designs adopted in the proposal are also theoretically justified.\n3. The findings that the source of task-specific embeddings is symmetry are distinctive across different tasks is really interesting.", "weaknesses": "1. As the very first definition of the paper, Structural Representation is not very clear. For example, in line 107, 'order r' is confusing, since it was previously defined as the cardinality of a node subset S. And the explanations for the subscript S, $\\pi \\circ$, and permutation matrices are missing from the definitional formulation. Also, how do I understand the output format of the function f, which is not clear to me? Do the last r rows of the output matrix repeat some r rows of the previous n rows?\n2. The same question appears in the formulation of the reduction map: where is the input of r for the corresponding output matrix in equation (3)? Before presenting the idea of task-agnostic node embeddings, it seems to me that a more general question should be asked: what kind of task-agnostic information can we store in node embeddings? This is because the analogy between pre-training for word embeddings and node embeddings is not perfectly aligned across different graphs. If the scenario we're focusing on in this paper is the nodes from the same graph, then it's necessary to make this point very clear.\n3. It is confusing to me that in the real world, most of the graphs come with node-level distinctive features, which is fed in $V_1$, for this purpose, how significant is the necessity of breaking symmetry technique to distinguish structurally isomorphic nodes?\n4. There is one point that seems counter-intuitive to me: if the downstream tasks are always embodied with certain structural symmetries, since after all they are performed in the graph domain, then whether it is a bit detour to dismiss all symmetries in the expansion map step? Why not preserve all symmetries in the first place, but fuse them without bias, and then follow the same idea of the current design of the reduction map?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)