Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: **Update following author response and reviewer discussion:**

I would like to thank the authors for providing a response, and in particular for providing further justification for their injectivity assumption. However, the main concern remains the lack of empirical validation, even on toy examples, showing that (or whether) the derived theory here goes beyond a hypothetical thought exercise and can be implemented in practice. It shouldn't be difficult to provide such examples, assuming the proposed approach does indeed work as indicated by the theory developed here, and without such examples, the paper seems rather incomplete. Therefore, unfortunately, my score remains unchanged at this point, although I would like to encourage the authors to keep pursuing this direction.

---

**Initial review:**

This manuscript discusses a hypothetical pooling approach that recursively applies a generic (unspecified) GNN to subgraph constructed from local neighborhoods of a certain radius (or sequence of them, applied in successive applications of the recursion) in an input graph. The main motivation set out by this work is to prove that, under some assumptions (which may or may not be realistic) on the applied GNNs, this pooling strategy is sufficiently expressive to admit a configuration of weights that would enable counting subgraphs of certain size in the main input graph. The authors provide theoretical study of this expressivity and prove the capability to count subgraphs in an existence sense. That is, they show there exists some function that can be written in the form of their proposed pooling architecture (with sufficiently rich architecture between pooled levels) such that non isomorphic subgraphs would necessarily be distinguishable by some of the extracted features, and thus counting equivalency classes of these features would provide the desired subgraph counting. The authors also provide other results showing functions written in the form of their pooling based architecture have reasonable complexity of node operations, and providing some lower bound on the capability of any GNN approach to count subgraphs, thus putting their theoretical results in context.

The proposed pooling approach itself is rather straight forward, but intuitively makes sense. Given an input sequence of radii, at each iteration of the recursion each node in the graph constructs a subgraph over nodes that are within the current considered radius in the sequence. Then, by recursion, the same approach is applied to each of these subgraphs, with the remainder of the radii sequence (subsequent to the current one) being passed on, until reaching only a single radius or a single node as stopping conditions. Given the resulting (sub)graph features for each node, these are combined with the input node features via generic functions parametrized by unspecified neural networks (written as an MLP with arbitrary architecture for the sake of presenting pseudocode in the supplement) that are supposed to be injective, when carefully examining the derivation and proofs in the supplement. Finally, the resulting node features are aggregated together (again, via generic functions modeled as unspecified neural networks that are supposed to be injective, this time up to node permutation) into graph features that provide a readout to be returned as the output of the network to outer levels of the recursion, or finally to the general output of the network.

It seems to me that the main theoretical results here crucially hinge on the injectivity assumption, and yet the authors make no attempt to verify that any existing GNN indeed provides an architecture that satisfies their assumed conditions. More importantly, they do not provide any empirical evidence that the approach described here is viable in practice. There is no implementation or demonstration of this approach, even on toy examples, let alone benchmarks on graph datasets. There is also no discussion on the impact of the proposed pooling on the training of the resulting RNP-GNN. It is not clear to me that this approach is feasible to apply in practice, beyond a hypothetical thought experiment. Therefore, while this line of research seems like an interesting direction, I find it somewhat lackluster and do not thing it is mature enough at this stage to be accepted for publication.

Finally, as a minor remark, the writing here seems somewhat rushed, with several typos and unclear phrases. Some examples:
- Equation (4) should probably have "RNP-GNN" rather than "RNN-GNN"
- The last line before section 5: "Appendix ??" missing a proper reference.
- Page 6: "sincethe" missing a space between "since" and "the"
- Page 7: "used for for aggregation" has a duplicated "for"
- The last sentence of section 5 (right before section 6) should be rephrased - I couldn't decipher it grammatically.
There may be more that I missed, but the paper and supplement would benefit from some additional proofreading.
review_title: Interesting idea, with nice theoretical results, but seems rather hypothetical with no demonstration that the theory can feasibly be implemented and no indication it really has impact in practice

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: 
The goal of the paper is to show that GNN's (without exponential computational complexity) can be constructed with the ability to count subgraphs. To this effect, the authors propose a principled neighborhood pooling strategy and theoretically characterize their expressive power - with respect to other models proposed earlier. More specifically, the authors propose a recursive neighborhood pooling strategy which characterizes graphs based on the counts of subgraphs . Furthermore, they show that if the tuple of recursion parameters are chosen well, their proposed model can capture all induced subgraphs (universality) of sizes smaller than the first value in the tuple of recursion parameters plus 1 - and show a relationship to the reconstruction conjecture (Kelly et al. 1957). The authors also provide a bound on the number of iterations required to learn the expressive representations.

Pros:
1. Theoretical contributions which provide a strategy to learn expressive representations with the ability to count subgraphs and distinguish graphs based on the same.
2. Proposed model provides a strategy to perform a tradeoff on the exponential nature required to compute sugraphs in earlier works.
3. Comprehensive literature review

Concerns:
1. The theorems all state that, there exists a set of recursion parameters, etc - but do not provide a computationally tractable strategy to determine the same for real world graphs (e.g. diameters of the graph > 15) - or a strategy to determine the vertex covering sequence if it exists - which is the basis for theorem 1(among all permutations of the set $\mathcal{S}$ - without looking over all permutations - this can explode even with subgraphs of size 10 for instance).
2. Lack of any experimental evidence to empirically show gains - While the authors explicitly say that their work is theoretical, they could have included synthetic experiments to demonstrate the same- given that the Local Relational Pooling,  k-WL works and k-IGN (the latter two, which are exponential) works have experimental results. 

If the concerns are addressed, I will be happy to update my scores.
review_title: Review of Recursive Neighborhood Pooling for Graph Representation Learning

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper has a fully theoretical flair while proposing a novel and seemingly efficient procedure to recursively compute the higher-order (i.e. more than 1-hop) neighbourhood of a node that are used for learning discriminative graph embedding. The paper contributes with the model above (RNP-GNN) and by providing a proof of its representational power and a general theorem supplying an information theoretic lower bound on the complexity of GNNs that can count induced substructures.

To the extent of my knowledge the recursive neighbourhood construction procedure presented in the paper is original and it is based on solid graph-theoretic concepts. A proof of the asymptotic complexity of the approach is provided in Section 6, suggesting that the approach can yield to increased representational power at minor computational costs. These results are derived under a sparsity assumption which is not completely clear how much it would hold in practice. In particular, I am not sure whether the sparsity constraint should hold on average in the graph or if the presence of a single node infringing the constraint will induce an exponential growth in complexity. I am thinking in particular to social graphs where hubness might become an issue if the second is true. I would like to read some elaborations as concerns this specific point. 

The theoretical results appear solid and the proof well-constructed although, admittingly, I have not checked the proofs in Appendix in detail. I do have one question as regards the construction of counting substructures proof. Since it entails leveraging vertex covers, does it require this to be minimal or any vertex cover would suffice? Is there any change if the cover is not minimal?
Concluding, while the paper has certainly good quality theoretical contributions, it lacks an empirical analysis (even a small one, given the theoretical nature of the problem), which would have made the paper claims more convincing. In particular, since much of the results hang on the tradeoff between representational power and efficiency, one would have liked to see an empirical proof of such excellent tradeoff, possibly in graphs of different nature (i.e. bio-chemical and social, given that they tend to have considerably different connectivity patterns). The short but informative empirical analysis in the paper by Murphy et al, ICML 2019 is an excellent example.

One final remark: the paper, while generally well written, has misprints here and there which can be easily spotted by careful proofreading. Not listing them here, but they should be taken care of.

=========== POST REBUTTAL

The rebuttal is very helpful and "to the point" in clarifying the issues that I had raised as concerns the impact of the assumptions taken in the theoretical proofs. The fact that complexity hinges on average node degree and that any vertex cover sufficies for the proof confirms that the approach put forward in the paper might work out of the theoretical box. The Authors also suggest that the theoretical framework can be translated to a running model with a certain ease and that, in fact, its practical implementation and empircal assessment is on the way. Which brings me to the key point in my assessment. I am convinced there is value in this work and in the theoretical contribution in the paper.  I am not convinced that this paper can have a strong impact without an empirical validation. As I have underlined in my review, there are several related works in literature, with a similar theoretical flair which, nevertheless, provided at least a simple empirical validation. I believe that this paper shold do the same: it would be stronger, more complete and with a higher potential to influence the community. As it is, this is a borderline paper (leaning on the positive side). 


review_title: Theoretical results on representative power of graph neural networks leveraging an efficient recursive procedure to assemble higher-order neighbourhoods of a node

final_score: rating: 6: Marginally above acceptance threshold
review_content: The proposed paper seeks a theoretical possibility of counting the subgraph by a graph neural network. To this end, the authors proposed a recursive neighborhood pooling graph neural network and proved the express power of the model. The universal approximation results on a subgraph have been shown as well. Analysis of computational complexity shows the algorithm is much efficient than the known class of models that can count substructures.

The strength of this paper is the detailed theoretical analysis of the proposed method. The analysis has been taken from multiple perspectives: model complexity, computational complexity, and theoretic lower-bound on the class of the proposed method. The paper gives a new insight into measuring the representation power of graph neural networks through subgraph counting.

Although subgraph counting is an interesting problem from a theoretical viewpoint, the weakness of this paper is that it is not answered how relevant it is to real-world tasks and how successful it is. Since this is the first paper proposing a new way of measuring the express power of the graph neural network, it would have been much better if there's some discussion on this point.

review_title: Interesting work from theoretical perspective but without real world applications.

Meta-review: The reviewers agree that this is an interesting and promising paper, although it is on the theoretical side, without even satisfying toy examples to demonstrate its usefulness. This itself is not a fatal problem (ICLR can and should welcome theoretical papers), however including such experiments would significantly strengthen the impact of this paper, and make it more competitive with other ICLR submissions.
Decision: Reject