Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds

Abstract

Relationships between entities in datasets are often of multiple nature, like geographical distance, social relationships, or common interests among people in a social network, for example. This information can naturally be modeled by a set of weighted and undirected graphs that form a global multilayer graph, where the common vertex set represents the entities and the edges on different layers capture the similarities of the entities in term of the different modalities. In this paper, we address the problem of analyzing multi-layer graphs and propose methods for clustering the vertices by efficiently merging the information provided by the multiple modalities. To this end, we propose to combine the characteristics of individual graph layers using tools from subspace analysis on a Grassmann manifold. The resulting combination can then be viewed as a low dimensional representation of the original data which preserves the most important information from diverse relationships between entities. We use this information in new clustering methods and test our algorithm on several synthetic and real world datasets where we demonstrate superior or competitive performances compared to baseline and state-of-the-art techniques. Our generic framework further extends to numerous analysis and learning problems that involve different types of information on graphs.

References in corpus (7)

• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Clustering with Multi-Layer Graphs: A Spectral Perspective
• Learning Multi-modal Similarity
• Multiway Spectral Clustering: A Margin-Based Perspective
• Multimodal diffusion geometry by joint diagonalization of Laplacians

Cited by in corpus (33)

• Discrete Signal Processing on Graphs: Sampling Theory
• Learning graphs from data: A signal representation perspective
• Signal Recovery on Graphs: Variation Minimization
• A Survey on Multi-View Clustering
• Spectral Graph Clustering for Intentional Islanding Operations in Resilient Hybrid Energy Systems
• Phase Transitions in Spectral Community Detection
• Scalable and Robust Sparse Subspace Clustering Using Randomized Clustering and Multilayer Graphs
• Community detection in multiplex networks based on orthogonal nonnegative matrix tri-factorization
• Making Laplacians commute
• Multi-Layer Spectral Clustering Approach to Intentional Islanding In Bulk Power Systems
• Structure fusion based on graph convolutional networks for semi-supervised classification
• A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging
• Neither Global Nor Local: A Hierarchical Robust Subspace Clustering For Image Data
• Link prediction in dynamic networks using random dot product graphs
• Multilayer Spectral Graph Clustering via Convex Layer Aggregation: Theory and Algorithms
• MADMM: a generic algorithm for non-smooth optimization on manifolds
• Detecting Localized Categorical Attributes on Graphs
• Localization, Decomposition, and Dictionary Learning of Piecewise-Constant Signals on Graphs
• Signal Recovery on Graphs: Fundamental Limits of Sampling Strategies
• Graph Fourier Transform based on Directed Laplacian
• Fast Path Localization on Graphs via Multiscale Viterbi Decoding
• Common and Individual Structure of Brain Networks
• Machine Learning Analysis of Complex Networks in Hyperspherical Space
• A common variable minimax theorem for graphs
• The Atlas for the Aspiring Network Scientist
• Heat kernel coupling for multiple graph analysis
• A Systematic Survey on Multi-relational Community Detection
• Multi-View Graph Embedding Using Randomized Shortest Paths
• Embedding Graphs on Grassmann Manifold
• Multilayer Clustered Graph Learning
• Mask Combination of Multi-layer Graphs for Global Structure Inference
• Manifold Optimization Assisted Gaussian Variational Approximation
• Discriminative community detection for multiplex networks