Beyond Rank-1: Discovering Rich Community Structure in Multi-Aspect Graphs
Beyond Rank-1: Discovering Rich Community Structure in Multi-Aspect Graphs
复制标题
DOI：
10.1145/3366423.3380129
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
Ekta Gujral;Ravdeep Pasricha;E. Papalexakis
中科院分区：
文献类型：
--
作者：
Ekta Gujral;Ravdeep Pasricha;E. Papalexakis
真实的多方面或多视图图中的社区是如何构造的？我们如何在一个高维、多方面的图中有效、简洁地总结和探索这些社区，而不丢失重要信息？最先进的研究集中在单个图中的模式，在大型网络的单个快照中识别结构，或者在时间上不断演变的图中识别结构，并随着时间的推移将其缝合。然而，据我们所知，还没有一种方法可以通过联合利用来自各个方面的信息，从多方面图中发现和总结社区结构。多方面/张量社区提取的最新技术仅限于在提取的社区中发现集团结构，甚至更糟的是，在不存在集团结构的地方强加集团结构。在本文中，我们通过授权基于张量的方法从多方面图中提取丰富的社区结构来弥合这一差距。特别是，我们引入了cLL 1，一种新的约束块项张量分解，它通常能够从多方面数据集中提取高于秩1但仍然可解释的结构。随后，我们提出了RichCom，一个社区结构提取和摘要算法，利用cLL 1来识别丰富的社区结构（例如，团、星、链等），同时利用图的不同方面之间的高阶相关性。我们的贡献有四个方面：（a）新颖的算法：我们开发了cLL 1，一个有效的框架，从一般的多方面数据中提取丰富和可解释的结构;（B）图形摘要和探索：我们提供了RichCom，一个摘要和编码方案，以发现和探索cLL 1识别的社区结构;（c）多方面图形生成器：我们提供了一种简单而有效的合成多方面图生成器，以及（d）真实世界的实用性：我们在小型和大型真实的数据集上呈现了经验结果，这些结果证明了与现有技术水平相当或上级的性能。
How are communities in real multi-aspect or multi-view graphs structured? How we can effectively and concisely summarize and explore those communities in a high-dimensional, multi-aspect graph without losing important information? State-of-the-art studies focused on patterns in single graphs, identifying structures in a single snapshot of a large network or in time evolving graphs and stitch them over time. However, to the best of our knowledge, there is no method that discovers and summarizes community structure from a multi-aspect graph, by jointly leveraging information from all aspects. State-of-the-art in multi-aspect/tensor community extraction is limited to discovering clique structure in the extracted communities, or even worse, imposing clique structure where it does not exist. In this paper we bridge that gap by empowering tensor-based methods to extract rich community structure from multi-aspect graphs. In particular, we introduce cLL1, a novel constrained Block Term Tensor Decomposition, that is generally capable of extracting higher than rank-1 but still interpretable structure from a multi-aspect dataset. Subsequently, we propose RichCom, a community structure extraction and summarization algorithm that leverages cLL1to identify rich community structure (e.g., cliques, stars, chains, etc) while leveraging higher-order correlations between the different aspects of the graph. Our contributions are four-fold: (a) Novel algorithm: we develop cLL1, an efficient framework to extract rich and interpretable structure from general multi-aspect data; (b) Graph summarization and exploration: we provide RichCom, a summarization and encoding scheme to discover and explore structures of communities identified by cLL1; (c) Multi-aspect graph generator: we provide a simple and effective synthetic multi-aspect graph generator, and (d) Real-world utility: we present empirical results on small and large real datasets that demonstrate performance on par or superior to existing state-of-the-art.