Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies a theoretical framework to address learning problems over graphs under partial observation constraints. In this context, a Random Balls Sampling GNN architecture based on random neighborhood model is introduced and its expressibility and learnability are characterized theoretically. Applications of the proposed architecture to settings with perturbations and size-generalizability are also discussed.   
main_review: 1. The notion of estimability of a graph parameter is central to the theoretical claims in the paper. Therefore, I recommend that the authors elaborate more on this aspect in Section 3.2. Moving Definition 18 and some of the discussions in Appendix D.1 to the main paper will greatly improve the readability of this section of the paper. 

2. Similarly, the notion of 'uniformly continuous' graph parameter must be explicitly defined in Section 5.2.

3. What is the intuition behind the factor $2^{-r}$ in equation (2)?

4. In Section 6.3.1, what does the notation $G_{\leq N}$ signify? Also, shouldn't you have $|p(G) - {\cal A}(G_{\leq N})|\leq \epsilon$ in the definition of a size generalizable parameter $p$ for the algorithm ${\cal A}$ that operates on the given dataset?

5. The main paper lacks experimental evaluations and limited experiments are relegated to the Appendix. It would be useful to have an experimental setup in the main paper to illustrate the applicability of various theoretical claims in the paper. 

The theory in this paper is tangential to my expertise and therefore, I am not fully familiar with other theoretical works in this context. However, the notions of learning from partially observed graphs and size generalizability are interesting and would be of interest to a wider audience. The readability of the paper could be improved by some reorganization of the content between the main paper and Appendices and including formally defining the notions of estimability, uniform continuity, size generalizability etc. 


limitations_and_societal_impact: NA
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes to use randomly sampled subgraphs from a large graph to estimate the function value computed from the entire graph. The paper has done extensive theoretical analysis using the "randomized Benjamini–Schramm topology". The model also has analyzed learnability issues when estimating these functions. 
main_review: Strengths

+The main problem addressed in this paper is the estimation of graph functions through sampling neighborhoods on the graph. This paper seems to be the first theoretical analysis of this problem. This problem is related to two problems. The first one is the estimation of a value of a large graph (e.g. the average degree) through sampling, which is a traditional problem. The second problem is the analysis of GNNs generalizing to different sizes of graphs. 

+Using the "randomized Benjamini–Schramm topology" brings a new technique to the area is another contribution of the submission. 

Weaknesses

-The problem studied in this paper is unrealistic. The introduction says the motivation is the learning problem where the input is a huge graph and the output is a single value. At least I don't know such a problem exists: we don't have thousands of social networks and need to classify them. The experiment in the appendix does not use any data supporting the motivation. Actually, the experiment samples tiny graphs, all of which does not have computation or memory issues. 


-The function to be estimated is unknown, so we are not sure whether it is estimable. Particularly, the learned model as a function is not necessarily estimable. For example, we can use the learning model to estimate the maximum degree. Therefore, it is unknown where the analysis is applicable. 

-By reading this submission, I have a feeling that it overly claims the contribution. For example, the title put parenthesis over "some". Do you mean "some" can be removed? Also, line 270:  "... guarantees the asymptotic convergence on any graph learning problem without assuming any graph structure." I believe "any graph learning problem" is not true: it is limited to the estimable functions. There are also other cases. 

-There should be a more thorough introduction of the literature. There is plenty of work on randomized testing graph properties or computing graph parameters. Not all of them are based on "randomized Benjamini–Schramm topology" -- why this topology is advantageous? 

Nevertheless, I still think the research carries value, but the authors may want to find the scenario for the analysis. For example, are there any learning problems that have prior knowledge that the unknown function is estimable?  


limitations_and_societal_impact: No potential negative societal impact is known.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper uses sublinear algorithms to estimate certain graph functions.

The paper is essentially a property testing (sublinear algorithms) paper posing as a GNN paper. This is not necessarily a bad thing if the connection is strong enough; however, this connection does not become very clear to me.

The main relation to GNN is very vague as core concepts such as universality are not well-defined. I presume the universal approximation theorem is meant here, but I cannot be sure.

main_review: In section 5.1 an important restriction is mentioned that somehow does not become clear in Theorem 3.
(the theorem is only applicable to the continuous functions in  the randomized Benjamini–Schramm topology)

There are some applications mentioned, but they are not very illuminating. Could you perhaps state some concrete examples of functions that can be estimated?

Not clear what this means:
A rooted graph (G, v) is a graph G augmented with a vertex v in V (G) 

WeaklyConnectedComponents quadratic query complexity? Needs to check all possible adjacency matrix entries? What if the degrees are super-constant? Does that mean that the sampling is also super-constant?

The proof idea of Theorem 3 feels unfinished. Why is good to be able to list all isomorphism classes of all graphs on x vertices?

Shouldn't Theorem 3 mention sampling complexity in some way or another? 
limitations_and_societal_impact: Fine
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: To take the words of the authors directly, this paper answers the question "What graph functions are representable by GNNs when we can only observe random neighborhoods?" In answering this question, the authors consider a notion of an estimable function in a random neighborhood model, which they then show is equivalent to uniform continuity in a metric topology, which they dub the randomized Benjamini-Schramm topology. With this perspective in hand, they show that sufficiently powerful graph neural networks coupled with universal approximators are capable of estimating uniformly continuous functions in this topology. They then discuss implications of this in terms of robustness, sampling complexity, and generalization.
main_review: I will begin by discussing the strengths of this paper, then move on to the weaknesses, followed by some brief comments.

**Strengths**

1. This paper is very well-presented. Although its contents are technically demanding, the results are presented in such a way that lends to easy understanding. Despite this paper being somewhat outside of my main research area, I found it to be not too difficult to digest. The authors should be applauded for refraining from using extremely fancy machinery to convey their results, which is all-too-tempting in papers like this. Because of this, I think this paper is of broad interest to the graph learning community.

2. The approach taken by this work is quite general. As the authors point out, it makes essentially no assumption on the graph structure itself, only demanding that the function to be estimated is estimable under their sampling model. Related to this is the simplicity of their approach: although they study estimation under a specific random ball sampling algorithm, the RBS-GNN is not particularly exotic. That is to say, the results presented are apparently applicable in many contexts, as discussed in Section 6.4, where weaker classes of GNNs are considered.

3. The problem studied is quite relevant: there is great interest in applying graph neural networks approaches to huge graphs, with many approaches dedicated to ways to split graphs up or sample them in clever ways to avoid storing a humongous data structure. This paper offers a nice set of results for this particular problem, which will be useful to practitioners in understanding what constitutes an "estimable" parameter and what sampling strategies should work.

4. The proposed random Benjamini-Schramm topology seems to be novel.

**Weaknesses**

1. Although the authors admit this, the generality of their approach leads to some issues with bounds having poor dependance on the graph size and estimation accuracy. This is addressed briefly in a few places, but it would have been nice to see some more concrete examples regarding this. For the benefit of the research community, this addition would ground this work in practice better.

3. The main paper does not show any empirical validation of the ideas in the paper. I do understand that this is primarily a theoretical paper, but the fact that a specific sampling method was studied motivates the inclusion of some empirical results. I did see that there are some in the supplementary material, which is appreciated, but these were somewhat weak in my opinion. The RBS-GNN clearly underperformed relative to competing approaches, which is understandable given the limited observation scheme. However, I would have liked to see a comparison with other neural approaches that sample subgraphs for the purpose of embedding.

4. Despite my aforementioned appreciation of the presentation of this work, there are a few things that could use a bit more explanation. I list these below.

i. Section 5.2. When defining the sampling distance, a few things stick out to me. First, the explanation of an $r$-profile is unclear: I am not sure what this distribution is meant to look like. I see that there is some randomness that comes up due to the random ball sampling, but how this translates to a random vector is not explained very well. Given that the metric topology of this sampling distance is the core contribution of this paper, this warrants more effort in explanation. I would have suggested moving part of Section 6 to the supplementary material in order to make room for this.

ii. Again in Section 5.2, eq (2). It isn't too surprising that this is a reasonable distance to choose, casting aside my previous doubts about $r$-profiles. However, this could use a bit more explanation. Reading it, the weighting by $2^{-r}$ treats smaller sampling radii as more important, while downweighting larger sampling radii: and of course, this kind of weighted sum of a difference of sequences is a common example of a distance between sequences in functional analysis. In this context, this could be interpreted as saying that the distance is small for graphs that exhibit similar motif structures, but perhaps with differing global structure. Could you please explain this in more detail? Is the sampling distance the only appropriate distance for defining this topology, or is it one in some class of appropriate metrics for this task?

**Comments**

1. Overall thoughts: I found this paper to be quite enjoyable and informative. The presentation is quite good, and the results are novel, providing an interesting perspective on randomized approaches to graph parameter estimation. I appreciated how the authors tied the notion of an estimable graph parameter to a novel metric topology, which allowd them to approach this problem from a functional analysis perspective. Overall, despite the issues I pointed out on practicality and some didactic concerns, I think this is a fine paper, and should be accepted.

**Editorial** (No impact on decision)

1. Line 228: "Benjamini-Schram" is misspelled.

2. Line 303: "numbere" is misspelled.

3. Some of the citations do not look very good. Please take another pass on these, **with a particular focus on capitalization.** Some problematic citations I noticed were [20],[31],[34],[40],[42],[43],[56],[58],[61],[63/64],[71],[72]. There are also inconsistencies on venue citation, for instance between [13/15] and [11/21]. I would suggest using the `@string` macro in BibTeX to ensure consistent venue naming, e.g.,

```
@string{iclr={International Conference on Learning Representations}}

@article{
title={Absurdly Deep Convolutional Neural Networks},
author={John Smith},
journal=iclr,
}
```

limitations_and_societal_impact: Limitations are addressed in body of the paper, societal impact is not an issue for this work.
review_title: null

Meta-review: This paper considers estimation of a real number associated to a large graph. Some examples of quantities that one might wish to estimate are the density of triangles (or relatedly the clustering coefficient). Rather than observing the entire graph, it is assumed that algorithms have access to a specific random sampling procedure whereby random nodes are selected and then their neighborhoods are randomly explored. A variation on the Benjamini-Schramm topology is introduced and the set of estimable graph properties is characterized in terms of continuity in this topology. A number of other results are presented regarding generalization across multiple graph sizes, etc.

The proposed sampling/observation model is reasonable and placed within context of related observation models. While the work is entirely theoretical, its results clearly demarcate what is possible or impossible with regards to the specific sampling model. Thus, there are natural implications for what can be learned by graph neural networks. The work seems likely to spur further investigation with other sampling models and to make tighter connections to finite size graph neural networks. 
Decision: Accept (Poster)