Provable Filter for Real-world Graph Clustering
Xuanting Xie Erlin Pan Zhao Kang Wenyu Chen Bingheng Li
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.