Clustering with Multi-Layer Graphs: A Spectral Perspective

Abstract

Observational data usually comes with a multimodal nature, which means that it can be naturally represented by a multi-layer graph whose layers share the same set of vertices (users) with different edges (pairwise relationships). In this paper, we address the problem of combining different layers of the multi-layer graph for improved clustering of the vertices compared to using layers independently. We propose two novel methods, which are based on joint matrix factorization and graph regularization framework respectively, to efficiently combine the spectrum of the multiple graph layers, namely the eigenvectors of the graph Laplacian matrices. In each case, the resulting combination, which we call a "joint spectrum" of multiple graphs, is used for clustering the vertices. We evaluate our approaches by simulations with several real world social network datasets. Results demonstrate the superior or competitive performance of the proposed methods over state-of-the-art technique and common baseline methods, such as co-regularization and summation of information from individual graphs.

References in corpus (1)

• Fast unfolding of communities in large networks

Cited by in corpus (23)

• Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds
• Community detection in multi-relational data with restricted multi-layer stochastic blockmodel
• Learning Laplacian Matrix in Smooth Graph Signal Representations
• Spectral Clustering of Attributed Multi-relational Graphs
• vGraph: A Generative Model for Joint Community Detection and Node Representation Learning
• Multi-Layer Spectral Clustering Approach to Intentional Islanding In Bulk Power Systems
• Training Robust Graph Neural Networks with Topology Adaptive Edge Dropping
• General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers
• Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
• Graph Signal Processing -- Part I: Graphs, Graph Spectra, and Spectral Clustering
• Multilayer Spectral Graph Clustering via Convex Layer Aggregation: Theory and Algorithms
• Multi-modal image retrieval with random walk on multi-layer graphs
• Spectral clustering via adaptive layer aggregation for multi-layer networks
• Structure-Preserving Community In A Multilayer Network: Definition, Detection, And Analysis
• AMOS: An Automated Model Order Selection Algorithm for Spectral Graph Clustering
• Outlier Edge Detection Using Random Graph Generation Models and Applications
• A variable smoothing for Nonconvexly constrained nonsmooth optimization with application to sparse spectral clustering
• A Systematic Survey on Multi-relational Community Detection
• An Extensible Dashboard Architecture For Visualizing Base And Analyzed Data
• Parameterized Dynamic Cluster Editing
• Scalable Holistic Analysis of Multi-Source, Data-Intensive Problems Using Multilayered Networks
• Efficient Community Detection in Boolean Composed Multiplex Networks
• Diversified Coherent Core Search on Multi-Layer Graphs