PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms

作     者：Etienne, Lasalle Rémi, Vaudaine Titouan, Vayer Pierre, Borgnat Paulo, Gonçalves Rémi, Gribonval Márton, Karsai 

作者机构：Inria ENS de Lyon CNRS Université Claude Bernard Lyon 1 LIP UMR 5668 Lyon69342 cedex 07 France CNRS ENS de Lyon LPENSL UMR5672 LyonF-69342 cedex 07 France Department of Network and Data Science Central European University Vienna1100 Austria National Laboratory for Health Security HUN-REN Alfréd Rényi Institute of Mathematics Budapest1053 Hungary 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2024年

核心收录：

主　　题：Graph algorithms 

摘      要：Clustering the nodes of a graph is a cornerstone of graph analysis and has been extensively studied. However, some popular methods are not suitable for very large graphs: e.g., spectral clustering requires the computation of the spectral decomposition of the Laplacian matrix, which is not applicable for large graphs with a large number of communities. This work introduces PASCO, an overlay that accelerates clustering algorithms. Our method consists of three steps: 1- We compute several independent small graphs representing the input graph by applying an efficient and structure-preserving coarsening algorithm. 2- A clustering algorithm is run in parallel onto each small graph and provides several partitions of the initial graph. 3- These partitions are aligned and combined with an optimal transport method to output the final partition. The PASCO framework is based on two key contributions: a novel global algorithm structure designed to enable parallelization and a fast, empirically validated graph coarsening algorithm that preserves structural properties. We demonstrate the strong performance of PASCO in terms of computational efficiency, structural preservation, and output partition quality, evaluated on both synthetic and real-world graph datasets. Copyright © 2024, The Authors. All rights reserved.