A Unified Framework for Optimization-Based Graph Coarsening
Manoj Kumar, Anurag Sharma, Sandeep Kumar; 24(118):1−50, 2023.
Abstract
Graph coarsening is a commonly used technique for reducing the dimensionality of large-scale graph machine learning problems. The objective of graph coarsening is to learn a smaller, more manageable graph while preserving the properties of the original graph. Most existing graph coarsening methods only consider the graph matrix, such as adjacency and Laplacian, while ignoring the node features. In this paper, we propose a new optimization-based framework for graph dimensionality reduction that takes both the graph matrix and the node features as input. Our framework jointly learns the coarsened graph matrix and the coarsened feature matrix, while ensuring desired properties. The proposed optimization formulation is a multi-block non-convex problem, which we efficiently solve using block majorization-minimization, log determinant, Dirichlet energy, and regularization frameworks. Our algorithms are provably convergent and applicable to various tasks. We also demonstrate that the learned coarsened graph is similar to the original graph by a small epsilon value. Extensive experiments show the effectiveness of our framework in real-world applications.
[abs]
[code]