Graph-based Semi-supervised Local Clustering with Few Labeled Nodes

Graph-based Semi-supervised Local Clustering with Few Labeled Nodes

Zhaiming Shen, Ming-Jun Lai, Sheng Li

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 4190-4198. https://doi.org/10.24963/ijcai.2023/466

Local clustering aims at extracting a local structure inside a graph without the necessity of knowing the entire graph structure. As the local structure is usually small in size compared to the entire graph, one can think of it as a compressive sensing problem where the indices of target cluster can be thought as a sparse solution to a linear system. In this paper, we apply this idea based on two pioneering works under the same framework and propose a new semi-supervised local clustering approach using only few labeled nodes. Our approach improves the existing works by making the initial cut to be the entire graph and hence overcomes a major limitation of the existing works, which is the low quality of initial cut. Extensive experimental results on various datasets demonstrate the effectiveness of our approach.
Keywords:
Machine Learning: ML: Clustering
Data Mining: DM: Mining graphs
Machine Learning: ML: Semi-supervised learning