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