Abstract
Community detection is a fundamental unsupervised learning problem for unlabeled networks with broad applications. Most existing algorithms require the number of clusters ($r$) as a pre-set input, which is rarely known in real-world scenarios. This paper introduces SPUR, a semi-definite programming (SDP) approach that simultaneously estimates $r$ and recovers community memberships. We provide theoretical guarantees for exact recovery under "weak assortativity," a more realistic condition than the standard strong assortativity.
Introduction
In network analysis, community detection aims to group nodes based on their connectivity patterns. While spectral clustering and other state-of-the-art methods perform well when the number of communities $r$ is known, their performance drops significantly if $r$ is misspecified. Existing methods to estimate $r$ often involve complex two-stage processes or difficult-to-tune penalty terms that require prior knowledge of model parameters.
The SPUR Method
The researchers propose a convex relaxation approach formulated as a semi-definite program: $$\max \text{trace}(AX) - \lambda \text{trace}(X)$$ subject to $X \succeq 0, X \geq 0, X\mathbf{1} = \mathbf{1}$.
In this formulation, the term $\text{trace}(AX)$ encourages the solution to fit the observed adjacency matrix $A$, while $\lambda \text{trace}(X)$ acts as a penalty on the number of clusters. Since the trace of a normalized clustering matrix corresponds to the number of clusters, varying $\lambda$ allows the model to explore different granularities of community structure.
To automate the selection of $\lambda$, the SPUR algorithm performs a grid search and selects the value that maximizes the "low-rankness" of the solution $X$, specifically by looking at the proportion of leading eigenvalues. This data-driven approach removes the need for manual tuning or prior knowledge of $r$.
Key Insights: Weak Assortativity and Hierarchy
A significant contribution of this work is the proof of exact recovery under weak assortativity. Unlike strong assortativity, which requires nodes to be more connected to their own group than to the rest of the network combined, weak assortativity only requires a node to be more connected to its own group than to any other single group. This is a much more common characteristic of real-world networks.
Furthermore, the method naturally handles hierarchical structures. As shown in the figures, a large $\lambda$ might identify broad "meta-clusters," whereas decreasing $\lambda$ progressively reveals finer sub-communities. This multi-resolution property allows for a more nuanced understanding of network topology.
Experimental Results
The authors validated SPUR on both synthetic Stochastic Block Models (SBM) and real-world benchmarks:
- Synthetic Data: SPUR demonstrated superior robustness in estimating $r$ as the number of clusters increased, outperforming methods like USVT and the Bethe-Hessian.
- Real-World Networks:
- College Football: SPUR estimated 13 clusters (ground truth is 12 conferences), whereas spectral methods estimated only 10.
- Karate Club & Political Books: The algorithm achieved exact recovery of the ground truth clusters.
Conclusion and Future Work
SPUR provides a theoretically grounded and practically effective way to perform community detection without pre-specifying the number of clusters. While the computational cost of SDP is higher than spectral methods, the simultaneous estimation of $r$ and memberships offers a significant advantage in accuracy and interpretability. Future work may focus on improving the scalability for massive networks and providing a formal theoretical framework for the observed multi-resolution properties.
Summary updated