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

DOI10.1109/TSP.2013.2295553zbMATH Open1394.94973arXiv1303.2221OpenAlexW2059861509MaRDI QIDQ4579005FDOQ4579005

Pascal Frossard, P. Vandergheynst, Xiaowen Dong, N. N. Nefedov

Publication date: 22 August 2018

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1303.2221

Mathematics Subject Classification ID

Applications of graph theory to circuits and networks (94C15)

Cited In (16)

• Subclass graph embedding and a marginal Fisher analysis paradigm
• Nonsmooth nonconvex optimization on Riemannian manifolds via bundle trust region algorithm
• Title not available (Why is that?)
• A common variable minimax theorem for graphs
• Learning robust affinity graph representation for multi-view clustering
• Community detection with dependent connectivity
• Learning a consensus affinity matrix for multi-view clustering via subspaces merging on Grassmann manifold
• Embedding graphs on Grassmann manifold
• A random effects stochastic block model for joint community detection in multiple networks with applications to neuroimaging
• Mutual structure learning for multiple kernel clustering
• Title not available (Why is that?)
• Nonconvex weak sharp minima on Riemannian manifolds
• Link prediction in dynamic networks using random dot product graphs
• A Riemannian Gradient Sampling Algorithm for Nonsmooth Optimization on Manifolds
• Constrained spectral clustering via multi-layer graph embeddings on a Grassmann manifold
• Manifold Optimization-Assisted Gaussian Variational Approximation

This page was built for publication: Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4579005)