Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: In this paper, SignNet and BasisNet new neural structures are proposed, which are the same as the two key SY invariants displayed by eigenvectors. It is also proved that under certain conditions, they can approximate any continuous function of invariants with the expected eigenvectors. The experimental results show that the proposed method is superior to the forward baseline in molecular graph regression, learning expression graph representation and learning neural field on triangular grid.
strength_and_weaknesses: In this paper, SignNet and BasisNet new neural structures are proposed, which is interesting
clarity,_quality,_novelty_and_reproducibility: This paper is of fair quality and novelty.
summary_of_the_review: My research field is not related to this manuscript and I am not very familiar with the research content.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose SignNet and BasisNet which are invariant to the sign and rotation symmetries that exist in eigenspaces, particularly in the Laplacian context for graphs. They demonstrate a universal approximation theorem with the approach under some conditions. They evaluated SignNet and BasisNet with various experimental tasks/datasets. 
strength_and_weaknesses: Strengths:

- The task that the authors are tackling is of general interest and importance, especially given the prevalence of Laplacian eigendecompositions in the literature, and the method/architecture that they propose are to the best of my knowledge novel and original. 

- The paper is well written and clearly motivated. 

- Their theorem on universal approximation for spectral graph convolutions is significant. 

- Their experimental evaluation is comprehensive and demonstrates the efficacy of the proposed approach well. 

Weaknesses: 

- Proposition 2, Theorem 2 and Proposition 3 are stated somewhat verbally/informally in the main paper. It would be ideal to include a mathematically rigorous statement in the main paper. In particular, given how commonly the term "universally approximates" is used in the paper, it was not rigorously defined in the main paper.  Given that there can be different types of universal approximation, it would be best to rigorously define it in the main paper to avoid any ambiguity/confusion. 


clarity,_quality,_novelty_and_reproducibility: Clear paper, well-written, novel approach that has strong experimental evaluation. 
summary_of_the_review: Overall a strong paper. Would be stronger if they make their theoretical statements more clear/specifically stated.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces two architectures SignNet and BasisNet that respect some basic symmetries inherited by spectral graph methods i) sign flips: if v is an eigenvector then so is −v; and (ii) more general basis symmetries: in higher dimensional eigenspaces there might be infinitely many choices of basis eigenvectors. The authors show that under certain conditions the proposed architectures are universal and can approximate any continuous function of eigenvectors with the proper invariances. Moreover, the networks are theoretically powerful for graph representation learning—they can provably approximate and go beyond both spectral graph convolutions and powerful spectral invariants. Experimental results are shown on molecular graph regression tasks, learning expressive graph representations, and texture reconstruction on triangle meshes. 
strength_and_weaknesses: Strength: Designing proper architectures that preserve symmetries and are more expressive than current ones is a very interesting and open topic in the graph machine learning literature. The proposed architectures in the paper are theoretically sound, and lead to nice integrations of symmetry-preserving positional encodings into a GNN framework. The results are adequately analysed and sufficiently supported.

Weaknesses: Some of the notions are not easy to understand from the text. Theorem 1 which is one of the main results of the paper should be discussed and explained more. 
clarity,_quality,_novelty_and_reproducibility: This is a relatively well-written paper, of high quality. The results are novel, and the authors provide enough material for reproducing them. 
summary_of_the_review: In summary, this is a strong paper with nice theoretical results. Some aspects that I think should be clarified are the following:

1) While Theorem 1 is interesting and insightful, could you please provide an explanation of what it implies in practice? Does it mean that when the group is a product, we could do separate sums over the elements of the group to achieve invariance? 

2) How does the computational complexity of IGN affect the overall complexity of the algorithm?

3) Is there an inductive bias towards locality in SignNet (as in other graph convolutional methods)? 

4) Figure 2 needs more explanation. Since the proposed positional encoding schemes can take as input node features, why do we need another GNN layer i.e., GNN(A,X,sigNet or basisNet(V,X)) on the top of that? Is that related to localisation aspects?
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work investigates the function invariance w.r.t. eigenvectors of graph Laplacian to reduce the learning complexity, including sign invariance and basis invariance. Then it proposes corresponding SignNet and BasisNet to incorporate these two invariances where many popular models can be directly plugged in as basic models. Moreover, it provides theoretical guarantees that the proposed models are expressive enough to conduct tasks beyond eigenvectors. Finally, the proposed methods are evaluated by synthetic and real-world experiments.
strength_and_weaknesses: Pros:
1. The motivation of introducing invariances into the model naturally reduces the learning complexity, which is verified sufficiently by excellent performance on real tasks against strong baselines.
2. It is very easy to directly plug many popular GNNs into SignNet to achieve performance boost, as shown in Table 1.
3. The theoretical arguments are comprehensive, including constructing SignNet and expressiveness of SignNet/BasisNet.

Cons:
1. Is BasisNet included in any experiment other than Appendix J.3? I am wondering whether BasisNet suffers high complexity because there might be many distinct multiplicities $d_i$ so that too many IGNs are included. In that sense, is there any way to implement BasisNet efficiently? Also, how is the runtime of BasisNet in Table 9?
clarity,_quality,_novelty_and_reproducibility: The details are presented clearly. 

The quality of theoretical arguments is good, and it enjoys great numerical performance. 

The novelty and reproducibility are also good.
summary_of_the_review: I would like to suggest an acceptance.

=== Acknowledgement ===

Due to time limit, I did not check proof in Appendix. The theorems seem to be good intuitively.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper introduces two new architectures (signNet and basisNet) that are invariant to sign flip of eigenvector and also to other basis vector symmetries arising from degenerate eigenvalues in higher dimensions. This is especially useful for models that use Laplacian eigenvectors. The paper demonstrates that these architecture innovations improve performance for molecular benchmarks.

All reviewers were impressed by the paper and recommend strong acceptance.
  
justification_for_why_not_higher_score: Still not fully clear what the what the practical implication is of the second model basisNet.
justification_for_why_not_lower_score: All reviewers feel that this is a significant contribution.
Decision: Accept: notable-top-25%