Denoising High-Order Graph Clustering

High-Order Graph (HOG) clustering has received much attention for its advantage of exploiting the rich intrinsic structure of data. However, the construction of HOG involves the generation of a large number of redundant walks, which dilutes the useful walks and thus leads to untrustworthy high-order similarity and, consequently, suboptimal clustering results may be obtained. We formalize this issue as the Weight Explosion (WE) problem. Furthermore, current works rarely focus on exploiting the correlation between multi-order graphs that can capture high-order relations at various levels. In this paper, we first analyze the pattern of redundant walks, also termed as noise, and subsequently propose a novel$h$-length Simple Path Search ($h$-SPS) algorithm to solve the WE problem.$h$-SPS aims to find valid walks to denoise HOG and thus avoids enumerating walks to report the similarity. Regarding the second problem, we propose a multi-order graphs fusion method, which adaptively integrates graphs of varying orders by solving a convex problem. This allows us to capture information across different order levels effectively. Extensive experiments on benchmark datasets demonstrate that our method11https://github.com/YonghaoChen511/DenoHOG can effectively solve the proposed WE problem, while also well exploiting the correlation of multi-order graphs.