Towards Stable, Globally Expressive Graph Representations with Laplacian Eigenvectors

Thank you for your insightful comments and valuable questions. We respond to all the weaknesses and questions below. As we have revised our paper and given some responses in our public comments titled "Paper revision" (shortened as PR) and "Further comments regarding Q1 of Reviewer wrYh and Q1 of Reviewer 9aT4" (shortened as FC), in the following we will directly quote them if our intended response is already there.

For W1. We remark that the transition from Vanilla OGE-Aug (Definition 3.6) to OGE-Aug (Definition 4.1) is quite natural, by merely replacing the raw Laplacian eigenvectors with the "smoothed" eigenvectors. Although we admit there is a gap between our proposed OGE-Aug (Definition 4.1) and our implemented version (Algorithm 1), we claim that in the limiting case (by increasing tensor order to $O(n)$), our practically implemented OGE-Aug has the potential to recover the universal expressivity as is the case for Definition 3.6 and 4.1. Finally, our rationale to implement Algorithm 1 (instead of applying a universal point cloud network, as our theory indicates) is mainly due to the unacceptable complexity of $n\\cdot\\exp(\\tilde{O}(n))$ of applying such universal point cloud networks. There is an inevitable trade-off between the practicality of our model and the gap between our theory and implementation.

For W2. We have followed the suggestions, adopting notation guidelines suggested by ICLR template. Please refer to the 1st bullet point of PR as well as our revised paper. As for the pseudocode of our practically implemented OGE-Aug, please refer to the 4th bullet point of PR as well as Algorithm 1 in our revised paper.

For W3. We have already provided code to reproduce our experimental results in our supplementary materials.

For W4. Please refer to the 6th bullet point of PR as well as our revised paper.

For W5. Please refer to the 7th bullet point of PR as well as our revised paper. We provide the experimental results on the ogbg-molhiv benchmarks. We will update the result on ogbg-molpcba once they are ready.

For Q2. In our Table 6 we provide the training costs of our method on different benchmark dataset. We now compare them to some baselines. We take ZINC as our benchmarking dataset. In the following table, Time means training time per epoch. The baseline information is quoted from [1].

One may see that our model runs much faster than Graphormer [2] or SAN [3], even though our model also uses the graph transformer architecture with positional encodings computed from Laplacian eigenvectors. Moreover, our model is faster than subgraph GNNs like SSWL [4]. Those results verify the relatively good efficiency of our method.

[1] Xiyuan Wang, Pan Li, Muhan Zhang. Graph as Point Set. arXiv:2405.02795.

[2] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, Tie-Yan Liu. Do Transformers Really Perform Bad for Graph Representation? arXiv:2106.05234.

[3] Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, Prudencio Tossou. Rethinking Graph Transformers with Spectral Attention. arXiv:2106.03893.

[4] Bohang Zhang, Guhao Feng, Yiheng Du, Di He, Liwei Wang. A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests. arXiv:2302.07090.

For W3. Actually, if we require the $f$ in OGE-Aug (Definition 4.1) to be an $O(n)$-invariant universal representation, then OGE-Aug is no less expressive than Vanilla OGE-Aug, and is thus universal. However, this makes the method too costly. Thus, we do not use an $O(n)$-invariant universal representation for $f$ in practice. We provide the details of our practically used point cloud network (and the corresponding OGE-Aug architecture) in Algorithm 1 (Appendix D.2.1), in which only tensors up to 2nd order are used. Although we cannot quantitatively determine the expressive power of the resulting model, we argue that it is no less powerful than Point Set Transformer proposed in [1], as the point cloud network we use is no less powerful than the one adopted in [1].

Regarding the misalignment between our definition for stability (Definition 4.2) and Proposition 4.3, we have slightly revised our definition for stability (please refer to the 2nd bullet point of PR and our revised paper) to make our Proposition 4.3 fully align with it.

For W4. We have detailed such comparison in FC, in which the EPNN framework of [2] is discussed. Similar to existing works such as BasisNet [3] or SPE [4], EPNN is also among the methods that try to encode inner products between Laplacian eigenvectors, instead of directly encoding the eigenvectors themselves. Further, the expressive power of EPNN is bounded by certain subgraph GNNs (and thus by 3-WL), while our method has the potential to achieve universal representation of graphs.

For W5. Please refer to the 5th bullet point of PR as well as our revised paper.

For Q1. Please refer to the 3rd bullet point of PR, as well as FC.

[1] Xiyuan Wang, Pan Li, Muhan Zhang. Graph as Point Set. arXiv:2405.02795.

[2] Bohang Zhang, Lingxiao Zhao, and Haggai Maron. On the expressive power of spectral invariant graph neural networks. arXiv:2406.04336.

[3] Lim, Derek, et al. Sign and basis invariant networks for spectral graph representation learning. arXiv:2202.13013.

[4] Huang, Yinan, et al. On the stability of expressive positional encodings for graph neural networks. arXiv:2310.02579.

Thank you for your valuable comments and questions. We respond to all the weaknesses and questions below. As we have revised our paper and given some responses in our public comments titled "Paper revision" (shortened as PR) and "Further comments regarding Q1 of Reviewer wrYh and Q1 of Reviewer 9aT4" (shortened as FC), in the following we will directly quote them if our intended response is already there.

For W1. First, we explain why our method stands as a novel approach to incorporate Laplacian eigenvectors into MPNNs while ensuring sign-and-basis-invariance. As we have pointed out in FC, almost all existing methods to process Laplacian eigenvectors in a sign-and-basis-invariant fashion try to encode the pairwise inner products between Laplacian eigenvectors, which constitute an $n\\times n$ matrix for each eigenspace. It is currently unknown how to universally encode those $n\\times n$ matrices. Therefore, such methods fail to achieve universal representation of graphs. In contrast, our method provides a practical possibility to achieve universal representation of graphs, by directly encoding the Laplacian eigenvectors themselves with sufficiently powerful point cloud networks. This methodology shift marks a major novelty of our paper.

Second, we explain how our approach to ensuring stability differs from the one adopted in [1]. The work [1] uses $Z(G)=\\rho\\big(\\mathbf{V}\\mathrm{diag}(\\phi\_1(\\mathbf{\\Lambda}))\\mathbf{V}^T,\\ldots, \\mathbf{V}\\mathrm{diag}(\\phi\_m(\\mathbf{\\Lambda}))\\mathbf{V}^T\\big)$ to produce a provably stable positional encoding, while we use Z(G)=\\mathrm{MultisetEncoder}\\left(\\left\\{\\!\\!\\left\\{\\left(\\lambda\_k,f(\\mathbf{V}\_k^\\text{smooth})\\right)\\right\\}\\!\\!\\right\\}\_{k=1}^K\\right). One may easily see the following differences between our approach and the one in [1]: (a) we direct encode the Laplacian eigenvectors (with smoothing factors), instead of encoding the inner products between eigenvector pairs; (b) we explicitly treat different Laplacian eigenspaces separately, by first generating an encoding for each of them, and then pooling them into a multiset, while [1] only treats different Laplacian eigenspaces differently by an eigenvalue modulation factor $\\phi(\\mathbf{\\Lambda})$; (c) by properly selecting the smoothing function $\\rho$, we can control the degree of overlap between \\mathbf{V}\_1^\\text{smooth},\\ldots, \\mathbf{V}\_K^\\text{smooth}, which reflects the degree of parameter sharing across different eigenspaces. The approach in [1] is less flexible than ours.

For W2. We provide below a theoretical argument for the ability of our method to capture global properties of graphs. Notice that PSRD coordinates [2] can provably capture shortest-path distances (Theorem 5.1 of [2]), i.e., they are provably aware of global properties. But PSRD coordinates are just a special case of OGE-Aug, with the specific choice of the point cloud network similar to SchNet [3] or LorentzNet [4]. Therefore, OGE-Aug has the potential to capture global properties such as shortest-path distances. Actually, we remark that any graph property that can be expressed or approximated as a polynomial of the Laplacian $\\mathbf{L}$ is computable given full spectral information of $\\mathbf{L}$.

Currently, we did not conduct synthetic experiments to verify the above argument, i.e., the ability of our method to capture shortest-path distances or other long-range properties. We apologize for that, and will report our updated result in our future paper revisions or comments. On the other hand, we may still witness evidence of the good global performance of OGE-Aug from its results on several real-world benchmarks, such as the targets $U\_0$, $U$, $H$ and $G$ of QM9, as well as PCQM-Contact of the Long Range Graph Benchmark.

[1] Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, and Pan Li. On the stability of expressive positional encodings for graph neural networks. arXiv:2310.02579.

[2] Xiyuan Wang, Pan Li, Muhan Zhang. Graph as Point Set. arXiv:2405.02795.

[3] Kristof T. Schütt, Pieter-Jan Kindermans, Huziel E. Sauceda, Stefan Chmiela, Alexandre Tkatchenko, Klaus-Robert Müller. SchNet: A continuous-filter convolutional neural network for modeling quantum interactions. arXiv:1706.08566.

[4] Gong, S., Meng, Q., Zhang, J. et al. An efficient Lorentz equivariant graph neural network for jet tagging. J. High Energ. Phys. 2022, 30 (2022).

Thank you for your thoughtful comments and valuable suggestions. We respond to all the weaknesses below. As we have revised our paper and given some responses in our public comments titled "Paper revision" (shortened as PR) and "Further comments regarding Q1 of Reviewer wrYh and Q1 of Reviewer 9aT4" (shortened as FC), in the following we will directly quote them if our intended response is already there.

For W1. Although we propose to apply existing invariant point cloud networks to Laplacian eigenvectors, we point out that such application is not "without any transfer challenge".

• First, invariant point cloud networks typically process only fixed-dimensional data (for example, 3-dimensional Euclidean coordinates), while our application requires that such networks are able to deal with coordinates with different dimensions (since Laplacian eigenspaces have different dimensions). This requirement restricts the types of point cloud networks that we may use. It is also necessary to re-implement the point cloud networks (making them able to accommodate different dimensions) to adapt them to our case. As is shown in Appendix D.2.1 in our revised paper, the invariant point cloud network used in our practically implemented OGE-Aug is different from any existing one. So actually we did not directly apply an existing point cloud network, but re-designed one.
• Second, as we have pointed out in FC, almost all existing methods to process Laplacian eigenvectors in a sign-and-basis-invariant fashion try to encode the pairwise inner products between Laplacian eigenvectors, which constitute an $n\\times n$ matrix for each eigenspace. It is currently unknown how to universally encode those $n\\times n$ matrices. Therefore, such methods fail to achieve universal representation of graphs. In contrast, our method provides a practical possibility to achieve universal representation of graphs, by directly encoding the Laplacian eigenvectors themselves with sufficiently powerful point cloud networks. This methodology shift is a major novelty of our paper.
• Finally, the fact that an arbitrary invariant point cloud network can be integrated into our framework is itself a novelty of our claimed method, as it is quite flexible.

For W2. The explicit form of $\\rho$ is given in equation (73) of our revised paper. As for $\\phi$ and $\\psi$, we remark that our practical implementation of OGE-Aug is shown as Algorithm 1 in Appendix D.2.1 of our revised paper, which does not fully align with equation (7). Therefore, instead of discussing the Lipschitz continuity of $\\phi$ and $\\psi$ separately, we can discuss the Lipschitz continuity of the entire Algorithm 1. Algorithm 1 includes two types of layers: MLP layers on the tensor products, as well as message passing layers. The Lipschitz continuity of those layers with respect to their arguments will be upper-bounded as long as norms of the network parameters are not large. Therefore, we claim that stability results similar to Proposition 4.3 can hold for Algorithm 1.

For W3. Our framework explicitly respects sign invariance. Because by definition of $O(p)$-invariant universal representations (Definition 3.3), if $f$ is such a representation and $\\mathbf{V},\\mathbf{V}'\\in \\mathbb{R}^{n\\times p}$, with $\\mathbf{V}'$ being identical to $\\mathbf{V}$ except for some columns flipping signs, then obviously there exists orthogonal matrix $\\mathbf{Q}$ (diagonal, whose diagonal elements corresponding to those sign-flipped columns are -1, otherwise 1) that makes $\mathbf{V}=\\mathbf{V}'\\mathbf{Q}$. Thus $f(\\mathbf{V})=f(\\mathbf{V}')$.

For W4, bullet point 1. Please refer to the 8th bullet point of PR and our revised paper.

For W4, bullet points 2 and 3. Please refer to the 9th bullet point of PR and our revised paper.

For W4, bullet point 4. We reported our running time in Table 6 of the revised paper.

For W5. Although we don’t have a rigorous quantitative study on how insisting on a universal $f$ could lead to stability loss, we qualitatively argue that the more complex $f$ is, the larger $J\_f$ tends to be, making the stability bound looser. This fact somewhat implies a stability loss. A quantitative analysis of this question may be conducted by measuring the constants $J\_f$ of different point cloud networks $f$, and empirically observe the effect on $J\_f$ with increasing expressivity in $f$. But this would be out of the main scope of our work.

Moreover, we point out that our main consideration to reject a universal $f$ is that it would be too computationally costly. Actually, the point clout network architecture we use can theoretically reach universality as long as we use very high-order tensors. But this makes the complexity at a scale of $O(n\\cdot n^n)$ which is unacceptable. That’s why in our Algorithm 1 we restrict the tensor order to be at most 2, making the complexity polynomial.

Thank you for your insightful comments and questions. We respond to all the weaknesses and questions below. As we have revised our paper and given some responses in our public comments titled "Paper revision" (shortened as PR) and "Further comments regarding Q1 of Reviewer wrYh and Q1 of Reviewer 9aT4" (shortened as FC), in the following we will directly quote them if our intended response is already there.

For W1. Please refer to the 7th bullet point of PR, and the revised paper.

For W2. We investigated the impact of using different $\\rho$, by altering the range width $\\delta$ on which $\\rho$ has a non-zero value. Moreover, we compared the performance of OGE-Aug on ZINC with that of Vanilla OGE-Aug to verify the significance of using the smoothing function $\\rho$. Please refer to the 9th bullet point of PR and the revised paper.

To discuss how our method captures global properties of graphs, we may notice that PSRD coordinates [1] can provably capture shortest-path distances (Theorem 5.1 of [1]), i.e., they are provably aware of global properties. But PSRD coordinates are just a special case of OGE-Aug, with the specific choice of the point cloud network similar to SchNet [2] or LorentzNet [3]. Therefore, OGE-Aug has the potential to capture global properties such as shortest-path distances. Moreover, the good performance of OGE-Aug on some real-world benchmarks, such as the targets $U\_0$, $U$, $H$ and $G$ of QM9, as well as PCQM-Contact of the Long Range Graph Benchmark, also stands as evidence for the strong capabilities of OGE-Aug to capture global graph properties.

For Q1. Please refer to the 3rd bullet point of PR, as well as FC.

For Q2. In our revised paper, we show that the time complexity of our practically adopted OGE-Aug is $O((n^2\\max\_j\\mu\_j+m)\\cdot\\max\_j\\mu\_j)$, where $n$ and $m$ are the number of nodes and edges, respectively, while $\\max\_j\\mu\_j$ is the maximum dimension of Laplacian eigenspaces. Therefore, our OGE-Aug scales much better than 3-WL based methods such as 1-2-3-GNN or PPGN, which have time complexity $O(n^3)$, and comparable to subgraph GNNs, which have time complexity $O(nm)$.

We also empirically measure the training time per epoch of our model. The result is shown in Table 6 of our paper. We now compare it to some baselines. We take ZINC as our benchmarking dataset. In the following table, Time means training time per epoch. The baseline information is quoted from [1].

One may see that our model runs much faster than Graphormer [4] or SAN [5], even though our model also uses the graph transformer architecture with positional encodings computed from Laplacian eigenvectors. Moreover, our model is faster than subgraph GNNs like SSWL [6]. Although the graphs in ZINC have small sizes (even too small to make dense-product based methods like SUN or PPGN inefficient), the above result still partially shows the relatively good efficiency (thus potential for scaling to large-scale graphs) of our OGE-Aug.

[1] Xiyuan Wang, Pan Li, Muhan Zhang. Graph as Point Set. arXiv:2405.02795.

[2] Kristof T. Schütt, Pieter-Jan Kindermans, Huziel E. Sauceda, Stefan Chmiela, Alexandre Tkatchenko, Klaus-Robert Müller. SchNet: A continuous-filter convolutional neural network for modeling quantum interactions. arXiv:1706.08566.

[3] Gong, S., Meng, Q., Zhang, J. et al. An efficient Lorentz equivariant graph neural network for jet tagging. J. High Energ. Phys. 2022, 30 (2022).

[4] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, Tie-Yan Liu. Do Transformers Really Perform Bad for Graph Representation? arXiv:2106.05234.

[5] Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, Prudencio Tossou. Rethinking Graph Transformers with Spectral Attention. arXiv:2106.03893.

[6] Bohang Zhang, Guhao Feng, Yiheng Du, Di He, Liwei Wang. A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests. arXiv:2302.07090.