Algorithm and System Co-design for Efficient Subgraph-based Graph Representation Learning
Algorithm and System Co-design for Efficient Subgraph-based Graph Representation Learning
复制标题
DOI：
10.14778/3551793.3551831
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Haoteng Yin;Muhan Zhang;Yanbang Wang;Jianguo Wang;Pan Li
中科院分区：
文献类型：
--
作者：
Haoteng Yin;Muhan Zhang;Yanbang Wang;Jianguo Wang;Pan Li
基于子图的图表示学习（SGRL）最近被提出来处理规范图神经网络（GNN）遇到的一些基本挑战，并在许多重要的数据科学应用中表现出优势，如链接，关系和模体预测。然而，目前的SGRL方法存在可扩展性问题，因为它们需要为每个训练或测试查询提取子图。最近扩展规范GNN的解决方案可能不适用于SGRL。在这里，我们提出了一个新的框架SUREL可扩展SGRL的共同设计的学习算法和它的系统支持。SUREL采用基于步的子图分解，重用步生成子图，大大减少了子图抽取的冗余，支持并行计算。在六个具有数百万节点和边的同构、异构和高阶图上的实验证明了SUREL的有效性和可扩展性。特别是，与SGRL基线相比，SUREL实现了10倍的速度提升，预测性能相当甚至更好;而与规范GNN相比，SUREL实现了50%的预测精度提升。
Subgraph-based graph representation learning (SGRL) has been recently proposed to deal with some fundamental challenges encountered by canonical graph neural networks (GNNs), and has demonstrated advantages in many important data science applications such as link, relation and motif prediction. However, current SGRL approaches suffer from scalability issues since they require extracting subgraphs for each training or test query. Recent solutions that scale up canonical GNNs may not apply to SGRL. Here, we propose a novel framework SUREL for scalable SGRL by co-designing the learning algorithm and its system support. SUREL adopts walk-based decomposition of subgraphs and reuses the walks to form subgraphs, which substantially reduces the redundancy of subgraph extraction and supports parallel computation. Experiments over six homogeneous, heterogeneous and higher-order graphs with millions of nodes and edges demonstrate the effectiveness and scalability of SUREL. In particular, compared to SGRL baselines, SUREL achieves 10X speed-up with comparable or even better prediction performance; while compared to canonical GNNs, SUREL achieves 50% prediction accuracy improvement.