Graph coarsening improved by geometric flow based edge weighting
Geometric Flow enhanced Graph Coarsening
Artificial Intelligence
Summary
Graphs are networks made of nodes connected by edges, and analyzing them can be slow for big graphs. The authors found a better way to group nodes by looking not just at direct connections but also at how tightly connected groups of neighbors are. They use a math idea called Ricci curvature to adjust the importance of edges, making it easier to find meaningful clusters. This helps reduce the size of graphs while keeping important structure, speeding up graph-based computations.
What this means in practice
- •For bioinformatics data scientists: Improve protein network analysis by clustering more meaningful groups using edge weights informed by geometric connectivity.
- •For social network analysts: Efficiently reduce large social graphs while preserving community structures through Ricci curvature based edge reweighting for faster network analysis.
Authors
Chaoqun Fei, Guoxuan Li, Tinglve Zhou, Chuanqing Wang, Yangyang Li
Abstract
Recently, researchers have proposed a graph pooling operation, akin to the pooling process in conventional convolutional neural networks (CNN), aimed at reducing the computation cost of Graph convolutional neural networks (GCNNs). While most GCNN-based methods treat graph pooling as a node clustering problem and propose learning a cluster assignment matrix, existing clustering-based pooling methods tend to focus solely on the rough topology information of graphs, neglecting the exploitation of higher-order mutual connections among neighbors. In terms of message passing on graph, the ease of information passing on edges reflects the closeness between neighboring nodes, which significantly relies on the interconnectivity among neighbors. In this study, we address this gap by considering such local connection information and introducing a novel graph pooling method named RicciPool. We introduce discrete graph curvature, particularly Ollivier-Ricci curvature, as a measure of higher-order connectivity around an edge. Subsequently, we construct an Ollivier-Ricci flow formula to reweigh edge weights, leveraging the crucial information provided by Ricci curvature, particularly vital for extracting clusters in graphs. Building upon this foundation, we utilize the spectral clustering technique to learn a new cluster assignment matrix. Experimental results on multiple bioinformatics protein datasets and social networks underscore the effectiveness of our proposed method.