Testing Clusterability on Labeled Graphs

Graph clustering is a fundamental task in analyzing complex networks, with wide applications in social networks, bioinformatics, and recommendation systems. Traditional clustering methods often focus merely on structural connectivity, which neglect edge labels that provide critical semantic information. Many real-world networks are labeled with vertices and edges carrying additional information in the form of labels. These labels provide crucial insights into the underlying structure and function of the network. Despite the importance of labeled graphs, the problem of testing clusterability on such graphs has been paid limited attention from the viewpoint of property testing. This paper addresses the problem of testing clusterability on labeled graphs, extending the framework for bounded degree graphs. This paper introduces a novel framework for testing clusterability on labeled graphs, integrating both graph structures and label consistency constraints. We introduce a new definition of clusterability that incorporates label information and propose a sublinear-time algorithm to efficiently verify with high probability whether a labeled graph exhibits a high-quality clustering structure, where each cluster is of high internal conductance, low external conductance and contains as many labels as possible. The algorithm achieves currently best query complexity of õ(√n) in expectation, ensuring scalability for large-scale graphs. Our work bridges the gap between traditional graph clustering and the emerging field of labeled graph analysis, providing a theoretical foundation for testing clusterability in labeled networks. Theoretical analysis shows that the tester reliably accepts clusterable graphs and rejects those ϵ-far from clusterability with high probability.