Classic Graph Structural Features Outperform Factorization-Based Graph Embedding Methods on Community Labeling
Classic Graph Structural Features Outperform Factorization-Based Graph Embedding Methods on Community Labeling
复制标题
DOI：
10.1137/1.9781611977172.44
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Andrew Stolman;Caleb C. Levy;C. Seshadhri;Aneesh Sharma
中科院分区：
文献类型：
--
作者：
Andrew Stolman;Caleb C. Levy;C. Seshadhri;Aneesh Sharma
图表示学习（也称为图嵌入）是将网络结构合并到机器学习模型中的流行技术。无监督图嵌入方法旨在通过学习每个节点的低维向量表示（嵌入）来捕获图结构。尽管这些嵌入广泛用于各种下游转导式机器学习任务，但很少有原则性分析这种方法对常见任务的有效性。在这项工作中，我们为一类嵌入在成对社区标记的常见任务上的性能提供了实证和理论分析。这是经典社区检测问题的二元变体，旨在构建一个分类器来确定一对顶点是否参与社区。根据我们的基础理解目标，我们专注于一类流行的无监督嵌入技术，这些技术学习顶点邻近矩阵的低秩分解（此类包括 GraRep、DeepWalk、node2vec、NetMF 等方法）。我们对具有基本事实的各种真实和合成图进行社区标签的详细实证分析。在我们研究的所有案例中，通过嵌入特征训练的模型在社区标签上表现不佳。相比之下，具有经典图结构特征的简单逻辑模型轻松优于嵌入模型。为了获得更原则性的理解，我们对这些嵌入在捕获社区结构方面的（无效）有效性进行了理论分析。我们正式证明流行的低维分解方法要么不能产生社区结构，要么只能产生“不稳定”的社区。这些社区在小扰动下本质上是不稳定的。
Graph representation learning (also called graph embeddings) is a popular technique for incorporating network structure into machine learning models. Unsupervised graph embedding methods aim to capture graph structure by learning a low-dimensional vector representation (the embedding) for each node. Despite the widespread use of these embeddings for a variety of downstream transductive machine learning tasks, there is little principled analysis of the effectiveness of this approach for common tasks. In this work, we provide an empirical and theoretical analysis for the performance of a class of embeddings on the common task of pairwise community labeling. This is a binary variant of the classic community detection problem, which seeks to build a classifier to determine whether a pair of vertices participate in a community. In line with our goal of foundational understanding, we focus on a popular class of unsupervised embedding techniques that learn low rank factorizations of a vertex proximity matrix (this class includes methods like GraRep, DeepWalk, node2vec, NetMF). We perform detailed empirical analysis for community labeling over a variety of real and synthetic graphs with ground truth. In all cases we studied, the models trained from embedding features perform poorly on community labeling. In constrast, a simple logistic model with classic graph structural features handily outperforms the embedding models. For a more principled understanding, we provide a theoretical analysis for the (in)effectiveness of these embeddings in capturing the community structure. We formally prove that popular low-dimensional factorization methods either cannot produce community structure, or can only produce ``unstable"communities. These communities are inherently unstable under small perturbations.