PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphVite: A High-Performance CPU-GPU Hybrid System for Node Embedding

Zhaocheng Zhu, Shizhen Xu, Meng Qu, Jian Tang

arXiv:1903.00757v1cs.LGcs.DCstat.ML

TL;DR

Existing node-embedding systems handled hundreds of thousands to a few million nodes, while scaling to tens or hundreds of millions remained challenging. GraphVite co-optimizes a CPU-GPU system and reports training 51 times faster than the current fastest system without sacrificing performance.

  • Problem

    Existing node-embedding systems process hundreds of thousands or a few million nodes, while scaling to tens or hundreds of millions remains challenging.

    Source: §1 · p. 1

  • Method

    GraphVite generates augmented edge samples online with CPU random walks, trains embeddings through parallel GPU negative sampling, and reduces CPU-GPU synchronization with a collaboration strategy.

    Source: §1 · p. 2

  • Results

    51 times faster than the current fastest system without sacrificing performance.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Experiments on four large networks show faster single-machine node-embedding training without sacrificing performance.

    Source: §7 · p. 10

    Parallel updates rely on ϵ-gradient exchangeability, which bounds the difference from exchanging two gradient-step orders by ϵ for small ϵ.

    Source: §3.2 · p. 4

Abstract

from arXiv · show

Learning continuous representations of nodes is attracting growing interest in both academia and industry recently, due to their simplicity and effectiveness in a variety of applications. Most of existing node embedding algorithms and systems are capable of processing networks with hundreds of thousands or a few millions of nodes. However, how to scale them to networks that have tens of millions or even hundreds of millions of nodes remains a challenging problem. In this paper, we propose GraphVite, a high-performance CPU-GPU hybrid system for training node embeddings, by co-optimizing the algorithm and the system. On the CPU end, augmented edge samples are parallelly generated by random walks in an online fashion on the network, and serve as the training data. On the GPU end, a novel parallel negative sampling is proposed to leverage multiple GPUs to train node embeddings simultaneously, without much data transfer and synchronization. Moreover, an efficient collaboration strategy is proposed to further reduce the synchronization cost between CPUs and GPUs. Experiments on multiple real-world networks show that GraphVite is super efficient. It takes only about one minute for a network with 1 million nodes and 5 million edges on a single machine with 4 GPUs, and takes around 20 hours for a network with 66 million nodes and 1.8 billion edges. Compared to the current fastest system, GraphVite is about 50 times faster without any sacrifice on performance.

1 INTRODUCTION

GraphVite targets the scale limits of existing node-embedding systems with a CPU-GPU design that co-optimizes the algorithm and system. It reports faster training without sacrificing performance.

1 INTRODUCTION

  • Node embeddings support downstream tasks, but existing systems handled only hundreds of thousands to a few million nodes, while larger networks challenge single-machine training.Source: §1 · p. 1
  • GPU adoption faces random network access, large embedding matrices, slow CPU-GPU bus transfers, and costly CPU-GPU or inter-GPU synchronization.Source: §1 · pp. 1–2
  • GraphVite co-optimizes CPU and GPU roles, assigning random-access network augmentation to CPUs and matrix-heavy embedding training to GPUs.Source: §1 · p. 2
  • CPU random walks generate edge samples online; GPU grid-block negative sampling trains disjoint embedding subsets concurrently, while collaboration reduces CPU-GPU sample-pool synchronization.Source: §1 · p. 2
  • 51 times faster than the current fastest system without performance sacrifice, with training taking around 20 hours for 66 million nodes and 1.8 billion edges.Source: §1 · p. 2

2 PRELIMINARIES

Node embedding methods augment networks to create training edges, then learn representations from those samples. The section explains why hybrid systems must address memory, bus-bandwidth, and synchronization constraints.

2.1 Node Embedding Methods Review

  • Random walks or other neighborhood strategies add positive edges, and paired vertex and context vectors use dot products to predict whether sampled edges are positive.Source: §2.1 · p. 2
  • Existing methods separate network augmentation from embedding training, typically parallelizing the stages with CPU threads and asynchronous SGD.Source: §2.1 · pp. 2–3

2.2 Challenges for Hybrid Node Embedding System

  • For a 50-million-node, 1-billion-edge scale-free graph, augmentation needs 373 GB and each embedding matrix 23.8 GB, exceeding typical GPU capacity.Source: §2.2 · p. 3, Table 1 · p. 3
  • Embedding workloads incur O(nd) computation and memory access, making CPU-GPU transfers a bottleneck; frequent synchronization of shared data adds cost.Source: §2.2 · p. 3

3 GRAPHVITE: A HYBRID CPU-GPU NODE EMBEDDING SYSTEM

GraphVite co-optimizes a hybrid CPU-GPU system for node embedding, assigning online network augmentation to CPUs and embedding training to GPUs, with asynchronous collaboration between stages.

3 GRAPHVITE: A HYBRID CPU-GPU NODE EMBEDDING SYSTEM

  • GraphVite combines CPU and GPU strengths through parallel online augmentation, parallel negative sampling, and a collaboration strategy that reduces synchronization cost.Its CPU augmentation and GPU training stages run asynchronously.Source: §3 · pp. 3–4, Figure 1 · p. 3

3.1 Parallel Online Augmentation

  • CPUs generate augmented edge samples on demand from degree-proportional random-walk starts, then use cache-friendly pseudo-shuffling to separate correlated samples across s blocks.Pseudo-shuffling addresses the speed cost of general random-access shuffling; samples are appended sequentially within each block.Source: §3.1 · p. 4

3.2 Parallel Negative Sampling

  • GPU training partitions samples and embeddings into an n × n grid; GPUs update orthogonal blocks concurrently, synchronizing between episodes, with episode size balancing exchangeability against synchronization frequency.Negative samples are drawn only from each GPU’s context rows; more than n partitions can be scheduled in groups of n blocks per episode.Source: §3.2 · pp. 4–5, Figure 2 · p. 5

3.3 Collaboration Strategy

  • Two main-memory sample pools let CPUs augment one pool while GPUs train from the other, reducing synchronization cost and nearly doubling hybrid-system speed.The pools are swapped when CPUs fill a new one.Source: §3.3 · p. 5

3.4 Discussion

  • Discussion details small-granularity sample transfers to make GPU edge-sample memory negligible, fixed context partitions to reduce transfers, and single-GPU support for networks up to 12 million nodes.The single-GPU scope follows from a GPU typically holding at most 12 million node embeddings.Source: §3.4 · p. 6

4 EXPERIMENTS

The experiments assess GraphVite’s efficiency and embedding quality on Youtube and larger networks, across different implementations and hardware configurations.

4.1 Datasets

  • The evaluation uses Youtube, Friendster-small, Hyperlink-PLD, and Friendster, ranging from 1 million to 65 million nodes.Friendster is listed with 1.8 billion edges; Hyperlink-PLD has 623 million edges.Source: §4.1 · p. 6

4.2 Compared Systems

  • Comparisons include CPU-parallel LINE, DeepWalk, and node2vec, plus LINE in OpenNE, a GPU implementation.The study parallelizes LINE’s network augmentation for comparison and uses the fastest in-memory random-walk setting for DeepWalk.Source: §4.2 · p. 6, §4.3 · p. 7

4.3 Implementation Details

  • Following LINE and DeepWalk settings, the method samples 40-edge random walks, partitions vertex and context matrices by degree, and draws negative samples with probability proportional to degree raised to 3/4.The passage states that training uses 4,000 epochs; for the other 3 datasets, it specifies 2-edge walks and 2,000 epochs.Source: §4.3 · pp. 6–7

4.4 Results on Youtube

  • With 4 GPUs, GraphVite trains Youtube in one and a half minutes; with one GPU, it is 19 times faster than LINE.LINE is identified as the fastest existing system in this comparison.Source: §4.4 · p. 7, Table 3 · p. 7
  • GraphVite achieves the best or competitive Youtube node-classification results in most settings, though it falls slightly behind DeepWalk with small training-label percentages.The authors attribute the small-data gap to DeepWalk also using hierarchical softmax.Source: §4.4 · p. 7, Table 4 · p. 7

4.5 Results on Larger Datasets

  • Friendster’s 1.8 billion-edge network trains in less than one day, while existing systems cannot solve networks this large within a week except LINE on Friendster-small.Hyperlink-PLD and Friendster are evaluated with 4 GPUs because their embedding matrices do not fit on one GPU.Source: Table 5 · p. 7, §4.5 · p. 8
  • On larger datasets, GraphVite converges; it significantly outperforms LINE on Friendster-small, reaches 0.943 AUC on Hyperlink-PLD, and about 81.0% Micro-F1 on Friendster.Figure 4 plots performance across training epochs, with LINE shown for reference on Friendster-small.Source: §4.5 · p. 8, Figure 4 · p. 8

5 ABLATION STUDY

The ablations examine GraphVite’s components, shuffle strategy, episode size, scaling, and hardware sensitivity; performance experiments use Youtube with 2% labeled data.

5.1 What is the contribution of each main component?

  • Parallel online augmentation improves embedding quality and slightly accelerates sampling; parallel negative sampling boosts speed about 3 times, while collaboration improves speed without affecting performance.The ablation uses a strong baseline with the same GPU implementation and parallel edge sampling on CPU.Source: §5.1 · pp. 8–9

5.2 Is it necessary to perform pseudo shuffle?

  • All shuffle algorithms improve performance by about 1 percent over no shuffle, but pseudo shuffle adds little overhead while random shuffle and index mapping slow the system several times.The authors identify pseudo shuffle as the best speed-performance trade-off.Source: §5.2 · p. 9, Table 7 · p. 9

5.3 What is a practical choice for episode size?

  • Performance is insensitive to episode size, while larger episodes generally improve speed until very large sizes leave too few episodes; GraphVite uses 2 ∗108 edge samples for Youtube.The authors recommend scaling episode size roughly in proportion to |V| for other networks.Source: §5.3 · p. 9, Figure 5 · p. 9

5.4 What is the speedup w.r.t the numebr of CPUs and GPUs?

  • GraphVite scales almost linearly with CPUs and GPUs, achieving 11× speedup when hardware scales to 20×; synchronization and shared-memory and bus load limit the gain.The reported speedup is about half the theoretical maximum.Source: §5.4 · p. 9, Figure 6 · p. 9

5.5 Does the hardware configuration matter?

  • Moving from the Xeon E5 and Tesla P100 server to the Core i7 and GTX 1080 server increases training time only 1.6×.The paper characterizes these configurations as near the best and worst in current machine-learning servers.Source: §5.5 · pp. 9–10, Table 8 · p. 10

6 RELATED WORK

GraphVite builds on scalable sample-based node embedding methods while changing how augmentation and training are implemented. Its CPU-GPU design addresses limits of CPU-only and mini-batch-SGD systems.

6 RELATED WORK

  • DeepWalk, LINE, node2vec, and VERSE are sample-based methods that the paper identifies as especially scalable.Source: §6 · p. 10
  • Its online augmentation generates decorrelated edge samples with pseudo shuffle, like LINE, without storing the full augmented network.DeepWalk and node2vec use correlated path-derived samples, while GraRep and NetMF use adjacency-matrix powers.Source: §6 · p. 10
  • GraphVite’s parallel negative sampling trains on orthogonal sample blocks without transferring embeddings between workers during an episode, unlike prior shared-memory or context-partitioned approaches.The system focuses on negative sampling for node embedding rather than distributed matrix factorization generally.Source: §6 · p. 10
  • Unlike CPU-parallel systems or GPU systems based on mini-batch SGD, GraphVite collaboratively uses CPUs and GPUs to train node embeddings.The paper describes CPU systems as unable to scale to ten-million-node networks without a large cluster, and mini-batch GPU systems as limited by bus bandwidth.Source: §6 · p. 10
  • Among related word-embedding systems, Wombat supports one GPU, while BlazingText supports multiple GPUs by copying parameter matrices to each.GraphVite partitions parameter matrices across GPUs and avoids sharing rows, reducing per-GPU memory use and synchronization cost.Source: §6 · p. 10

7 CONCLUSION

GraphVite combines CPU-generated online edge samples, multi-GPU parallel negative sampling, and a collaboration strategy to reduce synchronization. Experiments on four large networks show faster training without sacrificing performance.

7 CONCLUSION

  • GraphVite combines parallel online augmentation, multi-GPU negative sampling, and CPU-GPU collaboration, and outperforms existing systems in speed without sacrificing performance.The authors plan to extend the system to semi-supervised settings and graph neural networks.Source: §7 · p. 10

Related papers

Loading 1903.00757v1…