Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: Graph Representation Learning, and specifically GNNs have generated tremendous over the past few years. In this work, the authors propose a framework, which builds on recent works on subgraph enhanced (aggregated) GNNs to obtain expressive representations.  Here, the authors firstly propose a unifying framework (which ties most recently proposed works), and secondly introduces a way to 'learn to sample' from the subgraphs leveraging techniques which can back-propagate through discrete distributions.
strengths_and_weaknesses: Strengths:
1. The idea to learn using data to 'select' subgraphs is interesting
2. The paper is largely well written and easy to understand.
3. The propositions and theorems appear valid


Weaknesses:
1. The results are relatively worse on the ZINC dataset than ESAN, and comparison is not performed on other datasets performed in comparable works (e.g. MUTAG, Proteins, PTC, etc). Is there an underlying reason - which I may have missed.
2. Per, section 5 (and appendix F.1), sampling subgraphs - the authors use unordered subgraphs rather than the proposed theoretical strategy. Can you provide results atleast on a sample synthetic result, for the proposed framework?







Post Rebuttal Updates:

Thank you very much for the rebuttal authors -- for adding the  ordered experimental results, justification for the smaller datasets, etc. After reading the response and the other reviews (and corresponding replies), I am happy to increase my scores.


Best,

Reviewer 5AyY
questions: 1. Please provide timings for other datasets as well.
2. Page 4, line 161 - do you mean Union? or both strategies work? What do you see in practice - performance wise?
limitations: Yes, the authors do talk about computation costs and ways to scale them down in practice.
review_title: null

final_score: 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.
review_content: summary: This paper provides a unifying framework for a variety of Graph Neural Networks (GNNs) that have been recently introduced and are based on a common principle: providing to the network subgraph information in various forms. The authors show that most of the existing works can be expressed via the so called Ordered Subgraph Aggregation Network (OSAN) framework, where one runs a GNN (or a 1-WL algorithm) over a marked/anchored version of the initial graph. In particular, first a k-vertex tuple is selected as anchor, which in turn induces a k-ordered subgraph. Secondly, each vertex in the graph is initially coloured by computing the atom type (similar to isomorphism type) of the subgraph induced by the vertex along with the k-tuple anchor - this is contrary to classical WL where all vertices initially have the same colour. Then a conventional GNN (or 1-WL) is run over the graph. The processes is repeated for all possible k-tuple anchors and finally the results are aggregated into a final representation. 

Using this general framework, the authors prove that k-OSANs form an hierarchy and, by using some specific graph constructions, they have been able to contrast this hierarchy with the corresponding k-WL. In particular, they show that k-OSANs are incomparable with k-WL, but strictly less expressive than k+1-WL. They further proceed by showing how k-OSANs can simulate popular subgraph enhanced GNN architectures, and discuss the potential consequences of their theory in characterising the expressive power of these specific architectures. Finally, given the high computational complexity of k-OSANs, they propose a practical implementation, where only a handful of anchor subgraphs is used, and their selection is done in a data-driven manner by sampling from a learnable subgraph distribution using the perturb-and-MAP framework. The proposed algorithm is evaluated experimentally, where it is shown in several datasets that data-driven sampling can provide benefits against sampling uniformly at random, while providing improvements against non subgraph-enhanced GNNs.
strengths_and_weaknesses: To begin with, I believe that the present manuscript provides an important contribution to the GNN community and will be of interest to various readers working with GNNs and exploring their expressive power, as well as to readers working on graph theory and graph isomorphism. However, I found the presentation unsatisfactory - in my opinion the paper is hard to follow (densely written and notation heavy) and has several clarity issues, which unfortunately now might limit its impact to a small audience. Moreover, the experimental section could be improved, mainly to make the data-driven subgraph sampling more convincing. In detail:

# Strengths
- Subgraph-enhanced GNNs have become one of the most popular families of GNN architectures in the last couple of years. However, many of these innovations have been proposed almost in parallel and this has created a confusing landscape of methods and it was unclear how to compare them. What I liked the most about this paper is that it brings order to this spectrum of methods, paving the path for future work within this framework.
- Secondly, the theoretical results are general and intuitive (please see below for my reservations) and clarify the limitations of subgraph-enhanced GNNs.
- A very appealing aspect of the method is that it relies on 1-WL, which implies that vertex representations are the ones that get updated instead of k-tuple representations.
- Subgraph sampling has been also a long standing question for these and related architectures (such as the ones that use subgraph features, e.g., GSN, Bouritsas et al., TPAMI'22 and F-MPNNs, Barcelo et al., NeurIPS'21), therefore proposing a learnable algorithm is definitely towards the right direction (also see below for some reservations).

# Weaknesses
## 1. Exposition and Clarity
### Theory
- The exposition of the theoretical results needs to be improved. Right now, the authors do not provide any intuition or proof sketches in the main text, while the proofs are complicated (in some cases based on intricate graph constructions along the lines of the CFI gadgets), which will make it very hard for future readers to obtain an actual understanding of the presented theory. For example: 
   - Proposition 2 and Theorem 3 are important results because they settle an open question regarding the comparison of k-WL with subgraph-enhanced GNNs, but unfortunately are poorly explained, while the proofs in the supplementary material are confusing in certain parts. Moreover, there are some small inconsistencies between the main paper and the proofs, e.g. Theorem 3 says that k+1-OSANs can distinguish non-isomorphic graphs that k-OSANs deem isomorphic, while the proof in the supplementary (Theorem 10) claims a strict inclusion, which is a stronger result. Also, the proof is very brief and points to a theorem in a different paper without adding sufficient explanations. Could the authors provide a more extensive explanation in the rebuttal so as to be able to validate this claim? Also, the chain of arguments to prove these two claims in the supplementary is tangled. Could the authors clearly explain the chain of arguments in the rebuttal and in the main paper?
   - I am a bit confused by section E.3. supplementary material. How are these results different from section D? In the title the authors mention a comparison between the vertex-subgraph k-OSWL variant and k-WL, yet in the proofs below they mention k-OSWL. Moreover, I think I am missing something in Lemma 23 (which perhaps I am also missing in section D): you mention that k-OSWL is strictly less expressive than (k+1)-WL and that (k+1)-OSWL distinguishes graphs that (k+1)-WL deems isomorphic. However, I don’t see why this immediately implies that k-OSWL is strictly less expressive than (k+1)-OSWL, since there might be graphs that k-OSWL distinguishes, therefore also (k+1)-WL, but are deemed isomoprhic by (k+1)-OSWL.

### Gradient computation
- The presentation of the I-MLE is also quite elusive. I believe the authors should provide clarifications and improve a lot the exposition in this part, first because this is probably going to be knew to the interested readers from the GNN community, and second because data-driven subgraph sampling is a novel contribution that can be potentially impactful, but currently doesn’t do its complete justice.
- Furthermore, it is not immediately clear to me why the authors chose this specific parametrisation for the subgraph distribution. Another potential and simpler choice could have been to iteratively sample without replacement k vertices M times (one for each subgraph) and then estimate the gradients with a variant of the REINFORCE algorithm (as in Bouritsas et al., NeurIPS'21). Another idea that comes to my mind is the Plackett-Luce distribution (M times, one for each subgraph), as in the NeuralSort (Grover et al., ICLR'19) or more recent ones. Note that this can be made deterministic (essentialy sampling the top-k vertices with the highest scores) and therefore the overall pipeline can become permutation invariant, contrary to the current version, which is permutation sensitive due to sampling. Is there any particular advantage of the algorithm chosen?

## 2. Experiments:
I believe that the experimental section should be extended and improved in some respects:
- First: it would have been useful to include in your tables more baselines, and especially baselines falling under the k-OSAN framework (e.g., as with ESAN). The results in Table 2b raise some concerns that perhaps the data-driven subgraph sampling is not yet at a level that can be reliably used in practice, so more extensive comparisons and/or an explanatory discussion with the potential reasons for this and remedies, would help. Also, note that the performance of the current baseline is not immediately visible in the tables.  
- Second: even though subgraph sampling is learnable, the authors still have to make several design choices that seem arbitrary, i.e., the number of subgraphs to sample and the number of vertices per subgraph. Can the authors discuss any potential strategies to circumvent ad-hoc selections? An ablation study in a controlled setup, showing how the performance changes when increasing the number of subgraphs and the number of vertices would have been very helpful. 
- Another potential interesting experiment would be to select a more informative baseline, than the random one, for subgraph sampling, e.g., according to certain subgraph properties that either (1) are potentially related to the task at hand, or (2) can break graph symmetries and make the vertices more identifiable.
- I found it a bit puzzling that the authors experimentally used unordered subgraphs, although all the theoretical analysis refers to ordered subgraphs. If I am not mistaken, unordered subgraphs are sufficient to simulate the architectures from previous works, but I am wondering if the theoretical results comparing k-OSANs to k-WL also hold for unordered subgraphs.
- Subgraph sampling is not permutation equivariant w.r.t. the subgraphs. The authors mention in appendix C that they use an auxiliary loss to prevent degenerate solutions, but I believe more emphasis should be given to this and this part should be ablated.
- The tables are not quite self-explanatory. What are the # and #Subg. Columns? Also, I think it is going to be helpful to explain how the operation used is implemented within the k-OSAN framework (I understand that vertex deletion means that the anchor subgraph has n-1 vertices, while vertex selection means a 1-vertex subgraph, is that correct?).  
questions: - Since the “upstream model” is a GNN, I can imagine that the end-to-end model will inherit its expressivity issues. Although I understand that the downstream model will do all the heavy-lifting, I am wondering how important is the upstream  model, i.e., what kind of subgraphs does it select? A discussion here would be useful.
- Regarding the terminology isomorphism type and atomic type: In several papers on k-WL and equivalent higher-order GNNs the term isomorphism type is used to refer to order-preserving bijections between k-tuples (e.g., Chen et al., NeurIPS’20). Perhaps using the term isomorphism class to refer to the equivalence class induced by isomorphism might be more appropriate? Also, I am a bit confused by the atomic type definition: this is not order preserving, right?
- L260: I found the explanation of the ordered subgraph encoding a bit confusing. Could the authors elaborate more on what they mean by position/rank?
- L331: “In addition…ease of implementation”: I am not really sure what this sentence refers to. What are the “initial features for the subgraphs”?

### Minor:
- L179: perhaps use a different symbol for the two different embedding functions (UPD) to avoid confusion.
Why does the selection vector $\pi_{v, \mathbf{g}}$ depend also on the vertex and not only on the subgraph? I noticed that further down in the text this is instatiated with a subgraph only dependence.
- Section F.2 SM - id GNNs: It is mentioned that id GNNs can count cycles and this is consistent with the 2-WL expressivity upper bound. Probably this is just a subtle detail, but 2-WL can count cycles up to 7 vertices - perhaps a clarification is needed here.

limitations: - A more elaborate discussion on the limitations of the data-driven subgraph sampling and on the choice of the subgraph parameters would be helpful (see above).
- No immediate negative societal impact
review_title: null

final_score: 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.
review_content: summary: The paper proposed a subgraph based GNN approach, k-OSAN. The authors showed that increasing subgraph size always increases the expressive power, and k-OSAN is strictly less powerful than the (k + 1)-WL while being incomparable to the k-WL. To circumvent random or heuristic subgraph selection, this paper devised a data-driven variant of k-OSANs. In experiments, the authors verified that data-driven subgraph selection is superior to previously used random sampling in predictive performance. Recently, subgraph GNN is proposed as a promissing approach, and in general, this is a paper of strong theoretical results.
strengths_and_weaknesses: Strength: A new subgraph GNN model with theoretical expressive power guarantee.
Weakness: Though this paper has strong theoretical results, the experiments is kind of weak. The auhors only showed the data driven approach is better than the random approach, but it is not clear how the proposed subgraph GNN compares with other GNN implementations, given the introduced addtional complexity of proposed method.
questions: 1. The paper in its current form is hard to follow, and I suggest the authors can first have a high-level overview of the proposed approach and then going into the detailed mathematical formulations.
2. It is proved that k-OSAN has a higher expressive power, can the authors provide some empirical results? even on some synthetic data.
Minors: Please define t(g) at line 154
limitations:  The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: 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.
review_content: summary: This work develops a general family of subgraph-based GNN architectures that generalizes and unifies many of the recently proposed subgraph-enhanced GNNs. $k$-OSANs are based on message passing on all ordered $k$-vertex subgraphs of an input graph. Expressive power of this architecture is analyzed, showing that $k$-OSANs incomparable to $k$-WL, but always less powerful than $(k+1)$-WL. Further, a data-driven subgraph sampling procedure is developed.

strengths_and_weaknesses: Strengths:
1. The theoretical results are interesting. In particular, the upper bound of $k$-OSANs (and hence many other methods) by $(k+1)$-WL is a nice result.
2. That the architecture uses message passing, and can independently process subgraphs is great for efficiency; future works can probably take advantage of this even further.
3. The use of ordered subgraphs in an overall permutation invariant architecture is pretty novel and smart.
4. The data-driven subgraph sampling seems mostly reasonable, and it tackles the important problem of how to get good performance without using all subgraphs / a uniformly sampled subset of the exponentially many subgraphs.

Weaknesses:
1. Experimental results are not that strong. Most comparisons are between random sampling and data-driven sampling. Assuming you use edge features on ZINC (is this true?), the results are not great, and the methods get outperformed by some message passing GNNs.

**Note:** I have not checked the proofs of expressive power, and thus I have not read much of the Appendix.

questions: 1. I think it is worth explicitly stating that your theoretical results give upper bounds on the expressive power of many existing methods, say at the very end of Section 3. This is a nice result!
2. At the end of the related work (line 84), it would be better to say that the above works *mostly* "do not study the approaches" expressive power beyond 2-WL. For instance, some works like the reconstruction GNN (Cotta et al, 2021) demonstrate ability to compute functions on graphs like cycles, that 2-WL cannot count (beyond a certain size). Also, the edge deletion ESAN (Bevilacqua et al. 2022) goes past 2-WL on strongly regular graphs.
3. Could you clarify, what is the O(n+ klog k ) algorithm for computing the MAP of the subgraph sampling distribution for ordered subgraphs?
4. It's worth mentioning the diversity loss (Appendix C) used in I-MLE sampling in the main paper.
5. The MAE numbers reported here for Alchemy and QM9 appear to be in different units than that of other work. In particular, these are much larger. Can you clarify how to compare these to that of other works?


limitations: Unless I missed some things, this work does not discuss limitations much at all in the main paper. I also do not see this in the Appendix, though the Appendix is long, so difficult to search.
review_title: null

Meta-review: metareview: The paper considered subgraph-enhanced graph neural networks that provably boost the expressive power of standard message-passing graph neural networks. It proposed a theoretical framework for studying the expressive power of these GNNs and the relation to the Weisfeiler-Leman hierarchy and extended the existing results. It then addressed the limitation of subgraph sampling in existing methods, exploring different sampling approaches using state-of-the-art data-driven methods. Empirical results showed data-driven architectures increase prediction accuracy and reduce computation time.

The work has made novel and solid contributions: theoretical analysis of the expressive power of subgraph-enhanced GNNs, data-driven approaches for sampling subgraphs, and strong performance of the proposed approaches. The authors have addressed well the comments by the reviewers during the response period and strengthened the work.

confidence: Certain
Decision: Accept