Venue: ICLR 2018 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The paper focuses on the recently graph convolutional network (GCN) framework.
They authors identify a couple of issues with GCN: the fact that both training and test data need to be present at training time, making it transductive in nature and the fact that the notion of ‘neighborhood’ grows as the signal propagates through the network. The latter implies that GCNs can have a large memory footprint, making them impractical in certain cases. 
The authors propose an alternative formulation that interprets the signals as vertex embedding functions; it also interprets  graph convolutions as integral transforms of said functions.
Starting from mini-batches consisting purely of training data (during training) each layer performs Monte Carlo sampling on the vertices to approximate the embedding functions.
They show that this estimator is consistent and can be used for training the proposed architecture, FastGCN, via standard SGD. 
Finally, they analyze the estimator’s variance and propose an importance-sampling based estimator that has minimal layer-to-layer variance.
The experiments demonstrate that FastGCN is much faster than the alternatives, while suffering a small accuracy penalty.

This is a very good paper. The ideas are solid, the writing is excellent and the results convincing. I have a few comments and concerns listed below.

Comments:
1. I agree with the anonymous commenter that the authors should provide detailed description of their experimental setup.
2. The timing of GraphSAGE on Cora is bizarre. I’m even slightly suspicious that something might have been amiss in your setup. It is by far the smallest dataset. How do you explain GraphSAGE performing so much worse on Cora than on the bigger Pubmed and Reddit datasets? It is also on Cora that GraphSAGE seems to yield subpar accuracy, while it wins the other two datasets.
3. As a concrete step towards grounding the proposed method on state of the art results, I would love to see at least one experiment with the same (original) data splits used in previous papers. I understand that semi-supervised learning is not the purpose of this paper, however matching previous results would dispel any concerns about setup/hyperparameter mismatch. 
4. Another thing missing is an exploration (or at least careful discussion) as to why FastGCN performs worse than the other methods in terms of accuracy and how much that relative penalty can be.

Minor comments:
5. Please add label axes to Figure 2; currently it is very hard to read. Also please label the y axis in Figure 3.
6. The notation change in Section 3.1 was well intended, however I feel like it slowed me down significantly while reading the paper. I had already absorbed the original notation and had to go back and forth to translate to the new one. 

review_title: Solid idea, excellent presentation, questions about experiments

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper addresses the memory bottleneck problem in graph neural networks and proposes a novel importance sampling scheme that is based on sampling vertices (instead of sampling local neighbors as in [1]). Experimental results demonstrate a significant speedup in per-batch training time compared to previous works while retaining similar classification accuracy on standard benchmark datasets.

The paper is well-written and proposes a simple, elegant, and well-motivated solution for the memory bottleneck issue in graph neural networks.

I think that this paper mostly looks solid, but I am a bit worried about the following assumption: “Specifically, we interpret that graph vertices are iid samples of some probability distribution”. As graph vertices are inter-connected and inter-dependent across edges of the graph, this iid assumption might be too strong. A short comment on why the authors take this particular interpretation would be helpful.

In the abstract the authors write: “Such a model [GCN], however, is transductive in nature because parameters are learned through convolutions with both training and test data.” — as demonstrated in Hamilton et al. (2017) [1], this class of models admits inductive learning as well as transductive learning, so the above statement is not quite accurate.

Furthermore, a comment on whether this scheme would be useful for alternative graph neural network architectures, such as the one in MoNet [2] or the generic formulation of the original graph neural net [3] (nicely summarized in Gilmer et al. (2017) [4]) would be insightful (and would make the paper even stronger).

I am very happy to see that the authors provide the code together with the submission (using an anonymous GitHub repository). The authors mention that “The code of GraphSAGE is downloaded from the accompany [sic] website, whereas GCN is self implemented.“ - Looking at the code it looks to me, however, as if it was based on the implementation by the authors of [5]. 

The experimental comparison in terms of per-batch training time looks very impressive, yet it would be good to also include a comparison in terms of total training time per model (e.g. in the appendix). I quickly checked the provided implementation for FastGCN on Pubmed and compared it against the GCN implementation from [5], and it looks like the original GCN model is roughly 30% faster on my laptop (no batched training). This is not very surprising, as a fair comparison should involve batched training for both approaches. Nonetheless it would be good to include these results in the paper to avoid confusion.

Minor issues:
- The notation of the limit in Theorem 1 is a bit unclear. I assume the limit is taken to infinity with respect to the number of samples.
- There are a number of typos throughout the paper (like “oppose to” instead of “opposed to”), these should be fixed in the revision.
- It would be better to summarize Figure 3 (left) in a table, as the smaller values are difficult to read off the chart.

Overall, I think that this paper can be accepted. The proposed scheme is a simple drop-in replacement for the way adjacency matrices are prepared in current implementations of graph neural nets and it promises to solve the memory issue of previous works while being substantially faster than the model in [1]. I expect the proposed approach to be useful for most graph neural network models.

UPDATE: I would like to thank the authors for their detailed response and for adding additional experimental evaluation. My initial concerns have been addressed and I can fully recommend acceptance of this paper.

[1] W.L. Hamilton, R. Ying, J. Leskovec, Inductive Representation Learning on Large Graphs, NIPS 2017
[2] F. Monti, D. Boscaini, J. Masci, E. Rodala, J. Svoboda, M.M. Bronstein, Geometric deep learning on graphs and manifolds using mixture model CNNs, CVPR 2017
[3] F. Scarselli, M. Gori, A.C. Tsoi, M. Hagenbuchner, G. Monfardini, The Graph Neural Network Model, IEEE Transactions on Neural Networks, 2009
[4] J. Gilmer, S.S. Schoenholz, P.F. Riley, O. Vinyals, G.E. Dahl, Neural Message Passing for Quantum Chemistry, ICML 2017
[5] T.N. Kipf, M. Welling, Semi-Supervised Classification with Graph Convolutional Networks, ICLR 2017
review_title: Fast solution for the memory bottleneck issue in graph neural networks

final_score: rating: 6: Marginally above acceptance threshold
review_content: Update:

I have read the rebuttal and the revised manuscript. Additionally I had a brief discussion with the authors regarding some aspects of their probabilistic framework. I think that batch training of GCN is an important problem and authors have proposed an interesting solution to this problem. I appreciated all the work authors put into the revision. In this regard, I have updated my rating. However, I am not satisfied with how the probabilistic problem formulation was presented in the paper. I would appreciate if authors were more upfront about the challenges of the problem they formulated and limitations of their results. I briefly summarize the key missing points below, although I acknowledge that solution to such questions is out of scope of this work.

1. Sampling of graph nodes from P is not iid. Every subsequent node can not be equal to any of the previous nodes. Hence, the distribution changes and subsequent nodes are dependent on previous ones. However, exchangeability could be a reasonable assumption to make as order (in the joint distribution) does not matter for simple choices of P. Example: let V be {1,2,3} and P a uniform distribution. First node can be any of the {1,2,3}, second node given first (suppose first node is '2') is restricted to {1,3}. There is clearly a dependency and change of distribution.

2. Theorem 1 is proven under the assumption that it is possible to sample from P and utilize Monte Carlo type argument. However, in practice, sampling is done from a uniform distribution over observed samples. Also, authors suggest that V may be infinite. Recall that for Monte Carlo type approaches to work, sampling distribution is ought to contain support of the true distribution. Observed samples (even as sample size goes to infinity) will never be able to cover an infinite V. Hence, Theorem 1 will never be applicable (for the purposes of evaluating population loss). Also note that this is different from a more classical case of continuous distributions, where sampling from a Gaussian, for instance, will cover any domain of true distribution. In the probabilistic framework defined by the authors it is impossible to cover domain of P, unless whole V is observed.

----------------------------------------------------------------------
This work addresses a major shortcoming of recently popularized GCN. That is, when the data is equipped with the graph structure, classic SGD based methods are not  straightforward to apply. Hence it is not clear how to deal with large datasets (e.g., Reddit). Proposed approach uses an adjacency based importance sampling distribution to select only a subset of nodes on each GCN layer. Resulting loss estimate is shown to be consistent and its gradient is used to perform the weight updates.

Proposed approach is interesting and the direction of the work is important given recent popularity of the GCN. Nonetheless I have two major question and would be happy to revisit my score if at least one is addressed.

Theory:
SGD requires an unbiased estimate of the gradient to converge to the global optima in the convex loss case. Here, the loss estimate is shown to be consistent, but not guaranteed to be unbiased and nothing is said about the gradient in Algorithm 1. Could you please provide some intuition about the gradient estimate? I might not be familiar with some relevant results, but it appears to me that Algorithm 1 will not converge to the same solution as full data GD would.

Practice:
Per batch timings in Fig. 3 are not enough to argue that the method is faster as it might have poor convergence properties overall. Could you please show the train/test accuracies against training time for all compared methods?

Some other concerns and questions:
- It is not quite cleat what P is. You defined it as distribution over vertices of some (potentially infinite) population graph. Later on, sampling from P becomes equivalent to uniform sampling over the observed nodes. I don't see how you can define P over anything outside of the training nodes (without defining loss on the unobserved data), as then you would be sampling from a distribution with 0 mass on the parts of the support of P, and this would break the Monte Carlo assumptions.
- Weights disappeared in the majority of the analysis. Could you please make the representation more consistent.
- a(v,u) in Eq. 2 and A(v,u) in Eq. 5 are not defined. Do they both correspond to entries of the (normalized) adjacency?
review_title: Interesting ideas, but I have both theoretical and practical concerns

final_score: rating: 7: Good paper, accept
review_content: The paper presents a novel view of GCN that interprets graph convolutions as integral transforms of embedding functions. This addresses the issue of lack of sample independence in training and allows for the use of Monte Carlo methods. It further explores variance reduction to speed up training via importance sampling.  The idea comes with theoretical support and experimental studies.

Some questions are as follows:

1) could you elaborate on n/t_l  in (5) that accounts for the normalization difference between matrix form (1) and the integral form (2) ?

2) In Prop.2., there seems no essential difference between the two parts, as e(v) also depends on how the u_j's are sampled.

3) what loss g is used in experiments?
review_title: present a novel view of GCN that leads to scalable GCN further with importance sampling for variance reduction

Meta-review: Graph neural networks (incl. GCNs) have been shown effective on a large range of tasks. However, it has been so far hard (i.e. computationally expensive or requiring the use of heuristics) to apply them to large graphs. This paper aims to address this problem and the solution is clean and elegant. The reviewers generally find it well written and interesting. There were some concerns about the comparison to GraphSAGE (an alternative approach), but these have been addressed in a subsequent revision.

+ an important problem
+ a simple approach
+ convincing results
+ clear and well written

Decision: Accept (Poster)