Venue: ICLR 2018 conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Existing training algorithms for graph convolutional nets are slow. This paper develops new novel methods, with a nice mix of theory, practicalities, and experiments.

Let me caution that I am not familiar with convolutional nets applied to graph data.

Clearly, the existing best algorithm - neighborhood sampling is slow as well as not theoretically sound. This paper proposes two key ideas - preprocessing and better sampling based on historical activations. The value of these ideas is demonstrated very well via theoretical and experimental analysis. I have skimmed through the theoretical analysis. They seem fine, but I haven't carefully gone through the details in the appendices.

All the nets considered in the experiments have two layers. The role of preprocessing to add efficiency is important here. It would be useful to know how much the training speed will suffer if we use three or more layers, say, via one more experiment on a couple of key datasets. This will help see the limitations of the ideas proposed in this paper.

In subsection 4.3 the authors prove reduced variance under certain assumptions. While I can see that this is done to make the analysis simple, how well does this analysis correlate with what is seen in practice? For example, how well does the analysis results given in Table 2 correlate with the standard deviation numbers of Figure 5 especially when comparing NS+PP and CV+PP?
review_title: Existing training algorithms for graph convolutional nets are slow. This paper develops new novel methods, with a nice mix of theory, practicalities and experiments.

final_score: rating: 3: Clear rejection
review_content: This paper proposes a new training method for graph convolutional networks. The experimental results look interesting. However, this paper has some issues.

This paper is hard to read. There are some undefined or multi-used notations. For instance, sigma is used for two different meanings: an activation function and variance. Some details that need to be explained are omitted. For example, what kind of dropout is used to obtain the table and figures in Section 5? Forward and backward propagation processes are not clearly explained

In section 4.2, it is not clear why we have to multiply sqrt{D}. Why should we make the variance from dropout sigma^2? 

Proposition 1 is wrong. First, \|A\|_\infty should be max_{ij} |A_ij| not A_{ij}. Second, there is no order between \|AB\|_\infty and \|A\|_\infty \|B\|_\infty. When A=[1 1] and B is the transpose matrix of A, \|AB\|_\infty =2 and \|A\|_\infty \|B\|_\infty = 1. When, A’=[1 -1] and B is the same matrix defined just before, \|A’ B \|_\infty = 0 and \|A’\|_\infty \|B\|_\infty =1. So, both \|AB\|_\infty \le \|A\|_\infty \|B\|_\infty and \|AB\|_\infty \ge \|A\|_\infty \|B\|_\infty are not true. I cannot believe the proof of Theorem 2.

review_title: A new training method of graph convolutional networks. Good but there are some errors.

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper proposes a method to speed up the training of graph convolutional networks, which are quite slow for large graphs. The key insight is to improve the estimates of the average neighbor activations (via neighbor sampling) so that we can either sample less neighbors or have higher accuracy for the same number of sampled neighbors. The idea is quite simple: estimate the current average neighbor activations as a delta over the minibatch running average. I was hoping the method would also include importance sampling, but it doesn’t. The assumption that activations in a graph convolution are independent Gaussians is quite odd (and unproven). 

Quality: Statistically, the paper seems sound. There are some odd assumptions (independent Gaussian activations in a graph convolution embedding?!?) but otherwise the proposed methodology is rather straightforward. 

Clarity: It is well written and the reader is able to follow most of the details. I wish the authors had spent more time discussing the independent Gaussian assumption, rather than just arguing that a graph convolution (where units are not interacting through a simple grid like in a CNN) is equivalent to the setting of Wang and Manning (I don’t see the equivalence). Wang and Manning are looking at MLPs, not even CNNs, which clearly have more independent activations than a CNN or a graph convolution. 

Significance: Not very significant. The problem of computing better averages for a specific problem (neighbor embedding average) seems a bit too narrow. The solution is straightforward, while some of the approximations make some odd simplifying assumptions (independent activations in a convolution, infinitesimal learning rates). 

Theorem 2 is not too useful, unfortunately: Showing that the estimated gradient is asymptotically unbiased with learning rates approaching zero over Lipchitz functions does not seem like an useful statement. Learning rates will never be close enough to zero (specially for large batch sizes). And if the running activation average converges to the true value, the training is probably over. The method should show it helps when the values are oscillating in the early stages of the training, not when the training is done near the local optimum.



review_title: Interesting but not enough

Meta-review: The paper studies subsampling techniques necessary to handle large graphs with graph convolutional networks.  The paper introduces two ideas: (1) preprocessing for GCNs (basically replacing dropout followed by linear transformation with linear transformation followed by drop out); (2) adding control variates based on historical activations.  Both ideas seem useful (but (1) is more empirically useful than (2), Figure 4*). The paper contains a fair bit of math (analysis / justification of the method).

Overall, the ideas are interesting and can be useful in practice. However, not all reviewers are convinced that the methods constitute a significant contribution.  There is also a question whether the math has much value (strong assumptions - also, from interpretation, may be too specific to the formulation of Kipf & Welling making it a bit narrow?).  Though I share these feelings and recommend rejection, I think that the reviewers 2 and 3 were a bit too harsh, and the scores do not reflect the quality of the paper.

*Potential typo: Figure 4 -- should it be CV +PP rather than CV?

+ an important problem
+ can be useful in practical applications
+ generally solid and sufficiently well written
- significance not sufficient
- math seems not terribly useful


Decision: Reject