Provable Filter for Real-world Graph Clustering
This addresses a practical limitation in graph clustering methods that typically focus only on homophilic graphs, improving applicability for real-world graphs with mixed structural properties.
The paper tackles the problem of graph clustering for real-world graphs that exhibit both homophilic and heterophilic properties, proposing a novel method that constructs separate graphs for homophilic and heterophilic edges to build low-pass and high-pass filters, which achieves superior performance compared to state-of-the-art clustering methods in experiments.
Graph clustering, an important unsupervised problem, has been shown to be more resistant to advances in Graph Neural Networks (GNNs). In addition, almost all clustering methods focus on homophilic graphs and ignore heterophily. This significantly limits their applicability in practice, since real-world graphs exhibit a structural disparity and cannot simply be classified as homophily and heterophily. Thus, a principled way to handle practical graphs is urgently needed. To fill this gap, we provide a novel solution with theoretical support. Interestingly, we find that most homophilic and heterophilic edges can be correctly identified on the basis of neighbor information. Motivated by this finding, 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. Important features are further enhanced by the squeeze-and-excitation block. We validate our approach through extensive experiments on both homophilic and heterophilic graphs. Empirical results demonstrate the superiority of our method compared to state-of-the-art clustering methods.