Reviewer ZLDq

We thank the reviewer for the valuable feedback and for recognizing the motivation and the effectiveness of our work. In the following, we will clarify the raised questions.

Q1: Why Link Prediction task

Theoretically, we propose a new spectral GNN that can be applied to many problem settings. Essentially, it is an eigenbasis capable of encoding the linear constraints, which improves the expressivity. We focus on the link prediction task, which mainly its success depends on counting the sub-structures and triangles, which can be resolved by discriminating between the k-regular graphs, (what LLwLC is capable of doing it). We expect that LLwLC performs well in other tasks, but we did not conduct such experiments.

Q2: Expressivity

The sufficient conditions under which LLwLC can solve graph isomorphism entails that LLwLC is a universal approximator of functions defined on graphs [1]. Given that we can encode any subgraph into our eigenbasis, we can examine whether there exists a specific substructure collection that can completely characterise each graph. By the reconstruction conjecture we know that if we have all the $n − 1$ vertex-deleted subgraphs, then we can reconstruct the graph. Consequently, if the reconstruction conjecture holds and the substructure collection contains all graphs of size $k = n-1$ then LLwLC can distinguish all non-isomorphic graphs of size $n$ and is therefore universal. Based on [2], almost every graph has reconstruction number three. This is consistent with our experimental results, where we observed that certain small substructures such as Neumann constraints, significantly improve the results.

[1] Chen, Zhengdao and Villar, Soledad and Chen, Lei and Bruna, Joan, "On the Equivalence between Graph Isomorphism Testing and Function Approximation with GNNs.", NeurIPS, 2019.
[2] Bollobas, Bela, "Almost Every Graph Has Reconstruction Number Three.", Journal of Graph Theory, 1990.

Q3: Computational Complexity

The time complexity of extracting the subgraphs is at most O(n) (though as we discussed we can do it with only three subgraphs). The time complexity of our method, given the sparsity of graph Laplacian matrix, is $\mathcal{O}(\kappa E)+ \mathcal{O}(k^2n)$ for the outer loop (Lanczos algorithm) and the QR factorization, respectively, where $\kappa \ll n$ is the number of computed eigenvectors and $k \ll n$ is the number of linear constraints. Thus, we are linear w.r.t number of nodes.

Reviewer eeNp

We thank the reviewer for the insightful comments and will clarify the raised questions in the following.

W1: Theoretical Analysis of LLwLC.

We provide a new spectral GNN which encodes the subgraph structures into the eigenbasis. We encode relations between a "set of nodes/edges": we write each subgraph as a linear constraint, formulate it as an eigenvalue problem with linear constraints, and compute the eigenvectors accordingly. Encoding link representation (the same as the first constraint in Neumann constraints in Eq. 3 of the paper) in graph-structured data gives the power to count triangles and substructures. The sufficient conditions under which LLwLC can solve graph isomorphism entails that LLwLC is a universal approximator of functions defined on graphs [1]. Given that we can encode any subgraph into our eigenbasis, we can examine whether there exists a specific substructure collection that can completely characterise each graph. By the reconstruction conjecture[2], we know that if we have all the $n − 1$ vertex deleted subgraphs, then we can reconstruct the graph. Consequently, if the reconstruction conjecture holds and the substructure collection contains all graphs of size $k = n-1$, then LLwLC can distinguish all non-isomorphic graphs of size $n$ and is therefore universal. Based on [3], almost every graph has reconstruction number three. This is consistent with our experimental results, where we observed that certain small substructures such as Neumann constraints (or in the other ablation study with only ten vertex-deleted subgraphs) significantly improve the results. While, in theory, LLwLC can be applied to many problem settings, we focus on the challenging link prediction task.

[1] Chen, Zhengdao and Villar, Soledad and Chen, Lei and Bruna, Joan, "On the Equivalence between Graph Isomorphism Testing and Function Approximation with GNNs.", NeurIPS, 2019.
[2] Ulam, Stanislaw M, "A Collection of Mathematical Problems", 1960.
[3] Bollobas, Bela, "Almost Every Graph Has Reconstruction Number Three.", Journal of Graph Theory, 1990.

Q1 & Q4:

Thank you for the comment. As you mentioned in Q1, the round-off errors might raise numerical issues, which must be addressed. Actually, the numerical round-off errors are studied in sections 4.2 and 4.3and we prove that our proposed LLwLC has a convergence (numerical round-off errors are analysed here).

In section 4.2 (section 3.3 in the revision), we theoretically analyze the effect of numerical roundoff errors, which lead to a perturbed tridiagonal matrix. Theorem 1 shows the error bounds of the computed perturbed tridiagonal matrix. In section 4.3 (section 3.3 in the revision), we utilize Greenbaum’s results, which mention that for our computed perturbed Lanczos algorithm exists, an exact Lanczos algorithm but for a different matrix.
Also, Theorem 2 cognize the upper bound of the low-rank approximator of the Lanczos algorithm.

So, based on these three facts, we conclude that LLwLC has convergence, and the effect of practical round-off errors in the LLwLC is accurately investigated.

Q2: svd(T) in Fig. 2

In this step, we decompose the tridiagonal matrix $\mathbf{T}$ using eigendecomposition.

Q3: Orthogonal Projector

Thank you for the detailed correction.

Q5: Timings

The average time complexity is O(n). The time complexity of our method, given the sparsity of graph Laplacian matrix, is $\mathcal{O}(\kappa E)+ \mathcal{O}(k^2n)$ for the outer loop (Lanczos algorithm) and the QR factorization, respectively, where $\kappa \ll n$ is the number of computed eigenvectors and $k \ll n$ is the number of linear constraints. Thus, we are linear w.r.t number of nodes.

Q6: Neumann explanation

We revised the introduction to clarify that the only necessary constraint for LLwLC is that matrix C be full column rank. So, we can encode any linear constraint in our matrix. One possibility which is quite useful is the Neumann constraints, in which the first constraint is the link representation between the links in one-hop and two-hop away nodes (link representation), and the second constraint is the one-hop away subgraph.

We highly appreciate your time in reviewing our paper and providing constructive feedback to improve our work further. We updated the paper to improve on the presentation issues.

Reviewer NmSE

We thank the reviewer for the feedback and address the raised questions in the following.

Q1: Clarity

In the introduction, we summarized the MPNN expressivity limitations, mainly their inability to count cycles and the three main directions in the literature to address this problem. Then, we propose our novel spectral GCN, which explicitly utilizes the subgraph structures in eigenspaces to mitigate the existing limitations of GNN expressivity specifically for the task of link prediction where we can accurately show the effectiveness of our LLwLC (as discussed in Q2). We could shorten the discussion of the limitations if the reviewer thinks it would improve the clarity.

Q2: Relation between LLwLC and Link Prediction

We provide a new spectral GNN which encodes the subgraph structures into the eigenbasis. We encode relations between a "set of nodes/edges": we write each subgraph as a linear constraint, formulate it as an eigenvalue problem with linear constraints and compute the eigenvectors accordingly. While, in theory, LLwLC can be applied to many problem settings, we focus on the challenging link prediction task, which mainly its success depends on counting the sub-structures and triangles, which can be resolved by discriminating between the k-regular graphs (what LLwLC is capable of doing it). (Also, the expressivity power of LLwLC is discussed in Q4).

Q3: Link representation

The first constraint of the Neumann constraint is the link representation constraint.

Q4: Differences to NBFNet & SEAL

The main difference between our work and SEAL & NBFNet is that we consider the relation between "a set of nodes (an induced subgraph encoded as a linear constraint) or link representations between a group of nodes", which leads to more expressivity compared to MPNNs (Specifically, encoding link representation (the same as the first constraint in Neumann constraints in Eq. 3 of the paper) in graph-structured data gives the power to count triangles and substructures). The time complexity of LLwLC, given the sparsity of the graph Laplacian matrix, is in average linear w.r.t number of nodes. The more important comparison is concerning the expressivity of LLwLC. The sufficient conditions under which LLwLC can solve graph isomorphism entails that LLwLC is a universal approximator of functions defined on graphs [1]. Given that we can encode any subgraph into our eigenbasis, we can examine whether there exists a specific substructure collection that can completely characterise each graph. By the reconstruction conjecture[2], we know that we can reconstruct the graph if we have all the $n − 1$ vertex deleted subgraphs. Consequently, if the reconstruction conjecture holds and the substructure collection contains all graphs of size $k = n-1$, then LLwLC can distinguish all non-isomorphic graphs of size $n$ and is therefore universal. Based on [3], almost every graph has reconstruction number three. This is consistent with our experimental results, where we observed that certain small substructures such as Neumann constraints (or in the other ablation study with only 10 vertex-deleted subgraphs) significantly improve the results.

[1] Chen, Zhengdao and Villar, Soledad and Chen, Lei and Bruna, Joan, "On the Equivalence between Graph Isomorphism Testing and Function Approximation with GNNs.", NeurIPS, 2019.
[2] Ulam, Stanislaw M, "A Collection of Mathematical Problems", 1960.
[3] Bollobas, Bela, "Almost Every Graph Has Reconstruction Number Three.", Journal of Graph Theory, 1990.

Q5: Time Complexity

The time complexity of our method, given the sparsity of graph Laplacian matrix, is $\mathcal{O}(\kappa E)+ \mathcal{O}(k^2n)$ for the outer loop (Lanczos algorithm) and the QR factorization, respectively, where $\kappa \ll n$ is the number of computed eigenvectors and $k \ll n$ is the number of linear constraints. Thus, we are linear w.r.t number of nodes.

Q6: Comparison OGBL-Collab

Table 1 of the original paper actually contains the comparison to other methods. We just separated LanczosNet and LLwLC to show the effect of our proposed method in direct comparison to LanczosNet.

Reviewer 8BZ5

We thank the reviewer for the insightful comments. There were a few questions which we want to clarify in the following.

Q1: Benefits of Linear Constraints (Neumann constraints)

We encode relations between a "set of nodes/edges": we write each subgraph as a linear constraint and formulate it as an eigenvalue problem with linear constraints, and compute the eigenvectors accordingly. Encoding link representation (the same as the first constraint in Neumann constraints in Eq. 3 of the paper) in graph-structured data gives the power to count triangles and substructures. The sufficient conditions under which LLwLC can solve graph isomorphism entails that LLwLC is a universal approximator of functions defined on graphs [1]. Given that we can encode any subgraph into our eigenbasis, we can examine whether a specific substructure collection can completely characterise each graph. By the reconstruction conjecture[2], we know that if we have all the $n − 1$ vertex deleted subgraphs, we can reconstruct the graph. Consequently, if the reconstruction conjecture holds and the substructure collection contains all graphs of size $k = n-1$, then LLwLC can distinguish all non-isomorphic graphs of size $n$ and is therefore universal. Based on [3], almost every graph has reconstruction number three. This is consistent with our experimental results, where we observed that certain small substructures such as Neumann constraints (or in the other ablation study with only ten vertex-deleted subgraphs) significantly improve the results.

[1] Chen, Zhengdao and Villar, Soledad and Chen, Lei and Bruna, Joan, "On the Equivalence between Graph Isomorphism Testing and Function Approximation with GNNs." NeurIPS, 2019.
[2] Ulam, Stanislaw M, "A Collection of Mathematical Problems", 1960.
[3] Bollobas, Bela, "Almost Every Graph Has Reconstruction Number Three.", Journal of Graph Theory, 1990.

Q2: More than 2-hop neighborhoods

LLwLC is not limited to 2-hop neighborhoods (with an average time complexity of O(n)). In theory, the only requirement that matrix C must satisfy is to be full column rank.

Q3: Detailed Explanation of Fig. 1

The first Neumann constraint is the relation between nodes in 1-hop-away nodes and two-hop-away nodes $\Sigma_{y \in S, y\sim x} (f(x) - f(y)) = 0$ (edge representation between them). We represent it in the first row. So, if we multiply the first constraint with the eigenvector ($C^Tf = 0; (Left: -0.40 + 0.61 + 0.03 - 0.25 \approx 0$, Right: $-0.39 - 0.20 + 2 \times (0.29) \approx 0$)).

The second Neumann constraint is 1-hop-away nodes of the subgraph which is encoded by the degree of nodes in the subgraph $\Sigma f(x)d_x = 0$. We show it in the second row. So, if we multiply the second row with the eigenvector in the third row ($C^Tf=0$; Left: $2 \times 0.24 - 2\times 0.46 - 2\times 0.40 + 2 \times 0.61 = 0$ Right: $-2 \times 0.39 + 2 \times 0.23 + 2\times 0.36 - 2 \times 0.20 = 0$).

When we compute the eigenvectors by projecting to the null space of the constraints, we force the eigenvectors to be aware of the relation between a set of nodes/edges explicitly. So, the third row is one of the computed eigenvectors for the graphs which satisfy the constraints explicitly.

Q4: Time Complexity of "extracting bag of subgraphs"

Theoretically, regarding the time complexity, as we discussed in question 1, based on the reconstruction conjecture [1] we know that if we have all the $n-1$ vertex deleted subgraphs, then we can reconstruct the graph. So, worst-case time complexity is $\mathcal{O}(n)$, but as we discussed, theoretically[2] and experimentally, we can do it with a much less number of constraints.

[1] Ulam, Stanislaw M, "A Collection of Mathematical Problems", 1960.
[2] Bollobas, Bela, "Almost Every Graph Has Reconstruction Number Three." Journal of Graph Theory, 1990.

Q5: Technical Detail

Thanks for the detailed & valuable technical comments.

• Q5.1: Thanks for the correction. Of course, they cannot be applied to the inductive setting.
• Q5.2: We will change the iteration indexing such that both start at 0.
• Q5.3 & W1: As mentioned in the answer to Q1, SEAL does not utilize the relation between a set of nodes/edges, whereas the goal of LLwLC is to encode the relation between a set of nodes into the eigenbasis (SEAL ignores the pairwise relation between nodes). Also, regarding the effect of DRNL, as discussed in W1, please notice that the experiments with the LanczosNet in Tables 2 and 3 (specifically, Collab results) also utilize the DRNL features. However, their results are drastically worse than our novel LLwLC.

W2: Time Complexity

The time complexity of our method, given the sparsity of graph Laplacian matrix, is $\mathcal{O}(\kappa E)+ \mathcal{O}(k^2n)$ for the outer loop (Lanczos) and the QR factorization, respectively, where $\kappa \ll n$ is the number of computed eigenvectors and $k \ll n$ is the number of linear constraints.

We highly appreciate your effort in reviewing our paper and providing good feedback and constructive questions that further improve our paper.

W1 & Q5.3.:

We introduce a novel eigenbasis that addresses the significant limitations of MPNNs. So, our introduction mainly focuses on the limitations of MPNNs in general and how our proposed eigenbasis can address them. We do experiments on LP tasks because their success depends on counting the sub-structures and triangles, which can be resolved by encoding linear constraints into our eigenbasis and discriminating between the k-regular graphs. Also, as discussed in the introduction, the major limitation of previous subgraph-based link prediction is just leveraging oversimplified pairwise node representation features. DRNL, as you mentioned, strictly provides the distance relation "just" between the query nodes that we want to predict the link for and the other individual nodes. No more information is provided by the DRNL, specifically regarding the relation between "other nodes in the graph with each other" or "any set of nodes" (any linear constraints between nodes/edges), which leads to more expressivity (This is what DRNL is missing). On the other hand, LLwLC, given encoding "relation between a set of nodes/edges" in the input graph by encoding it as a linear constraint to the eigenbasis, can address this issue with time complexity linear to the number of nodes. (However, I agree with the reviewer that, given SEAL utilizing DRNL, it can provide oversimplified distance node representation. However, as I mentioned, it does not encode the relation between the graph's set of nodes/edges. So, LLwLC has stronger expressivity power than any labeling method by providing this information in its constraint matrix).

Q3:

We explain our subgraph policy extraction in detail in section 3.2 of our paper. As we explained, we investigate two policies: "Constraints C", where we encode "vertex deleted subgraph", which removes one node for any k-hop subgraphs to make each constraint. Also, to encode Neumann constraints for k-hop subgraphs, as we explained that the Neumann eigenvalue constraints encode the boundary conditions of the input graph, for the k-hop subgraph, for its first constraint, we only consider nodes in the boundary (between (k-1)-hop subgraph and k-hop subgraph; which provides us link representation expressivity). The second constraint also encodes the relation between the k-1 hop subgraph. Figure 1 shows the Neumann constraint (an example of encoding link representation) for two hops away nodes. The main difference between the two graphs is the first constraint, which encodes the relation between purple and green nodes (on the left, two purple nodes (two hops away) are connected to two green nodes (one hop away) (the color corresponds to the constraint on each node (1, 1, -1, -1)), while on the right the boundary nodes are connected to one node in two hops away (so the corresponding constraint is 2, -1, -1). The boundary nodes are different, so the link representation is different. So, the network will be capable of distinguishing between the two graphs).

Q4/Q5:

We extended our manuscript with a comparison of the computational complexities. A wall clock comparison will be provided in a potential camera ready.