Covariate-Assisted Community Detection on Sparse Networks

Yaofang Hu, Wanjie WangarXiv 2022 · DOI · arXiv

TL;DR

This paper introduces CA-SCORE, a novel method for community detection in sparse networks that effectively leverages node covariates, even when these covariates don't perfectly align with the network's community structure. CA-SCORE builds upon the degree-corrected stochastic block model (DCSBM) and an "adjusted neighbor-covariate" (ANC) matrix to combine network and covariate information, showing strong performance on both synthetic and real-world datasets.

What Problem Does This Paper Address?

Community detection, the task of identifying groups of nodes that are more densely connected within themselves than to other groups, is a fundamental problem in network analysis. However, many real-world networks are "sparse," meaning they have relatively few connections per node. This sparsity makes it difficult to reliably detect communities using only the network's adjacency information. While node covariates (attributes associated with each node) can help, combining them with network data is challenging, especially when the covariate information might be high-dimensional or not perfectly aligned with the true community structure. This paper aims to bridge this gap by proposing a method that can effectively use covariates to improve community detection in sparse networks, even when the covariate "classes" and network "communities" don't perfectly match.

Methods

The core of this work lies in the proposed Degree-Corrected Stochastic Block Model with Node Covariates (DCSBM-NC). This model allows for variations in node degrees across communities and, crucially, accommodates situations where node covariates might have a different underlying structure than the network communities.

To leverage this model, the authors introduce an Adjusted Neighbor-Covariate (ANC) matrix, denoted as $Y(\alpha)$. This matrix cleverly combines the network's adjacency matrix ($A$) with the node covariate matrix ($X$), incorporating information from a node's neighbors' covariates and the node's own covariates. The weighting of these two sources of information is controlled by a tuning parameter $\alpha$.

Based on the ANC matrix, the paper proposes the Covariate-Assisted Spectral Clustering on Ratios of Eigenvectors (CA-SCORE) method. This algorithm involves computing the singular vectors of the ANC matrix and then applying k-means clustering to these vectors. The method is inspired by existing spectral clustering techniques but adapted to utilize the combined network and covariate information.

Datasets

The paper evaluates its proposed method on two real-world datasets:

  • LastFM app user data: This dataset represents a social network where users are nodes and friendships are edges. Node covariates are derived from the artists each user follows.
  • Citation network data: This dataset consists of academic papers as nodes, with edges representing citations. Node covariates are derived from the abstracts of these papers.

The authors also conduct extensive simulations using both Gaussian and multinomial covariates to test the performance of CA-SCORE under various conditions.

Key Insights and Ideas

  • Covariates as a powerful supplement: Even when network connections are sparse, node covariates can provide crucial information for community detection.
  • Handling misalignment is key: The ability to effectively combine network and covariate information when their underlying structures don't perfectly align is a significant challenge that CA-SCORE addresses.
  • Neighbor information is valuable: The ANC matrix's strategy of incorporating neighbors' covariates is a clever way to propagate information, especially for nodes with few direct connections.
  • Tuning parameter $\alpha$ balances network and covariate influence: The parameter $\alpha$ in the ANC matrix allows for flexible weighting between network structure and covariate information, adapting to different network densities and covariate strengths.
  • Spectral methods remain effective: By adapting spectral clustering to the combined network-covariate information, CA-SCORE maintains computational efficiency while improving accuracy.

Key Results

  • Improved performance on synthetic data: CA-SCORE consistently outperforms methods that rely solely on network structure, especially in sparse settings and when covariates provide useful information.
  • Strong performance on real-world data: On both the LastFM and citation network datasets, CA-SCORE achieves competitive or superior community detection results compared to other state-of-the-art methods. For instance, on the LastFM dataset, CA-SCORE shows significant improvements in error rates and Normalized Mutual Information (NMI) across different country size groups.
  • Theoretical guarantees: The paper provides theoretical guarantees for CA-SCORE's ability to recover community labels under certain conditions, including when the network is relatively dense or when covariate labels closely match community labels.
  • Robustness to tuning: The paper demonstrates that CA-SCORE is relatively robust to the choice of its tuning parameter $\alpha$, and an adaptive method for selecting $\alpha$ is proposed.

Limitations and Future Work

  • High-dimensional covariates and feature screening: While the paper discusses high-dimensional covariates, it suggests that a proper feature screening step might be beneficial. Designing a network-assisted feature screening method for variables with excessive zeros is identified as an area for future exploration.
  • Adaptation of SCORE variants: The authors note that while their work is inspired by SCORE, there are many other SCORE-like methods (e.g., mixed-SCORE, D-SCORE, Hier-SCORE). Adapting and interpreting community structures when node covariates are present in these other frameworks is an exciting avenue for future research.
  • Oracle case analysis: The appendix presents a theorem for the "oracle case" where the ideal model is known. Further work could explore how these results translate to more realistic scenarios where the model parameters are unknown.

Summary updated

Abstract

Community detection is an important problem when processing network data. Traditionally, this is done by exploiting the connections between nodes, but connections can be too sparse to detect communities in many real datasets. Node covariates can be used to assist community detection; see Binkiewicz et al. (2017); Weng and Feng (2022); Yan and Sarkar (2021); Yang et al. (2013). However, how to combine covariates with network connections is challenging, because covariates may be high-dimensional and inconsistent with community labels. To study the relationship between covariates and communities, we propose the degree corrected stochastic block model with node covariates (DCSBM-NC). It allows degree heterogeneity among communities and inconsistent labels between communities and covariates. Based on DCSBM-NC, we design the adjusted neighbor-covariate (ANC) data matrix, which leverages covariate information to assist community detection. We then propose the covariate-assisted spectral clustering on ratios of singular vectors (CA-SCORE) method on the ANC matrix. We prove that CA-SCORE successfully recovers community labels when 1) the network is relatively dense; 2) the covariate class labels match the community labels; 3) the data is a mixture of 1) and 2). CA-SCORE has good performance on synthetic and real datasets. The algorithm is implemented in the R(R Core Team (2021)) package CASCORE.
BibTeX
@misc{hu2022covariate,
  author = {Yaofang Hu and Wanjie Wang},
  title = {{Covariate-Assisted Community Detection on Sparse Networks}},
  year = {2022},
  eprint = {2208.00257},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2208.00257},
}
Figure