Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Overall this work contributes novel ideas from multiple aspects from introducing the new concept of GNNs being automorphic equivalence-aware to further push the expressiveness of these models, including the developed local definition of how to integrate this into the model, to the development of a genetic algorithm-based method for avoiding hand-crafted/hyperparameter tuned subgraph templates that are instead learned/efficiently searched.
main_review: Strengths:

S1) See the summary above.

S2) This work not only presents an empirically well performing method, but also theoretically proves the expressiveness to learn distinct representations of nodes having different local automophic equivalence sets which they have defined. 

S3) The background/related work of this work is well presented to provide context for the later method developed.

S4) The empirical evaluation is quite thorough. For example, even an investigation is made on the strength of the proposed GA-based subgraph search algorithm against other search algorithms such as randomized and Bayesian optimization-based method where their proposed method consistently outperforms the others across all datasets.

Weaknesses:

W2) The motivation of the structural equivalence in the second paragraph of the introduction is still not very convincing from a high-level when compared with the more traditional message passing GNN framework that also includes more information from those nodes in a clique formation as compared to longer-reaching weak ties. Although this is presented better throughout the paper, at this stage it still seems lacking.

W2) The comment that “previous analytic methods only classify nodes into categorical equivalence sets, which cannot be optimized for various specific applications in an end-to-end manner” seems to be incorrect as such non-categorical (structure) information has been presented in numerous self-supervised learning approaches to help guide graph neural networks. Please see the following surveys [1,2,3].

Other comments:

1) The way this work is searching for subgraph templates is somewhat related to the work in 3D GNNs that are learning appropriate 3D kernels [4] in point cloud and 3D molecule domain, which might be considered as related work. 

2) It would be appreciated to have more discussion on some of the findings (although acknowledging that space is already an issue with this work with much content being moved to the supplemental file), such as that in Figure 4(b) where the first layer is extremely biased towards S1, but in the second layer there seems to be hardly any statistical difference between the subgraphs. Also, discussing subgraph templates such as the triangle S3 in the main work, but only defining in the supplemental is not preferred.  


References:

[1] Xie, Yaochen, et al. "Self-supervised learning of graph neural networks: A unified review." arXiv preprint arXiv:2102.10757 (2021).

[2] Liu, Yixin, et al. "Graph self-supervised learning: A survey." arXiv preprint arXiv:2103.00111 (2021).

[3] Wu, Lirong, et al. "Self-supervised on Graphs: Contrastive, Generative, or Predictive." arXiv preprint arXiv:2105.07342 (2021).

[4] Lin, Zhi-Hao, Sheng Yu Huang, and Yu-Chiang Frank Wang. "Learning of 3D Graph Convolution Networks for Point Cloud Analysis." IEEE Transactions on Pattern Analysis and Machine Intelligence (2021).

I have read through the other reviews and responses, but am not inclined to update my score. Thank you.
limitations_and_societal_impact: This is not needed in the body of their work and they have provided the following in their checklist:
"""
Did you discuss any potential negative societal impacts of your work? 
Since our paper propose a general graph neural network model and the datasets we use are public available, no direct potential negative societal impacts is associated with our work.
"""
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the author proposed a GNN model that leverages the concept of automorphic equivalence. Specifically, they proposed GRAPE that uses learnable AE-aware aggregators to explicitly differentiate the structural equivalences of each node's neighbors with the aids of various subgraph templates. Moreover, the author theoretically prove that GRAPE is expressive in terms of generating distinct representations for nodes with different AE features. Experiment on real-world dataset proves the effectiveness of GRAPE.
main_review: Overall, the paper is well written, and the formulation process including theocratic proofs are adequate and solid. However, I have concerns of the practicability of the proposed method. I think it is a borderline paper between 5-6 (weak reject to weak accept).

Reasons to accept:
1. The paper is well written.
2. The formulation process including theocratic proofs are solid. 

Reasons to reject:
1. The proposed algorithm requires subgraph template, which may not be easily available in many real-world applications. In addition, I didn't find the studies for the impact of different subgraph templates to the performance of the proposed algorithm. Does different subgraph templates and different number of templates have a huge impact to the proposed algorithm?
2. The proposed algorithm seems to increase the complexity and might not be easily applied to real world applications. Although the authors showed the comparison of different algorithm's training time in Figure 4, the authors mentioned that two baselines Geniepath and GAT are trained on CPU, which is not a fair comparison. It is true that GAT used attention mechanism which will cost more GPU memory, but you can modify it to batch training, like in [1] https://arxiv.org/pdf/1806.01973.pdf, rather than training the whole graph at once. 
limitations_and_societal_impact: To me, there is no obvious negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a new GNN architecture, named GRAPE, which aims to take into account automorphic equivalence relationships in the egonets surrounding a node to improve the discriminative power of the learning architecture.
The authors present two theorems to support their architectural design and show numerical experiments on a number of datasets in which the new architecture appears to perform well.
main_review: The paper considers a variation of GNN which account for (local) AE relationships. In my view, there are already many related ideas (though not quite the same) out there, so I would rank the originality of this approach to be not that high.

I found a number of claims made in the paper to be somewhat surprising or lacking precision, e.g., it is stated that there are efficient algorithms to solve the graph isomorphism / automorphism problem. I don't think this is the case. These are clever heuristcs, but as far as I am aware there are no efficient (polynomial time) algorithms for solving the isomorphism problem. 

In a similar vein I found the discussion related to the WL algorithm confusing -- the WL algorithm is precisely used in the context of graph isomorphisms, and previous works (Morris et al, Xu et al) show that standard message passing cannot be more powerful than this algorithm, but can in fact be as powerful as the WL algorithm. However, the WL algorithm can distinguish non-automorphic nodes based on their neighborhoods; so I am not fully sure I get the point of Proposition 3.1 and Theoem 3.2.
As another point, the description of the genetic algorithm to be lacking sufficent detail to appreciate what is really done here.

Overall I found the theoretical contribution here to be not that convincing. In my view the proposed architecture is largely of interest because of its empirical performance -- which appears to be good. However, in this context a somewhat more rigorous experimental setup would have made for a much stronger paper and I would urge the authors to improve this section by including more relevant comparisons (like GNNs with random/unique initial node features, or GNNs based on higher-order WL equivalents); likewise the paper would benefit from the inclusion of a larger array of datasets.

============
Update post author reponse/discussion. I have raised my score to 6 following the responses of the authors
limitations_and_societal_impact: Given the broad literature on limitations of GNN (in terms of WL test, robustness guarantees, etc), I find it surprising that a discussion of the weaknesses of the presented method is not really present.
The possible societal impact of using graph neural networks in classification task (e.g., in social networks, as considered here) is also not discussed in any detail.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 
This paper studies the problem of improving the expressive power of GNN models. It computes the automorphism equivalence set for each node and uses the set to enhance the message passing. This method is proven to be more expressive than standard MPNN.

main_review: ### Originality 

This paper studies the problem of improving the expressive power of GNN models. It proposes to use automorphism-aware aggregation to achieve it.

Using a genetic algorithm to search for motif templates is novel. 

The method using automorphism equivalence matching and counting to improve the expressive power of GNNs is previously proposed in [6], while the relation of this work to [6] is not adequately addressed and discussed. [6] also proved by matching and counting subgraph isomorphism, the expressive power of GNNs can be improved. Though the AE-aware aggregator is not the same as the counting based aggregation in [6], the similarity in the core idea should definitely be discussed more.


### Quality

The claims in this paper are well justified. The experiments are well designed and able to show the effectiveness of the method.

### Clarity

The presentation is clear.

### Significance

This paper proposes to use automorphic matching to improve the graph neural networks’ expressive power. The motif template searching genetic algorithm can be useful in this direction, while the relation to [6] is not clearly discussed. My major concern is about the novelty here. I may raise my score if the connection to [6] can be clarified.


limitations_and_societal_impact: The authors addressed the limitations and potential negative societal impact.
review_title: null

Meta-review: This paper presents a new GNN architecture which addresses the automorphic equivalence among nodes. The idea is novel and effective. The results have demonstrated the superiority of the proposed approach. The reviewers liked the idea, while raised concerns such as some theoretical claims, datasets and the selection of subgraph templates. The authors have done a great job in rebuttal and have clarified some claims that caused misunderstanding. In the end, the reviewers reached consensus in accepting this paper. 
Decision: Accept (Poster)