OCN: Effectively Utilizing Higher-Order Common Neighbors for Better Link Prediction
Authors: Juntong Wang
Xiyuan Wang
Muhan Zhang
Venue: NeurIPS 2025 poster ()
Keywords: Link Prediction
Higher-Order Common Neighbors
Structural Features
Probabilistic Modeling
Orthogonality
Primary area: deep_learning
TL;DR: We design orthogonalization to eliminate redundancy between different-order Common Neighbors and normalization to mitigate over-smoothing for link prediction..

Abstract: Common Neighbors (CNs) and their higher-order variants are important pairwise features widely used in state-of-the-art link prediction methods. However, existing methods often struggle with the repetition across different orders of CNs and fail to fully leverage their potential. We identify that these limitations stem from two key issues: redundancy and over-smoothing in high-order common neighbors. To address these challenges, we design orthogonalization to eliminate redundancy between different-order CNs and normalization to mitigate over-smoothing. By combining these two techniques, we propose Orthogonal Common Neighbor (OCN), a novel approach that significantly outperforms the strongest baselines by an average of 7.7\% on popular link prediction benchmarks. A thorough theoretical analysis is provided to support our method. Ablation studies also verify the effectiveness of our orthogonalization and normalization techniques.

OCN: Effectively Utilizing Higher-Order Common Neighbors for Better Link Prediction
Juntong Wang Xiyuan Wang!. 1.2 Muhan Zhang
Institute for Artificial Intelligence, Peking University
Schooo of Intelligence Science and Technology. Peking University twang25dstu. pku. pku.edu.cc en, {wangxiyuan yaaayuuannmmmmu.u.aaa muhann Hêpku. edu
Abstract
Common Neighbors (CNs) and their higher-order variants are important pairwise features widely used in state-of-the art link prediction methods. However, existing methods often struggle with the repetition across different orders of CNs and fail to fully leverage their potential. We identify that these limitations stem from two key issues: redundancy and over-smoothing high-order common neighbors. To address these challenges, design orthogonalization to eliminate redundancy be- tween different-orde CNs and normalization to mitigate over-smoothing. By com- bining these two techniques, propose Orthogonal Common Neighbor (OCN), novel approach that significantly outperforms the strongest baselines by an average of 7.7% popular link prediction benchmarks. A thorough theoretical analysis is provided to support our method. Ablation studies also verify the effectiveness of our orthogonalization and normalization techniques. Code is available at: ? https//giihbb.com//iggiinnmo///
Introduction
The application of link prediction spans numerous fields. For example, it can be used to forecast website hyperlinks [Zhu et al., 2002]. In bioinformatics, it plays critical role in analyzing protein- protein interactions (PPIs) [Airoldi et al., 2008]. Similarly, in e-commerce, link prediction is a core component in developing recommendation systems [Huang al., 2005, Lü al., 2012]. Currently, the most popular link prediction models are based on Graph Neural Networks (GNNs). The first GNN for link prediction was the Graph AutoEneoder (GAE) [Kipf and Welling, 2016]. uses the inner product of the two target nodes' representations, produced by Message Passing Neural Network (MPNN) [Gilmer al., 2017], as the logits for the probability that link exists between the two nodes. Despite its success some citation graphs, such Cora [Sen et al., 2008), GAE computes the representations of two nodes separately, thus failing capture structural relationships between them, such as the number of common neighbors (i.e., nodes connected to both target nodes by an edge), which is crucial heuristic in link prediction.
To address the inability to capture pairwise structural relationships, various methods have been proposed [Zhang et al., 2021, Yun et al., 2021, Chamberlain al., 2023, Wang et al., 2024]. Although these methods differ in their detailed implementations, they all focus on computing the neighborhood overlap between the two target nodes, which includes both common neighbors and higher-order common neighbors (nodes connected to the two target nodes via walk or path). While higher-order common neighbors provide auxiliary information to common neighbors and improve performance in some cases (Yun et al., 2021, Chamberlain et al., 2023], they have not yet been widely adopted and do not always improve performance due to two key problems:
*Correspoddence to Muhan Zhang
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

The first problem is redundancy: different- order common neighbors of the same node pair may overlap significantly. A node can be common neighbor and a higher-order common neighbor of some node pair at the same time, as the path or walk connecting them may not be unique. This overlap makes higher-order CNs less informative when common neighbors are already used.
The second problem is over-smoothing. In the context of node classification problems [Oono and Suzuki, 2020], over-smoothing describes the phenomenon that, as the number of GNN layers increases, all nodes have similar representations because their neighborhoods become more and more similar. Here, wer-smoothing means that, as the order of common neighbors increases, a node can become a high-order CN for more and more node pairs simultaneously. When the path/walk length is sufficiently large, the high-order common neighbors of a node pair will encompass the entire graph. At this time, aggregating the features/embeeldings of the high-order common neighbors makes every node pair have similar pairwise representations, leading to over-smoothing in the context of pairwise representation learning.
Both issues hinder the effective utilization of higher-order common neighbors, thereby limiting the learning of complex pairwise structures and preventing state-of-the-art link prediction models from achieving optimal performance. For example, Wang et al. [2024] found that utilizing only first-order common neighbors led to the best performance in their models. To address these two problems, we propose two techniques: coefficient orthogonalization and path-based normalization, respectively.
For coefficient orthogonalization, which solves redundancy, we remove the linear correlation between the coefficients of different-order common neighbors. For instance, given pair of nodes in graph with n nodes, the coefficient indicating whether each node participates in some order of common neighbors of this node pair becomes vector R We use the Gram-Schmidi orthogonalization process to eliminate the correlation between the coefficient vectors of different-order common neighbors, so that models can better leverage information from higher-order CNs. The coefficients can be binary (0 or I) to indicate whether a node is a common neighbor, or functions of node degrees as used in [Yun et al., 202 ], or the number of walks of a certain length connecting the two target nodes in which the node participates, as used in this work. With coefficient orthogonalization, our model significantly outperforms previous link prediction models using common neighbors. Furthermore, to accelerate the orthogonalization process, we propose a polynomial trick, which achieves similar performance to precise orthogonalization while eliminating the extra computational overhead.
For path-based normalization, which addresses over-smoothing, we divide the coefficient of each node by the number of k--hop walks in which it participates. The intuition behind the normalization is that when a node participates in a large number of walks, it will more frequently appear in the common neighbors of other node pairs, which causes the features of different links to become similar, leading to over-smoothing. Notably, when the path or walk has a length of I, the path count reduces to the node degree, and our normalized CN degenerates to a famous link prediction heuristic, Resource Allocation [Zhou et al., 2009]. To theoretically analyze path-based normalization, we use a random graph model and prove that, with the normalization, k-hop CNs lead to a strictly decreasing upper bound of the proximity of positive node pairs (real links) with the increasing of k. while without the normalization, high-order CNs do not decrease the proximity no matter how large 1 is used. This result justifies the effectiveness of using normalized high-order CNs, and potentially explains why previous methods using high-order CNs do not always work (due to lack of normalization). In practice, we use a method similar to batch normalization [loffe and Szegedy, 2015] to estimate the number of walks efficiently, avoiding the computational overhead of exact counting.
By combining both techniques with previous methods [Wang et al., 2024], we propose Orthogonal Common Neighbor (OCN) and its variant with an approximated and faster orthogonalization process, Orthogonal Common Neighbor with Polynomial Filters (OCNP). In our experiments, the performance of OCN and OCNP significantly outperforms existing models, achieving state-of-the-nn results on several Open Graph Benchmark datasets [Hu et al., 2020]. Ablation studies also verify the effectiveness of orthogonalization and normalization.
2 Preliminaries
For an undirected graph G = (V, E, X), where V= == 21, n.. represents the set of n nodes,
E. C V x V denotes the edge set, X E ROxP a matrix of node features, and A E Raxx the symmetric adjacency matrix. The entries of the adjacency matrix are defined such that Auv 1
2

---

if there is an edge (u, v) E, and Aue = otherwise. This adjacency matrix captures the direct connections between nodes in the graph. The degree of node u, denoted by d(u, A). defined as the sum of the entries in the corresponding row of the adjacency matrix, i.e.d(u, A) = v== Aue- which represents the number of neighbors of node u.
We further define A' as the higher-order adjacency matrix, where the entry An represents the number of walks of length between nodes u and v. Specifically, A' encapsulates more complex relationships between nodes, extending beyond direct neighbors to capture connections that involve intermediary nodes. The matrix A' can be computed by raising the adjacency matrix A to the power where higher powers encode longer walks between nodes.
The k-order neighbor set (u, A!) defined as the set of all nodes that are reachable from node through a walk of length L, i... (u, A') {u | E V, Ane > 0}.
This set includes all nodes that can be reached from u by traversing 1-length walks, thereby expanding the notion of proximity beyond direct neighbors. While some methods define high-order neighbors based on paths or shortest paths, we adopt a different approach. Specifically, we do not rely on shortest paths.
In the context of k-hop neighbors, the k-hop common neighbors of two nodes u and e, denoted as CN, v). are defined as:
CN^(u,U)
U
(NN, n (a,
20h 1)ck 124.
by N254
where the union is taken over all pairs i and l22 such that 2(k: 1) < k1 + 2k. Here, Nk, (u) and NE, (v) denote the sets of nodes reachable from u and via walks of lengths 1 and 2z respectively. The concept of common neighbors is critical in graph-based models, as it quantifies the overlap between the neighborhood structures of two nodes, which a useful measure for tasks such as link prediction.
3 Related Work
Link Prediction Model Link prediction generally employs three main approaches; Node embed- dings, Link prediction heuristics, and GNNs. Node embeddings aim find an embedding for nodes such that similar nodes (in the original network) have similar embeddings [Perozzi et al., 2014, Belkin and Niyogi, 2001, Grover and Leskovec, 2016, Kazemi and Poole, 2018]. Link prediction heuristics [Newman, 2001, Barabåsi et al., 2002, Adar and Adamic, 2003, Zhou et al., 2009] mainly rely on handcrafted structural features for prediction. In recent years, methods based on GNNs have become research hotspot. SEAL [Zhang and Chen, 2018] calculates the shortest path distance between nodes and j. extracts the k-hop subgraph, generates augmented features X', applies MPNN to aggregate node representations, and predicts the link.
Architecture Combining MPNN and SF The SF-then-MPNN framework, exemplified by SEAL [Zhang and Chen, 2018], enriches the input graph with structural features, which are then passed to MPNN to enhance expressivity. However, this approach requires re-running the MPNN for each target link, leading to lower scalability. In contrast, models such as NcoGNN [Yun et al., 2021] and BUDDY [Chamberlain et al., 2023] adopt the 3F-and-MPNN framework, where the MPNN takes the original graph input and runs only once for all target links, thus enhancing scalability. However, this approach sacrifices expressivity, as the structural features are detached from the final node representations. To address this, the MPNNNtthen-SC framework proposed by NCN [Wang et al., 2024] significantly improves performance by first running MPNN on the original graph and then employing structural features to guide the pooling of MPNN features, resulting in better expressivity while retaining high scalability.
4 Orthogonalization
We observe substantial redundancy between CNs of different orders. By analyzing the cor- relation coefficients between CNs at various orders, we find that this correlation increases
3

---

with the order, reaching high levels, as shown in Figure 1. This indicates that the cur- rent definition of CNs contains significant linear dependencies across different orders. In contrast, higher-order CNs based on shortest path distances (SPDs) are inherently indepen- dent, as a node cannot simultaneously belong to the common neighbor sets of different SPDs.
The presence of such redundancy negatively impacts model performance by reducing the model's expressive power. When different orders of CNs become highly cor- related, it becomes difficult for the model to effectively differentiate between them, limiting its ability to capture distinct structural relationships This not only impedes the model's capacity to learn from richer, higher-order interactions, but also diminishes its generalization abil- ity. preventing it from uncovering subtle but important relationships in the graph.
Curvelalion Live Coefünient.
Index of CN*
Index of CN
The heatmap illustrates the correlation coefficients between differ- ent orders of k-order Common Neigh- bors (CNs), highlighting increasing re- dundancy with higher orders.
Figure 1:
4.1 Scalable Orthogonalization
To mitigate the negative effects of redundancy, propose using the Gram-Schmidt process transform k-hop CNs into mutually independent representations. This approach maximizes the information content of each CN* matrix by eliminating linear correlations between different orders of CNs.
For CN*,, we define it based on Equation (I) as follows: (N,( = 2 -ic (Axt),, ky kg
(A*z), u² where CN (u, v) E IR",, with its i-th element representing the number of 2k- and 2k length walks from node u to node v that node participates in as an intermediate point. The result of orthogonalizing CN* v)) for k 1, 2,...... ... is referred as OCN*, The matrix OCN* can be interpreted set of orthogonalized representations for the k-hop CNs. The detailed definition and explanation the correlation matrix can be found in Appendix B.
However, orthogonalizing CN* over the entire graph poses significant computational challenges. To address this, we draw inspiration from Batch Normalization [loffe and Szegedy, 2015], which maintains running estimates of batch statistics (mean and variance) to normalize activations during training. Similarly, we propose strategy for orthogonalizing CN* across mini-batches. The core idea is to maintain a running inner product: & + (1 3:) + B.Ei, where é is the running inner product maintained by the t-th mini-batch. This update process, which considers both the previous running inner product and the currently computed inner product, is equivalent to a Simple Moving Average (SMA) [Arce, 2004]. A detailed proof is provided in Appendix C. The complete orthogonalization algorithm is outlined in Algorithm
4.2 Orthogonal Common Neighbor with Polynomial Filters
While Cram-Schmide orthogonalization effectively reduces redundancy, it has a relatively high time complexity (see Appendix for detailed analysis). To address this, we explore alternative orthonormal bases for orthogonalization. For example, Chebyshev polynomials form an orthonormal basis and can be used polynomial filters to process CNs.
Inspired by Wang and Zhang [2022], we propose using an orthonormal basis as polynomial filters to filter common neighbors. This can be expressed as: OCN se Σk CgCN*, where ag represents the coefficient of the k-th term in the polynomial filter basis. Although this approach compromises strict orthogonality, it reduces redundancy between CN through spectral domain operations. To further reduce time complexity, take the limiting case T and construct diagonal matrix, applying consistent filtering operations to each edge signal of C within the same dimension.
By replacing inner product operations with weighted operations, we avoid the extensive computations and iterations required by Gram-Schmin orthogonalization. This approach effectively adjusts the signal in the frequency domain and removes redundant information.

---

Building on this, we introduce Orthogonal Common Neighbor with Polynomial Filters (OCNP). We can select any popular orthogonal polynomial bases (e.g., Jacobi. Monomial, Chebyshev, or Bernstein). This operation can be viewed as passing the signal of each edge through filter defined by the chosen polynomial, thereby adjusting the frequency characteristics of the signal. For a detailed analysis, please refer to Appendix J.
5 Normalization
A common issue is that, the order of CNs increases, the high-order CNs of different nodes become more sim- ilar. To quantify this effect, analyze the coefficient of variation of CNs at different orders across various nodes. As shown in Figure 2, the coefficient of variation de- creases at higher orders, indicating that the high-order CNs of different nodes begin overlap more frequently and that the similarity of higher-order neighborhood struc- tures continually increases. This may lead to loss of distinctiveness among nodes. In other words, as we con- sider more hops the network, the feature representations of links become increasingly homogeneous, potentially undermining the performance of link prediction models.
Total Varfince Total Mon
Order Common Neighbor Between Nodes
Figure 2: To demonstrate that the higher- order common neighbors of different node pairs become similar, we use the Cora dataset as an example. We cal- culate the coefficient of variation (CV), which is the ratio of the standard devia- tion to the mean, of the CNs of different nodes at the same order. High CV in- dicates low over-smoothing degree. Re- sults shows that as the order increase, over-smoothing becomes more and more significant, but our method (yellow) can alleviate this problem.
This observation consistent with the intuitive motiva- tion behind our normalization trick. Specifically, when node participates in a large number of walks, it will more frequently appear as a CN for other node pairs, causing the features of different links to become similar and thus leading to smoothin..... Therefore, we propose nor- malization trick similar to batch normalization [Ioffe and Szegedy, 2015] to mitigate this issue. We divide the co- efficient of each node by the number of walks in which it participates obtain normalizedCN. This normalization technique helps to reduce the influence of frequently appearing common neighbors, ensuring that nodes with a large number of high-order walk participations are not overly emphasized.
normalizedCN provides the following insight: If k-hop CNs are less frequently shared among other node pairs, then these k-hop CNs carry greater significance in the relationship between the two nodes. For example, if the more distant social circles in which two individuals indirectly participate include many people (i.e., are more mainstream), then the commonalities between these two individuals will be fewer. Conversely, the social circle more niche, it suggests higher potential for direct connection between the two individuals.
Upper Bound of Distance
unnormalizedCN nomalizedCN
Order of the k-hop CNs
Figure 3: The impact of higher-order k-hhpp CNs on the upper bound of d, is illustrated. k-hop CNs have no effect (blue line). The yellow line shows how the upper bound tightens with increas- ing k. which is the result obtained after introducing normalizedCN. With normalizedCN, the contribu- tion of each k-hop CN is now ExeOn*(.))) [Peto]
This compensates for the traditional Resource Allocation (RA) [Zhou et al., 2009] method, which ignores the potential contribution of k- hop CNs and fails account for the higher-order structure of the graph. Next, we analyze this trick theoretically using a random graph model and prove its effectiveness. It can be seen that when the path or walk has length of 1, the path count reduces to the node degree, and normalizedCN degenerates to RA.
rather than just 1.
5

---

5.1 Theoretical Justification for Normalization
In this section, we analyze common neighbor with and without normalization on random graphs and Barabási-Alber model [Albert and Barabási, 2002] to show that normalization leads to better estimator of link existence. The latent space model [Hoff al., 2002] is commonly applied to describe proximity in latent spaces, where nodes with similar locations in the latent space tend to share specific characteristics. We first discuss the D-dimensional Euclidean space (i.c., a space with curvature 0). We introduce a latent space model [Sarkar et al., 201 I] for link prediction that describes a graph with N nodes. All definitions and proofs in this section are in Appendix D.
To illustrate the effectiveness of normalization, we compare two link prediction heuristics: CN and normalized CN.
Definition 5.1. We define the normalizedCN between (i. j) as a measure of their similarity with Structural Feature based on the contributions from all k-hop CNs. It is inversely propor- tional to the number of distinct node pairs for which it is also the k-hop common neighbor: nomallizdCN (i. = (1.) [Patei]
where (i, j) is the set of k-hop CNs of (i,j), [P(( is the total number of paths for the set of distinct node pairs which node e serves as a k-hop CN for those node pairs. Note that, even for the same node pair, there may be more than one path in which acts as the k-hop CN of (i.j).
Theorem 5.2. When k normalizedC((i..) j) degenerates into RA( Specifically,
(4())
for each e E CN= (i, the following relationship holds: normalizedCN (c, i,,,,) dec)
RA(c, j.). The proof is trival.
When there is normalization, in the latent space we have the following Proposition 5.3. Here, di denotes the distance between node and node j in the latent space. The smaller this distance is, the higher the probability that there exists link between i and j.
Proposition 5.3. (Latent space distance bound with k-hop CNs). For any > O, with
probability at least 1 - 8, we have dij < En=o
M-2 In + 2 (rmmax)2 - (1 a) Dizi-T))
where a /N ln(1226)/2
(i.)
And max M
max(rM (M E (1,.... 22 13)
N+V-3N In (N-V-2N 2N 6j2R
is the maximum of the feature radius for the set of intermediate nodes in D dimensional Euclidean
space. N is the number nodes. represents the order of the k-hop CNs. 1/2x 1)2w(1,) (i,j) is the number of k-hop CNs about (i,
After applying our normalization trick, we have the following Proposition 5.4:
Proposition 5.4. (Latent space distance bound with k-hop CNs after normalization). We sim- ply need to modify the overall contribution of k-hop CNs from (is( to Eecent [e]] For any 8 > O, with probability at least we have
yaa(i.f)
28-2
d, S
M-2
Σ In + n=
(rmax))
DTc IJ
26-1
where S is the maximum degree of all k-hop CNs of (i.j) and E
[0,1] and y
(2)(d.)) (N 2M-Ja-h -a)
Next, we analyze the upper bound of d(i,j) for these two cases. When there is no normalization, is evident that as N becomes large, (1 - a)) approaches 1, so the order of the k-hop CNs has no effect. Additionally, the exponent term D contains large denominator D, meaning that
even if (1 - a) does not approach I, it would not significantly affect the result (as shown by the blue line in Figure 3). However, when we apply the normalization trick, the upper bound of d; becomes tighter as le increases (as shown by the yellow line in Figure 3). In fact, this aligns with the general belief that the effectiveness of incorporating higher-order k-hop CNs is indisputable [Wang et al.,

---

2024, Chamberlain et al., 2023, Mao et al., 2024, Yun et al., 2021]. Based on the above analysis, normalizedCN provides a tighter upper bound of d(i, compared CN and more effective.
The above theoretical analysis was conducted on a random graph model. We extend the theoretical argument the more realistic Barabási-Alhert model [Albert and Barabási, 2002], and obtain the following Proposition 5.5 and Proposition 5.6 before and after introducing our path-based normalization, respectively. The detailed derivation process is provided in Appendix Q.
Proposition 5.5. (Distance bound with k-hop CNs on Barabási-Albes model). For any 0, with probability at least - 8, we have
2(N 2)
(m (2N + 1)!!
Nm²
b In 6
drg - 2k
In
1)+
+V 2
1nd-1)
a
(2N+1)!! NN
(NV(I)
2 N!
4
(3)
where N = #nodes,k represents the order of the k-hop CNs.
Proposition 5.6. (Distance bound with k-hopp CNs on Barabási-A Abert model after normal-
ization). After introducing normalizedCN, for any 5 > O, with probability at least - 5, we have
n-2
N - MoN--n-ch C 11
dij S 2k 1n[
N W
1)+ F.,
(4)
n-2
where W.)) is Lambert W function, Ç is the maximum degree of all k-hop CNs of (i,j), the total number of paths of length 1, between and is denoted as ji.
C 1
1
(2N + 1)!!
Nm
E
(m
+
In 8 (18-1)
(
12k D2k VN
LV
2 N!
2
4
(5)
and D is the maximum degree on the graph.
Results show that without introducing normalizedCN, the upper bound of 8;j is monotonically increasing affine function with respect to After introducing normalizedCN, this upper bound gradually decreases as k increases. This extends theoretical analysis to more realistic scenarios.
Orthogonal Common Neighbor
Following the structure + OCN* construct: OCN* = EUEN*(ONN*()) MPNN(u, X) = h = OCNE O MPNN(A,
OCN OCNN+1 + ...., we can naturally
In particular, OC reflects the two nodes of the edge itself, have:
MPNN(N' a, @ MPNN(N' (1), a, h4 @ hy MPNN(i, A,z) MPNN(J, A,æ)
We naturally get our Orthogonal Common Neighbor (OCN) model:
K
OCN(i, = MPNN(1, X) M,NN(J, Σ
OOLOON..MMNN (A, X)h--
The complete algorithm is shown in Algorithm 2. The model architecture is detailed in Appendix G. According to Section 4.2, we obtain our Orthogonal Common Neighbor with Polynomial Filters (OCNP) by replacing the computation method of OC in Equation (7) from Algorithm I with Equation (73).
Theorem 6.1. OCN is strictly more expressive than Graph Autoencoder GAE), CN, RA, AA. Moreover, Neo-GNN BUDDY and NCN not more expressive than OCN. The proof can be found in Appendix

---

Table I: Results on link prediction benchmarks. The format is average + standard deviation.
OOM means out of GPU memory.
Cora
Citeseer
Pubmed
Collab
PPA
Citation2
DDI
Metric
HR@ 100
HR@ 100
HR@ 100
HR@50
HR@ 100
MRR
HR@20
CN
33.92:10:46
29.79:1090
23.13::0.15
56.44:1..00
27.65=00.00
51.47=0.00
17.73=0.00
AA
3..85:t1.34
15.19.1.33
27.38:0.11
64.35:10.00
32.45=0.00
51.89=0.00
18.61=0.000
RA
41.07:1.48
33.5610.17
27.03
64.0011..00
49.33=0000
51.9810.00
27.60=0.00
GCN
66.79-11665
67.08-12.94
13.02:1..39
4..75
18.67-1.32
84.7410.21
37.07=5.077
SAGE
55.02:14.03
57.01
39.66=10.72
48.10:10.81
16.55=2..40
82.60=00336
53.90=4.74
SEAL
81.71::1.30
83.8912.15
7..54:1.32
64.74110.43 OOM
48.8013.16
87.67=0.32
30.5613.88
NBFnet
71.65:22.27
14.07:1..75
58.73
0OM
OOM
4.00110.58
Nco-GNN
10.4221.31
84.67-12.16
13.93
57.52-0.37
49. 1310.600
87.26-0.84
63.57=3.552
BUDDY
88.00#10.44
92.93-0.277
74.10
65.94
49.85=0.20
87.56-0011
78.51
NCN
89.05-10.96
91.5611
19.05=
04.76110.7
61.19
8..0910.06
62.32-6.110
NCNC
89.65-1.336
93.47100955
81.29
66.61
61.723..33
89.12-0.40
84.11=3.67
PLNLP
70.59
32.38
84.92-0.29
90.88-3.13
OCN
89.82-10.11
93.62 1.30
83,9610..11
3.75
69.79-0085
88.57-00066
97.42-10.34
OCNP
1..06:11001
93.41+1.02
82.32+1.21
07.7441.116
74.87=00.4
87.06-0.27
97.65-0.38
In our ablation study, when incorporating 3-hop common neighbors (3-hop CN), the model's per- formance did not show significant improvement and instead exhibited instability and increased fluctuations during training. This suggests that higher-order neighbors may introduce redundant in- formation, affecting the model's stability and generalization ability. Therefore, despite the possibility of selecting more orthogonal bases, and considering training resources and model stability, we prefer to use OCN1 and OCN2 to ensure efficiency on large-scale graph datasets. The analysis of a₁ and a2 along with a discussion highlighting differences from NCN can found Appendix N.
7 Experiment
In this section, we present comprehensive evaluation of the performance of OCN. The full experimental setup is provided in Appendix F and Appendix H.
For our evaluation, we utilize seven well-known real- world datasets for link prediction. Three of these datasets come from Planetoid's citation networks: Cora, Cite- seer, and Pubmed [Yang et al., 2016]. The remaining datasets are sourced from the Open Graph Benchmark (OGB) [Hu et al., 2020], including ogbl-collab, ogbl-ppa, oibt-citation,, and ogbl-ddi. Detailed statistics and dataset splits are provided in Appendix F.
11
v3
7.1 Evaluation on
Datasets
In evaluation real-world datasets, we adopted series of baseline methods, including traditional heuris- tic approaches such as CN [Barabási and Albert, 1999], RA [Zhou et al., 2009], and AA [Adar and Adamic, 2003], well as GAE models such GCN [Kipf and Welling, 2017] and SAGE [Hamilton et al., 2017], SF- then-MPNN models. including SEAL [Zhang and Chen, 2018] and NBFNet [Zhu et al., 2021]. as well as SF-and- MPNN models such as Neo-GNN [Yun et al., 2021] and BUDDY [Chamberlain et al., 2023]. We also compared with models that adopt the same MPNN-then-ST architec- ture, including NCN and NCNC [Wang et al., 2024]. In ad-
Figure White, green, orange, and yel- low represent node features 0, 1, 2. and respectively. U2 and va are symmet- ric, and GAE cannot distinguish (v, U2) and (v1, vz). With node features ignored, (U), U2) and (V1, Us) are symmetric, so CN, RA, AA, Neo- Ceo-GNN, and BUDDY cannot distinguish them. NCN also de- generates into GAE, so it also cannot. However, (01, v2) and (#1, 03) have dif- ferent 2-hop CNs, which allows OCN to distinguish them.

---

Table 2: Ablation study link prediction benchmarks. The format is average score + standard deviation. OOM means out of GPU memory.
Cora
Citeseer
Pubmed
Collab
PPA
Citation2
DDI
Metric
HR@@ 100
HR 100
HR 100
HR
HR 100
MRR
HR @ 20
OCN-Orth
88.62
92.04=11.53
80.95:t11144
64.64: 0.45
18. 5.994
74.53-24311 31
36.08:99.36
OCN-normallzedCCN
89.11=#1.45
92.25:
81.35:
67.30:t 0.33
59.944::
86.33=0.17
97.56:1:0.43
OCN-CAT
88.634: 0.99
92.52+ 1.37
81.12 0.39
63,20:1 0.80
34,30:1 6.55
87.344: 0.23
24.30= 3.11
OCN-Linear
87.73+1.223
90.60=1.224
79.71=1.08
0,.58:
6,91
88, 88.56=00.13
84.89:22.7
OCN-sAANDmpan
89.07=1.35
91.98=1.32
80.27=1.01
68.75:10.34
09.30:1..54
00M
12.65
OCN-3
85.84=22.23
88 04.60044.59
69,56-444.66
72.28:+11.33
OOM
82.88
19:49.33
OCN-SPD
89.17+1..15
91.97:11.60 1.60
80.69+1.35 1.33
62.58-+0.91
44.37422.1
86.99=0.68
96.82:+0.16
OCN
89.82=#0.91
93.62:# 1.30
83,96:10.51
72.43:43.75
09.79
88.57:00066
97.42:1:0.44
OCNP-Filter
88.73+1.336
22.18++2.65
81,40+00888
63.09++..75
30.86+1.003
86.96+0.19
27.2744..17
OCNP-CAT
88.05= 1.53
91.71=1.66
81.61=0.73
63.89+0.39
28.11422.01
86.98=0.44
26.13++4.85
CenP-Linear
87.68:1.41
90.93=1.799
80.29:10.90
60.89:1.91
12.82
87.10=0.28
49.48.10.34
OCNP-sAANDmpan
88.95=0.96
92.36=11440
0.63
16.90.11.29
$7.45=0.89
0OM
96.86:10.11
OCNP-3
1..17:1.44
01.60
09.0
59.31+0.557
OOM
OOM
91.31+2.79
OCNP-SPD
89.08 + 1.37
91.36:#1.85
80.25++0.77
66.24440.51
52.93+1.14
07.27
97.33-+0.95
OCNP
90.06++ 1.01
93,41++1.00 1.00
82.32++ 1.21
67.74+0.16
74.87
87.06+0.27
97.65++0.38
dition, we also selected the strong baseline PLNLP [Wang et al., 2021], which uses training tricks. Furthermore, we compared it with GIDN [Wang et al., 2022], which also utilizes training tricks, as well as several node embedding methods. The detailed comparison results can be found in Appendix K. The baseline results are derived from [Wang et al., 2024]. Our model is OCN, and its architecture is detailed in Appendix G.
The experimental results, as shown in Table 1, demonstrate that OCN outperforms all baselines on all datasets except Citeseer and Citation2. Compared to the best-performing NCNC, OCN only 0.6% behind on Citeseer and Citation2, but OCN still outperforms all baselines except NCNC on these two datasets. On the remaining five datasets, OCN improves by an average of 7.7% over NCNC. Across the seven datasets, OCN improves by an average of 7.2% over NCN and by an average of 12.4% over BUDDY. These excellent results undoubtedly prove the superior expressiveness of our OCN model. Furthermore, on the ogbl-ppa dataset, OCN surpassed the large-scale GraphGPT [Zhao et al., 2024] (0.6876 + 0.0067), and on the ogbi-ddi dataset, it achieved 97.42, significantly outperforming the strongest baseline, NCNC. OCNP not only maintains the overall performance of OCN but also significantly reduces computational complexity, while achieving substantially superior results compared to NCNC on the ogbl-ppa. The famous baseline models' average rankings are: BUDDY: 4.7, NCN: 4.29, NCNC: 2.71, while our models' average rankings are: OCN: 1.57, OCNP: 2.28.
Additionally, we conducted comparison between OCN, OCNP, and other Link Prediction Models, as detailed in Section K. Our models consistently demonstrated superior performance when compared to both node embedding-basse methods and models that incorporated various training tricks, regardless of whether these tricks were applied or not. The results show that, even with the introduction of such training techniques, our models still maintain an edge in terms of prediction accuracy and efficiency. Furthermore, we have also provided an ablation study on the MPNN used in both OCN and OCNP in Section L. This study offers deeper insights into the specific factors in MPNN that enhance the performance.
7.2 Ablation Analysis
To assess the effectiveness of the OCN and OCNP design, we conducted a comprehensive ab- lation analysis, as shown in Table 2. By eliminating the influence of normalizedCN on the k- hop CN weights, we derive OCN-Orth. Similarly, removing the effect of normalizedCN from OCNP results in OCN-Filter. Furthermore, keeping the impact of normalizedCN while remov- ing the orthogonalization process in OCN and the filtering mechanism in OCNP leads to OCN- normalizedCN. Additionally, we modify both models in Equation (7) as follows: MPNN(i, A, X) O
MPNN A, X) _ ag OCNK, MPNN(A A, X), which results OCN-CAT and OCNP-CAT. The experimental results for OCN-CAT and OCNP-CAT show notably lower performance, especially on PPA. A detailed analysis of the significant performance gap resulting from changing the aggrega- tion strategy from summation to concatenation can be found in Appendix O. To investigate the impact

---

of the nonlinear layers in our models, we remove the nonlinear layers from both OCN and OCNP, yielding OCN-Linear and OCNp-Linear, respectively. To verify that employing the MIPNN-then-SP paradigm better addresses the deficiencies mentioned earlier, we construct two variants utilizing the SF-and-MPNN framework. Finally, when incorporating 3-hop CNs, the models are referred to as OCN-3 and OCNP-3. When we use SPD-based higher-order common neighbors, we obtain OCN-SPD and OCNP-SPD.
Beyond thoroughly verifying the significant role of each component in our models, an intriguing experimental observation is that removing the nonlinear layers does not lead to a drastic performance drop, except for ogbl-ppa, where performance collapses entirely. While the overall performance gap on smaller-scale graph datasets remains relatively minor, it is important highlight that OCN and OCNP are originally designed to achieve substantial improvements on large-scale graphs, whereas their benefits on smaller graphs are naturally less pronounced. This is likely because extensively leveraging high-order CNs may introduce more uninformative information in smaller-scale graphs. Furthermore, incorporating 3-hop CNs not only imposes a substantial increase in computational cost and time but also contributes to greater instability in model performance. This instability manifests as significant oscillations in the loss curve, which could potentially stem from the increased norm the model. MPNN may still implicitly learn information from higher-order neighbors. Using SPD-based higher-order common neighbors also results in a performance decline, as we have analyzed, due to information loss.
7.3 Scalability
We compare the inference time and GPU mem- ory usage on the ogbl-collab dataset in Fig- ure 5. Both OCN and NCN exhibit similar com- putational overhead, as they only need to run the MPNN model once. However, in contrast, SEAL shows significantly higher computa- tional overhead, particularly as the batch size increases. This is because SEAL needs to rerun the MPNN model for each individual target link, which leads to substantial increase in inference time with larger batch sizes. When it comes to GPU memory consumption, OCN generally re- quires more memory than NCN, OCNP tends outperform OCN in both inference speed and memory consumption.
ICAC
10'
GPU memory/ca
timels
20a
10a
10*
10
10"
batch size
batch 5ize
Figure Inference time and GPU memory on ogbl-collab. The measured process includes pre- processing and predicting one batch of test links. As shown in Appendix I, the relation between time y and batch size is y = B Ct.
We also conducted similar tests a variety of other datasets. The results are shown in Figure 9. We observe patterns that are quite similar to the ones seen in the ogbl-collab dataset, as presented in Figure 5. Specifically, both OCN and OCNP generally show better scalability than Neo-GNN, handling larger datasets more efficiently. On the other hand, SEAL continues to demonstrate the poorest scalability among the models tested. In terms of memory usage, the overhead of OCN is either comparable to or slightly higher than that of NCN, depending on the dataset.
Conclusion
We propose a novel method called OCN for the link prediction task and effectively alleviates two key issues. OCN demonstrates significant performance improvements across multiple datasets. Furthermore, to further reduce the time complexity of OCN, we introduce OCNP. The work presented in this study offers new perspective the link prediction task and provides valuable insights for future research on handling higher-order neighborhood information in large-scale graphs.
Acknowledgments and Disclosure of Funding
This work is supported by the National Key R&D Program of China 3022ZD01603000 and the National Natural Science Foundation of China (62276003).
10

---

References
Jianhan Zhu, Jun Hong. and John G. Hughes. Using markov models for web site link prediction. In James Blustein, Robert B. Allen, Kenneth M. Anderson, and Stuart Moulthrop. editors, HY- PERTEXT 2002, Proceedings of the 13th ACM Conference on Hypertext and Hypermedia, June 11-15, 2002, University of Maryland, College Park, MD, USA. pages 169-170. ACM, 2002. doi: 10.1145/513338.5 513381. URL https:://oll. org/ 10. 1ee11114551333 513381
Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg, and Eric P. Xing. Mixed membership stochastic blockmodels. In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Léon Bottou, edi- tors, Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second An- nual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, httpttttss:///ppeeeeeeeee
December 8- -1, 2008, pages 33 43-40. Curran Associates, Inc., 2008. -bt.eeeattbbbbbabbaababaaac Abstract html. neurips. cc wttp:/cppppppe/e/e http://a///////////// http:hhhhhh/111eee458555 http://8888eeee00877777666222212
Zan Huang, Xin Li, and Hsinchun Chen. Link prediction approach to collaborative filtering. Mary Marlino, Tamara Sumner, and Frank M. Shipman III, editors, ACM/IEEE Joint Conference on Digital Libraries, JCDL 2005, Denver, CO, USA, June 7-11, 2005, Proceedings, pages 141-142. ACM, 2005. doi: 10.1145/10638851064411 URL https:/ //oo:. org/ 10. 1065415.
Linyuan LU, Matúš Medo, Chi Ho Yeung, Yi-Cheng Zhang, Zi-Ke Zhang, and Tao Zhou. Recom- mender systems. Physics reports, 519(1):1144) 2012.
Thomas N. Kipf and Max Welling. Variational graph nuto-encoders. CoRR, abs/1611.073008, 2016. URL http::/ http:///axxvvv.o org/ http////////.1/.//// 07308.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference Machine Learning. ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1263-1272 PMLR, 2017. URL http::/ http:::/ppocceeinge. mlr. pwwps/vwss gi gilmeri7a 17 html.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rar Rad.. Collective classification in network data. Al Mag., 29()):33-066, 2008, doi: 10.1609/AIMAG, V2913.2157. URL attps:://on org/ 10. 1 / a aimag. . v2913. 2157.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: theory of using graph neural networks for multi-node representation learning, Advances in Neural Information Processing Systems, 34:9061-9073 2021.
Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo J Kim. Neo-gnns: Neigh- borhood overlap-aware graph neural networks for link prediction. Advances in Neural Information Processing Systems, 34: 14683-1133944 2021.
Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Yannick Hammerla, Michael M. Bronstein, and Max Hansmire. Graph neu- ral networks for link prediction with subgraph sketching. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL
formm? wrrummid=mooEEDaaaa0
Xiyuan Wang, Haotong Yang, and Muhan Zhang. Neural common neighbor with completion for link prediction. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. URL https: https:///peetteee /ttp:////peeeeeeeeee net/ Sarum?id=sNFLNNit...
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https://openrevienn net/
forum?id-S11d02EFP
Tao Zhou, Linyun I Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B, 71:623-630 2009.

---

Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Francis R. Bach and David M. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, ICMI. 2015, Lille, France, 6-11 I July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pages 148-456. JMLR.org. 2015. URL http: / /ttpe/eeooceeeesse//ee/ee/e mlr. press/v37 v37/ioffel5 html.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph henchmark: Datasets for machine learning on graphs. Advances in 2020.
neural information processing systems,
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: online learning of social representations. In Sofus A. Macskassy, Claudia Perlich, Jure Leskovee, Wei Wang, and Rayid Ghani, editors, The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 14, New York, NY, USA August 24- 27, 2014, pages 701-710. ACM, 2014. doi: 10.1145/ 2623330.2623732. URL https:: /doi. org/ 10. 1 10111114/182 2623330. 2623732.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. Thomas G. Dietterich, Suzanna Becker, and Zoubin Ghahramani, editors, Advances in Neural Information Processing Systems /4 [Neural Information Processing Systems: Natural and Synthetic, NIPS 2001, December 3-8, 2001, Vancouver, British Columbia, Canada J. pages 585-591. MIT Press, 2001. URL https: / pptp/eeeioc....../////////o...sp www.eeddiiinnn.iiis...oom http://ec22ccccccccaaaeceeeeeeee
neurips....... cttccc/cpppa (paper/200//aa///aaa //aahh/ Abstract .tml.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Balaji Krishnapuram, Mohak Shah, Alexander Smola, Charu C. Aggarwal, Dou Shen, and Rajeev Rastogi, editors, Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pages 855-864. ACM, 2939754.
2016. doi: 10. 10.1145/2939672.29393
URL https: //doi. org/ 10. 1
Seyed Mehran Kazemi and David Poole. Simple embedding for link prediction in knowledge graphs. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 4289-4300, 2018. URL httptt:s:/pprooeeddtie neurips. cc/ /ttp//////aaa000000000000043451
Abstrccctt.-rtttt...t...a.aa.... maastract.htll.....
Mark EJ Newman. Clustering and preferential attachment in growing networks. Physical review E, 64(2):02510,, 2001.
Albert-Laszlo Barabãsi, Hawoong Jeong, Zoltan Néda, Erzsebet Ravasz, Andras Schubert, and Tamas Vicsek. Evolution of the social network of scientific collaborations. Physica A: Statistical mechanics and its applications, 311(34)):900611, 2002.
LAAaE Adar and LA Adamic. Friends and neighbors the web. social networks, 25(3):211-230, 2003.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Samy Ben- gio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 5171-5181 2018. URL https: : / //proceedings....////e www.ddinnnnnnnnnnioeoeem wttpippp.ccppppeee/0// /218// hash/ 2echh/53f077 (w..:ddc33337000 (BB.ffffcc377900000200008866222
Abstract html.
Gonzalo R. Arce. Nonlinear Signal Processing A Statistical Approach. Wiley, 2004. ISBN 978-0-471-67624-9. URL http://eu /uu wiley. wwt.///eeyDDD//Aieeeeeeooooo 0471666244716622111111 html.
Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference USA, volume 162 of Proceedings of Machine Learning Research, pages 23341-23362 PMLR, 2022. URL https: // httpp//eeeecgc..c//////////. mlr, prwss/esssssspeppp
Machine Learning, ICMI, 2022, 17-23 July 2022, Baltimore, Maryland,
aeress/v66l vttp//vv/////aa/ /aa///////22aammmmmm html. httml22m..tml.
12

---

Réka Albert and Álbert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
Peter D Hoff, Adrian Raftery, and Mark S Handcock. Latent space approaches social network analysis. Journal of the american Statistical association, 97 10960)0:000-1999 2002.
Purnamrita Sarkar, Deepayan Chakrabarti, and Andrew W. Moore. Theoretical justification of
popular link prediction heuristics. In Toby Walsh, editor, IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pages 2722-2727. ISCAI/AAAL 2011. doi:
URL https::tppo. / /doi. org/ /trg//.../o 5777 /tt.:/77781157777--7-11111111110
Haitao Mao, Juanhui Li, Harry Shomer, Bingheng Li, Wenqi Fan, Yao Ma. Tong Zhao, Neil Shah, and Jiliang Tang. Revisiting link prediction: a data perspective. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. net/ wowooooddnuuuuuaeee
URL https:/
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In Maria Florina Balcan and Kilian Q. Weinberger, editors. Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 40-48, New York, New York, USA, 20-22 Jun 2016. PMLR. URL nttps://proceediin mlr. waaas//v8yyaggalla htmll.
Albert-Láázıó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Truck Proceedings. OpenReview.net, 2017. URL net/ htt//foruummdddSSAayyl
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1024-1034, 2017. URL https: http:///pooeeeeneee//ee/e/ee/see neurips.. cc/paper /ampp/rr//11///// http//2211///////// hhshh 55t.abbossaaaeeeeaaaaeeeeeeeaaaa abeag Abstract .tttl..ct..t.l.....
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford
networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 34:29476-29490, 2021.
Zhitao Wang, Yong Zhou, Litao Hong, Yuanhang Zou, Hanjing Su, and Shouzhi Chen. Pairwise learning for neural link prediction. CoRR, abs/2112.02936, 2021. URL https://a//a org/
abs/2112.0222
Zixiao Wang, Yuluo Guo, Jin Zhao, Yu Zhang, Hui Yu, Xiaofei Liao, Hai Jin, Biao Wang, and Ting Yu. GIDN: A lightweight graph inception diffusion network for high-efficient link prediction. CoRR, abs/2210.01301, 2022. doi: 1048550/ARXIV2211000000 URL httpt:t/t/ddale org/10. 48550/ atte//rXivvivee 213000111..
Qifang Zhao, Weidong Ren, Tianyu Li, Xiaoxiao Xu, and Hong Liu. Graphgpt: Graph learning with generative pre-trained transformers. CoRR, abs/2401.00529, 2024. doi: 10.48550/ARXIV.2401. 00529. URL ht http//do.oogg///////// 48550/arXiv
Gábor Lugosi. Concentration inequalities. In Rocco A. Servedio and Tong Zhang, editors, 2/st Annual Conference on Learning Theory COLT 2008, Helsinki, Finland, July 9-12, 2008, pages 7-8. Omnipress, 2008. URL http: htttt::/ccott200B/e cs wwllsinii.fippaper... wwt.f//ppp//iueeeeee /lugosi pdf.
Colin McDiarmid et al. On the method of bounded differences. Surveys in combinatorics, 141(1): 148-188, 1989.
Isaac Chavel. Riemannian geometry: a modern introduction. Number 108. Cambridge university press, 1995.
13

---

Matthias Fey and Jan Eric Lenssen. Fast graph represettttn learning with pytorch geometric. CoRR, abs/1903.02428, 2019. URL http://axxiv.../abbbe//
02428.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- peeh-peffrmaneee deep learning library. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' D'Alché-Bus Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 8024-8035, 8035, 2019. URL https:/ http:///poccceees.e//ee/././s.es peruurrdingg.nuuripss.. wttppppp//019////////eee 2Bbc2288ee7112220058877777777771 Abstrrr Abstract...tt.ee.........aa.aatt html.
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. In Ankur Teredesai, Vipin Kumar, Ying Li, Rómer Rosales, Evimaria Terzi, and George Karypis, editors, Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pages 2623 2631. ACM, 2019. doi: 10.1145/3292500. 3330701, URL https: / /oi. org/ 10. 1145 0294500 3330701.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. LINE: large-scale information network embedding. In Aldo Gangemi, Stefano Leonardi, and Alessandro Panconesi, editors, Proceedings of the 24th International Conference World Wide Web, WWW 2015, Florence, Italy, May 18-22, 2015, pages 1067-1077 ACM, 2015. doi: 10. 11114455273627727410033 URL https: //tp:///oioo/oo org 10. 1145/27362222 220.1666777.24199...
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL URR.htpps//oppeeeeeee...eee wwwp://wwwiieeeeoonmeeeeee ryGs6iA5Km.
Shuming Liang, Yu Ding, Zhidong Li, Bin Liang, Siqi Zhang, Yang Wang, and Fang Chen. Can gnns learn link heuristics? concise review and evaluation of link prediction methods. arXiv preprint arXiv:2411.14711, 2024.
Kaiwen Dong, Zhichun Guo, and Nitesh Chawla. Pure message passing estimate common neighbor for link prediction. Advances in Neural Information Processing Systems, 37:73000~ 73035, 2024.
14

---

Jeasre Shunose Palaacc (Uriginal va Orthogonalized (N)
380 Vine
C4
Jo0
54
Orooginntad 503
Edge Index
Dersity
Figure 6: This figure demonstrates that orthogonalization reduces redundancy in higher-order common neighbors, as shown by the increased and concentrated JSD values, making the representations more independent and distinguishable.
A Evaluating the Effectiveness of Orthogonalization
The orthogonalization process removes redundant information at the matrix granularity. However, for the point pairs (t.j) that we are interested in, we need measure the similarity of the distribution of information between different k-hop CNs at different orders for this point pair. By comparing the difference in similarity
the edge granularity before and after the orthogonalization process, we can objectively assess the effectiveness of orthogonalization in eliminating redundant information at a finer granularity. We introduce the Censen-Shanme Divergence (JSD) as metric, with the core goal being to verify whether orthogonalization can effectively reduce the similarity of the common neighbor matrices between different orders for each edge.
Let Pe and represent the vector corresponding to edge = (i,j) in the matrices of CNa and CNº, and then substitute them into respectively. We will normalize them: P.- Σt Po,k' le Σt 90.6"
the definition of Jensen-Shannon distance:
DJs(Pe, go) = (DKz(fe ma) + DKL m.))
(8)
where m, and Te represent the average P. and go. which are defined as m. = 1/4 (pe. + qo).
As shown in the left part of Figure 6, taking the Collab dataset's C.V1 and CN2 as example, the ISD values between each edge's distribution of CN1 and CN2 are represented by the orange points. The JSD values after orthogonalization (purple points) are generally higher and more concentrated, indicating that the orthogonalization process has successfully transformed the higher-order CN matrices into more independent and distinguishable representations for each node pair (i.j). The density curve on the right reflects the difference before and after orthogonalization for each edge. It evident that the JSD values for the majority of (i.j) pairs have increased after orthogonalization.
B Detailed Representation and Meaning of High-order Common Neighbors
According to Equation (1), assuming there exist k-hop CNs for the two endpoints of interest, the following cases arise:
For k-hop CNs, if = 2A (even), the path contains exactly one k-hop CN (each endpoint k-hops away from the CN). However, there might be more than such k-hop path. In this case, construct w as shown below:
W buo....u..-12
& Ak
Vig EV
Wio ....p........... i2z = p p 2k), E 2, x
15

---

where A represeenss the element in the a-th row and b-th column of the k-th power of the adjaceney matrix. If 2A- (odd), the path contains k-hop CNs. we construct w as shown below:
W ig 11
A k--1
A $22
Vik-1 E V Vig V
1&k 1
W/ Wigmiggia
A 1b
120-1622
(10)
Wimiigaaat = =0,
p E (0, 2 11, p Z. p p
As defined above which can be summarized plainly as: For each order k. we maintain three (h, n
shaped matrices. For example: For 4-order CN: Possible path length to (u, v) combinations are (4, 4), (3, 4), or (4. For 7-rrder CN: Possible combinations are (7, 7). (6, 7), or (7,6).
Take a matrix representing (3, 4) distances as example: Element 2 at position (1c, y) indicates: For the æ-th edge (u, v) the batch, node y has exactly 2 paths (u, v) with lengths precisely (3,4). If = O: Node cannot reach (u, v) via any (3, 4)-leggth paths - it's not a 4-order CN under (3, 4) definition. It might still qualify
4-order CN under (4, 4) or (4, 3) definitions. If none apply: Node y is not 4-order CN for (u, v) at all.
C Proof of Convergence to Global Orthogonality.
Proof.
& (1 31) 6- + BEG
(11)
II (1 B:) 60+ -
-
(12)
1=1
==
5o +
t+1 51
(13)
t
i=1
Σ 1=0
& + SMA
(14)
The inner product ę of each mini batch is an independent and identically distributed (i. d. random variable with finite expected value E[g]] = ç¹ = (C (OCN)) which represents the global inner product of the k-thh CN vector with the i-th OCN vector over the entire graph. As l xc, the running average of the inner product converges to its expectation.
D Related Derivation of normalizedCN.
Definition D.I. we introduce a latent space model [Sarkar et al., 2011] 1] for link prediction that describes graph with N nodes, each associated with location in the space:
if dij max(ra,r)) if d. max(ra
P(i ~ jldis) = 14 max Brog
(15)
where P(i ~ jildy) denotes the probability of forming an edge between nodes and .... dy represents the latent distance between nodes, indicating the likelihood of link forming between them. The model has two parameters, and v, where a > 0 controls the steepness of the function. To ease the analysis, we set a +00. r; is connecting threshold parameter corresponding to node i. With a = +oc, we have
dig > max(r,, ry
(16)
+ coldy-max((e max(r
otherwise (16) equals to 1.
16

---

The nodes are distributed uniformly across a D-dimensional Euclidean space, with each node having an associated radius r and corresponding volume ((r). The probability of establishing a connection between any two nodes i and j. denoted as P(i j), is influenced by both the radii (ri, ry) and the distance dip between them.
1. The volume of ball with radius is expressed as V(r) V(1rr where (r) refers to the volume ball with radius and ((1) is the volume unit-radius hypersphere.
2. The degree of node i, represented by Deg is proportional to the volume V(r.) of the ball corresponding to the node's radius, and given by (ig = NV(rr)), where N represents the total number of nodes.
The likelihood of link between two nodes and forming a function of their distance dij given by the following logistic expression:
P(i ~ j())) ealdy max (r,,r
(17)
where P(i j diz) signifies the probability a connection between nodes and j. > governs the steepness of the transition, and max(r:, defines the critical radius at which the likelihood drops sharply.
In order to ensure the proper normalization of probabilities, we assume that all the nodes are contained within hypersphere of unit volume in the D-dimensional space. The maximum allowable radius, denoted TMAX. is chosen such that:
1/D
((rMAX) = V(I) 1, which implies that 7MAX =
(18)
V(1)
For any pair of nodes and j. the volume of the intersection of the balls with radii and rj. which are separated by a distance dejs is represented by A(r;, Tj, dky). The intersection volume bounded follows using the properties of hyperspheres:
D/2
rs rr dey )
A (rorrj,d)) v(1)
dij 2
<
(1
maaxx
(19)
2
where max max(fri,r) ry). This relation connects the intersection volume A(ra, Ty, diy) to the distance dij through the volume of the unit hypersphere.
Definition D.2. (simple path and set) Given nodes and in graph G(V, F), simple path of length f. from to is defined as a sequence path(i, k k..22.)) where hy ki ke-2 j. and Se(i,j) represents the set all such possible paths, where each intermediate node k1, .2...., kz-2 belongs to the set of vertices V.
be random variable which takes the value if the path (i. K.K1,, k2..... k,,22, belongs Se(i. and otherwise. The total number of paths of length l between and j. denoted as neli,j), is then given by:
Let Y ki, ki.,k
me(i.
Σ
Ki,,ii..... .i....... k. drj)
(20)
l 2E
Lemma D.3.
A < N (1 -22 6/N
with probability at least
(21)
A> N (1+ -33n
with probability at least
(22)
where A is the maximum degree.
17

---

Proof. The degree (kg(k) of any node & is a binomial random variable with expectation E Dege [k)] = NV (Tx). where Vr, is the volume of hypersphere radius rk- Thus, using the Chernoff bound [Lu- gosi, 2008),
Deg(k) < (T+) (1 O/
holds with probability at least 8
(23)
Deg(k) (r (1+ V-33-11 6/NV(r+)) holds with probability at least
(24)
Applying the union bound on all nodes yields the desired proposition, i. e..
< (V((M)))
(1 (1-V-2lnd/NV(rwan = N (1 (1- -2lm8/N)
(25)
> (V(MA)
(1+V-3ln0/NV =N [ -3188//)
(26)
Lemma D.4. For any graph with maximum degree A, we have:
me(i. S m-1
(27)
Proof. This can be demonstrated using straightforward inductive approach. When the graph is represented by its adjacency matrix M, the number of paths of length between nodes and is given by M (i, It is clear that (i, j) can be at most A, which occurs when both i and j have degree A, and their respective neighbors form a perfect matching. Assuming the inductive hypothesis holds for all m < l, we obtain the following:
(i.j) = Σ M(ip))M 5 M(ipp) A
Σ
(28)
Lemma D.5. For l A.
Ine (i,j X XI...., Xp...., ne ( &p X...,, Xx < s=² |
(29)
Proof. Consider all paths where is m hops from (and hence L hops from j). From Theorem D.4, the number of such paths can be at most
1--m-1- A--2
(30)
With the groundwork laid above, we can now proceed to prove our main result in Theorem 5.3. Here, we restate it once again:
Propusition D.6. (Latent space distance bound with k-hop CNs). For any 0, with probability at least 1 - 8, we have
M-2
dis v
Σ
rn+
n=ū
Tex (2,
Dizk 1j
2
(r
(31)
(N V-2N In 26
2N
Tn 2 (rmaa) )2 - (1 (x) DIZI-1
<
n=0
where a = / [n((1 N11(1/26)/2 (N + V-3N In rM max } (M E (1,.... 2h: -1) is the maximum of the feature radius for the set of intermediate nodes in D dimensional Euclidean space.
18

---

N is the number of nodes. k represents the order of the k-hop CNs. (ix j) is the number of k-hop CNs about j.. (The above only shows the case where the k-hop CNs are in symmetric positions, as in (9). The asymmetric case, as in (10), is very similar. )
Proof. Define p)( the probability of observing an ε-hop path between points and j. Next, we compute the expected number of (-hop paths.
Consider E-hop path between j. for clarity of notation, let denote the distances di.k, dRs A2 etc. by 01, d2. up to a and radius rsy Tk....... by To: , Tg-11 We also denote the distances dyks djk2s-.. by d1, .2..... de-1. Note r 7 (1, 1}.
From the triangle inequality,
de-3 S ae-2 + at-1 -
(32)
and by induction,
Ti-
(33)
m=k+1
Similarly,
di 2 (dij - aa144 2 (di; - -:
(34)
and by induction,
k 1
dx 2 dij
(35)
Case (Symmetric case): The K-order common neighbor is located at the midpoint of the path.
P2x(i,,) = Pii ~ ki ~ ~ k j j| dij) P S n... a2z S r26-1 dij)
=
Jd P(11 S STy..... 1 S 122--1.1,,..... d2x-2 dis)
Fak 1tr2k
24 mm=p
(ar S dz diy)) ... P (azk-1 S S12 S r2e d2l-2)
d=z-2=(d1: (dis 2 rn)
di d1=(dur-oo;
2k
2k
2k-3
S
r/
Tim dis
x A
12
Mmm (di² ro)+ x x... x A r'2--1: P2k-
F2k:
(
dij
Σ ra
2
m=3
==
2k
2
p 2
A
Tma
dij
O'
p=1
m=pt1
(36)
r2k-1
p
(i. < A 2k-1
pd
p
Tm:
di
I'
(37)
m=p+1
Case 2 (Asymmetric case): The K-order common neighbor is located at positions on the path, at distance of k-1 hops and k hops from the endpoints, or at positions at distance of k hops and k- hops from the endpoints.
Similarly,
E 1i2k [12k-1(i_))] < 2A22-2 22-
II A
Tim
dij
Σ T
(38)
m=p+1
n=0
19

---

Due to the high similarity between the two cases above. in the following analysis, we will focus only on the symmetric case. Through empirical Bernstein bounds [McDiarmid et al., 1989], we have: For any & > 0.
21 EE=1 C
Pr (f( X,) - 1 X 2 exp
(39)
Back to main proof, have:
N ln(1/20)
12x (1,5)
E 1122 (1,
22--2
2k-1
2k
N Mln(1/28)
A
2k
A
Σ
Tm
dij
Σ
Tn
A
p=1
m=p+1
n=0
2k
2h
p-2
1 (2))
p
mm
dij
Σ
I'
+
N
2
3N In
(N -2 In
8) 2k
m=p+1
n=
(40)
which can be rewritten as:
24 II
72x (1,1) (NN
Pp: Σ
Tim
dij
Σ
I'n
b(N,6,))
(41)
m=p+1
(lm(1/28)
where c(N,8,k) = (N- -WW--220 22 6) 2 and 6(N,6,R)
(N - (N-
VV-V-N 2 5) 2k-1
N+V 3NIn
Note max = max(r Em=pt1 Im we have:
D/2
(iy 2-22 -n I'n
2h-11
72x (1,5) < c(N,6,k) k))
(1 mmaaa
+ D,N,
2
p=1
D/2
2h -
dis 2--2 I'n
= =(N,8,1 k))
+ 1,N,
2
$ 2c(N,8,8)
2h-1
maxx
dij
m Vin
M-
27
D/2
+ 6(N,8K))
3M E (1,.... 2h .2k 1)
(dyy - >m
1--
2
(12k-1)
c((N8,k))
(r
+ 6(N,8,K)
(42)
i.
20

---

M-2
72x (i,5) b(N
DiZK
dis _
Σ n=0
On + +2/
(1
c(N, δ,
M-2
mi2k (i.
N (la11/2))
D(ZE-1)
<
Σ
In + 2
(riaay)2
(N 2-
2N In 1182k-1
N
3N In
(43)
n=0
M-2
(ln(1/28)
DIEN
<<
In + 2
(riaax)2
2
N
3N In
1=0
The motivation for introducing normalizedCN has been explained in detail in the main text. After introducing normalizedCN, will derive Theorem 5.4, which we restate here as follows:
Proposition D.7. (Latent space distance bound with h-hop CNs weighted by normalizedCN(i.)) Originally, the contribution of each k-hop CN was assigned a value of 1. However, after introducing normalizedCN, the contribution of each k-hop CN is now given by EeecN* (5.5) [P[o]] Therefore, mac(t.))
we simply need modify the overall contribution (i, Decont(s) P/(P(())) For any > with probability at least 1 we have
M Σ n=0
(1
D(K-1]
26
di S
On +
(44)
where Ç is the maximum degree of all k-hop CNs of (i,j) and p [0, and γ (2x(i.))
[N- (N-V-2N inn---- -a). (The above only shows the case where the k-hop CNs are in symmetric positions, as (9). The asymmetric case, as in (10), is very similar. )
Proof. Consider the metric: the k-hop CNs we are interested in are also the k-hopp CNs of several other pairs. We record the reciprocal of the sum of these pairs as the weight of the k-hop CNs.
N-n-1
k
k
(i >
A
m
I'm
A
Tm
D;
p+
p+
(45)
N-n-1
k
(i,j) <
A
Tmm
D;
Σ
A
Tm:
m mmpp)
n=0
p=1
p+
(46)
21

---

k
k
E [[TEONK
(1)
A
p
mm
I'
m=p+1
m=p
N-n-1
A:
k
p- 2
A
Tmm
D;
Σ ==
I'
m==+1
Dik 11-
N-n-1
T'min
D(K-1)7
(T's )²-
(DD
Em= I'n
2
(47)
E (vaa (i,
N (l((1/2))
(2)(1, z
A 2k-22
Dik-11
N-n-1
2
I'm
Vai
117-
(rupax )² -
D Pn--nm 1- Fui
(48)
Consider (p (p (1-pD(e-1)) pD(6-1)) 13) N-
(m) where ((K--1) + 1)(
1))-1)), So We get:
E (1,
NIn(1/25)
(in S
(5) (max P(K-1)N + 1
(49)
2
Note = (2) (maxfp: (ptE)) P(K- ((k we have: cN,,8kk c(N.6.k) and 6(V,8, 6(N,8,
M 2
1/2x (1,5) ((N,5K))
DISk
dij <
In + 2/
(mmax)²
==0
M-2
(2k(1, 5) ((N,8M
DI26-11
<
Σ ==0
I' +
(rypay2
((N.6.))
M-2
N Ln(L/28)
D(2k-1)
<
Σ n=0
In +
(rmna) x 1
(50)
N --3 Ind
3N
30c 1
<
M-2 Σ n=0
Fn + 2,
(r
(T(5)
D(6-1)
(max E})
2k-2 -E-T
2
Dik-oj
Σ Fa +2,
(r
'p
=
n=0
where 7 = (N-v-2N Ind
York (i.)
a) and = max 3.
Additionally, in negative curvature spaces, the contribution of high-hop common neighbors becomes more significant. Euclidean space may underestimate it because the connectivity of nodes is more
22

---

dependent on local geometric structures, whereas in hyperbolic space, the global structure and curvature effects between nodes have a more pronounced impact on path propagation, meaning that the high-hop CNs information between nodes exhibits stronger structural dependence. In some tree-like graph structures, or in regions of graphs with negative curvature, large number of high-hop CNs of various orders are more likely to occur. We hope that normalizedCN can assign reasonable weight to each k-hop CNs in the hyperbolic space.
Proposition D.8. When the latent space becomes a hyperbolic space with curvature K, normalizedCN still remains effective, without the need to explicitly introduce in the form of normalizedCN.
Proof. The volume of sphere or a ball in hyperbolic nespace with sectional curvature 6 is given by
(Sini(( (
Vir(r) cn-1
dt,
(51)
where Cp-1 = 2/2 [(n/2)
is the n 1- 1-dimensional area of a unit sphere in R" (see [Chavel, 1995]).
Let R 1
we have:
V=
Vi(r) = Cn-1R" [ sinh n-1 1
dt
(52)
R
Using the recurrence formula for integrals involving hyperbolic functions f sinh" exda (n > 0), we finally obtain:
n-1 cr cosh ex n-1 s-nh"=2 crdr
1. When n is even (n = 2k):
1)t (n 1)(n - .....pp In (2k 1)]
" (n
1)(n -3...... ... 3.
An f(m)(((())))))))))) k=1
n(n 2n 4)... ... [n (2k 2)] f( (-)))
n(n 2) 4.2
(53)
2. When is odd (n = 2k + 1):
(-1) (n 1)(n 3)... (2k 1)]
An ((n) +
[(n (k))
(54)
n(n 2)(n 4) ... [n - (2k 2)]
Where f(n) 1 (sinh ar ar), V-k, and V2(r) Cn-RR"-1 An-1
ax
follows naturally that:
(at (er----rr -
cr + e- + e
v(r) - v(1)
(55)
Clearly, when x approaches 0, which means the space degenerates from hyperbolic space to Euclidean space, we have:
D
eor e e C
cor + -ar ea + e-a
lim
= D
(56)
This is consistent with the result for Euclidean space.
We first need to find an upper bound for the volume of the intersection of two spheres hyperbolic n-space with centers at O and O₂ by scaling. In this case, we assume symmetry, as shown in Figure 7, where the upper bound for the volume of the intersection is the volume of sphere with radius We can set up the following system of equations:
23

---

d
01
r
r
r
r
2r
2
Figure 7: The upper bound for the volume of the intersection of spheres in hyperbolic n-space with centers at O and O₂ is the volume of a sphere with radius т.
cosh cosh sinli 2
cos
sinh d sinh r
(57)
a sin 0
cosh T = cosh sinh cos(20)
Here, assuming the Gaussian curvature of the space is + d represents $. represents F, and represents for simplicity in form. The solution is:
8yy 1)
cosh 7 = 2x 1
(58)
where x = cosh d and = cosh
Thus, when is greater than 64, we can almost assume that:
A
car - e-ar
car + e ear
< [[V-x)]]
(59)
V(1)
ea e-a
ea + -
Similar to (42), derive:
cash
(32(a-1))
12
(an(i,j) c(N,8,8)
VK
+ b6N, 8,N,)
(60)
Since the range of dı is [0, 1]. within this range, we can approximate - as 1 (x - 1)2, which is similar the approach taken in Euclidean space. Ultimately, we can derive:
cosh
(log/=
n-b
Disk-
dij cosh
<
+1
(61)
K
8 cosh2 2 rggin
The form of (61) is very similar to (D). Following the same approach as in Euclidean space, after introducing normalizedCN, we can finally conclude that the effect of dey brought by normalizedCN is consistent with that in Euclidean space.
24

---

Table 3: Statistics of dataset.
Cora
Citeseer
Pubmed
Collab
PPA
DDI
Citation2
#Nodes #dges
2. 708
327
18, 717
235, 868
576, 289
4, 267 134,, 889 fixed 312.84
2, 927, 963 30, 561, 187 fixed
5, 278
4, 676
44, 327
1, 285, 465
30, 326, 273 fixed 52.62
slits
random
random 2.74
random 4.5
fixed
average degree
3.9
5.45
10.44
E Proof of Theorem 6.1
Proof. When algorithm A distinguish all the link pairs that algorithm B can distinguish, consider algorithm A to be more expressive than algorithm B. provided there exists a pair of links that can distinguish but cannot. Therefore, can prove this by constructing simple counterexample.
Graph Autoencoder's prediction for link (i. is (MPNN(i, A, X), MPNN A, X))- So MP A, X) @ MPNN( A, X) leads to GAE which is part of OCN, so OCN can also express GAE. As MPNN can learn arbitrary functions node degrees, OCN can express CN, RA, AA we construct example in Figure 4. White, green, orange, and yellow represent node features 0, 1, 2, and 3, respectively. U2 and V3 are symmetric, and GAE cannot distinguish (v1, v2) and (v), 03). With node features ignored, (v1, 02) and (V1, 03) symmetrie, CN, RA, AA, Neo-GNN, and BUDDY cannot distinguish them. NCN also degenerates into GAE, so also cannot. However, (V1, 02) and (U1, U3) have different 2-hop CNs, which allows OCN to distinguish them.
F
Dataset Statistics
The statistics for each dataset are presented in Table 3. The data is randomly split with 70%, 10%, and 20% allocated to the training, validation, and test sets, respectively. Unlike the others, the collab dataset permits the of validation edges as input for the test set.
Cora, Citeseer, and Pubmed are very small-scale graphs where link prediction is relatively easy. Existing models have nearly saturated performance on these small graphs. The real challenge in link prediction lies in large-scale graphs. Our model achieves significant performance improvements on these haguevalue, challenging large graphs, particularly on ogbl-ppa and ogbl-ddi.
G Model Architecture
(i,
OCN
hy hy
M
A
Ā
h
LLP
A
O0N' MPNN(A.))
R
OCN+
Figure Architecture of OCN.
Target Link Removal. We do not modify the input graph during the validation and test phases, where the target links remain hidden. For the training set, we remove the target links from A, and we define the modified graph A.
25

---

Table 4: Parameter configurations (OCN) actoss different datasets.
Dutasat
miskinpot
mmplagrrs
unlayers
lridiim
In
Inmn
jk
gundp
sdp
tdp
gumslp
pnokp
pocedp
gaulr
preir
uvr_sin
tallact
0.0024
0.000
0.002
0.0015
Clasion2
0.12
0,0009
DDI
0.55
0.18
0.5
0.10
0.13
0.00086 0.000
MPNN. To generate the node representations h, we employ the MPNN framework. For each node i, the representation is obtained by:
h; MPNN(i, X)
(62)
In the case of all target links, MPNN is exccuted only once. Predictor. The link prediction task leverages node representations and the graph structure. The link
representations for OCN are computed as follows:
K
3ig = (1, A, X) & MPNN(J, A,X) Og OCNK BRONK MPNN(A, X)
(63)
Here, By denotes the representation of the link (i.j), The resulting representation is then processed predict the likelihood of the link's existence:
Å. siggoid(MM... (MLP(zig)
(64)
H Experimental Settings
Computing Setup. We utilize PyTorch Geometric [Fey and Lenssen, 2019] and PyTorch [Paszke et al., 2019] for developing the models. All experiments are performed Linux server equipped with an Nvidia 4090 GPU.
Baselines. The results reported in [Wang et al., 2024] are directly used for comparison.
Model Hyperparameters. For hyperparameter tuning, we employ Optuna [Akiba et al., 2019] to conduct random search. The hyperparameters that yield the best validation scores are chosen for each model. The complete hyperparameter configuration listed in Table 4 and Table 5.The key hyperparameters in our framework are defined as follows:
maskinput: Boolean indicator for target link removal during training
mplayers: Number of message passing layers in the GNN architecture
nnlayers: Depth of Multilayer Perceptron (MLP) components
In: Layer normalization switch for MPNN modules
Innn: Layer normalization control MLP components
jk: Jumping Knowledge connection enablement
gnndp: Dropout probability applied to GNN node representations
gnnedp: Edge dropout ratio for graph adjacency matrices
predp: Dropout rate in the prediction head network
preedp: Edge dropout probability during prediction
genlr: Learning rate for GNN parameter optimization
prelr: Learning rate specific to predictor module
Training Procedure. We optimize models using the Adam optimizer. Results for all models averaged from 10 runs with different random seeds.
Computation Time. The total computational cost for reproducing all experiments is shown Table 6.
26

---

Table 5: Parameter configurations (OCNP) across different datasets.
Dotanet
muckinput
implayers
sulayers
hiddim
In
Iunn
nos
jk
gundp
xdp
Idp
gonedp
predp
presip
pealr
pedl
usc. Alin
Iallact
Coru
256
I
I
0.05
0.7
0.3
0.01
0.05
0.4
0.0043
U10024
Classer
0.12
0.88
0.06
0/5010
Pahural
0.1
0.3
0.0097
0.002
0.1
0.23
0,0077
Chario22
0.28
0.0022
0,0008
0.25
0.13
0.009
0,008
Table 6: Total time(s) needed in one run
CORA
CITESEER
PUBMED
COLLAB
PPA
CITATION2
DDI
OCN
10
24
110
380
17010
18132
1600
OCNP
9
21
96
350
16770
21520
1131
I Time and Space Complexity
Let represent the number of target links, n the total number of nodes in the graph, and the maximum degree of a node. The time and space complexities of the existing models can be written as O(B + Ct) and O(D + Et), respectively. The constants B, C, D, and are independent of t, as summarized in Table 7. The derivation of complexity is as follows: models such as NCN [Wang et al., 2024], GAE [Kipf and Welling, 2016], and GNN, which utilize different structural features and operate the original graph, exhibit similar complexities of ndF + nF? Specifically, the method by BUDDY [Chamberlain et al., 2023] uses a simplified version of MPNN, simplifying the complexity term B ndF. Additionally, Neo-GNN [Yun al., 2021] requires precomputing the higher-order graph A', which results in time and space complexity of ((dd', ). BUDDY hashes each node, resulting in ((nh) time and Onnh') space complexity. In contrast, SEAL [Zhang and Chen, 2018 88's B is O, as it does not run MPNN on the original graph. For each target link, a vanilla GNN simply requires feeding the feature vector an MLP, yielding C 122 In addition to GAE's operation, BUDDY also hashes the structural features, which introduces a higher complexity per edge, (d'), where is the number of hops Neo-GNN considers. For each target link, SEAL segregates subgraph size O(d'),
), where represents the number of hops in the subgraph, and runs MPNN on it, which gives C' ==dd d' F2 + d''1 time, pools the node embeddings with complexity of OddF), and feeds them into MLP, resulting in O(F3). NCNC-1 runs NCN for each possible common neighbor, leading to time complexity of O + +dF²). For higher-order computations, NCNC-K executes (dd) times NCNC-K, resulting in time complexity of (dd F + d F²). OCN computes k-hop CNs with complexity O(d²).
+1 F. NCN computes common neighbors in (d)
The process Schmidt orthogonalization has a time complexity of O(k"n), and it computes (63) with complexity of (dF). Finally, OCN feeds it into an MLP, resulting in O(F2). Similarly, the only difference between OCNP and OCN is that OCNP replaces the Schmidt orthogonalization process with Polynomial Filters, which results in time complexity of (Km)).
OCNP
According to Equation (1), we can express CN,, and transform the Hadamard product into a Kronecker product(8) with many desirable properties. We have:
CN₂ =
U
(PIA + (P2Atz)
24
= J P2 K
(65)
=J Pa) A K
km 1(
(P B (WT @ @W K,
27

---

Table 7: Scalability comparison. h, N., h" the complexity of hash function in BUDDY, where all 2 I. F: the dimension of node representations. When predicting the t target links, time and space complexity of existing models can be expressed as O(B Ct) and O(D + Et), respectively.
METHOD
B
GAE
rd. + nF² ndF + nF ndt
F
nF
NEO-GNN
d' + F2 + F2 d' 41 F d' F2 dF Fd
nF nat
d F
BUDDY
ndF + nh
nF + nh"
F +
l
SEAL
0
d' +1 F
NCN
ndF + nF
nF
dF
NCNC
ndF + nF
d dF
nF
d' F
OCN
ndF + nF
d + k2n dF F
nF
dF
OCNP
ndF + nF
d kn + F22
nF
where P1 and P3 are called selection matrices, defined as Plj.k| 8(S[1,j], k),, where S E 22xh describes the start and end points of each edge. Expanding Σ
))* abbreviate it as [k]]
[K]
Σ
Σ)
(66)
x
Therefore, we can write CN2, as CN = U [k, V. We note that the Frobenius inner product the Schmidt orthogonalization process can be derived follows:
1
(ICNKA +CNKs 12 ||CNKa CNNKNNE lle)
(CNKA) CN
7
1
U [KA + kB) V + [KA kB] VIII KA + kBl - U [Ka
KB] VI
4
Σ of (k))
of (U
(67)
Here, of (A) represents the i-th singular value of A. Next, abbreviate VE (U kk V) as VΣ o² (kn). Then, we can write the Schmidt orthogonalization process for as follows:
B (B, - (B, A2)
-U[bb] V Σ oz (ka) Σ o2 (KE)U [k]] oF (KA
[K]
= UUV
(68)
For given term 2/ kk), we abbreviate as N Therefore, after undergoing Schmidt orthogo- nalization, each eigenvalue in the diagonal matrix undergoes the following transformation:
28

---

Ak1 Σ 02 (Ri)
a
E1o
(kB)
VE (k22)
5 (kB)
X,j
X
(69)
= 1 Σ [22(kn))
ky
]
Σ 02 2kB - i)
That is to say, the original B is equivalent to the following transformation:
CN
V=U
[ ( Eke-l (Ko 1)5 1
v
CNEB
1
Ei=r v2 (k()) D (kn i)
(70)
We abbreviate
1 E VΣ 02 (KB)
oz -i)
02
as g(kB). We then
select two different CNK, and CN& to analyze the relationship between g(ka) and g(kn). When kn is not significantly larger than ka, note that there is:
0² (KB)) S (KB -kB 1)215) ]
02 (KA - 1)/11) 02 (KA))
Σ
2
02 (Ka) V Σ 02 (KA - -1)
]
2
of (U (kai))
Σ of (U [KA -VA
(71)
We assume that the introduction of (Pn & P2) and K does not significantly alter the larger eigen- values in the adjacency matrix A. Therefore, consider the larger singular values to correspond to the larger eigenvalues. Assuming we only consider the top largest singular values, we have:
]
g(ka) @ g(kn)
Σ 2
1
of (U(A)))
Σ of (U -
-1
(72)
(h + 1)2 (2
X3 X3)
+ + X2
This means that in our framework, g(ka) and gkk)) are approximately orthogonal.
Thus, we can obtain OCNP through the following operations: Let the k-th term of the selected polynomials be Tą. Then, OCN* = CN* diag(TT). and we only need to replace the step in Algorithm 2 with:
29

---

Table Results on link prediction benchmarks. The format average score + standard deviation. +tricks means model with tricks of PLNLP.
COLLAB
PPA
CITATION2
DDI
METRIC
HITS@ 50
HITS@ 100
MRR
HITS@20
NODE2VEC
41.36-10.69
27.8342.02
53.47=0.12
21.95-11.58
DEEPWALK
50.37+:0.44
28.88+1.53
84.48-00.30
26.42-16.10
LINE
55.13+1.35
26.03+2.55
82.33-1.552
10.15=1.699
PLNLP
70.59=0.229
32.38+2.558
84.92:0.29
90.88=3.13
GIDN
70.96=0.55
OCN
72.43
69.79:10.85
88.57=0.06
97.42=10.34
OCNP
67.74+0.16
74.87+0.94
87.06+0.27
97.65+0.38
NCN+TSSCKS
68.04+0.42
90.83+2.83
OCN
69.03+0.94
69.23+0.39
88.97=0.12
94.25-0071
OCNP+TRICKS
69.8910.22
73.44.00.73
88.7910.21
97.43
OCN* = CN diag(TT).
(73)
K Comparison with other Link Prediction Models
A key strength of GNNs lies in their inherent capacity preserve permutation equivariance, meaning that edges with identical structural patterns- referred prediction. On the other hand, traditional node embedding methods, such as Node2Vec [Grover and Leskovee, 2016], LINE [Tang et al., 2015], and Welk [Perozzi et al., 2014], often provide inconsistent results for isomorphic edges, which impair their ability generalize. In our study, compared the performance of our proposed methods against these well-established node embedding methods, using several OGB datasets. Furthermore, PLNLP [Wang et al., 2021] and GIDN [Wang et al., 2022] improve their performance by employing a variety of training strategies, such as adjustments the loss function and data augmentation techniques. As seen our experiments (Table 8), we also applied the PLNLP tricks. While these adjustments did not yield substantial improvements, our models still delivered superior performance compared both the node embedding methods and the models incorporating training tricks, irrespective of whether the tricks were applied.
natters--efeerree to as isomorphic edges can can give the same
L Ablation of MPNN
We provide an ablation study on the MPNN used OCN and OCNP. The results are shown in Table The MPNN models include GIN [Xu et al., 2019], GraphSage [Hamilton et al., 2017], MPNN with MAX aggregation, MPNN with SUM aggregation, MPNN with MEAN aggregation, and GCN [Kipf and Welling, 2017].
M Scalability Comparison on Datasets
The time and memory consumption models on different datasets are shown Figure 9. On these datasets, we observe results that are somewhat similar to those on the ogbl-collab dataset in Figure 5. OCN and OCNP generally scale better than Nco-GNN. SEAL has the worst scalability. The memory overhead of OCN is comparable to slightly higher than NCN. In general. both the time and memory overhead of OCNP are better than those of OCN.
Liang et al. [2024] experimentally emphasizes the importance of explicitly incorporating NCN (number of common neighbors) deepedden structural information and highlights that ordinary GNNs cannot learn such structural patterns. However, Dong et al. [2024] further demonstrates that while ordinary GNNs indeed cannot learn CN, they can acquire CN knowledge by introducing noise as auxiliary input (though the learned CN contains variance). This approach significantly increases both parameter size and computational overhead, resulting in poor scalability. Our model exhibits substantially better scalability and efficiency compared to MPLP [Dong et al., 2024].
30

---

Table 9: Ablation study MPNN.
Dataset
Model
GCN
GIN
GraphSage
MAX
SUM
MEAN
Cora
GAE
8..0
70.45.11.88
70.5
61.63:14.43
NCN
89,05=0,96
70,62=11.6
10,94
66.53#2.27
OCN
89.82=0.91 13.55=1991
53.14+1.87
46.9411.84
45.46
1.72
OCNP
90.06=1.011
1..09=11.02
74.96:1.25
67.92
7.478
71.90
Citeseer
GAE
91.78:+0.94
61.21
61.23:+1.28
53.02::3.75
NCN
11.56++1.43
61.58++1.18
61.95++1.05
53.40++2.34
OCN
19.57=1..7
66.29:14.09
65.87=1377
88. 88.9113.27
90.05:2.28
13.62211.30
OCNP
89.95-12.34
68.6913.26
49.95
89.13
90.52+1.66
9..41=1002
Pubmed
GAE
1..81+1.64
59.00+00.11
57.20+11.37
55.08+1.443
NCN
79.05+1.116
59.06+00.49
58.06+0..9
56.32+00.77
OCN
83.9610.551 1..10
63.8011106
52.4311.007
61.22.0.58
52.62.16.01
OCNP
82.32
6,.
1..48
56.90.1.555
29.48.12.49
54.43
collab
GAE
36.96+00.95
38.94+0.81
28.11+0.26
27.08
NCN
64.76+0087
64.38+00.06
63.94+0.43
64.19
OCN
09.2
32.43++3.75
66. 0.33
0..9
65.35+00440
65.36+0.34
OCNP
67.74:10.16
57.70 3.56
58.26:12..64
59.31
60.30
19.09
GAE
19.49=00.7
10,25
11.79+1.02
20.86=#0.81
NCN
0..1
07.9
56.41 OOM
50.31
OCN
69.79:0088
67.29
OOM
59.23310.56
OOM
OCNP
74.87+00.94
1..08++1.03
OOM
OOM
6..59+
OOM
Citation2
OCN
88.57+00.06
70.09+42.77
OOM
OOM
0.24
OOM
OCNP
87.06-10.27
OOM
OOM
OOM
0.34:00.09
OOM
DDI
OCN
97.42+0.33
55.88+1.771
19.33-+13.66
0.45--0.33
0.68+
12.27+4..3 6.94 +2.71
OCNP
97.65++0.38
52.38+2.98
49.03++12.2
0. 0.19
1.04+:0.46
N
Discussion Highlighting Differences from NCN
The primary motivation of NCN (and NCNC) lies in proposing a new architecture MPNN-then-SF aiming to address various limitations the previous two major architectures (SF-then-MPNN and SF-and-MPNN), Here, NCN is just instantiation of MPNN-then-SS while NCNC is merely itcrative version of NCN, Neither focuses on incorporating higher-order CN; in fact, NCN found that attempting to introduce higher-order CN leads to performance degradation, and causes out-of-memory (OOM) issues on large graphs.
In contrast, work directly targets the utilization of higher-order CN from the outset. We systemat- ically investigate and summarize why existing methods of incorporating higher-order CN perform poorly. Ultimately, we identified the key phenomena mentioned in study these precisely what cause the performance deterioration when introducing higher-order CN. Therefore, our core motivation is unlock the potential of higher-order CN by addressing these phenomena.
Equation (7) may appear similar to NCN at first glance. However, our primary motivation and contribution lic in employing two key methods to incorporate higher-order CN for addressing the two phenomena we first discovered. Thus, our core contribution focuses on the preprocessing of CN before it reaches Equation (7) the equation itself merely represents summation step. The structural resemblance to NCN exists because our innovation doesn't 't involve architectural modifications, hence we retained NCN's MPNN-then -thnn-SFF framework. We also analyzed the performance using SF-and-MPNN structure in our ablation studies.
We focus on the values of: for OCN1 and for OCN2, To ensure fair comparison with OCN, we also introduced higher-order CN to NCN and analyzed: on for CN1 and 02 for CN2, We present the results from Figure 10a to Figure 101.
31

---

BUDDY
10
10
memeryytg
GPU memory/Ga
10
309
times
10"1
10
10
10-1
10a
10
10a
10
10a
30"
10
batch size
batch size
batch size
batch $26
(a)Cora
(h)
GPU memory/Ga
GPU memory/Ga
10-1
timel
10
10-1
10'2
10-2
10-1
30-
batch
batch
Pu)bdb
(d) Oppl-ppa
GPU memory/oa
10t
104
GPU momeryica
1.09
timels
10*
100
100
10'0
10a4
10a
10
16
1.4 batch size
10
10f
16
30
batch size
batch 5ize
batch size
(e)0gbl-ddi
(D0bbl-citation2
Figure 9: Inference time and GPU memory on datasets. The process we measure includes preprocess- ing, MPNN, and predicting one batch of test links.
Across all datasets, the learned a1 and 02 values are highly consistent between OCN and OCNP. Additionally, ai and a2 remain relatively stable across all epochs (we only show epoch 1, epoch 50 and epoch 100 due to space limitations), with a₁ always being greater than a:2.
Through comparative analysis,
draw the following conclusions:
The orthogonalization and normalization in our method lead to significantly faster convergence.
2. First-order neighbors are more important than second-order. Since NCN does not perform orthogonalization between CN1 and CN2, it results in certain similarity between CN1 and CN2, which leads to instability in their importance. Therefore, NCN fails to maintain the inductive bias where 02 < 011 On large graphs. NCN suffers from OOM issues and cannot complete the lincar combination of higher-order CN.
3. NCN reported performance degradation when incorporating higher-order CN which is likely caused by the two key phenomena discovered in our work.
O Analysis of the Performance Gap Resulting from Changing the Aggregation Strategy from Summation to Concatenation
We first formulate the final step of our original model OCN (OCNP) as:
MLP (MPNN(i, A, X) MPNN(,, A, a O MPNNNA,NN ag O. MMNN (A, (A,X))
(74)
And the final step of OCN-CAT (OCNP-CAT) is formulated as:
MLP (MPNN(i, A, X) O MPNN(J, 4, X) || an OCN!, MPNN X) 02 OCN? MPNN (A, X))
(75)
32

---

(a) OCN: Cora
(b) OCNP: Cora
(c) NCN: Cora
(d) OCN: Citeseer
OCNP: Citeseer
(f) NCN: Citeseer
( OCN: Pubmed
(h) OCNP: Pubmed
ii NCN: Pubmed
ii OCN: Collab
(k) OCNP: Collab
NCN: Collab
Figure 10: In the figure, ag. a1, and 3 represent the learned coefficients for OCN1 OCN? and MPNN(1, X) @ MPNN(J, X) respectively the expression MPNN(1, X, ④ MPNNG, A, X) + E 0g OCN' MPNN(A,
33

---

Algorithm ORTHIOGONALZZATIONVEEEBR
Input: (CN
lk=1 mini-batch B, {[CC)) ( 1 Truncated polynomial order K;
Running inner product {f5") K Timl h-1 over the last mini-batch, Output: Orthogonalized data (OCN)) JR=1
Initialize OCN; +- CN, |1 for k to K do if training then
for 1 to k 1 do
& + (CN; OCN;)
D Inner product within this batch
3. < 1)
St f (1- -1-111)) + 9:5t
> Maintain the global running inner product between
mini-batches
end for end if
CN k-1 -CNN
OCN + CNt /ICNN
end for return {OCN 1k=1
For the -CAT variant: 1. The MLP parameters are divided into three parts [W]][, [W3). 2. The norms of different parts and a values jointly determine the importance of different orders.
Experimental results show the norms of the linear layers as presented from Figure 11a to Fig- ure 11. where W1 corresponds OCN1 W2 corresponds to OCN2 and W3 corresponds to MPNN(i, A, X) O MPNN(J, A, X). For OCN (OCNP), the MLP parameters W do not need split into (WallWa||Wa W3), and their norms are shown by the purple line (from Figure lf to Figure 1j)..
Our empirical analysis reveals two key insights regarding the model's learning behavior:
1. Norm Distribution Pattern:
The parameter norms associated with higher-order neighbor representations exhibit monotonic growth across network layers (i.e., |[*())|2 increases with order k), indicating the model's 's inherent preference for amplifying higher-order neigh- borhood information through geometric scaling.
2. Operator Dynamics Comparison: Through controlled experiments comparing concatena- tion (CAT) and summation (SUM) operators, we observe:
Magnitude Disparity: CAT implementations consistently produce larger parameter norms than their SUM counterparts (|]W<rT]|2 > || l|)
The SUM formulation fsUM lin lin(E k=1 0g (+)) enables explicit control over neighborhood order importance through learnable coefficients {at) where ag directly determines the relative contribution of k-tt order features.
Control Mechanism:
K
Coupling Effect:: In contrast, the CAT formulation fCAT lin K l (k)) demon- strates parameter entanglement between projection matrices and coefficients, as the effective importance becomes jointly determined by aę and the induced ||[ dællla norms in the linear transformation, where d, denotes the dimension slice for k-th order features.
P Algorithm
Please refer to Algorithm and Algorithm 2.
34

---

Splt Weight Nerm
Spitt Waight Norma
Joc3 parti part
6.5
6.0
Wi wond swrt)
5.
382
bpech
(a) -CAT: Cora
(b) -CAT: Citeseer
Split Weightt Norms
Split Weight Norms
11.
271, bec't part)
pentt ewrt)
10-
14,
25
320
177
20
340
Epac2
Eoach
(c) -CAT: Pubmed
(d) -CAT: Collab
Weight Norms
3.
Brangee
Spit Weight Norms
mond vi panis
20
00
100
22
382
(c) -CAT: DDI
(1) -SUM: Cora
Layer Weight Norms
Layer Weight horms
3.1
0.73
6.50
23
2.8
5.50
277
5.25
3.00
(g) -SUM: Citeseer
(h) -SUM: Pubmed
Layer Whightt
Layar Weightt
5.3
2.3
2.8
tzech
-SUM: Collab
(i) SUMM DDI
Figure 11: Norms of the linear layers where W1 corresponds OCN' W2 corresponds OCN2 and W3 corresponds to MPNN(i, X) @ MPNN(j, A, X). For OCN (OCNP), the MLP parameters W do not need to be split into (W, (W))), and their norms are shown by the purple line.
35

---

Algorithm 2 OCNOVERBATCH
mini-batch B. {[NN) 1k=12 ;Truncated polynomial order K K:Running inner product ((=")==)t and v over the last mini-batch:inpt graph A, node feature matrix X and target links ((1,,1), (2), (fc.1)]
Input: {CN k==
Learnable Parameters: ag,, all parameters in MPNNs
Output: link existence probability Aij for k to K do if training then
d CN* T 11 - 1/(1+t)]
1 (1 nn + nove
Convergence to the full graph of CN normalizedlN
end if
CN CNº diag ((vA))
end for
{OCN) Ik=1
(76)
(I
(77)
Zy + (,, X) as described in (7) A. +- (MLLP(Zi)) return Aij
Theoretical Analysis with Barabási-Albert Model
The theoretical analysis is conducted on random graph models, which may not fully capture the structural properties of real-world networks. Therefore, we extend the theoretical arguments the more realistic Terrbási-Albber model, Given the numerous variants and extensions of this model, we select a class with broader universal significance. The specific construction method of a graph this model is as follows:
Definition Q.1. (Graph-Construuce Construction Barabási-Albert Form Gv from Gn-1 by adding vertex n, sampling (with replacement) verfices W1, ....... Wm from Gn-1, bb and connecting each we
Conditioned the past, the wi are i.i.d.: for k <
deg d (k)
Pr(w; = k)
degn-1 (k:). 7=
Σ
(78)
Definition Q.2. We define the score sy based on the linking probability of (i.
Pr(i ~ josig, Gmmar(t.))1) + (mon(s))))
(79)
where sutisfies deg(k) NV(r)) NV(1) N= =
Proposition Q.3. When connecting an edge at vertex b, the expectation of degree of vertex (assuming b >> a) is:
E(deg,(a)) = m (2/a bl 1)!!
(80)
2/a la bl!
Simultaneously,
E[Pr(a ~ b[G 4la-b/ oj la-bl
(2le-b)
O(1a - -/-
(81)
ग la bj
Proof. Consider that when forming Gş, the newly added vertex S, and let the number of edges connecting & to the previously existing vertices be m, i.c. deg (E) m. When forming Gę+1, the
36

---

newly added vertex is Ç + 1, and it is clear that the expected contribution of ç + to the degree of this time
doge (E)
(E) = 2m(5 - 1)
m..
(82)
By analogy. when forming G5+2, we have
dege(E (E) + (1)
2
m..
(83)
2m
At this point, we can restate the problem as the following problem of finding the general term of sequence:
The first term Ei = 0, the second term E2 = m, and for 3, the recurrence formula
E, Ei L22 + Ei-1
(84)
2(1-22 -2)
According to the recurrence formula, for v 2 3: Ey.
Su-1
2)n-2)-
Meanwhile, the partial sums satisfy: Sy = S + Ev. Substituting Eg:
S. = S + S S
2v -
(85)
2(v 2)
2(v 2)
lterating from v
2j -
2j 3 3
S. S₂ 11
II /=3
V 0 2.
(86)
2(j
2)
2(j 2)
j=3
Splitting the product into two parts:
2j 3
17
11 II
2j 3 j 2
(87)
2(j
2)
j=3
The first part:
1
w-2
II 1=3
(88)
2
2
For the second part, let & = j 2, then when j 3, kt 1, and when j = u, k = U
2:
2 3
1-
2(k + 2) 3
1ー 2k +
1I j=3
11
(89)
j
k=1 k
k=1
Now compute the product
Im
1
where
= V 2:
-=
2k
(2k + 1)
IT (2k + 1) m!!
1=
(90)
k
1==1 h
Given:
m
(2m 2)!
II
(2k + 1)
(91)
2 (m + 1)!
37

---

Therefore:
2k +1
(2(1 2) + 2)
(2u 2)
(92)
k
2 2(v-2)+1 - 2) + 1)!(U 2)
20-1 1)!(U - 2)!
1 1-2
(2v 2)
(2u 2)
m
m 2=
(93)
2 (0 (v 2)
(0 1)!(v: - 2)
Note that:
(2v 2)
2v - 2
(v 1)
(94)
(v 1)((1 2)
Therefore:
S. = =mm(v - -1) (2v (20-2) -2
2
-21+3
1 12
(95)
m(v - -2) (2
22 2044
Eg
m
(96)
2(v - 2)
1 -
That is:
22-2(2(1 - 2) 1)!! (v ---2 2)!
(2v 5)!! 1
E, = m
(97)
(u 2)! 2
Returning to our original problem, we consider the expectation of the degree of vertex when connecting an edge at vertex b, and we can clearly obtain:
(2 1)!!
E(dega(a)) = m
(98)
2/a bl
a
b/!
And we have:
E[Pr(a ~ b[Gb-1)] = 4la-b/ la-b)) ~
O(Ia - - b(-
(99)
V n
Proposition Q.4. For any 8 O, with probability at least 5, we have
II 2h (2A +1J!!
24 At! + A 118-1
Po)(i,)) S
2
(100)
22k (min(i, k1. k22-1.1) 2])2k*
where A max((k: k(t1l)-
Proof. The idea of the proof is very similar our previous proof of Theorem 5.3. First, from the result of Theorem Q.3, we can easily obtain: For any t > 0,
2t
Pr (deg, (a) EEdeg, (a) 2 t) < exp
(101)
b|m²
Similar to the method used earlier to prove Theorem 5.3, can similarly obtain:
38

---

m b +14
la-bi In
+
P(a ~ b)
2 la bl!
(102)
2m(b 2)
Therefore we can obtain:
I1 2k (2A 12A++DD
A Ind
Pau(i.j) P(a ~ ky ~ ..........
At!
(103)
22k (minli, k K22- 1, 2)26
Proposition Q.5. For any 8 > O, with probability at least ô, we have
VNLiT 1)+ 1 NN
2(N - 2)
(m (2N + 1)!!
Nm
b1 In (2n0-11 (no-11]
}b]. (104)
Siy S 2k
In
(2N+1)!!
LNV(1) 2NN!
2
where #nodes,k represents the order of the k-hop CNs.
Proof.
From the process of obtaining Equation (102) and Theorem Q.2, we can obtain:
m22 kd ++/+1!!! ke+t kill
Ind
(105)
+ addyimi Meai))
2(maro( kz) 2)
Let 1k:41 kig I, we can get:
([maa(kk41,aa k;) - 2) 1) + Fe
dk.k141 S In(
(106)
(2r+ 2
Velna-
So next we only need to compute ke. > let k- = mun(ks 1s+1).
We have
m k- + 1)!!
N
m
In 6-1-1
deg(k-) NV(rk NV(1) <
+
(107)
2 2 N 1
2
S0:
m k | 1)!!
k
mm2
In
8-1
mmin 1 1
}}
(108)
NV(1) N IIN k_
2
summary,
1
2( (mmar(kkit1 k)) 2)
m22
k
+ 1)!!
N
k
\m2
In
d.j & 2k dk < 2k In(
(2t+ vtln 1)+
1] []
NV(1)
2
N
k_11
2
(109)
Proposition Q.6. After introducing normalizedCN, for any > 0. with probability at least 6, we have
Si S 2k In(
n n N
W
N - n 1n-n-1om nl -
0 2
LV (m
(2N 1)!!
Nm
In 8
ind-1)
1/
2NN!
2
(110)
where (.) is Lambert W function, Ç is the maximum degree of all k-hop CNs of (i.j), the total number of paths of length I between and j is denoted as (i(i.))
122k
C
(111)
( 122k D2k-2 v N In
D is the maximum degree on the graph.
39

---

Proof.
Using an idea very similar to the process of proving Theorem 5.4, we first obtain:
N-R-1
IT (2A++1)1!
1n11--1 24+AH!
IT (2A +1)M 2 (max (i, 11, (1:k-1:5) - 2)
A- + A- In
E [[EE (0) 2 (
2
2
2 (min(i, k1, .. h2k 125k-1,5) 2)
(112)
Let D the maximum degree in the entire graph, then we have:
D2k 11 (2AT-11) 1n-6--1
EoNNs (1)
(mmmm (1,1
A-!
122- -
N N-n-1 22 V N (2()
I (20 1 +1 l
17
(5)
24
2 (mminii Aas 11.) 2
2 (ina Ao 2
(113)
let P(A*) ()
+21++111
20 At1
+V
A+ bt
P(A-)
2(min( k1 ... k2)-11))22 and 11* P( P(
[24 +i!!! --
A-1
(1,k, 22)
X, we have:
D
N)N-n-1 2 V In(20)
(5) (ix)
7 Eox1 (1)
(114)
4
We then get:
2
Cone (1)) T[xx (1)) 2
(115)
V
D2k-
4
So we can transform the problem into finding a closed-form upper bound for x based on the inequality =--2( 2 C. We can solve this problem using the following method.
Clearly, we have:
x n- 211 - x) x) N-n-1 x= n-2 (N-n-1)a
(116)
Let l: 12-2, N 1(> 0). and replace the original equation with the amplified upper bound:
x e mar C.
(117)
The left-hand side of it is always greater than equal to the left-hand side of the original equation, so its solution up must be less than or equal to the true solution of the original equation.
e me =c = khn mx
Inc
Inc
(118)
De z cl/k
m
m 1/k
(119)
h
Let y = x. then yeŋ
m 1//k B
Using the definition the Lambert function (())) = 2. we obtain Tap
W (1/) (A: = n 2, m = - n 1).
40

---

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]
We have included discussion for our contributions in the Abstract and Intro- duction.
Justification:
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 the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: Section 4.1, Section 4.2, and Section 6 all include discussions of the work's limitations from different perspectives.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
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?
41

---

Answer:
[Yes]
Justification:
Please see theoretical appendix for details.
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 in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Please refer to the detailed elaboration of the methodology in the main text, the algorithm information in the appendix and our submitted source code.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is 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 describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
42

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We include the source code along with our submission.
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, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //niss cttpssccccpbbcccccceeeecc httpe/guuddeeeeeeuubiiieeeeeee /Cooeeeooiissseeeeee cessionPoocyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
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 understand the results?
Question:
Answer: [Yes]
Justification: We have shown detailed experimental settings/details in the Experiment and Appendix section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We have provided standard deviation as part our experiment 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, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
43

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please see the appendix.
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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 NeurIPS Code of Ethics https: / /nuuriss..p.. cc cc/public// wtth://tthhhhsieeeeeeeeeeeeeeeee
didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification:
We confirm this perform conform with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have 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 special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper does not perform socictal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
44

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
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 paper does not include any data or models that have a high risk for misuse.
Guidelines:
The answer NA means that the paper poses 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 usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We have credited correctly for the existing data and models referred.
Guidelines:
existing assets. The authors should cite the original paper that produced the code package or dataset.
The answer NA means that the paper does
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.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, paperswi thcode. com com/dataseta 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 it has changed) should be provided.
45

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new datasets introduced.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is 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. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subjects are involved.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 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 subjects are involved.
Guidelines:
The answer NA means that the paper does not 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 expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
46

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
The LLM was used solely for grammar checking purposes.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https 200t://eee//oooeeeeeeee///////// for what should or should not be described.
47


Reviews:
[{"review_id": "G4RwuBrIVG", "reviewer": "Reviewer_qjCp", "summary": "This paper proposes a novel link prediction framework OCN, which leverages orthogonalized multi-hop common neighbor features. The authors identify and address the issues of redundancy and over-smoothing in higher-order common neighbors. By orthogonalizing the coefficients of different-order CNs, the model ensures a more expressive representation. Additionally, a path-based normalization technique is introduced to reduce the dominance of frequently appearing nodes. Experiments demonstrate competitive performance across multiple benchmark datasets.", "questions": "1. Both NCNC and SEAL already capture local structural information (NCNC through common neighbors and SEAL via enclosing subgraphs). Since OCN also uses K=2, could the authors clarify what specific relational patterns or advantages OCN captures that contribute to its superior performance over these baselines?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The idea of decorrelating multi-hop common neighbors via orthogonalization is reasonable and helps mitigate redundancy.\n\n2. The proposed normalization strategy, inspired by batch normalization, is effective and empirically validated to reduce over-smoothing.\n\n3. Empirical results across multiple benchmark datasets show competitive performance compared to recent baselines.\n\n\nWeaknesses:\n\n1. While the paper introduces mechanisms for handling high-order common neighbors, the final model only uses OCN¹ and OCN², limiting the demonstrated impact of the orthogonalization and normalization designs. This weakens the motivation for high-order modeling.\n\n2. The explanation of key concepts such as “coefficient,” “orthogonalization,” and “path-based normalization” is not always directly clear. For instance, the coefficient definitions rely on abstract descriptions without concrete examples or diagrams. Based on the current description, one may infer that each node pair maintains a k × n coefficient matrix, but this is not explicitly stated.\n\n3. The paper lacks clear explanation of how the values in Figure 1 and Figure 2 are obtained, which may hinder reader understanding of the motivation and insights.", "was_revised": false, "final_justification": "", "rebuttal": "### W1.\nThank you very much for your question! The previously suboptimal performance of OCN-3 (shown in Table 2) stemmed from using the same hyperparameters as those for OCN, which failed to fully exploit the potential of higher-order CN. After further tuning the model using 3-hop CN with Optuna, we obtained some new good results. As shown in the below table, the tuned OCN-3 model indeed outperforms the original model on certain datasets. However, introducing higher-order CNs inevitably leads to a sharply increased computational burden and GPU memory consumption. Overall, we believe higher-order CNs can yield benefits, though this is also dependent on the specific model architecture and dataset characteristics. Therefore, we consider this work highly enlightening for subsequent research on how to efficiently utilize higher-order CNs.\n\n\n| Method      | Cora (HR@100) | Citeseer (HR@100) | Pubmed (HR@100) | Collab (HR@50) | PPA (HR@100) | Citation2 (MRR) | DDI (HR@20) |\n|-------------|---------------|-------------------|-----------------|----------------|--------------|-----------------|-------------|\n| OCN          | 89.82±0.91    | 93.62±1.30        | 83.96±0.51      | 72.43±3.75     | 69.79±0.85   | 88.57±0.06      | 97.42±0.34  |\n| OCN-3          | 90.96±0.64    | 92.33±0.85        | 87.12±1.40      | 73.04±2.13     | OOM   | 87.34±0.38      | 90.06±1.29  |\n\n### W2.\nThank you very much for your question and suggestions. The complete algorithm flow for orthogonalization and path-based normalization is presented in Algorithm 2 on page 34. The entire method relies on the definition of $CN^k$ (in line 156 and Appendix B). Specifically: \n$CN^k(u,v) = \\sum_{2(k-1) < k_1 + k_2 \\leq 2k, \\atop k_1 \\leq k, \\ k_2 \\leq k} \\left(A^{k_1}\\right)_u \\odot \\left(A^{k_2}\\right)_v$\n\nThe defined k-order CN is a scalar value, but it is defined for a specific node pair $(u, v)$. It represents: if a node has paths to $u$ of length $k₁$ and to $v$ of length $k₂$ (this refers to any path, not necessarily the shortest path), and the lengths $k₁$ and $k₂$ satisfy the given constraints, then this node is considered a k-order CN for the pair (u, v). The term $\\left(A^{k_1}\\right)_{u}$ (and similarly for $k_2$) actually counts the number of paths of length $k₁$ (or $k₂$) from this k-order CN node to $u$ (or $v$). This definition is also the commonly accepted definition of CN in the link prediction field, although some models define CN based on the Shortest Path Distance , whereas ours on the length of paths.\nWhat we actually orthogonalize is a matrix of shape $(h, n)$, where $h$ is the number of edges in the current batch, and n is the total number of nodes. In plain language, the definition in Appendix B means: For each order $k$, we have three matrices of shape $(h, n)$. e.g. for 4-hop CN, the distance pairs can be (4,4); (3,4); or (4,3). For 7-hop CN, (7,7); (6,7); or (7,6). For such an $(h, n)$ matrix, suppose it corresponds to the distance pair (3,4). Then, the value $z$ at row $x$ and column $y$ indicates that for the edge $(u, v)$ corresponding to row $x$, the total number of paths from the node corresponding to column $y$ to $u$ that are exactly of length 3, and to $v$ that are exactly of length 4, is $z$. If the total number of paths is 0, it means the node corresponding to column $y$ cannot reach $u$ and $v$ via any paths of lengths exactly (3,4) respectively. Consequently, this node is not a 4-hop CN under the (3,4) criterion. However, it might be a 4-hop CN under the (4,4) or (4,3) criteria. If it satisfies none of these criteria, then it is not a 4-hop CN for the pair $(u, v)$.\n\nOrthogonalization:\nThe orthogonalization process is the standard Gram-Schmidt, but applied to matrices instead of vectors. The matrices we orthogonalize all have the shape $(m, n)$, where $m$ represents the total number of edges and $n$ represents the total number of nodes. Orthogonality between matrices is defined by the Frobenius norm:\n$$\n\\|A^T B\\|_F = 0 \\quad \\text{is equivalent to} \\text{tr}(A^T B) = 0 \n$$\nSection 4.1 primarily addresses one key challenge: how to obtain the true inner product value on a large real-world graph. Calculating the inner product for matrices used in orthogonalization inherently requires matrix multiplication. However, in real graphs, the number of edges $m$ and nodes $n$ is extremely large. Performing the full $(m, n)$ matrix multiplication across the entire graph is computationally expensive. Furthermore, training is performed batch-wise, so we only have access to a submatrix $(m', n)$ constructed from the edges within the current batch, where $m'$ is the number of edges in this batch.\nOur goal is therefore to approximate the inner product computed over all edges (i.e., the true inner product achieving orthogonality on the full graph) using only the partial information from the edges visible within the current batch. Inspired by Batch Normalization, we maintain a running inner product across batches. This running inner product accumulates the contribution of historical inner product information. It is then combined with the inner product calculated from the current limited information via a weighted sum. As the number of training steps $t$ tends towards infinity, this running inner product converges to the full-graph inner product. In our experiments, we observed that the inner products indeed converged to a stable value.\n\n4.2 aims to find a method that achieves mutually orthogonal results—even if approximately—while bypassing the Gram-Schmidt. Because Gram-Schmidt requires each subsequent matrix to operate on every preceding orthogonal basis, we desire a way to directly compute the orthogonalized result from each $(m, n)$ matrix in a single step. Through proof, we discovered that simply applying $OCN^k = CN^k \\cdot \\text{diag}(T_k)$—that is, right-multiplying the $(m, n)$ matrix by a diagonal matrix (with an arbitrarily chosen polynomial basis placed on its diagonal)—sufficiently approximates the result originally requiring Gram-Schmidt. This reduces the time complexity from $O(k^2)$ to $O(k)$ (see Table 7).\n\nPath-based Normalization:\nThe exact steps and equations used for normalization in Section 5 are detailed in Definition 5.1. We provide accessible descriptions of the underlying concepts and their practical implications in lines 212-221. The precise, step-by-step computational workflow for path-based normalization is presented within the first for loop of Algorithm 2 on page 34.\nThank you very much once again for your questions and suggestions!\n\n### W3.\nThank you very much for question. The data in Fig.1 come from Cora. The correlation coefficients used are Pearson correlation coefficients. The data in Fig.2 are also sourced from Cora. We also computed the relevant metrics on other datasets and found that they exhibit similar patterns. Therefore, we only showed Cora.\nThe purpose of Fig.2 is to illustrate the difference between using path-based normalization and not using it. The coefficient of variation (CV) decreases at higher orders, indicating that the high-order CNs of different nodes begin to overlap more frequently and that the similarity of higher-order neighborhood structures continually increases. Our path-based normalization method can significantly slow this decreasing trend of the CV.\n\n### Q1.\nThank you for your question! \nAs for empirical advantages of OCN, they primarily come from the following points. Firstly, OCN captures the feature information of the high-order CNs, rather than only their counts. Secondly, the information coming from CNs have undergone decorrelation, thus increasing their utilization by models. Thirdly, the weight (significance) assigned to each high-order CN is dynamically adjusted (If $k$-hop CNs are less frequently shared among other node pairs, then these $k$-hop CNs carry greater discriminative significance for the relationship between the two nodes.).\nPrevious work generally treated high-order CNs only as a source of information of count, failing to fully exploit the rich information inherent in the CNs. Furthermore, information across different high-order CNs often contains substantial redundancy and coupling. Our model preserves the most effective information while performing decorrelation. Simultaneously, our model does not assign equal weight to every CN; we recognize that the importance of each CN varies. This approach also helps mitigate the mentioned over-smoothing phenomenon. The redundancy and over-smoothing phenomena are two intriguing issues we identified; addressing them is a key reason our model outperforms other baselines. The above points are all verified by ablation study in Table 2 and main results in Table 1.\nWe hope this answer addresses your query. Further discussion is welcome!"}, {"review_id": "c1WrcmdD7S", "reviewer": "Reviewer_8Aox", "summary": "The paper introduces Orthogonal Common Neighbor (OCN), a novel method for link prediction that addresses the limitations of traditional Common Neighbors (CNs) and their higher-order variants. Existing approaches suffer from redundancy across different CN orders and over-smoothing, which hinder their effectiveness. OCN tackles these issues through two key techniques: orthogonalization, to remove redundancy between different-order CNs, and normalization, to alleviate over-smoothing effects. The proposed method achieves an average improvement of 7.7% over strong baselines on standard link prediction benchmarks. The authors provide both theoretical analysis and ablation studies to support the effectiveness of their approach.", "questions": "Q1. Have you considered using the proposed normalized Common Neighbors (CN) as an additional baseline, alongside standard heuristics such as CN, Adamic-Adar (AA), and Resource Allocation (RA)? It would be helpful to understand whether you experimented with this and how it compares in performance.\n\nQ2. The formulation in Equation (4) is not entirely clear to me. Specifically, could you clarify why the function MPNN(A, X) is used to compute the score for a node pair (i, j)? Some additional explanation would help to better understand the underlying intuition.\n\nQ3. Could you elaborate on the rationale for choosing different evaluation metrics across datasets (Hits@100 for some, Hits@20 for others, and MRR elsewhere)? This choice appears inconsistent and also deviates from recent works such as [n1]. A clarification on this point would strengthen the experimental section.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\nS1. The problem addressed in this paper is well-motivated and clearly presented in the introduction, highlighting its relevance to the link prediction literature.\n\nS2. The proposed method demonstrates strong empirical performance, consistently outperforming the considered competing methods.\n\nS3. The paper includes a theoretical analysis that offers valuable insights into the behavior of the proposed approach.\n\n**Weaknesses:**\n\nW1. Some sections of the paper, particularly those describing the proposed method, would benefit from greater clarity. In particular, the discussion of the orthogonal scalability issues and the proposed solution in Section 4.1 is difficult to follow, and Section 4.2 is also not clearly explained. Improving the exposition of these key methodological components would enhance the overall readability and understanding of the paper.\n\nW2. The ablation study suggests that higher-order common neighbors may introduce redundant information, potentially affecting the model’s stability and generalization ability (lines 286–288). This is concerning, as the use of higher-order neighbors is one of the central contributions of the paper. Evidence that performance may degrade beyond a certain number of hops raises questions about the robustness and general applicability of the proposed approach.\n\nW3. The theoretical analysis is conducted on random graph models, which may not fully capture the structural properties of real-world networks. It would strengthen the paper to extend the theoretical justification to more realistic graph models such as Watts-Strogatz, Barabási-Albert, or Stochastic Block Models. If such an extension is not feasible, a discussion of this limitation should be included.\n\nW4. The set of evaluation metrics is somewhat limited. For a more comprehensive assessment of predictive performance, additional metrics such as MRR (Mean Reciprocal Rank) should be reported on datasets like Cora, Citeseer, and PubMed, following the practice of recent works such as [n1].\n\nW5. The experimental evaluation lacks some relevant and recent baselines, including [n1] and [n2], which also leverage heuristics and have demonstrated state-of-the-art performance in link prediction. Including these baselines would provide a more complete and convincing empirical comparison.\n\n[n1] Mixture of Link Predictors on Graphs. NeurIPS 2024.\n\n[n2] LPFormer: An Adaptive Graph Transformer for Link Prediction. KDD 2024.\n\n**Overall recommendation**\n\nThe paper addresses an important problem in link prediction and proposes an interesting approach that combines higher-order common neighbors with orthogonalization and normalization techniques. The work shows good empirical results and includes some theoretical analysis, contributing to the significance of the topic.\n\nHowever, the clarity of key methodological sections (W1) is lacking, making it difficult to fully grasp the proposed solution. The quality of the theoretical justification is limited by the use of overly simplistic graph models (W3), and the experimental evaluation would benefit from stronger baselines and more comprehensive metrics (W4, W5).", "was_revised": true, "final_justification": "The authors addressed most of my initial concerns, including clarifications, additional experimental comparisons with further methods, and an extension of their theoretical analysis to the Barabási–Albert graph model (noting that, due to space constraints, only results are provided, not full proofs). These additions improve the completeness of the work, and I have accordingly raised my score to Borderline Accept.\n\nHowever, my overall assessment is not fully positive. A major issue that remains unresolved is the clarity and readability of the paper—an aspect also noted by other reviewers. This significantly affects the accessibility and impact of the contribution. I hope the authors will take this feedback seriously and work to improve the exposition if the paper is accepted.", "rebuttal": "### W1. \nThank you! Section 4.1 addresses how to obtain the true inner product on a large real-world graph. In real graphs the number of edges $m$ and nodes $n$ is extremely large. Performing the full (m, n) matrix multiplication across the entire graph is computationally expensive. And training is performed batch-wise, so we only have access to a submatrix $(m', n)$, where $m'$ is #edges in this batch.\nOur goal is to approximate the inner product computed over all edges (i.e., the true inner product achieving orthogonality on the full graph) using only the edges visible within the current batch. We maintain a running inner product across batches, which accumulates the contribution of historical inner product information and combined with the inner product calculated from the current batch. As $t$ approaches infinity, it converges to the full-graph inner product. In experiments, we observed the inner products indeed converged to a stable value.\n\n4.2 aims to find a method that achieves mutually orthogonal results bypassing the Gram-Schmidt which has a high complexity. We desire a way to directly compute the orthogonalized result from each $(m, n)$ matrix in a single step. We discovered that applying $OCN^k = CN^k \\cdot \\text{diag}(T_k)$—that is, right-multiplying the $(m, n)$ matrix by a diagonal matrix (with an arbitrarily chosen polynomial basis placed on its diagonal)—sufficiently approximates the result originally requiring Gram-Schmidt. It reduces the time complexity from $O(k^2)$ to $O(k)$ (see Table 7).\n\nDue to space limit, we moved many details into Appendix B, C, I and J. We will make these sections more clear in the revised version.\n\n### W2. \nThank you! The previously suboptimal performance of OCN-3 (Table 2) stemmed from using the same hyperparameters as those for OCN, which failed to fully exploit the potential of higher-order CN. After further tuning the model using 3-hop CN with Optuna, we obtained new good results. As shown in the below table, the tuned OCN-3 model indeed outperforms the original model on certain datasets. But introducing higher-order CNs inevitably leads to a sharply increased computational burden and GPU memory consumption. We believe higher-order CNs can yield benefits, though this is also dependent on the specific model architecture and dataset characteristics. So we consider this work highly enlightening for subsequent research on how to efficiently utilize higher-order CNs.\n\n|Method|Cora(HR@100)|Citeseer(HR@100)|Pubmed(HR@100)|Collab(HR@50)|PPA(HR@100)|Citation2(MRR)|DDI(HR@20)|\n|-|-|-|-|-|-|-|-|\n|OCN|89.82±0.91|93.62±1.30|83.96±0.51|72.43±3.75|69.79±0.85|88.57±0.06|97.42±0.34|\n|OCN-3|90.96±0.64|92.33±0.85|87.12±1.40|73.04±2.13|OOM|87.34±0.38|90.06±1.29|\n\n### W3. \nThank you! We have extended the theoretical analysis to the Barabási-Albert model (given the numerous variants and generalized models, we selected one class demonstrating broad applicability), and we are privileged to complete the proof during rebuttal. Due to space constraints, we present only the conclusions here. Subsequently, we will provide the full detailed theoretical analysis and proofs in the camera ready version.\n\n**Construction.** Form $G_n$ from $G_{n-1}$ by adding vertex $n$, sampling $m$ (with replacement) vertices $w_1,\\dots,w_m$ from $G_{n-1}$, and connecting $n$ to each $w_i$.\n\nConditioned on the past, the $w_i$ are i.i.d.:\nfor $k<n$\n$$\n\\Pr(w_i=k)=\\frac{\\deg_{n-1}(k)}{Z},\\qquad\nZ=\\sum_{k=1}^{n-1}\\deg_{n-1}(k).\n$$\n\n**Definition 1**\nWe define the score based on the linking probability of $(i,j)$ $s_{ij}$:\n$$ Pr(i\\sim j|s_{ij},G_{max(i,j)-1})=\\frac{1}{1+e^{\\alpha(s_{ij}-r_{min(i,j)})}},$$\n\nwhere $r$ satisfies $\\deg(k)=NV(r_k)=NV(1)r^{D}_k$，$N = \\text{number of nodes}.$\n\n**Proposition 1**\nWhen connecting an edge at vertex $b$, the expectation of degree of vertex $a$ (assuming $b>a$) is:\n$$E(\\deg_b(a))=m\\frac{(2|a-b|+1)!!}{2^{|a-b|} |a-b|!}.$$\nSimultaneously,\n$$ E[Pr(a\\sim b|G_{b-1})]=\\frac{1}{4^{|a-b|}}\\tbinom{2|a-b|}{|a-b|}\\sim \\frac{1}{\\sqrt{\\pi |a-b|}} \\sim O(|a-b|^{-\\frac{1}{2}}).$$\n\n\n**Proposition 2**\nFor any δ > 0, with probability at least δ, we have\n\n$$P_{2k}(i,j)\\leq \\frac{\\prod^{2k}\\frac{(2\\Delta^++1)!!}{2^{\\Delta^+} \\Delta^+!}+\\sqrt{\\frac{\\Delta^+ \\ln \\delta^{-1}}{2}}}{2^{2k}(min(i,k_1,\\cdots,k_{2k-1},j)-2)^{2k}},$$\n\nwhere $\\Delta=max(|k_i-k_{i+1}|).$\n\n**Proposition 3**\nFor any δ > 0, with probability at least δ, we have\n$$s_{ij}\\leq 2k\\Bigl[\\frac{1}{\\alpha}\\ln(\\frac{2(N-2)}\n     { \\frac{(2N+1)!!}{2^{N}N!}+\n                \\frac{\\sqrt{N\\ln\\delta^{-1}}}{4}}-1)\n                +\\Bigl[\\frac{1}{NV(1)}(m\\frac{(2N+1)!!}{2^N N!}+\\sqrt{\\frac{Nm^2}{2}\\ln{\\delta^{-1}}})\\Bigr]^{-\\frac{1}{D}}\\Bigr],$$\n                \nwhere $N=\\text{number of nodes}$, $k$ represents the order of the k-hop CNs.\n                \n**Proposition 4**  \nAfter introducing normalizedCN, for any δ > 0, with probability at least δ, we have\n\n$$s_{ij}\\leq 2k\\Bigl[\\frac{1}{\\alpha}\\ln(\\Bigl[\n  -\\frac{n-2}{N-n-1}\n  W\\!\\Bigl(\n       -\\frac{N-n-1}{n-2}C^{\\tfrac{1}{n-2}}\n    \\Bigr)\n\\Bigr]^{-\\tfrac{1}{k}}-1)\n                +\\Bigl[\\frac{1}{NV(1)}(m\\frac{(2N+1)!!}{2^N N!}+\\sqrt{\\frac{Nm^2}{2}\\ln{\\delta^{-1}}})\\Bigr]^{-\\frac{1}{D}}\\Bigr],$$\nwhere $W(\\cdot)$ is **Lambert W function**， ζ is the maximum degree of all k-hop CNs of $(i, j)$,the total number of paths of length ℓ between i and j is denoted as $η_l(i, j).$\n$$\nC =\n\\frac{1}{\\tbinom{\\xi}{2}}\n\\frac{D^{2k-1}}\n     {\\eta_{2k} - D^{2k-2}\n        \\dfrac{\\sqrt{N\\ln\\delta^{-1}}}{4}},\n$$ and $D$ is the maximum degree on the graph.\n\nPlotting the curves in MATLAB shows that without introducing normalizedCN, the upper bound of $s_{ij}$ is a monotonically increasing affine function with respect to $k$. After introducing normalizedCN, this upper bound gradually decreases as $k$ increases. This extends our theoretical analysis to more realistic scenarios. \n\n### W4. \nThank you! We evaluated our model using the [n1] evaluation metric, and the results are as follows. It is noteworthy that [n1] essentially aggregates the outputs of many previous outstanding models. Nevertheless, our single model is able to compare competitively to [n1]'s ensemble model.\n\n|Method|Cora(HR@1)|Cora(HR@3)|Cora(HR@10)|Cora(HR@100)|  \n|-|-|-|-|-|\n|Link-MoE|32.12±4.72|38.81±1.09|75.84±0.28|96.26±0.09|   \n|OCN|35.10±5.22|49.44±4.86|65.91±2.08|89.82±0.91|\n|OCNP|39.21±5.71|50.75±6.07|65.19±1.32|90.06±1.01|\n\n\n|Method|Citeseer(HR@1)|Citeseer(HR@3)|Citeseer(HR@10)|Citeseer(HR@100)|  \n|-|-|-|-|-|\n|Link-MoE|58.50±0.46|76.72±0.24|82.77±0.19|96.44±0.14|   \n|OCN|57.70±0.22|78.65±0.98|86.11±0.79|93.62±1.30|\n|OCNP|60.79±0.70|74.53±0.42|87.40±1.14|93.41±1.02|\n\n\n|Method|Pubmed(HR@1)|Pubmed(HR@3)|Pubmed(HR@10)|Pubmed(HR@100)|  \n|-|-|-|-|-|\n|Link-MoE|45.13±0.38|52.57±2.27|61.11±1.03|90.38±0.24|   \n|OCN|62.52±2.19|69.23±0.60|72.74±1.69|83.96±0.51|\n|OCNP|48.25±1.26|68.02±0.99|72.08±2.32|82.32±1.21|\n\n\n|Method|Collab(HR@20)|Collab(HR@100)|PPA(HR@20)|PPA(HR@50)| \n|-|-|-|-|-|\n|Link-MoE|63.83±0.65|75.16±1.64|48.36±1.37|59.87±0.80|98.59±0.02  |99.28±0.01|99.63±0.02|\n|OCN|67.64±0.45|74.17±1.20|46.62±0.49|61.29±1.91|\n|OCNP|65.39±0.23|70.43±0.92|55.99±1.58|62.12±2.10|\n\n### W5. \nThanks! The results are as follows. As we can see, our models outperform [n2] on 5/6 datasets, and outperforms [n1] on 3/6 datasets.\n\n\n|Method|Cora(MRR)|Citeseer(MRR)|Pubmed(MRR)|Collab(HR@50)|PPA(HR@100)|Citation2(MRR)| \n|-|-|-|-|-|-|-|\n|LPFormer [n2]|39.42±5.78|65.42±4.65|40.17±1.92|68.14±0.51|63.32±0.63|89.81±0.13|\n|Link-MoE [n1]|44.03±2.28|67.49±0.30|53.10±0.24|71.32±0.99|69.39±0.61|91.25±0.02|\n|OCN|51.75±3.24|64.69±1.31|47.09±0.76|72.43±3.75|69.79±0.85|88.57±0.16|\n|OCNP|45.35±5.66|65.55±0.49|44.12±0.53|67.74±0.16|74.87±0.94|87.06±0.27| \n\n### Q1.\nThanks for your suggestion! The new results are as follows (hereinafter abbreviated as NC):\n\n|Method|Cora(HR@100)|Citeseer(HR@100)|Pubmed(HR@100)|Collab(HR@50) |PPA(HR@100)|Citation2(MRR)|DDI(HR@20)|\n|-|-|-|-|-|-|-|-|\n|CN|33.92±0.46|29.79±0.90|23.13±0.15|56.44|27.65|51.47|17.73|\n|AA|39.85±1.34|35.19±1.33|27.38±0.11|64.35|32.45|51.89|18.61|\n|RA|41.07±0.48|33.56±0.17|27.03±0.35|64.00|49.33|51.98|27.60|\n|NC|47.11|39.81|34.74|65.88|43.26|53.32|30.49|\n\nNC significantly outperforms the standard heuristics, demonstrating the importance of decorrelation and normalziation of high-order common neighbors.\n\nThe superiority of NC over RA can also be demonstrated by the following example: Two hexagons are connected via a single node (Node 1). In the left hexagon, starting clockwise from the node adjacent to 1, the nodes are numbered consecutively as 2, 4, 6, 8, 10, 12. In the right hexagon, starting counterclockwise from the node adjacent to 1, the nodes are numbered consecutively as 3, 5, 7, 9, 11, 13. The computed values are: NC(13,5)=41/6,NC(13,1)=5/3,NC(13,9)=4/3.RA(13,5)=1/3,RA(13,1)=1/3,RA(13,9)=1/2. It is evident that the accuracy with which NC reflects the structural features is far better than RA.\n\n### Q2. \nThanks for raising this issue! The original expression was indeed inaccurate. The correct formulation should be: $\\sum_{k=1}^K \\alpha_k \\{OCN^k \\cdot \\text{MPNN}(A, X)\\}_{ij}.$\n\nHere, the preceding OCN is the $(m, n)$ matrix as previously defined, while $\\text{MPNN}(A, X)$ is an $(n, \\text{dim})$ matrix. The notation ${\\cdot}_{ij}$ indicates the selection of the specific node pair $(i, j)$. We sincerely apologize for the oversight and greatly appreciate the identification of this error.\n\n### Q3. \nThe metrics adopted in our paper are widely accepted within the field. They follow the authoritative benchmark OGB (Open Graph Benchmark), which considers the different characteristics and purposes of the datasets and suggest different metrics. Our evaluation framework is also the officially recommended standard by OGB. These metrics have been utilized in nearly all influential works within the domain, such as SEAL, Neo-GNN, Buddy, NCN and [n2]. In contrast, a limited number of related works, such as [n1], employ their own evaluation metrics."}, {"review_id": "PhqP9wUjO8", "reviewer": "Reviewer_PbQ7", "summary": "A number of approaches have been proposed for link prediction in graphs. Recent ones includes Graph Neural Network based techniques. These techniques are often adopted to encode structural information by considering common neighbors between node pairs. One hop neighbors might not provide complete structural similarity indices in several graphs. Higher order neighbors reachable with $l$ hops is expected to provide more detailed information. Empirically, it has been observed that including higher order neighbors do not translate always to better performance in link prediction.\n\nThe present paper identifies to challenges in using higher order neighbors for link prediction. The first challenge is that of redundancy, meaning, as the order of neighbors considered grows, the nodes belonging to common neighbor set do not additionally include sufficient number of unique elements. The second challenge is the homogeneity of latent representations learned in a GNN across different nodes in the network. Both issues are definitely harmful for link prediction.\n\nAuthors propose two key ideas to alleviate these difficulties. Empirical results are presented to demonstrate that the correlation among representation of nodes in higher order neighborhood is very high. A orthogonalization is performed to remove these linear correlations. Thus a second level latent (linear?) representation is derived for the GNN based representation vectors. To allow scalable computation of the orthogonal components  the Gram-Schimdt batch orthogonalization is performed. \n\nThe second observation is that the nodes with high between-ness that are elements of multiple $l$-hop paths are over emphasized in the learned latent representation. And thus contribute adversely towards homogenization of the representations. This is addressed by simply normalizing the representation vectors with the count of the paths passing through these nodes.\n\nBoth the above approaches are nice and simple heuristics that is likely to improve performance of link prediction in a wide variety of network structures.", "questions": "1. Please define clearly the proposed method and the related orthogonalization/normalization techniques. Use clear mathematical equations of flow charts.\n\n2. Highlight the novelty in terms of existing higher order neighbor based techniques.\n\n4. Rewrite the caption of the Figures in the Results section for better interpretation.", "limitations": "The presentation of the paper and its clarity should be improved. The originality and contributions in more broader terms should be highlighted.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper proposes two effective approaches which reduces redundancy and homogeneity in GNN based link prediction using higher order common neighbor heuristics. Since using higher order common neighbors along with GNN appears to be a state of art in link prediction, the proposed method definitely is useful and effective. \n\nThe paper has extensive experimental results to demonstrate the effectiveness of the proposed techniques. Comparisons on benchmark data sets with various state of art methods are presented. The paper however lacks in novelty as all the methods used are well known in similar literature. The intuitions exploited in the work is also common knowledge in this research community and similar approaches were explored earlier.\n\nThe presentation of the paper is not very good. Several terms and concepts are undefined. For example, in Section 4 it is mention that \"by analyzing the correlations coefficients among CNs of various orders...\", although no definition of correlation coefficient or how it is computed is mentioned before. Similarly in Section 5 the exact steps/equations used in normalization is not clear. \n\nThere are a number of abbreviations that are undefined at first use and few inconsistent notations. legends of some of the plots like Figure 3,4, 5 are not easily understood.\n\nThe superiority of the proposed method cannot be established just on the basis o prediction accuracy. A combined analysis in terms of scalability and performance should be presented.", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for giving a very nice summary of the main merits and motivation of our paper, acknowledging that our paper proposes \"**nice and simple heuristics** that is likely to improve performance of link prediction\", \"**two effective approaches** which reduces redundancy and homogeneity\", and recognizing that \"the proposed method definitely is **useful and effective**\", \"the paper has **extensive experimental results** to demonstrate the effectiveness\". Below, we address your remaining concerns one by one.\n### W1. methods used are well known\nWhile we leverages higher-order CNs, our core contribution and innovation are beyond merely introducing higher-order CNs to link prediction using existing techniques. The most important precondition is, **previous works exhibited low utilization efficiency and suboptimal effectiveness** when incorporating higher-order CNs, sometimes even hurting the performance. Our focus is thus **Effectively Utilizing Higher-Order CNs**. \n\nNeo-GNN computes features for high-order neighborhood overlap $N^{l_1}(i), N^{l_2}(j)$ as $\\sum_{u \\in N_1^{l_1}(i) \\cap N_1^{l_2}(j)} A_{iu}^{l_1} A_{ju}^{l_2}f(d(u))$. But it simply concatenates structural features directly to the final representations, detaching them from MPNN, leading to reduced expressivity. And it only contains degree information and fundamentally fails to consider the features and influence of the high-order CNs themselves.\n\nBUDDY further considers overlap features and difference features: $\\sum_{u\\in N_{l_1}^{1}(i)\\cap N_{l_2}^{1}(j)}1$, $\\sum_{u\\in N_{l}^{1}(i)-\\cup_{l'=1}^{k}N_{l'}^{1}(j)}1$. But it only uses count information and simply concatenates structural features directly to the final representations.\n\nNCN is the 1st work that goes beyond merely using the count information of CN. Nevertheless, it does not utilize higher-order CNs nor consider the relationships between them. Prior to our work, the approach to incorporating higher-order CNs within the field remained solely at the level of computing count-based features and concatenating them. Beyond them, there have been no other successful works utilizing higher-order CNs. \n\nNone have genuinely analyzed the higher-order CNs or explored how to truly unlock the potential of higher-order CNs. We are **the 1st to conduct an in-depth analysis of the reasons for failure** and, for the first time, successfully makes high-order CNs useful.\n\n### W2. terms and concepts are undefined\nThank you for your question. The correlation coefficients in Fig.1 used are just standard Pearson and the graph is Cora.\nThe exact equations employed for normalization in Section 5 are detailed in Definition 5.1. Additionally, we provide intuitive explanations of their practical implications in lines 212-221. In our **response to Q1**, we provide a further, more formal and comprehensive explanation. \n\nAll terms and concepts beyond common terminology are defined within the main text or appendices. We sincerely appreciate and hope your feedback.\n\n### W3. abbreviations, notations inconsistent, and plots (Fig.3–5) \nThanks! After a thorough verification, all abbreviations in the text were defined upon their first occurrence. Could you kindly provide more details regarding your concerns? \n\nFig.3:\nWithout path-based normalization, the upper bound of the probability for edge formation between (u, v) corresponds to the blue curve in Fig. 3. This is clearly suboptimal because increasing higher-order CNs information fails to tighten the probability bound. After introducing our normalization technique, the probability upper bound becomes the brown curve in Fig. 3. This provides a tighter and more reasonable probability estimation, consequently leading to significant performance improvement.\n\n**Fig. 4** is an example constructed in the proof of Theorem 6.1 (in Appendix E) to demonstrate that our model possesses superior expressive ability compared to other models. When algorithm A can distinguish all link pairs distinguishable by algorithm B, and there exists at least one link pair that A can distinguish but B cannot, we consider algorithm A to have stronger expressive ability than algorithm B. Fig. 4 represents one such counterexample. Nodes $v_2$ and $v_3$ are symmetric from $v_1$’s perspective, so GAE cannot distinguish between $(v_1, v_2)$ and $(v_1, v_3)$. If node features are ignored, $(v_1, v_2)$ and $(v_1, v_3)$ remain symmetric; thus CN, RA, AA, Neo-GNN, and BUDDY cannot distinguish them. This is because Neo-GNN and BUDDY only leverage the count of CNs without utilizing their feature information. Although NCN incorporates CNs' features, it only considers 1-hop CNs. In our example, differentiation between $(v_1, v_2)$ and $(v_1, v_3)$ occurs only when 2-hop CNs are considered—where differences in their features break symmetry. This enables OCN to distinguish the pairs, whereas NCN degenerates to GAE and consequently fails to differentiate them.\n\n**Fig. 5** illustrates the inference time versus batch size on Collab (left), and the GPU memory consumption versus batch size (right). Different colors represent distinct models. For a detailed theoretical analysis, please kindly refer to *Appendix I*. The complexity expressions can be decomposed into slope and constant terms.  \n\n\n### W4. combined analysis in terms of scalability and performance\nThank you for your suggestion! Undoubtedly, our method excels in **both prediction accuracy and scalability**.\n\nRegarding prediction accuracy, according to the OGB leaderboard:\n**PPA**: Ours ranks 2nd. The top-ranked GraphGPT (SMTP) has a parameter count orders of magnitude larger than ours (and excels only on PPA and citation2). Refined-GAE is a purely empirical work relying on heavy hyperparameter search, and performs well only on PPA.\n**Collab**: Ours ranks 1st. HyperFusion is an A+B+C ensemble of existing methods (with much more parameters). Such hybrid models are prevalent among top leaderboard entries.\n**DDI**: Our model ranks 3rd, trailing the 2nd-place ELGNN by merely 0.12. The 1st-place is the ensemble method HyperFusion.\n\nIn summary, across the OGB—excluding citation2 where performance gaps are minimal—our model achieves 1st, 2nd, and 3rd placements. It delivers superior performance with low parameter counts, beating many ensemble methods.\n\nRegarding scalability, we kindly direct the reviewer's attention to **Fig. 9 in our appendix**, where we have made a full comparison of inference time of the baselines. In summary,\n1. OCN and NCN exhibit similar computational costs as they run the MPNN model only once.\n2. In contrast, SEAL incurs substantially higher overhead, especially with larger batch sizes, since it re-executes MPNN per target link, causing sharp inference time growth.\n3. OCN and OCNP generally scale better than Neo-GNN, while SEAL performs the worst.\n\n### Q1: The complete algorithm for orthogonalization and path-based normalization is presented in Algorithm 2 on page 34.  \nSpecifically:  $CN^k(u,v) = \\sum_{2(k-1) < k_1 + k_2 \\leq 2k, \\atop k_1 \\leq k, \\ k_2 \\leq k} \\left(A^{k_1}\\right)_u \\odot \\left(A^{k_2}\\right)_v.$\n\nThe defined k-order CN is a scalar value, but it is defined for a specific node pair $(u, v)$. The term $\\left(A^{k_1}\\right)_{u}$ (and similarly for $k_2$) actually counts the number of paths of length $k₁$ (or $k₂$) from this k-order CN node to $u$ (or $v$). \nWhat we actually orthogonalize is a matrix of shape $(h, n)$, where $h$ is the number of edges, and n is the total number of nodes. \n\nOrthogonalization:\nThe orthogonalization process is Gram-Schmidt, but applied to matrices. Orthogonality between matrices is defined by the Frobenius norm:$\\|A^T B\\|_F = 0 \\quad \\text{equivalent to} \\text{tr}(A^T B) = 0$\nSection 4.1 addresses how to obtain the true inner product on a large real-world graph. In real graphs, the number of edges $m$ and nodes $n$ is extremely large. Performing the full matrix multiplication across the entire graph is computationally expensive. And training is performed batch-wise, so we only have access to a submatrix $(m', n)$ constructed from the edges within the current batch, where $m'$ is the number of edges in this batch.\nOur goal is therefore to approximate the inner product computed over all edges (i.e., the true inner product achieving orthogonality on the full graph) using only the edges visible within the current batch. We maintain a running inner product across batches, which accumulates the contribution of historical inner product information then combined with the inner product calculated from the current limited information via a weighted sum. As the number of training steps tends towards infinity, this running inner product converges to the full-graph inner product. In our experiments, we observed that the inner products indeed converged to a stable value.\n\n4.2 aims to find a method that achieves mutually orthogonal results—even if approximately—while bypassing the Gram-Schmidt. We desire a way to directly compute the orthogonalized result from each $(m, n)$ matrix in a single step. Through proof, we discovered that simply applying $OCN^k = CN^k \\cdot \\text{diag}(T_k)$—that is, right-multiplying the $(m, n)$ matrix by a diagonal matrix (with an arbitrarily chosen polynomial basis placed on its diagonal). This reduces the time complexity from $O(k^2)$ to $O(k)$ (see Table 7).\n\nPath-based Normalization:\nThe exact steps and equations used for normalization in Section 5 are detailed in Definition 5.1. We provide accessible descriptions of the underlying concepts and their practical implications in lines 212-221. The precise, step-by-step computational workflow for path-based normalization is presented within the first for loop of Algorithm 2 on page 34.\n\nThank you once again for your questions and suggestions.\n\n### Q2: We have addressed this concern in our response to W1. Thank you!\n### Q3: We will revise the captions for better interpretation in the subsequent version."}, {"review_id": "1T3NKzz8Hz", "reviewer": "Reviewer_Ndeq", "summary": "This paper focuses on the link prediction problem and proposes a higher-order common neighbor-based method by alleviating the issues of redundancy and over-smoothing. Experimental results demonstrate the effectiveness of the proposed method.", "questions": "Q1. According to Equation (1), the definition of k-hop common neighbors includes three cases: $k_1= k_2 = k$, $k_1 = k_2 + 1 = k$, and $k_1+1 = k_2 = k$. However, the meanings of these cases are not clearly explained in the main text and are instead relegated to the appendix. \n\nQ2. The performance improvement of OCNP over OCN is not significant according to Table 6. This should be discussed in more details.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "S1. It is reasonable to use higher-order common neighbors to enhance the performance of link prediction. \n\nS2. The problems of redundancy and over-smoothing are clearly described, and two techniques: coefficient orthogonalization and path-based normalization are proposed to address these problems.\n\nS3. Theoretical analysis is provided to demonstrate the effectiveness of the proposed normalization technique on graphs.\n\nW1. The definition of k-hop common neighbors is not clearly presented and is difficult to follow.\n\nW2. The efficiency improvement achieved by OCNP is not significant.", "was_revised": true, "final_justification": "The authors addressed my concerns about k-hop common neighbors and the comparison with OCN. Thus, I will keep my positive score.", "rebuttal": "### W1.\nThank you deeply for your question! I hope the following answers will satisfy you.\nSpecifically: \n$CN^k(u,v) = \\sum_{2(k-1) < k_1 + k_2 \\leq 2k, \\atop k_1 \\leq k, \\ k_2 \\leq k} \\left(A^{k_1}\\right)_u \\odot \\left(A^{k_2}\\right)_v$\n\nThe defined k-order CN is a scalar value, but it is defined for a specific node pair $(u, v)$. It represents: if a node has paths to $u$ of length $k₁$ and to $v$ of length $k₂$ (this refers to any path, not necessarily the shortest path), and the lengths $k₁$ and $k₂$ satisfy the given constraints, then this node is considered a k-order CN for the pair (u, v). The term $\\left(A^{k_1}\\right)_{u}$ (and similarly for $k_2$) actually counts the number of paths of length $k₁$ (or $k₂$) from this k-order CN node to $u$ (or $v$). This definition is also the commonly accepted definition of CN in the link prediction field, although some models define CN based on the Shortest Path Distance , whereas ours on the length of walks (paths).\nWhat we actually orthogonalize is a matrix of shape $(h, n)$, where $h$ is the number of edges in the current batch, and n is the total number of nodes. In plain language, the definition in Appendix B means: For each order $k$, we have three matrices of shape $(h, n)$. e.g. for 4-hop CN, the distance pairs can be (4,4); (3,4); or (4,3). For 7-hop CN, (7,7); (6,7); or (7,6). For such an $(h, n)$ matrix, suppose it corresponds to the distance pair (3,4). Then, the value $z$ at row $x$ and column $y$ indicates that for the edge $(u, v)$ corresponding to row $x$, the total number of paths from the node corresponding to column $y$ to $u$ that are exactly of length 3, and to $v$ that are exactly of length 4, is $z$. If the total number of paths is 0, it means the node corresponding to column $y$ cannot reach $u$ and $v$ via any paths of lengths exactly (3,4) respectively. Consequently, this node is not a 4-hop CN under the (3,4) criterion. However, it might be a 4-hop CN under the (4,4) or (4,3) criteria. If it satisfies none of these criteria, then it is not a 4-hop CN for the pair $(u, v)$.\n\n### W2. \nThank you for raising this point. The primary goal of OCNP is to discover a method that achieves mutually orthogonal results—even approximately—while bypassing the Gram-Schmidt orthogonalization process. Since Gram-Schmidt requires each subsequent matrix to operate on all preceding orthogonal bases, we aimed to directly derive orthogonalized results from each $(m,n)$-dimensional matrix in a single step.\n\nThrough theoretical analysis, we proved that simply applying: $OCN^k = CN^k \\cdot \\text{diag}(T_k)$—i.e., right-multiplying the $(m,n)$ matrix by a diagonal matrix (with arbitrary polynomial basis elements on its diagonal)—yields results approximately equivalent to full Gram-Schmidt orthogonalization. This reduces the time complexity from $O(k^2)$ to $O(k)$ (see Table 7; theoretical analysis in Appendix I).\nConsequently, higher $K$ values deliver more pronounced asymptotic efficiency gains due to the $k^2 \\to k$ complexity reduction. OCNP’s key contribution lies in providing a paradigm-shifting perspective for bypassing Gram-Schmidt orthogonalization in future work.\n\n### Q1. \nThank you for highlighting this point! Indeed, we have elaborated on the classification and analysis of both symmetric and asymmetric cases in the Appendix. The theoretical framework remains universally applicable to both scenarios, though the main text only shows the case where the $k$-hop CNs are in symmetric positions. The asymmetric case follows a highly similar analytical approach.\nWe sincerely appreciate your suggestion and will clearly explain the meanings and implications of these cases in the main text in subsequent revisions.\n\n### Q2.\nThank you for your suggestion! Indeed, OCNP achieves virtually identical performance to OCN, as previously stated. The primary goal of OCNP is to discover a method that attains mutually orthogonal results—even approximately—while bypassing the Gram-Schmidt orthogonalization process. Though OCNP delivers approximately orthogonal outcomes, mathematically we can consider the final results of OCN and OCNP as approximately equivalent.\nThe key contribution of OCNP lies in its potential to inspire future methodologies for circumventing Gram-Schmidt orthogonalization. We sincerely appreciate your insightful question!\n\n### Figure 5 is too small and should be replotted.\n\nThank you for your suggestion! We have redrawn the figure, but it cannot be displayed here due to constraints. The updated version will be incorporated in subsequent revisions."}]

Author rebuttal:

Meta-review: The work offers useful, principled improvements for a widely used structural signal in link prediction. The method is simple, well-motivated, and effective, with ablations and theory. The remaining issues post-rebuttal are presentation-centric rather than technical: with clearer definitions, worked examples, and a compact cost and metrics summary, the contribution will be accessible and reproducible.

For the next version, I’d suggest: 1) making the core objects concrete with a toy graph, 2) adding a short subsection on the batch inner-product estimator such as what you store, the update rule, a one-line equation, and when it matches full-graph orthogonality in practice, 3) unifying reporting with two compact tables: one mapping each dataset to its metric, and one cost table with parameter count, training time, and peak GPU memory. In addition, you can consider making cosmetic chanes like tightening writing and figures and sharpening related-work positioning.
Decision: Accept (poster)