Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds
This work addresses clustering in multi-layer graphs, which is useful for analyzing complex datasets with multiple relationship types, but it is incremental as it builds on existing subspace analysis methods.
The paper tackles the problem of clustering vertices in multi-layer graphs by merging information from multiple modalities using subspace analysis on Grassmann manifolds, resulting in superior or competitive performance on synthetic and real-world datasets compared to baseline and state-of-the-art techniques.
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.