Towards Sparse Hierarchical Graph Classifiers

By Cătălina Cangea, Petar Velickovic, Nikola Jovanovic, Thomas Kipf, Pietro Lio'. 2018

291 citations recorded by the source corpus.

Recent advances in representation learning on graphs, mainly leveraging graph convolutional networks, have brought a substantial improvement on many graph-based benchmark tasks. While novel approaches to learning node embeddings are highly suitable for node classification and link prediction, their application to graph classification (predicting a single label for the entire graph) remains mostly rudimentary, typically using a single global pooling step to aggregate node features or a hand-designed, fixed heuristic for hierarchical coarsening of the graph structure. An important step towards ameliorating this is differentiable graph coarsening---the ability to reduce the size of the graph in an adaptive, data-dependent manner within a graph neural network pipeline, analogous to image downsampling within CNNs. However, the previous prominent approach to pooling has quadratic memory requirements during training and is therefore not scalable to large graphs. Here we combine several recent advances in graph neural network design to demonstrate that competitive hierarchical graph classification results are possible without sacrificing sparsity. Our results are verified on several established graph classification benchmarks, and highlight an important direction for future research in graph-based neural networks.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, 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 Graph Learning

Citations in the corpus

Fast Graph Representation Learning with PyTorch Geometric (2019, methodology): “…and ARMA ﬁlter convolutions (Deﬀerrard et al., 2016; Bianchi et al., 2019), GraphSAGE (Hamilton et al., 2017), the attention-based operators GAT (Veličković et al., 2018) and AGNN (Thekumparampil et al., 2018), the Graph Isomorphism Network (GIN) from Xu et al. (2019), and the Approximate…”
Just Jump: Dynamic Neighborhood Aggregation in Graph Neural Networks (2019, methodology): “, ~h v ← ~h v + Θ s ~h(t−1) v (Cangea et al., 2018), or updated using Gated Recurrent Units via ~h (t) v ← GRU(~h(t−1) v ,~h v ) (Cho et al.”
FSPool: Learning Set Representations with Featurewise Sort Pooling (2019, background): “Similarly, Cangea et al. (2018) and Gao & Ji (2019) truncate to a ﬁxed-size set by computing a score for each element and keeping elements with the top-k scores.”
Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks (2021, background): “For instance, TopK pooling (Cangea et al., 2018) can be performed over the vertices of the complex and the higherorder structures associated with the pooled vertices can be maintained at the next layer.”
ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations (2019, methodology): “We use a similar architecture as deﬁned in (Cangea et al. 2018; Lee, Lee, and Kang 2019) which is depicted in Fig.”
EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs (2019, background): “By convention, it takes a matrix X t with many rows as input and produces a matrix Z t with only k rows (see, e.g., (Cangea et al. 2018; Gao and Ji 2019)).”
Deep Representation Learning for Social Network Analysis (2019, background): “DiffPool may suffer from computational issues brought by the computation of soft clustering assignment, which is further addressed in (Cangea et al., 2018).”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, methodology): “Notable instances of this architecture include, e.g., (Duvenaud et al., 2015; Fey et al., 2018; Hamilton et al., 2017; Velickovic et al., 2018), and the spectral approaches proposed in, e.g., (Bruna et al., 2014; Defferrard et al., 2016; Kipf & Welling, 2017; Monti et al., 2017)—all of which…”
BrainGNN: Interpretable Brain Graph Neural Network for fMRI Analysis (2020, methodology): “Design To make sure that down-sampling layers behave idiomatically with respect to different graph sizes and structures, we adopt the approach in Cangea et al. (2018) and Gao and Ji (2019) for reducing graph nodes.”
Single Image 3D Hand Reconstruction with Mesh Convolutions (2019, background): “Therefore, the need for a learnable graph coarsening mechanism [9, 37] naturally arises in our scenario.”
Utilizing graph machine learning within drug discovery and development (2021, methodology): “top-k pooling takes a similar approach, but instead of using an auxiliary learning process to pool nodes, it is used to prune nodes [96, 97].”
MeshCNN: a network with an edge (2019, methodology): “Subsequently, feature computation is performed on top of the edges themselves, while leveraging mesh decimation techniques, such as edge collapse, in a manner that adheres to shape geometry and topology.”
Spectral Clustering with Graph Neural Networks for Graph Pooling (2019, methodology): “…model-free methods that precompute the pooled graphs by leveraging graph-theoretical properties (Bruna et al., 2013; Defferrard et al., 2016), to model-based methods that perform pooling trough a learnable function of the node features (Ying et al., 2018; Cangea et al., 2018; Hongyang Gao, 2019).”
Machine Learning on Graphs: A Model and Comprehensive Taxonomy (2020, unknown): “Other methods use differentiable pooling (Ying et al., 2018b; Cangea et al., 2018; Gao and Ji, 2019; Lee et al., 2019).”
Self-Attention Graph Pooling (2019, background): “Pooling with a dense matrix causes the memory efﬁciency problem, as mentioned by (Cangea et al., 2018).”