Pairwise Covariates-adjusted Block Model for Community Detection

Sihan Huang, Yang Feng, Feng, YangarXiv 2018 · DOI · arXiv

Abstract

Community detection is a fundamental problem in network science, typically addressed using the Stochastic Block Model (SBM). However, the SBM's assumption of stochastic equivalence—where all nodes in a community share identical connection probabilities—is often too rigid for real-world applications. We introduce the Pairwise Covariates-adjusted Stochastic Block Model (PCABM), a generalization that incorporates edge-level covariate information. By modeling connection rates as a function of both community membership and pairwise data, PCABM achieves superior community detection consistency and flexibility. We provide efficient estimation algorithms, including Spectral Clustering with Adjustment (SCWA), and demonstrate the model's effectiveness on both synthetic and empirical networks.

Introduction

In many real-world networks, connections are not solely determined by group labels. Factors such as geographic distance, shared interests, or individual popularity (degree) play significant roles. While the Degree-Corrected SBM (DCBM) accounts for node-level popularity, it cannot integrate specific pairwise relationships. PCABM fills this gap by allowing researchers to adjust for external "edge-level" information directly within the block model framework.

The PCABM Framework

The core of PCABM lies in modeling the probability of an edge between nodes $i$ and $j$ using a Poisson distribution with rate $\lambda_{ij}$: $$\lambda_{ij} = B_{c_i c_j} \exp(z_{ij}^T \gamma)$$ Here, $B_{c_i c_j}$ represents the baseline block effect between communities, while $\exp(z_{ij}^T \gamma)$ adjusts this baseline based on observed pairwise covariates $z_{ij}$ and their corresponding coefficients $\gamma$.

Algorithmic Contributions

To make this model practical, the authors developed several key tools:

  • Spectral Clustering with Adjustment (SCWA): This algorithm "cleans" the adjacency matrix by removing the estimated effects of covariates before performing spectral clustering, ensuring computational efficiency.
  • Pseudo-Likelihood EM (PLEM): An iterative refinement process that improves community assignment accuracy beyond initial spectral estimates.
  • Edge-sampling Cross-Validation (ECV): A novel framework for model selection (determining the number of communities $K$) and feature selection (identifying relevant covariates).

Key Insights and Ideas

A major theoretical insight of the paper is the relationship between PCABM and existing models. For instance, the authors prove that the popular DCBM is a special case of PCABM where the covariate is the log-product of node degrees.

Furthermore, the paper highlights the importance of understanding the causal relationship between communities and covariates.

Causal structures for covariates-adjusted vs. covariates-confounding scenarios.

As illustrated in the figure above, the model distinguishes between:

  • Covariates-adjusted (a): Both community membership ($c$) and external factors ($Z$) independently drive the network structure ($A$).
  • Covariates-confounding (b): The community structure itself influences the covariates. The authors warn that including such confounded covariates can degrade performance, a problem their ECV algorithm is designed to mitigate.

Experimental Results

The researchers validated PCABM across several contexts:

  • Political Blogs: Using node degrees as a covariate, PCABM matched or exceeded the performance of specialized degree-corrected models.
  • Add Health Friendship Network: By adjusting for different covariates, the model could "switch" perspectives. For example, adjusting for "School" allowed the model to uncover "Race" as the secondary community driver with high accuracy (ARI ~0.91).
  • Consistency: Mathematical proofs and simulations confirmed that as networks grow, PCABM's estimates for both coefficients and community labels converge to their true values.

Conclusion and Future Directions

PCABM offers a flexible and robust framework for community detection that leverages the richness of modern network datasets. While powerful, future work could extend the model to handle high-dimensional covariate sets using Lasso-style penalties or address challenges posed by highly imbalanced community sizes. By decoupling covariate effects from block structures, PCABM provides a clearer lens through which to view complex social and biological networks.

Summary updated

Abstract

One of the most fundamental problems in network study is community detection. The stochastic block model (SBM) is a widely used model, for which various estimation methods have been developed with their community detection consistency results unveiled. However, the SBM is restricted by the strong assumption that all nodes in the same community are stochastically equivalent, which may not be suitable for practical applications. We introduce a pairwise covariates-adjusted stochastic block model (PCABM), a generalization of SBM that incorporates pairwise covariate information. We study the maximum likelihood estimates of the coefficients for the covariates as well as the community assignments. It is shown that both the coefficient estimates of the covariates and the community assignments are consistent under suitable sparsity conditions. Spectral clustering with adjustment (SCWA) is introduced to efficiently solve PCABM. Under certain conditions, we derive the error bound of community detection under SCWA and show that it is community detection consistent. In addition, we investigate model selection in terms of the number of communities and feature selection for the pairwise covariates, and propose two corresponding algorithms. PCABM compares favorably with the SBM or degree-corrected stochastic block model (DCBM) under a wide range of simulated and real networks when covariate information is accessible.
BibTeX
@misc{huang2018pairwise,
  author = {Sihan Huang and Yang Feng and Feng, Yang},
  title = {{Pairwise Covariates-adjusted Block Model for Community Detection}},
  year = {2018},
  eprint = {1807.03469},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1807.03469},
}

Loading related content...

Figure