Bridging Theory and Practice in Link Representation with Graph Neural Networks
Authors: Veronica Lachi
Francesco Ferrini
Antonio Longa
Bruno Lepri
Andrea Passerini
Manfred Jaeger
Venue: NeurIPS 2025 spotlight ()
Keywords: Graph Neural Networks
Link Representation
Expressiveness
Primary area: deep_learning

Abstract: Graph Neural Networks (GNNs) are widely used to compute representations of node pairs for downstream tasks such as link prediction. Yet, theoretical understanding of their expressive power has focused almost entirely on graph-level representations. In this work, we shift the focus to links and provide the first comprehensive study of GNN expressiveness in link representation. We introduce a unifying framework, the $k_\phi$-$k_\rho$-$m$ framework, that subsumes existing message-passing link models and enables formal expressiveness comparisons. Using this framework, we derive a hierarchy of state-of-the-art methods and offer theoretical tools to analyze future architectures. To complement our analysis, we propose a synthetic evaluation protocol comprising the first benchmark specifically designed to assess link-level expressiveness. Finally, we ask: does expressiveness matter in practice? We use a graph symmetry metric that quantifies the difficulty of distinguishing links and show that while expressive models may underperform on standard benchmarks, they significantly outperform simpler ones as symmetry increases, highlighting the need for dataset-aware model selection.

Bridging Theory and Practice in Link Representation with Graph Neural Networks
Veronica Lachi"
Francesco Ferrini' University of Trento Trento, Italy Francesco.fervee @unitn. ferriniuuiiinn.ii
Antonio Longa University of Trento Trento, Italy
Fondazione Bruno Kessler Trento, Italy vlachi@fbk.er eu
antonio. loriiiooonnauunitn.co
Bruno Lepri
Andrea Passerini
Manfred Jaeger University of Aalborg Aalborg, Denmark jaegerêcs aau. dk
Fondazione Bruno Kessler
University of Trento
Trento, Italy lepri@fbk.eu
Trento, Italy
andrea. aadrea.passerinieumii it
Abstract
Graph Neural Networks (GNNs) are widely used to compute representations node pairs for downstream tasks such as link prediction. Yet, theoretical under- standing of their expressive power has focused almost entirely on graph-level representations. In this work, shift the focus links and provide the first comprehensive study of GNN expressiveness in link representation. We introduce unifying framework, the k framework, that subsumes existing message- passing link models and enables formal expressiveness comparisons. Using this framework, derive hierarchy of state-of-the-nn methods and offer theoretical tools to analyze future architectures. To complement our analysis, we propose a synthetic evaluation protocol comprising the first benchmark specifically designed to assess link-level expressiveness. Finally, we ask: does expressiveness matter in practice? We use graph symmetry metric that quantifies the difficulty distinguishing links and show that while expressive models may underperform on standard benchmarks, they significantly outperform simpler ones as symmetry increases, highlighting the need for dataset-aware model selection.
Introduction
Graph Neural Networks (GNNs) have achieved remarkable success across wide range of tasks involving structured data, including node-level 119 [51 36, (28), graph-level [18] (2). and link-level
tasks [44] [58] [56] [13. Despite the growing importance of link representation learning, the theoretical
analysis of GNNs has so far focused almost exclusively on their expressiveness for graph-level
representation [53 37 6. particular, it is well-established that message-passinggg GNNs are most as powerful as the I-dimensional Weisfeiler-Lehmar (1-WL) test in distinguishing non -somoohoo graphs [53 37.. However, their ability distinguish links that is, to generate discriminative representations of node pairs remains far less understood.
It is well known that standard GNNs struggle distinguish structurally different links, they typically compute link embeddings by aggregating the representations of the two endpoint nodes. This node-centric strategy introduces significant expressiveness bottleneck: links whose endpoints are automorphic may be mapped to identical representations, even if their structural roles in the To mitigate this issue, several methods have extended GNNs with structural
graph differ 44 58 13].
Equal contribution
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

features (SFs) 558 56 13]. While such approaches are more expressive than standard GNNs, there is still no unifying framework to systematically characterize their discriminative power or organize them into a principled expressiveness hierarchy-uniee the case of graph-level representation, where the k- H-Weisfeiler--ehmaa hierarchy provides a widely adopted standard 37 531.
In this work, we bridge this gap by conducting a comprehensive investigation into the expressive power of GNN-based models for link representation. We observe that most existing methods for link representation combine two ingredients: a message-passingg GNN for node encoding and a pairwise function for aggregating information about the target link. Building on this insight, we propose a general theoretical framework that captures a broad class of link representation methods. The framework characterizes models based on two key dimensions: the expressiveness of the functions involved and the radius of the neighborhood around the link that they access. It subsumes many stateoof-the-art models and allows us to formally reason about their ability to distinguish links.
We explore link-level expressiveness along three axes. First, grounded in the proposed framework, we develop theoretical foundation to analyze and compare the expressiveness of link representation models. Specifically, we derive criteria to assess a model's capacity to discriminate between different link structures, enabling us organize existing methods into an expressiveness hierarchy and to position novel models within it. Second, we introduce a synthetic evaluation protocol designed to probe the expressiveness of link representation methods. This protocol comprises both a synthetic dataset and an accompanying evaluation procedure. While previous work has introduced synthetic tools for assessing graph-level expressiveness 7 48 40 3 & the best of our knowledge, no analogous setup exists for links. Our procedure enables systematic, reproducible, and scalable comparisons across models. Third, we investigate the practical relevance of expressiveness on link representation by studying whether more expressive models lead to better performance in real-world scenarios. We propose a graph symmetry metric to quantify structural ambiguity among links, and we empirically show that while simple models suffice in low-symmetry settings, more expressive models significantly outperform them as symmetry increases.
2 Preliminaries
Definition 2.1 (graph). A graph is a tuple G (Vc, Eg) where VG = {l,..., n) is set of nodes, EG C Va x Va is set of edges. To each graph is associated node features matrix X Raxf and an adjacency matrix Ag E {0, 1 with Ac... = if and only if (u, v) E Eg. In our analysis, we consider simple, finite and undirected graphs. We will call g the set of all graphs.
Definition 2.2 (neighborhood)) Let G (Vg. be graph. Given two nodes u, U E Va. u is said to be m-far from u if there exists a path of m edges connecting u and u. Given a node w E VG. we denote by N²m(w) the set of nodes m-far away from v. In particular, the 1-hop neighborhood of u, denoted N(e), corresponds to N' and includes all nodes connected to ie.. Nvv) = {u E VG | (v, u) E Ea). Finally, given two nodes u, v E Ve, their joint m-hop neighborhood is defined as (""(uvv) = N U UN)()).
Definition 2.3 (link representation model). A link representation model M is class of functions F mapping node pairs in graphs to vector representations:
F: ((u, v), G, x*) + ((u,o) E Rdd
with G e G. X e Raxf node feature matrix and u, U E VG-
In this work, we adopt a broad notion of link, referring to any pair of nodes (u,v) v) E VG x VG. regard- less of whether an edge between them actually exists in G. i.e., whether (u,v) E Fg. Accordingly, the link representation model computes vector representation for arbitrary node pairs, not only for existing edges. Throughout the paper, the term link will always refer to a generic node pair.
Models that compute link representations can be applied to a variety of downstream tasks. For instance, they can be used for link prediction [57 an edge between two nodes, for link classification 43 47 [5], where different types of relationships
35]
60). where the goal is to predict the existence of
are inferred and for link regression 33 where real-valued properties associated with node pairs
are estimated. In this work, we focus on message-passing (MP) link representation models, which have demonstrated superior performance and robustness across wide range of benchmarks (32).

---

Definition 2.4 (GNN), Let G = (Va, Ec) be a graph with feature matrix X". A GNN iteratively
updates the representation of nodes Va following the propagation scheme:
X
UPDATE (x-=1 AGGREGATE ((x I N()))))
(2)
We denote the final representation at the I-th layer as x p(u, G, X.).
In the rest of this paper, whenever we refer to MP models, we refer to models that employ the iterative mechanism defined Definition 2.4 to compute node representations.
A key theoretical question concerns GNNs expressive power, their ability to distinguish non- isomorphic inputs. Standard GNNs have been shown to be most as powerful the 1-WL test [37 [4 a heuristic for graph isomorphism based on iterative multiset aggregation [50]. To go beyond this limit, higher-order GNNs [37] aggregate over k-tuples of nodes, reaching the ex- pressivity of the k-WL test: we denote by kp the smallest such A such that is as powerful as k-WI,, kip expresses the representational power of p within the k- L-. paradigm.
contrast to graph-level tasks, the expressiveness of passage-passingg models for link representation remains less explored 58 44 (24] We now provide formal definitions on what does it mean for two links to be
different in graph.
{I,.... n2 is a bijective function that assigns a new index to each node of the graph. All the possible node permutations constitute the permutation group II, Given subset of nodes S S VG. we define the permutation и on as क (S) == (i)i E 5). Additionally, we define π (Ac) as the matrix Ag with rows and columns permutated based πτ, i..., I (A)))(() (Ac)..j-
Definition 2.5 (node permutation). A node permutation
{I...., n) :(1,.....
Definition 2.6 (automorphism). An automorphism on the graph G = (Va, Fa) is a permutation E II, such that o (Ag) Ag. All the possible automorphisms on graph G constitute the automorphism group -n
Definition 2.7 (automorphic links). Let G = (Va, EG) be a graph and M its automorphism group. Two pairs of nodes (u, v), (u', v'), VG Ve are said to be automorphic links (u, v) ~ (u', exists a E D such that af v)) = {u', v'}.
The notion of automorphic links provides the foundation for evaluating models expressivity, as an expressive model should be able to distinguish between non automorphic links.
Definition 2.8 (more expressive). Let Mi and M2 be two link representation models (Def. 2.3 M2 more expressive than M1 (M1 S M2) if, for any graph = (Va, Ea) and any pair v), (u', o() E Va x Va with (u, v) & (w',v'):
3F E M1 Fi((u, v), G, X*) + Pi(l U), X*) = 3Pg E M2 Fa((u, G,,
3 The Expressive Power of MP-based Link Representation Methods
We propose a general framework for message- messagg-passing models that compute link representations, encompassing broad class of existing methods specific instances. By formalizing these models under unified perspective, we enable a principled analysis of their expressive power. Leveraging this framework, further establish expressiveness- hierarchy of existing approaches.
3.1 MP-based methods for link representation
Before defining the framework, we first review representative MP-based models, including Pure GNNs 30
29
45
22
53 NCN [46, NCNC [66,, ELPH [3] BUDDY [13, Neo-GNN [56] and
SEAL
58
Pure GNN Methods. Pure GNN Methods learn representation X(a,)) E RRd for each pair of node (u, v) with u, e E VG as ((a,e) = g(xt, x5)), where is an aggregation function and x x are the node representation of u and v learned by the GNN at the final layer L. In principle, any type of GNN can be used, and the function g can be modeled using an MI.P over any aggregation function over the feature vectors. In practice, the most commonly used pure GNN model is GAE (29]
3

---

Neo-GNN.
Given a graph G = (Va. Eg), Neo-GNN computes node representation matrix Z as:
Z =
struct
with X diag(x"iml)) X, x. Fe((AG)))
1=1
where Fe is a learnable function over the adjacency matrix Ag. L is the maximum hop considered, and B E (0, 1) controls the weight of distant neighbors. The final link representation is computed as an aggregation of the node representation obtained through standard GNN and the one in Z, namely x(u,v) ((z,; Ze), (x ))
NCN. NCN computes the representation of node pairs using the representations of their common neighbors. NCN defines the link representation as:
((u,)) = X
Σ
X
(EN(u)nN(()
where x is the node representation at the final L-th layer of GNN. NCNC extends NCN to deal with settings with incomplete topological information (e.g.. for link prediction graph completion), by considering not only nodes N N(u) n (u) but all nodes N(u) U (()) and calculating for them the probability of being common neighbors with NCN.
Given graph G = (Va, EG), for each link (u, v), SEAL constructs an h--op enclosing subgraph G(h), which contains all nodes within h hops of and v. Nodes in (((h) are labeled using the Rouble-Radius Node Labeling (DRNL)(58), which assigns different labels based on distances to and V. The representation of link (u, v) is obtained processing the graph ((hh) with a GNN.
SEAL.
ELPH. In ELPH, two types of count-based features are computed: (i) Age [dy, del, i.e. the number of nodes at distance du from node and d, from node and (ii) Bu [d]. the number of nodes at distance d from and more distant than d from u. These counts are estimated using MinHash (for Jaccard similarity) and Hyperl.ogl.og (for set cardinality). The link representation is obtained as:
((,,)) 9(x x {Auv [du, du), Bu [d] d, dy, d, < [L]))
(5)
where g an aggregation function and the final layer. To overcome ELPH's memory limitations, BUDDY precomputes structural features via offline graph traversals and sketching.
3.2 A General Framework for MP-based Link Representation Methods
Building on the definitions introduced in Section 3.1 we observe that MP-based approaches for link representation generally follow a common paradigm: they combine the representations of the two endpoint nodes with additional pairwise information extracted from their local neighborhoods, except for pure GNN methods, which rely solely on node representations. Although specific mechanisms and architectural designs vary, the core structure of these models can be systematically characterized by two key factors: (i) the link neighborhood radius, which defines the portion of the graph considered when extracting pairwise information for the link, and (ii) the expressiveness of the saasaage-asssingg (MP) functions used to compute the node representations. Importantly, the link neighborhood radius
Table 1: Model formulations from Section 3.1 expressed within the - framework. A " indicates that the corresponding component is not included in the model.
Model
COMB
Ao
AGG
202
GNN
@
1-WL
NCN
0 1-WT.
Σ
a G X
1-WT.
X
ELPH
1-WL
Σ
II II 1a
1-WL
x! m
Neo GNN
1-WL
Σ
b=p(Ex
with
1-WL
x
b= E
Al. Al.
SEAL
t
Σ
1-I.""(u. WL m xP x minffii, u). e)) +1

---

is distinct from the radius induced by the depth of the MP function itself. Motivated by these common factors, we introduce a general framework that unifies existing approaches under common formalism. In this framework, the link representation is constructed by combining: (1) the representations of the two endpoint nodes, and (2) representation of the link's m-order neighborhood, each computed via MP functions that may have different levels of expressive power and different number of layers.
We formalize this the following definition, which we refer as the kg-kip- framework for link representation. For ease of readability, we omit the graph G E G as an explicit argument in message-passingg passing and link- representation functions, assuming it is implicitly defined as the underlying structure on which these functions operate.
Definition 3.1 (kg-kp -- framework) ) Given graph G = (Vg. Eç) with feature matrix X a MP link representation model M belongs to the ka-kp-m framework if its functions can be expressed as:
F((u,v) x²) = COMB (g(Ó(u, d0) x²)) AGG((/(( x²) lie U N (u, w)))) ==
(6)
f(i, (u.u,u, u. x =
(5 h(,, v, x²) u,
(7)
where @ and are MP functions (Definition 2.4 with expressive power respectively of Kg and kp- h(u, v, (.) [gudd is new node feature matrix computed using the original feature matrix and possibly pairwise information, & scales the message passing representations by coefficient incorpo- rating pairwise information from the graph, AGG is aggregation function over the representations of nodes in Un_ No (u, v) and COMB combine the endpoints representations with the neighborhood representation.
Table provides the formulation of all the models presented in Section 3.1 using the ka-kp-m framework, while Figure T provides a visualization of the framework components. Through the ka- kp-m framework, methods. Let M be the set of link representation models expressible by the kg-ko-m framework. Let M E M, we indicate with k-S -M - the specific value that ka-kp-m assume in the model M.
systematically study the expressive power of MP-based link representation
Theorem 3.2. Let M E M, the following hold:
1. If m = 0, then, regardless of WM, M is not able to distinguish between links whose endpoints are automorphic, iee,
vF E M, M,V(U, u), (ul, s.t. 30,, E E with (u) = u' Aoz(v)= (8) F(uu, v'), x'), F F((,,)),X)
therefore, automorphic links whose endpoints are automorphic will be assigned to the same representation. Moreover, given M1, M2 M, if while m. >> O and COMB injective, regardless of R. and R.Ms MM S M2.
2. Let MI, M2 M with k-d,, -kdds 1-WL and let 1st, jalz be the number of layers used respectively by M1, M2. If 1,4 S m + 12,, then M1 S M2.
3. Let MI, M2 M with md = Mo, If hs S KM then Mj S M2.
P D.0. h ( p 100000,100000 (
B.GG
G:
COMB 9
V
Figure 1: kg-kp-m framework: nodes representations in the m-order neighborhood of target link are calculated using MP function P with possibly modified node features; these representations are aggregated and combined with representations of endpoints of target link obtained through MP function ó.
5

---

Proof is provided in Appendix [ Intuitively, the theorem highlights that relying solely on the representations of the endpoints through g and & is fundamentally limited: even if Φ is highly expressive, such models fail to distinguish links whose endpoints are automorphic. This limitation arises from the fact that the k-WL. algorithm, preserves graph automorphisms for every k [34 T6 [1]. Instead, more efficient and expressive modeling strategy is to compute over a suitable m-order neighborhood using an appropriate number MP layers. In many models, the number of such layers is design choice: for instance, ELPH encodes link information by counting nodes at various distances from the link, which effectively corresponds to zero message-passingg layers. Conversely, in computed through function on the adjacency matrix, effectively implementing a single round of message passing. This distinction is crucial: even models with large neighborhoods but few message-passinggg passing layers can be outperformed bottootddd-ohhhhhhooooooooooo in expressiveness and efficiency-by models with smaller m but deeper architectures. Thus, controlling expressiveness via the number of layers offers a more principled and computationally efficient path. Finally, increasing the expressiveness of the base model p on the m-order neighborhood leads to more expressive representations. One example of model with more expressive p SEAL which increases expressiveness by adding link-aware positional encodings to node features, effectively simulating the power of 1-|N" (u, o)) which is strictly more expressive than I-WL (59). However, increasing expressivity beyond 1-WL comes at a computational cost: for example, the complexity of k-WL is On log n) 25 Details on the computational costs of the models are provided in Appendix D
Neo-GNN, node representations
Using Theorem 3.2 it is possible to study the expressiveness of existing methods. The following
Theorem introduces hicrarchy of existing methods.
Theorem 3.3. The following hold:
1. For any radius and number of layers, NCN, Neo-GNN, ELPH, SEAL more expressive than Pure GNNs;
2. if IfINCN 2 m -Ne--NNN NCN is more expressive then Neo-GNN;
3. NNNNNNNNN 2 m ELPH 1, Neo-GNN is more expressive than ELPH;
4. iINNN 2 m ELPH NCN is more expressive then ELPH;
5. SEAL is more expressive then NCNC, NCN, ELPH. Neo-GNN.
Proof is provided in Appendix A and rely on Theorem 3.2 and the formal expression of models within the theoretical framework described in Table
The ka-ko-m framework serves a foundation for analyzing the expressiveness link representation models a principled and structured way. In the next section, we complement this theoretical perspec- tive by introducing synthetic evaluation protocol designed to empirically assess the expressiveness of link representation models.
4 A Synthetic Evaluation Procedure for Link Representation Expressiveness
We introduce a synthetic protocol to empirically assess a MP model's ability to assign distinct representations to structurally different links. The protocol is designed to help evaluate new link representation models in simple and controlled setting. It consists of synthetic dataset and an evaluation framework. The synthetic dataset and the code are publicly available
4.1 LR-EXP: A Synthetic Benchmark for Link-Level Expressiveness
While several synthetic datasets have been proposed to evaluate the expressive power of GNNs in distinguishing non-isomorphic graphs 7 48 40 8) comparable benchmark for as- sessing link-level expressiveness is still missing, despite its potential utility as a fast and con- trolled way to empirically assess the expressivity of both existing and new models. To address this gap, we propose a novel synthetic dataset, LR-EXP, aimed at measuring a model's ability to assign different outputs to non-automorphic links. To make the distinction task challenging, the dataset includes non-automorphic links whose endpoint nodes share the same 1-WL colors.
gnn- 2124/README..o md

---

This is critical design choice: differently colored nodes are trivially distinguishable by any pure GNN with an injective aggregation function g. LR-EXP includes I 1400 graphs, each containing at least one such pair of non-automorphic links. Each graph is generated in two steps: (1) sample an Rénós-RRénii graph with n E .5,..., 17) nodes and edge probability U(0, 1); (2) duplicate the graph and add inter-block edges with probability p' ~ 1). This construc- tion introduces rich symmetries and increases the probability of obtaining node pairs that are non-automorphic yet indistinguish- able under the WL test. We retain only those graphs where such link pairs exist, and use them to define training, validation, and test sets. Figure 2 shows examples of these link pairs. Impor- tantly, while EXP relatively small in scale, this is by design: goal is not to evaluate scalability, but to isolate and probe expressivity. Since expressiveness concerns a model's ability to produce different outputs for structurally distinct inputs, rather than generalization over large data volumes, dataset size is not a confounding factor for the phenomenon we aim to study.
non-automorphic links with
graph #50
graph
#430
groph #500
Figure 2: Examples of LR-EXP graphs. Node colors show WL col- ors: dashed lines mark test links that are non-automorppic but indis- tinguishable for standard GNNs.
4.2 Evaluation Framework
Our training and evaluation approach is inspired by the method proposed in Wang and Zhang [49] In particular, employ siamese network design (9), with central component consisting of two identical models with identical parameters, each processing one link independently to generate separate embeddings. For a pair of links (u, & (u', v') E VG x Va, and model F, the model generates a corresponding pair of embeddings. The model is trained with the goal of encouraging separation of links embeddings using the contrastive loss:
L(F, (u, u). (ul, v'), v'), x = max (o, F((u, (II (
F(lU) x*) X*) v²), )9))
(10)
Contrastive loss functions are often defined with an explicit margin term which controls the degree of dissimilarity enforced between negative pairs. In our case, the goal is to fully minimize similarity between representations of non-automorphic links. Following the approach in (48), we deliberately adopted a zero-margin formulation to push the model toward maximal dissimilarity between such pairs. This choice aligns with our objective of measuring and testing expressiveness, where even small overlaps in representation between structurally different links would be undesirable.
To evaluate models, we compare their outputs pairs of non-uutomo links. If the resulting representations differ sufficiently, this indicates successful discrimination. However, selecting an appropriate threshold is challenging: high threshold may cause false negatives, where true distinc- tions fall below the threshold; a low threshold may cause false positives, where random noise creates apparent differences. To address this, we adopt the Reliable Paired Comparison method [49), which assesses groups of results using two components: the Major Procedure, quantifying representation differences, and the Reliability Check, measuring internal variability. A pair is considered distin- guishable only if both checks are passed. As all pairs are non-automorphie, the task framed as one-class classification, and we report precision as the fraction of correctly distinguished pairs. See Appendix B.1 for details.
4.3
Experimental results on LR-EXP
We evaluated the expressive power of all models from Section 3.1 on LX-EXP. As discussed in Section 3.2 some models treat m as fixed design choice while keeping the number of layers I as tunable parameter, and vice versa. Even in models where m is left as a free parameter, practical implementations impose constraints due to computational costs. For example, both ELPH and SEAL limit to maximum of 3. In our experiments, we adopt m 3 for all models that allow it, ensuring a fair comparison. We set the number of layers 1 = 3 across all methods, which strikes a balance between expressiveness and avoiding oversmoothing effects [10]. Under this configuration, Theorem

---

shows that NCN is more expressive than ELPH and matches the expressiveness of Neo-GNN while SEAL is the most expressive method.
3.3
The experimental results on LR-EXP provide empirical valida- tion of our theoretical framework. Table shows that Pure GNN methods (GCN, GAT, GAE. SAGE) completely fail to distinguish non-automorphic links, achieving zero precision. This is a consequence of their fundamental limitation the au- tomorphic node problem we analyzed in Section 3.2 which prevents them from generating distinct representations for links composed by automorphic nodes. The remaining methods demonstrate progressively better performance as their expres- sive power increases. The performance gap between BUDDY (45%) and ELPPH (62%) stems from BUDDY's approximate counting of common neighbors (Section 3.1 which reduces its expressiveness shown in [3. Neo-GNN and NCN ICNNeachieve achieve comparable precision (75%), outperforming both ELPH (62%) and BUDDY (45%). Finally, SEAL demonstrates its high ex- pressiveness, being able to correctly distinguish 97% of links. Further results as we vary the number of layers and the radius m are in Appendix. Appendix reports robustness checks under variations of the significance level employed in the Reliable Paired Comparison.
Table 2:
Test precision (mean + std over 5 runs) for different models. Higher model expressiveness leads to higher test precision.
Model
Test Precision (%)
GCN
0 (= 0)
GAT
(=
GAE
0 (=
SAGE
0 (=
BUDDY
45 (1
ELPH
62 (1
Neo- GN-
75 (1 2)
NCN
75 (1 1)
SEAL
97 (2
5 Do More Expressive Models Perform Better in Real-World Benchmarks?
An interesting and practically relevant question is whether increased expressivity in link representation translates into better performance downstream tasks involving real-world data [27 38 Among the various tasks enabled by expressive link representations, we focus on link prediction due to its broad impact across domains such as recommender systems (55), knowledge graph completion [4], and biological interaction prediction [26]. Intuitively, link prediction should particularly benefit from models with high expressive power when the dataset contains many non-automorphic links whose endpoint nodes are automorphic, a setting where Pure GNNs struggle. this section, we aim to answer the following three questions: (1) How can we formally quantify the presence of non- automorphic links with automorphic endpoints a dataset? (2) Are there real-world link prediction benchmarks where this property is especially prevalent? (3) How do models with varying levels of expressiveness perform across datasets with different levels of structural difficulty?
We address these questions by first introducing metric to quantify the link-level symmetry of dataset. We then apply this metric to a collection of real-world link prediction benchmarks and analyze their structural difficulty. Finally, we evaluate the performance of several state-of-the-art models with different expressive capabilities across these datasets. Code is available a
5.1 A Metric for Measuring the Symmetry of Graphs
We introduce metric quantify the presence of non automorphic links with automorphic endpoints in dataset. This occurs when the underlying graph exhibits a high number of non-trivial automor- phisms that is, intuitively, when the graph highly symmetric. The symmetry of graph is tightly connected to the concept of node orbits, which we define below.
Definition 5.1 (orbit). The orbit of vertex D is defined as the set of nodes of VG to which e can be mapped via an automorphism or X Formally, Orb(v) (a(v) a IG). We denote with OG (Orb(u) E Va the set of all the orbits of V with respect to the action of NG.
Ve under the action of the automorphism group
Following 4 it is possible to define metric that mesures how much graph is symmetric follows:
We not report results for NCNC, as coincides with NCN for fully observed topologies. httts:://anony:: wwwpen/sssiiiieee///aoeaoooeeeee ganaaa--nn---- 8124//EADDD md

---

Table 3: MRR real-world link prediction datasets sorted by increasing ÿc. The top three results are highlighted using first, second, and third. DOM means Out Of Memory, >24h means more than 24 hours. As symmetry increases, only more expressive models maintain top performance. Results are averaged over runs with different random seeds; standard deviations are reported in Appendix
Graph Symmetry (-)
Models
OGBL CITATION2
CORA
CITESEER
PUBMED
OGBL
OGBL
OGBL
NSC
YST
GRQ
AIFB
EDIT
DDI
PPA
COLLAB
TSW
fG
0.01
0.02
0.02
0.08
0.10
0.12
0.13
0.16
0.23
0.30
0.41
0.67
GCN
19.98
16.61
21.09
7.13
13.46
26.94
6.09
26.79
1.17
6.89
10.85
4.12
GAT
0OM
13.84
19.58
4.95
12.92
00M
4.18
2.47
0.40
0.63
1.07
0.40
SAGE
22.05
14.74
21.09
9.40
12.60
27.27
5.53
20.32
1.77
1.34
0.54
8.35
GAE
DDM
18.32
25.25
5.27
3.49
00M
00M
16.61
2.32
2.32
10.98
BUDDY
19.17
13.71
22.84
7.56
12.43
27.70
5.67
18.40
13.68
46.23
13.73
22.66
Neo-GNN
16.12
13.95
17.34
7.74
10.86
21.68
5.23
22.86
5.78
29.51
13.11
8.10
NCN
23.35
14.66
28.65
5.84
12.86
35.06
5.09
30.36
11.99
48.45
6.47
10.32
NCNC
19.61
14,98
24.10
8.58
>24h
33.52
4.73
30,20
13.54
47.60
0OM
10.30
SEAL
20.60
10.67
13.16
5.88
9.99
29.71
6.43
30.85
17.51
56.72
16.30
25.82
Definition 5.2 (graph symmetry measure rG). Given graph G (Va, EG), its symmetry measure
calculated as:
TG = 1 10al -1
(II)
[Val -1
where |0 denotes the number of orbits of the graph and |VG is the number of nodes.
Computing all node orbits is computationally expensive. However, the number of orbits can be efficiently approximated using the number of distinct colors assigned by the WL convergence W LL 31 39), i.c.
W WLG [Vll -
fG =
(12)
The approximation in Equation reflects how closely the WL-induced partition (used Equation II matches the true orbit partition. Although there is complete characterization of WL failures in distinguishing nodes from different orbits, it said that WL gives different representations to almost all nodes that belong to different orbits [2]. A practical example is presented in (39], where the authors explicitly compare WL partitions and orbit partitions on the Alchemy dataset [14, Out of 202,579 graphs, only in 4 graphs the partition of the nodes induced by the WL is different wrt the orbits, highlighting that the WL approximation is extremely close in practice.
5.2 Symmetric Real- World Datasets for Link Prediction
We selected twelve datasets for link prediction, including well-known citation networks such as CORA and CITESEER, large-scale benchmarks from the Open Graph Benchmark suite like OGBL- CITATION2 and OGBL-COLLAB, and structurally complex knowledge and ontology graphs such as AIFB, EDIT-TSW More details about datasets can be found in Appendix E. For each dataset, we compute the proposed symmetry metric fG (Equation 12. The computed values are reported in the first row of Table with datasets sorted in ascending order of fc. As shown, the datasets exhibit widely varying degrees of symmetry. For instance, OGBL-CITATIONZ, CORA, and PUBMED display very low nGG values, largely due to the presence of informative node features that yield many unique WL colors. At the other end of the spectrum, datasets such as EDIT-TSW which lacks node features and exhibit high topological regularity, show significantly higher symmetry scores.
Table rreporss the results, in terms of the standard link prediction metric MRR. achieved by the models described in Section 3.1 The models are listed in ascending order of theoretical expressiveness, as characterized by Theorem 3.3 Since we are now evaluating under the standard link prediction setting (i.e., graphs with missing edges), we also include the NCNC variant of NCN. For ELPH, we report results for BUDDY, its more scalable version. All evaluations are conducted under the challenging and realistic HeaRT setting (32 Further details on model architectures and hyperparameter selection are provided in Appendix E while the complete results, including standard deviations and an additional
evaluation metric, reported in Appendix F

---

The results reveal clear trend: as fc increases. more expressive models become necessary. In the five datasets with the lowest symmetry, pure GNN-based methods consistently rank among the top three performers. However, as symmetry increases, their performance deteriorates and none of them appears the top three on the six most symmetric datasets. Conversely, SEAL,, the most expressive model in our hierarchy, ranks first across all high-symmetry datasets. This provides a key practical insight: while simple, less expressive models may suffice when node features are informative and structural ambiguity is limited, datasets with high link symmetry demand more powerful architectures.
Conclusion
We propose theoretical framework that formally compares wide range of existing models and establishes a hierarchy of them. We introduced LR-EXP, the first synthetic benchmark explicitly designed evaluate link-level expressiveness. Finally, demonstrated that increased expressiveness translates into performance gains on real-world link prediction tasks, especially in structurally symmetric graphs. These findings highlight that model selection should account for dataset symmetry: while simple models may suffice in low-symmetry settings, high-expressiveness architectures are essential when structural ambiguity is present.
Limitations and Future Work Our framework is tailored to MP models and does not directly account for recent advances in transformer- based architectures or spectral methods for link repre- sentation. Extending the framework to encompass these directions may provide additional insights, making this an interesting and valuable direction for future work. Furthermore, the highsyymmetry datasets used in our evaluation are relatively small, highlighting the need for larger and more robust benchmarks to properly assess model generalization and advance research in this area 5
10

---

Acknowledgments
Funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union the European Health and Digital Executive Agency (HaDEA). Neither the European Union nor the granting authority can be held responsible for them. Grant Agreement no. 101 101763 TANGO. We acknowledge the support of the MUR PNRR project FAIR- Future Al Research (PE00000013) funded by the NextGenerationEU. This work was also supported by Ministero delle Imprese del Made in Italy (IPCEI Cloud DM 27 giugno 2022 IPCEI-CL-0000007)
References
[1] Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The sur- prising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.01 179, 2020.
[2] László Babai and Ludik Kucera. Canonical labelling of graphs linear average time. 20th anmual symposium on foundations of computer science (sfcs 1979), pages 39-46. IEEE, 1979.
[3] Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In International Conference on Machine Learning, pages 599-608. PMLR, 2021.
[4] Fabian Ball and Andreas Geyer-Schulz. How symmetric are real-world graphs? a large-scale study. Symmetry, 10(1):29, 2018.
[5] Maya Bechler-Speicher, Ben Finkelshtein, Fabrizio Frasca, Luis Müller, Jan Tönshoff, Antoine Siraudin, Viktor Zaverkin, Michael Bronstein, Mathias Niepert, Bryan Perozzi, et al. Position: Graph learning will lose relevance due to poor benchmarks. arXiv preprint 250.. 2025.
[6] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022. URL htt.:ppprreeeieeeeeeeoorrrraaaaa
[7] Filippo Maria Bianchi and Veronica Lachi. The expressive power of pooling in graph neural networks. Advances neural information processing systems, 36:71603-7161 2023.
[8] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. JEEE Transactions on Puttern Analysis and Machine Intelligence, 45(1))657-66) 2022.
[9] Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verification using a" siamese" time delay neural network. Advances in neural information processing systems, 6, 1993.
[10] Chen Cai and Yusu Wang. A note over-smoothing for graph neural networks. arXiv preprint arXiv:2006. 13318, 2020.
[11] Jin- Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(():389-411 1992.
[12] Lei Cai, Jundong Li, Jie Wang, and Shuiwang Ji. Line graph neural networks for link prediction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 440):5103-5113,, 2021.
[13] Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Yannick Hammerla, Michael M. Bronstein, and Max Hansmire. Graph neural networks for link prediction with subgraph sketching. In The Eleventh International Conference on Learning Representations, 2023. URL https..ps: URt. //tppe/eeeeeeeeeee////e wttpeeeiiwwwwwweereeeeeee net/forum?
id=m1oq

---

[14] Guangyong Chen, Pengfei Chen, Chang Yu Hsieh, Chee- Kong Lee, Benben Liao, Renjie Liao, Weiwen Liu, Jiezhong Qiu, Qiming Sun, Jie Tang, al. Alchemy: A quantum chemistry dataset for benchmarking ai models. arXiv preprint arXiv: 19066094060 2019.
[15] Xueqi Cheng, Yu Wang, Yunchao Liu, Yuying Zhao, Charu C Aggarwal, and Tyler Derr. Edge classification graphs: New directions in topological imbalance. In Proceedings of the Eighteenth ACM International Conference on Web Search and Data Mining, pages 392-400, 2025.
[16] Anuj Dawar and Danny Vagnozzi. Generalizations of k-dimensional weisfeiler-leman stabiliza- tion. Moscow Journal of Combinatorics and Number Theory, 9(3):229 252, 2020.
[17] Bowen Dong, Charu C Aggarwal, and S Yu Philip. The link regression problem in graph streams. In 2019 IEEE International Conference on Big Data (Big Data), pages 1088-1095. IEEE, 2019.
[18] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. arXiv preprint arXiv:
2019.
[19] Francesco Ferrini, Antonio Longa, Andrea Passerini, and Manfred Jaeger. Meta-path learning for multi-relational graph neural networks. In Learning on Graphs Conference, pages 2-1. PMLR, 2024.
[20] R. A. Fisher. Contributions to Mathematical Statistics. Wiley, 1950.
[21] Martin Grohe, Moritz Lichter, and Daniel Neuen. The iteration number of the weisfeiler-leman algorithm. ACM Transactions Computational Logic, 26(1):1-31, 2025.
[22] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL itts: http://prooeedinnn.neeiiippp nwwripu....... 28777h/ie/cbbbeecaccccccccceee-3
pdff
[23] Harold Hotelling. The generalization of student's ratio. The Annals of Mathematical Statistics, 2(3):360-378, 1931. doi: 10..1214/aoo /214//om//17777329999 URL URL httphst//poooecteeuuccee
org/
euclid. aodd/daoo////moooooooooo 111773297777999
[24] Xingyue Huang, Miguel Romero, Ismail Ceylan, and Pablo Barceló. A theory of link predic- tion via relational weisfeiler-leman knowledge graphs. Advances in Neural Information Processing Systems, 16:19914-99748 2023.
[25] Neil Immerman and Rik Sengupta. The k-dimensional weisfeiler-leman algorithm. arXiv preprint 17X1v2190. 2019.
[26] Kanchan Jha, Sriparna Saha, and Hiteshi Singh. Prediction of protein-pront interaction using graph neural networks. Scientific Reports, 12(1):8360, 2022.
[27] Fabian Jogl, Pascal Welke, and Thomas Gärtner, Is expressivity essential for the predictive perfor- mance of graph neural networks? In NeurlPS 2024 Workshop on Scientific Methods for Under- standing Deep Learning, 2024. URL https::/ wtw.::/wwwweeeoouummmmmmm wow.:rmpnnrdd/
[28] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: arXiv:1609.02907, 2016.
[29] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint 1rXiv:1611.07308, 2016.
[30] Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional
networks. In International Conference on Learning Representations, 2017. URL httpps
//openreview net net//forum/id-SJU4ayyl)
12

---

[31] Veronica Lachi, Francesco Ferrini, Antonio Longa, Bruno Lepri, and Andrea Passerini. A simple and expressive graph neural network based method for structural link representation. In Creometry-grunder Representation Learning and Generative Modeling Workshop (GRaM) at ICML. 2024, pages 187-201. PMLR, 2024.
[32] Juanhui Li, Harry Shomer, Haitao Mao, Shenglai Zeng, Yao Ma, Neil Shah, Jiliang Tang, and Dawei Yin. Evaluating graph neural networks for link prediction: Current pitfalls and new bench- marking. In Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023. URL http::::/opeeeeeeeeeeeeee/// http:///ww.....oooooooo//////a/a
[33] Jinbi Liang, Cunlai Pu, Xiangbo Shu, Yongxiang Xia, and Chengyi Xia. Line graph neural networks for link weight prediction. Physica A: Statistical Mechunics and its Applications, page 130406. 2025.
[34] Moritz Lichter, Simon Raßmann, and Pascal Schweitzer. Computational complexity of the weisfeiler-leman dimension. In 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025), pages 13-1. Schloss Dagstuhl-Leibrng Zentrru für Informatik, 2025.
[35] Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications. 390(6): 150-1170, 2011.
[36] Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Simplifying approach to node classifica- tion in graph neural networks. Journal of Computational Science, 62:101695, 2022.
[37] Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602 4609, 2019.
[38] Christopher Morris, Fabrizio Frasca, Nadav Dym, Haggai Maron, Ismail Ilkan Ceylan, Ron Levie, Derek Lim, Michael M Bronstein, Martin Grohe, and Stefanie Jegelka. Position: Future directions in the theory of graph machine learning. Forty-first International Conference on Machine Learning, 2024.
2024.
[39] Matthew Morris, Bernardo Cuenca Grau, and Ian Horrocks. Orbit-equivariant graph neural networks. The Twelfth International Conference on Learning Representations, 2023.
[40] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. International Conference on Machine Learning, pages 4663 4673. PMLR, 2019.
[41] Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):11-33, 2015.
[42] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations.
[43] Andrea Rossi, Denilson Barbosa, Donatella Firmani, Antonio Matinata, and Paolo Merialdo. Knowledge graph embedding for link prediction: A comparative analysis. ACM Transactions on Knowledge Discovery from Data (TKDD), 15(2):1-44 1-)9, 2021.
[44] Balasubramaniam Srinivasan and Bruno Ribeiro. the equivalence between positional node embeddings and structural graph representations. In International Conference on Learning Representations, 2020. URL, http:
[45] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. http//tttts:/oppeeeeveee wttp://wwww......eoooooooeetetea
[46] Xiyuan Wang, Haotong Yang, and Muhan Zhang. Neural common neighbor with completion for link prediction. The Twelfih International Conference on Learning Representations, 2024.
13

---

[47] Xuhong Wang, Ding Lyu, Mengjian Li, Yang Xia. Qi Yang, Xinwen Wang, Xinguang Wang, Ping Cui, Yupu Yang, Bowen Sun, al. Apan: Asynchronous propagation attention network for real-time temporal graph embedding. In Proceedings of the 2021 international conference on management of data, pages 2628 2638, 2021.
[48] Yanbo Wang and Muhan Zhang. An empirical study of realized gnn expressiveness. arXiv preprint (.XX::23000077022 2023.
[49] Yanbo Wang and Muhan Zhang. An empirical study of realized GNN expressiveness. In Forty-first International Conference on Machine Learning, 2024. URL /tRp::tts://o/eereivie
het//forun2dd==llZZPO022
[50] Boris Weisfeiler and Andrei Leman. The reduction of graph canonical form and the algebra which appears therein. nti, Series, 2(9):12-16, 1968.
[51] Shunxin Xiao, Shiping Wang. Yuanfei Dai, and Wenzhong Guo. Graph neural networks in node classification: survey and evaluation. Machine Vision and Applications, 33(1):4, 2022.
[52] Yu Xie, Shengze Lv, Yuhua Qian, Chao Wen, and Jiye Liang. Active and semi semi-supervised graph neural networks for graph classification. IEEE Transactions on Big Data, 8(4):920-95) 0200099322200 2022.
[53] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural
networks? In International Conference on Learning Representations, 2019. URL https //openreview. wtt.:/ee/ooommmmmrmmsstttt
[54] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?, 2019.
[55] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974-983, 2018.
[56] Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo Kim. Neo-gnns: Neighborhood overlap-aware graph neural networks for link prediction. Advances in Neural Information Processing Systems, 34: 13683-13694, 2021.
[57] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
[58] 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 19073, 2021.
[59] Cai Zhou, Xiyuan Wang. and Muhan Zhang. From relational pooling to subgraph gnns: A universal framework for more expressive graph neural networks. In International Conference on Machine Learning. pages 42742-42766 PMLR, 2023.
[60] Tao Zhou, Progresses and challenges in link prediction. Iscience, 24(11), 2021.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The main claims are clearly stated in both the abstract and introduction, with pointers to specific sections that provide theoretical or empirical support. Each claim is substantiated in the body of the paper, ensuring consistency between the stated goals and the actual contributions.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discussed the limitations of our framework in Section 6 addressing both its scope, that is, its focus on message passing models, and broader limitation related to the scarcity of large high-symmetry datasets for evaluating link-level expressiveness.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
15

---

Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Appendix A provides formal proof' for all theoretical results presented in the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: For synthetic experiments, we provide details on graph construction, training. and evaluation in Section 4 Additional implementation details are included in Appendix E for both synthetic and real-world experiments. To ensure full reproducibility, we also release the complete source code.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
16

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We release both the code and the datasets, along with usage instructions, to ensure full reproducibility of the experimental results https://anonymouur 4open
science/r/link-nee http://///nnnkkppppreettttttooaa gnn- wwwggnnnnnnnnnne 8124/README md
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips.co
Seallic/guiee/Codeeefe
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
ptaiss.cc/uublicguuidees Sewpeddeee/ooeeSeeneeeeeeeeeeeee
ssinnolicc for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We specify all relevant training and evaluation details, including hyperparame- ters, data splits, and optimizer settings, in Appendix
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Result tables report standard deviation as error bars (Appendix F). Unless otherwise specified, results averaged over 5 runs with different seeds.
17

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix E.2 reports the compute resources used to experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: httpe//eeerrssccpppeeeeeeeeee/ee cc/ppbblic/Bhhhiccidddddliiii
Answer: [Yes]
Justification: The authors have read the NeurIPS Ethics Guidelines. All datasets used are publicly available, and we believe our work poses no immediate harmful consequences.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
18

---

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

---

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

---

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

---

A Proofs
Proof of Theorem 3.2 We prove theorem by addressing each of its three components individually,
1. Let M E M. If m = 0, then, regardless of k M is not able to distinguish between links whose endpoints are automorphic, i.e.,
vF E M, V(u v), (u', s.t. Jo,, E En with ai (w) = A o2((v) - o() F F((u, 2), x")
(13)
(14)
therefore, automorphic links whose endpoints are automorphic will be assigned to the same representation. Moreover, given M1, M2 E if m. = O, while m Ma >> 0 and COMB is injective, regardless of k- and k-bla MM S M2.
Proof Suppose md O, i.c. M is composed only of the functions and g, i.e., its functions are:
F(uu,v) x*) - g( x"), (0,
Assume is maximally expressive at the node level (note that GNN can achieve this, as the k-WL algorithm, preserves graph automorphisms for every & [34] 16 IT), i... assigns representations to nodes solely based their automorphism classes. Then for any automorphisms σ1, 02 E In such that 01 (1)) = and 02(v) = v', it follows that
o(u, x = p(ul x"), x = 6(v', x)).
Thus, regardless of the function g. we obtain
g X"), o(v, x²) = g( x²) M0'' x))),
i.e., the model cannot distinguish between links whose endpoints are automorphic. If (u, v) and (u', o') are not themselves automorphic pairs, then the model fails to differentiate them, thus assigning the same representation to non-automorphic links.
Now consider M1 M with all functions F M1 composed only of Φ and g. while M2 E M with all functions F E M2 that also include a component f (on the m-order neighborhood). Using Definition 2.8 we show that M2 is more expressive.
Let F1 E M1, F2 E M2. (u, v), (u', d') VG x VG such that (u, v) # (u',v') and Ri((u,)) x²) = (i x"),
but
E2((u, ()) + Fz v'), )
This implies that
g (o(,, Φ0v x²)) g x²) M(1', xx)). but due to the presence of component f and the use of an injective COMB, we get F2((u, v). x + (2 x*)
demonstrating by Definition 2.8 that M2 is more expressive than Mj.
2. Let MI, M2 M with k.M k-Ma 1-WL and let MMi IMa be the number of layers used respectively by Mi, M2. If m, + MM S M2 + Ma, then Mi S M2.
Proof Let F1 E M1, F22 E M2. Assume 1 > 1 + Ms - M2 and (M, < MM and
Mi M2.
Let (u, v), (u', o') E VG x VG such that
F Fi((u, G, v/), G, x)
Let c,, denote the color assigned to node u after & iterations of the 1-WL algorithm. Assume & = and ef = c,,; otherwise, F2 alone could distinguish between (u, v) and (ul, v'), and the proof would be complete.
22

---

We divide the proof into three steps. Since Fi distinguishes (u, v) from (uf, v') while Ey = cy and c = Co this implies that:
{ /
m M4
pi (((() iE m j=0
pi(w,x)) x)
w
U 5=0
U (
(1)
Let's consider the smaller neighborhood m
{ /pitu.))
m N2a
m Ng U valdsen 5=0
x)
w E
U (u) j=0
and Pı(1,X) ie
If these sets are already different, then F- (with smaller neighborhood but same P1) suffices, and the proof is complete. If instead they equal, then from (1) it follows that the difference lies in the sets:
{ pi (ww x)
m
} + (plix) iE U j=m2+1
U (u(()))) j=m2+1
W
Since F2 uses number of layers M 2 M m m Ma, it can compensate for the smaller neighborhood radius my by using more layers to reach the same depth of information F.. Thus, using p2 in F2, we obtain:
m
N o) } + pe(w, X)
m M2 U N (vdd. j=0
P=(w, X)
we E
U j=0
w E
which implies
F2((u, v), x0) # Fa((u',e') e'), x²).
and by Definition 2.8 this yields M1 S M2.
3. Let MI, M2 E M with mi m M2, If k-bts < hal then Mi S M2.
Proof Let m m2 = and knd kM Let Fi M1 and F3 e M2 and (u, (1',"") E Va x VG such that
F
FR ((,
Assume that ce ch and ce if..ie.. i.e., and u', as well and v', have the same WL color after iterations. Otherwise, F2 could already distinguish the links based on kMa alone, and the proof would be trivial.
Now, since Fi can distinguish the links despite dh = and oe = & this implies that:
+ { /all...))) i (u'''o .0) }
we E U (u, 3
P1(w, G)
(I)
. 1
j=0
Since k-M < k-M,,, and both models operate the same neighborhood radius m, it follows that there exists a number of layers (possibly greater than in Fj [21 25)) such that Fz can also distinguish these sets. That is,
{
(u, + (
ie U (alu,oo) ). j=u
palwu, G)
w E U
1=
which implies
F2((u, v), G, X,X + Fa(lul, G,)).
Therefore, by Definition 2.8 F F2.
23

---

Proof of Theorem 3.3 This follows directly from Theorem 3.2 Pure GNNs only rely on node rep- resentations & and the combining function 9. without any function over the m-order neighborhood. As established in Theorem 3.2 such models cannot distinguish between links whose endpoints are automorphic. In contrast, NCN, Neo-GNN, ELPH, and SEAL incorporate neighborhood func- tions f (all with injective COMB operations, namely concatenation), which increases their expressive power.
According to Table Neo-GNN uses a fixed number of message-pant paasgggg-- layers (Neo- GNN while NCN allows (NCN to be freely chosen. Since both models operate with the same type of base function p (e.g., 1-WL), Theorem 3.2 implies that if /NCN 2 mNNooGNN then NCN can simulate or surpass Neo-GNN's receptive field and representational capability. Hence, Neo-GNN I NCN.
3. By design, ELPH does aggregates counts over the m-hop neighborhood. If Neo-GNN uses neighborhood of size at least mL 1, then Theorem 3.2 ensures it can access all the information available to ELPH and apply additional learned transformations via its GNN layers. Thus, Neo-GNN is more expressive.
any message- message-passing layers (FELPH 0, Table I. and instead
4. ELPH relies only on aggregated neighborhood counts and uses [LLPP layers. NCN uses fixed radius m NCN = 1 (Table l). but allows a configurable number of layers. If (NCN 2 m ELPII 1, then by Theorem 3.2 NCN can effectively capture structural signals that ELPH computes with wider but shallower architectures, achieving greater expressiveness.
5. SEAL is more expressive due to both its flexible architecture and enhanced pessagg-paassing capabilities. Specifically, SEAL builds a subgraph around the link and augments the adjacency matrix with positional encodings that are link-aware, effectively allowing a learned structural encoding over link neighborhood N (u, v). This corresponds to the expressive power of higher-order WL test (namely 1-| (u, - [59]), which is strictly more powerful than 1-WL. Moreover, SEAL allows arbitrary m SEAL and (SEAL, so for any other model with weaker p. one can always configure SEAL with the same and sufficient number of layers match exceed its expressiveness. Prior results have shown that highly expressive architectures may require deeper message passing to converge
21 25
which SEAL supports by design.
B
Additional Information on LR-EXP
B.1
Evaluation method
This section provides more detailed explanation of how the components of the Reliable Paired Comparison work to evaluate different models in the synthetic setting.
Major Procedure Given graph G, select two structurally distinct links v),, e' (u', v"). Then we create q isomorphic copies [G1, G....., Gg) by randomly permuting its nodes. For each copy G₃ and pair of links e,, e/, compute the embedding differences:
d, = f(G,, e - f(G,, e i i [q],
(15)
where f is the embedding function learned by the model. Assuming that the difference vectors independent random vectors N (1, E), we consider that f(,)) follows a Gaussian distribution, so random permutations only introduce Gaussian noise into the results.
If the model is not able to distinguish links e and e', the mean difference should be μ 0. To
check this a level Hotelling's s T-square test is conducted, comparing hypothesis Ho μ = 0 and H1 : y o The statiisic for y is calculed as:
2 = g(d ( s--(s-(d- -1),
(16)
where
9
9 (dc d) d)
dis
$
(17)
i=1
24

---

Hotelling's T-square test establishes that T follows the distribution of random variable (d-1)d
Pd.g-d- where Fd.g-d represents F-distribution with degrees of freedom d and d This theorem provides link between the unknown parameter z and specific distribution Fa.q enabling us to validate the confidence interval of l by analyzing how well it matches the assumed distribution. To evaluate the hypothesis Ho l 0, we substitute l 0 into Equation
23
16.. leading to:
Tes = qd S- sd'ss''a
(18)
An a-level test of Ho la 0 against the alternative H1 * 0 supports Ho (meaning the model fails to differentiate the pair)
The = qd' s- 11- (9-
Fa.g
(19)
where (()) represents the upper (100a)-th percentile of the F-distributiin Fá.gad 20 with degrees of freedom and d. Conversely, we reject Ho (indicating that the model successfully distinguishes the pair) if:
T2 = qddds-ss s-lds
(q (9-1)d (q-d) d) Fla-a(a)).
(20)
By selecting appropriate value of a, the Main Procedure ensures a reliable confidence interval to evaluate distinguishability. However, choosing a heuristically may not be optimal approach. Additionally, computational precision can introduce deviations in the assumed Gaussian fluctuations. To address this issue, we employ the Reliability Check, which captures both external differences between two graphs and internal variations within single graph.
Reliability Check
Without loss of generality (WLOG), we replace (G,, et)) with a permutation of G. denoted as ee). This allows to analyze the internal fluctuations of G for the same link. We follow the same steps as in the Main Procedure.
Proceeding with (G,, ex) and ,G7,e5] we compute the T -stattistic as:
T2 reliability = =dd" S-1 d,
(21)
where
=
de. d, = f(Gr,e)) - e(), i
(22)
1=1
S = q
Σ (d. dd, - -d)
(23)
Since G and GT are isomorphic, the GNN should not differentiate between them, implying that O. Consequently, the test is considered reliable only if
(g 1)d (q d) Fag-a((a)
The feliaillity
(24)
By combining the reliability check with the distinguishability results, we obtain the full RPC Reliability Procedure Check.
For each pair of structurally different links e and e', the threshold is computed as:
(q - 1)d
Threshold
Fd. 1..---0 d(a).
(25)
(g d)
25

---

Next, we perform the Main Procedure on e and e' to evaluate distinguishability and we conduct the
Reliability Check on and e" The GNN is considered capable of distinguishing and e' only if both conditions
reliahility
Threshold <
T
(26)
are satisfied.
B.2 Experimental Results with different significance level values
We tested the sensitivity of results of Section 4.3 to the choice of the significance level in the reliability check. Specifically, we experimented with three commonly used values in statistical testing, i.e., The resulting performance on LR-EXP are reported in Table
As expected, all standard GNN models consistently fail recognize any links, regardless of the significance level. Among the more expressive models, the majority show stable behavior across different values of significance, with fluctuations that remain within the standard deviation. BUDDY and NCN exhibit slightly larger fluctuations in absolute value, but the key point for this experiment is the expressiveness ranking across models. This ranking remains robust across all significance levels, with one minor exception: at significance level 0.1, Neo-GNN slightly surpasses NCN. However, this difference falls within the standard deviation range.
Table 4: Test Precision (mean + std over 5 runs) for significance level values 0.1, 0.05, 0.01.
Model
0.1
0.05
0.01
GCN
0 0
0 0
0 0
GAT
0:0
0
0 0
GAE
0
0
0
SAGE
11:0
844
3
BUDDY
54 5
45
59 #9
ELPH
+2
62
Neo-GNN
76 16 6
+
71 + 2
NCN
7
75
SEAL
92
97 0
97 7
C Further Experiments on LR-EXP
In the experiment of Section to ensure a fair comparison, we selected for each model the maximum neighborhood radius that makes it as expressive as possible while still respecting its design constraints. For example, in models like NCN, the radius is fixed by design and equal to 1, so it cannot be varied. In others, such ELPH, the radius tunable but constrained to maximum of 3 by the original authors for computational reasons, and we adopted that upper bound. As for GNN depth, we fixed the number of layers to as commonly done in the literature 44).To To explore this further, we conducted two additional experiments the LR-EXP dataset: 1) Fixed radius number layers (see Table 5): 2) Fixed number of layers = 3, varying the neighborhood radius (see Table 6))
1, varying the
Table 5: 1) Fixed Radius
# Layers
NCN
Neo-GNN
ELPH
SEAL
74 + 1
42 4
40 +
79 + 3
75 1
42
55 +
89 1
3
75
+
1
45
62 + 2
89 +
These results are fully consistent with Theorem the number layers improves expressiveness all the models; when fixing the number of layers, increasing the radius also improves expressiveness in all the models.
3.2 (Point 2): when fixing the radius, increasing
26

---

Table 6: 2) Fixed # Layers =
Radius
NCN
Neo-GNN
ELPH
SEAL
1
75 +1
45
62 + 2
89 + 2
2
63 3
61
90 = 3
3
2
62 7
97 + 0
D Computational Costs
The overall time complexity of models for link prediction can be expressed as O(B + Ct), where / is the number of links to be predicted, B is the preprocessing cost and C' per-link cost [46]. In Table we report the time complexity existing models, where is the number of nodes. is the maximum node degree, h is the complexity of the hash function used in BUDDY, f is the feature dimension and m is the radius of the neighborhood.
Table 7: Time complexity of models expressed O(B Ct), where is the number of links to be predicted, the preprocessing cost and per-link cost.
Method
GAE
ndf + nf² ndf + nf² + nd
f²
Neo-GNN
d + f2 h + f dim+ 1) dm
BUDDY
ndf + nh 0 ndf + n2 ndf + n2
SEAL
NCN
df + f2
NCNC
d2 f + df2
Among these, SEAL is the most expressive but also the most computationally expensive, due to its exponential dependence the neighborhood radius. NCN and BUDDY provide the best trade-off' between expressiveness and computational cost. Neo-GNN, while more expensive than NCN, is in fact less expressive. GAE is the least costly, but also the least expressive.
E
Experimental details
E.1 Real world datasets
Table presents the statistics of the standard datasets commonly used for link prediction tasks. The Cora, Citeseer, and Pubmed datasets are well-known citation networks, often employed as benchmarks for graph-based learning methods. These datasets relatively small in scale, both in terms of nodes and edges. In contrast, the OGB (Open Graph Benchmark) datasets including ogbl- collab, ogbl-ddi, ogbl-ppa, and ogbl-citation2 are significantly larger and more complex, providing challenging benchmarks for evaluating scalability and performance on large graphs.
For Cora, Citeseer, and Pubmed, adopt fixed train/validationntssl split of 85/5/10%. For the OGB datasets, we use the official splits provided by the OGB benchmark.
Table 8: Statistics of datasets. The split ratio is for train/validation/test.
Dataset
Cora
Citeseer
Pubmed
ogbl-collab
oghl-ddi
ogbl-ppa
ogbl-citation2
#Nodes
2,708
3,327
18,717
235,868
4,267
576,289
2,927,963
#Edges
5,278
4,676
44.327
1,285,465
1,334,889
30,326,273
30,561,187
Mean Degree
3,90
2.81
4.74
10.90
625,68
105.25
20.88
Split Ratio
85/5/10
85/5/10
85/5/10
92/4/4
80/10/10
70/20/10
98/1/1
Table reports the statisties of additional datasets characterized by high symmetry, which are also used in our experiments. These datasets span various domains, including social networks, biological systems, and knowledge graphs, offering diverse struetural properties and serving as valuable benchmarks for evaluating models under highly regular and repetitive connection patterns.
27

---

Specifically, the AIFE dataset models the organizational structure of the AIFB research institute, capturing relationships among staff, research groups, and publications. Edit- TSW2 models user interactions and content editing activities within the Wiktionary platform. Finally, the NSC YST., and GRQ² datasets, introduced in [2], focus on relational learning tasks and exhibit highly symmetric structures, making them particularly suitable for evaluating link prediction models.
Table 9: Statistics of datasets. The split ratio is for train/validationntest.
Dataset
NSC
YST
GRQ
aifb
edit-tsw
#Nodes
332
2,284
5,241
8,285
1,079
#Edges
2,126
6,646
14,484
46,042
2.756
Mean Degree
12.81
5.82
5.53
5.56
5.11
Split Ratio
80/10/10
80/10/10
80/10/10
80/10/10
80/10/10
E.2 Implementation details
This section provides hyperparameters details for models trained and evaluated on both LR-EXP and the real-world datasets. All experiments were conducted workstation running Ubuntu 22.04 with an AMD Ryzen 9 7950X CPU (32 threads), 124GB of RAM, and two NVIDIA GeForce RTX 4090 GPUs (24GB each).
Synthetic Hyperparameter Settings We present the hyperparameter search space for the LR-EXP datasets in Table TO For each model, initially followed the hyperparameter configurations proposed in their respective papers. However, due to the small size the synthetic graphs in LR-EXP, significantly reduced the embedding dimensions, which led improved performance in most cases.
Table 10: Hyperparameter Search Ranges for LR-EXP. Abbreviations: LR Learning Rate, Drop. Dropout, WD Weight Decay, #L Number of Model Layers, #P Number of Prediction Layers, Dim = Embedding Dimension.
Dataset
LR
Drop.
WD
#L
#P
Dim
LR-EXP (0.01, 0.001) (0.1, 0.3, 0.5) (Ie-4, le-7, 0) (1, 2, 3) (1, 2, 3) (2-256)
Real- World Hyperparameter Settings We report the hyperparameter search space for all real- world datasets used our experiments Table For Cora, Citeseer, Pubmed, ogbl-collab, ogbl-ddi, ogbl-ppa, and ogbl-citation2, we adopt the hyperparameter settings declared in the paper [32]. For the remaining datasets, NSC, YST. GRQ. aifb, and edit-tsw, we conducted hyperparameter search using the ranges specified in the table.
F Real-world results with standard deviations
In this section, we present the same results as in Table now including standard deviations computed over 5 runs with different random seeds. Specifically, Table 12 reports the MRR results on standard small datasets, Table 13 shows the MRR results on the OGB benchmark, and Table 14 reports the MRR results for highly symmetric datasets.
Hits@k. k. We also report the Hits @ metric, using 10 for the standard small datasets (Table 15 and for the new highly symmetric dataset (Table 16), and 20 for the larger datasets (Table [7]. following the evaluation protocol of Li et al. (32]
28

---

Table 11: Hyperparameter search ranges for all real-world datasets. Abbreviations: LR = Learning
Rate, Drop. Dropout, WD Weight Decay, #I Number of Model Layers, #P Number of Prediction Layers, Dim = Embedding Dimension.
Dataset
LR
Drop.
#1.
#P
Dim
Cora
(0.01, 0.001)
(0.1. 0.3, 0.31. 0.5)
(le-4, le-7,
(1, 3)
(1. 3)
(128. 256)
Citeseer
(0.01, 0.001)
(0.1. 0.3, 0.5)
(le-4, 1e-7.0)
(1, 3)
(1.
(128, 256)
Pubmed
(0.01, 0,001)
00.1,
(Ic-4, 1c-7.0)
(1, 1,2,33
(1,2,3)
(128, 256)
ogbl-collab
(0.01, 0.001)
(0, 0.5)
3
256
ogbl-ddi
(0.01, 0.001)
0.5)
3
256
ogbl-ppa
(0.01, 0.001)
(0, 0.5.
256
ogbl-citation2
(0001,0.001)
(0, 0.3, 0.5)
3
128
NSC
0.01,,.0011
(0.1, 0.3,0.0,.33
(le-4, lc-7.0)
(1,2,3)
(1,
(64, 128, 256)
YST
10.01,0.001
(0.1,
1e-74))
(1,
(1,2,3)
(64, 128, 256)
GRQ
(0.01, 0.001)
(0.1. 0.3.
(le44.
(1,2,3)
(1,2,3)
(64, 128, 256)
aitb
(0.01, 0.001)
00.1, 0.5)
1e-.0)
(1,
(1,2.3)
(64, 128, 256)
edit-tsw
(0.01, 0.001)
(0.1, 0.3, 0.5)
(1--4,
(1,2,3) (1,2,3)
(64, 128, 256)
Table 12: MRR with standard deviations on real-world link prediction datasets.
Models
NSC 0.16
YST 0.24
GRQ 0.30
ATFB 0.41
EDIT-TSW 0.67
fG
GCN
26.79 1.08)
1.17 (#: 0.02)
6.89 (:: 0.47)
10.85 (#: 0.12)
4.12 (#: 0.21)
GAT
2.47 (#: 3.58)
0.40 0.00)
0.63 0.40)
1.07 0.51)
0.40 (#: 0.00)
SAGE
20.32 0.11
1.77 1.38)
1.34 1.32)
0.54 (#: 0.08)
8.35 (# 7.27)
GAE
16.61 (#: 10.00)
2.32 (#: 0.01)
2.32 (# 0.01)
10.98 (#: 0.01)
3.54 (#: 0.01)
BUDDY
18.40 (:1: 0.07)
13.68 (1L: 0.61)
46.23 (1. 0.42)
13.73 (1. 0.11)
22.66 (1: 0.46)
ELPH
26.09 (1 1.04)
13.15 (1. 1,12)
38.88 (1 0.55)
13.39 (1. 0.60)
10.10 7,37)
Neo-GNN
22.86 0.75)
5.78 0.12)
29.51 (1 0.38)
13.11 (1 0.51)
8.10 (L 0.29)
NCN
30.36 0.28)
11.99 (:: 0.06)
48.45 (# 0.02)
6.47 (#: 0.23)
10.32 (:: 0.39)
NCNC
30.20 (= 0.03)
13.54 (:: 0.47)
47.60 (#: 0.52)
00M
10.30 (+: 0.39)
SEAL
30.85 (= 1.46)
17.51 (#: 0.94)
56.72 (# 1.35)
16.30 (#: 0.22)
25.82 (#: 1.47)
Table 13: MRR with standard deviations on real-world link prediction datasets.
Models
CoRA 0.02
CITeSEER 0.02
PUBMED
fG
0.08
GCN
16,61 (#: 0.30)
21.09 (#: 0.88)
7.13 (#: 0.27)
GAT
13.84
19.58 (1:
4.95 0.14)
SAGE
14.74 0.69)
21.09 (:: 1.15)
9.40 0.70)
GAE
18.32 (#: 0.41)
25.25 (:: 0.82)
5.27 (+: 0.25)
BUDDY
13.71 (# 0.59)
22.84 (#: 0.36)
7.56 (#: 0.18)
Neo-GNN
13.95 (1. 0.39)
17.34 (L 0.84)
7.74 (1 0.30)
NCN
14.66 0.95)
28.65 1.21)
5.84 0.22)
NCNC
14.98 1.00)
24.10 (L 0.65)
8,58 (1L 0.59)
SEAL
10.67 (# 3.46)
13.16 (+: 1.66)
5.88 (# 0.53)
Table 14: MRR with standard deviations on real-world link prediction datasets.
Models
CITATINT
OGBL-DDI 0.10
OGBL-PPA 0.12
OGBL-COLLAB
fG
0.01
0.13
GCN
19.98 (#: 0.35)
13.46 (:: 0.34)
26.94 (d: 0.48)
6.09 (+: 0.38)
GAT
22.05 (#: 0.12)
12.92 (#: 0.39)
27.27 (#: 0.30)
4.18 (#: 0.33)
SAGE
00M
12.60 (::
0OM
5.53 0.50)
GAE
3.49 1.73)
0OM
BUDDY
19.17 (#: 0.20)
12.43 (1: 0.50)
27.00 (+: 0.33)
5.67 (+: 0.36)
Neo-GNN
16.12 (# 0.25)
10.86 (#: 2.16)
21.68 (+: 1.14)
5.23 0.90)
NCN
23.35 0.28)
12.86 (#: 0.78)
35.06 (+: 0.26)
5.09 0.38)
NCNC
19.61 0.54)
>24h
33.52 (1:
4.73 0.86)
SEAL
20.60 (1 1.28)
9.99 (1L 0.90)
29.71 (1: 0.71)
6.43 0.32)
29

---

Table 15: Hits @ 10 with standard deviations real-world link prediction datasets.
Models
NSC 0.16
YST 0.24
GRQ 0.30
ATFB 0.41
EDIT-TSW
FG
0.67
GCN
43.08 (:: 1.36)
0.75 (#: 0.00)
13.47 (d: 2.97)
17.56 (#: 0.92)
5.91 (d: 0.97)
GAT
2.36 4.09)
0.00
0.44
1.51 (#
0.00
SAGE
24.06 (1: 3.68)
3.56 3.96)
2.44 (1: 4.17)
0.41 (2: 0.38)
10.67 (4: 10.07)
GAE
30.38 (# 9.90)
3.38 (# 0.00)
3.38 (#: 0.00)
16.92 (# 0.09)
3.80 (# 0.00)
BUDDY
28.93 (# 2.68)
22.89 (# 0.69)
67.26 0.25)
24.28 (# 0.5T)
36,00 2.27)
ELPH
38.37 (#
22.34 (#
59,44 0.99
26.19 (#: 183)
21.45
Neo-GNN
37.11 (1: 0.72)
10.29 (1 0.17)
44.50 (1: 0.24)
24.29 (L: 1.74)
12.36 (1: 1.09)
NCN
47.17 (1 0.94)
20.03 (1 0.00)
68.67 (1: 0.14)
9.42 (::: 0.76)
16.48 (: 0.56)
NCNC
46.86 (d: 0.27)
22.44 (1: 1.04)
68,28 (d: 0.23)
DOM
15.03 (d: 1.87)
SEAL
51.26 (#: 0.98)
28.36 (# 1.46)
71.64 (+: 1.04)
31.84 (#: 0.70)
42.55 (#: 2.39)
Table 16: Hits 10 with standard deviations on real-world link prediction datasets.
Models
CoRA 0.02
CITESEER 0.02
PUBMED
fc
0.08
GCN
36,26 (d:: 1.14)
47.23 (:: 1.88)
15.22 (1: 0.57)
GAT
32.89 (d: 1,27)
45.30
1.30)
9.99 (1 0.64)
SAGE
34,65 (=:
48.75
1.85)
20.54
GAE
37.95 (:: 1.24)
49.65
1.48)
10.50 0.46)
BUDDY
30.40 (+: 1.18)
48.35 (:: 1.18)
16.78 (# 0.53)
Neo-GNN
31.27 (#: 0.72)
41.74 ( 1.18)
17.88 (# 0.71)
NCN
35.14 (:: 1.04)
53.41
1.46)
13.22 0.56)
NCNC
36.70 (d: 1.57)
53.72
0.97)
18.81 1.66
SEAL
24.27 (d: 6.74)
27.37 3.20)
12.47 (:: 122)
Table 17: Hits@20 with standard deviations on real-world link prediction datasets.
Models
OGBL-CITATION2
OGBL-DDI
OGBL-PPA
OGBL-COLLAB
fG
0.01
0.10
0.12
0.13
GCN
51,72 (t: 0.46)
64.76 (#: 1.45)
68.38 0.73)
22.48 (# 0.81)
GAT'
53.13 (t: 0.15)
66.83 (:: 2.23)
69.49 (t 0.43)
18.30 (# 1.42)
SAGE
ODM
67.19 (#: 1.18)
DOM
21.26 (# 1.32)
GAE
DOM
17.81 (::: 9.80)
DOM
DOM 23.35 (::: 0.73)
BUDDY
47.81 0.37)
58.71 (1:
71.50 0.68)
Neo-GNN
43.17 (1 0.53)
$1.94 (1: 10.33)
64.81 (1: 2.26)
21.03 (1: 3.39)
NCN
53.76 (t= 0.20)
65.82 (#: 2.66)
81.89 (+: 0.31)
20.84 (# 1.31)
NCNC
51.69 (# 1.48)
>24h
82.24 ( 0.40)
20.49 (# 3.97)
SEAL
48.62 1.93)
49.74 (#: 2.39)
76.77 0.94)
21.57 0.38)
30


Reviews:
[{"review_id": "4nl9FaYDL9", "reviewer": "Reviewer_eEem", "summary": "This paper studies the expressiveness of GNNs for link prediction and presents a new unifying framework that formally characterizes existing link prediction models. The authors also present a new synthetic dataset to specifically evaluate link-level expressiveness and highlight the role of graph symmetry in the performance of GNN models for link prediction.", "questions": "See weaknesses. Additionally:\n- In the real-world benchmark analysis, can the authors comment on why the more expressive models (BUDDY, SEAL, etc.), perform so much worse in lower-symmetry settings? \n- Do the authors have any intuition as to how their framework relates to knowledge graph embedding (KGE) models, which also focus on link prediction?\n- Could the authors please clarify if they are using the oblivious or non-oblivious (i.e. folklore) version of the WL hierarchy (see Grohe, 2021 for details)? For completeness, it would be useful to explicitly state this.\n\nReferences:\n\nM. Grohe. The logic of graph neural networks. In _LICS_, 2021.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper is well written and easy to follow\n- The proposed framework is clear and appears naturally for comparing these models\n- Experimental results on the newly presented synthetic dataset support the theoretical expressivity results\n- Analysis on real-world performance and the effect of graph symmetry provides interesting insights\n\nWeaknesses:\n- The scope of the proposed framework is not fully clear within the context of existing literature. How does it compare to works such as Huang et al., 2023, which studies the expressivity of GNNs for link prediction over heterogeneous graphs or Zhang et al., 2021, which presents theoretical results on multi-node representation learning?\n- Motivation-wise, the usefulness of this new characterization is still a bit unclear to me due to its limited scope. Link representations are already addressed in the traditional WL hierarchy by higher order GNNs which can generate node-pair representations for link-level tasks.\n\nReferences:\n\nHuang et al. A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs. In _NeurIPS_, 2023.\n\nZhang et al. Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning. In _NeurIPS_, 2021.", "was_revised": true, "final_justification": "While the general framework is interesting, the overall scope of the work is somewhat limited, since the analysis excludes higher-order GNNs. However, the framework's ability to accomodate several current methods is technicall solid, and thus I maintain my score.", "rebuttal": "**We would like to thank the reviewer for the thoughtful comments and useful suggestions.**\n\n\n---\n\n\n\n**W1: Comparison with Zhang et al., 2021 and Huang et al., 2023**  \n\nZhang et al. (2021) propose the *labeling trick*, a specific method designed to improve the expressiveness of GNNs for link prediction. In our work, we present a general framework that *subsumes* all message-passing methods for link representation, including the labeling trick (see the last row of Table 1). The role of the framework is to provide a formal lens through which different link representation models can be expressed using the same building blocks, characterized by the functions $\\phi $, $\\rho$, and the parameters $ l $ and $m $. By rewriting each method within the framework, we can precisely understand its expressiveness and compare it to others in a principled way. For instance, thanks to Theorem 3.2, we can conclude that the labeling trick is more expressive than any other existing method based on structural features. We will better explain it in the revised version of the manuscript.\n\nHigher-order GNNs could, in principle, be used  to construct expressive link representations. We note, however, that the quadratic complexity of “proper” order-2 GNNs has prevented practitioners from actually following that approach. Thus, the approach by Huang et al. (2023), though inspired by higher-order message passing, effectively still computes node level representations (but relative to a second, fixed reference node). The goal of our paper was to provide a framework that accommodates a large number of current methods that have been applied in practice. Extending the framework  to include also (proper) higher-order approaches would be interesting from a purely theoretical point of view, but is outside our current scope. \n\n---\n\n**W2: Usefulness of the framework with respect to WL hierarchy**  \n \nAs noted in our response to W1, while it is true that higher-order GNNs (e.g., 2-WL-based architectures) could, in principle, produce expressive node-pair representations, their quadratic complexity has significantly limited their practical adoption. Many alternative link prediction models have been proposed that rely on other strategies, such as structural features or neighborhood-based heuristics, to achieve higher expressiveness in a more computationally efficient way. The goal of our paper is to provide a unified framework that encompasses all these methods (and potentially also future ones), and to offer theoretical tools to compare their expressiveness in a principled manner.\n\n---\n\n**Q1: Why do the more expressive models perform so much worse in lower symmetry setting?** \n \nMore expressive models are explicitly designed to distinguish non-automorphic links with automorphic endpoints (i.e., dashed red links in Figure 2). However, in low-symmetry graphs, such ambiguous links are rare. These graphs tend to have highly informative features and irregular structures, making most links trivially distinguishable from their endpoints alone. As a result, standard GNNs are often sufficient to achieve strong performance.  \nIn this context, the added expressiveness of models like SEAL and BUDDY does not yield a clear advantage, but it does not systematically hurt either. For instance, on the four real-world datasets with symmetry below 0.1, BUDDY performs better than GCN in two cases and worse in two; SEAL outperforms GCN in one case. This suggests that in low-symmetry settings, simpler models are often sufficient and the performance gap narrows.\n\n---\n\n**Q2: Do the authors have intuitions on the connection with KGE?**  \n\nOur framework could be quite easily generalized to directed and multi-relational graphs, including knowledge graphs. We did not go in this direction for the time being, because, on the one hand, this would cause a significant blowup in complexity of notation and the statement of Theorem 3.2. On the other hand, such structurally richer graphs would typically exhibit much lower symmetry levels, thereby alleviating the limitations of node-level representations for link prediction. This is particularly true for knowledge graphs. Indeed, for link prediction in the transductive setting (in particular: knowledge graph completion) it would be admissible to include unique node identifiers as node attributes, in which case our expressivity problem disappears completely. This also is a reason why our synthetic data focuses on inductive link prediction on many small graphs.  \nAs for KGE models, positioning them within our framework is less straightforward, since many do not rely on message passing and operate under fundamentally different assumptions. A detailed investigation of how KGE approaches relate to our framework is an interesting open question, and we consider this a valuable direction for future work.\n\n---\n\n**Q3: Which version of the WL-hierarchy are the authors using?**  \n\nWe thank the reviewer for the opportunity to clarify this important point. We use the oblivious version of the Weisfeiler–Leman test. We will make this explicit in the preliminaries section of the paper to avoid any ambiguity."}, {"review_id": "BM9VlFJypl", "reviewer": "Reviewer_gepd", "summary": "This paper studies how Graph Neural Networks (GNNs) represent links (pairs of nodes), which is less understood than node or graph-level tasks. The authors propose a new framework that helps describe and compare many existing link models. They build a hierarchy based on expressiveness and support it with both theory and experiments. They also design a small synthetic dataset (LR-EXP) to test whether models can tell different types of links apart, and analyze how symmetry in graphs affects performance.", "questions": "1. Can the framework be extended to non-MP models like GNN transformers?\n2. What is the best trade-off between the number of GNN layers and neighborhood size?\n3. Can you propose new methods or models that boost the existing performance based on the insight in this paper?", "limitations": "See above", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "### **Strengths**\n\n- The proposed framework is simple and unifies many existing methods.\n- The paper provides strong theoretical insights about when and why some models are more expressive.\n- The LR-EXP dataset is designed to test link-level expressiveness and can be used for future studies.\n\n### **Weaknesses**\n- The paper is more like a benchmark paper instead of a research-track paper, as it mainly provides an evaluation method for existing ones.\n- The datasets used in this study are limited in size.\n- More ablation or empirical studies on design choices like GNN depth vs. neighborhood radius would help.", "was_revised": true, "final_justification": "The author's rebuttal has addressed my concerns in terms of the paper's significance. They have also provided additional ablation and empirical studies. My previous proposed questions have been answered clearly. Therefore I would like to raise my score.", "rebuttal": "**We would like to thank the reviewer for the thoughtful comments and useful suggestions.**\n\n---\n\n**W1: The paper is more a benchmark paper of a research-track paper**  \n\nWhile our paper introduces a new synthetic dataset and evaluates link prediction models on real-world benchmark, its primary contribution is theoretical. We propose a novel framework to formally analyze and compare the expressiveness of GNN-based link representation models. The paper presents new theoretical results (Theorems 3.2 and 3.3), establishes an expressiveness hierarchy of existing methods, and introduces a graph symmetry metric to connect theoretical insights with empirical performance. We believe, as also recognized by the other reviewers, that the strength and originality of these methodological and theoretical contributions make the paper well-suited for the Research track.\n\n---\n\n**W2: The datasets used in this study are limited in size**  \n\nWe would like to clarify that our study includes both small and large-scale datasets. In particular, we evaluate on OGBL-Citation2 (2,927,963 nodes and 30,561,187 edges) and OGBL-PPA (576,289 nodes and 30,326,273 edges), which are among the largest publicly available link prediction benchmarks.\n\nThat said, we emphasize that expressiveness is not inherently related to dataset size. Our goal is not to assess scalability, but to understand the expressiveness of different models.\n\n---\n\n**W3: More ablation or empirical studies on design choices like GNN depth vs. neighborhood radius would help.**  \n\nWe thank the reviewer for this suggestion and have conducted additional ablation experiments to further analyze the effect of GNN depth and neighborhood radius on model expressiveness.\n\nIn the original experiment reported in the paper, to ensure a fair comparison, we selected for each model the maximum neighborhood radius that makes it as expressive as possible while still respecting its design constraints. For example, in models like NCN, the radius is fixed by design and equal to 1, so it cannot be varied. In others, such as ELPH, the radius is tunable but is constrained to a maximum of 3 by the original authors for computational reasons, and we adopted that upper bound. As for GNN depth, we fixed the number of layers to 3 as commonly done in the literature [1].\n\nTo explore this further, we conducted two additional experiments on the LR-EXP dataset:\n\n1. **Fixed radius (1), varying the number of layers**  \n2. **Fixed number of layers (3), varying the neighborhood radius**\n\nThe results on the LR-EXP dataset are reported below.\n\n**(1) Fixed Radius = 1**\n\n| # Layers | NCN     | NeoGNN     | ELPH     | SEAL     |\n|----------|---------|------------|----------|----------|\n| 1        | 74 ± 1  | 42 ± 4     | 40 ± 4   | 79 ± 3   |\n| 2        | 75 ± 1  | 42 ± 4     | 55 ± 4   | 89 ± 1   |\n| 3        | 75 ± 1  | 45 ± 3     | 62 ± 2   | 89 ± 2   |\n\n**(2) Fixed # Layers = 3**\n\n| Radius | NCN     | NeoGNN     | ELPH     | SEAL     |\n|--------|---------|------------|----------|----------|\n| 1      | 75 ± 1  | 45 ± 3     | 62 ± 2   | 89 ± 2   |\n| 2      | —       | 63 ± 3     | 61 ± 4   | 90 ± 3   |\n| 3      | —       | 75 ± 2     | 62 ± 7   | 97 ± 0   |\n\n> Note: For NCN, the radius is fixed by design to 1 and cannot be increased.\n\nThese results are fully consistent with Theorem 3.2 (Point 2):  \n- When fixing the radius, increasing the number of layers improves expressiveness in all the models.  \n- When fixing the number of layers, increasing the radius also improves expressiveness in all the models.\n\n[1] Oono, Kenta, and Taiji Suzuki. Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. ICLR 2020.\n\n---\n\n**Q1: Can the framework be extended to non-MP models like GNN transformers?**  \n\nThe current version of the framework is specifically designed to model message-passing based link representation methods, and does not extend to non-MP architectures such as GNN transformers.\n\nThis focus is intentional: MP models are the foundation of most existing theoretical work in graph learning, and their expressiveness in the context of link representation is still not fully understood. Just as MP GNNs served as the basis for early expressiveness studies in node and graph classification, later extended to more complex architectures like transformers, we believe that starting from MP models is a necessary and meaningful first step.\n\nAs stated in the Limitations section (Section 6), extending the framework to account for transformer-based or attention-based architectures is a valuable direction for future research, and we thank the reviewer for highlighting this point.\n\n---\n\n**Q2: What is the best trade-off between the number of GNN layers and neighborhood size?**  \n\nWe would like to clarify that we do not claim the existence of a trade-off between the number of GNN layers and the neighborhood radius. In fact, according to Theorem 3.2, increasing **both** the number of layers and the neighborhood radius leads to higher expressiveness for message-passing models in link representation.\n\nIf a trade-off exists, it is not between these two parameters, but rather between **expressiveness and computational cost**. Our framework allows us to reason about this trade-off more precisely. Specifically, it suggests that:\n\n1. There is no need to go beyond 1-WL expressivity in the base GNN, as increasing base expressiveness adds cost without increasing expressiveness in pair-wise representation (Theorem 3.2 point 1).\n2. It is more efficient to use node representations computed with message passing layers, in a smaller neighborhood, rather than using weaker node features (like simple structural counts) over a larger neighborhood (Theorem 3.2 point 2).\n\n---\n\n**Q3: Can you propose new methods based on the insight in this paper?**  \n\nTheorem 3.2 provides insights for designing expressive and efficient link prediction models, specifically, by using node representations computed via 1-WL message passing over a limited-radius neighborhood and a suitable number of layers. \n\nAdditionally, the symmetry metric helps guide **model selection**: on datasets with low structural symmetry, simple pure GNNs already suffice, avoiding unnecessary complexity and low generalization ability. On highly symmetric datasets, more expressive models are worth the added computational cost, as they can significantly improve performance."}, {"review_id": "Nf4yBtohZZ", "reviewer": "Reviewer_qEnu", "summary": "Graph neural networks have been enjoyed significant use in modeling graph structured data for tasks such as graph classification, node classification, and link prediction. Over the years, there are many different GNN architectures that have been introduced for these three diverse tasks; and the community has come to understand the representational capacity, or expressive power, of these models by characterizing the shape of data that they can learn to represent. In the case of graph and node classification, the traditional route to do this is through an appeal to the Weisfeiler Lehman graph isomorphism test. This has led the community to develop ever-more expressive models that, and ultimately, the \"solving\" of many significant graph benchmarks in the field. Link prediction has been comparatively less studied -- the automorphic node problem has been identified, and addressing it directly has led to techniques such as labeling tricks or models such as BUDDY/ELPH, and expressivity has been explored on a case-by-case basis. What has been missing in the literature is a hierarchy of link-level representations, which would allow the field to contextualize their models more completely, but to also begin to characterize the design principles going forward. The authors seek to address this task directly. They do so by introducing a unifying expressiveness framework and place existing models within it. They validate this new definition of expressivity in synthetic graphs generated with high degrees of symmetry, and verify the expressiveness gains. Ultimately, however, they observe that despite the significant improvements in expressivity, the gains on benchmark datasets are rather modest. The authors work ultimately raises more questions than it answers, but in doing so arms the field a new set of tools to answer these questions.", "questions": "1. The static link prediction problem is often a relatively contrived version of the industrial problem, because in industrial settings the graph is dynamic. Have you given any thought to how this work might extend to the dynamic link representation problem?\n2. While many graphs are undirected (eg, the FB Friendship graph); many graphs _are_ directed (eg, a financial transaction graph). How would you extend this work to directed settings? Or are directed real-world graphs usually so lacking in symmetry that the link-level representations are easier to distinguish?\n3. Could you share more about the intuition behind the loss? I suppose I would have expected to see a margin term\n4. Have you tried to make a model like SAGE more expressive in your framework? You could do this for example by adding in DRNL features, positional encodings, and/or structural features (eg common neighbor counts). It would be highly interesting to me to see the performance of a simple model like SAGE as a function of expressivity improvements.\n5. In Srinivasan et al [1], they show in remark 2 that graphsage provides node embeddings rather than structural representations due to the random walks. It seems to me like that would lead to SAGE potentially outperforming GCN on LR-EXP. How did you train SAGE? Did you sample the neighborhoods? How do you think about squaring this with your expressiveness hierarchy?\n6. How well does the approximation in eq 12 agree with 11?\n7. How sensitive are the results to the choice of α in the reliability check? Characterizing this would be helpful.\n\n[1] https://arxiv.org/pdf/1910.00452", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. The work is well motivated and addresses a significant problem in the space.\n2. The work is well written and presented. There are no significant typos, and is relatively easy to follow despite the mathematically intricate nature of the work.\n3. LR-EXP is a well constructed, albeit small, synthetic playground that provides meaningful information about performance of these models.\n4. Theorem 3.2 is succinct and yet intuitive.\n5. The synthetic experiments clearly display the ordering yielded by theorem 3.2, indicating that the theoretical framework is valid.\n6. The experiments presented in Table 3 tell a relatively clear story that further justifies the theoretical framework.\n\n**Weaknesses**\n1. Minor typo -- in Table 3 some of the entries use a comma instead of a period.\n2. The authors do not make much contact with previous link-representation expressivity results such as Srinivasan et al.\n3. The authors do not spend much time explaining _why_ the symmetry definition given in eq 11 (or 12) would meaningfully impact the real-world expressivity of the models. I know that this isn't the usual way to consider this task, but it would be interesting to understand the required expressivity for a given task/dataset in terms of the available automorphisms in the graph at hand.\n4. The gap between synthetic performance differences and real-world gains could be explored more deeply", "was_revised": true, "final_justification": "The work is technically valuable and provides important insights into the field of link prediction. I feel as if the paper is a clear accept, and this is only more true given the answers provided in the rebuttal.", "rebuttal": "**We would like to thank the reviewer for the thoughtful comments and useful suggestions.**\n\n---\n\n**W1: Minor typo -- in Table 3 some of the entries use a comma instead of a period.**  \n\nWe apologize for the formatting error, we will correct the table to use consistent notation.\n\n---\n\n**W2: The authors do not make much contact with Srinivasan et al.**  \n\nWe fully agree that Srinivasan et al. provide a foundational result: they show that structural node representations produced by standard GNNs are not sufficient for link prediction, as link-level tasks require joint structural representations. This insight has led to a growing body of work on message-passing models that aim to overcome this limitation, often by incorporating joint structural features into the link representation.  \nHowever, despite this growing literature, there is currently no unified framework for systematically analyzing and comparing the expressiveness of these models. This is precisely the gap our work aims to fill.  \nOur main contribution is to introduce a general framework that subsumes all MP-based link representation models — from standard GNNs to more expressive models that use joint structural information. The framework allows these methods to be described using a common formal scheme, making it possible to compare their expressiveness in a principled way. We will clarify this connection to Srinivasan et al. more explicitly in the revised version of the paper.\n\n---\n\n**W3: Why the symmetry definition given in eq 11 (or 12) would meaningfully impact the real-world expressivity of the models.**  \n\nThe symmetry metric directly reflects the amount of available automorphisms in the graph. When the symmetry is low, the graph structure is irregular, and standard GNNs are unlikely to fail, since structurally different links are more easily distinguishable. In contrast, high symmetry increases the chance of presence of structurally different links with identical representations given by standard GNNs.  \nThis is exactly what we observe in Table 3: on real-world datasets with low symmetry, standard GNNs perform well; on highly symmetric datasets, they fail to rank among the top-performing methods. We will clarify this connection more explicitly in the paper.\n\n---\n\n**W4: The gap between synthetic performance differences and real-world gains could be explored more deeply**  \n\nThe synthetic dataset was intentionally designed to stress-test the expressiveness of the models, by including links that are particularly challenging to be distinguished by standard GNNs. This design amplifies the gap between expressive models (those using joint structural features) and standard GNNs.\n\nIn real-world datasets, such extreme cases are less common, and high-symmetry patterns are harder to find. This is precisely what we show in our real-data experiments: expressive models still tend to perform better, but the gap is smaller – reflecting the lower frequency of hard-to-distinguish links in practice.\n\nOverall, our results confirm that expressiveness matters most when symmetry is present, and that the synthetic and real-world results are aligned in that regard.\n\n---\n\n**Q1: Have you given any thought to how this work might extend to the dynamic link representation problem?**  \n\nOur framework can be extended to the temporal link prediction setting by including the time variable $t $ as an explicit argument of the functions $\\phi, \\rho, h$ within the framework. This would allow the framework to cover temporal GNNs operating on both snapshot-based and event-based dynamic graphs [1].\n\nA particularly interesting direction would be to extend the analysis in [2] to the temporal link prediction setting and use our framework to investigate the expressiveness of time-then-graph and time-and-graph architectures in the temporal link prediction task. We see this as a promising line of future work. \n\n[1] Longa, Antonio, et al. \"Graph Neural Networks for Temporal Graphs: State of the Art, Open Challenges, and Opportunities.\" Transactions on Machine Learning Research.  \n[2] Gao, Jianfei, and Bruno Ribeiro. \"On the equivalence between temporal and static equivariant graph representations.\" International Conference on Machine Learning. PMLR, 2022.\n\n---\n\n**Q2: How would you extend this work to directed settings?**  \n\nOur framework could be quite easily generalized to directed graphs by redefining the functions $h $ and $\\psi $ to operate over ordered node pairs $(u, v) $, rather than treating the two nodes separately. \n\n---\n\n**Q3: Could you share more about the intuition behind the loss? I suppose I would have expected to see a margin term**  \n\nWe agree that contrastive loss functions are often defined with an explicit margin term $\\gamma $, which controls the degree of dissimilarity enforced between negative pairs. In our case, the goal is to fully minimize similarity between representations of non-automorphic links. Following the approach in [3], we deliberately adopted a zero-margin formulation to push the model toward maximal dissimilarity between such pairs. This choice aligns with our objective of measuring and testing expressiveness, where even small overlaps in representation between structurally different links would be undesirable.\n\nWe will clarify this design choice in the revised paper.  \n\n[3] Wang, Yanbo, and Muhan Zhang. \"An Empirical Study of Realized GNN Expressiveness.\" Forty-first International Conference on Machine Learning.\n\n---\n\n**Q4-Q5: Expressiveness of SAGE**  \n\nWe thank the reviewer for pointing this out. In our original implementation of GraphSAGE, we did not include neighborhood sampling, rather we used a deterministic aggregation over all neighbors. Following your observation and Remark 2 in Srinivasan et al., we re-ran the experiments using stochastic neighbor sampling. As expected, GraphSAGE now achieves an accuracy of 8.2 ± 3.5, outperforming GCN. We will include this updated result in the paper, along with an explicit reference to the theoretical motivation included in Srinivasan et al.\n\n---\n\n**Q6: How well does the approximation in eq 12 agree with 11?**  \nThe approximation in Equation 12 reflects how closely the WL-induced partition (used in Equation 11) matches the true orbit partition. Although there is no complete characterization of WL failures in distinguishing nodes from different orbits, it is said that WL gives different representations to **almost all** nodes that belong to different orbits [4].\n\nA practical example is presented in [5], where the authors explicitly compare WL partitions and orbit partitions on the Alchemy dataset [6]. Out of 202,579 graphs, only in 4 graphs the partition of the nodes induced by the WL is different wrt the orbits, highlighting that the WL approximation is extremely close in practice.\n\nWe will clarify this point further in the final version of the paper.\n\n[4] Babai, László, and Ludik Kucera. \"Canonical labelling of graphs in linear average time.\" 20th annual symposium on foundations of computer science (sfcs 1979). IEEE, 1979.  \n[5] Morris, Matthew, Bernardo Cuenca Grau, and Ian Horrocks. \"Orbit-Equivariant Graph Neural Networks.\" The Twelfth International Conference on Learning Representations.  \n[6] Chen, Guangyong, et al. \"Alchemy: A quantum chemistry dataset for benchmarking ai models.\" arXiv preprint arXiv:1906.09427 (2019).\n\n---\n\n**Q7: How sensitive are the results to the choice of α in the reliability check? Characterizing this would be helpful.**  \n\nWe tested the sensitivity of our results to the choice of the significance level in the reliability check. Specifically, we experimented with three commonly used values in statistical testing, i.e., $\\{0.1,\\ 0.05,\\ 0.01\\} $. The resulting performance on LR-EXP are reported below.\n\nAs expected, all standard GNN models consistently fail to recognize any links, regardless of the significance level. Among the more expressive models, the majority show stable behavior across different values of significance, with fluctuations that remain within the standard deviation. BUDDY and NCN exhibit slightly larger fluctuations in absolute value, but the key point for this experiment is the expressiveness ranking across models. This ranking remains robust across all significance levels, with one minor exception: at significance level 0.1, Neo-GNN slightly surpasses NCN. However, this difference falls within the standard deviation range.\n\n|Model| 0.1|0.05|0.01|\n|--------|-----------|-----------|-----------|\n|GCN|0 ± 0|0 ± 0|0 ± 0|\n|GAT|0 ± 0|0 ± 0|0 ± 0|\n|GAE|0 ± 0|0 ± 0|0 ± 0|\n|SAGE|11 ± 0|8 ± 4|3 ± 0|\n| BUDDY|54 ± 5| 45 ± 1    | 59 ± 1    |\n| ELPH|61 ± 1|62 ± 7|62 ± 1|\n| NeoGNN | 76 ± 6|75 ± 2| 71 ± 2    |\n| NCN| 70 ± 1 |75 ± 1|81 ± 1 |\n| SEAL| 92 ± 0|97 ± 0| 97 ± 0 |\n\nWe also note that the lack of a strictly monotonic trend in the number of reliably distinguished links when decreasing the significance level $\\alpha$ is due to the **two-part structure** of our statistical test. Specifically, it combines:\n\n1. The **Major Procedure**, which tests whether a model can distinguish between two *non-automorphic* links (i.e., tests if their representations differ significantly);\n2. The **Reliability Check**, which ensures that the same model assigns *equal* representations to *automorphic* links (i.e., avoids false positives due to internal fluctuation).\n\nFor each pair of non-automorphic links, we compute a threshold $\\tau $, and accept the distinction only if the test statistic $T^2_{\\text{major}} > \\tau $ **and** the corresponding statistic for automorphic links $T^2_{\\text{check}} < \\tau $. This means that when $\\alpha$ increases, some previously rejected distinctions may now pass the Major Procedure (leading to more links being distinguished), but at the same time, the Reliability Check may fail for others (causing fewer to pass the overall test). These two effects may balance out or interfere with each other, explaining why no simple monotonic pattern emerges in the results."}, {"review_id": "bNhgJEU73u", "reviewer": "Reviewer_mA2W", "summary": "This study presents a systematic study of the expressive power of MPNNs (message-passing type of GNNs) when they are used to generate link-level features. The authors proposes a formal framework that characterises any link representation model by the WL strength of the endpoint encoder $\\phi$, the neighborhood encoder $\\rho$ and the radius of neighborhood. Under this framework, they prove a partial order over several SOTA link predictors and obtain theorems. Beyond the theorectical foundation, they propsoe LR-EXP, a synthetic benchmark containing pairs of non-automorphic links whose endpoints are automorphic, and they introduce a symmetry score that approximates the density of node orbits in a real graph. Experiments confirm the predicted hierarchy on both LR-EXP and several real benchmarks, showing that SEAL is in practice and in theory the highly expressive models.", "questions": "1. In Section 3 the assumption of Thm 3.2 relies on COMB being injective under certain condition. Many practical implementations concatenate and then feed an MLP; is this always injective in training (for instance Neo-GNN), and if not, how sensitive are the conclusions?", "limitations": "See the question above, and It would also be helpful for authors to discuss societal impact (if any) of their work.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The study looks into an important and open problem—how to compare link-level expressiveness—using rigorous definitions and proofs. The formalism in the study is compact yet flexible enough to encode every mainstream message-passing link predictor, which makes the hierarchy both transparent and extensible.\n\n2. Theorem 3.2 clearly exposes why using only endpoint embeddings is fundamentally limited, and why trading neighbourhood size for depth or higher-order WL power can be more efficient. \n\n3. The synthetic benchmark LR-EXP is well-motivated. By forcing the endpoints of each test pair to share WL colours, the benchmark show that the empirical relationship between the symmetry score and test performance and it is convincing and offers a useful rule of thumb for practitioners when building GNN4LP.\n\nWeakness\n\n1. The framework is only restricted to message-passing designs. Graph transformer-based link predictors, line-graph methods such as LGLP and classical proximity indices like Katz Index are only discussed qualitatively; their formal place in the hierarchy therefore remains unclear.\n2. In Section 4 the LR-EXP graphs contain at most seventeen nodes (Erdos–Rényi graph); while size is not essential to the expressiveness argument, I wonders whether the training protocol and Reliable Paired Comparison evaluation would remain tractable on larger graphs with rich attributes.\n3. The real-world study focuses on ranking metrics like Hits@50, MRR. But the computational cost of the most expressive models (especially SEAL’s sub-graph extraction) is not reported; this is crucial for users balancing accuracy against throughput.", "was_revised": true, "final_justification": "I maintain my original score of Accept.", "rebuttal": "**We would like to thank the reviewer for the thoughtful comments and useful suggestions.**\n\n---\n\n\n**W1: The framework is only restricted to message-passing designs.**  \n\nWe agree that many effective link prediction methods go beyond message-passing, including transformer-based models and heuristic methods. However, our focus is intentional: understanding the expressiveness of MP-based link representations is a necessary first step, just as MP models have been the starting point for theoretical analysis in graph-level tasks. These foundational studies have later inspired and supported the development of more powerful models such as graph transformers.\nWe believe that the same applies to link representation: MP models are still not fully understood in this context, and our framework provides the first steps toward filling that gap. As we state in the paper, in the Limitations section (Section 6), extending the framework to encompass transformer-based architectures is our intention for future work.\n\n---\n\n**W2: Do training protocol and Reliable Paired Comparison evaluation would remain tractable on larger graphs with rich attributes?**  \n\nOur training protocol uses a Siamese architecture where both branches share the same weights and apply the link representation model under evaluation. As a result, the computational cost of training is essentially the same as training the base model itself. Our framework does not introduce any additional significant overhead; the scalability depends entirely on the model being tested.\n\nThe same applies to the Reliable Paired Comparison evaluation. After training, inference is performed on isomorphic copies of the original graph. These copies are generated with linear complexity in the graph size ($\\mathcal{O}(|V| + |E|) $), and the inference time again depends only on the model used.\n\nIn short, the scalability of our approach on larger graphs depends solely on the scalability of the link representation models being evaluated, not on the protocol itself.  \n\n---\n\n**W3: Missing computational cost of the most expressive models**  \n\nWe agree that computational cost is an important factor when evaluating expressive models. Below, we report the time complexity of the methods considered in our paper, as presented in [1]. The overall time complexity for link prediction is $\\mathcal{O}(B + Ct) $, where t is the number of links to be predicted and the terms $B $ (preprocessing) and $C $ (per-link cost) are summarized below:\n\n| Method   | B                                 | C                               |\n|----------|-----------------------------------|---------------------------------|\n| GAE      | $ndf + nf^2$                       | $f^2$                            |\n| Neo-GNN  | $ndf + nf^2 + nd^{\\ell}$               | $d^{\\ell}+ f^2$                      |\n| BUDDY    | $ndf + nh$                       | $h + f^2$                       |\n| SEAL     | $0$                               | $d^{(\\ell+1)}f + d^{\\ell}f^2$           |\n| NCN      | $ndf + nf^2$                       | $df + f^2$                       |\n| NCNC     | $ndf + nf^2$                       | $d^2f + df^2$                     |\n\nwith: \n- $n $: number of nodes in the graph  \n- $d $: maximum node degree  \n- $f $: feature dimension  \n- $h$: complexity of the hash function used in BUDDY  \n- $\\ell $: neighborhood radius\n\nAmong these, **SEAL** is the most expressive but also the most computationally expensive, due to its exponential dependence on the neighborhood radius $\\ell$. **NCN** and **BUDDY** provide the best trade-off between expressiveness and computational cost. **Neo-GNN**, while more expensive than NCN, is in fact less expressive. **GAE** is the least costly, but also the least expressive.\n\nWe will include this analysis in the final version of the paper. \n\n[1] Wang, Xiyuan, Haotong Yang, and Muhan Zhang. \"Neural Common Neighbor with Completion for Link Prediction.\" The Twelfth International Conference on Learning Representations.\n\n---\n\n**Q1: the assumption of Thm 3.2 relies on COMB being injective under certain condition. Many practical implementations concatenate and then feed an MLP; is this always injective in training (for instance Neo-GNN), and if not, how sensitive are the conclusions**  \n\nWe would like to clarify that the `COMB` function referenced in Theorem 3.2 specifically corresponds to the one defined in our Definition 3.1, that is, the function that combines the link endpoints’ representations with the representation of the neighborhood around the two nodes involved in the link. This should not be confused with the more general \"combine\" operations used inside GNN layers.\n\nAs shown in Table 1 of the paper, all existing SOTA models (including Neo-GNN) implement the `COMB` function of Definition 3.1 as a simple concatenation, without any MLP. Since concatenation is inherently injective, the assumption in Theorem 3.2 holds for these models.\n\nIf one implements `COMB` using both concatenation and an MLP, injectivity is no longer guaranteed. Since injectivity of `COMB` is an assumption of Theorem 3.2, if that assumption does not hold, the expressiveness guarantees derived from the theorem may no longer apply."}, {"review_id": "HkP39ZI8MY", "reviewer": "Reviewer_i6RA", "summary": "This paper studies the expressiveness hierarchy of the link prediction models. Beyond previous k-WL test that focuses on node-level expressiveness, this work establishes a hierarchy that can describes the level of expressiveness for recent SOTA link prediction models. By introducing a framwork, this paper unifies common link prediction methods so that their expressiveness can be compared directly under this framework. Then the study introduces a synthetic benchmark, specifically designed to test the link-level expressiveness for link prediction models. Several interesting observations have been made on both the synthetic benchmark and the real-world datasets.", "questions": "1. When defining the neighborhood of a node $N^m(v)$, the paper defines as $m$-far away from $v$. How is the distance metric defined here? Is shortest-path or \"number-of-steps\" distance employed here?\n\n2. When computing the symmetric metrics, is the node feature considered or only the graph structure? If the node feature is considered, how is the WL-test approximation applied to assign the inital colors?", "limitations": "See weakness.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n[S1] The expressiveness hierarchy of link-level representation by GNNs is an open question in the field. The paper provides a unfied framework to include common link predictors and can depict their expressiveness under this framework. This study provides a good insight of how/why the GNN4LP, especially those with SF, performs well on current benchmark.\n\n[S2] The observations made in experimental sections are interesting. The empirical results on synthetic graphs well align with the theorectical conclusions. Besides, the results on real-world graphs shows the distinct strengths of different link predictors.\n\nWeakness:\n\n[W1] The proposed framework only works for GNNs, especially the message-passing types. There are many other link prediction methods without message-passing but performs well. For instance, graph transformer, LGLP[1], network embedding methods and typical heuristic methods like Common Neighbor families, Katz Index, Page Rank Index are not discussed in the paper. \n\n[W2] The notation should be consistent. For example in Definition 3.1, $h(u, v, G, X^0)$ does not include the graph structure $G$ in equation (7).\n\n[1]  Cai, Lei, et al. \"Line graph neural networks for link prediction.\"", "was_revised": true, "final_justification": "My questions and concerns were fully addressed. Therefore, I update my score towards accept.", "rebuttal": "**We would like to thank the reviewer for the thoughtful comments and useful suggestions.**\n\n---\n\n**W1: The proposed framework only works for GNNs**  \n\nWe agree that many effective link prediction methods go beyond message-passing, including transformer-based models and heuristic methods. However, our focus is intentional: understanding the expressiveness of MP-based link representations is a necessary first step, just as MP models have been the starting point for theoretical analysis in graph-level tasks. These foundational studies have later inspired and supported the development of more powerful models such as graph transformers.\n\nWe believe that the same applies to link representation: MP models are still not fully understood in this context, and our framework provides the first steps toward filling that gap. As we state in the paper, in the Limitations section (Section 6), extending the framework to encompass transformer-based architectures is our intention for future work.\n\n---\n\n**W2: The notation should be consistent. For example in Definition 3.1 h does not include the graph structure in equation (7).**  \n\nFor ease of readability, we have omitted the graph $G $ as an explicit argument in message-passing and link-representation functions, assuming it is implicitly defined as the underlying structure on which these functions operate. We have specified it in line 159-161 of the paper. To maintain the consistency, we will follow this notation throughout the paper starting from line 159. \n\n---\n\n\n**Q1: When defining the neighborhood of a node $N^m(v) $  the paper defines as m-far away from $v $. How is the distance metric defined here?**  \n\nWe thank the reviewer for the question. We would like to clarify that in Definition 2.2 we do not define a distance metric between nodes. Specifically, we do not assign a single distance value (e.g., shortest-path distance) between two nodes.\n\nInstead, we define the $ \\mathcal{N}^m(v) $ neighborhood of a node $ v $ as the set of all nodes that are connected to $ v $ by a path of length $m $. Therefore, a node $ u $ may appear in multiple neighborhoods $ \\mathcal{N}^m(v) $ for different values of $m $, whenever there exist multiple paths of different lengths $m$ connecting $u $ and $ v $.\n\nWe will clarify this point in the paper by expanding the explanation following Definition 2.2.\n\n---\n\n**Q2: When computing the symmetric metrics, is the node feature considered or only the graph structure? If the node feature is considered, how is the WL-test approximation applied to assign the initial colors?**  \n\nYes, node features are considered when computing the symmetry metric. We initialize the node colors based on the input features using an injective mapping from the feature space to the color space. In particular, we define each node’s initial color as:  \n  \n$c_v^0 = {HASH}(x_v) $\n\nwhere $x_v \\in \\mathbb{R}^f $ is the feature vector of node $v $, and `HASH` is an injective function mapping the features to unique colors.\n\nThis initialization corresponds to iteration 0 of the WL test. From that point on, standard WL refinement proceeds, updating each node’s color based on its own color and the multiset of its neighbors’ colors. We will make this formalism explicit in the final version of the paper."}]

Author rebuttal:

Meta-review: This paper makes a substantive contribution by shifting expressiveness analysis to link representations, unifying mainstream message-passing link models, deriving a clear expressiveness hierarchy, and providing actionable design guidance. Theoretical results are precise, and the LR-EXP suite plus symmetry metric effectively link theory to practice. Reviewers praised clarity and impact; rebuttal experiments addressed concerns on scope, ablations, and empirical grounding, leading to score increases. Remaining issues are minor and easily fixed. Overall, this is a clear, well-supported, and impactful contribution deserving strong acceptance.
Decision: Accept (spotlight)