An End-to-End Deep Learning Architecture for Graph Classification

By Muhan Zhang, Zhicheng Cui, Marion Neumann, Yixin Chen. 2018

1,721 citations recorded by the source corpus.

Neural networks are typically designed to deal with data in tensor forms. In this paper, we propose a novel neural network architecture accepting graphs of arbitrary structure. Given a dataset containing graphs in the form of (G,y) where G is a graph and y is its class, we aim to develop neural networks that read the graphs directly and learn a classification function. There are two main challenges: 1) how to extract useful features characterizing the rich information encoded in a graph for classification purpose, and 2) how to sequentially read a graph in a meaningful and consistent order. To address the first challenge, we design a localized graph convolution model and show its connection with two graph kernels. To address the second challenge, we design a novel SortPooling layer which sorts graph vertices in a consistent order so that traditional neural networks can be trained on the graphs. Experiments on benchmark graph classification datasets demonstrate that the proposed architecture achieves highly competitive performance with state-of-the-art graph kernels and other graph neural network methods. Moreover, the architecture allows end-to-end gradient-based training with original graphs, without the need to first transform graphs into vectors.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Information Systems, Graph Learning

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

In Computer Vision and Pattern Recognition

In Information Systems

In Graph Learning

Citations in the corpus

Strategies for Pre-training Graph Neural Networks (2019, methodology): “READOUT is a permutation-invariant function, such as averaging or a more sophisticated graph-level pooling function (Ying et al., 2018b; Zhang et al., 2018).”
Fast Graph Representation Learning with PyTorch Geometric (2019, methodology): “, 2016), sort pooling (Zhang et al., 2018) or the global soft attention layer from Li et al.”
Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity (2019, neutral): “, 2017), GRAPHSAGE, DGCNN/SORTPOOL (Zhang et al., 2018), SAN (Zhao et al.”
Pre-training Graph Neural Networks with Kernels (2018, neutral): “Note that some of our results are reported from Zhang et al. [2018].”
How Powerful are Graph Neural Networks? (2018, methodology): “…∈ { 1 , 2 , . . . , 6 } ; (2) state-of-the-art deep learning architectures Diffusion-convolutional neural networks (DCNN) (Atwood & Towsley, 2016), PATCHY-SAN (Niepert et al., 2016) and Deep Graph CNN (DGCNN) (Zhang et al., 2018); (3) Anonymous Walk Embeddings (AWL) (Ivanov & Burnaev, 2018).”
Hierarchical Graph Representation Learning with Differentiable Pooling (2018, methodology): “Some recent approaches have also proposed applying CNN architectures to the concatenation of all the node embeddings [29, 39], but this requires a specifying (or learning) a canonical ordering over nodes, which is in general very difficult and equivalent to solving graph isomorphism.”
Provably Powerful Graph Networks (2019, methodology): “We follow the standard 10-fold cross validation protocol and splits from Zhang et al. (2018) and report our results according to the protocol described in Xu et al. (2019 Graph regression results.”
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (2018, methodology): “More refined approaches use differential pooling operators based on sorting (Zhang et al. 2018) and soft assignments (Ying et al.”
Simplifying Graph Convolutional Networks (2019, methodology): “We replace the GCN in DCGCN (Zhang et al., 2018b) with an SGC and get 71.0% and 76.2% on NCI1 and COLLAB datasets (Yanardag & Vishwanathan, 2015) respectively, which is on par with an GCN counterpart, but far behind GIN.”
Devign: Effective Vulnerability Identification by Learning Comprehensive Program Semantics via Graph Neural Networks (2019, methodology): “This kind of approach hinders effective classification over entire graphs [20, 21].”
GroupINN: Grouping-based Interpretable Neural Network for Classification of Limited, Noisy Brain Data (2019, methodology): “There are many variations [10, 14, 43] of how a graph convolutional layer is designed.”
On Explainability of Graph Neural Networks via Subgraph Explorations (2021, background): “…the performance of deep graph models, such as graph convolution (Kipf & Welling, 2017; Gilmer et al., 2017; Gao et al., 2018; Wang et al., 2020; Yuan & Ji, 2021), graph attention (Veliˇckovi´c et al., 2018; Wang et al., 2019), and graph pooling (Yuan & Ji, 2020; Gao & Ji, 2019; Zhang et al., 2018).”