Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks

One of the fundamental problems in network analysis is detecting community structure in multi-layer networks, of which each layer represents one type of edge information among the nodes. We propose integrative spectral clustering approaches based on effective convex layer aggregations. Our aggregation methods are strongly motivated by a delicate asymptotic analysis of the spectral embedding of weighted adjacency matrices and the downstream k-means clustering, in a challenging regime where community detection consistency is impossible. In fact, the methods are shown to estimate the optimal convex aggregation, which minimizes the misclustering error under some specialized multi-layer network models. Our analysis further suggests that clustering using Gaussian mixture models is generally superior to the commonly used k-means in spectral clustering. Extensive numerical studies demonstrate that our adaptive aggregation techniques, together with Gaussian mixture model clustering, make the new spectral clustering remarkably competitive compared to several popularly used methods. Supplementary materials for this article are available online.

网络分析领域的核心问题之一，是检测多层网络（multi-layer networks）中的社区结构，其中每一层对应节点间的一类边信息。本文提出基于高效凸层聚合的集成谱聚类（spectral clustering）方法。所提聚合方法的核心动机源自对加权邻接矩阵（weighted adjacency matrix）的谱嵌入（spectral embedding）以及后续k均值聚类（k-means clustering）的精细渐近分析，该分析针对社区检测一致性无法保证的挑战性情形。事实上，实验证明所提方法可估计最优凸聚合方案，在特定多层网络模型下可最小化误聚类误差。进一步的分析表明，在谱聚类任务中，采用高斯混合模型（Gaussian mixture model, GMM）的聚类方法整体性能优于常用的k均值聚类。大量数值实验表明，将自适应聚合技术与高斯混合模型聚类相结合，可使该新型谱聚类方法在与多种主流方法的对比中展现出显著的竞争力。本文的补充材料可在线获取。