Pure Message Passing Can Estimate Common Neighbor for Link Prediction
Authors: Kaiwen Dong
Zhichun Guo
Nitesh V Chawla
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Neural Networks
Link Prediction
Primary area: graph_neural_networks
TL;DR: We demonstrate that node-level message passing can effectively capture link-level structural features, such as Common Neighbor, for link prediction.

Abstract: Message Passing Neural Networks (MPNNs) have emerged as the {\em de facto} standard in graph representation learning. However, when it comes to link prediction, they are not always superior to simple heuristics such as Common Neighbor (CN). This discrepancy stems from a fundamental limitation: while MPNNs excel in node-level representation, they stumble with encoding the joint structural features essential to link prediction, like CN. To bridge this gap, we posit that, by harnessing the orthogonality of input vectors, pure message-passing can indeed capture joint structural features. Specifically, we study the proficiency of MPNNs in approximating CN heuristics. Based on our findings, we introduce the Message Passing Link Predictor (MPLP), a novel link prediction model. MPLP taps into quasi-orthogonal vectors to estimate link-level structural features, all while preserving the node-level complexities. We conduct experiments on benchmark datasets from various domains, where our method consistently outperforms the baseline methods, establishing new state-of-the-arts.

Pure Message Passing Can Estimate Common Neighbor for Link Prediction
Kaiwen Dong Zhichun Guo Nitesh V. Chawla
CComputer Science and Engineering, University of Notre Dame Lucy Family Institute for Data and Society, University of Notre Dame [kdong2, zguo5, nchawla)@nd.cr edu
Abstract
Message Passing Neural Networks (MPNNs) have emerged as the de facto standard in graph representation learning. However, when it comes to link prediction, they are not always superior to simple heuristics such Common Neighbor (CN). This discrepancy stems from a fundamental limitation: while MPNNs excel node-level representation, they stumble with encoding the joint structural features essential to link prediction, like CN. To bridge this gap. we posit that, by harnessing the orthogonality of input vectors, pure message- passsigganngggggg can indeed capture joint structural features. Specifically, we study the proficiency of MPNNs in approxi- mating CN heuristics. Based on our findings, we introduce the Message Passing Link Predictor (MPLP), a novel link prediction model. MPLP taps into quasi- orthogonal vectors estimate link-level structural features, all while preserving the node-level complexities. We conduct experiments on benchmark datasets from various domains, where our method consistently outperforms the baseline methods, establishing new state-of-the-arts.
Introduction
Link prediction is a cornerstone task in the field of graph machine learning, with broad-ranging implications across numerous industrial applications. From identifying potential new acquaintances on social networks [ to predicting protein interactions (2), from enhancing recommendation
systems completing knowledge graphs 4. the impact of link prediction is felt across diverse domains. Recently, with the advent of Graph Neural Networks (GNNs) 5 and more specifically, Message-Passing Neural Networks (MPNNs) (6), these models have become the primary tools for tackling link prediction tasks. Despite the resounding success of MPNNs in the realm of node and graph classification tasks (5) 7. it is intriguing to note that their performance in link prediction does not always surpass that of simpler heuristic methods [10].
Zhang al. [1 highlights the limitations of GNNs/MPNNs for link prediction tasks arising from its intrinsic property permutation invariance. Owing to this property, isomorphic nodes invariably receive identical representations. This poses challenge when attempting distinguish links whose endpoints are isomorphic nodes. As illustrated in Figure Ta nodes en and U3 share a Common Neighbor 02, while nodes ei and vis do not. Ideally, due to their disparate local structures, these two links (U1, 03) and (V1, U5) should receive distinct predictions. However, the permutation invariance of MPNNs results in identical representations for nodes 23 and vs. leading identical predictions for the two links. As Zhang et al. [11] asserts, such node-level representation, even with the most expressive MPNNs, cannot capture structural link representation such Common Neighbors (CN), a critical aspect of link prediction.
In this work, posit that the pure Message Passing paradigm 6 can indeed capture structural link representation by exploiting orthogonality within the vector space. We begin by presenting a
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

03
V1
V/5
1/2
2/4
4/4
06
Message Passing
Message Passing
Message Passing
98
CN) =1
CN(11, vo) = 0
(a)
(b)
Figure I: (a) Isomorphic nodes result identical MPNN node representation, making it impossible to distinguish links such as (V1, va) and (V1, 15) based these representations. (b) MPNN counts Common Neighbor through the inner product of neighboring nodes' one-hot representation.
motivating example, considering a non-attributed graph as depicted in Figure a In order to fulfill
the Message Passing's requirement for node vectors as input, we assign one-hot vector each node v4 such that the i-th dimension has a value of one, with the rest set to zero. These vectors, viewed signatures rather than mere conmuutationiivariian node representations, relationships, Subsequently, we execute a single iteration of message passing as shown in Figure [bb updating each node's vector by summing the vector of its neighbors. This process enables us to compute CN for any node pair by taking the inner product of the vectors of the two target nodes.
illuminate pairwise
At its core, this naive method employs orthonormal basis as the node signatures, thereby ensur- ing that the inner product of distinct nodes' signatures is consistently zero. While this approach effectively computes CN, its scalability poses significant challenge, given that its space complexity quadratically proportional to the size of the graph. To overcome this, we draw inspiration from the premise that the family of vectors almost orthogonal to each other swells exponentially, even with just linearly scaled dimensions [3]. Instead of relying on the orthogonal basis, we can propagate these quasi-orthogonal (QO) vectors and utilize the inner product to estimate the joint structural information of any node pair.
DotHash [12] and capitalize
In sum, our paper presents several pioneering advances in the realm of GNNs for link prediction:
We are the first, both empirically and theoretically, to delve into the proficiency of GNNs in approximating heuristic predictors like CN for link prediction. This uncovers previously uncharted territory in GNN research.
Drawing upon the insights gleaned from GNNs' capabilities in counting CN, we introduce MPLP, novel link prediction model. Uniquely, MPLP discerns joint structures of links and their associated substructures within graph, setting new paradigm in the field.
Our empirical investigations provide compelling evidence of MPLP's dominance. Bench- mark tests reveal that MPLP not only holds its own but outstrips state-of-the-ane models in link prediction performance.
2 Preliminaries and Related Work
Notations. Consider an undirected graph G = (V,E,,,, where V represents the set of nodes with cardinality n, indexed as {1...., n). E C V x V denotes the observed set of edges, and X,, E F. encapsulates the attributes associated with node i. Additionally, let A,, signify the neighborhood of a node v, that is Nr, = (u]SPD((,, v) = 1} where the function SPD(..)) measures the shortest path nodes. Furthermore, the node degree of is given by d, [.g To generalize,
distance between we introduce the shortest path neighborhood, A2, representing the set of nodes that are hops away from node v, defined No (uD((u, v) = s).
Link predictions. Alongside the observed set of edges E, there exists an unobserved set of edges, which we denote as F. C x V E. This unobserved set encompasses edges that are either absent from the original observation anticipated to materialize in the future within the graph G.

---

102
CN
MSE
100
10
AA
MSE
10-1
RA
MSE
10-1
10
C.ele
USAir
E.coli
Yeast
PB
NS
Power
Router
Figure 2: GNNs estimate CN, AA and RA via MSE regression, using the mean value Baseline.
Lower values are better.
Consequently, we formulate the link prediction task discerning the unobserved set of edges Ee. Heuristics link predictors include Common Neighbor (CN) [I]. Adamic-Ada index (AA) [14), and Resource Allocation (RA) [IS]. CN is simply counting the cardinality of the common neighbors, while AA and RA count them weighted to reflect their relative importance as a common neighbor.
CN(u, u)
Σ
1; AA(u,)) = E
RA(u,v)
Σ
(1)
K.N. log dR
d2
REN.TAE
KEN. N.N.
Though heuristic link predictors are effective across various graph domains, their growing computa- tional demands clash with the need for low latency. To mitigate this, approaches like ELPH [16) and DotHash [12] propose using estimations rather than exact calculations for these predictors. Our study, inspired by these works, seeks to further refine techniques for efficient link predictions. A detailed comparison with related works and our method is in Appendix
GNNs for link prediction. The advent graphs incorporating node attributes has caused significant shift in research focus toward methods grounded in GNNs. Most practical GNNs follow the paradigm of the Message Passing [6]. can be formulated as:
( AGGREGATE (nh h. A.9.Y Vu E. E..)).
((+1) UPDATE ((h(),m!)) mm!))
(2)
where hr represents the vector of node layer and h X o... For simplicity, we use h, to represent the node vector at the last layer. The specific choice of the neighborhood aggregation function, AGGREGATE(()) and updating function, UPDATE(-), dictates instantiation of GNN model, with different choices leading to variations of model architectures. In the context of link prediction tasks, the GAE model [17] derives link representation, hii,j). as a Hadamard product of the target node pair representations, (( h; h2. Despite its seminal approach, the SEAL model [18], which labels nodes based on proximity to target links and then performs message-passingg for each target link, is hindered by computational expense, limiting its scalability. Efficient alternatives like ELPH (16) estimate node labels, while NCNC [19] directly learns edgewise features by aggregating node representations of common neighbors.
3 Can Message Passing count Common Neighbor?
In this section, we delve deep into the potential of MPNNs for heuristic link predictor estimation. We commence with empirical evaluation to recognize the proficiency of MPNNs in approximating link predictors. Following this, we unravel the intrinsic characteristics of 1-layer MPNNs, shedding light on their propensity unbiased alternative. Ultimately, we cast light on how successive rounds of message passing can estimate the number of walks connecting target node pair with other nodes in the graph. All proofs are provided in Appendix G
biased estimators for heuristic link predictors and proposing an
3.1 Estimation via Mean Squared Error Regression
To explore the capacity MPNNs capturing the overlap information inherent in heuristic link predictors, such as CN, AA and RA, we conduct an empirical investigation, adopting the GAB

---

framework [[7] with GCN [5] and SAGE 7 as representative encoders. SEAL [8], known for its proven proficiency in capturing heuristic link predictors, serves as a benchmark in our comparison. Additionally, we select a non-informative baseline estimation, simply using the mean of the heuristic link predictors on the training sets. The datasets comprise eight non-attributed graphs (more details in Section 55. Given that GNN encoders require node features for initial representation, we have to generate such features for our non-attributed graphs. We achieved this by sampling from high- dimensional Gaussian distribution with a mean of 0 and standard deviation of 1. Although one-hot encoding is frequently employed for feature initialization on non-attributed graphs, we choose to forgo this approach due to the associated time and space complexity.
To evaluate the ability of GNNs to estimate CN information, we adopt a training procedure analogous to conventional link prediction task. However, we reframe the task as regression problem aimed at predicting heuristic link predictors, rather than a binary classification problem predicting link existence. This shift requires changing the objective function from cross-entropy to Mean Squared Error (MSE). Such an approach allows us to directly observe GNNs' capacity to approximate heuristic link predictors.
Our experimental findings, depicted in Figure 2 reveal that GCN and SAGE both display an ability to estimate heuristic link predictors, albeit to varying degrees, in contrast to the non-informative baseline estimation. More specifically, GCN demonstrates a pronounced aptitude for estimating RA and nearly matches the performance of SEAL on datasets such as C.ele. Yeast, and PB. Nonetheless, both GCN and SAGE substantially lag behind SEAL in approximating CN and AA. In the subsequent section, we delve deeper into the elements within the GNN models that facilitate this approximation of link predictors while also identifying factors that impede their accuracy.
3.2 Estimation capabilities of GNNs for link predictors
GNNs exhibit the capability of estimating link predictors. In this section, we aim to uncover the mechanisms behind these estimations, hoping to offer insights that could guide the development of more precise and efficient methods for link prediction. We commence with the following theorem:
Theorem 3.1. Let G = (V. E) be non-attributed graph and consider a I-layer GCN/SAGE. Define the input vectors X E R NxF initialized randomly from a zero-mean distribution with standard deviation Nodee Additionally, let the weight matrix W E F= be initialized from a zero-mean distribution with standard deviation o weiight- After performing message passing, for any pair of nodes {(u, v)[(u, v) V x V. E}, the expected value of their inner product is given by:
GCN: B(h,. hww) Vando KEN.NA.
C
Σ
1
SAGE: E(h.. .hw) Vannte KEN.
C
Σ
1,
de
where d, d, + and C Phode Fweight
The theorem suggests that given proper initialization of input vectors and weight matrices, MPNN- based models, such GCN and SAGE, can adeptly approximate heuristic link predictors. This makes them apt for encapsulating joint structural features of any node pair. Interestingly, SAGE predominantly functions ability to weigh the count of common neighbors in a way similar to RA. This particular trait of GCN is evidenced by its enhanced approximation of RA, depicted in Figure 2
CN estimator, whereas the aggregation function in GCN grants it the
Quasi-orthogonal vectors. The GNN's capability to approximate heuristic link predictors is primarily grounded in the properties of their input vectors in a linear space. When vectors are sampled from a high-ding figgh-iimensionll linear space, they tend to be quasi-orthogonal implying that their inner product is nearly 0 w.h.p. With message-passing, these QO vectors propagate through the graph, yielding in a linear combination of QO vectors at each node. The inner product between pairs of QO vector sets essentially echoes the norms of shared vectors while nullifying the rest. Such trait enables GNNs to estimate CN through message- paasaagg... A key advantage of QO vectors, especially when compared with orthonormal basis, is their computational efficiency. For a modest linear increment in space dimensions, the number of QO vectors can grow exponentially, given an acceptable margin of error [3]. An intriguing observation is that the orthogonality of QO vectors remains intact even after GNNs undergo linear transformations post message-passingg attributed to the randomized weight matrix initialization. This mirrors the dimension reduction observed in random projection 200
Limitations. While GNNs manifest marked ability in estimating heuristic link predictors, they not unbiased estimators and can be influenced by factors such as node pair degrees, thereby

---

compromising their accuracy. Another challenge when employing such MPNNs is their limited generalization to unseen nodes. The neural networks, exposed to randomly generated vectors, may struggle to transform newly added nodes in the graph with novel random vectors. This practice also violates the permutation- rrruutatooniivaaiaanee principle of GNNs when utilizing random vectors as node representation. It could strengthen generalizability if we regard these randomly generated vectors as signatures of the nodes, instead of their node features, and circumvent the use MLPs for them.
Unbiased estimator. Addressing the biased element in Theorem 3.1 we propose the subsequent instantiation for the message-passing functions:
h (1+1)
Σ
MeN,
Such an implementation aligns with the SAGE model that employs sum aggregation devoid of self- node propagation. This methodology also finds mention in DotHash [12], serving as cornerstone for our research. With this kind of message-passing design, the inner product of any node pair signatures can estimate CN impartially:
Theorem 3.2. Ler G = (V, E) be a graph, and let the vector dimension be given by F E N.. Define the input vectors X = (X which are initialized from a random variable having a mean of 0 and a standard deviation of vT Using the I I-layer pessage-passiing Equation 3 for any pair of nodes {u, v))(u, v) E x },, the expected value and variance of their inner product are:
E( hww CN(u,)); v);
Var(h. ho) = F (dade + CN(( u)² 2 2CN(u, ui) + FVar(x' (onxx)))N((, v).
Though this estimator provides an unbiased estimate for CN, its accuracy can be affected by its variance. Specifically, DotHash recommends selecting a distribution for input vector sampling from vertices of hypercube with unit length, which curtails variance given that Var (ar(x²) = 0. However, the variance influenced by the graph structure isn't 't't adequately addressed, and this issue will be delved into Section 4
Orthogonal node attributes. Both Theorem 3.1 and Theorem 3.2 underscore the significance of
quasi orthogonality in input vectors, enabling message-passing to efficiently count CN. Intriguingly, in most attributed graphs, node attributes, often represented as bag-of-words [21]. exhibit inherent orthogonality. This brings forth a critical question: In the context of link prediction, do GNNs primarily approximate neighborhood overlap, sidelining the intrinsic value of node attributes? We earmark this pivotal question for in-depth empirical exploration in Appendix [E] where we find that random vectors as input to GNNs can catch up with or even outperform node attributes.
3.3 Multi-layer message passing
Theorem elucidates the estimation of CN based on single iteration of message passing. This section explores the implications of multiple message-passing iterations and the properties inherent the iteratively updated node signatures. We begin with a theorem delineating the expected value of the inner product for two nodes' signatures derived from any iteration of message passing:
Theorem 3.3. Under the conditions defined in Theorem 3.2 let h denote the vector for node after the I-th message-paseeee passing iteration. We have:
E
(P)) 12.9))
Σ
|walks u))l ()) v)},
KEV
where wwalks (u, v)] counts the number of length-l walks between nodes u and
This theorem posits that the message-passing procedure computes the number of walks between the target node pair and all other nodes. In essence, each message-passing trajectory mirrors the path
of the corresponding walk. As such, ! aggregates the initial QO vectors originating from nodes reachable by length-/ walks from node u. In instances where multiple length-/ walks connect node k to u, the associated QO vector Xx,; is incorporated into the sum |walks (k, u) times.
5

---

One might surmise a paradox, given that paassag--pssing calculates the number of walks, not nodes. However, in simple graph devoid of self-loops. where at most one edge can connect any two nodes, it is guaranteed that |walks (u, r)] iff (u, v) = 1. Consequently, the quantity of length-1 walks target node pair equates to CN, first-order heuristic. It's essential to recognize, however, that (walks (u, u)] 2 1 only implies SuD(u, v) L. This understanding becomes vital when employing message-passingg for estimating the local structure of a target node pair in Section
4 Method
In this section, introduce novel link prediction model, denoted as MPLP. Distinctively designed, MPLP leverages the pure essence of the message-passing mechanism to adeptly learn joint structural features of the target node pairs.
Node representation. While MPLP is specifically designed for its exceptional structural capture, it also embraces the inherent attribute associations of graphs that speak volumes about individual node characteris- tics. To fuse the attributes (if they exist in the graph) and structures, MPLP begins with a GNN, utilized to encode node u's representation: GNN(u) IR R. This node representation will be integrated into the structural features when constructing the QO vectors. Importantly, this encoding remains flexible, permit- ting the choice of any node-level GNN.
CNN(s) @ CNN(s)
4.1 QO vectors construction
Probabilistic hypercube sampling. Though deter- ministic avenues for QO vector construction are doc- umented [2 23 our preference leans toward prob- abilistic techniques for their inherent simplicity. We inherit the sampling paradigm from DotHash (12).
Figure 3: Representation of the target link (u, v) within our model (MPLP), with nodes color-coded based on their distance from the target link.
where each node & is assigned with a node signature h acquired via random sampling from the vertices of an F-dimensional hypercube with unit vector norms. Consequently, the sampling space becomes (-1/VE,1/VFF
for f
(0)
Harnessing One-hot hubs for variance reduction. The stochastic nature of our estimator brings along an inevitable accompaniment: variance. Theorem 3.2 elucidates that a graph's 's topology can augment estimator variance, irrespective of the chosen QO vector distribution. At the heart of this issue is the imperfectness of quasi-orthogonality. While pair of vectors might approach orthogonality, the same cannot be confidently said for the subspaces spanned by larger sets QO vectors.
Capitalizing on the empirical observation that real-world graphs predominantly obey the power- law distribution [24), we propose strategy to control variance. Leveraging the preva- Ience of high-degree nodes-or hubs-we designate unique one-hot vectors for the foremost hubs. Consider the graph's top-b hubs; while other nodes draw their QO vectors from hy- 1/ 63 b-b X these hubs are assigned one-hot vectors from [o)F~b 1) reserving distinct subspace of the linear space to safeguard orthogonality. Note that when new nodes are added, their QO vectors are sampled the same way as the non-hub nodes, which can ensure a tractable computation complexity.
percube
Norm rescaling to facilitate weighted counts. Theorem 3.1 alludes to an intriguing proposition: the estimator's potential to encapsulate not just CN, but also RA. Essentially, RA and AA are nuanced heuristics translating to weighted enumerations of shared neighbors, based on their node degrees. In Theorem 3.2 such counts are anchored by vector norms during dot products. MPLP enhances this count methodology by rescaling node vector norms, drawing inspiration from previous works 12] 25

---

This rescaling is determined by the node's ' representation, GNN(u), and its degree du. The rescaled vector is formally expressed as:
[(GNN())]][d)) h
(4)
where f: f R is an MLP mapping the node representation and degree to scalar, enabling the flexible weighted count paradigm.
4.2 Structural feature estimations
Node label estimation. The estimator in Theorem 3.2 can effectively quantify CN. Nonetheless, solely relying on CN fails to encompass diverse topological structures embedded within the local neighborhood. To offer richer representation, an adept labeling tool [T. demarcating nodes based on their shortest-pan -path distances relative to a target node pair. For given pair (u, v), node & belongs to node set DE(p, q) iff SPD(u, k) p and Sp k) = q. Unlike its usage as node labels, we opt to enumerate these labels, producing link feature defined by #(p.4) DD{p,, 9)|. Our model adopts philosophy akin to ELPH [16), albeit with a distinct node-estimation mechanism.
turn to Distance Encoding (DE) 26). DE acts as
Returning to Theorem 3.3 we recall that message-passineg as in Equation essentially corresponds to walks. Our ambition to enumerate nodes necessitates a single-layer gessage-passing alteration, reformulating Equation 3 to:
(0) h
(5)
KEN;
Here, Ne pinpoints v's shortest-path neighborhoods distanced by the shortest-path s. This method sidesteps the duplication dilemma highlighted in Theorem 3.3 ensuring that v7 aggregates at most
one QO vector per node. Similar strategies are explored [27 28
For tractable computation, we limit the largest shortest-path distance as 2 maz(p, q). Conse- quently, to capture the varied proximities of nodes to the target pair (u, v), deduce:
E ((())
r
r P.9 2
IW
Σ
#(8,4),
p=0
#(p. 9)
(6)
ISaSr
Σ
#(p,s),
q=
1se5r
Concatenating the resulting estimates yields the expressive structural features of MPLP.
Shortcut removal. The intricately designed structural features improve the expressiveness of MPLP. However, this augmented expressiveness introduces susceptibility distribution shifts during link prediction tasks [29]. Consider a scenario wherein the neighborhood of a target node pair contains a node k. Node resides a single hop away from one of the target nodes but requires multiple steps to connect with the other. When such a target node pair embodies positive instance in the training data (indicative of an existing link), node i can exploit both the closer target node and the link between the target nodes as shortcut to the farther one. This dynamic ensures that for training-so set positive instances, the maximum shortest- path distance from any neighboring node to the target pair constrained to the smaller distance increased by one. This can engender a discrepancy in distributions between training and testing phases, potentially diminishing the model's generalization capability.
To circumvent this pitfall, we adopt an approach similar to preceding works 18 30 19
31. Specifi-
cally, we exclude target links from the original graph during each training batch, as shown by the dash line in Figure 3 This maneuver ensures these links are not utilized as shortcuts, thereby preserving the fidelity of link feature construction.
Feature integration for link prediction. Having procured the structural features, we proceed to formulate the encompassing link representation for target node pair (u, v) as:
h (u,x) (GNN(u) @ GNN(e)) (1,, 1), I),..., r)),
which can be fed into classifier for link prediction between nodes (u, v).
7

---

Table 1: Link prediction results on non-attributed benchmarks. The format is average score + standard deviation. The top three models are colored by First, Second, Third.
USAir Hits@
NS
PB Hits@ 50
Yeast Hits@
C.ele 5o
Power @o
Router @its 50
E.coli Hits 50
Metric
Hits
CN
80.52+4.07
74.00=1.96
37 17.22=a.66
72. 72.60+8.85
47. 11..7
11.57=0.a5
9 9.38
34=2.72770
AA
85.51
74.00 98
39.48s9.58
T3.6241.01
58.34
11.57
1.38
68. 18.13
85.9521188
74.00
38 38.9443..5 54
T3.6241.01
61.47a1-59
11.57
9.38&1.00
74.45:20.5
GCN
73.29
75.32=2.07
37 31.32=44.0
13.15+2.4
10,68
40=20.00
21.12+.55
61.02-1..0
SAGE
83.81
56.62
47. 07.26::2.o0 sa
71.06as.12
58.97
6.89
42 22.222
75.60=2240
SEAL
90.47.5.00
86.30 oo
44.47
83.92.1.17
64.80
31.46..3 25
61 10 10
83.42.1.01
Neo-GNN
$6.07
83.54=3.92
44.04=1.9
83.14+0.78
63.22+4.52
21.9844.22
42.81 +2.81
73.76
ELPH
87.6011.49
88.4912.11
46.91 22.21
82.T4.1.19
64.45:::::1
26.61 11773
61.07 on
15.25
NCNC
86.1671177
83.18a3.17
46.85
82.0020.a7
60.49
23.28a1.55
62.4528.77
83.94
MPLP
92.12:2.21
02.022:2.00
62.55=22.90
36.36:0072
74. 74.28=2.00
32, ss
64.68
86.1 86.11+0.88
MPLP+
91.24::211
88. 88.91::2.0
51.81:22.9
84.95:0.e6
72.73:2.0
31.86 se
60.94
87.07
Table 2: Link prediction results on attributed benchmarks. The format is average score + standard deviation. The top three models are colored by First, Second, Third.
CS Ho
Physics Hi
Computers H0
Photo Hi
Collab Ho
PPA Hits @ 100
Citation2 MRR
Metric
CN
51.04 50
61 46
21.9622.00
29.33
61.37a0.0 00
27 77.66=o.mm 00
51.47
AA
68. 08,26:1125 28
70.98+1.96
26.96=2.0s
37.35+2
61.35
02.15=0.00
51.89:5.00
RA
68.25s1.29
12.29
28.05
40.77
64.00sa.00
49.33=0.00
51.98:0.00
GCN
66,00=2.00 90
73.71#2.25
22.95=10.58
28. 28.1147.51
35.53=2.89
18 18.07=0.00
84.74=0.21
SAGE
57.79
74.10a2.51
33.79aa.11
46.01 sa
88.8227.41
16.55=0.00 0.00
82.60
SEAL
68.50a0
74.27
30.43.9.07
46.08
64.74g0.45
48.80
87. 07.67:2.
Nco-GNN
71.13=1.00
72 28
22.76=a.07
44.83+3322
57 ....2....7
49. 13:0.00
87.26=00.4
ELPH
72.26=2 ss
65.80+2.25
29.01=2.00
43.51+2.57
9.....ssss
19. 85:.
87.56+0.11
NCNC
74.65:1.28
75.96:1.73
36.481:4.18
47.98-2.36
66. 66.61:0.71
61.42:0077
89.12:0
MPLP
76.40.1.44 44
76.46 95
43.47a3.61
58.08
67.05
00M
OOM
MPLP+
75.55=1.46 46
76.36:1.40
42.21+a.50
67.76=2.76
66. 06.99:20.00
65. 65.24s1.50
90.72=0.12
4.3 More scalable estimation
MPLP estimates the cardinality of the distinct node sets with different distances relative to target node pairs in Equation 6 However, this operation requires a preprocessing step to construct the shortest-path neighborhoods No for S r, which can cause computational overhead on large-scale graph benchmarks. To overcome this issue, we simplify the structural feature estimations as;
#(p g) E. (h A
where h (1+1) EvEN.
(0 follows the message-passing defined in Equation Similar to common GNNs, such a pressage-passingg only requires the one-hop neighborhood Ny. which provided in a format of adjacency matrices/lists by most graph datasets. Therefore, we substitute the structural features MPLP with the estimation in Equation]] We denote such a model with walk-level features as MPLP+
4.4 Triangular substructure estimation
Our method, primarily designed to encapsulate the local structure of target node pair, unexpectedly exhibits the capacity for estimating the count of triangles linked to individual nodes. This capability, traditionally considered beyond the reach of GNNs, marks a significant advancement in the field [32] Although triangle counting is less directly relevant in the context of link prediction, the implications of this capability are noteworthy. To maintain focus, we relegate the detailed discussion on pure message- passage-passing for effective triangle counting to Appendix C

---

Table 3: Link prediction results OGB datasets under HeaRT 33 by First, Second, Third.
The top three models colored
Collab
PPA
Citation2
Models
MRR
Hits@20
MRR
Hits@20
MRR
Hits @0
CN
4.20
16.46
25.70
68.25
17.11
41.73
AA
5.07
19.59
26.85
70.22
17.83
43.12
RA
6.29
24.29
28.34
71.50
17.79
43.34
GCN
6.09
22.48
26.94
68.38
19.98
51.72
SAGE
5,53
21.26
27.27
69.49
22.05
53.13
SEAL
6,43
21.57
29.71
76.77
20.60
48.62
Neo-GNN
5.23
21.03
21.68
64.81
16.12
43.17
BUDDY
5.67
23.35
27.70
71,50
19.17
47.81
NCNC
4.73
20.49
33.52
82.24
19.61
51.69
MPLP+
6.79
25.10
41.40
84.88
23.11
55.51
Experiments
Datasets, baselines and experimental setup We conduct evaluations across a diverse spectrum of 15 graph benchmark datasets, which include 8 hon-attributed and 7 attributed graphs ? It also includes three datasets from OGB [10] with predefined train/test splits. In the absence of predefined splits, links are partitioned into train, validation, and test sets using 70-10-20 percent split. Our comparison spans three categories of link prediction models: (1) heuristic-based methods encompassing CN, AA, and RA; (2) node-level models like GCN and SAGE; and (3) link-level models, including SEAL, Neo-GNN (25], ELPH [16], and NCNC 19. Each experiment conducted 10 times, with average score and standard deviations reported. The evaluation metrics aligned with the standard metries for OGB datasets, and we utilize Hits 50 for the remaining datasets. We limit the number of hops r = 2, which results in good balance of performance and efficiency, A comprehensive description of the experimental setup is available in Appendix D
Collab
PPA
Citation2
91
60
90
+
50
Hits 89
Hitg0100
GCN
88
Neo-GNN
87
BUDDY
86
MPLP
MPLP+
20
10"
10'
10a
10'
10a
10a
10a
10a
10a
10
Inference Time
Inference Time
Inference Time
Figure Evaluation of inference time on large-scale OGB datasets. The inference time encompasses the entire cycle within full-batch inference.
Results Performance metrics are shown in Tables 1 and 2 Our methods, MPLP and MPLP+, demonstrate superior performance, surpassing baseline models across evaluated benchmarks by significant margin. Notably, MPLPP tends outperform MPLP+ in various benchmarks, suggesting that node-level structural features (Equation 6) might more valuable for link prediction tasks than the walk-level features (Equation]) 7). In large-scale graph benchmarks such PPA and Citation2, MPLP+ sets new benchmarks, establishing state-of-the-an art results. For other datasets, our methods
'On OGB dataset Collab, PPA, and Citation2, report the performance of BUDDY [16. streamlined version of ELPH. the rest of datasets, we report performance ELPH. which is empirically better when the computation budget allowed.
Our code is publicly available at htttpss: httter///ggtttt..c.aaaaaaeeraaca
labelling

---

show a substantial performance uplift, with improvements in Hits @ 50 ranging from 2% to 10% compared to the closest competitors.
We extend our evaluation of MPLP+ to assess its performance on large-scale datasets under the challenging HeaRT setting proposed by Li et al. 33 HeaRT introduces more rigorous and realistic set of negative samples during evaluation, typically resulting in notable decline in performance across link prediction methods. As detailed in Table 3
MPLP+ consistently outperform all other methods across three OGB graph benchmarks in this demanding context. This underscores the robustness of MPLP+, affrrming ability to maintain superior performance across a variety of graph benchmarks and evaluation settings.
Time efficiency We conduct an analysis of the time efficiency of our methods, MPLP and MPLP+ against established baselines using three large-scale OGB datasets. The results, illustrated in Figure 4 demonstrate that our approaches not only deliver superior performance across the graph benchmarks but also set new benchmark for Mtate-of-the-ar time efficiency full-batch inference. In particular, the primary component underlying inference speeds to rival that of the baseline GCN. Additionally, the structural feature estimations enhance the models' expressiveness, enabling more accurate representation of graph structures, particularly in the context of link prediction tasks. More details can found in Appendix D.3
methods is the pessang-passing operation, which allows their
MSE of Estimation for #(1.1)
MSE of Estimation for #(1.2)
MSE of Estimation #(1,0)
EUPH
10?
102
MPLP
10"
10
10
10-1
1000
2000
3000
4000
1000
2000
3000
4000
1000
2000
3000
4000
Signature Dimension
Signature Dimension
Signature Dimension
Figure 5: MSE of estimation for #(1,1),#(111 #(1, and #(1, on Collab. Lower values are better.
Estimation accuracy We investigate the precision of MPLP in estimating #(p. g), which denotes the count of node labels, using the Collab dataset. The outcomes of this examination are illustrated in Figure Although ELPH possesses the capability to approximate these counts utilizing techniques like HinHash and Hyperloglog, our method exhibits superior accuracy. Moreover, ELPH runs out of memory when the dimension is larger than 3000. Remarkably, deploying one-hot encoding strategy for the hubs further bolsters the accuracy of MPI.P, concurrently diminishing the variance introduced by inherent graph structures. An exhaustive analysis, including time efficiency considerations, is provided in Appendix F.I
Extended ablation studies Further ablation studies have been carried out to understand the indi- vidual contributions within MPLP. These include: (1) exploration of the distinct components of MPLP in Appendix F.2, (2) an analysis of the performance contributions from different structural estimations in Appendix and (3) an examination of parameter sensitivity in Appendix F:4
6 Conclusion
We study the potential of message- passing GNNs to encapsulate link structural features. Based on this, we introduce a novel link prediction paradigm that consistently outperforms state-of-the-at baselines across various graph benchmarks. The inherent capability adeptly capture structures enhances the expressivity of GNNs, all while maintaining their computational efficiency. Our findings hint at promising avenue for elevating the expressiveness of GNNs through probabilistic approaches.
mnessage-passing
10

---

7 Acknowledgements
We would like to thank the anonymous reviewers for their insightful comments and helpful discussions. This research supported in part by the University of Notre Dame's Lucy Family Institute for Data and Society and the NSF Center for Conputer-Assisted Synthesis (C-CAS), under grant number C2E-2202693.
References
[1] David Liben-Nowell and Jon Kleinberg. The link prediction problem for social networks. In Proceedings of the twelfth international conference Information and knowledge management, CIKM '03, pages 556-559, New York, NY, USA, November 2003. Association for Computing Machinery. ISBN 978- 1788--581111 13-72331173-11 doi: 10. (0.1145/956663.95699 996677... URL http://doii org/
10. 1145/9566663 956972
[2] Damian Szklarczyk, Annika L. Gable, David Lyon, Alexander Junge, Stefan Wyder, Jaime Huerta-Cepas, Milan Simonovic, Nadezhda T. Doncheva, John H. Morris, Peer Bork, Lars J. Jensen, and Christian von Mering. STRING v11: protein-protein association networks with increased coverage, supporting functional discovery in senome-wide experimental datasets. Nucleic Acids Research, 47(D1):D077-D111 January 2019. ISSN 1362-4962 doi: 10.1093/ nar/gky 1 1131.
[3] Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recom- mender systems. Computer, 42(8):30-37, 2009. Publisher: IEEE.
[4] Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-foo ford networks: A general graph neural network framework for link prediction. Advances Neural Information Processing Systems, 34, 2021.
[5] Thomas N. Kipf and Max Welling. Seme-Super Classification with Graph Convolutional Networks. 16Xiv:1609 16t.9.090000 [cs, stat), February 2017. URL http:///aaxxio wwtp://rrgg/bbb///eeeee ab66 02907 arXiv: 0.99002977
[6] Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural Message Passing for Quantum Chemistry. CoRR, abs/1704.01212, 2017. URL www.ooggg/////eeeeee/e.eeeeeee/e
//arxiv. farxiv.org/ae abs/ 01..00..1122
arXiv: 1704.01212.
[7] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive Representation Learning Large Graphs. arXiv: 02216 [cs, stat], September 2018. URL http::/arxxi org/ abs/ 1706.02216
arXiv: 1706.02216.
[8] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. arXiv: 1700 [cs, stat], February 2018. URL
http://arxiv.oot org. abgg/bbs/// awtpaasss..//////.////////a...ta 10903
arXiv: 1710.
[9] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? CoRR, abs/ 10.00006, 2018. URL http://arxiv. hww.voorggaaaao orgg/bs///iioo httpp//1110000.0666.111111111110 arXiv: 1810.00826.
[10] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. arXiv:2005.0065 [cs, stat], February 2021. http:htt:/aaatt org/ org/abs/ arXiv: 2005.00687.
[11] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling Trick: The- ory of Using Graph Neural Networks for Multi-Node Representation Learning. In M. Ran- zato, A. Beygelzimer,
Dauphin, S. Liang, and Wortman Vaughan, editors, Ad- vances in Neural Information Processing Systems, volume 34, pages 9061-9073, Curran Associates, Inc., 2021. URL http://://ppppppppppeeeee nww.ins..ppp... httpa/ppss..cppppp/////////1//1 (bcee3/7999233444440077777883833 Pwpsssapprppppp.

---

[12] Igor Nunes, Mike Heddes, Pere Vergés, Danny Abraham, Alexander Veidenbaum, Alexandru Nicolau, and Tony Givargis. DotHash: Estimating Set Similarity Metrics for Link Predic- tion and Document Deduplication, May 2023. arXiv:2305. 17310 [es].
http::////wvvv...aaaaa/ arrg/abs/2305... 2305. 17310
[13] Paul C. Kainen and Véra Kúrková. Quasiorthogonal dimension of euclidean spaces. Ap- plied Mathematicss Letters. 6(3):7-10, May 1993. ISSN 0893-9659, doi: 10.1016/
0993399659993))00223-3 URL https: htt.://ccedrrttttccmm///e/aaaaaa ps1/0893965993900233
[14] Lada A. Adamic and Eytan Adar. Friends and neighbors on the Web. Social Networks, 25(3): 211-230, 2003. ISSN 0378- 8733. doi: http:///d..rrr/......oo//////2//
URL
sci http://wwww....ccooo/////c/ooo/a
[15] Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B, 71(4):623-630 2009. Publisher: Springer.
[16] 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. September 2022. URL
attps://openrevill www./eeeeenenneeeeeeeee ret//forummdddmoloooooooooo
[17] Thomas N. Kipf and Max Welling. 1611.07309
Variational Graph Auto-Encoders, 2016. _eprint:
[18] Muhan Zhang and Yixin Chen. Link Prediction Based on Graph Neural Networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gar- nett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL httpp:://procesdings neurips /ceaur/ppp.cccppeee//////// 53200773770093334409666622222222
[19] Xiyuan Wang, Haotong Yang. and Muhan Zhang. Neural Common Neighbor with Com- pletion for Link Prediction, February 2023. URL htttp://arxiv, http:://axxxv..oraabbbe hergg/bs/2000 2302 00890 arXiv:2302.00890 [es].
[20] William Johnson and Joram Lindenstrauss. Extensions of Lipschitz maps into Hilbert space. Contemporary Mathematics, 26:189-206, January 1984. ISSN 9780821850305. doi: 10. 00.1000/com/000667774000..
[21] Skye Purchase, Yiren Zhao, and Robert D. Mullins. Revisiting Embeddings for Graph Neural Networks. November 2022. URL httl::ttt//peerreiiiee http://ppaarreeeeeoneeeeoooradaa
[22] Paul C Kainen. Orthogonal dimension and tolerance. Unpublished report, Washington DC: Industrial Math, 1992.
[23] Paul C Kainen and Věra Kurkova. Quasiorthogonal dimension. In Beyond traditional proba- bilistic data processing techniques: Interval, fuzzy etc. Methods and their applications, pages 615-629, Springer, 2020.
[24] Albert-Láászóó Barabási and Réka Albert. Emergence of Scaling in Random Net- works. Science, 28665439):509-51,, 1999. doi: 10.1 10.1126/sceecce.286
URL https://www http::::/wwwsssiennee science.ecc.cccccc......e wwtp:///////////oo//oooooooa 1126/science 286. 5439. 5599 _eprint:
[25] Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo Kim. Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction. November 2021. URL.
[26] Pan Li, Yanbang Wang, Hongwei Wang. and Jure Leskovee. Distance Encoding: De- sign Provably More Powerful Neural Networks for Graph Representation Learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 4465-4478. Curran As- sociates, Inc., 2020. URL. 27735660036555777777555522222333
www.ggs.nuriis.... ct.ppp.cc/pppeee cc/ppaper/2020//ilel
pdf
12

---

[27] Ralph Abboud, Radoslav Dimitrov, and Ismail Ilkan Ceylan. Shortest Path Networks for Graph Property Prediction. November 2022. UtLLptpps//ppprrrrie..oo//ooooo
mWzuwkxuFgt
[28] Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How Powerful are K-hop Message Passing Graph Neural Networks. May 2022. URL htt.tt::////oeerreeier
bet/fforun2ddnnNSaRRRRS..
[29] Kaiwen Dong, Yijun Tian, Zhichun Guo, Yang Yang. and Nitesh Chawla. FakeEdge: Alleviate
Dataset Shift in Link Prediction. December 2022. URI htt..httts:///// htttpp:://openreieee..eee
id=QDNojSXuvtX
[30] Haoteng Yin, Muhan Zhang, Yanbang Wang, Jianguo Wang, and Pan Li. Algorithm and System Co-design for Efficient Subgraph-based Graph Representation Learning. Proceedings of the VLDB Endowment, 15(11):2788 2796, July 2022. ISSN 21 21500-097. doi: 10.14778/355179. org/abs//. 2202. 13538 #rXiv:2202.33538 [es].
3551831. URL wattt::p/aariit
[31] Jiarui Jin, Yangkun Wang. Weinan Zhang, Quan Gan, Xiang Song, Yong Yu, Zheng Zhang, and David Wipf. Refined Edge Usage of Graph Neural Networks for Edge Prediction. December 2022. doi: 10.48550/arxww.2222..222 12970. URL htttp::/arxxiiii wrw. httg//bb/220/
/212 2212. 12970v1
[32] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can Graph Neural Networks Count Substructures? arXiv:2002.cm 04025 [cs, stat], October 2020. /ttp://///aaxx/ org/ abs/ 2002. 04025
arXiv: 2002.04025.
[33] 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 Benchmarking, July 2023. URL http:///aaxx wttp://wwwwraaa//////e/// 10453 arXiv:2306. 10453
[es].
[34] Leo Katz. new status index derived from sociometric analysis. Psychometrika, 18(1):39-43, March 1953. ISSN 1860-0980. doi: (0.1007/BF02288026. URL https:///oi..orrgee 1007/BF02280026
[35] Gerard Salton and Michael J. McGill. Introduction to Modern Information Retrieval, McGraw- Hill, Inc., USA, 1986. ISBN 0-07-054484-0.
[36] Sergey Brin and Lawrence Page. The Anatomy of a Large-Scale Hypertextuul Web Search Engine. Computer Networks, 10:-17,, 1998. URL httt::t//wwwddt stanford. edu/
Baickrub/googlee html
[37] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks, November 2021. URL
02244 arX.v:1810.02244
[cs, stat].
[38] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably Powerful Graph Networks. arXiv:1905.1 1111999151116 1166 [cs, stat], June 2020. URL http:://aaxi..org///// 1905. 11136 arXiv: 1136.
[39] Muhan Zhang and Pan Li. Nested Graph Neural Networks, 2021. URL httpts:t////xii... abs/2110.1330
[40] Fabrizio Frasca, Beatrice Bevilacqua, Michael M. Bronstein, and Haggai Maron. Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries, June 2022. URL http
//arxiv. hwtp://rggabb////aegee 11140 M.ii:2206.111444 [cs].
[41] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random Features Strengthen Graph Neural Networks, 2021. _eprint: 2502.03155.
[42] Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewiez. The Surprising Power of Graph Neural Networks with Random Node Initialization, 2021. _eprint: 2070.01179.
13

---

[43] Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks, November 2021. URL 10di:2111.00622 [es].
[44] Vladimir Batagelj and Andrej Mrvar. Pajek datasets website, 2006. URL htth::ttpllddoo fmf
[45] Mark EJ Newman. Finding community structure in networks using the eigenvectors matrices. Physical review E, 74(3):036104, 2006. Publisher: APS.
[46] Robert Ackland and others. Mapping the US political blogosphere:
Are conservative bloggers more prominent? In BlogTalk Downunder 2005 Conference, Sydney, 2005.
[47] Christian Von Mering, Roland Krause, Berend Snel, Michael Cornell, Stephen G Oliver, Stanley Fields, and Peer Bork. Comparative assessment of large-scale data sets of protein-protein interactions. Nature, (17(6887) 403, 2002. Publisher: Nature Publishing Group.
[48] Duncan J. Watts and Steven H. Strogatz. Collective dynamics of worldd networks. Nature, 393:440 442, 1998. Utttttps://app www.eettiscooollatt...... wrtp/ooppsoooo 3034643
[49] Neil Spring, Ratul Mahajan, and David Wetherall. Measuring ISP topologies with Rocketfuel. ACM SIGCOMM Computer Communication Review, 32(4):133-145 2002. Publisher: ACM New York, NY, USA.
[50] Muhan Zhang, Zhicheng Cui, Shali Jiang, and Yixin Chen. Beyond link prediction: Predicting hyperlinks in adjacency space. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
[51] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of Graph Neural Network Evaluation, June 2019. URL arXiv: 1811.05868 [cs, stat].
www.aiii...//bbbb. org/abs/
1811 05868
[52] Matthias Fey and Jan E. Lenssen. Fast Graph Representation Learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
14

---

Appendix
Table of Contents
A Related work
16
Efficient inference at node-level complexity
16
Estimate triangular substructures
Method
Experiments
17
D
Experimental details
18
D
Benchmark datasets
18
D
More details in base line methods
19
D.3
Evaluation Details: Inference Time
19
Software and hardware details
D35
Time Complexity
19
D.6
Hyperparameterss
20
E
Exploring Bag- Of- Words Node Attributes
20
E.1
Node Attribute Orthogonality
21
E.2
Role of Node Attribute Information
21
Expanding QO Vector Dimensions
22
F
Additional experiments
22
F.1
Node label estimation accuracy and time
................................
22
F2
Model enhancement ablation
23
3
Structural features ablation
24
Parameter sensitivity
25
Theoretical analysis
25
Proof for Theorem 3.1
25
Proof for Theorem 3.2
27
G.3 Proof for Theorem 3,3
29
Limitations
29
Broader Impact
30
15

---

A Related work
Link prediction Link prediction, inherent to graph data analysis, has witnessed a paradigm shift from its conventional heuristic-bai bbstd methods to the contemporary, more sophisticated GNNs approaches. Initial explorations in this domain primarily revolve around heuristic methods such as CN, AA, RA, alongside seminal heuristics like the Katz Index (34), Jaccard Index (35), Page Rank [36], and Preferential Attachment [24]. However, the emergence of graphs associated with node attributes has shifted the research landscape towards GNN-based methods. Specifically, these GNN-centric techniques bifurcate into node-level and link-level paradigms. Pioneers like Kipf and Welling introduce the Graph Auto-Encoder (GAE) to ascertain node pair similarity through GNN- generated node representation. On the other hand, link-level models, represented by SEAL 18] opt for subgraph extractions centered node pairs, even though this can present scalability challenges.
Amplifying GNN Expressiveness with Randomness The expressiveness of GNNs, particularly those of the MPNNs, has been the subject of rigorous exploration [9]. A known limitation of MPNNs, test, often results in indistinguishable representation
their equivalence to the WWeisfeller-Lehmae for non-isomorphic graphs. A suite of contributions has surfaced to boost GNN expressiveness, of which 407 stand out. An elegant, yet effective paradigm involves brreetty-breaking through stochasticity injection < Although enhancing expressiveness, such random perturbations can occasionally undermine generalizability. Diverging from these approaches, our methodology exploits probabilistic orthogonality within random vectors, culminating robust structural feature estimator that introduces minimal estimator variance.
Link-Level Link Prediction While node-level models like GAE offer enviable efficiency, they occasionally fall short in performance when compared with rudimentary heuristics [16). Efforts to build scalable link-level alternatives have culminated innovative methods such as Neo-GNN 25 which distills structural features from adjacency matrices for link prediction. Elsewhere, ELPH [6
harnesses hashing mechanisms for structural feature representation, while NCNC 19 adeptly aggregates common neighbors' node representation. Notably, DotHash [12], which profoundly influenced our approach, employs quasi- orthogonl random vectors for set similarity computations, applying these in link prediction tasks.
Distinctively, our proposition builds upon, yet diversifies from, the frameworks of EL.H and DotHash. While resonating with ELPH's architectural spirit, we utilize a streamlined, efficacious hashing technique over MinHash for set similarity computations. Moreover, we resolve ELPH's limitations through strategic implementations like shortcut removal and norm rescaling. When paralleled with DotHash, our approach magnifies its potential, integrating with GNNs for link predictions and extrapolating its applicability to multi-hop scenarios. It also judiciously optimizes variance induced by the structural feature estimator in sync with graph data. We further explore the potential of achieving higher expressiveness with linear computational complexity by estimating the substructure counting (32]
B Efficient inference at node-level complexity
In addition to superior performance, MPLP stands out for its practical advantages in industrial applications due to its node-level inference complexity. This design is akin to employing an MLP as the predictor. Our method facilitates offline preprocessing, allowing for the caching node signatures representations. Consequently, during online inference in production setting, MPLP merely requires fetching the relevant node signatures or representations and processing them through an MLP. This approach significantly streamlines the online inference process, necessitating only node-level space complexity and ensuring constant time complexity for predictions. This efficiency in both space and time makes MPLP particularly suitable for real-world applications where rapid, on-the-fly predictions are crucial.
C Estimate triangular substructures
Not only does MPLP encapsulate the local structure of the target node pair by assessing node counts based varying shortest-path distances, but it also pioneers in estimating the count of triangles
16

---

Table 4: Performance of different GNNs on learning Figure 6: Representation of the target link the counts of triangles, measured by MSE divided by(u, variance of the ground truth counts. Shown here are the estimation component.
(u, v) of MPLP after including the triangular
median (i.e., third-best) performances of each model over five runs with different random seeds.
Dataset
Ardos-Renyl
Random Regular
GNN(()) (N)
GCN
8.27E-1
2.05
GIN
1.25E-1
4.74E-1
SAGE
1.48F-1
5.21E-1
SGNN
1.13E-1
4,43B-1
2-IGN
9.85E-1
5.96E-1
PPGN
2.51E=7
3.71E-5
LRP-1-3
2.49E-4
3,83E-4
Deep LRP-1-3
4.77E-5
5.16E-6
MPLP
1.61E-4
3.70E-4
#
linked to any of the nodes- ability traditionally deemed unattainable for GNNs 32 In this section, we discuss a straightforward implementation of the triangle estimation.
C.1 Method
Constructing the structural feature with DE can provably enhance the expressiveness of the link prediction model [T) However, there are still prominent cases where labelling trick also fails to capture. Since labelling trick only considers the relationship between the neighbors and the target node pair, it sometimes miss the subtleties of intra-neighbor relationships. For example, the nodes of 1 1) in Figure exhibit different local structures. Nevertheless, labelling trick like DE tends treat them equally, which makes the model overlook the triangle substructure shown in the neighborhood. Chen et al. [32] discusses the challenge of counting such substructure with a pure message-passing framework. We next give implementation of message-passing passing to approximate triangle counts linked to a target node pair- mair-equivalent in complexity to conventional MPNNs.
For triangle to form, two nodes must connect with each other and the target node. Key to methodology is recognizing the obligatory presence of length-1 and length-2 walks to the target node. Thus, according to Theorem 3.3 estimation formalize
#( A
E (1))
n.))
(8)
Augmenting the structural features with triangle estimates gives rise to more expressive structural feature set of MPLP.
C.2 Experiments
Following the experiment Section 6.1 [32], we conduct an experiment to evaluate MPLP's ability to count triangular substructures. Similarly, we generate synthetic graphs the benchmarks: the Erdos-Renyi graphs and the random regular graphs. We also present the performance baseline models reported in (32] Please refer to [32 for details about the experimental settings and bascline models. The results are shown Table 4
As the results show, the triangle estimation component of MPLP can estimate the number of triangles the graph with almost negligible error, similar to other more expressive models. Moreover, MPLP achieves this with much lower computational cost, which is comparable to 1-WL GNNs like GCN, GIN, and SAGE. demonstrates MPL.P's advantage of better efficiency over more complex GNNs like 2-IGN and PPGN.
17

---

Table 5: Statistics of benchmark datasets.
Dataset
#Nodes
#Edges
Avg. node deg.
Std. node deg.
Max. node deg.
Density
Attr. Dimension
C.ele
297
4296
14.46
12.97
134
9.7734%
Yeast
2375
23386
9.85
15.50
118
0.8295%
Power
4941
13188
2.67
1.79
19
0.1081%
Router
5022
12516
2.49
5.29
106
0.0993%
USAir
332
4252
12.81
20.13
1.39
7.738516
E.coli
1808
29320
16.24
48.38
1030
1.8009%
NS
1589
5484
3.45
3.47
34
0.4347%
PB
1222
33428
27.36
38.42
351
4.4808%6
CS
18333
163788
8.93
9.11
136
0.0975%
6805
Physies
34493
495924
14.38
15.57
382
0.0834%%
8415
Computers
13752
491722
35.76
70.31
2992
0.5201 %
767
Photo
7650
238162
31.13
47.28
1434
0.8140%
745
Collab
235868
2358104
10.00
18.98
671
0.0085%6
128
PPA
576289
30326273
52.62
99.73
3241
0.0256%
58
Citation2
2927963
30561187
10.44
42.81
10000
0.0014%
128
D Experimental details
D.1
Benchmark datasets
The statistics of each benchmark dataset are shown in Table The benchmarks without attributes
are:
USAir graph of US airlines;
NS
a collaboration network of network science researchers;
PB
46
graph of links between web pages US political topics;
Yeast
protein-protein interaction network in yeast;
C.ele
48
the neural network of Caenorhabditis elegans;
Power
48
the network of the western US's electric grid;
Router the Internet connection the router-level;
E.coli 50
the reaction network of metabolites in Escherichia coli.
4 out of benchmarks with node attributes come from while Collab, PPA and Citation2 are from Open Graph Benchmark [10]:
CS: co-authorship graphs in the field of computer science, where nodes represent authors,
edges represent that two authors collaborated on a paper, and node features indicate the keywords for each author's 's papers;
Physics: co-authorship graphs in the field of physics with the same node/edge/feature definition of CS:
Computers: a segment of the Amazon co-purchase graph for computer-related equipment, where nodes represent goods, edges represent that two goods are frequently purchased together together, and node features represent the product reviews;
Physics: segment of the Amazon co-purchase graph for photo-related equipment with the same node/cdge/fcatuue definition as of Computers;
Collab: large-scale collaboration network, showcasing wide array of interdisciplinary partnerships.
PPA: large-scale protein-protein association network, representing the biological interac- tion between proteins.
18

---

Citation2: large-scale citation network, with papers nodes and the citaitons as edges.
Since OGB datasets have fixed split, no train test split is needed for it. For the other benchmarks, we randomly split the edges into 70- (0-10-20 as train, validation, and test sets. The validation and test sets are not observed in the graph during the entire cycle of training and testing. They are only used for evaluation purposes. For Collab, it is allowed to use the validation set in the graph when evaluating on the test set.
We run the experiments 10 times on each dataset with different splits. For each run, we cache the split edges and evaluate every model on the same split to ensure fair comparison. The average score and standard deviation are reported in Hits 100 for PPA, MMR for Citation2 and Hits@ 50 for the remaining datasets.
D.2 More details in baseline methods
In our experiments, we explore advanced variants of the baseline models ELPH and NCNC. Specifi- cally, for ELPH, Chamberlain al. [16] propose BUDDY, a link prediction method that preprocesses node representations to achieve better efficiency but compromises its expressiveness. NCNC [I9] builds upon its predecessor, NCN, by first estimating the complete graph structure and then perform- ing inference. In our experiments, we select the most expressiveness variant to make sure it is fair comparison between different model architectures. Thus, we select ELPH over BUDDY, and NCNC over NCN to establish robust baselines in our study. We conduct a thorough hyperparameter tuning for ELPH and NCNC to select the best-performing models on each benchmark dataset. We follow the hyperparameter guideline of ELPH and NCNC to search for the optimal structures. For ELPH, we run through hy peerparaaeterss including dropout rates on different model components, learning rate, batch size, and dimension of node embedding. For NCNC, experiment dropout rates on different model components, learning rates on different model components, batch size, usage of jumping knowledge, type of encoders, and other model-specifee terms like alpha. For Neo-GNN and SEAL, due to their relatively inferior efficiency, we only tune the common hyperparameters like learning rate, size of hidden dimensions.
D.3 Evaluation Details: Inference Time
In Figure Al we assess the inference time across different models on the OGB datasets for a single epoch of test links. Specifically, clock the wall time taken by models score the complete test set. This encompasses preprocessing, message- message-passing, and the actual prediction. For the SEAL model, we employ dynamic subgraph generator during the preprocessing phase, which dynamically computes the subgraph. We substitute ELPH with BUDDY from [16] in this evaluation, since BUDDY exhibits better time efficiency compared ELPH. For both BUDDY and proposed methods, we initially propagate the node features and signatures just once at the onset of inference. These are then cached for subsequent scoring sessions.
D.4 Software and hardware details
We implement MPLP in Pytorch Geometric framework (52). We run our experiments on a Linux system equipped with NVIDIA A100 GPU with 80GB of memory.
D.5 Time Complexity
The efficiency of MPLP stands out when it comes to link prediction inference. Let's denote as the number of target links, the maximum node degree, the number of hops compute, and F as the dimension count of node signatures.
For preprocessing node signatures, MPLP involves two primary steps:
1. Initially, the algorithm computes all all- pairs unweighted shortest paths across the input graph to acquire the shortest-path neighborhood No for each node. This can be achieved using BFS approach for each node, with time complexity of ((V))
2. Following this, MPLP propagates the QO vectors through the shortest-pali patt neighborhood, which has complexity of Ottd (ttd"F) F), and then caches these vectors in memory.
19

---

During online scoring, MPLP performs the inner product operation with a complexity of ((tF), enabling the extraction of structural feature estimations.
However, during training, the graph's s structure might vary depending on the batch of target links due the shorteut removal operation. As such, MPLP proceeds in three primary steps:
1. Firstly, the algorithm extracts the r-hop induced subgraph corresponding these target links. In essence, we deploy a BFS starting at each node of the target links to determine their receptive fields. This process, conceptually similar message-passing but in reversed message flow, has a time complexity of (ldr).. Note that, different from SEAL, we extract r-hop subgraph induced from a batch of target links.
2. To identify the shortest-path neighborhood N we simply apply sparse-sparse matrix multiplications of the adjacency matrix to get the s-power adjacency matrix, where s rr Due to the sparsity, this takes (d')...
3. Finally, the algorithm engages in message-passinn to propagate the QO vectors along the shortest-par path neighborhoods, with complexity of O(td F). followed by performing the inner product at (tFF).
Summing up. the overall time complexity for MPLP in the training phase stands at O(tdr + [V[d" td" F).
For MPLP+, it does not require the preprocessing step for the shortest-path neighborhood. Thus, the GNNs, O(td" F).
time complexity is the same as any standard
D.6 Hyperparameters
We determine the optimal hyperparameters for our model through systematic exploration. The setting with the best performance on the validation set is selected. The chosen hyperparameters are as follows:
Number of Hops (r): We set the maximum number of hops to r = 2. Empirical evaluation suggests this provides optimal trade-off between accuracy and computational efficiency.
Node Signature Dimension (F): The dimension of node signatures, F, is fixed at 1024, except for Citation2 with 512. This configuration ensures that MPLP is both efficient and accurate across all benchmark datasets.
The minimum degree of nodes be considered hubs (b): This parameter indicates the minimum degree of the nodes which are considered as hubs to one-hot encode in the node signatures. We experiment with values in the set [50, 100, 150).
Batch Size (B): We vary the batch size depending on the graph type: For the 8 non- attributed graphs, we explore batch sizes within [512, 1024]. For the attributed graphs coming from [51), we search within [2048, 4096). For OGB datasets, we use 32768 for Collab and PPA, and 261424 for Citation2.
More ablation study can be found in Appendix F.4.
E Exploring Bag-Of- Node Attributes
In Section 3 we delved into the capability of GNNs to discern joint structural features, particularly when presented with Quasi-Orthogonal (QO) vectors. Notably, many graph benchmarks utilize text data to construct node attributes, representing them Bag-Of-Wal Words (BOW). BOW is method that counts word occurrences, assigning these counts as dimensional values. With large dictionary, these BOW node attribute vectors often lean towards QO due to the sparse nature of word representations. Consequently, many node attributes in graph benchmarks inherently possess the QO trait. Acknowl- edging GNNs' proficiency with QO vector input, we propose the question: Is it the QO property or the information embedded within these attributes that significantly impacts link prediction in benchmarks? This section is empirical exploration of this inquiry.
20

---

1.0
Photo
1.0
Collab
1.0
0.6
0.6
0.6
0.2
0.2
0.2
Figure 7: Heatmap illustrating the inner product of node attributes across CS, Photo, and Collab datasets.
1.0
Photo
1.0
QO vectors
1.0
0.6
0.6
0.6
0.2
0.2
0.2
Figure 8: Heatmap illustrating the inner product of node attributes, arranged by node labels, across CS and Photo. The rightmost showcases the inner product of QO vectors.
E.1 Node Attribute Orthogonality
Our inquiry begins with the assessment of node attribute orthogonality across three attributed graphs: CS, Photo, and Collab. CS possesses extensive BOW vocabulary, resulting in node attributes spanning over 8000 dimensions. Contrarily, Photo has comparatively minimal dictionary, encompassing just 745 dimensions. Collab, deriving node attributes from word embeddings, limits to 128 dimensions.
For our analysis, we sample 10000 nodes (7650 for Photo) and compute the inner product of their attributes. The results are visualized in Figure 7 Our findings confirm that with larger BOW dimension, CS node attributes closely follow QO. However, this orthogonality isn't as pronounced in Photo and Collab espeiall Collab, where word embeddings replace BOW. Given that increased node signature dimensions can mitigate estimation variance (as elaborated in Theorem 3.2) one could posit GNNs might offer enhanced performance on CS, due its extensive BOW dimensions. Empirical evidence from Table supports this claim.
Further, in Figure g we showcase the inner product of node attributes in CS and Photo, but this time, nodes are sequenced by class labels. This order reveals that nodes sharing labels tend to have diminished orthogonality compared to random pairs potential variance amplifier in structural feature estimation using node attributes.
E.2
Role of Node Attribute Information
To discern the role of embedded information within node attributes, we replace the original attributes in CS, Photo, and Collab with random vectors denoted as random fear. These vectors maintain the original attribute dimensions, though each dimension gets randomly assigned values from {-1, 1}. The subsequent findings are summarized Table 6. Intriguingly, even with this "noise" as input, performance remains largely unaltered. CS attributes appear to convey valuable insights for link predictions, but the same isn't evident for the other datasets. In fact, introducing random vectors to Computers and Photo resulted in enhanced outcomes, perhaps due to their original attribute's
21

---

Table 6: Performance comparison of GNNs using node attributes versus random vectors (Hits @ 50). For simplicity, all GNNs are configured with two layers.
CS
Physics
Computers
Photo
Collab
GCN GCN(random feat)
66.00+2.90
23.71
22.95+10.58
28.141
35.53+2.39
51.6742.70
69.55+2.45
35.86+3.17
46.8442.58
17.25
SAGE SAGEorandom feat)
57.79
74.10:2.51
1.86
5.70+10.15
36.82
11.78++1.2
64.71#3.05
29.23=3.92
39.94+3.11
28.87 #2.3
Random feat
GCN(F = 1000)
3.73
49.28+2.74
36.92+3.36
48.7243..
31.93=2.10
GCN(F 2000)
24.97+2.67
49.13#44.44
40.24+3.04
53.49+3.50
40.16#1.70
GCN(F -3000)
39.51+6.17
53.76+3.85
42.33+3.82
56.27+3.17
47.22=1.60
GCN F 4000)
43.2313.37
61.86:14.10
42.85-13.60
56.87
50.40
GC 5000)
48 18.2543.28
63.1944.31
44.52+2.78
58.13+3.79
52.13+1.02
GC = 6000)
51.44+1.50
65.10#4.11
44.90:22.74
58.10+3.35
53.78 10.84
GC 7000)
52.00+1.74
66.76+3.32
45.11+13.9
57.41+2.62
55.04+1.00
GCN(F 8000)
54.2113.47
69.27
44.47=4.11
58.6743.90
55.36=1.15
GCN(F = 9000)
53.1642.80
70.79+2.83
45.03=3.13
57.15+3,87
OOM
GCN(F 10000)
55.9142.63
71.88
45.26-11.4
58.12+2.54
OOM
insufficient orthogonality hampering effective structural feature capture. Collab shows a performance drop with random vectors, implying that the original word embedding can contribute more to the link prediction than structural feature estimation with merely 128 QO vectors.
E.3 Expanding QO Vector Dimensions
Lastly, we substitute node attributes with QO vectors of varied dimensions, utilizing GCN as the encoder. The outcomes this experiment are cataloged in [Talle 6 What's striking is that GCNs, when furnished with lengthier random vectors, often amplify link prediction results across datasets, with the exception of CS. On Computers and Photo, GCN even rivals our proposed model (Table 2). potentially attributed to the enlarged vector dimensions. This suggests that when computational resources permit, expanding our main experiment's node signature dimensions (currently set at 1024) could elevate our model's performance. On Collab. the performance increases significantly compared to the experiments which are input with 128-dimensional vectors, indicating that the structural features
critical for Collab than the word embedding.
F
Additional experiments
F1
Node label estimation accuracy and time
In Figure 5] we assess the accuracy of node label count estimation. For ELPH, the node signature dimension corresponds the number MinHash permutations. We employ a default hyperparameter setting for Hyperloglog, with 8, configuration that has demonstrated its adequacy in [16]. For time efficiency evaluation, we initially propagate and cache node signatures, followed by performing the estimation.
Furthermore, we evaluate the node label count estimation for #(2, 2) and #(2, 0). The outcomes detailed in Figure 9 While MPLP consistently surpasses ELPH in estimation accuracy, the gains achieved via one-hot hubs diminish for #(2, 2) and #(2, 0) relative to node counts shortest-pai distance of 1. This diminishing performance gain can be attributed to our selection criteria for one-hot encoding, which prioritizes nodes that function as hubs within a one-hop radius. However, one-hop hubs don't t necessarily serve two-hop hubs. While we haven't it identified a performance drop for these two-hop node label counts, an intriguing avenue future research would be to refine variance reduction strategies for both one-hop and two-hop estimations simultancously.
22

---

MSE of Estimation for #
MPLP wo One hot Hubs
MSE Estimation for # (2200)
MPLP
10a
Estimation Time
10a
10a
100
1000 2000
3000
4000
1000
2000
3000
4000
203
502
B20
100:
1500
2000
3000 1500 6000
Signature Dimension
Signature Dimension
Signature Dimension
Figure 9: MSE of estimation for #(2, #(2, 0) and estimation time Collab. Lower values are better.
Table 7: Ablation study on non-attributed benchmarks evaluated by Hits@50, The format is average score + standard deviation. The top three models are colored by First, Second, Third.
Yeast
Cale
Power
w/o Shortent removal
80.9413.4s
85.47.2200
49.51
82.62.c..
57.51
19.09_a.54
36.67.10.0
70.041134
One-hot habs w/o Norm rescaling MPLP
04
79.07=2.4
85. 2.
89.34.2.79
52.50.2m
83.01:1000
64.81
29 29.0012.m0
50 53
79.36.2
85. 19.4.0
89 50..882..00
52.8/1es.59
85. 85.11=0.02
67.97
29. 29.544177
51.01::408
79.35+a
Regarding the efficiency of estimation, MPLP consistently demonstrates superior computational effi- ciency contrast to ELPH. When we increase the node signature dimension to minimize estimation variance, ELPH's time complexity grows exponentially and becomes impractical. In contrast, MPLP displays sublinear surge in estimation duration.
It's also worth noting that ELPH exhausts available memory when the node signature dimension surpasses 3000. This constraint arises as ELPH, while estimating structural features, has to cache node signatures for both MinHash and Hyperloglog. Conversely, MPLP maintains efficiency by caching only one type of node signatures.
F.2 Model enhancement ablation
We investigate the individual performance contributions of three primary components in MPLP: Shortcut removal, One-hot hubs, and Norm rescaling. To ensure a fair comparison, we maintain consistent hyperparameters across benchmark datasets, modifying only the specific component under evaluation. Moreover, node attributes are excluded from the model's input for this analysis. The outcomes of this investigation are detailed in Table and Table
Among the three components, Shortcut removal emerges as the most pivotal for MPLP. This highlights the essential role of ensuring the structural distribution of positive links is aligned between the training and testing datasets (29].
Regarding One-hot hubs, while they exhibited strong results in the estimation accuracy evaluations presented Figure and Figure their impact on the overall performance relatively subdued. We
Table 8: Ablation study attributed benchmarks evaluated by H5t The format is average score + standard deviation. The top three models are colored by First, Second, Third.
CS
Physies
Computers
Photo
Collab
w/o Shorteut removal
41.6347.27 27
62.58+2.40
32.74+3.03
52.09+2.52
60.45-1.44
w/o One-hot hubs
65.4944.28
71.58+2.28
0..0
55.63=2448
65.07
w/o Norm rescaling
65. 65.2012.82
67.73
13.8313.24
52.59.3.57
03.99.0.59
MPLP
65.70+3..8
71.03:3.55
37.56+3.57
55.63#2.48
66.07
23

---

Table 9: The mapping between the configuration number and the used structural features in MPLP.
Configurations
#(1,)
#(1,2)
#(1,0)
#(2,2) 2)
#(2,0)
# #(A)
(1)
(2)
(3)
(4)
55)
(11)
(12)
(13)
(14)
(15)
Table 10: Ablation analysis highlighting the impact of various structural features on link prediction. Refer Table 9 for detailed configurations of the structural features used.
Configurations
USAir
NS
PB
Yeast
C.ele
Power
Router
E.coli
(1)
76.61=26.74
26 79
13.30
58.70+30.50
46. 24.
14.40=1140
17.20 17.29
60.10 00.10=:00.e0
(2)
62.54:461
84.76=4.68
45.84
80.56g0.s es
56. 26..22:0033
21.38
48.97
67.78-29988
(3)
67. 67.76=23.6
70.00 -5.05
44.81#2.68
67 02
36 19.66
25.24
21 12.3222.66
56. 1:78
37.18
25.13=1.90
12.35
1.42=10.80
18.75:.8.00
5.47=1.18
30.47:3.10
34.90=30.dd
(5)
86.24 26.24=2270
84.91 14.91=2.00
48.35:13.76
84.42:0 56
66.69133.0
22.25:1:59
49.68
80.94.1.42
(6)
77.41=5.27
11.0002200 29
46.05+22.76
74.70=1.46 45
68.6.70
27.754
22.37
71.41=2.47
(7)
71. 11:15:55555
76.72 70.77
43.57:13.00
73.08
24.99:20..14
1..5
31.26
(8)
80.16:4.82
58. -7
52 16
82.52=0.5
63 13.622:4.02
28. 21.000
+0.97
77 17.266=1..1
75.13
87.28.33.5
80.84:0.9r
60.63::4.54
23.85
49.78
1.81
(10)
76.82=426
77. 77.011:3.70
45. 22.2777
67 07.31=3.20
11.66:13.4
26.9 26.95+1.47
28.31
70.14=0.77
(11)
82.82=5.52
88.91 68.91=2.90
52.57+33.05
84.61
67.11s2.62
28.98
50.63
80.16:2.20
(12)
87 $7.29-1.05
08-22.9
18.86+3.42
8.1.99
66. 06
23.79+1.57
50.06:3.00
79. 79.57=2.46
(13)
78.21=274
58 08:0..2
46.00s2.a1
74.88=2.4 49
54.644:4.00
28. 08.82.1.29
26.24#2.18
74.67=a..0
(14)
89.14-2.38
51.631287
82.6820..5
63.01:3321
29.4111:54
51.0814.12
76.88:1.60
(15)
81.06=6.62
$9.73=2.12
83.19:2.00
85.0620.es
66.41=a..0
28.86+2.40
50.63+3.79
78.91=2.68
hypothesize that, the context of these sparse benchmark graphs, the estimation variance may not be sufficiently influential on the model's outcomes.
Finally, Norm rescaling stands out as significant enhancement MPLP. This is particularly evident in its positive impact on datasets like Yeast, Physics, Photo, and Collab.
F.3 Structural features ablation
We further examine the contribution various structural features to the link prediction task. These features include: #(1, 1), #(1, #(1, 0). #(2, 2), #(2, 0), and #( To ensure fair comparison, we utilize only the structural features for link representation, excluding the node representations derived from GNN(... Given the combinatorial nature of these features, they grouped into four categories:

---

Table 11: Ablation study of Batch Size (B) non-attributed benchmarks evaluated by Hits @ 50. The format is average score + standard deviation. The top three models are colored by First, Second, Third.
USAir
PB
Yeast
Ceele
Power
Router
E.coli
M 256)
90.31
88.9812.44
$1.14.244
84.07.0.m
71.59 11.591223
28.92.11
56. 15.11
85.12 1.
MPLP 512)
40
89.40:2212
49.63:2.us
84.17:u.00
71.72:8.35
66
84.72:1.44
M 1024)
90. 30.19+2.22
88. 88.19-2.84
30.60+4.40
83. 67=0.07
70 70.61=4.11
28 63 0:
19.75=5.14
8 8/152=11os
B 2048)
81.20=a.50
61.79=18.05
50.34+3.05
76.79a6.79
31.79=10.as
28.45=1.88
49.37=3.89
84-431.25
MPLP(B 4096)
$1.20.2..0
61.79118.55
52.59.2.3
58.26,7.20
31.54_11:55
27.25
50. 20.26.444
85, 15
B 8192)
21.2012a0
26.20121.34
51.91
24.47.221.12
31.79.19.4
17.22as:17
38.6717.76
10.67
#(1,
#(1,2), #(1,0):
#(2,2), #(2, 0); #(A).
The configuration of these structural features and their corresponding results are detailed in Table and Table 10
Our analysis reveals that distinct benchmark datasets have varied preferences for structural features, reflecting their unique underlying distributions. For example, datasets PB and Power exhibit superior performance with 2-hop structural features, whereas others predominantly favor 1-hop features. Although #11,1), which counts Common Neighbors, is often considered pivotal for link prediction, the two other 1-hop structural features, #(1, 2) and #(1, 0), demonstrate more pronounced impact on link prediction outcomes. Meanwhile, while the count of triangles, #(A), possesses theoretical significance for model expressiveness, it seems less influential for link prediction when assessed in isolation. However, its presence can bolster link prediction performance when combined with other key structural features.
F.4 Parameter sensitivity
We perform an ablation study to assess the hyperparameter sensitivity of MPLP, focusing specifically on two parameters: Batch Size (B) and Node Signature Dimension (F).
Our heightened attention to B stems from its role during training. Within each batch, MPLP executes the shorteut removal. Ideally, if B 1, only one target link would be removed, thereby preserving the local structures of other links. However, this approach is computationally inefficient. Although shorteut removal can markedly enhance performance and address the distribution shift issue (as elaborated in Appendix F.2). it can also inadvertently modify the graph structure. Thus, striking a balance between computational efficiency and minimal graph structure alteration essential.
Our findings are delineated in Table 1T Table 12, Table 13] and Table 14 Concerning the batch size, our results indicate that opting for smaller batch size typically benefits performance. However, this size is increased past a certain benchmark threshold, there can be a noticeable performance drop. This underscores the importance of pinpointing optimal batch size for MPLP. Regarding the node signature dimension, our data suggests that utilizing longer QO vectors consistently improves accuracy by reducing variance. This implies that, where resources allow, selecting a more substantial node signature dimension is consistently advantageous.
G Theoretical analysis
G.1 Proof for Theorem 3.1
We begin by restating Theorem and then proceed with its proof:
Let G (V. E) be a non-attributed graph and consider 1-layer GCN/SAGE. Define the input vectors X E NxF initialized randomly from zero-mean distribution with standard deviation node- Additionally, let the weight matrix W FRFxxx XF be initialized from zero-mean distribution with standard deviation tweight. After performing message passing, for any pair of nodes ((u, (u, v) V x V E}, the expected value of their inner product is given by:
25

---

Table 12: Ablation study of Batch Size (B) attributed benchmarks evaluated by Hits@50. The format is average score + standard deviation. The top three models are colored by First, Second, Third.
CS
Physics
Computers
Photo
MBLP(B 256)
74.96+1.87
76.06+1.47
43.38-2.83
57.58:22.2
MPLP(B 512)
75.61+2.25
75.38+1.79
42.95=2.56
57.19
MPLP(B 10024)
74.8942200
74.89
42.69-2.41
13.97
MPLP(B - -0048)
75.02+2.68
75.4741.68
41.39=2.87
55.89+3.03
MPLP(B = -4996
75.4641.78
74.88+2.57
40.65-2.85
55.89
MPLP(B 8192)
75.2611.91
74.14
40.00=3.40
55.90+2.52
Table 13: Ablation study of Node Signature Dimension (F) non-attributed benchmarks evaluated
by Hits@50. 50. The format is average score + standard deviation. The top three models are colored by First, Second, Third.
USAir
PB
Yeast
C.ele
Power
Router
E.coll
EPLP(E 256)
90.64:2 su
88.521:.07
30.42:3:.5
80.633u.s4
70.8914.70
25.74:1.5M
51.84.1200
84.60 04.601...
MPLP 90.49::105
27.58s180
MPLP(F 1024)
90. 90.16=1:01
89.10-2.12
30.60=a.40
83 13.87=1100
70.61=4.18
28 88=2
53 33.92=2.88
84.81
MPLP(E 2018))
90.14#224
29.27=1:92
81..8L
MPLP(E 1096)
39.96+11.88
89.5-1-2.2
51.07=2.87
8/1 11.80.0.
71.91=8.12
29 1.
54.71=6.07
=1.667
For GCN:
E(hu h2)
C
E
v dud keNu N.C. di"
For SAGE:
C
Eihh. h.)
1,
dduch keN, NN.
where d, d, and the constant C' is defined C 0 mode weight F.
and W as (W1, W..... WF). Using GCN as the MPNN, the node representation is updated by:
Proof. Define X as (X
h W
k.
dxdu
where d, d,
Table 14: Ablation study of Node Signature Dimension (F)) on attributed benchmarks evaluated by
Hits 50. The format is average score + standard deviation. The top three models are colored by First, Second, Third.
CS
Physics
Computers
Photo
MPLP(F 256)
74.90+1.88
73.91
40.6543.24
55.13
MPLP(F -512)
74.67+2.63
74.49=2.05
39.36+2.28
55.93
MPLP(F -1024)
75.02+2.68
75.27+2.95
42.27=3.96
55.89+3.03
MPLP(F -2048)
75.30+2.14
75.82+2.15
41.98-18.21
57.11+2.56
MPLP(F -4096)
76.0441.57
76.1742.04
43.33-2.98
58.55+2.47
26

---

For any two nodes (u, v) from ((,,,) E V X V E). we compute:
hag h h hw
W
Xa
W
Σ
Xb.
du
V dodeo
bEN())U(e)
Σ
W
Σ
X
aEN(u)ufu) vdddu
Vddd,
W W1
W.
E aEN(u)Ufu} V dodu
X
Xs.
BEN())Ufe} V dodd
W W1
W WF
Given that
E W. W) o weight F" when i = J.
2. E W. W, when + j.
we obtain:
B(h hn) o²
weight
Σ
Σ
X
Vdgda bEN(e)U()) v dodg
(EN(U))(M))
Also the orthogonal of the random vectors guarantee that [ X₂) 0 when b. Then, have:
EE hw) Vando KEN N.N.
C
Σ
1
de
o where C= o mode weight FF.
This completes the proof for the GCN variant. A similar approach, utilizing the probabilistic orthogonality of the input vectors and weight matrix, can employed to derive the expected value for SAGE the MPNN.
G.2 Proof for Theorem 3.2
We begin by restating Theorem 3.2 and then proceed with its proof:
Let G = (V, E) be a graph, and let the vector dimension given by F E N4. Define the input vectors X = (Xis), which are initialized from random variable x having mean of 0 and standard deviation of VF. Using the message-passing described by Equation 3 for any pair of nodes {(u, u), v) E x VJ, the expected value and variance their inner product are: E(h, hv) = CN(u, v),
Var(h. h.) (dude + CN(u, 2CN(u, u)) + FVar(x3)CN(((
Proof. We follow the proof of the theorem in 12]. Based on the message-passing defined in Equa- tion 3
-E((
Σ Xkm.
Σ Xkons)
E(h. hw) =
V.EN
= Σ
Σ
X XK...Kou
KN, K.ENS
Σ
Σ
(X Xhoa).
A.EN, K.EN.
27

---

Since the sampling of each dimension is independent of each other, we get:
F
Blh ho) = Σ
KN R,E. i=1
When hy kis
: =E(x²) 1
When ku # kin
E(X Ku, ( (R.it) B(Xe,.)))) 0.
Thus:
E(h ho) = Σ Σ
(Kiu = kw) F
kuEN E.,,,, i=1
Σ kEN.
1= 1= CN(uu))
For the variance, we separate the equal from non-equal pairs k2 and k,. Note that there is no covariance between the equal pairs and the non-equal pairs due to the independence:
Var(h. ho) = Var
ΣΣ Eo i=1
Σ
Mu ENu
F
Var
Σ
Σ
i=1
Eu KoENN
F
XbureXkun kond ))
Σ
Var Σ
x)
+ Var
Σ
E
==1
WEN.N.
KoEN koEN
For the first term, obtain:
Var
Σ
x² x²
Var (xNux))))(,,u)
KEN
For the second term, further split the variance of linear combinations to the linear combinations of variances and covariances:
Var Σ Σ
= E
Σ
Kv koENo
ls ENEN he ENoo
Σ
Σ
Kov(XKniiXaae Xa.i Xo,i).
(EA. BENu BENU ((kma))
Note that the Cov(Xa, i XR.nis Na, (t,)) is a F otherwise O.
1
when (kins kin) (b.a). a), and
Thus, we have:
Var Σ Σ
(dud, + CN(u, 2CN(u, F2
A.EN &. ENN.
and the variance is:
Var Var h.) = F (dnd, + CCN(u, v)² 2CN(U, u)) + "Var(x3)CN(uu,
28

---

G.3
Proof for Theorem 3.3
We begin by restating Theorem and then proceed with its proof:
Under the conditions defined in Theorem 3.2 let h denote the vector for node u after the 1-th
message-passing iteration. We have:
E
h (1))
walks (k:, walks/ (A: e)},
KEV
where [walks u)] counts the number length-/ walks between nodes u and v.
we can equivalently express it Proof. Reinterpreting the message-passing described in Equation 3 as:
ms!
((+1)
U NEN.
m h h(+1)=
Σ
h
(9)
wEms (1+1)
where ms!" refers multiset, union of multisets from its neighbors. Initially, ms! {(u}}. The node vector (1) is derived by summing the initial QO vectors of the multiset's elements.
We proceed by induction: Base Case (1 = 1):
U NEN.
m
U [fu}} {[k|w walks ()) b)}} MEN.
Inductive Step (1 1): Let's assume that ms! {&/w e ( (k)))) holds true for an arbitrary 1. Utilizing Equation 9 and the inductive hypothesis, we deduce:
ms (1+1)
U {fklw e walks u)}}.
wEN.
& initiates the lllegghh walks terminating at v and if is adjacent to u, then k must similarly initiate the l-length walks terminating at This consolidates our inductive premise.
With the induction established:
E
(p)
h(
E
Σ
Σ
hike
(0)
Ems
Ems
The inherent independence among node vectors concludes the proof.
H Limitations
Despite the promising capabilities of MPLP, there are distinct limitations that warrant attention:
Training cost vs. inference cost: The computational cost during training significantly outweighs that of inference. This arises from the necessity to remove shortcut edges for positive links the training phase, causing the graph structure to change across different batches. This, in turn, mandates repeated computation of the shortest- -aatt neighborhood. Even though MPLP+ can avoid the computation of the shortest-path neighborhood for each batch, it shows suboptimal performance compared MPLP. potential remedy is to consider only a subset links in the graph as positive instances and mask them, enabling a single round of preprocessing. Exploring this approach will be the focus of future work.
2. Estimation variance influenced by graph structure: The structure of the graph itself can magnify the variance of estimations. Specifically, in dense graphs or those with a high concentration of hubs, the variance can become substantial, thereby compromising the accuracy of structural feature estimation.
3. Optimality of estimating structural features: Our research demonstrates the feasibility of using message-passing passing to derive structural features. However, its optimality remains undetermined. Message-passing by nature, involves sparse matrix multiplication operations, which can pose challenges terms of computational time and space, particularly for exceedingly large graphs.
29

---

I
Broader Impact
Our study is centered on creating a more efficient and expressive method for link prediction, with the goal of significantly advancing graph machine learning. The potential applications of our method are diverse and impactful, extending recommendation systems, social network analysis, and biological interaction networks, among others. While we have not identified any inherent biases in our method, we acknowledge the necessity rigorous bias assessments, particularly when integrating our method into industrial-scale applications.
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims made in abstract and introduction clearly reflect the contribution.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitation discussed in Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect 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 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 images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't '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 to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
31

---

Justification:
The proof is rigorously shown in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear 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 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: The experimental details are extensively discussed in the main body and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make 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 one good way accomplish this, but reproducibility can also be provided via detailed 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, or other means that are appropriate to the research performed.
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) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is 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 or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
32

---

Answer: [Yes]
Justification:
The code and data are publicly available. The code is open source.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipps.cc/pullic//uuii wwwpc//ggue////eeeeceooc CoodeSubeiiieeeec ssi wsionnolli onnolicy)))) 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, etc.
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 possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental settings are discussed the main body and the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of 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, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
The error bars are clearly reported in the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support 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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call 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 the standard error of the mean.
33

---

It is OK to report 1-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 enrors 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 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 on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The compute resource is discussed in Appendix D.4
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: h/tppr//////riss..//// httpp//bllt//tcccccccieeeeeeeeee
Answer: [Yes]
Justification: Yes, the research conforms with the NeurIPS Code of Ethics.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Broader impact is discussed in Appendix
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., 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
34

---

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.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition 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: This study is not feasible for safeguards.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: is all properly cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package 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 (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee wwworeewwthhhe....c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
35

---

Answer:
[NA]
Justification: No new asset is introduced.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/coddemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
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 as details about compensation (if any)?
Answer: [NA]
Justification: No crowdsourcing experiments research with human subjects used in this study.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in 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 in 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 or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human participants in this study.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending 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 we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
36


Reviews:
[{"review_id": "gqcLg8v8yQ", "reviewer": "Reviewer_L71H", "summary": "This paper first shows that pure message passing can count common neighbor. Based on the proposed theory, this paper develops MPLP  for link prediction, where the common neighbor is an important heuristic feature. Experiments on link prediction demonstrate the performance gains of MPLP over baselines.", "questions": "See Weaknesses.", "limitations": "The authors have adequately addressed the limitations.", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This paper shows that pure message passing can count common neighbor.\n2. The paper is well-written.\n3. The authors provide the theoretical analysis and experimental details.", "weaknesses": "1. If MILP aims to count the common neighbor exactly, why not directly use the pre-computed common neighbor? If MILP aims to develop a neural network to approximate common neighbor heuristics, what is the novelty of MILP compared with [1]?\n2. To capture structural link representation such as Common Neighbors (CN),  Zhang et al. [2] propose labeling trick, which is a position encoding in my opinion. Indeed, the Quasi-orthogonal vector is also a position encoding. I suggest discussing the relationship between Quasi-orthogonal vectors and existing position encodings such as random walk position encodings (RWPE), relative random walk probabilities (RRWP) [3], Resistance Distance encodings [4], and Laplace position encodings (LapPE). Notably, Laplace position encodings are also orthogonal.\n3. Is MILP scalable to large-scale graphs? If MILP assigns each node with a unique orthogonal vector, then the orthogonality requires the dimension of the orthogonal vector to be larger than the number of nodes, as the orthogonal vectors are linearly independent.\n\n\n\n[1] Neural Common Neighbor with Completion for Link Prediction.\n\n[2] Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning.\n\n[3] Graph Inductive Biases in Transformers without Message Passing.\n\n[4] Rethinking the Expressive Power of GNNs via Graph Biconnectivity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback. We will address the following points in the rebuttal:\n\n## W1\nWe apologize for any confusion regarding MPLP. MPLP aims to count the number of nodes at varying distances from a target node pair. Compared to pre-computed heuristics like Common Neighbor, MPLP is significantly more efficient in terms of both time and space complexity. In a graph with $N$ nodes, pre-computed common neighbors require $O(N^2)$ space to store all pairwise information, whereas MPLP only requires linear space $O(NF)$, where $F \\ll N$ represents the node signature dimension. Regarding time complexity, MPLP can be seen as an approximation of the labeling trick[2], trading off variance for efficiency. Generally, MPLP is more scalable for large-scale graphs.\n\nUnlike NCN[1], MPLP considers not only the common neighbors but also the nodes beyond the 1-hop neighborhood. This makes MPLP more expressive and powerful in capturing structural representation than NCN. The experimental results in our paper demonstrate the effectiveness of MPLP in link prediction tasks.\n\n## W2\nWe appreciate the reviewer's suggestion. In fact, our quasi-orthogonal (QO) vectors are used to build a link **structural** representation rather than **positional** encoding [5]. There are distinct differences between position encoding and our QO vectors:\n\n1. Unlike typical position encodings[3,4] designed for graph-level tasks, our QO vectors are specifically targeted for link prediction tasks. Position encodings represent the relative position of each node in the graph, whereas our QO vectors cannot represent individual node positions but can be decoded to represent pairwise **structural representation** for link prediction tasks.\n\n2. When applying position encodings to link prediction tasks, most of them are limited to transductive settings. This is because position encodings represent node position within a specific graph. If graph changes, the position encodings should also change. However, our QO vectors can be decoded as a structural representation and applied in both transductive and inductive settings.\n\nWe will add a detailed comparison between QO vectors and position encodings in the revised version.\n\n## W3\nWe apologize for any confusion regarding the scalability of MPLP. MPLP is designed to have greater scalability for large-scale graphs compared to methods like labeling tricks[2]. Each node is assigned a random **quasi-orthogonal** vector of dimension $F \\ll N$. These vectors do not need to be strictly orthogonal but should be orthogonal in expectation. Therefore, MPLP is scalable for large-scale graphs.\n\n\n[1] Neural Common Neighbor with Completion for Link Prediction.\n\n[2] Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning.\n\n[3] Graph Inductive Biases in Transformers without Message Passing.\n\n[4] Rethinking the Expressive Power of GNNs via Graph Biconnectivity.\n\n[5] On the Equivalence between Positional Node Embeddings and Structural Graph Representations.\n\n----\n\n**We hope that we have addressed your concerns, and that you will consider raising your score. If we have left any notable points of concern unaddressed, please let us know, and we will be happy to respond.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VSee6b4nNZ", "reviewer": "Reviewer_h157", "summary": "The authors of this work introduce the Message Passing Link Predictor (MPLP), a link prediction model that uses pure message passing - as originally proposed by Gilmer et al. - to estimate structural similarities between nodes. The method is motivated by the fact that a single round of message passing using one-hot-encodings of nodes in un-attributed graphs can be used to estimate the common neighbors between node pairs. This idea is used to develop MPLP, a novel link prediction model that uses message passing to construct quasi-orthogonal vectors, whose inner product can be used to efficiently estimate structural similarities. Combining those vectors with node features and shortest path neighborhoods, MPLP obtains node representations that can be used by a classifier to predict links. Moreover, an advanced model MPLP+ is proposed with a simplified estimation of shortest path neighborhoods based on multiple rounds of message passing using one-hop information only. The two resulting models are evaluated in eight unattributed and seven attributed graphs, showing excellent performance compared to nine baseline methods.", "questions": "[Q1] Referring to W1, what would happen if we assume that the weight matrix is absent, i.e. if we remove the weight parameters in the aggregation function?\n\n[Q2] Related to W2, how does the training time of the proposed models compare to those of the baseline methods?\n\n[Q3] I understand that the authors followed the evaluation metrics of OGB. Nevertheless, it would be good to include additional evaluation metrics such as accuracy, AUC-ROC or AUPR, see e.g. [arXiv 1505.04094].", "limitations": "The paper includes a detailed discussion of limitations in section H of the appendix, which I consider sufficient for this work.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "[S1] Showing that a single round of neural message passing in a Graph Convolutional Network (GCN) and SAGE can be used to estimate the number of common neighbors between node pairs, while multiple rounds of message passing can estimate the number of walks between node pairs, this work provides interesting insights into the design of Graph Neural Networks, as well as its inherent relations to heuristic link prediction techniques.\n\n[S2] The work includes both theoretical and practical insights that make it interesting for a wide range of researchers and practitioners in graph learning.\n\n[S3] The two proposed models are extensively evaluated in large attributed and unattributed graphs, showing promising performance across a wide range of data dets from different contexts.\n\n[S4] The inference time of both proposed models and baseline methods is compared across three large data sets from the OGB benchmark, demonstrating that despite its improved performance the proposed methods are actually more efficient than some of the baseline methods. \n\n[S5] In the appendix, the authors included extensive ablation studies in which they investigated the impact of different structural estimators, the sensitivity to parameter values, and the impact of removing specific components of the architecture.\n\n[S6] The paper is very well-written, clearly motivating the problem and giving a good intuition of the proposed approach. I enjoyed reading this work, although some of the math in the appendix is hard to follow for non-specialists.", "weaknesses": "[W1] I could not follow the role of the weight matrix W, which is assumed to be randomly initialized from a zero-mean distribution, in theorem 3.1, see Q1.\n\n[W2] The experimental evaluation does not include results on the training time of the different models. \n\n[W3] The evaluation is solely based on HITS@50, see Q3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first want to express our gratitude for the reviewer's comment that the reviewer \"enjoyed reading this work\". For us, it is the most rewarding feedback to know that our work is well-received. We will address the following points in the rebuttal:\n\n## Q1\nThe weight matrix $W$ in theorem 3.1 does not have any specific role for holding the theorem. We just keep it here because the standard GCN/SAGE formulation has the weight matrix. If we remove the weight matrix $W$, the entire theorem will still hold, except that the constant $C$ will be different as $C = \\sigma^2_{node}F$. In other words, the untrained zero-mean-initialized weight matrix $W \\in \\mathbb{R}^{F^{\\prime} \\times F}$ will only introduce a scaling factor to the expectation of the inner product.\n\n## Q2\nWe appreciate the reviewer's suggestion. Generally, it is challenging to provide a fair evaluation of training times for different methods due to variations in learning rates, batch sizes, and early stopping criteria. Since the size of trainable parameters in GNNs is relatively small compared to other deep learning models, training time is usually not a bottleneck. Most of the computational cost in GNNs comes from processing the graph structure (See Table 1 in [7]), such as message passing[1,2] or the labeling trick[3] for link prediction. Therefore, inference time can be used as a proxy for the computational cost of training models. In the Figure 4 of experimental section, MPLP is shown to be more efficient than other methods in terms of inference time, indirectly indicating that MPLP is more computationally efficient than other methods.\n\n## Q3\nWe thank the reviewer for the suggestion. We follow the evaluation protocol of previous works[4,5] to ensure a fair comparison. While we acknowledge that other metrics like AUC-ROC and AUC-PR are important for evaluating link prediction tasks, recent studies[6] have shown that performance evaluated by AUC-ROC and AUC-PR is nearly saturated for most methods. Therefore, we focus on the evaluation of MRR and Hits@K, which are more sensitive to the performance differences between methods.\n\n[1] SIGN: Scalable Inception Graph Neural Networks\n\n[2] Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks\n\n[3] Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning.\n\n[4] Open Graph Benchmark: Datasets for Machine Learning on Graphs\n\n[5] Graph Neural Networks for Link Prediction with Subgraph Sketching\n\n[6] Neural Link Prediction with Walk Pooling\n\n[7] MLPInit: Embarrassingly Simple GNN Training Acceleration with MLP Initialization\n\n\n---\n**We hope that we have addressed your concerns. If we have left any notable points of concern unaddressed, please let us know, and we will be happy to respond.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FBmYIi9QXo", "reviewer": "Reviewer_CYaw", "summary": "This paper studies the problem of encoding pairwise structural features to enhance link prediction (LP). They note that previous literature has shown that standard MPNNs cannot encode the necessary pairwise information needed for LP. The authors argue that with careful design, MPNNs can in fact estimate pairwise structural features (e.g., common neighbors). This is done by equipping each node with quasi-orthogonal vector, which is used to estimate the counts of various structural features between two nodes. The authors then benchmark their method(s) on a number of datasets and compare against prominent benchmarks. They further highlight the efficiency of their method against other methods.", "questions": "1. Can you reproduce Figures 8 and 9 with MPLP+ against BUDDY/ELPH?\n2. Can you better explain why MPLP+ is more efficienct than BUDDY?\n3. Are there any other contributing factors that may lead to MPLP/MPLP+ doing better than a similar method like\n\nOther:\n--------\n\n1. I recommend including the results of BUDDY in the main tables. I know you include ELPH and it typically does better, but it gets confusing when the results are for ELPH but the efficiency for BUDDY. I think it'll just make the experiments section easier to read.", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and easy to understand. I think the motivation and the design of the method is explained quite clearly.\n2. The problem itself is an important one. Recently, many methods have been proposed for estimating the pairwise structural information between nodes. However, there is a trade-off between expressivity and efficiency (e.g., SEAL is very expressive but slow while BUDDY or NCN is less expressive but much faster). Balancing these concerns is crucial for enhancing current LP methods as for current methods, those that are expressive tend to be computationally inefficient and vice-versa.\n3. Overall, the performance is good. More so, when one considers the efficiency of MPLP+.", "weaknesses": "Weakness 1:\n----------------\nMy main concern is that I'm unsure why the performance of this method is this good. Let me explain. MPLP estimates the structural counts via the use of quasi-orthogonal vectors. The predictor (i.e., score function), then takes as input (a) the elementwise product of both node representations (outputted by a MPNN) and (b) the estimated structural counts which are of the form #(p, q) such that (1, 1) is CNs. I'm just restating the Eq. at the end of 4.2.  \n\nHowever, **how is this appreciatively different from BUDDY [16]?**. In the score function, they also include the elementwise product of both nodes in the target link. They then concatenate the same kind of structural counts considered by MPLP. They differ only in their method of estimating those counts. BUDDY (and ELPH) use subgraph sketching instead of orthogonal vectors. As such, **I can't seem to understand why MPLP/MPLP+ do so much better than BUDDY** (I know you report ELPH in your tables but it only does marginaly better than BUDDY). If the performance difference was small I wouldn't be as confused, by the gap on some datasets is enormous. For example BUDDY has a 49.85 Hits@100 on ogbl-PPA while MPLP+ is 65.24. A smaller, but still noticeable, gap is present on ogbl-Citation2 with BUDDY at 87.56 and MPLP+ at 90.72. My point is, the different in performance is non-trivial. The authors clearly report that their method can outperform BUDDY.\n\nBut as I noted, there doesn't seem to be anything specific reason why this is occurs, as they are estimating the same information. Is the approximation used by the authors better? If so, then why? The authors seems to argue that in Appendix F.1, where they compare the MSE of the label counts by ELPH/BUDDY and theirs. However, I have a few issues with the results: **(a)** The results aren't very clear to me. For example, is it on all test samples? Positive and negative? **(b)** Also the authors don't specify the # of hops used when estimating the counts for ELPH/BUDDY. From personal experience using their code, I find setting hops=3 can help improve the counts while still being fairly efficient. **(c)** **Most importantly, the authors only compare to MPLP and not MPLP+**. To me, this is a very important point as MPLP+ is itself a comprimise between efficiency and estimation quality. As shown in Table 2, MPLP is impractical on larger datasets as it's OOM. So why not compare the estimation quality of MPLP+, the model which still performs well but can scale to larger graphs? In my opinion it is very important that the authors include MPLP+ in the experiments in Appendix F.1.\n\nI apologize for the wall of text, but the magnitude of increase over BUDDY seems very strange to me. To summarize, I suggest the authors: (a) Giving more explanation as to why the large discrepancy in performance may exist and (b) Include MPLP+ in Figures 8 and 9. I think if the authors can show that MPLP+ still does a much better job at estimating the structural features, that may be the answer. Otherwise, I very strongly recommend the authors try to give any difference that exist between the two methods that can explain it.\n\nWeakness 2:\n----------------\nI find it odd that MPLP+ is more efficienct than BUDDY. MPLP+ and BUDDY both use L layers of message passings. Furthermore, as noted before, the scoring function is similar. The only difference is in estimating the structural counts.  However, BUDDY pre-computes and caches the subgraph counts, so it is qctually quite efficiency as they don't need to be recomputed. This is as opposed to MPLP+ which does have to recompute them each time. Because of this I don't really see how BUDDY can be slower except for various differences in implementation. Because from the theoretical complexity I shouldn't expect BUDDY to be slower. Again, I recommend the authors try to explain why this might be the case.\n\nWeakness 3:\n----------------\nI should have noticed this earlier, but the similarity between MPLP and BUDDY hurts the novelty of the paper. As far as I can see, the authors are proposing a new method that can potentially estimate the structural counts a little better and faster. While noteworthy, this is a small contribution. However, I personally only find this to be a minor weakness of the paper.\n\n\nWeakness 4:\n----------------\nSome benchmark datasets are missing. Including Cora, Citeseer, and Pubmed (see [33]). I recommend including them. Also, for HeaRT, I recommend reporting the results on all datasets and not just ogbl-ppa/collab/citation2. To be clear, this is a very minor weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first want to appreciate the reviewer's extensive feedback, which is extremely valuable to us given the large volume of review loads this year. We also very appreciate the reviewer's positive feedback on the importance of the problem we address, especially acknowledging the importance of trade-off between expressivity and efficiency for link prediction tasks. We will address the following points in the rebuttal:\n\n## W1: Comparison with ELPH/BUDDY\nDue to the space limit, we post this rebuttal as the **\"global\" rebuttal** on the very top of the page. Please refer to the global rebuttal for the detailed response.\n\n## W1 (cont.) Issues about Appendix F.1\nWe apologize for the any confusion in Appendix F.1. In Appendix F.1, we find that ELPH's MinHash/HyperLogLog can introduce a high variance of estimation compared to MPLP. We address the reviewer's concerns as follows:\n\n### For example, is it on all test samples? Positive and negative?\n\nWe report the estimation quality on a set of both positive and negative edges. For positive edges, we use all the training edges. For negative edges, we randomly sample the same number of negative edges as the positive edges. We keep the edges consistent across MPLP and ELPH to ensure a fair comparison.\n\nIn MPLP, we use the shortcut removal technique to avoid the distribution shift problem. For a more fair comparison, we also implement the shortcut removal technique for ELPH in Appendix F.1. We will clarify this in the revised version.\n\n### the authors don't specify the # of hops used when estimating the counts for ELPH/BUDDY.\n\nFor ELPH, we use the node signatures of 2-hop neighbors to get estimations for #(1,1), #(1,0), #(1,2), #(2,2) and #(2,0). Since the estimation variance becomes higher for both MPLP and ELPH at the #(2,2) and #(2,0), we did not report the variance beyond 2-hop neighbors. It is very interesting to learn from the reviewer that setting hops=3 can help improve the performance, where we thought that the variance would be too high to be useful. In our experiments, the performance gain from 3-hop neighbors of MPLP(+) is marginal.\n\n### Most importantly, the authors only compare to MPLP and not MPLP+\n\nMPLP+ is different from MPLP/ELPH/BUDDY in that MPLP+ estimates the number of walks between two nodes rather than the number of nodes like MPLP/ELPH/BUDDY. Therefore, to have an apple-to-apple comparison, we can only compare MPLP to ELPH in Appendix F.1 to evaluate the quality of estimating number of nodes.\n\n## W2\nWe apologize for any confusion about the efficiency of MPLP+. MPLP+ is similar to BUDDY and can also cache the node signature during the inference time. In Appendix D.3, we discuss the detail of benchmarking the inference time for both BUDDY and MPLP+.\n\nWhile theoretically, MPLP+ and BUDDY should have similar efficiency. However, the implementation of two methods causes the efficiency discrepancy. For MPLP(+), we utilize `pytorch_sparse` to implement the message-passing, which is built on [3]. BUDDY utilizes `pytorch_scatter` to implement its message-passing, which is both slower and more memory-hungry compared to the sparse-dense matrix (Spmm) opeartion in MPLP(+).\n\nIn fact, we also submit a Pull Request in BUDDY's Github repo to change its message-passing implementation to Spmm. Even though BUDDY with Spmm shows comparable efficency as MPLP+, it still exhibits higher estimation variance (Appendix F.1.) and lower overall performance (Table 1/2) compared to MPLP(+).\n\n[3] Design Principles for Sparse Matrix Multiplication on the GPU.\n\n\n## W3\nThank you for pointing this out. We discuss in the paper that our link prediction framework shares a similar spirit of learning structural representation as ELPH/BUDDY. However, beyond ELPH/BUDDY, MPLP(+) proposes several distinct components (Shortcut Removal, Norm Scaling, One-hot hubs, walk-based counting) that significantly boost the model performance with a totally different but simple node/walk-estimation mechanism (quasi-orthogonal vectors).\n\n## W4\nWe appreciate the reviewer's constructive suggestion. We do not include the Cora/Citeseer/Pubmed in our main experiment because recent studies[4,5] and we find that these three datasets overwhelmingly rely on the node attributes for link prediction tasks. An MLP without graph structural information can already achieve comparable performance as GNNs on these three datasets. This makes them not sensitive enough between different link prediction methods.\n\nFor HeaRT setting, we will report the results on all datasets in a revised version.\n\n[4] Linkless Link Prediction via Relational Distillation\n\n[5] Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking\n\n## Q1\nPlease refer to rebuttal for W1 (cont.) Issues about Appendix F.1.\n\n## Q2\nPlease refer to rebuttal for W2.\n\n## Q3\nPlease refer to rebuttal for W1.\n\n## Q4\nWe thank the reviewer for the suggestion. We will include BUDDY's results into the main tables to make it more clear.\n\n---\n**Thanks again for your comments and diligence in reviewing our work. We hope our responses have addressed your concerns. If so, we hope that you will consider raising your score. If there are any notable points unaddressed, please let us know and we will be happy to respond.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Reviewers,

We appreciate your valuable feedback and constructive suggestions when reviewing our paper. Here, we want to address a concern raised by **Reviewer CYaw** regarding the difference between MPLP(+) and ELPH/BUDDY[1]:

## W1: Comparison with ELPH/BUDDY
We appreciate the reviewer's question about the difference between MPLP and BUDDY. We agree that the principle of capturing structural information is similar between MPLP and BUDDY. However, there are several key differences between MPLP and BUDDY:

1. **MPLP is more expressive than ELPH/BUDDY due to the flexibility of orthogonal vectors**: Sec 4.1 introduces that MPLP(+) can perform a weighted count with the norm rescaling technique. In general, by scaling the norm of the vectors according to the node degrees, MPLP can capture more nuanced structural information than BUDDY with a weighted counting mechansim. For example, Resource Allocation(RA) and Adamic-Adar(AA) are two weighted counting methods for Common Neighbor(CN), which shows better overall performance than unweighted counting CN. MPLP generalizes these two methods beyond the 1-hop neighborhood by using degree-normalized orthogonal vectors. However, BUDDY cannot perform a weighted counting due to the mechanism of MinHash and HyperLogLog. Therefore, we believe that the incorporation of RA/AA into MPLP is one of the driving factors boosting its performance. In fact, in the Github repository of BUDDY, BUDDY uses a pre-computed RA score as the edge feature to improve the performance on OGBL-PPA, which also suggests the effectiveness of RA, but, in our humble opinion, violates BUDDY's beauty of only using node-level features/signatures to perform link prediction tasks.

2. **ELPH/BUDDY can cause a distribution shift problem, while MPLP will not**: Sec 4.2 introduces that during training, MPLP(+) will perform a shortcut removal for the positive node pairs to avoid the distribution shift problem[2]. This technique is critical for both ELPH/BUDDY and MPLP. Consider a target node pair $(u,v)$ and another node $w$ that connects to node $u$ only but not $v$. If $(u,v)$ is a positive node pair, there is an edge connecting $u$ and $v$. When counting the 2-hop neighbors for node $v$, $w$ will always be counted because it can exploit the node $u$ and the link between $u$ and $v$ to reach node $v$. This will cause a distribution shift problem because the model can easily distinguish the positive node pairs from the negative node pairs, just during training. MPLP(+) will perform a shortcut removal for the positive node pairs to avoid this problem. However, ELPH/BUDDY will not perform this shortcut removal, which will cause a distribution shift problem.

- In fact, I believe that the authors of BUDDY are aware of this problem but have not addressed it in their paper.
In their code, they have a `use_zero_one` flag to always discard the 2-hop neighbor counts due to the issue above. Recently, the Github repo of BUDDY has been updated with a new feature branch `rewiring`, where they also start to implement a shortcut removal technique to avoid the distribution shift problem. It can be found in the `src/datasets/elph.py` file's `remove_bridges` function.

3. **MPLP+ is walk-based**: MPLP+, different from ELPH/BUDDY, estimates the number of walks (Theorem 3.3) rather than nodes between two nodes. It is still an open question whether walk-based methods are better than node-based methods for link prediction tasks (MPLP is node-based). However, MPLP+ shows better empirical performance than ELPH/BUDDY in our experiments.

4. **Lower estimation variance**: With the same computational budget, MPLP can perform the pairwise structural estimation with lower variance than ELPH/BUDDY. This is empirically shown in Appendix F.1.

We want to again appreciate the reviewer's in-depth question on the difference between MPLP and BUDDY. While we have discussed the differences above in Appendix A, we have not dived into much details in the main paper to avoid distracting the reader. We will consider adding the above detailed comparison between MPLP and BUDDY in the revised version.

[1] Graph Neural Networks for Link Prediction with Subgraph Sketching

[2] FakeEdge: Alleviate Dataset Shift in Link Prediction

Meta-review: The reviewers all lean towards accepting the paper with one reviewer scoring the paper to be of very high quality and impact. Reasons to accept the paper are 

(i) both theoretical and practical results that should be relevant to the graph learning community
(ii) strong and extensive experimental evaluation with competitive results
(ii) extensive ablation studies
(iv) a clearly and well-written paper with a strong motivation of the proposed approach

There was one reviewer who was not satisfied with the reasons the authors provided for why their methods works. Indeed, some explanations where inconsistent and the authors should take this feedback into account in the final version of their paper.
Decision: Accept (poster)