We present graph partition neural networks (GPNN), an extension of graph neural networks (GNNs) able to handle extremely large graphs. GPNNs alternate between locally propagating information between nodes in small subgraphs and globally propagating information between the subgraphs. To efficiently partition graphs, we experiment with spectral partitioning and also propose a modified multi-seed flood fill for fast processing of large scale graphs. We extensively test our model on a variety of semi-supervised node classification tasks. Experimental results indicate that GPNNs are either superior or comparable to state-of-the-art methods on a wide variety of datasets for graph-based semi-supervised classification. We also show that GPNNs can achieve similar performance as standard GNNs with fewer propagation steps.
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"