  Graph clustering is a fundamental task in graph analysis, and recent advances
in utilizing graph neural networks (GNNs) have shown impressive results.
Despite the success of existing GNN-based graph clustering methods, they often
overlook the quality of graph structure, which is inherent in real-world graphs
due to their sparse and multifarious nature, leading to subpar performance.
Graph structure learning allows refining the input graph by adding missing
links and removing spurious connections. However, previous endeavors in graph
structure learning have predominantly centered around supervised settings, and
cannot be directly applied to our specific clustering tasks due to the absence
of ground-truth labels. To bridge the gap, we propose a novel method called
\textbf{ho}mophily-enhanced structure \textbf{le}arning for graph clustering
(HoLe). Our motivation stems from the observation that subtly enhancing the
degree of homophily within the graph structure can significantly improve GNNs
and clustering outcomes. To realize this objective, we develop two
clustering-oriented structure learning modules, i.e., hierarchical correlation
estimation and cluster-aware sparsification. The former module enables a more
accurate estimation of pairwise node relationships by leveraging guidance from
latent and clustering spaces, while the latter one generates a sparsified
structure based on the similarity matrix and clustering assignments.
Additionally, we devise a joint optimization approach alternating between
training the homophily-enhanced structure learning and GNN-based clustering,
thereby enforcing their reciprocal effects. Extensive experiments on seven
benchmark datasets of various types and scales, across a range of clustering
metrics, demonstrate the superiority of HoLe against state-of-the-art
baselines.
