Abstract
We present a convex optimization framework for clustering multiple networks observed on a shared set of nodes. By employing a fusion penalty based on Schatten norms, our method preserves the structural and spectral properties of networks while automatically determining the optimal number of clusters. This approach proves highly effective for detecting changepoints and latent states in network time series, outperforming traditional vectorization-based methods.
Introduction
In modern data science, researchers frequently encounter sequences or collections of networks, such as longitudinal social interactions or brain connectivity maps under varying stimuli. A primary challenge is grouping these related networks into clusters to identify common underlying "regimes."
Traditional clustering methods typically suffer from two major drawbacks: they either vectorize edges, ignoring the inherent structural relationships between nodes, or they rely on overly simplistic summary statistics that discard granular information. Furthermore, standard algorithms like $k$-means require a pre-specified number of clusters ($k$), which is often unknown in practice. This paper introduces a method that respects network structure, handles noise gracefully, and discovers the cluster count naturally through a convex optimization path.
Methodology
The proposed framework extends convex clustering to tensors, representing a collection of $T$ networks as a $p \times p \times T$ data tensor. The optimization problem balances data fidelity (via Frobenius loss) with a fusion penalty that encourages the centroids of similar networks to converge.
The core innovation lies in the use of Schatten-$q$ norms for the fusion penalty. Unlike standard vector penalties, Schatten norms operate on the singular values of the difference matrices. Specifically, the nuclear norm ($q=1$) encourages low-rank differences between clusters, while the spectral norm ($q=\infty$) promotes shared eigenstructures. This allows the algorithm to "see" the spectral properties of the networks. The optimization is solved using an Alternating Direction Method of Multipliers (ADMM) framework, with weights that can be tuned for standard clustering, changepoint detection, or regime-switching identification.
Results and Discussion
The method was evaluated using synthetic datasets, including Stochastic Block Models (SBM) and Graphon-based simulations. In these studies, the convex approach successfully recovered underlying graph models and cluster assignments where $k$-means baselines failed.
Key results indicate that treating networks as matrices rather than vectors is crucial for capturing spectral properties. The resulting "centroids" are weighted graphs that provide a denoised, probabilistic view of the edges within each cluster. Because the objective function is convex, the algorithm produces a continuous "clustering path" as the regularization parameter increases, offering a hierarchical view of the data without requiring multiple restarts for different cluster counts.
Conclusion and Future Work
While the current approach is limited by the computational cost of repeated singular value decompositions and the requirement for aligned nodes across the collection, it represents a significant step forward in network analysis. Future work will focus on scaling the algorithm to massive networks using randomized methods and extending the framework to handle unaligned nodes or non-Gaussian noise structures (such as Poisson distributions for count-based edges).
Summary updated