OCN: Effectively Utilizing Higher-Order Common Neighbors for Better Link Prediction

W1.

Thank you deeply for your question! I hope the following answers will satisfy you. Specifically: $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$

The 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). What 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)$.

W2.

Thank 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.

Through 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). Consequently, 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.

Q1.

Thank 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. We sincerely appreciate your suggestion and will clearly explain the meanings and implications of these cases in the main text in subsequent revisions.

Q2.

Thank 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. The key contribution of OCNP lies in its potential to inspire future methodologies for circumventing Gram-Schmidt orthogonalization. We sincerely appreciate your insightful question!

Figure 5 is too small and should be replotted.

Thank 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.

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.

W1. methods used are well known

While 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.

Neo-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.

BUDDY 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.

NCN 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.

None 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.

W2. terms and concepts are undefined

Thank you for your question. The correlation coefficients in Fig.1 used are just standard Pearson and the graph is Cora. The 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.

All terms and concepts beyond common terminology are defined within the main text or appendices. We sincerely appreciate and hope your feedback.

W3. abbreviations, notations inconsistent, and plots (Fig.3–5)

Thanks! After a thorough verification, all abbreviations in the text were defined upon their first occurrence. Could you kindly provide more details regarding your concerns?

Fig.3: Without 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.

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.

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.

W4. combined analysis in terms of scalability and performance

Thank you for your suggestion! Undoubtedly, our method excels in both prediction accuracy and scalability.

Regarding prediction accuracy, according to the OGB leaderboard: 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. 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. DDI: Our model ranks 3rd, trailing the 2nd-place ELGNN by merely 0.12. The 1st-place is the ensemble method HyperFusion.

In 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.

Regarding 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,

1. OCN and NCN exhibit similar computational costs as they run the MPNN model only once.
2. 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.
3. OCN and OCNP generally scale better than Neo-GNN, while SEAL performs the worst.

Q1: The complete algorithm for orthogonalization and path-based normalization is presented in Algorithm 2 on page 34.

Specifically: $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.$

The 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$). What 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.

Orthogonalization: The 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$ 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 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. Our 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.

4.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).

Path-based Normalization: The 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.

Thank you once again for your questions and suggestions.

Q2: We have addressed this concern in our response to W1. Thank you!

Q3: We will revise the captions for better interpretation in the subsequent version.

W1.

Thank 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. Our 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.

4.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).

Due 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.

W2.

Thank 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.

W3.

Thank 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.

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$.

Conditioned on the past, the $w_i$ are i.i.d.: for $k<n$

$$\Pr(w_i=k)=\frac{\deg_{n-1}(k)}{Z},\qquad Z=\sum_{k=1}^{n-1}\deg_{n-1}(k).$$

Definition 1 We define the score based on the linking probability of $(i,j)$ $s_{ij}$: $Pr(i\sim j|s_{ij},G_{max(i,j)-1})=\frac{1}{1+e^{\alpha(s_{ij}-r_{min(i,j)})}},$

where $r$ satisfies $\deg(k)=NV(r_k)=NV(1)r^{D}_k$，$N = \text{number of nodes}.$

Proposition 1 When connecting an edge at vertex $b$, the expectation of degree of vertex $a$ (assuming $b>a$) is: $E(\deg_b(a))=m\frac{(2|a-b|+1)!!}{2^{|a-b|} |a-b|!}.$ Simultaneously, $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}}).$

Proposition 2 For any δ > 0, with probability at least δ, we have

$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}},$

where $\Delta=max(|k_i-k_{i+1}|).$

Proposition 3 For any δ > 0, with probability at least δ, we have

{ \frac{(2N+1)!!}{2^{N}N!}+ \frac{\sqrt{N\ln\delta^{-1}}}{4}}-1) +\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],$$ where $N=\text{number of nodes}$, $k$ represents the order of the k-hop CNs. **Proposition 4** After introducing normalizedCN, for any δ > 0, with probability at least δ, we have $$s_{ij}\leq 2k\Bigl[\frac{1}{\alpha}\ln(\Bigl[ -\frac{n-2}{N-n-1} W\!\Bigl( -\frac{N-n-1}{n-2}C^{\tfrac{1}{n-2}} \Bigr) \Bigr]^{-\tfrac{1}{k}}-1) +\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],$$ where $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).$

C = \frac{1}{\tbinom{\xi}{2}} \frac{D^{2k-1}} {\eta_{2k} - D^{2k-2} \dfrac{\sqrt{N\ln\delta^{-1}}}{4}}, $$ and $D$ is the maximum degree on the graph.

Plotting 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.

W4.

Thank 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.

W5.

Thanks! The results are as follows. As we can see, our models outperform [n2] on 5/6 datasets, and outperforms [n1] on 3/6 datasets.

Q1.

Thanks for your suggestion! The new results are as follows (hereinafter abbreviated as NC):

NC significantly outperforms the standard heuristics, demonstrating the importance of decorrelation and normalziation of high-order common neighbors.

The 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.

Q2.

Thanks 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}.$

Here, 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.

Q3.

The 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.

W1.

Thank 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.

W2.

Thank 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: $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$

The 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. What 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)$.

Orthogonalization: The 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:

$$\|A^T B\|_F = 0 \quad \text{is equivalent to} \text{tr}(A^T B) = 0$$

Section 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. Our 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.

4.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).

Path-based Normalization: The 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. Thank you very much once again for your questions and suggestions!

W3.

Thank 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. The 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.

Q1.

Thank you for your question! As 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.). Previous 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. We hope this answer addresses your query. Further discussion is welcome!

Dear authors,

Thank you for the detailed response and for your efforts in addressing my comments. Most of my concerns have been adequately addressed. While the introduction of OCN-3 aims to explore the role of higher-order CN, the empirical results for order 3 are not particularly strong, suggesting that the practical benefits of this extension remain to be further validated. As also noted by several other reviewers, the clarity and presentation of the paper still require further improvement. I will therefore maintain my current ratings.

Best regards,

Reviewer qjCp.