Presentation Information
[B-16-15]A Study on Graph Coarsening for Approximate Preservation of Markov Flux via Local Node Contraction
◎△Kazuma Aoyama1, Hiroyuki Ohsaki1 (1. Kwansei Gakuin University)
Keywords:
Graph Coarsening,Random Walk
Graph coarsening is a fundamental technique for improving the efficiency of data processing and analysis in large-scale information networks. However, most existing methods mainly focus on preserving static topological structures, such as graph cuts or community structure, and do not necessarily preserve dynamic processes such as random walks. In this study, we propose MAFC (Markov-Flux Coarsening), a local node contraction method for graph coarsening that aims to approximately preserve stationary flux in simple random walks on undirected graphs. The proposed method defines a cost function that combines the similarity of conditional transition probabilities between adjacent supernodes and the strength of internal flux, thereby greedily contracting node pairs while suppressing the loss of approximate lumpability. Experimental results using stochastic block models show that the proposed method can reduce preservation errors in the stationary distribution and the second eigenvalue compared with baseline methods, depending on the parameter setting. These results demonstrate that the proposed method is effective for controllably preserving major dynamic properties of random walks during graph coarsening.