A Provable Framework of Learning Graph Embeddings via Summarization
A Provable Framework of Learning Graph Embeddings via Summarization
复制标题
DOI：
10.1609/aaai.v37i4.25621
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Houquan Zhou;Shenghua Liu;Danai Koutra;Huawei Shen;Xueqi Cheng
中科院分区：
文献类型：
--
作者：
Houquan Zhou;Shenghua Liu;Danai Koutra;Huawei Shen;Xueqi Cheng
给定一个大图，我们可以从一个较小的摘要图中学习它的节点嵌入吗？从原始图和它们的汇总图中学习到的嵌入之间的关系是什么？图表示学习在许多图挖掘应用中起着重要的作用，但学习大规模图的嵌入仍然是一个挑战。最近的工作试图通过图摘要来缓解它，典型地包括三个步骤：通过将节点和边组合成超节点和超边来减小图的大小，学习摘要图上的超节点嵌入，然后恢复原始节点的嵌入。然而，这些步骤背后的理由仍然不明。在这项工作中，我们提出了GELSUMM，一个基于图求和的图形嵌入学习框架，其中我们以封闭的形式展示了从摘要图学习和使用三种著名的图嵌入方法进行恢复的理论基础。通过对真实世界数据集的广泛实验，我们证明，我们的方法可以学习图嵌入与匹配或更好的性能在下游任务。这项工作提供了理论分析，学习节点em。通过归纳总结，有助于解释和理解现有工作的机制。
Given a large graph, can we learn its node embeddings from a smaller summary graph? What is the relationship between embeddings learned from original graphs and their summary graphs? Graph representation learning plays an important role in many graph mining applications, but learning em-beddings of large-scale graphs remains a challenge. Recent works try to alleviate it via graph summarization, which typ-ically includes the three steps: reducing the graph size by combining nodes and edges into supernodes and superedges,learning the supernode embedding on the summary graph and then restoring the embeddings of the original nodes. How-ever, the justification behind those steps is still unknown. In this work, we propose GELSUMM, a well-formulated graph embedding learning framework based on graph sum-marization, in which we show the theoretical ground of learn-ing from summary graphs and the restoration with the three well-known graph embedding approaches in a closed form.Through extensive experiments on real-world datasets, we demonstrate that our methods can learn graph embeddings with matching or better performance on downstream tasks.This work provides theoretical analysis for learning node em-beddings via summarization and helps explain and under-stand the mechanism of the existing works.