Expressive Sign Equivariant Networks for Spectral Geometric Learning

Summary

The authors proposed a novel sign-equivariant model that is equivariant to the sign flip of eigenvectors for spectral graph learning. They demonstrated that the proposed architecture could capture the information when sign-invariant models would fail. The authors then made theoretical analyses of the sign-equivariant polynomial space and also proposed some constructible neural network architecture with sign-equivariance guaranteed by design. Experimental results on both the synthetic and real-world datasets demonstrate superior performance on link prediction, especially when automorphism exists.

Strengths

1. The paper is well-organized and easy to follow. The authors first provided an example to demonstrate the limitation of the previous "sign-invariant" models and then made theoretical analyses. Experiments were followed to demonstrate superior performance over the baselines. 2. The problem that the authors tried to address is novel. The authors pointed out the limitation of sign-invariant models and mathematically supported their claim in Proposition 1. The proposed "sign-equivariant" architecture can properly address the limitation, both theoretically and empirically. 3. The mathematics are solid and the claims are well-supported. The definitions of sign-equivariance and -invariance are well-formulated. Sign-equivariance of polynomials and neural networks is proven in the appendices. Universality is also proven and guaranteed. 4. Experiments on graphs with high symmetries demonstrated the effectiveness of the proposed model architecture. State-of-the-art performance was also achieved.

Weaknesses

1. Proposition 1 lacks some detail (See Question 1 & 2). 2. Limitation of the proposed architecture is not explicitly discussed.

Questions

1. In Proposition 1, the first result claims that if $f$ is sign invariant and the eigenvalues are distinct, then the node-wise representations are the same for automorphic nodes. Consider the complete graph of 3 nodes, the adjacency matrix is $$ \begin{pmatrix} 0&1&1\\\\ 1&0&1\\\\ 1&1&0\\\\ \end{pmatrix} $$ We have eigenvector $v_1=(1,1,1)$ belonging to $\lambda=2$ and $v_2=(0,1,-1)$ belong to $\lambda=-1$ (normalization is ignored for conciseness). Let $f$ be the pointwise absolute function, then $f$ is clearly sign-invariant (but not necessarily basis-invariant). In this graph, all three nodes are automorphic, but we have $z_1=(1,0)$ and $z_2=(1,1)$. This is probably because the eigenspace corresponding to $\lambda=-1$ is 2-dimensional. Therefore, I believe basis-invariance is also a necessary condition. The first claim is also not directly proven in Appendix A.3.2. Please provide a more detailed justification. 2. Similarly, the scenario when the dimension of the eigenvalue is greater than 1 is not explicitly discussed. In the above example, the sign-invariant model may still be capable of distinguishing the automorphic nodes. In footnote 2, the authors mentioned that sign invariant embeddings maintain "some positional information". The authors may provide a more accurate description using mathematical formulations similar to Proposition 1. 3. What are the potential limitations of the proposed model architecture?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

No potential negative societal impact is expected.

Summary

The paper proposes a sign-equivariant design for processing spectral features in geometric deep learning. This is particularly useful to process the eigenvectors of graph Laplacians and generate graph positional encodings, especially for link prediction tasks. The equivariant, rather than invariant, approach guarantees improved expressivity of the models, which is verified in a numberof experiments.

Strengths

The paper is clearly written and well motivated. I liked this simple yet effective design and I think the proposed method could be useful for many future works in the field.

Weaknesses

I don't see major flaws in the paper. See "Questions" for other comments.

Questions

I don't think the claim that the Geometric Deep Learning approach fails here is correct. The issue you describe is due to a bad design choice of intermediate representation within the network (i.e. the same as the input and output representation). Note that this choice is not common in other equivariant networks either; for instance, in group-convolution NNs (GCNNs), the input representation is an image (this is a quotient representation of $SE(2)$) but intermediate features transform like a regular representation (the output of a group convolution is a function over the full group, not only the pixels). This step is fundamental to achieve universal approximation. The limited expressive power you mention in line 48 is only due to the choice of intermediate representations (similarly, in a GCNN, if the intermediate features are constrained to transform as images, equivariance requires isotropic filters, which are indeed less expressive). In any case, while a group-convolution approach is probably a poor choice here (the group $(-1, 1)^k$ has size $2^k$), smaller representations which can provide a better trade off might exist. Your method seems to provide a nice solution to this, so I would argue it still fits within the GDL framework but provides a more efficient solution than its naive implementation. Isn't computing the eigenvectors of the graph Laplacian an expensive preprocessing step? Estimating these features has $O(n^3)$ complexity, which seems to exceed the $O(n)$ operations in the DSS layers (or $O(n^2)$ is an attention-based or message-passing based model). In Appendix A.2 you discuss the computational complexity of your method but do not include this aspect. Could you comment on this? Could you report the table with all baselines and their performance in Section 4.2? Also, is there any more recent work on this dataset you could include?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

I did not see an explicit discussion of the limitations in the paper, which I think would be a nice addition. For example, the authors could comment further on the complexity of computing the eigenvectors.

Summary

This paper contributes construction and analysis of sign equivariant neural network architectures for processing eigenvectors while respecting their symmetries. While a similar approach has been proposed by a prior work (Lim et al., 2023), this work is motivated by the fact that sign invariance, pursued in prior work, is in general not sufficient for multi-node tasks as sign invariance leads to structural node representations that does not distinguish automorphic nodes while multi-node tasks require positional node representations that provides a form of node identification (Srinivasan et al., 2019). The authors provide a construction of sign equivariant neural network architecture with analysis and provable guarantee on expressive power, and also propose its application as an alternative to PCA-based frame averaging which requires only a single evaluation of base model (while frame averaging requires 2^k) while guaranteeing equivariance to orthogonal groups in arbitrary dimensions. The developed architectures are empirically demonstrated for link prediction on graphs, n-body dynamics prediction, and node clustering on SBM graphs, which support the main claims of the paper. Lim et al., Sign and Basis Invariant Networks for Spectral Graph Representation Learning (2023) Srinivasan et al., On the equivalence between positional node embeddings and structural graph representations (2019)

Strengths

S1. The paper tackles an important and practical problem of developing expressive neural architectures that respect symmetry of eigenvectors, and successfully complements and improves key prior work (Lim et al., 2023) by achieving sign equivariance. Also, the paper is overall well written and easy to read, and the provided illustrations are clear. S2. The motivation for sign equivariance over invariance only is clearly presented in Section 2.1 where multi-node tasks are considered, and I find the discussion sound and informative. S3. In addition to multi-node tasks, a novel (as far as I can tell) and powerful alternative based on sign equivariance to PCA based frame averaging for modeling O(k) equivariant functions is provided. The approach trades off generality, as the base model (h) should satisfy sign equivariance unlike frame averaging that works with arbitrary base functions, but more efficient as it eliminates the requirement of frame averaging for 2^k forward passes. S4. The proposed parameterization of sign equivariant polynomial is novel and theoretically sound as it is grounded to the theory of equivariant polynomials. A strong theoretical guarantee on universality is provided for the non permutation equivariant case as well. S5. Overall, the experimental results overall seem sound and support the main claims of the paper. Lim et al., Sign and Basis Invariant Networks for Spectral Graph Representation Learning (2023)

Weaknesses

W1. The description of how sign equivariant network is applied in Appendix D.4 was a bit unclear to me. In in the equation e_ij = V_i^TDV_j, does the V refer to the output of sign equivariant module within the given GraphGPS layer? Is V passed and updated across GraphGPS layers?

Questions

I have no specific questions for now other than W1.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

As far as I can tell, the authors didn't address the limitations and potential societal impact of the work. I encourage the authors to discuss them in the next revision of the paper.

Summary

This paper focuses on addressing the sign ambiguity problem of eigenvectors. It argues that previous sign-invariant models are insufficient for some applications, e.g., link prediction and multi-node tasks. To solve this problem, the authors propose a sign-equivariant neural network with provable expressiveness guarantees, which is more powerful than the sign-invariant models and sign-equivariant linear maps. Experiments on various tasks validate the superiority of the proposed method.

Strengths

1. This paper is the first to study the sign-equivariance problem of eigenvectors. It finds that the signs of eigenvectors contain meaningful positional information but the sign-invariant models can only preserve the structural information. Therefore, the sign-invariant models cannot distinguish automorphic nodes and are insufficient for link prediction or multi-node tasks. 2. This paper proves that the sign equivariant polynomial can be implemented by the elementwise product between a linear sign-equivariant polynomial and a general sign-invariant polynomial. The linear sign-equivariant polynomial cannot learn the interactions between eigenvectors, and the sign-invariant polynomial cannot preserve positional information. This theoretical discovery combines the advantages of both methods and addresses their shortcoming. 3. Based on the characterization of sign-equivariant polynomial functions, this paper provides a general framework for analyzing the sign-symmetry models and gives a new perspective on the universality of SignNet.

Weaknesses

The major weakness of this paper is that it lacks experiments on real-world data. This paper uses three tasks, e.g., link prediction, n-body problem, and node clustering, to validate the effectiveness of the proposed method. However, all the experiments are based on synthetic data, which makes the results unconvincing. I think there are many real-world datasets for both link prediction and node clustering tasks, and the authors should give more empirical results on at least these two tasks.

Questions

This paper considers both sign-equivariance and permutation-equivariance. I wonder why the authors do not discuss the basis-equivariance for eigenvectors.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

This paper should discuss the limitation of sign-equivariance from the perspectives of efficiency and scalability.

Summary

This paper proposes to build sign equivariant neural networks with applications of the method in O(n) equivariant modeling and graph representation learning. They show that corresponding equivariant MLPs are inexpressive, by contrast to the proposed method which is universal (non-permutation equivariant version) or plausibly much more expressive (permutation equivariant version). Experiments are performed on artifcial datasets and show that the proposed method achieve comparable or better results than alternatives.

Strengths

This is a well written and motivated paper. I also appreciate the detailed appendix. The experimental protocol seems rigorous and results are presented for a few different settings. The paper highlights interesting and potentially useful applications of sign (O(1)) equivariance.

Weaknesses

(W1) I think the main result of this paper could be obtained from the results of [Villar 2021]. They already show how to use invariants to builds equivariant functions. Sign equivariance is O(1) equivariance, so it is a particular case of O(n) equivariance. This connection is not mentioned by the authors and would be important to investigate. As such polynomials may not really be needed, the results from invariant theory could be sufficient. Also, Proposition 11 from the aforementioned work may offer a way to obtain the desired permutation equivariance with universality. (W2) More generally, given the previous comment, I feel like the paper should situate itself more within the literature on O(n) equvariance, since sign and basis equivariance are that. I appreciate that some of the applications considered included processing eigenvectors, which is different from most of what is done in that literature, but this was already put forward by [Lim 2023]. (W3) The experiment on CLUSTERS is interesting but the improvement to other methods is not too important and has not convinced me of the practical usefulness of the method. Especially, since CLUSTERS is a synthetic task. It would also be great to have results on real-world graphs to see if the method brings a performance increase there. (W4) It seems like the proposal for orthogonal equivariance is a realization of the partial canonicalization framework of [Kaba 2023]. Partial canonicalization is performed with respect to SO(3), with the reminder handled by a sign equivariant function. Proposition 2 follows from their results. The results on the N-body problem seem worst compared to learned canonicalization, which should be included for comparison. There are also many other methods outside of those presented in [Puny 2022] that could be compared against. (W5) The paper [Sachs 1983] is relevant to the Proposition 1 presented in this paper and should be mentioned. (W6) I think the application on link prediction is the most promising aspect of the submission. The authors should compare with the setup/methods that was proposed by [Sartorras 2021] in their autoencoding experiment. In that paper, the method was used to solve a similar issue caused by automorphic nodes.

Questions

(Q1) Can the authors provide a comparaison of their theoretical results with [Villar 2021] and discuss how their work compares? (Q2) Would you elaborate on some limitations of this work and potential future directions?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes

Response to rebuttal

Hi, thanks for addressing my concerns. After carefully checking the appendix, I think the sign-equivariance networks have some benefits in terms of both efficiency and scalability. Also, I agree with the authors that the sign-equivariant layers can improve the sign-invariant readout functions, e.g., SignNet. The combination of local equivariant and global invariant is important for geometric deep learning. Although it is a pity that the authors do not provide more empirical results, I think the clear motivation and important theoretical results deserve a good point. Therefore, I raise my score to 6.

Comment on Authors' Rebuttal

I appreciate your comprehensive response regarding my concerns about some theorems on sign equivariance. You have also frankly and meticulously explained the potential limitation of the proposed model when the eigenvalues coincide. Though the proposed model may fail in this case, to the best of my knowledge, I believe that the authors have paved the road for a new sub-realm for further work on sign equivariance, which is important for tasks like link prediction where node-level GNNs would fail. In this sense, **I raise my score from 6 to 7**.

Response to rebuttal

Thank you for the response. I have no questions for now and will discuss with other reviewers.