Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds
Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds
复制标题
DOI：
10.1109/tsp.2013.2295553
复制
发表时间：
2014-02-01
影响因子：
5.4
通讯作者：
Nefedov, Nikolai
中科院分区：
文献类型：
--
作者：
Dong, Xiaowen;Frossard, Pascal;Nefedov, Nikolai
数据集中实体之间的关系通常具有多种性质，例如地理距离、社会关系或社交网络中人们之间的共同兴趣。该信息自然可以通过一组形成全局多层图的加权无向图来建模，其中公共顶点集表示实体，不同层上的边捕获实体在不同模态方面的相似性。在本文中，我们解决了分析多层图的问题，并提出了通过有效合并多种模态提供的信息来对顶点进行聚类的方法。为此，我们建议使用格拉斯曼流形上的子空间分析工具来结合各个图层的特征。由此产生的组合可以被视为原始数据的低维表示，它保留了实体之间不同关系中最重要的信息。作为我们框架的说明性应用，我们在聚类方法中使用我们的算法，并在几个合成和现实世界数据集上测试其性能，结果表明它优于基线方案，并且与最先进的技术具有竞争力。我们的通用框架进一步扩展到涉及图表上不同类型信息的众多分析和学习问题。
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.