Transforming PageRank into an Infinite-Depth Graph Neural Network
Popular graph neural networks are shallow models, despite the success of very
deep architectures in other application domains of deep learning. This reduces
the modeling capacity and leaves models unable to capture long-range
relationships. The primary reason for the shallow design results from
over-smoothing, which leads node states to become more similar with increased
depth. We build on the close connection between GNNs and PageRank, for which
personalized PageRank introduces the consideration of a personalization vector.
Adopting this idea, we propose the Personalized PageRank Graph Neural Network
(PPRGNN), which extends the graph convolutional network to an infinite-depth
model that has a chance to reset the neighbor aggregation back to the initial
state in each iteration. We introduce a nicely interpretable tweak to the
chance of resetting and prove the convergence of our approach to a unique
solution without placing any constraints, even when taking infinitely many
neighbor aggregations. As in personalized PageRank, our result does not suffer
from over-smoothing. While doing so, time complexity remains linear while we
keep memory complexity constant, independently of the depth of the network,
making it scale well to large graphs. We empirically show the effectiveness of
our approach for various node and graph classification tasks. PPRGNN
outperforms comparable methods in almost all cases.