From Fine to Coarse: Analyzing Degree Distribution in Graph Coarsening
Yuto Kakihara, Shota Inoue, Hiroyuki Ohsaki · 2025
Graph coarsening is a widely used technique for reducing the complexity of large-scale networks while preserving their essential structural properties. However, coarsening alters the degree distribution, a key characteristic of graphs, making it crucial to understand these transformations. In this study, we analyze the impact of various coarsening algorithms—including RM, COARSENET, MGC, LVN, LVE, kron, and HEM—on the degree distribution of undirected graphs. We first develop an analytical model describing how the degree distribution evolves under RM-based coarsening and validate our findings using numerical experiments on diverse graph types. Additionally, we investigate the feasibility of recovering the original degree distribution from the coarsened graph using both analytical methods and graph neural networks. Our results indicate that RM retains the degree distribution more accurately for graphs with low average degree, while COARSENET and MGC cause significant alterations. Although analytical reconstruction performs well for low-degree graphs, its accuracy declines for graphs with higher connectivity. In contrast, graph neural networks consistently achieve high reconstruction accuracy across all coarsening methods, with particularly strong performance when using LVE and kron.