Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling

Abstract

In graph neural networks (GNNs), pooling operators compute local summaries of input graphs to capture their global properties, and they are fundamental for building deep GNNs that learn hierarchical representations. In this work, we propose the Node Decimation Pooling (NDP), a pooling operator for GNNs that generates coarser graphs while preserving the overall graph topology. During training, the GNN learns new node representations and fits them to a pyramid of coarsened graphs, which is computed offline in a pre-processing stage. NDP consists of three steps. First, a node decimation procedure selects the nodes belonging to one side of the partition identified by a spectral algorithm that approximates the \maxcut{} solution. Afterwards, the selected nodes are connected with Kron reduction to form the coarsened graph. Finally, since the resulting graph is very dense, we apply a sparsification procedure that prunes the adjacency matrix of the coarsened graph to reduce the computational cost in the GNN. Notably, we show that it is possible to remove many edges without significantly altering the graph structure. Experimental results show that NDP is more efficient compared to state-of-the-art graph pooling operators while reaching, at the same time, competitive performance on a significant variety of graph classification tasks.

References in corpus (23)

• Adam: A Method for Stochastic Optimization
• Distributed Representations of Words and Phrases and their Compositionality
• Inductive Representation Learning on Large Graphs
• An Empirical Evaluation of Generic Convolutional and Recurrent Networks for Sequence Modeling
• Neural Message Passing for Quantum Chemistry
• Geometric deep learning: going beyond Euclidean data
• WaveNet: A Generative Model for Raw Audio
• Spectral Networks and Locally Connected Networks on Graphs
• Discrete Signal Processing on Graphs
• Hierarchical Graph Representation Learning with Differentiable Pooling
• Graph Neural Networks with convolutional ARMA filters
• Self-Attention Graph Pooling
• How Powerful are Graph Neural Networks?
• Convolutional Neural Network Architectures for Signals Supported on Graphs
• Towards Sparse Hierarchical Graph Classifiers
• Edge Contraction Pooling for Graph Neural Networks
• Learning Backtrackless Aligned-Spatial Graph Convolutional Networks for Graph Classification
• Graph Neural Networks in TensorFlow and Keras with Spektral
• Wasserstein Weisfeiler-Lehman Graph Kernels
• Walk-Steered Convolution for Graph Classification
• An Agent-Based Algorithm exploiting Multiple Local Dissimilarities for Clusters Mining and Knowledge Discovery
• Towards Interpretable Sparse Graph Representation Learning with Laplacian Pooling
• Learning Vertex Convolutional Networks for Graph Classification

Cited by in corpus (7)

• Understanding Pooling in Graph Neural Networks
• Superpixel perception graph neural network for intelligent defect detection of aero-engine blade
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification
• Generalizing Downsampling from Regular Data to Graphs
• Learning Hierarchical Graph Neural Networks for Image Clustering
• Maximal Independent Sets for Pooling in Graph Neural Networks
• RFC-HyPGCN: A Runtime Sparse Feature Compress Accelerator for Skeleton-Based GCNs Action Recognition Model with Hybrid Pruning