UC Davis

The stochastic block model, also known as the planted partition model, is considered a canonical random graph model to study clustering and community detection on network-structured data. Decades of extensive study on the problem have established many profound results, among which the phase transition for weak recovery at Kesten-Stigum threshold is particularly interesting both from a mathematical and an applied point of view. It says that no estimator can perform substantially better than chance on sparse graphs if the model parameter is below the threshold when we have access only to the network topology.

Nevertheless, if we slightly extend the horizon to the ubiquitous semi-supervised setting, such a fundamental limitation will disappear completely. We prove that with arbitrary fraction of the labels revealed, the detection problem is feasible throughout the parameter domain. Moreover, we introduce two efficient algorithms, one combinatorial and one based on optimization, to integrate label information with graph structures. Our work brings a new perspective to stochastic model of networks and semidefinite program research. The foundational change caused by semi-supervised learning demonstrates its indispensable power.

In turn, the mathematically rigorous results help us to develop powerful tools for real-world applications. We propose a variation of graph convolutional network based on our clustering algorithms, which is the first of its kind to incorporate semi-supervised approach in the design of propagation scheme. It utilizes the non-local information that is justified by the learning target. Meanwhile, it captures the essence of cluster structure instead of model statistics. Numerical experiments show it outperforms other models on challenging tasks.