Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum

We wish to thank the reviewer for the positive and detailed review. Below we address the issues you raised:

1. Computational Feasability

Question: The proposed equiEPNN assumes access to full eigenvector decomposition, which can be computationally expensive for large graphs. How does the method scale in practice? Is it feasible for datasets like ogbg-ppa large molecule graphs?

Eigendecomposition is computationally feasible for ogbg-ppa. Despite the large number of average nodes and number of graphs in ogbg-ppa, 158,100 graphs with an average of 243.4 nodes per graph [OGB Documentation], we can see in the table below the eigendecomposition concludes in approximately 45 minutes, which we feel is reasonable, as this computation is a preprocessing step, which occurs only once during the training procedure.

We ran the eigendecomposition for ogbg-ppa on an NVIDIA A40 GPU. The rest of the results are taken from [Rampášek et al.] and were evaluated on an NVIDIA A100 GPU.

[Rampášek et al.] Rampášek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., & Beaini, D. (2022). Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35, 14501-14515.

2. Restrictiveness of Assumptions

Question: The paper presents completeness results for EPNN under specific sparsity and automorphism assumptions. How restrictive are these in practice?

In many popular datasets, the assumptions break quite often. Please note Table 1 in the manuscript features very common datasets, which do not adhere to the sparsity conditions. For example, in ENZYMES only 35.8% of the graphs fulfill one of the sparsity conditions. These restrictive conditions prompted us to develop equiEPNN, which alleviates the sparsity of eigendecompositions and is provably more expressive than EPNN.

3. Performance on Unsatisfactory Datasets

The proposed method relies on simple spectrum graphs and the sparsity condition outlined in Theorem 2. However, according to the Statistics Analysis in Table 1, most real-world datasets appear to not satisfy both conditions simultaneously.

We agree the sparsity conditions in Theorem 2 for the completeness of EPNN do not hold in many real-world dataset. In fact, one of the reasons we introduced equiEPNN is to alleviate this incompleteness. On the other hand, the simple spectrum presumption, which also applies for our analysis of equiEPNN, may not always hold as well. Yet, even in highly symmetrical datasets (which tend to have more high dimensional eigenspaces), the frequency of high dimensional eigenspaces is relatively low, thus the utility of equiEPNN practically applies to many datasets. Concretely, in ENZYMES and PROTEINS (highly symmetrical datasets), the average number of eigenvalues with multiplicity 2 and 3 are only 1.01 and 0.58, and 1.24 and 0.71, respectively.

More importantly, while our theoretical analysis focuses on simple spectrum graphs, equiEPNN can process graphs with eigenmultiplicity, as mentioned in the response to Reviewer nt25.

4. More Experiments

Would it be possible to provide more experimental results on datasets that fully satisfy the above conditions? Additionally, can the proposed method achieve comparable performance on datasets like ENZYMES and PROTEINS, which do not strictly meet the required assumptions?

Per your suggestion, we tested out equiEPNN on the PROTEINS and ENZYMES datasets [Morris et al.]. Below are the results:

On PROTEINS, we see that equiEPNN performs en par with the other spectral approaches, and quite close to PPGN, which has cubic complexity.

On ENZYMES, equiEPNN performs en par with most other methods, even PPGN, except compared to ChebNet, which uses complex Chebyshev interpolation on top of the eigendecomposition.

Additionally, we tested equiEPNN on a molecular property prediction task, OGBG-MOLPCBA, which is larger with 437,929 graphs and an average of 26 nodes per graph. The results are shown below

Property prediction results on OGBG-MOLPCBA

Here we compare to a leading spectral approach, ChebNet, and message-passing variants with a similar parameter count. We can see that we outperform ChebNet in this setting, and the other MPNN methods.

Furthermore, we tested equiEPNN on ZINC, where the graphs only partially satisfy one of the sparsity conditions (64.5 %), and we see that equiEPNN improves its empirical performance in comparison with EPNN [Gai et al.] and other leading models.

Graph regression results on ZINC with a parameter budget of ~500K

Below we further evaluate equiEPNN on ZINC with only 30K free parameters and we also evaluate equiEPNN on MNIST-Superpixels, a dataset that almost completely adheres to the completeness conditions of EPNN (see Table 1 in the paper), with 35K free parameters:

(bold denotes best overall result, and best result within the spectral category)

We can see that equiEPNN outperforms most other models, especially on ZINC where the graphs are sparse. On MNIST-SUPERPIXELS, which adheres to the completeness conditions, competing models are also able to capture the spectral information. In both cases, equiEPNN's capturing of rich spectral information allows it to perform en par with models with PPGN, a model with a cubic running time complexity.

5. Node-Level Tasks

The paper primarily focuses on graph-level tasks and the expressivity of models in distinguishing whole graphs. Have you considered how the proposed equiEPNN performs on node-level tasks, such as node classification or node clustering? Given that spectral methods often rely on global eigenvectors, how would equiEPNN handle localized, node-specific predictions in practice?

In this manuscript, we focused on the expressive power of spectral GNNs in terms of distinguishing among graphs, thus we believe node-wise prediction is out of scope for this paper. This is an excellent direction for future research, which we intend to look into.

Epilogue

We hope this response has addressed your concerns. If so, we would appreciate if you would consider updating your score. If there are any remaining issues or points needing clarification, we would be happy to address them.

Thank you for maintaining your positive evaluation and acknowledging that our comments addressed most of your concerns. We appreciate your suggestion to elaborate on insights and limitations in the paper. Below we outline our planned additions.

We will add a dedicated section on node-level expressivity, highlighting existing theoretical results and discussing future directions.

Theoretical Results

We will better highlight Subsection 4.3 in the paper, where in Theorem 3 we prove that EPNN induces unique node identifiers (UNIs) under sparsity conditions. Since equiEPNN alleviates eigendecomposition sparsity, it improves EPNN's ability to produce UNIs, allowing better node distinction.

Empirical Context

Recent work has shown that adding spectral information to MPNNs, via Laplacian positional encoding, usually improves their node classification performance [Fesser and Weber] (see table below).

GCN and GIN models, with and without Laplacian positional encoding, on node classification benchmarks:

This improvement was obtained by adding positional encoding (Laplacian eigenvectors) as initial node features, which did not respect the sign and basis ambiguity of the eigenvectors, and did not process the eigenvector information equivariantly. Thus, we conjecture that equiEPNN can outperform this implementation, but we leave this for future work.

We will also discuss limitations regarding the applicability to large graphs, and the real-world applicability of our theoretical results.

[Fesser and Weber] Fesser, Lukas, and Melanie Weber. Effective structural encodings via local curvature profiles. ICLR 2024

We appreciate the reviewer's recognition of the paper's theoretical rigor and the constructive proof of the expressive limitations of EPNN. We believe the reviewer's concerns are mostly due to expecting further empirical evaluation. We address this concern in the following response.

1. Runtime and Memory Overhead

What is the empirical runtime and memory overhead of equiEPNN versus EPNN on graphs? for example in case of $n>10^4$ nodes and $K>64$ eigenvectors?

equiEPNN has a marginal memory overhead and mild computational overhead versus EPNN. Firstly, note that equiEPNN is built on top of EPNN and its additional computational complexity is from its geometric update step. The complexity of this geometric update step of equiEPNN is at most n², which is also the running time of EPNN, thus their asymptotic running time are the same up to a constant.

Here's a table of empirical running time and memory overhead on ZINC:

We see that EPNN and equiEPNN require almost the same number of parameters, while equiEPNN requires about 18.5 % more compute time. PPGN [Maron et al.], which has cubic complexity, is significantly (54 %) more expensive computationally than EPNN.

2. Sparse Eigenvector Failure Modes

How prevalent are the sparse-eigenvector failure modes in large real-world graphs (e.g., social networks, protein interactions)?

We find that the sparsity conditions for the completeness of EPNN usually do not hold, justifying the necessity of equiEPNN.

For large real-world graphs, we choose the Cornell dataset, which consists of web pages and hyperlinks between them, and PPI, a benchmark protein-protein-interaction dataset. Empirically, we find that the (single) graph in the Cornell dataset does not meet any of the sparsity conditions, despite 91.7 % of its eigenspaces being one-dimensional. In PPI, while only 86 of the 31,281 eigenspaces are more than one-dimensional (i.e. 99.9 % are one-dimensional), none of the sparsity conditions hold. Thus, despite the graphs being close to having a simple spectrum, EPNN may be incomplete (miss crucial information) on them, due to the graphs' sparsity.

This analysis reveals the need for models that can handle sparse eigendecompositions more effectively. The equiEPNN model directly addresses this challenge, as proven in Corollary 1.

3. Handling Repeated Eigenvalues

Can equiEPNN handle repeated eigenvalues (higher multiplicity)? If not, what obstacles arise?

equiEPNN can naturally be extended to handle eigenvectors of eigenvalues of higher multiplicity, using the elegant formulation defined in [Huang et al.]. Thus, equiEPNN is applicable to any eigenmultiplicity and this is already implemented in the code.

Recall that the update steps of equiEPNN are defined as

$h_i^{(t+1)} = \\text{UPDATE}_{(t,1)}\\left(h_i^{(t)}, \\tilde{\\lambda}, \\left\\{(h_j^{(t)}, v_i^{(t)} \\odot v_j^{(t)}) \\mid j = 1, \\ldots, n\\right\\}\\right)$

$v_i^{(t+1)} = v_i^{(t)} + \\sum_{j=1}^{n} v_j^{(t)} \\odot \\text{UPDATE}_{(t,2)}\\left(h_i^{(t)}, h_j^{(t)}, v_i^{(t)} \\odot v_j^{(t)}\\right)$

where the $k$-th coordinate of $v_i^{(t)} \\odot v_j^{(t)}$ is the product of the $i,j$ coordinates of the $k$-th eigenvector. In the simple spectrum case, this operation is sign invariant. In the general setting, we consider invariants of the form $\\sum_{s =1}^n f(\\lambda_s)v_i[s]v_j[s]$. These functions are invariant, no matter what the eigenmulitplicity is. When the eigenmultiplicity is one, the elementwise product operation at the $s$ coordinate can be obtained by choosing $f$ such that $f(\\lambda_s)=1$ but $f(\\lambda_j)=0$ for $j \\neq s$. Thus, this method is equivalent to the one described in the paper in terms of the separation power when restricted to simple spectrum graphs.

[Huang et al.] On the Stability of Expressive Positional Encodings for Graphs, Huang et al. ICLR 2024

4. Empirical Performance of equiEPNN

Question: How does equiEPNN perform empirically compared to modern spectral GNNs on standard benchmarks? It would be valuable to assess the practical impact of the proposed solution in real-world scenarios.

We add comparisons on two benchmarks, proving the effectiveness of equiEPNN. Below we compare equiEPNN to leading models on a standard regression task for molecular graphs from the ZINC dataset, using models with 500K free model parameters:

Graph regression results on ZINC with a parameter budget of ~500K

Results of other models taken from [Ying et al.] and [Gai et al.]. We see that equiEPNN outperforms all other models for this task.

The second benchmark we add is a molecular property prediction task, OGBG-MOLPCBA, which is larger with 437,929 graphs and an average of 26 nodes per graph. The results are shown below

Property prediction results on OGBG-MOLPCBA

Here we compare to a leading spectral approach, ChebNet, and message-passing variants with a similar parameter count.

Epilogue

We hope this response has addressed your concerns. If so, we would appreciate if you would consider updating your score. If there are any remaining issues or points needing clarification, we would be happy to address them.

Thank you for addressing all of my questions. I have carefully reviewed your responses, as well as those provided to the other reviewers, and I appreciate the clarity and effort you put into them. I will revise my score.

We highly appreciate that the reviewer found the paper well-written and theoretically strong. We believe that we address the reviewer's concerns regarding the paper's focus and resolve the open question regarding the completeness of equiEPNN.

1. Eigenvalue Multiplicity Clarification

Clarify whether the eigenvalue multiplicity in question is geometric or algebraic. Does this matter and why?

In line 108, we assume our matrices are diagonalizable, and for such matrices, the algebraic and geometric eigenvalue multiplicities are equal. The various notions of Graph Laplacians are typically self-adjoint, and thus diagonalizable over the real numbers.

2. Focus on the Simple Spectrum Case

Explain why the obsession on the simple spectrum case, given that the main result is a negative one--that even in this case, EPNNs are not complete.

The focus on the simple spectrum case is based on the classical reference [2] (according to the numbering in our submission) which shows that when restricted to graphs with eigenmultiplicity m, graph isomorphism can be solved in $O(n^{2m+c})$ time, where n is the number of nodes and c is a constant related to the computational cost of computing the eigendecomposition. This suggests that the simple spectrum case is the easiest, and as the eigenmultiplicity m increases the problem becomes harder. Ultimately, we believe the GNN community should be able to design spectral-GNN models which are complete up to eigenmultiplicity m, where the larger m is, the more expressive the model. Our results show that we are still far from there, as standard spectral GNN are not complete even for m=1.

3. Handling Eigenvalue Multiplicity

Explain whether the degree of freedom in choosing eigenvectors that span eigen-subspace corresponding to eigenvalues of multiplicity >1 can be exploited, so that the chosen eigenvectors behave as if they are eigenvectors of the simple spectrum case. (The deeper question is what is intrinsically different about the complex spectrum case--eigenvalues or eigenvectors--that the authors chose not to analyze it.)

For graphs with multiple repeating eigenvalues, it is indeed unclear whether there is a good canonical choice of an eigenbasis, up to sign ambiguity. Therefore, handling eigenvectors of high order eigenspaces requires invariant features for each eigenspace. This is already fully incorporated into equiEPNN. We use the elegant method from [Huang et al.] which, for given nodes $i,j$ considers pairwise invariant features of the form $\sum_{s=1}^n f(\lambda_s)v_i[s]v_j[s]$. These features do not depend on the choice of eigenvectors inside each eigenspace, and are invariant regardless of the eigenmultiplicity. In the simple spectrum case they have equivalent discrimination power to the formulation we present in our submission. This is explained in more detail in our answer to Question 3 of reviewer nt25. Regarding the deeper question- we hope we answered this in our response to question 2, we'd be happy to discuss further if this answer does not address what you meant.

[Huang et al.] On the Stability of Expressive Positional Encodings for Graphs, Huang et al. ICLR 2024

4. Checking the Sparsity Conditions

Explain whether the sparsity condition on the eigenvectors required for EPNNs to be complete in the simple spectrum case can be checked in linear time for a given graph, thus justifying the practicality of the proposal for large graphs.

Spectral GNNs must compute the eigendecomposition (e.g. for positional encoding), thus no further computation time is required to check the sparsity conditions. We are not aware of a method that checks the sparsity assumptions and bypasses spectral eigendecomposition. However, note that Spectral GNNs compute the eigendecomposition in any case, so this inquiry is more on the practicality of Spectral GNNs in general.

In this context, it is worth noting that positional encoding via spectral methods is rather popular. Moreover, while the computational overhead of eigendecomposition is $O(n³)$, it only needs to be computed once as a preprocessing step, and not during training, and this complexity can be mitigated by considering only the top-k eigenvectors, and exploiting the sparsity of the graphs for eigendecomposition via the power method.

We provide the running time of computing the eigendecompositions of various datasets, including those with large graphs, below.

Running times are taken from [Rampášek et al.] and were evaluated on an NVIDIA A100 GPU.

[Rampášek et al.] Rampášek et al.. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems.

5. Incompleteness of equiEPNN

While the author proposed equiEPNN that has expressivity strictly better than EPNN in theory, whether equiEPNNs are complete in the simple spectrum case remains open. While the authors demonstrated equiEPNNs' better performance empirically in some datasets, theoretically this is still unsatisfying

We have recently proven that equiEPNN is incomplete on graphs with a simple spectrum. We also felt the need to address this issue, and indeed a few weeks ago we were able to show that equiEPNN is incomplete over simple spectrum graphs. This is proven by this counterexample:

Construction: Consider the subgroup $H \\leq \\{-1,1\\}^3$ defined by $H = \\{s \\in \\{-1,1\\}^3 : s_1 s_2 s_3 = 1\\}.$

Let $T \\in \\mathbb{R}^{4 \\times 3}$ be the matrix whose rows enumerate the elements of $H$:

We wish to thank the reviewer for recognizing our incompleteness results are valuable to the community and appreciating the novelty of equiEPNN. We understand the concerns raised are due to misunderstandings and insufficient empirical evaluation, and we believe we have addressed these issues below:

1. Sparsity Assumptions and Theoretical Completeness

The improved expressivity achieved by equiEPNN hinges on certain sparsity assumptions of the eigenvectors. These assumptions may not hold in many practical scenarios, potentially limiting the utility of the theoretical results.

Our theoretical results point to fundamental limitations of previous spectral methods while showing equiEPNN can, to a certain extent, bypass these sparsity limitations. equiEPNN is able to distinguish among a pair of graphs that violate the sparsity assumptions, see Corollary 1 in the manuscript, while EPNN is unable to distinguish this pair.

Nonetheless, we did not claim that equiEPNN is complete in the simple spectrum case, and actually we have recently been able to find a counter example showing that this is not the case. This new result is described in some detail in Answer 5 to reviewer BrRb, and will be incorporated into the camera ready of the paper, if accepted.

The main importance of these theoretical results, in our view, is in pointing out the shortcomings of prevalent spectral methods, which are not complete even in the simple spectrum case, and showing that their expressivity can be improved with a simple modification, which does not increase the model complexity. We believe these observations will lead to additional improvements, and ultimately to spectral models which are complete in the simple spectrum case.

2. Limited Empirical Validation

Empirical validations are limited to MNIST-Superpixel and ZINC. The generality of the findings across diverse graph types, especially those prevalent in real-world applications (e.g., social networks, biological graphs), remains to be further explored.

To address this concern, we introduce further benchmarks below.

The first benchmark we add is a standard regression task on the ZINC dataset of molecular graphs (in the manuscript, we tested eigenvector canonicalization on this same dataset). It has 12000 graphs with a 23.16 average number of nodes. We compare ourselves to leading methods with the standard ~500K parameter budget and find that our method attains the best results:

Graph regression results on ZINC with a parameter budget of ~500K

The second benchmark we add is a molecular property prediction task, OGBG-MOLPCBA, which is larger with 437,929 graphs and an average of 26 nodes per graph. The results are shown below:

Property prediction results on OGBG-MOLPCBA

We compare to a leading spectral approach, ChebNet, and message-passing variants with similar parameter count. equiEPNN performs strongly in comparison with leading models.

Epilogue

We hope this response has addressed your concerns. If so, we would appreciate if you would consider updating your score. If there are any remaining issues or points needing clarification, we would be happy to address them.