Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: Paper strengths:

1. Overall it is a solid and well-written article. 
2. The interesting and novel part is the theoretical demonstration that a fixed number of neighbors can approximate well some algorithms in the literature (it approximates well w.r.t to the forward embedding produced by those algorithms and to the backward gradients in relation to the parameters), 
3.It also demonstrates that some algorithms are impossible to approximate in constant time.

Weaknesses:

1. They do not introduce a new method, the algorithm is message-passing in which not all the neighbors are considered - authors choose a fixed number of neighbors by sampling. This gives them constant time for the calculation of the embedding w.r.t to the number of neighbors

Main points:

Overall, the article is well supported theoretically and quite complete. They generally show that if the assumptions made are contradicted, the approximation becomes impossible.

The experiments seem quite well chosen for the cases studied. In general, the experiments in which authors want to show the impossibility of an approximation, are done exactly on the corner cases chosen for the theoretical demonstrations. However,  they also have experiments on real datasets, used in the literature.

Other observations:

It is not very clear what do they mean by "standardization layer from GCN" which intervenes in several theorems.

It may have been good to show how accuracy varies relative to the chosen error. It is not very intuitive what an embedding approximation error of e = 0.01 means. For example, to have 0.1 error and 95% confidence I would have to choose 300 neighbors.... That seems to be a very large number, how practical is that?

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: In this paper, the authors provide a theoretical framework for characterizing the approximation guarantees provided by node sampling to estimate embeddings in various GNN architectures. In particular, they prove several PAC learning-style bounds on the embedding and gradient estimation when using node sampling approaches. They also observe that since the number of nodes selected for sampling is not dependent on the size of the graph, this amounts to a constant time operation for determining embedding and gradient estimates.

Importantly, a variety of existing works have already proposed node sampling (“constant-time GNNs”), so the contribution of this work lies in the theoretical bounds. A moderate set of experiments suggests the empirical behavior follows the theoretical expectations.

Overall (and described in the comments below), I believe this paper provides some interesting theoretical results for an approach that is widely-used in practice. However, I believe the title and abstract are misleading; this paper does not suggest some new sampling strategy; it only gives a theoretical approximation error for existing approaches and network architectures.

Comments

While the authors do make this clear later in the paper, the contributions of this work are only the theoretical bounds; the node sampling algorithms have been proposed in existing work. Both the title and abstract are misleading.

Still, the theoretical bounds do provide an interesting understanding of an approach which is commonly used in practice.

It would be helpful to give the intuition behind the assumptions and proofs. Currently, it is difficult for a non-expert to follow the reasoning and practical implications of much of this work.

Currently, it is not clear if these results are “constructive”, in the sense that they do not obviously suggest some new sampling strategy, etc. Of course, it is still interesting to characterize commonly-used practices, but one does wish the theory suggested, say, a better sampling strategy, etc.

Typos, etc.

“r”, the number of sampled nodes, is not defined in the main body of the paper.

The text in Footnote 1 is a little confusing, in that the text refers to approximating the embedding, while the text in the footnote describes a prediction problem. A reader could easily interpret this to mean that the error on the downstream prediction problem will be bounded (which is not what this work shows).

The text mentions that O_G (v,i) refers to the i^th “neighborhood” of v. Presumably, this should be “neighbor”.

“we take” -> “We take”

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: In this paper, the authors propose a constant-time approximation for graph convolution operation via theoretical analysis on the number of sampling from each neighbor. The authors prove that both node embedding and gradient can be approximated via constant number of samples among the neighbors. Extensive experiments are carried out to verify the correctness of the proposed bounds.

Strength:
1. The authors establish rigorous bounds on the number of required neighbors to sample to guarantee good approximation of the graph convolution operations. The bounds are established on both nodes embedding and gradients.
2. The authors corroborate the theoretical results with extensive experiments. The experiments are carried under the case both when the assumption holds and not.

Weakness:
1. Though the bounds do not depend on number of nodes, it does have an exponential dependence on the number of layers. For common GCN with L=2, even \epsilon = 0.1 requires more than 10^4 samples. As a result, the bound is less practical in providing guidance for real-world application. Moreover, the bound does not depend on the embedding dimension at all. Is this to be expected?
2. The authors only provide constant bound for convolution on individual nodes. For the final metrics like classification accuracy, we need to guarantee good approximation for all node’s convolution. In this case, the bounds will definitely depend on number of nodes at least through the union bounds among all nodes.
3. The proposed method is exactly the uniform neighbor sampling methods. There is little contribution on the methodology side from the paper. Also, it would be interesting if the authors could provide theoretical analysis for adaptive sampling methods as well.
4. The authors provide in-approximability results under certain conditionals. However, uniform sampling methods works well empirically under this case as well. It would be better if the authors could explain the gap between theory and empirical performance.

Detailed Comments:
1. Algorithm 2, please define notation like O(v<-v).

review_title: Official Blind Review #3

Meta-review: There was some interest in the ideas presented, but this paper was on the borderline and ultimately not able to be accepted for publication at ICLR.

The primary reviewer concern was about the level of novelty and significance of the contribution. This was not sufficiently demonstrated.
Decision: Reject