Beyond Asymptotics: Practical Insights into Community Detection in Complex Networks

Gibbs sampling uses the standard hierarchical structure to specify the stochastic block models (Nowicki and Snijders, 2001; Golightly and Wilkinson, 2005; McDaid et al., 2013):

The derivation of conditional distributions can be found in Appendix A.3.

We consider a general variational Bayes method from Zhang (2020), where they consider the optimization problem:

where $\mathcal{S}_{\mathrm{MF}}$ is the mean-field variational class and $\phi_{\bm{\theta}}(\bm{y}):=\frac{1}{(\sqrt{2\pi})^{n^{2}}}\exp\Big{(}-\frac{1}{2}\|\bm{y}-\bm{\theta}\|^{2}\Big{)}$. We can obtain a variational algorithm for the stochastic block model with explicit update formulas thanks to the mean-field assumption. The complete description of the variational class and the algorithm can be found in Appendix A.4.

The variational Expectation-Maximization method (Variational-EM) (Leger, 2016) considers

where $\bm{\alpha}^{\top}\bm{1}=1$ and $\mathcal{F}_{q\ell}$ is the model for community $q$ and $\ell$. A variational form of likelihood is considered as

where $\bm{\tau}_{i}$ is the variational parameters of the multinomial distribution which approximates $\mathbf{Z}_{i,:}{\,|\,}\mathbf{A}$. Details can be found in Appendix A.5.

Spectral Clustering has been successfully applied to various fields for its simplicity and accuracy (Von Luxburg, 2007). In the context of the stochastic block model (SBM), the top $K$ eigenspace of the adjacency matrix exhibits a simplex structure, where each cluster corresponds to a vertex of the simplex (Chen and Gu, 2024). Building on this insight, spectral-based methods have been extended to degree-corrected stochastic block models Karrer and Newman, 2011, leading to the development of approaches such as SCORE (Jin, 2015), one-class SVM (Mao et al., 2018), and regularized spectral clustering (Qin and Rohe, 2013). Although these methods are designed to address broader scenarios than the standard SBM, it remains an open question whether they can effectively handle challenging settings such as community imbalance and sparsity. Given the diversity of spectral clustering techniques, we detail the specific methods considered in this paper and their terminology for clarity.

We consider a broad range of scenarios to evaluate the performance of our methods. For the number of nodes, we use $N=250,500,1000,2000$, representing moderate-sized graphs to larger ones. For the number of communities, we set $K=5,10,20$, ranging from simpler structures to more complex configurations. Notably, even in a balanced dataset, the combination of $N=250$ and $K=20$ poses a significant challenge due to the limited information available for distinguishing a large number of diverse communities. To introduce heterogeneity in the cluster sizes, we adopt the approach outlined in (Zhang et al., 2022). Specifically, let $\bm{\alpha}=(\alpha_{1},\dots,\alpha_{K})$, where

Here, $\beta$ is a heterogeneity parameter controlling the imbalance in cluster sizes. A larger $\beta$ results in a greater imbalance in $\bm{\alpha}$. We set $\beta=0,5,10$ in our experiments to explore varying degrees of heterogeneity. For the kernel probability matrix, we follow a standard assumption in the literature (Lei et al., 2024). The elements of the kernel matrix $\mathbf{B}$ are given by

where $\rho\in(0,2/3)$. We note that $\rho=N^{-1}$ achieves exact recovery in asymptotic theory (Lei et al., 2024). To evaluate performance under varying levels of information, we select $\rho=N^{-1},N^{-0.5},N^{-0.1}$. These values allow us to explore scenarios ranging from weak to strong signal levels, with $N^{-1}$ serving as the threshold for perfect recovery. However, perfect recovery may not always be attainable in finite samples, which is the focus of this study. Specific initialization can be found in Appendix A.1.

In this project, we evaluate the performance of clustering algorithms using the adjusted Rand index (ARI; Hubert and Arabie, 1985) and normalized mutual information (NMI; Strehl and Ghosh, 2002) as metrics. ARI measures how many samples are in the same cluster to see how different the clustering result is from the true value, with range $[-1,1]$. Higher ARI values indicate more accurate clustering. As ARI and NMI yield similar results for our experiments, we focus our analysis of ARI, with results of NMI provided in Appendix A.2.

The results, shown in Figure 1, reveal that the performance of the chosen inference methods varies across scenarios. Note that all methods fail in the sparsest case ($b=1$) so we exclude it in the figure. This highlights a dichotomy between finite-sample performance and the asymptotic guarantees discussed in Lei et al. (2024). We hypothesize that achieving the asymptotic information-theoretic limit requires significantly larger sample sizes.

One of the most peculiar phenomena occurs when $K=10$ or $20$ and $b=0.5$. In this case, the performances of all algorithms improve when $\beta$ increases to $5$ while all methods fail when $\beta=0$. On the one hand, since $\beta=0$ represents a balanced clustering size scenario, this failure likely arises because the sample sizes for individual clusters are too small to extract meaningful information. For instance, spectral clustering when $N=5000$ achieves ARI around $0.15$. This indicates increasing $\beta$ does not necessarily make the task harder, as the latent communities with a larger sample size can be learned more easily due to the imbalance. Hence, an improvement in ARI can be observed as we increase the imbalance of the communities.

Variational Bayes exhibits significantly worse performance under $\beta=0$ compared to other methods. In other scenarios, its performance typically falls between spectral methods and variational EM. We suspect that, under $\beta=0$, the evidence lower bound (ELBO) deviates more substantially from the posterior distribution, resulting in poor performance. Another explanation is that VB may have a slower convergence rate in the balanced scenario. Hence, we recommend using variational-EM instead of variational Bayes for similar computation complexity and better performance.

Among eigenvalue decomposition-based methods, regularized spectral clustering performs the worst, despite claims that it mitigates sparsity. The performances of vanilla spectral clustering and $L_{2}$ normalization are similar, while SCORE dominates. Although a vanilla SBM does not incorporate degree heterogeneity, using $L_{2}$ normalization and SCORE does not degrade performance. The superiority of SCORE may stem from its projection of $K$ dimensional eigenspace into a $K-1$ dimensional space, effectively improving the estimation in larger clusters by trading off smaller ones. This is especially evident in scenarios with $K=5$ and $b=0.1$ for $N=250$ or $500$, where SCORE consistently outperforms all other methods. In a nutshell, We recommend using $L_{2}$ normalization over vanilla spectral clustering for similar performance and its generalizability to degree-corrected stochastic block models. While SCORE dominates all spectral methods in our settings, it may run into stability issues in real-world datasets due to its unique normalization scheme, so further investigation is needed. Nonetheless, SCORE seems to be a plausible recommendation.

Variational EM (VEM) generally outperforms vanilla spectral clustering, despite its reliance on non-convex optimization. We suspect it results from the initialization of spectral clustering and further optimization is capable of finding an improvement of the local maximum near its starting point. Since spectral clustering gives robust results, VEM also gives robust results that are better than spectral clustering. Another interesting discovery of VEM is that in challenging scenarios ($\beta>0$ and $b>0.1$), VEM’s performance deteriorates with increasing $N$, both in terms of median accuracy and variation. We attribute this to two factors. First, the data generation mechanism we adopt in this project yields a drastically different set of data, especially when $N$ is large. As larger $N$ amplifies the variability in the data, we can expect an increase in the variation of the estimation accuracy. Furthermore, VEM may suffer from its optimization landscape when the data has a more complicated structure. The inability to find the global optimum of the nonconvex optimization problem may contribute to its performance deterioration.

We initially conjecture that Gibbs will dominate because variational methods use approximation that leads to error and spectral methods do not vitalize the likelihood information from the model. However, Gibbs outperforms only when both $K$ and $N$ are small. We propose two potential explanations for this phenomenon. First, when $K$ is large, Gibbs may struggle to sample equally from all modes in practice, leading to estimation bias. Second, when $N$ is large, we notice that the performance of Gibbs is only slightly worse than VEM. This may be attributed to the influence of an uninformative prior. As $K$ increases, the effective sample size for each parameter shrinks, giving the prior greater sway in the posterior and subsequently degrading Gibbs sampling performance compared to VEM.