Equivariant Machine Learning on Graphs with Nonlinear Spectral Filters

Summary

This paper addresses the issue of inadequate modeling of graph equivariance in existing spectral GNNs due to nonlinear operations. The authors investigate the concept of domain translation in graph space as functional translations, drawing from the convolutional operations defined on images. Based on a series of in-depth analyses, they propose nonlinear spectral filters (NLSFs) that are fully equivariant to graph functional shifts and demonstrate universal approximation capabilities.

Strengths

1. The research problem is highly valuable, and the ideas presented are novel. 2. The theoretical analysis is rigorous, thoroughly supporting the arguments and solutions proposed in the paper. It reflects the authors' deep understanding and insight in the field. 2. Notable experimental improvements in classification tasks.

Weaknesses

1. The paper is missing important spectral GNN models such as [1,2,3,4]. 2. There is a lack of discussion on equivariant GNNs, such as [5,6,7,8,9,10,11,12]. While the focus is on spectral GNNs, it is also essential to discuss works in the spatial GNN domain, especially given that the paper’s title starts with "Equivariant Machine Learning on Graphs." Positioning your work within the broader GNN field can further elucidate the significance and unique advantages of your contributions. 3. The experiments are somewhat lacking in comprehensiveness. While you have demonstrated the effectiveness of your proposed model in common node and graph classification tasks, your core contribution is enhancing equivariant representation learning in spectral GNNs. I suggest adding experiments that specifically show how the improved performance is due to enhanced equivariant learning, such as graph isomorphism tests. [1] How powerful are spectral graph neural networks [2] Bernnet: Learning arbitrary graph spectral filters via bernstein approximation [3] Specformer: Spectral graph neural networks meet transformers [4] Graph neural networks with learnable and optimal polynomial bases [5] Universal Invariant and Equivariant Graph Neural Networks [6] E(n) Equivariant Graph Neural Networks [7] On the Generalization of Equivariant Graph Neural Networks [8] Expressive Power of Invariant and Equivariant Graph Neural Networks [9] Approximately Equivariant Graph Networks [10] Equivariant Polynomials for Graph Neural Networks [11] Graph Neural Networks for Learning Equivariant Representations of Neural Networks [12] Sign and Basis Invariant Networks for Spectral Graph Representation Learning

Questions

see weaknesses

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

4

Limitations

yes, the authors discuss the limitations in Section 6

Summary

This paper proposes a spectral GNN called non-linear spectral filters (NLSF), which aims to enhance GNNs with nonlinear functions. Since general GNNs with nonlinear functions do not commute with unitary operators, this paper defines Graph Functional Shifts, which is a set of unitary matrices commuting with a normal graph shift operator (GSO). It then formulates two functions for spectral index and filter bank, respectively, and concatenates these two functions as graph attention. In the experiment section, NLSF is compared with GAT, SAGE, and other spectral-like GNNs. In the node-classification task, att-Node-level NLSF shows outstanding performance among these models. In the graph classification task, att-Graph-level NLSF achieves comparable results with these models, and att-Pooling-NLSF performs better than other models in the graph classification task.

Strengths

1. NLSFs have a solid mathematical foundation and proof, especially on Universal Approximation and graph expressivity. 2. The experimental results validate the effectiveness of the theory.

Weaknesses

1. The method proposed in this paper requires the use of eigenvalues, hence it necessitates eigen decomposition of the GSO. The time complexity of eigendecomposition is relatively high, especially for very large graphs.

Questions

None

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

The authors introduce spectral GNNs that are equivariant to functional symmetries. Specifically, they introduce node-level, graph-level and pooling non-linear spectral filters and show that these are able to outperform standard convolutional GNNs on (semi-supervised) node classification and graph classification tasks.

Strengths

- The experimental results are compelling. - To the best of my understanding, the theory is sound - The idea being proposed is novel and worth being investigated - The paper is clearly written, even though it doesn't seem to be very accessible to readers unfamiliar with graphs signals processing

Weaknesses

- While the authors did a good job in trying to introduce all the relevant concepts, the paper is quite dense with mathematical details and notions that will likely be unfamiliar to many GNN researchers and may therefore hinder the accessibility of the manuscript.

Questions

- While it's very intuitive to understand what is meant by "shift" in the context of images and CNNs, this doesn't come across very clear in the paper in the context of graphs: what is the rationale behind the decision to "model the group of translations on graphs as the group of all unitary operators on signals that commute with the graph shift operator"? If more space in the paper can be used to make the underlying concepts more accessible (perhaps moving some of the material on the theoretical properties of the NLSFs to the appendix) I think the paper would greatly gain in accessibility, potentially increasing its impact beyond the graph signal processing community.

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

The limitations are clearly discussed.

Summary

The authors propose nonlinear spectral filters (NLSFs) that achieve full equivariance to graph functional shifts, demonstrating that these filters have universal approximation properties. These NLSFs are designed based on transferable spectral domain, potentially improving GNN performance in node and graph classification tasks across diverse graph structures.

Strengths

1- The paper is well-written and self-contained, offering clear, didactic insights. The experiments provide valuable conclusions that future practitioners will find useful. However, a synthesis of the information could further enhance readability and understanding for the reader. 2- The use of the nonlinear spectral filters for graphs to achieve full equivariance to graph functional shifts may be a promising avenue to explore.

Weaknesses

Despite these merits, I have the following concerns about the paper. 1- While the paper presents a compelling method with potential applications in graph analysis, one significant limitation is its scalability, particularly concerning large-scale graphs. The reliance on specific spectral properties, such as the leading eigenvectors, may not only limit the method's capacity to capture diverse graph dynamics but also result in computational inefficiencies when applied to extensive graph datasets. 2- The datasets used in the paper predominantly consist of mid-sized, homophilic graphs, which may not fully represent the diverse range of real-world applications, particularly in contexts involving heterophilic graphs. 3- The efficiency of the proposed models in terms of computation and resource utilization is not adequately discussed.

Questions

(i) Does your theory adapt differently when applied to heterophilous graphs compared to homophilous graphs, and if so, how are these differences addressed within your methodology? (ii) Given that your Nonlinear Spectral Filters (NLSFs) are motivated by respecting graph functional shift symmetries, similar to Euclidean CNNs, do you have any claims or observations regarding how NLSFs fit within or potentially extend the Weisfeiler-Lehman hierarchy of expressivity? Additionally, could you elaborate on how the expressivity of NLSFs, as informed by metrics from the Euclidean vector space, compares to traditional graph neural network models?

Rating

5

Confidence

5

Soundness

3

Presentation

3

Contribution

2

Limitations

Also, the efficiency of the proposed models in terms of computation and resource utilization is not adequately addressed. For practical applications, especially in resource-constrained environments, understanding the computational overhead is essential.

Summary

The paper tackles the task of Network design for graph neural networks. The suggested approach is based on spectral properties of graphs. So far in the literature spectral methods were limited in assuming that the graph domain is fixed. To address this, a relaxed version of symmetry is proposed based on band-limited projections. In addition, a nonlinear spectral filter design is suggested, suggesting node-level, graph-level, and pooling operations. The method is evaluated on several graph learning tasks, demonstrating improvement in generalization over existing spectral methods.

Strengths

The paper makes a valuable contribution to the literature on Graph Neural Networks (GNNs), particularly by addressing the challenge of transferability in spectral methods, which is highlighted as a significant issue. claims are supported by theoretical analysis. The paper is self-contained, providing both background information and a short overview on spectral graph learning.

Weaknesses

Writing Quality: Some sections of the manuscript could benefit from revision. For instance, reordering the paragraphs in the introduction could improve readability. Specifically, mentioning what was missing from previous works earlier rather than at the end would help. More examples can be found in the method section: i) The discussion on problem the activation functions is missing some details, e.g., what rho is exactly? ii) The paper states that "It is important to note that functional shifts, in general, are not induced from node permutations. In stead, functional shifts are related to the notion of functional maps...". This sentence is too vague. Consider adding more details to make it clearer. No qualitative results are provided. Is it possible to visualize learned features as in the illustration in figure 2? Is it possible to design a toy experiment showcasing the suggested notion of relaxed symmetry, for which the suggested network design generalizes adequately?

Questions

No question other than the weakeness stated above.

Rating

7

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes

reply to authors

I appreciate the author’s rebuttal and believe that their suggestions would greatly benefit the paper. I have no further concerns.