Multi-Component Coarsened Graph Learning for Scaling Graph Machine Learning

Graph coarsening is a reduction technique that approximates a larger graph to a smaller tractable graph. A good quality graph representation with specific properties is needed to achieve good performance with downstream applications. However, existing coarsening methods could not coarsen graphs with desirable properties, such as sparsity, tree, bipartite structure, or multi-component structure. This work presents an optimization framework for learning coarsened graphs with desirable multi-component structure. The proposed methods are solved efficiently by leveraging block majorization-minimization, log determinant, and spectral regularization frameworks. Extensive experiments with real benchmark datasets elucidate the proposed framework's efficacy in preserving the structure in coarsened graphs. Empirically, when there is no prior knowledge available regarding the graph's structure, constructing a multicomponent coarsened graph consistently outperforms state-of-the-art methods.