Phase transitions in semisupervised clustering of sparse networks

Abstract

Predicting labels of nodes in a network, such as community memberships or demographic variables, is an important problem with applications in social and biological networks. A recently-discovered phase transition puts fundamental limits on the accuracy of these predictions if we have access only to the network topology. However, if we know the correct labels of some fraction $\alpha$ of the nodes, we can do better. We study the phase diagram of this "semisupervised" learning problem for networks generated by the stochastic block model. We use the cavity method and the associated belief propagation algorithm to study what accuracy can be achieved as a function of $\alpha$. For $k=2$ groups, we find that the detectability transition disappears for any $\alpha >0$, in agreement with previous work. For larger $k$ where a hard but detectable regime exists, we find that the easy/hard transition (the point at which efficient algorithms can do better than chance) becomes a line of transitions where the accuracy jumps discontinuously at a critical value of $\alpha$. This line ends in a critical point with a second-order transition, beyond which the accuracy is a continuous function of $\alpha$. We demonstrate qualitatively similar transitions in two real-world networks.

References in corpus (25)

• Fast unfolding of communities in large networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Resolution limit in community detection
• Stochastic blockmodels and community structure in networks
• Community detection in complex networks using Extremal Optimization
• The Bethe lattice spin glass revisited
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Phase transition in the detection of modules in sparse networks
• Phase Transitions in the Coloring of Random Graphs
• Phase diagram of glassy systems in an external field
• Ideal Glass Transitions by Random Pinning
• Model Selection for Degree-corrected Block Models
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Random Pinning Glass Transition: Hallmarks, Mean-Field Theory and Renormalization Group Analysis
• Community Detection with and without Prior Information
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Phase Transitions in Community Detection: A Solvable Toy Model

Cited by in corpus (22)

• Statistical physics of inference: Thresholds and algorithms
• Structure and inference in annotated networks
• Social significance of community structure: Statistical view
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Community detection in networks with unequal groups
• Network structure, metadata and the prediction of missing nodes and annotations
• Inference via Message Passing on Partially Labeled Stochastic Block Models
• Algorithmic detectability threshold of the stochastic block model
• Transfer learning of phase transitions in percolation and directed percolation
• Mean Field Analysis of Personalized PageRank with Implications for Local Graph Clustering
• Active Learning for Community Detection in Stochastic Block Models
• Weighted Community Detection and Data Clustering Using Message Passing
• Detectability thresholds of general modular graphs
• Neural-prior stochastic block model
• Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries
• Phase transitions and optimal algorithms for semi-supervised classifications on graphs: from belief propagation to graph convolution network
• Efficient inference in stochastic block models with vertex labels
• Large Deviations of Semi-supervised Learning in the Stochastic Block Model
• Active Community Detection with Maximal Expected Model Change
• Mutual Information in Community Detection with Covariate Information and Correlated Networks
• Semi-supervised learning in unbalanced and heterogeneous networks