Provable Filter for Real-World Graph Clustering
针对真实世界图结构兼具同质与异质性的问题，提出一种基于邻居信息识别边类型并构建高低通滤波器的聚类方法，理论分析滤波器与聚类性能的关系，实验表明在异质和同质图上分别提升1.82%和0.83%的准确率。
Graph clustering, an important unsupervised problem, has been shown to be more resistant to advances in graph neural networks (GNNs). Most existing methods focus on homophilic graphs and ignore heterophily. This significantly limits their applicability, since real-world graphs exhibit a structural disparity and cannot simply be classified as homophily and heterophily. To fill this gap, we provide a principled way to handle practical graphs. Interestingly, we find that most homophilic and heterophilic edges can be correctly identified on the basis of neighbor information. Motivated by it, we construct two graphs that are highly homophilic and heterophilic, respectively. They are used to build low-pass and high-pass filters to capture holistic information. We make the first attempt to provide a theoretical analysis connecting the relationship between filters and clustering performance. Important features are further enhanced by the squeeze-and-excitation (SE) block. We validate our approach through extensive experiments on both homophilic and heterophilic graphs, as well as a co-saliency detection application. Empirical results demonstrate the superiority of our method compared to state-of-the-art clustering methods. In particular, our method achieves an average accuracy improvement of 1.82% on heterophilic graphs and 0.83% on homophilic graphs compared to the best baselines, including RGSL and DGCN.