Venue: ICLR 2018 conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Since existing GNNs are not computational efficient when dealing with large graphs, the key engineering contributions of the proposed method, GPNN, are a partitioning and the associated scheduling components. 

The paper is well written and easy to follow. However, related literature for message passing part is inadequate. 

I have two concerns. The primary one is that the method is incremental and rather heuristic. For example, in Section 2.2, Graph Partition part, the authors propose to "first randomly sample the initial seed nodes biased towards nodes which are labeled and have a large out-degree", they do not give any reasons for the preference of that kind of nodes. 

The second one is that of the experimental evaluation. GPNN is on par with other methods on small graphs such as citation networks, performs comparably to other methods, and only clearly outperforms on distantly-supervised entity extraction dataset. Thus, it is  not clear if GPNN is more effective than others in general. As for experiments on DIEL dataset, the authors didn't compare to GCN due to the simple reason that GCN ran out of memory. However, vanilla GCN could be trivially partitioned and propagating just as shown in this paper. I think such experiment is crucial, without which I cannot assess this method properly.

review_title: Incremental improvement on graph neural networks with heuristic graph partitioning

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors investigate different message passing schedules for GNN learning.  Their proposed approach is to partition the graph into disjoint subregions, pass many messages on the sub regions and pass fewer messages between regions (an approach that is already considered in related literature, e.g., the BP literature), with the goal of minimizing the number of messages that need to be passed to convey information between all pairs of nodes in the network.  Experimentally, the proposed approach seems to perform comparably to existing methods (or slightly worse on average in some settings).  The paper is well-written and easy to read.  My primary concern is with novelty.  Many similar ideas have been floating around in a variety of different message-passing communities.  With no theoretical reason to prefer the proposed approach, it seems like it may be of limited interest to the community if speed is its only benefit (see detailed comments below).

Specific comments:

1)  "When information from any one node has reached all other nodes in the graph for the first time, this problem is considered as solved."

Perhaps it is my misunderstanding of the way in which GNNs work, but isn't the objective actually to reach a set of fixed point equations.  If so, then simply propagating information from one side of the graph may not be sufficient.

2)  The experimental results in Section 4.4 are almost impossible to interpret.  Perhaps it is better to plot number of edges updated versus accuracy?  This at least would put them on equal footing.   In addition, the experiments that use randomness should be repeated and plotted on average (just in case you happened to pick a bad schedule).

3)  More generally, why not consider random schedules (i.e., just pick a random edge, update, repeat) or random partitions?  I'm not certain that a fixed set will perform best independent of the types of updates being considered, and random schedules, like the fully synchronous case for an important baseline (especially if update speed is all you care about).

Typos:

-pg. 6, "Thm. 2" -> "Table 2"
review_title: Partitioning for better message passing - maybe?

final_score: rating: 6: Marginally above acceptance threshold
review_content: Graph Neural Networks are methods using NNs to deal with graph data (each data point has some features, and there is some known connectivity structure among nodes) for problems such as semi-supervised classification. They can also be viewed as an abstraction and generalizations of RNNs to arbitrary graphs. As such they assume each unit has inputs from other nodes, as well as from some stored representation of a state and upon receiving all its information and executing a computation on the values of these inputs and its internal state, it can update the state as well as propagate information to neighbouring nodes. 

This paper deals with the question of computing over very large input graphs where learning becomes computationally problematic (eg hard to use GPUs, optimization gets difficult due to gradient issues, etc). The proposed solution is to partition the graph into sub graphs, and use a schedule alternating between performing intra and inter graph partitions operations. To achieve that two things need to be determined - how to partition the graph, and which schedules to choose. The authors experiment with existing and somewhat modified solutions for each of these problems and present results that show that for large graphs, these methods are indeed effective and achieve state-of-the-art/improved results over existing methos. 

The main critique is that this feels more of an engineering solution to running such GNNs on large graphs than a research innovations. The proposed algorithms are straight forward and/or utilize existing algorithms, and introduce many hyper parameters and ad-hoc decisions (the scheduling to choose for instance). In addition, they do not satisfy any theoretical framework, or proposed in the context of a theoretical framework than has guarantees of mathematical properties that are desirable. As such it is likely of use for practitioners but not a major research contribution. 
review_title: Extends the GNN framework to handle large graphs by running async updates on subgraphs derived by using graph partitioning algorithms. Results demonstrated on semi-supervised task. 

Meta-review: This paper was perceived as being well written, but the technical contribution was seen as being incremental and somewhat heuristic in nature. Some important prior work was not discussed and more extensive experimentation was recommended.
However, the proposed approach of partitioning the graph into sub graphs and a schedule alternating between intra and inter graph partitions operations has some merit.

The AC recommends inviting this paper to the Workshop Track.
Decision: Invite to Workshop Track