Phase transitions in semisupervised clustering of sparse networks

Area of Science:

• Network science
• Statistical physics
• Machine learning

Background:

• Predicting node labels (e.g., community membership) is crucial for network analysis.
• A known phase transition limits prediction accuracy based solely on network topology.
• Incorporating some labeled nodes (semisupervised learning) can enhance prediction accuracy.

Purpose of the Study:

• Investigate the phase diagram of semisupervised network learning.
• Analyze prediction accuracy as a function of the fraction of labeled nodes (α).
• Examine networks generated by the stochastic block model.

Main Methods:

• Employing the cavity method.
• Utilizing the belief propagation algorithm.
• Studying networks generated by the stochastic block model.

Main Results:

• For two groups (k=2), the detectability transition vanishes with any labeled data (α>0).
• For k>2, the easy/hard transition becomes a line of discontinuous accuracy jumps at a critical α.
• This line terminates in a critical point, leading to a continuous accuracy function for higher α.

Conclusions:

• Semisupervised learning significantly alters prediction accuracy landscapes in networks.
• The nature of the transition from hard to easy detection depends on the number of groups and labeled data.
• Observed transitions are qualitatively consistent in real-world social and biological networks.