Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold.

Area of Science:

• Network science
• Statistical inference
• Machine learning

Background:

• The stochastic block model is a fundamental tool for network community detection.
• A critical limitation exists at the Kesten-Stigum threshold, hindering performance on sparse graphs.
• Existing methods struggle with performance below this threshold.

Purpose of the Study:

• To investigate the impact of semi-supervised learning on stochastic block model limitations.
• To demonstrate the feasibility of community detection with partial label information.
• To develop novel algorithms for integrating network structure and labels.

Main Methods:

• Theoretical analysis of the stochastic block model in a semi-supervised context.
• Development of a combinatorial algorithm for label integration.
• Development of an optimization-based algorithm for label integration.

Main Results:

• The fundamental limitation imposed by the Kesten-Stigum threshold is overcome with partial labels.
• Community detection becomes feasible across the entire parameter domain.
• Two efficient algorithms are introduced, leveraging both graph topology and label data.

Conclusions:

• Semi-supervised learning significantly enhances the capabilities of the stochastic block model.
• The proposed algorithms offer practical solutions for community detection in real-world networks.
• This research opens new avenues for network analysis and semidefinite programming.