论文标题
使用图神经网络的子图频率分布估算
Subgraph Frequency Distribution Estimation using Graph Neural Networks
论文作者
论文摘要
小型子图（Graphlets）是描述大型网络基本单元的重要特征。子图频率分布的计算在包括生物学和工程在内的多个领域中具有广泛的应用。不幸的是，由于该任务的固有复杂性，大多数现有方法在计算密集型且效率低下。在这项工作中，我们提出了GNNS，这是一种新型的表示学习框架，该框架利用图形神经网络有效地采样了子图来估算其频率分布。我们的框架包括一个推理模型和一个生成模型，该模型了解节点，子图和图形类型的分层嵌入。借助学习的模型和嵌入，以高度可扩展和并行的方式对子图进行采样，然后根据这些采样的子图执行频率分布估计。最终，与现有方法相比，我们的方法达到了可比的精度和显着的加速三个数量级。
Small subgraphs (graphlets) are important features to describe fundamental units of a large network. The calculation of the subgraph frequency distributions has a wide application in multiple domains including biology and engineering. Unfortunately due to the inherent complexity of this task, most of the existing methods are computationally intensive and inefficient. In this work, we propose GNNS, a novel representational learning framework that utilizes graph neural networks to sample subgraphs efficiently for estimating their frequency distribution. Our framework includes an inference model and a generative model that learns hierarchical embeddings of nodes, subgraphs, and graph types. With the learned model and embeddings, subgraphs are sampled in a highly scalable and parallel way and the frequency distribution estimation is then performed based on these sampled subgraphs. Eventually, our methods achieve comparable accuracy and a significant speedup by three orders of magnitude compared to existing methods.
