提出Leiden-Fusion分区法,让图嵌入分布式训练更高效且无需频繁通信。
Leiden-Fusion Partitioning Method for Effective Distributed Training of Graph Embeddings
- 基于莱登算法改进,通过合并小社区提升子图连通性。
- 确保每个分区无孤立节点,保障图神经网络信息聚合有效。
- 适合大规模图数据训练,显著降低通信开销,提升效率。
在大规模图嵌入训练中,高效的训练框架与分区方法对处理大型网络至关重要。然而,现有同步分布式框架需持续通信以获取其他机器信息,且当前分区方法难以保证子图连通性,存在孤立节点,影响图神经网络(GNN)训练效果,因训练依赖邻居节点的信息聚合。为此,本文提出一种新分区方法Leiden-Fusion,旨在实现最小通信量的大规模图训练。该方法在莱登社区检测算法基础上,引入贪心合并策略,将最小社区与其高度连接的邻近社区合并。该方法保证初始连通图的每个分区均为密集连接子图,且无孤立节点。分区后,可独立训练每个分区的GNN,并最终整合所有嵌入用于节点分类任务,大幅减少网络通信需求,提升分布式图训练效率。我们在多个基准数据集上进行了充分评估,结果表明该方法在保持高图嵌入质量的同时,显著提升了训练效率。
原文摘要 · Abstract (English)
In the area of large-scale training of graph embeddings, effective training frameworks and partitioning methods are critical for handling large networks. However, they face two major challenges: 1) existing synchronized distributed frameworks require continuous communication to access information from other machines, and 2) the inability of current partitioning methods to ensure that subgraphs remain connected components without isolated nodes, which is essential for effective training of GNNs since training relies on information aggregation from neighboring nodes. To address these issues, we introduce a novel partitioning method, named Leiden-Fusion, designed for large-scale training of graphs with minimal communication. Our method extends the Leiden community detection algorithm with a greedy algorithm that merges the smallest communities with highly connected neighboring communities. Our method guarantees that, for an initially connected graph, each partition is a densely connected subgraph with no isolated nodes. After obtaining the partitions, we train a GNN for each partition independently, and finally integrate all embeddings for node classification tasks, which significantly reduces the need for network communication and enhances the efficiency of distributed graph training. We demonstrate the effectiveness of our method through extensive evaluations on several benchmark datasets, achieving high efficiency while preserving the quality of the graph embeddings for node classification tasks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。