Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This manuscript presents a general-purpose technique to improve GNN expressivity, dubbed as GNN-AK, that replaces the conventional neighbourhood/star-like aggregation (multi-set of neighbour embeddings) with an ego-net level aggregation. In particular, at each layer of GNN-AK, the authors first extract all $|\mathcal{V}|$ ego-nets of the original graph, then they apply a GNN on each one of them, and finally, they collect their outputs into node-wise representations.  The expressive power of different variants of their model is theoretically analysed (more expressive than 1-WL when the ego-net aggregation is as expressive as 1-WL, and no less powerful than 3-WL, when the ego-net aggregation is as expressive as 3-WL) and a series of design choices for a practical instantiation is provided. The authors extensively evaluate their method on both synthetic and real-world datasets and ablate the influence of some of the moving parts in the overall performance.
main_review: **Strengths**:
-	The paper is nicely written, has a good flow and is easy to follow.
-	The idea of ego-nets is simple and straightforward to implement. Contrary to other GNNs that improve expressivity using some kind of structural property (e.g., Bouritsas et al., arxiv’20,  Thiede et al., NeurIPS’21, Barceló et al., NeurIPS’21 and others), GNN-AK requires fewer hyperparameters to be selected by the user (mainly the size $k$ of the ego-net).
-	Practical solutions that improve scalability without sacrificing performance are proposed.
-	The experimental section is extensive and the method obtains competitive results in many datasets, which is a good indication that the proposed architecture will work well in practice.

**Weaknesses**:
My main concerns about this paper have to do with (1) its novelty, (2) the fact that the practical instantiation contains multiple choices that are not justified from the theory and obfuscate the actual underlying reason for the good empirical performance. In more detail:

1. **Novelty**: The idea of using ego-nets to improve the expressive power of GNNs is not completely new. As the authors also mention, this idea has been used several times in the past. For example, a reference that the authors have missed, “Identity-aware Graph Neural Networks”, You et al., AAAI’21, is also closely related and it goes one step further in terms of the theoretical results, showing that by identifying the root note in each ego-net (implicitly present in this work – via the distance to centroid), one can also count cycles. Other examples are e.g., k-hop GNNs, Nikolentzos et al., ’20 with also theoretical results orthogonal to this work (showing that their GNN can regress certain graph properties)  and Ego-GNNs, Sandfelder et al.’20. Although there are differences between the above, the main idea is similar, therefore I would like to ask the authors to explain what makes their method significantly different. This brings me to my second concern.
2. **Architecture instantiation**: 
    -   The current arguments the authors used to differentiate their work from other related mainly boil down to architecture/implementation details (e.g., they write “unlike GNN-AK, they only propose to use a final root node embedding” and “can be viewed as a special case of GNN-AK, which only computes a context embedding (one of three types of embeddings GNN-AK uses)”), but their theoretical results do not seem to advocate for the necessity of these architectural choices. 
    -  Further, more ad hoc choices that do not seem to result from the theory are presented later in the paper (3 types of embeddings, gating mechanism with the distance to centroid, etc.). This begs the following question: What is the actual reason for the arguably good empirical results? Is it due to the improved expressivity or due to engineering?
    -	Also, note that some of the choices of the authors (random-walks to extract the subgraphs, dropout on the ego-nets) introduce randomness in the algorithm which (1) sacrifices permutation equivariance (which is not necessarily bad), but (2) improves expressivity (e.g., see related works that use random features or other randomized algorithms for GNNs), which might be also a confounding factor.

3. **Theory**: 
   - The theoretical results up to Corollary 3.1 are similar to previous work (e.g., Bouritsas et al., arxiv’20, Bodnar, Frasca, Wang et al., ICML'21, Bodnar, Frasca et al., NeurIPS'21 and others). Unfortunately, the bar has been set higher in research on GNN expressivity, since currently, most architectures that are proposed enjoy these properties (more expressive than 1-WL, no less expressive than 3-WL – shown by counterexample), hence in order for the theoretical evidence to be convincing, in my opinion, further arguments are required (e.g., substructure counting, or graph property prediction - possibility/impossibility results). 
   - The authors do provide a novel theoretical argument in Theorem 4, which is good, however, its practical consequences are not clear to me (I don’t understand the following sentence: “This opens a future direction of generalizing rooted subgraph to general subgraph (as in k-WL) while keeping number of subgraphs in $O(|\mathcal{V}|)$.”). 
   - More clarity is needed in Conjecture 1 with respect to the magnitude of $k$. If it is $O(n)$, then this resembles the reconstruction conjecture (Kelly, 1957), if it is $O(1)$, then this would imply a polynomial-time solution to isomorphism, hence it is unlikely to hold. 
   - Can you theoretically compare ego-net enabled GNNs with other modern GNNs, such as the ones that use substructures or other structural properties to improve expressivity? Note that these methods can also distinguish 3-WL failed graphs, without necessarily resorting to an algorithm of higher computational complexity during training, which is the condition of your Theorem 3. 

**Other comments**:
- **Experiments**:
   - What version of GNN-AK do you use in Tables 1 and 2? Is it the vanilla GNN-AK or it contains the instantiation details mentioned in the previous sections?
   - Minor: I suspect that this method might suffer from scalability issues when dealing with denser graphs than those you tested on (e.g., social networks) since its complexity might grow with $O(n^2)$. Have the authors considered testing on this domain?
- The following claim in the intro should be relaxed:  “We also give sufficient conditions under which GNN-AK can successfully distinguish two non-isomorphic graphs.”. As far as I understood, this is based on a conjecture rather than a proven fact.
-  Theorem 4: (1) Notation clash ($k$ is now used for k-WL and $d$ for the num of hops of the ego-net) and (2) there are clarity issues in the proof.  I am not sure I follow the claim “and the rewiring of constructing its non-isomorphic counter graph has picked two edges that cannot be included by any k-hop ego-nets with k ≤ 4”. Is that a known fact from the original CFI paper? Maybe the authors would like to expand their explanations. Does this proof imply that with $k\geq4$ you might be able to distinguish two CFI graphs?

### --------------------- After rebuttal ---------------------
I have increased my score slightly, this time voting for weak acceptance. Please see my final comment for a justification, as well as the discussion with the authors for a detailed explanation of the remaining concerns.



summary_of_the_review: The main idea in this paper is simple, easy to implement and the empirical results are good. However, (1) this very idea is not that novel since ego-nets have been used in the past,  (2) most theoretical results are similar to prior work and do not make a particularly compelling case, while other works on ego-nets have gone further in that respect and (3) the multitude of engineering choices obscures the root causes for the improved empirical performance. Therefore, I am leaning towards rejection, but I would encourage the authors to clarify their position w.r.t. the above and make their statements more clear since it seems that ego-nets have good potential in terms of practical performance
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces a framework that can extend the expressive power and empirical performance of a base GNN by using an induced subgraph-based local aggregation method that substitutes the conventional multiset aggregation GNNs typically perform. The authors provide theoretical analysis for this framework, study its scalability for practical applications, and presents good empirical results. 
main_review: # Strengths 

- The motivation behind the proposed method is very clearly described in the introduction. 
- The high-level insights described at the beginning of Section 3 give a good overview of the paper before describing the details. 
- The proposed subgraph 1-WL procedures are a nice tool for analyzing the expressive power of the proposed models. In particular, I like the idea of defining an isomorphism test that relies on WL as a subroutine (i.e. the 1-Subgraph-1-WL*) and thus "uplifting" the expressive power of WL.
 - The theoretical analysis performed on top of these newly proposed isomorphism tests contains useful results. Although some of the results are relatively obvious, they help provide a description of the capabilities of the proposed framework. 
- In particular, I think Theorem 4 is the most original since it manages to establish a connection with all the tests in the k-WL hierarchy for $k \geq 3$.  
- The complexity analysis section is compact and clear. Like other recent papers, the proposed method manages to benefit from cutting through the k-WL hierarchy by achieving more advantageous complexity tradeoffs compared to k-WL based approaches. 
- I like that the authors have taken a careful approach with the subgraph sampling rather than simply implementing a naive sampling approach. The proposed sampling takes into account how the nodes are covered by different subgraphs and the method itself is adapted to avoid potential complications at testing time when no sampling is used.
- The experiment in Table 1 is very nice and clearly demonstrates the claimed capacity of the framework to "uplift" existing GNNs. It is also encouraging that the framework brings improvements irrespective of the base GNN that was tried. 
- The results for the real-world experiments are good. Although, some stronger baselines could have been included (see the next section) 
- The ablation study in Table 4 provides a useful overview of the tradeoff between computational expenses and performance. 

# Weaknesses 

- There seems to be a discrepancy between the high-level view of the GNN-AK model provided in Equation (2) and the actual implementation in Equation (6). The context representation from Equation (6) is based on subgraphs rooted at neighbours of node v and therefore it might be based on information that is outside the subgraph of v, thus becoming misaligned with Eq(2) and the proposed subgraph WL equations. 
- The subgraph sampling strategy is often referred to as a sort of Dropout for GNNs. However, the evidence that this subgraph sampling strategy improves generalisation in any way is weak. Table 4, which is studying this does not provide any standard errors around the provided scores. This is particularly important as more subsampling induces more noise into these measurements. It is therefore very difficult to assess the statistical significance of these scores. Even ignoring the lack of error bars, on ZINC no level of subgraph sampling produces improvements in the reported MAE compared to the full GIN-AK and in the case of CIFAR-10, the differences are far from being scientifically significant. 
- While I understand the positives that subgraph sampling brings, training-time computationally improvements are generally not so useful. Ideally, one would like to move as much of the processing from inference time to training time because that is the main setting where latency and computational constraints start to matter. However, the model does need to use all the subgraphs at inference time. 
- A stronger baseline for ZINC and MOLHIV exists: *Weisfeiler and Lehman Go Cellular: CW Networks (NeurIPS 2021)* (https://arxiv.org/abs/2106.12575). In fact, this work is also particularly relevant for this paper since it is also relying on induced subgraphs for "uplifting" existing GNNs, but it does so in a different way. 

# Minor weaknesses 

- In the introduction (last paragraph of page 2), the paper claims that sufficient conditions are derived under which GNN-AK can distinguish two graphs. This is misleading because these sufficiency conditions are only conjectured on page 1. While some empirical evidence is provided in favour of this conjecture, it does not represent a definitive result. 
- It is unclear to me why Conjecture 1 is a conjecture and not an actual result. On a first look, it seems rather immediate that the assumptions of the Conjecture imply distinguishability (which doesn't mean that is indeed the case). What I am trying to say is that there should be at least a brief description of the difficulties surrounding the proof of the result and what the main impediments are. 
- Nit: In Table 2 it is not immediately clear which numbers correspond to the outer vs inner loop. I suggest reformatting the table to make this more clear. 
summary_of_the_review: The strengths of the paper outlined above generally outweigh the weaknesses, so I am therefore recommending the paper for weak acceptance for now. I am looking forward to the discussion period and I am willing to change my score once my points are addressed. 

EDIT: I have raised my score to 8.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes GNN-AK, a framework that can use GNN as a kernel to encode local features. It generalizes the local neighbour aggregation in Massage Passing Neural Networks (MPNN) from a star-like pattern to a more flexibly defined subgraph. The paper also provides theoretical support that shows the superiority of the proposed method to 1&2-WL in terms of expressiveness.  The experimental results demonstrate that the proposed method outperforms other SOTA baselines on 7 different datasets.
main_review: Strengths:
1. The proposed GNN-AK framework is novel for uplifting the expressiveness of GNN. It is an interesting idea to use GNN as a kernel on the induced subgraph. The design for both the GNN-AK layer and subgraph sampling are reasonable. 
2. The proofs of theorems appear to be correct.
3. This paper provides a comprehensive experimental study, including both qualitative analysis and quantitative results, to show the effectiveness of GNN-AK framework. The ablation study shows that each component in the framework works well.

Weaknesses:
1. This paper didn’t explain how it gets d_{i|j}^{(l)} from distance-to-centroid. The Sigmoid function was used to combine the D2C feature.  It is counter-intuitive if a node with a larger D2C gets a higher weight during aggregation. It would be better to provide more details on this.
2. The dataset statistics are missing.
3. What would be the performance of the proposed method when a different way of combining the centroid, subgraph, and context encoding is used? 
4. Some recent SOTA methods are missing:
Bodnar, Cristian, et al. "Weisfeiler and lehman go cellular: Cw networks." arXiv preprint arXiv:2106.12575 (2021).
Ying, Chengxuan, et al. "Do Transformers Really Perform Bad for Graph Representation?." arXiv preprint arXiv:2106.05234 (2021).

summary_of_the_review: This paper puts forward a novel framework that can easily plug different kinds of GNN and improve the expressiveness. The proofs and experimental results well support the proposed method. Some concerns are listed above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper deals with supervised learning with graphs, specifically graph-level tasks. The paper proposes an algorithm to overcome the expressive limits of the standard GNNs, which are upper-bounded by the 1-WL. The main idea of the paper is to, for each node v, extract the subgraph induced by nodes of at most distance k to node v, and then deploy a GNN on top of each of these subgraphs. Further, the authors study the gains of the expressive power of this architecture compared to the 1-, 2-, 3-WL, and k-WL.  

Moreover, the authors propose a subgraph sampling strategy to speed up the computation. 

The proposed method is evaluated on large benchmark datasets, mostly stemming from the molecular domain, reporting good performance boosts compared to standard GNN architectures.
main_review: **Strengths**
1. Simple approach
2. Good experimental results 
3. Good cover of related work 

**Weaknesses**
1. Limited selection of benchmark datasets used, e.g., large-scale graphs from OGB and graphlearning.io missing
2. Theoretical statements for 2-WL are misleading. They simply consider the weaker version of the 2-WL, which is known to be equivalent to the 1-WL (see, e.g., https://arxiv.org/abs/2104.14624). This should be clearly stated in the main paper.  
3. Proof of Theorem 3 is not sufficient.

**Remark for Theorem 3**
The prove seems to show that there exist pairs of graphs 3-WL cannot distinguish but their architecture can. The proof is not rigorous enough and of a very handwavey nature. **However**, it does not show that their architecture is always at least as powerful. This also has implications for Corollary 3.1. 

**Remarks**
1. "Leman" is the preferred spelling, see https://www.iti.zcu.cz/wl2018/pdf/leman.pdf
2. You might also want to cite (Morris et al., 2019) when mentioning the relationship of 1-WL and GNN, see also https://arxiv.org/abs/2104.14624 for a comparison of the results  
3. The statement that 1-WL can distinguish almost all graphs needs more context. The result depends on the sizes of the graphs. 
4. In  Section 2 you might want to discuss 
- https://arxiv.org/abs/2010.01179
- https://arxiv.org/pdf/2101.10320.pdf (also extracting k-hops subgraphs)
5. In Section 3.1 you should use notation for multisets, e.g., {{ ...}}
6. In Section 3.2, you should state the k needed for the results. 
7. In Section 4, the description of Emb is clumsy and hard to parse
8. The complexity analysis is not very meaningful. You must derive the cardinality V_U and E_U, which, in general, will depend exponentially on k. 


summary_of_the_review: The paper proposes a simple and meaningful architecture to enhance the expressive power of most standard GNN architecture. 
The experimental results are promising, however, the authors only consider a limited set of benchmark datasets. 

However, there are some problems with the theoretical contributions, see above.
review_title: null

Meta-review: In standard message-passing GNNs (MPNNs), one step at any node u involves receiving state/embedding information from all of u’s neighbors, and then updating u’s state as a function of these messages and of u’s own current state. Thus, the communication pattern at every step is that of a star topology (a graph with u at its “center”, and with u connected to all its neighbors, and with no other edges). However, it is well-known that the expressive power here is bounded by that of the 1st order Weisfeiler-Leman isomorphism test (1-WL). This paper then takes the natural step of generalizing the star topology to more general ones (e.g., k-hop egonets, the subgraph induced by the nodes of distance at most k from u). It is shown that this framework is strictly more powerful than 1-WL and 2-WL (however, as pointed out by a referee, this is actually a weaker version of 2-WL that is equivalent to 1-WL), and is at least as powerful as 3-WL. Subgraph-sampling approaches that improve efficiency are also introduced. It is shown that this method beats the SOTA for some number of well-known graph-ML problems.

It looks like this paper has a very strong overlap with the NeurIPS 2021 paper "Nested Graph Neural Networks" (https://openreview.net/forum?id=7_eLEvFjCi3). Both papers use rooted subgraphs (k-hop ego-nets) to replace the k-hop rooted subtrees in traditional GNNs, and both use a base GNN over the rooted subgraph to compute a subgraph representation as the node representation while pooling the node representations into a graph representation. Both papers claim to outperform 1-WL in expressive power; both use distance to center node in order to enhance subgraph node features. The authors are urged to compare and contrast the two papers in the camera-ready version.
Decision: Accept (Poster)