Generalizing Downsampling from Regular Data to Graphs

Abstract

Downsampling produces coarsened, multi-resolution representations of data and it is used, for example, to produce lossy compression and visualization of large images, reduce computational costs, and boost deep neural representation learning. Unfortunately, due to their lack of a regular structure, there is still no consensus on how downsampling should apply to graphs and linked data. Indeed reductions in graph data are still needed for the goals described above, but reduction mechanisms do not have the same focus on preserving topological structures and properties, while allowing for resolution-tuning, as is the case in regular data downsampling. In this paper, we take a step in this direction, introducing a unifying interpretation of downsampling in regular and graph data. In particular, we define a graph coarsening mechanism which is a graph-structured counterpart of controllable equispaced coarsening mechanisms in regular data. We prove theoretical guarantees for distortion bounds on path lengths, as well as the ability to preserve key topological properties in the coarsened graphs. We leverage these concepts to define a graph pooling mechanism that we empirically assess in graph classification tasks, providing a greedy algorithm that allows efficient parallel implementation on GPUs, and showing that it compares favorably against pooling methods in literature.

arXiv commentAccepted at AAAI 2023; Extended version with proofs; 15 pages, 3 figures, 5 tables

References in corpus (20)

• Adam: A Method for Stochastic Optimization
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Fast Graph Representation Learning with PyTorch Geometric
• Hierarchical Graph Representation Learning with Differentiable Pooling
• Self-Attention Graph Pooling
• A Gentle Introduction to Deep Learning for Graphs
• TUDataset: A collection of benchmark datasets for learning with graphs
• Towards Sparse Hierarchical Graph Classifiers
• Spectral Clustering with Graph Neural Networks for Graph Pooling
• Structure-Feature based Graph Self-adaptive Pooling
• Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling
• Understanding Attention and Generalization in Graph Neural Networks
• Path Integral Based Convolution and Pooling for Graph Neural Networks
• Clique pooling for graph classification
• How hard is to distinguish graphs with graph neural networks?
• Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs
• HyperANF: Approximating the Neighbourhood Function of Very Large Graphs on a Budget
• Expressiveness and Approximation Properties of Graph Neural Networks
• Maximum Entropy Weighted Independent Set Pooling for Graph Neural Networks
• A Theoretical Comparison of Graph Neural Network Extensions