On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications
On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications
复制标题
DOI：
10.1145/3397191
复制
发表时间：
2020-08-01
影响因子：
3.6
通讯作者：
Lee, John Boaz
中科院分区：
文献类型：
--
作者：
Rossi, Ryan A.;Jin, Di;Lee, John Boaz
结构角色定义了一组结构相似的节点，这些节点与集合内部的节点比外部的节点更相似，而社区定义的节点集合在集合内部的连接比集合外部的连接更多。基于结构相似性的角色和基于接近的社区是根本不同但重要的互补概念。最近，结构角色的概念变得越来越重要，由于从保持角色概念的图中学习表示(节点/边嵌入)的工作的激增，结构角色的概念变得越来越重要并获得了很多关注。不幸的是，最近的工作有时混淆了结构角色和社区(基于邻近性)的概念，导致了关于网络嵌入方法能力的误导性或不正确的断言。因此，本文试图澄清结构角色和社区之间的误解和关键区别，并形式化导致基于社区或基于角色的结构嵌入的一般机制(例如，随机行走和特征扩散)。我们从理论上证明了基于这些机制的嵌入方法可以得到基于社区或基于角色的结构嵌入。这些机制通常很容易识别，并可以帮助研究人员快速确定方法是否保留了基于社区或角色的嵌入。此外，它们还作为开发基于社区或基于角色的结构嵌入的新的和改进的方法的基础。最后，我们将分析和讨论基于社区或角色的嵌入最合适的应用程序和数据特征。
Structural roles define sets of structurally similar nodes that are more similar to nodes inside the set than outside, whereas communities define sets of nodes with more connections inside the set than outside. Roles based on structural similarity and communities based on proximity are fundamentally different but important complementary notions. Recently, the notion of structural roles has become increasingly important and has gained a lot of attention due to the proliferation of work on learning representations (node/edge embeddings) from graphs that preserve the notion of roles. Unfortunately, recent work has sometimes confused the notion of structural roles and communities (based on proximity) leading to misleading or incorrect claims about the capabilities of network embedding methods. As such, this article seeks to clarify the misconceptions and key differences between structural roles and communities, and formalize the general mechanisms (e.g., random walks and feature diffusion) that give rise to community- or role-based structural embeddings. We theoretically prove that embedding methods based on these mechanisms result in either community- or role-based structural embeddings. These mechanisms are typically easy to identify and can help researchers quickly determine whether a method preserves community- or role-based embeddings. Furthermore, they also serve as a basis for developing new and improved methods for community- or role-based structural embeddings. Finally, we analyze and discuss applications and data characteristics where community- or role-based embeddings are most appropriate.