On semidefinite relaxations for the block model

Arash A. Amini, Elizaveta LevinaarXiv 2014 · OpenReview

TL;DR

This paper introduces a new, tighter semidefinite programming (SDP) relaxation for fitting the Stochastic Block Model (SBM), a popular tool for community detection in networks. This new method, SDP-1, not only offers improved theoretical guarantees for recovering communities but also works for a broader range of network structures (weakly assortative) than previous approaches.

What Problem Does This Paper Address?

Community detection is a fundamental problem in network analysis, aiming to identify groups of nodes that are more densely connected within their group than to nodes in other groups. The Stochastic Block Model (SBM) is a widely used statistical framework for modeling these communities. However, finding the best SBM fit to real-world network data using maximum likelihood estimation (MLE) is computationally intractable for large networks. While various methods exist, including spectral clustering and previous SDP-based approaches, they often have limitations: spectral methods can struggle with sparse networks, and existing SDP relaxations require strong assumptions about the network's structure (like strong assortativity) or may not be as accurate as desired. This paper addresses the need for a more robust and theoretically sound method for fitting SBMs that can handle a wider variety of network structures and provide more accurate community recovery.

Methods

The authors propose a novel semidefinite programming (SDP) relaxation, termed SDP-1, which is derived from the MLE of the SBM. They frame this and existing SDP relaxations within a unified theoretical framework, viewing them as relaxations of the MLE over different parameter spaces, and highlight a connection to the problem of sparse Principal Component Analysis (PCA).

Key methodological contributions include:

  • SDP-1 Relaxation: This new relaxation is designed to be "tighter" than previous ones, meaning its feasible region is smaller and closer to the true solution space, leading to better performance.
  • Unified Framework: The paper unifies existing SDP relaxations by showing they correspond to different constraints on the SBM parameters, revealing their relationships and limitations.
  • Primal-Dual Witness Construction: The theoretical analysis relies on a powerful proof technique that uses primal-dual solutions to demonstrate consistency (exact recovery of communities).
  • Relaxation of Assortativity: A significant theoretical advance is showing that SDP-1 can recover communities under "weak assortativity" conditions, a less restrictive assumption than the "strong assortativity" required by prior SDP methods.
  • Mixture of SDPs: The paper also explores combining features of different SDPs to achieve greater flexibility in handling both assortativity and block size constraints.

Datasets

  • Dolphins Network: This is a real-world social network dataset used to illustrate the application of SDP-1 to graphon estimation and to compare its performance with other methods.

Key Insights and Ideas

  • Tighter Relaxations Lead to Broader Applicability: The core insight is that a more "tighter" SDP relaxation (SDP-1) not only improves performance but crucially allows for weaker, more realistic assumptions about the network structure (weak assortativity instead of strong assortativity). This significantly expands the types of networks for which accurate community detection is possible.
  • SDPs as a Unified Family: By framing different SDPs within a single framework, the authors reveal their underlying relationships and why some are more powerful than others. This provides a clearer understanding of the landscape of SDP-based community detection.
  • SDP-1's Natural Tendency for Balanced Communities: The proposed SDP-1 relaxation has an inherent tendency to produce communities of similar sizes. This makes it particularly well-suited for applications like network histograms, which are used in graphon estimation.
  • Assortativity is Not Just a Proof Artifact: The paper demonstrates that the strong assortativity requirement for previous SDPs is not merely a limitation of their proof techniques but a fundamental necessity for their success.

Key Results

  • Improved Theoretical Guarantees: SDP-1 achieves strong consistency (exact recovery of communities with high probability) for a wider class of SBMs, specifically weakly assortative models, compared to previous SDPs that required strong assortativity.
  • Empirical Dominance: Experiments show that SDP-1 consistently outperforms other SDP relaxations (SDP-2, SDP-3) and spectral clustering methods (EVT) in terms of accuracy, especially for networks with a large number of communities.
  • Network Histograms: SDP-1 is shown to be an effective tool for fitting network histograms, a method for graphon estimation, providing cleaner community structures than other methods.
  • Failure of SDP-2' without Strong Assortativity: The paper provides theoretical evidence that SDP-2' fails to recover communities when the strong assortativity condition is violated.

Limitations and Future Work

  • Mixed Models: The paper notes that it remains an open question whether an SDP relaxation can effectively handle "mixed models" that contain both assortative and dissortative communities.
  • Computational Cost: While SDPs offer theoretical advantages, their computational cost can still be a factor, although the paper mentions an efficient first-order ADMM implementation.
  • Tuning Parameters: SDP-3, in particular, relies on a tuning parameter that can make it less suitable for certain tasks like histogram estimation.
  • Future Work: The authors suggest exploring the connection to sparse PCA further and investigating how to leverage these SDP relaxations for more complex network structures. They also highlight the potential for applying these methods to other clustering problems.

Summary updated

Abstract

The stochastic block model (SBM) is a popular tool for community detection in networks, but fitting it by maximum likelihood (MLE) involves a computationally infeasible optimization problem. We propose a new semidefinite programming (SDP) solution to the problem of fitting the SBM, derived as a relaxation of the MLE. We put ours and previously proposed SDPs in a unified framework, as relaxations of the MLE over various sub-classes of the SBM, revealing a connection to sparse PCA. Our main relaxation, which we call SDP-1, is tighter than other recently proposed SDP relaxations, and thus previously established theoretical guarantees carry over. However, we show that SDP-1 exactly recovers true communities over a wider class of SBMs than those covered by current results. In particular, the assumption of strong assortativity of the SBM, implicit in consistency conditions for previously proposed SDPs, can be relaxed to weak assortativity for our approach, thus significantly broadening the class of SBMs covered by the consistency results. We also show that strong assortativity is indeed a necessary condition for exact recovery for previously proposed SDP approaches and not an artifact of the proofs. Our analysis of SDPs is based on primal-dual witness constructions, which provides some insight into the nature of the solutions of various SDPs. We show how to combine features from SDP-1 and already available SDPs to achieve the most flexibility in terms of both assortativity and block-size constraints, as our relaxation has the tendency to produce communities of similar sizes. This tendency makes it the ideal tool for fitting network histograms, a method gaining popularity in the graphon estimation literature, as we illustrate on an example of a social networks of dolphins. We also provide empirical evidence that SDPs outperform spectral methods for fitting SBMs with a large number of blocks.
BibTeX
@misc{amini2014semidefinite,
  author = {Arash A. Amini and Elizaveta Levina},
  title = {{On semidefinite relaxations for the block model}},
  year = {2014},
  eprint = {1406.5647},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1406.5647},
}
Figure