Graph Partition Neural Networks for Semi-Supervised Classification

By Renjie Liao, Marc Brockschmidt, Daniel Tarlow, Alexander L. Gaunt, Raquel Urtasun, Richard S. Zemel. 2018

84 citations recorded by the source corpus.

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 several partitioning algorithms and also propose a novel variant 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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Graph HyperNetworks for Neural Architecture Search (2018, background): “Recently, Liao et al. (2018) found that such propagation scheme is inefﬁcient in passing long-range messages and suffers from the vanishing gradient problem as do regular RNNs.”
Hierarchical Graph Representation Learning with Differentiable Pooling (2018, background): “Since GNNs can efficiently perform messagepassing on dense, clique-like subgraphs (due to their small diameters) [26], pooling together nodes in such a dense subgraph is not likely to lead to any loss of structural information.”
Label Efficient Semi-Supervised Learning via Graph Filtering (2019, background): “Other related works include GraphSAGE [25], graph attention networks [51], attention-based graph neural network [47], graph partition neural networks [36], FastGCN [16], dual graph convolutional neural network [65], stochastic GCN [17], Bayesian GCN [58], deep graph infomax [50], LanczosNet [37], et”
LanczosNet: Multi-Scale Deep Graph Convolutional Networks (2019, methodology): “11 GPNN [40] 12.”
Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving (2020, methodology): “The core computation of GNNs is a parameterized message passing process where methods similar to block-Jacobi scheduling are popular (Liao et al., 2018).”
Reliable Data Distillation on Graph Convolutional Network (2020, methodology): “For comparison, we use the released partitioned datasets for the three citation networks as in [33] and the knowledge graph as in [36].”
A Survey on Deep Semi-Supervised Learning (2021, background): “Subsequently, GCN extensions for SSL started to propagate [193] [194] [195] [196] [197].”
Reviving and Improving Recurrent Back-Propagation (2018, unknown): “We refer to (Li et al., 2016; Liao et al., 2018) for more details.”
Structured Neural Summarization (2018, background): “However, as noted by Liao et al. (2018), GNN-based approaches suffer from a tension between the ability to propagate information across large distances in a graph and the computational expense of the propagation function, which is linear in the number of graph edges per propagation step.”