Provable Filter for Real-world Graph Clustering

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 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\