Towards Stable, Globally Expressive Graph Representations with Laplacian Eigenvectors

Authors: Junru Zhou, Cai Zhou, Xiyuan Wang, Pan Li, Muhan Zhang
Primary area: learning on graphs and other geometries & topologies
Keywords: graph neural networks, graph Laplacian eigenvectors

Abstract:
Graph neural networks (GNNs) have achieved remarkable success in a variety of machine learning tasks over graph data. Existing GNNs usually rely on message passing, i.e., computing node representations by gathering information from the neighborhood, to build their underlying computational graphs. Such an approach has been shown fairly limited in expressive power, and often fails to capture global characteristics of graphs. To overcome the issue, a popular solution is to use Laplacian eigenvectors as additional node features, as they are known to contain global positional information of nodes, and can serve as extra node identifiers aiding GNNs to separate structurally similar nodes. Since eigenvectors naturally come with symmetries---namely, $O(p)$-group symmetry for every $p$ eigenvectors with equal eigenvalue, properly handling such symmetries is crucial for the stability and generalizability of Laplacian eigenvector augmented GNNs. However, using a naive $O(p)$-group invariant encoder for each $p$-dimensional eigenspace may not keep the full expressivity in the Laplacian eigenvectors. Moreover, computing such invariants inevitably entails a hard split of Laplacian eigenvalues according to their numerical identity, which suffers from great instability when the graph structure has small perturbations. In this paper, we propose a novel method exploiting Laplacian eigenvectors to generate *stable* and globally *expressive* graph representations. The main difference from previous works is that (i) our method utilizes **learnable** $O(p)$-invariant representations for each Laplacian eigenspace of dimension $p$, which are built upon powerful orthogonal group equivariant neural network layers already well studied in the literature, and that (ii) our method deals with numerically close eigenvalues in a **smooth** fashion, ensuring its better robustness against perturbations. Experiments on various graph learning benchmarks witness the competitive performance of our method, especially its great potential to learn global properties of graphs.

Decision: reject
Reviewer scores: 5, 6, 6, 5

Reviews and discussion:
<thread>
creation date:
1730296699223

thread_type:
official_review

<thread_object>
creator: reviewer_erwe

<content>
summary:
This paper improves GNNs by incorporating Laplacian eigenvectors to capture global graph properties, addressing limitations in local message-passing approaches.  The proposed method uses learnable O(p)-invariant representations for each Laplacian eigenspace of dimension p and handles close eigenvalues in a smooth fashion, enhancing robustness and expressivity. Experiments show competitive performance, especially in capturing global graph characteristics.

strengths:
1. The proposed OGE-Aug method is theoretically robust, demonstrating strong expressiveness and stability. The underlying motivation is both novel and compelling.
2.  Empirical experiments indicate that OGE-Aug performs competitively and holds promise for real-world applications.
3. The theoretical contributions of this paper are sufficient, and the proofs appear sound.

weaknesses:
1. The proposed OGE-Aug method is intricate, highly complex, and challenging to implement. In this paper, the authors present a simplified version using a Cartesian tensor-based point cloud network, which introduces a gap between the theoretical framework and practical implementation.
2. This paper's writing is rough and difficult to read and follow. First, I recommend that the authors adopt the notation guidelines suggested by the ICLR template. In the current version, symbols such as V are used interchangeably to represent different elements, like sets and matrices, which makes the paper challenging to interpret. Second, the implementation of OGE-Aug should be presented with more detail, ideally including a pseudocode. 
3. There is no available code to reproduce the results or gain a deeper understanding of the method’s details.
4. In the experiments, the primary baselines are Laplacian-based embedding methods, but some recent state-of-the-art methods, such as Exphormer [1] on the PCQM-Contact dataset, are missing.
5. While the experiments include four different datasets or benchmarks, incorporating additional datasets or widely-used benchmarks, such as the OGB benchmark (e.g., ogbg-molhiv, ogbg-molpcba), could further strengthen the evaluation.

[1] Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, Ali Kemal Sinop. Proceedings of the 40th International Conference on Machine Learning, PMLR 202:31613-31632, 2023.

questions:
1. Please begin by clarifying the weaknesses section.
2. Could the authors provide an empirical comparison of training costs with the most competitive baselines?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730367954889

thread_type:
official_review

<thread_object>
creator: reviewer_9at4

<content>
summary:
This paper addresses the problem (established in [2]) of how to incorporate Laplacian eigenvectors into message-passing neural networks (MPNNs) to enhance expressivity while maintaining invariance to the symmetric group. The authors propose two main architectures to achieve this.

First, they present a natural method for integrating equivariant point cloud architectures into existing MPNNs. They then show that when using this method with a universal point cloud architecture, a universal GNN model can be constructed.

The paper then tackles the recently established problem (see [1]) of handling these eigenvectors in a stable manner. They propose a second architecture that, while sacrificing some expressivity compared to the first model, achieves provable stability bounds.

The paper concludes with empirical validation, showing that the second architecture achieves competitive, and in some cases state-of-the-art results across several standard graph benchmarks. 

[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 preprint arXiv:2310.02579, 2023.

[2] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint arXiv:2202.13013, 2022.

strengths:
1. The paper offers a simple and straightforward way to incorporate Laplacian eigenvectors into GNNs, making it easy to apply to existing architectures.

2. The theoretical result showing that the first approach can achieve universality with a model complexity of $n \cdot \exp(\text{max}(\mu))$ leverages the sparsity of natural graphs in an interesting way (most graphs have low values of $\mu$).

3. The approach is validated with competitive, and in some cases state-of-the-art, results across several common graph benchmarks, supporting its practical usefulness.

weaknesses:
1. The paper's novelty is somewhat limited. The idea of incorporating Laplacian eigenvectors into MPNNs while respecting the symmetries of the orthogonal group $O(d)$ was already discussed in [2], making the use of point cloud architectures a natural but not particularly novel approach. Similarly, the importance of stability when dealing with Laplacian eigenvectors was pointed out in [1], and the way the second model is derived from the first resembles the approach proposed in [1] as well.

2. The introduction and title of the paper emphasize improved global performance, but this is not explored in depth throughout the rest of the paper. A more convincing theoretical argument explaining why the proposed model enhances "global expressivity" would be beneficial. Additionally, synthetic experiments demonstrating that the model outperforms others in learning global properties of graphs would strengthen the claims. Lastly, a brief recap of the types of global information that can be inferred from Laplacian eigenvalues and eigenvectors would provide useful context and support the discussion.

3. The theory section could be more cohesive. The paper introduces a first model, notes its likely instability, and then replaces it with a second model that is provably stable but less expressive. All experiments are then performed on the second model. However, the discussion regarding expressivity primarily focuses on the first model, leaving the expressivity of the second under explored despite being the one used in practice. Additionally, the authors define stability in one way but then prove the stability of their model using a slightly different notion. This could benefit from clearer alignment and explanation.

4. The paper [3] provides a similar analysis, outlining expressivity bounds of previous methods using laplacian eigenvectors and proposing a new architecture. A comparison between the results of that work and the current paper could offer valuable insights and strengthen the positioning of this paper’s contributions.

5. While the results on the QM9 benchmark are promising, it would be helpful to include a comparison with other methods that also use Laplacian eigenvectors on this dataset. 



[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 preprint arXiv:2310.02579, 2023.

[2] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint arXiv:2202.13013, 2022.

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

questions:
The paper states that "taking inner products can potentially lose much of the rich structural and positional information carried by vanilla Laplacian eigenvectors." However, it seems to me that the inner product, which serves as a projection matrix onto the corresponding eigenspace, should preserve all the information about that space. I thought that the added expressivity comes from using more expressive point cloud architectures rather than the inner product itself.  Could the authors provide a more detailed explanation or proof of what specific information, if any, is lost when taking inner products of eigenvectors compared to using the raw eigenvectors? Additionally could the authors clarify whether the increased expressivity comes primarily from the expressive power of point cloud architectures rather than avoiding inner products?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730623823704

thread_type:
official_review

<thread_object>
creator: reviewer_7pzy

<content>
summary:
This paper studies the improvement of positional encodings (PEs) based on Laplacian eigenvectors, commonly used as feature augmentations to enhance the expressivity and effectiveness of GNNs.
The paper points out that existing PEs, which deal with symmetries of Laplacian eigenvectors with naive $O(p)$-group invariant encoders, may lose the full expressivity in the eigenvectors. Moreover, the paper argues that the instability resulting from the properties of eigenvectors is ignored in most research. Thus, the paper proposes a novel encoder to generate expressive and stable positional embeddings by utilizing invariant point cloud networks and incorporating smooth function for "soft splitting". Theoretical analysis and extensive experiments demonstrate the effectiveness of the proposed positional encoder.

strengths:
1. The paper is well-organized and easy to follow.
2. The experimental results seem promising.
3. Authors utilize a novel strategy to softly split the eigenvectors from different eigenspaces, solving the instability constraint of most existing work.

weaknesses:
1. The novelty of the method is somewhat limited, especially the direct application of existing invariant point cloud networks over the eigenvectors without any transfer challenge.
2. The paper doesn’t provide any detail about instance models of $\rho$, $\phi$, and $\psi$ (in Equations 6 and 7) implemented in the experiments, and doesn’t discuss the Lipschitz continuity of these practical models.
3. There is no detail about how OGE-Aug deals with the sign ambiguity of eigenvectors.
4. Authors ignore some essential experiments.
    - Authors don’t verify the stability of the OGE-Aug on OOD benchmarks such as DrugOOD [1], where SPE [2] is validated on this dataset.
    - There is no ablation study on the effectiveness of the proposed “soft splitting” strategy. I think it’ll be better to conduct experiments on Vanilla OGE-Aug as a control group.
    - There is no experiment studying the sensitivity of hyperparameters. For example, the authors don’t explore how different shapes of ρ influence the effectiveness and stability of the positional encodings.
    - The paper doesn’t report the running time of different positional encoding methods.
5. As mentioned in Line 346, insisting on the universality of invariant representation function f may hurt the stability of the positional encoder, however, there is no quantitative analysis nor experimental guidance about how to trade off university and stability.

[1] Ji, Yuanfeng, et al. "Drugood: Out-of-distribution dataset curator and benchmark for ai-aided drug discovery–a focus on affinity prediction problems with noise annotations." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 7. 2023.

[2] Huang, Yinan, et al. "On the stability of expressive positional encodings for graph neural networks." arXiv preprint arXiv:2310.02579 (2023).

questions:
See weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730726074175

thread_type:
official_review

<thread_object>
creator: reviewer_wryh

<content>
summary:
The paper presents a robust orthogonal group-equivariant neural network designed to enhance graph representation using Laplacian vectors. Experiments conducted on various graphs demonstrate the competitive performance of the proposed approach.

strengths:
- The writing is well-organized and generally reader-friendly.
- The theoretical analysis is comprehensive and detailed.

weaknesses:
- The datasets used in the experiments are somewhat limited. The proposed method would be more convincing if validated on a wider range of datasets, such as PATTERN, CLUSTER, or MolHIV.
- Additional illustrations, such as ablation or comparison experiments (e.g., investigating the impact of the continuous smoothing function *ρ*, or examining how the method captures global properties of graphs), would provide a more thorough and solid foundation for the study.

questions:
* Could you elaborate on how taking inner products may potentially lead to a loss of the rich structural and positional information provided by vanilla Laplacian eigenvectors (line 85)?
* How does the method scale to large-scale graphs? Could you discuss its scalability?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732700677875

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Paper revision

comment:
We thank all the reviewers for their thoughtful feedbacks and constructive suggestions. All the comments have been scrupulously considered. We are now presenting a revised version of the paper, in which we have integrated most of the reviewers' suggestions. We apologize for our late response, and hope that our revised paper could address the common concerns of the reviewers. We will continue to respond to each reviewer separately regarding other minor issues they have raised.

Here is an outline for our revision, which summarizes the changes compared with the previous version.

- **Regarding W2 of Reviewer eRwE:** Make symbols comply with ICLR format guide across the entire paper. Especially, we use different fonts for different use cases of symbol $V$: the bold upper-case $\bm{V}$ always represents a 2-D matrix, the bold lower-case $\bm{v}$ always represents a 1-D vector, while the calligraphic $\mathcal{V}(G)$ represents exclusively the node set of graph $G$. Other matrices and vectors are also made bold.
- **Regarding W3 of Reviewer 9aT4:** Slightly revise the definition of stability, making our theoretical result fully aligned with the definition. (In the revised **Definition 4.2**) 
- **Regarding Q1 of Reviewer wrYh and Q1 of Reviewer 9aT4:** Restate the source of expressivity gain of our proposed method: not merely from avoiding inner products, but by using more powerful point cloud networks. (In the revised **Section 1**) We will elaborate on this point in a subsequent response.
- **Regarding W2 of Reviewer 7pZy, W3 of Reviewer 9aT4, W1~2 of Reviewer eRwE:** Include a detailed description of our practical implementation of OGE-Aug in pseudocode, as well as a brief analysis of its computational complexity, expressivity and stability. (In the revised **Appendix D.2.1**)
- **Regarding W5 of Reviewer 9aT4:** Include **Point Set Transformer (PST)** [1], a baseline that also use Laplacian eigenvectors, on QM9. (In the revised **Table 1**)
- **Regarding W4 of Reviewer eRwE:** Include **Exphormer** [2], a state-of-the-art baseline on PCQM-Contact. (In the revised **Table 4**)
- **Regarding W1 of Reviewer wrYh and W5 of Reviewer eRwE:** Additional experiments on CLUSTER, PATTERN and ogbg-molhiv, validating the state-of-the-art performance of OGE-Aug. (In the revised **Appendix D.4**)
- **Regarding W4(1) of Reviewer 7pZy:** Additional experiments on DrugOOD, verifying the good OOD performance and stability of OGE-Aug.
- **Regarding W2 of Reviewer wrYh and W4(2)(3) of Reviewer 7pZy:** Ablation studies concerning the effect of smoothing function $\rho$ as well as the shape of $\rho$.

Additionally, **regarding W3 of Reviewer eRwE**, we have provided the code to reproduce our experimental results in the supplementary material.

[1] Xiyuan Wang, Pan Li, Muhan Zhang. Graph As Point Set. ICML 2024

[2] Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, Ali Kemal Sinop. Exphormer: Sparse Transformers for Graphs. ICML 2023.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732702998091

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Further comments regarding Q1 of Reviewer wrYh and Q1 of Reviewer 9aT4

comment:
Taking inner products will not lose information, **if we can find an encoder for** $n\\times n$ **matrices universal w.r.t. simultaneous row and column permutations.** That is to say, we need an encoder $f$ on $\\mathbb{R}^{n\\times n}$, such that given $\\mathbf{A}, \\mathbf{B}\\in\\mathbb{R}^{n\\times n}$, $f(\\mathbf{A})=f(\\mathbf{B})$ if and only if there exists $\\mathbf{P}\\in S\_n$ such that $\\mathbf{A}=\\mathbf{PBP}^T$. If such an $f$ exists, then we can get a universal representation of graphs by collecting a multiset $\\{\\!\\!\\{(\\lambda\_j,f(\\mathbf{V}\_j\\mathbf{V}\_j^T))\\}\\!\\!\\}$, since $\\mathbf{L}=\\sum\_{j=1}^K\\lambda\_j\\mathbf{V}\_j\\mathbf{V}^T\_j$.

But the real problem is that **existing methods that take inner products** (for example, BasisNet [1], SPE [2], Fürer invariant [3] or EPNN [4]) **fail to find such universal encoders for $n\\times n$ matrices.** For example, 

- BasisNet uses $f(\\mathbf{A})=\\text{2-IGN}(\\mathbf{A})$, which has the architecture of $f=R\\circ\\sigma\\circ L\_K\\circ\\sigma\\circ\\cdots\\circ\\sigma \\circ L\_1$. Each $L\_m$ has the form of $L\_m(\\mathbf{A})\_{ii}=\\mathrm{Linear}\\Big(A\_{ii},\\sum\_jA\_{ij},\\sum\_jA\_{ji},\\sum\_jA\_{jj},\\sum\_{j\\ne k}A\_{jk}\\Big)$ and $L\_m(\\mathbf{A})\_{ij}=\\mathrm{Linear}\\Big(A\_{ij},A\_{ji},A\_{ii},A\_{jj},\\sum\_k A\_{ik},\\sum\_k A\_{ki},\\sum\_k A\_{jk},\\sum\_k A\_{kj},\\sum\_k A\_{kk},\\sum\_{k\\ne l}A\_{kl}\\Big)$ for $i\\ne j$. The final layer $R$ is $R(\\mathbf{A})=\\mathrm{Linear}\\Big(\\sum\_i A\_{ii},\\sum\_{i\\ne j}A\_{ij}\\Big)$.
- Fürer invariant does not directly encode the multiset $\\{\\!\\!\\{(\\lambda\_k, f(\\mathbf{V}\_k\\mathbf{V}\_k^T)\\}\\!\\!\\}$. It lets $P\_{ij}^{(k)}=(\\mathbf{V}\_k\\mathbf{V}\_k^T)\_{ij}$, and $P\_{ij}=\\mathrm{concat}(P^{(1)}\_{ij},\\ldots, P^{(K)}\_{ij})$ where the concatenation is over all $P^{(k)}\_{ij}$ corresponding to different distinct eigenvalues $\\lambda\_1,\\ldots, \\lambda\_K$, and those $P^{(k)}\_{ij}$ are ordered in increasing order of $\\lambda\_k$. Then it takes the graph representation as $f(G)=f(\\mathbf{V}\_1\\mathbf{V}\_1^T,\\ldots, \\mathbf{V}\_K\\mathbf{V}\_K^T)=\\{\\!\\!\\{\\{\\!\\!\\{P\_{ij}:j\\in[n]\\}\\!\\!\\}:i\\in[n]\\}\\!\\!\\}$.
- EPNN does not directly encode the multiset $\\{\\!\\!\\{(\\lambda\_k, f(\\mathbf{V}\_k\\mathbf{V}\_k^T)\\}\\!\\!\\}$, either. Instead, it uses a message-passing-style encoder $f(G)=\\text{MessagePassing}(\\mathbf{X}, \\mathbf{P})$, where $\\mathbf{X}$ is the usual node feature, $\\mathbf{P}$ replaces the usual adjacency matrix $\\mathbf{A}$ by $P\_{ij}=\\{\\!\\!\\{(\\lambda\_k,(\\mathbf{V}\_k\\mathbf{V}\_k^T)\_{ij})\\}\\!\\!\\}\_{k=1}^K$, which somewhat looks like the Fürer invariant.

Although all above methods ensure permutation invariance and sign-basis invariance, none of the above proposes a way to **fully leverage the information in** $\\mathbf{V}\_1\\mathbf{V}\_1^T,\\ldots, \\mathbf{V}\_K\\mathbf{V}\_K^T$ (i.e., to universally encode them), even though we know that the set of $K$ $n\\times n$ matrices contains the full information of the graph. Actually, Bohang [4] has shown that EPNN is the most expressive one among those existing inner-product based methods, but EPNN is still upper-bounded by subgraph GNNs.

Based on the above discussion, we may answer **Q1 of Reviewer wrYh**: it is true that taking inner products between eigenvectors does not lose any information, but **it is true only when one uses a universal $n\\times n$ matrix encoder to encode such inner product matrices**, which is not the truth in previous works. Similarly, the answer to **Q1 of Reviewer 9aT4** is that the additional expressivity of our model comes from **using more expressive point cloud networks**, instead of avoiding inner products. Yet avoiding inner products makes it easier to build universal graph encoders: we circumvent the need of universally encoding $n\\times n$ matrices, but instead try to directly encode the $n\\times \\mu\_k$ “coordinates” within each Laplacian eigenspace, which can be easily realized by existing point cloud networks. Thus, our work actually finds a way to implement such a permutation and sign-basis invariant, yet universal graph encoder out of Laplacian eigenvectors, while existing works have failed. This is part of our main contribution. 

[1] Lim, Derek, et al. "Sign and basis invariant networks for spectral graph representation learning." *arXiv:2202.13013* (2022).

[2] Huang, Yinan, et al. "On the stability of expressive positional encodings for graph neural networks." *arXiv:2310.02579* (2023).

[3] Fürer, Martin. "On the power of combinatorial and spectral invariants." *Linear algebra and its applications* 432.9 (2010): 2373-2380.

[4] Zhang, Bohang, Lingxiao Zhao, and Haggai Maron. "On the Expressive Power of Spectral Invariant Graph Neural Networks." *arXiv:2406.04336* (2024).
</content>
</thread_object>

</thread>
<thread>
creation date:
1733308535830

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear Reviewers,

We sincerely appreciate your time and effort devoted to reviewing our paper. As the rebuttal period is soon coming to an end, this message is to gently notify you of our latest comments posted on OpenReview. We kindly request your attention to our comments, and look forward to your valuable feedbacks. 

Thank you again for your invaluable contributions to the evaluation of our paper.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper addresses the problem of how to incorporate Laplacian eigenvectors into message-passing neural networks to maximize expressivity while maintaining invariance/equivariance. The authors propose two main architectures to achieve this based on positional encodings from Laplacian eigenvectors. They improve the stability by incorporating a smooth function for "soft splitting" the eigenvectors. Theoretical analysis and extensive experiments demonstrate the effectiveness of the proposed positional encoder.

The reviews for this paper were borderline. The main weaknesses are the numerical evaluation, scalability, and little novelty since the reviewers 7pZy and 9aT4 claim that there are several similar methods in the literature.