PREDICT THEN PROPAGATE: GRAPH NEURAL NETWORKS MEET PERSONALIZED PAGERANK
Neural message passing algorithms for semi-supervised classification on graphs have recently achieved great success. However, for classifying a node these methods only consider nodes that are a few propagation steps away and the size of this utilized neighborhood is hard to extend. In this paper, we use the relationship between graph convolutional networks (GCN) and PageRank to derive an improved propagation scheme based on personalized PageRank. We utilize this propagation procedure to construct a simple model, personalized propagation of neural predictions (PPNP), and its fast approximation, APPNP. Our model's training time is on par or faster and its number of parameters on par or lower than previous models. It leverages a large, adjustable neighborhood for classification and can be easily combined with any neural network. We show that this model outperforms several recently proposed methods for semi-supervised classification in the most thorough study done so far for GCN-like models. Our implementation is available online.
The thurst behind this paper is that graph convolutional networks (GCNs) are constrained by construction
to focus on small neighborhoods around any given node. Large neighborhoods introduce in principle
a large number of parameters (while as the authors point out, weight sharing is an option to avoid this issue), 
plus even worse oversmoothing may occur. Specifically, Xu et al. (2018) showed that for a k-layer GCN one can 
think of the influence score of a node x on node y as the probability  that a walker that starts at x, 
lands on y after k steps of random walk (modulo some details). 
Therefore, as k increases the random walks reaches its stationary distribution, forgetting any local information that is useful, 
e.g., for node classification. To avoid this problem, the authors propose the following: use personalized Pagerank
instead of the standard Markov chain of Pagerank. In PPR there is a restart probability, which allows 
their algorithm to avoid “forgetting” the local information around a walk, thus allowing for an arbitrary 
number of steps in their random walk. The authors define two methods PEP, and PEPa based on PPR. The latter 
method is faster in practice since it approximates the PPR.   
A key advantage of the proposed method is the separation of the node embedding part from the propagation scheme. In this sense, 
following the categorization of existing methods into three categories, PEP is a hybrid of message passing algorithms,
and random walk based node embeddings. The experimental evaluation tests certain basic properties of the proposed method. One interesting performance feature of 
PEP and PEPa is that they can perform well using few training examples. This is valuable especially when obtaining labeled
examples is expensive.  Finally, the authors compare their proposed methods against state-of-the-art GCN-based methods.  
Some remarks follow. 
- The idea of using PPR for node embeddings has been suggested in recent prior work “LASAGNE: Locality and structure aware graph node embeddings” 
By Faerman et al.  While according to the authors’ categorization of the existing methods in the intro, LASAGNE 
falls under the “random walk” family  of methods, the authors should compare against it. 
 
- Continuing the previous point,  even simpler baselines would be desirable. How inferior is for instance 
an approach on one-vs-all classification using the approximate personalized Pagerank node embedding and 
support vector machines?  
 
- Also, the authors mention “since our datasets are somewhat similar…”. Please clarify with respect to 
which aspects? Also, please use datasets that are different. For instance, see the LASAGNE paper for 
more datasets that have different number of classes.  
- In the experiments the authors use two layers for fair comparison. Given that one of the advantages of the 
proposed method is the  ability to have more layers without suffering from the GCN shortcomings 
with large neighborhood exploration, it would be interesting to see an experiment where the number of layers is a variable.