Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds
Authors:
- 18 December 2013
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 62 (4) , 905-918
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 multi-layer 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. As an illustrative application of our framework, we use our algorithm in clustering methods and test its performance on several synthetic and real world datasets where it is shown to be superior to baseline schemes and competitive to state-of-the-art techniques. Our generic framework further extends to numerous analysis and learning problems that involve different types of information on graphs.Keywords
All Related Versions
This publication has 39 references indexed in Scilit:
- Community detection via heterogeneous interaction analysisData Mining and Knowledge Discovery, 2011
- Community detection in graphsPhysics Reports, 2010
- Multiway Spectral Clustering: A Margin-Based PerspectiveStatistical Science, 2008
- Modularity and community structure in networksProceedings of the National Academy of Sciences, 2006
- Optimal linear representations of images for object recognitionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- Eigenfaces for RecognitionJournal of Cognitive Neuroscience, 1991
- Application of the Karhunen-Loeve procedure for the characterization of human facesIEEE Transactions on Pattern Analysis and Machine Intelligence, 1990
- Low-dimensional procedure for the characterization of human facesJournal of the Optical Society of America A, 1987
- On Information and SufficiencyThe Annals of Mathematical Statistics, 1951