Multilayer Spectral Graph Clustering via Convex Layer Aggregation: Theory and Algorithms

Abstract

Multilayer graphs are commonly used for representing different relations between entities and handling heterogeneous data processing tasks. Non-standard multilayer graph clustering methods are needed for assigning clusters to a common multilayer node set and for combining information from each layer. This paper presents a multilayer spectral graph clustering (SGC) framework that performs convex layer aggregation. Under a multilayer signal plus noise model, we provide a phase transition analysis of clustering reliability. Moreover, we use the phase transition criterion to propose a multilayer iterative model order selection algorithm (MIMOSA) for multilayer SGC, which features automated cluster assignment and layer weight adaptation, and provides statistical clustering reliability guarantees. Numerical simulations on synthetic multilayer graphs verify the phase transition analysis, and experiments on real-world multilayer graphs show that MIMOSA is competitive or better than other clustering methods.

Published at IEEE Transactions on Signal and Information Processing over Networks

References in corpus (14)

• Fast unfolding of communities in large networks
• Natural Scales in Geographical Patterns
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Layer aggregation and reducibility of multilayer interconnected networks
• Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds
• Clustering with Multi-Layer Graphs: A Spectral Perspective
• Consistent estimation of dynamic and multi-layer block models
• Enhanced detectability of community structure in multilayer networks through layer aggregation
• Anomaly Detection in Time Series of Graphs using Fusion of Graph Invariants
• Mesoscopic Structures Reveal the Network Between the Layers of Multiplex Datasets
• Multi-layer graph analysis for dynamic social networks
• Incremental Method for Spectral Clustering of Increasing Orders
• Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
• Information Extraction from Larger Multi-layer Social Networks