Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper introduced graph reconstruction theory to GNN area and use it to improve the expressiveness of GNNs with some formal theoretical proof. The theoretical framework is not tractable but the author proposed using sampling based method and combine with GNN to  approximate k-reconstruction neural network. Some experiments over synthetic datasets and OGB graph datasets show some improvement over existing message passing based network. 
main_review: 1. Originality: although the idea is not presented before, the k-reconstruction idea that views graph as a set of k-subgraphs has some connection to k-WL or k-GNN. As we know that each node in k-WL is a k-size super node which corresponds to a k-subgraph. And the k-WL algorithm over these k-size super nodes are permutation invariant which can be looked as implementation of the f_w function used in the paper. I wish the author provide more formal analysis to connect these two type of models, figuring out their difference and similarity. Nevertheless, from my end the presented k-reconstruction GNN is too complicated and is more like a toy for theoretical analysis instead of real-world useable model. 

2. Quality: the author provides a great literature review for expressiveness of GNN. The author also introduced the graph reconstruction theory in section 2. For the definition of reconstructible function, I wish the author can provide more insight of why introducing these defnitions in section 2. A trivial example of reconstructible function is a function that always output a constant representation for all graphs. In section 4 the author use these reconstructible function to characterize the expressiveness of k-reconstruction neural network, but before this I don't see any value of introducing these definitions. I suggest the author rewrite the section 2 part with giving some insight of why introducing these definitions from graph reconstruction theory. For section 3, the presented model looks like theoretical toy model to me. This is very similar to the relational pooling paper but I don't get the value of this model . The contribution of relational pooling is more like the universal approximation ability on graphs but this has been studied extensively. For section 4, the author provided several theorems to characterize the expressiveness of the designed k-reconstruction networks, however these theoretical results are not "tight" at all, most of these theorems just tell us that the k-reconstruction is not worse than GNNs. No amazing theoretical result shows that the k-reconstruction network achieves the best expressiveness (higher than k-WL/k-FWL). Also, the improvement on real world datasets are not much noticeable although it does show some ability in synthetic dataset. 

3. Clarity: In general the written is ok, but need some improvement to provide more insight in the flow to help reader understand the paper much easier. 

4. Significance: my impression is that the paper is more for theoretical analysis instead of real-world usage. I would like to see some more practical model that can make use of the author's analysis. The author did lots of approximations and it's really hard to know how much expressiveness left after these approximations. 
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposed several kinds of GNN models that integrate the representations of subgraphs to obtain graph representations.

First, the k-reconstruction NN is defined using the representation of a subgraph of size k for the input graph G. Under the reconstruction conjecture, the k-reconstruction NN is proven to be most expressive. 

Next, this paper defined the k-reconstruction GNN, which is made by specializing k-reconstruction NN by obtaining representations using GNNs. The computational complexity of a k-reconstruction GNN is exponential with respect to k. Therefore, we proposed a method to approximate it by sampling subgraphs. The relationship between GNNs and k-reconstruction GNNs is discussed. Concretely, the k-reconstruction GNN is not less expressive than GNN if k is not too small. Also, k-reconstruction GNN is not more expressive than GNNs when k is small.

Finally, the proposed k-reconstruction GNN was applied to synthetic and real datasets (OGB). This paper showed that the proposed model improved the accuracy of the proposed GNN compared to baseline GNNs.
main_review: ### Strength

- [S1] We can apply the k-reconstruction GNN to any GNN for graph prediction tasks (in the experiments, this paper used GCN, GIN, and PNA).
- [S2] The proposed model is provably no worse than GNNs in terms of expressive power.

### Weakness

- [W1] I would say that there is room for improvement in the organization of the paper.
- [W2] Also, I think there is room for improvement in the proof of mathematical statements.
- [W3] Existing research employed the idea of reconstruction theory for the theoretical analysis of structured representation learning. Therefore, I think the novelty of the paper in this respect is limited.

### Soundness (Do theorems and experiments answer research questions, assuming they are correct?)

- [So1] The research question of this paper is to explore the relationship between graph theory and graph representation learning (GRL). More precisely, this paper tried to create a simple, scalable, and expressive GRL model using reconstruction theory. For the following reasons, I think that this paper is an answer to the research question from a theoretical perspective.
  - [So1.1] The proposed k-Reconstruction GNN is not less expressive than the corresponding GNN (Theorem 1, 2).
  - [So1.2] When the true distribution satisfies the hereditary property, the proposed architecture can reduce the variance of the empirical loss (Theorem 3). However, it requires strong convexity assumptions about the loss function and the architecture.
- [So2] As for the experimental side, I have both positive and negative opinions.
  - [So2.1] The proposed model is effective in the synthesis and real datasets of the graph classification task (Table 1, 2).
  - [So2.2] Table 1 shows that vanilla GIN and GCN can recognize cycles to some extent and that the advantage of the reconstruction model is not large.
  - [So2.3] As for GIN and GCN, the proposed model has improved the prediction accuracy on the OGB dataset, demonstrating the empirical effectiveness.

### Correctness (Are derivation of theorems and experiments correct?)

- [C1] I think the statement and proof of the theorem are written informally. Therefore, it was difficult for me to verify its correctness. I would like this paper to define concepts more mathematically rigorously write the statement more formally.
  - [C1.1] For Proposition 1, I tried to give formal proof by myself, but I could not do so, and I could not verify its correctness. 
  - [C1.2] Definition 6, I did not understand what was meant by "give a unique representation to a graph sampled with probability 1-ε".
  - [C1.3] In Definition 6, ε-universal is defined for a distribution D on the graph. On the other hand, (ε, k)-universal is defined for the induced subgraph. Is this correct that (ε, k)-universal is defined for the probability distribution on a graph of size k, obtained by sampling the graph from D and then uniformly randomly sampling more subgraphs of size k from it?


**Novelty and Significance (Do the paper have novel points? If so, are they significant?)**

- [N1] When we consider representation learning for graph structures, it is natural to compute representations for subgraphs and aggregate them. The idea of using subgraphs in a graph for GRL has been used in Graph Homomorphism Network (GHN) [Nguyen and Maehara, ICML2020], Graph Substructure Networks (GSN) [19], and Structural Message Passing (SMP) [Vignac et al., NeurIPS2020]. However, this paper has novel points because the proposed method of this paper is different from these works in how we extract subgraph information.
- [N2] As pointed out by this paper, Shawe-Taylor [88] and Bouritsas et al. [19] used reconstruction theory to guarantee expressive power. Therefore, the novelty of the use of reconstruction theory for GRL is limited. On the other hand, this paper is novel because it pointed out the problems of these architectures from the viewpoint of computational complexity and proposes a model with reduced computational complexity.
- [Nguyen & Maehara, ICML2020] http://proceedings.mlr.press/v119/nguyen20c.html
- [Vignac et al., NeurIPS2020] https://proceedings.neurips.cc//paper_files/paper/2020/hash/a32d7eeaae19821fd9ce317f3ce952a7-Abstract.html

**Clarity (Is the paper clearly written?)**

- [Cl1] I would say that there is room for improvement in the clarity of the paper.
- [Cl2] I think there is room for improvement in the proof of mathematical statements.
- [Cl3] In addition, this paper introduced several similar concepts (k-Reconstruction NN, full Reconstruction NN, and Reconstruction GNN). It was difficult for me to grasp the relationship between them. So, I would like this paper to clarify the relationship between them more explicitly.

**Other Comments**

- [O1] In Theorem 1, with respect to which variable the order of $o(1)$ is written?
- [O2] Some model definitions have $n$ (e.g. $(n-1)$-reconstruction GNN). Is it assumed that such models accept only graphs of size $n$ as input?
- [O3] 2-WL is undefined. If it is to be used in mathematical statements, its definition should be clarified.
- [O4] In l.156--164 and Appendix C, existing results on graph reconstruction are presented. It is interesting in itself, but I could not understand how it is related to the model proposed in this paper. For example, does it provide background ideas for the proposed model? Or can we analyze the expressive power of the proposed model by these existing studies? 
- [O5] It was difficult to grasp the meaning of l.215--223 when I read it for the first time. This paragraph have what is done in this section and what is done in the Appendix in an interleving manner. It might hindered my understanding.
- [O6] Is it correct that Var in Theorem 3 is the variance with respect to both the probability distribution $P(G, Y)$ and the randomness coming from sampling a subgraph from $G$?
- [O7] In l. 910, I think it is better to write something like $\mu_k(G) = E_{H\sim \mathcal{G}_k(G)}[\mu(H)]$. Also, I think it is better to state explicitly that H is uniformly sampled from $G_k(G$).
- [O8] For Theorem 1, I want to discuss the condition of $\ell$ (or equivalently $k$) in more detail because if I understand correctly, it just borrowed from conditions of the existing studies. Can we think that l should be sufficiently small (specifically, $O(\log n/\log \log n)^{1/2})$)?


### Post-rebuttal comments

My main concern in the initial review comments was about the accuracy of mathematical statements. I asked them to the authors and they answered my questions properly. Taking them into consideration, although I keep my rating (5), I do not object to accepting the paper, providing that the authors improve the mathematical descriptions in the camera-ready version.

limitations_and_societal_impact: - [L1] The authors discussed the problem of computational complexity of k-Reconstruction NN in l.208.
- [L2] The authors showed the theoretical limitation k-Reconstruction GNN in terms of expressive power.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper uses principles of the reconstruction conjecture to devise powerful graph representations addressing the current challenges in graph representation learning. The authors first present a theoretical construction of reconstruction-neural-networks, which is impractical because a universal graph function is not learnable. They then construct an approximate k-reconstruction-GNNs, which replace the graph representation function with GNN layers. The authors also discuss the hierarchy of expressive power and the relation of k-reconstruction networks to GNNs expressive power. They show theoretical guarantees regarding the expressive power of the suggested model, observing that under some conditions, k-reconstruction networks can distinguish graphs that GNNs cannot and even 2-GNNs cannot. While under other conditions, the opposite is true. The authors conduct an extensive set of experiments showing the model’s ability to distinguish several types of structures GNNs cannot, and also conduct some experiments on real-world tasks.
main_review: 1. **Originality**

   The paper provides a novel combination of a classical conjecture from graph theory with graph representation learning. I find the ideas and theory presented in the paper interesting. 

2. **Experimental Evaluation**

   - The authors provide a wide dissection of the different configurations of the suggested method illustrating a boost in performance when used with common GNN backbones. 
   - The results on real-life dataset are ok. But the graphs the method is applied to are relatively small, which leads to item (3) below stating my concerns.

**Convergence and Generalization**

In the approximation of the k-reconstruction GNNs the authors resort to averaging over subsets of the k-decks due to the complexity reasons. My questions are:

**(a)** When using subsets of the k-decks, although the authors provide a theoretical justification in line 242, how does the subset sampling effect the convergence of the training? 

**(b)** Could the proposed method generalize well to large graphs? 



---
After reading the author's response and the other reviews, I still lean towards acceptance. Although empirical results are not exceptional, I believe the theoretical concepts and relations to reconstruction conjecture from graph theory are valuable and may lay ground for future advancements in GRL. I hereby keep my score unchanged. 
limitations_and_societal_impact: No societal impacts discussed
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper bridges ideas from graph theory and graph representation learning to propose a simple but theoretically backed-up strategy to increment the expressive power of Deep Graph Networks (DGNs).
The underlying idea should be that, by considering subset of a graph where some vertices are removed, it is possible to discriminate between graphs that would appear identical to the original DGN.

main_review: This is an example of a very good paper. It is well written and organised, the bibliography is wide and complete, and it guides the reader towards the main findings, giving a substantial contribution to the field of graph representation learning. Given the amount of work put in by the authors, most of which was relegated to the appendix, submission to a journal may have been more appropriate.
The synthetic experimental part seems solid, but the real-world experiments suffer from the fact that the hyper-parameters have been fixed in advance. Thus, the comparison is actually unfair; it might be possible that on those real-world datasets a proper model selection over GIN, GCN and PNA could have nullified the reported performance improvements of the proposed approach. While the same issue occurs on synthetic datasets, given the way they are created it is less likely that the main results would have changed. While it would be highly appreciable to see the authors fix this mistake, the overall contribution is still undoubtedly valuable. Below there are some requests of clarifications and potential suggestions (mainly regarding style and presentation) that may help improve the mauscript.

line 11: "any GNNs" is too strong of a claim. Please consider changing the wording.
line 24: claiming that the representational limit of DGNs are upper-bounded by the WL-test may not be appropriate, as WL does not consider vertex/edge attributes (see also line 48-50).
line 37: it may be important to state from the beginning that the "universal approximation" property is related to graph isomorphism without attributes (unless I missed something).
line 60: what do the authors mean by "the combination of theoretical and empirical results is an additional connection"? Is it not enough to have incorporated the theoretical insights into the experiments of Section 5?

line 93-99: for someone that is not familiar with the reconstruction conjecture, this part may be vague. Please consider moving it a bit later, perhaps in a different form after the conjecture has been formulated.
lines 108-109: the term "edge directions" becomes clear later on in the paper (line 139). The authors may consider removing this reference or explaining it.
line 116: Question: if R can distinguish pairs of graphs G,H, is it implied that R distinguishes the individual graphs according to the previous definition? Some clarification may be in order here, perhaps using a more formal notation.

line 143: so far, reconstructible graphs have been defined, wheres reconstructible graph properties have not. What is a reconstructible property (formally)? Is it related to the concept of hereditary property defined later? Please clarify this point.
line 178: it seems the term $k$ is used both as an index taking different values as well as the exact size of the graphs under consideration. Please consider using a different index to help the reader.
line 188: similarly, it would be helpful to explicitly state that r^3 is considered more expressive than r^4 and so on.

line 239: what is the purpose of the ratio |S|\|S_B| ?

lines 251 and 269: it may be confusing that the use of the terms "more expressive" and "less expressive" is in contrasts with the results at lines 263 and 272, respectively. To be more clear, I was expecting a different kind of result after line 269, something of the kind k-Reconstruction "<=" GNN. Perhaps it is just me, but the titles of the paragraph sounded misleading.

line 256: Question: are there any restrictions on the length of the cycle?

line 280: Question: why is it GNN < n-1-reconstruction and not the opposite, given that the authors are conveying the message that n-1-reconstruction is more expressive?
lines 308-309: the hereditary property definition does not necessarily imply that inductive reasoning holds in general. Please clarify this aspect.

line 329: if there is no hierarchy between DGNs and k-reconstruction GNN, why talking about "increased" expressive power in general?

line 397: Question: what is the authors intuition behind the drop in performance of n-3.. n/2 - reconstruction GNNs (which in theory should be more powerful)? Is it because of the sampling approach vs the exact implementation of n-1-reconstruction?
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The reviewers agreed that this work provides a valuable contribution to the GNN research by expanding on the known connections between graph reconstruction theory with graph representation learning. While sometimes falling behind more powerful architectures, the proposed method is shown to consistently improve upon vanilla GNN. 

The reviewers originally expressed some concerns about the rigorousness of the mathematical statements. However, these were addressed during the rebuttal phase. 

I thus recommend the (revised) paper for publication.
Decision: Accept (Poster)