PyTorch-BigGraph: A Large-scale Graph Embedding System

Adam Lerer, Ledell Wu, Jiajun Shen, Timothée Lacroix, Luca Wehrstedt, Abhijit Bose, Alexander PeysakhovichMLSys 2019 · OpenReview

TL;DR

This paper introduces PyTorch-BigGraph (PBG), a novel system designed to generate embeddings for massive graphs with billions of nodes and trillions of edges, a scale previously unmanageable by existing methods. PBG achieves this by employing graph partitioning and distributed training techniques, enabling comparable embedding quality to smaller-scale methods while drastically reducing memory requirements and training time.

What Problem Does This Paper Address?

Graph-structured data is ubiquitous in modern applications, from social networks to e-commerce platforms. Graph embedding techniques aim to represent nodes as dense vectors, capturing their relationships and enabling downstream machine learning tasks like link prediction and recommendation. However, the sheer scale of real-world graphs—often containing billions of nodes and trillions of edges—poses a significant challenge. Traditional embedding systems struggle with memory limitations (requiring hundreds of gigabytes of RAM just for parameters) and computational bottlenecks, making it infeasible to train on such large datasets. This paper addresses the critical need for a scalable graph embedding system that can handle these massive graphs efficiently.

Methods

PBG introduces several key modifications to traditional multi-relation embedding systems to achieve scalability:

  • Graph Partitioning: PBG divides the graph's nodes into partitions that fit into memory. Edges are then bucketed based on the partitions of their source and destination nodes. This allows training to proceed by processing one bucket (a subset of edges between specific partitions) at a time, significantly reducing memory overhead.
  • Distributed Execution: PBG leverages the partitioning scheme for distributed training. It employs a hybrid approach combining a locking scheme for partitioned embeddings with an asynchronous parameter server for global parameters (like relation operators). This allows multiple machines to train on disjoint sets of partitions concurrently.
  • Efficient Negative Sampling: To optimize training, PBG uses a batched negative sampling strategy. Instead of sampling negatives for each positive edge individually, it reuses sampled negative embeddings within a batch. This reduces memory bandwidth and computational cost, making training faster.
  • Multi-Entity, Multi-Relation Support: PBG is designed to handle complex graphs with multiple entity types and relations, offering per-relation configuration options for features like edge weight and relation operators.

Datasets

The paper evaluates PBG on several large-scale datasets:

  • Social Networks: LiveJournal, Twitter, and YouTube user interaction graphs.
  • Knowledge Graphs: Full Freebase dataset (over 100 million nodes, 2 billion edges) and a subset, FB15k.

The authors note that the full Freebase dataset is used to demonstrate the system's scalability on a large knowledge graph, while social network datasets are used to show performance on typical web-scale graphs.

Key Insights and Ideas

  • Partitioning is Key to Memory Reduction: The paper demonstrates that partitioning the graph's nodes and processing edges in buckets drastically reduces memory requirements. For instance, partitioning the Freebase graph reduced memory consumption by 88%.
  • Distributed Training Offers Significant Speedup: By distributing the partitioned graph across multiple machines, PBG achieves substantial training time reductions. Training on 8 machines sped up the process by a factor of 4 for the Freebase dataset.
  • Batched Negative Sampling is Crucial for Efficiency: The batched negative sampling technique is highlighted as a significant contributor to PBG's speed, especially on large graphs where individual negative sampling becomes a bottleneck.
  • Embedding Quality Remains High: Despite the aggressive scaling techniques, PBG achieves comparable or even superior embedding quality to existing methods on various benchmarks, indicating that the partitioning and distributed training do not compromise performance.
  • ComplEx Models Can Be Sensitive to Partitioning: While PBG generally handles various relation operators well, the paper notes that training ComplEx models with partitioning can be unstable, suggesting this as an area for future research.

Key Results

  • Scalability: PBG successfully trains embeddings on graphs with billions of nodes and trillions of edges, outperforming existing systems in terms of scale.
  • Memory Efficiency: Partitioning reduced memory usage by up to 88% on the Freebase dataset.
  • Speedup: Distributed training on 8 machines accelerated training by a factor of 4 on Freebase. On Twitter, training time decreased linearly with the number of machines.
  • Performance: PBG achieved comparable or better link prediction accuracy and downstream task performance (e.g., user category prediction on YouTube) compared to state-of-the-art methods like DeepWalk and MILE. For example, on LiveJournal, PBG achieved a higher MRR (0.749) than DeepWalk (0.691) and MILE (0.505-0.629) while using significantly less memory.

Limitations and Future Work

  • ComplEx Model Instability: The paper acknowledges that training complex relation operators like ComplEx with partitioning can be unstable, leading to performance variations. Future work could focus on improving the stability and scalability of these more complex models.
  • Larger Graphs and Parallelism: The authors suggest that the benefits of PBG's architecture become even more pronounced on graphs that are 1-2 orders of magnitude larger, where more fine-grained partitioning and parallelism are essential. They hope their work will encourage the release of even larger datasets and further research in this area.
  • Exploration of Other Relation Operators: While PBG supports various relation operators, further investigation into their performance and scaling characteristics within the PBG framework is suggested.

Summary updated

Abstract

Graph embedding methods produce unsupervised node features from graphs that can then be used for a variety of machine learning tasks. Modern graphs, particularly in industrial applications, contain billions of nodes and trillions of edges, which exceeds the capability of existing embedding systems. We present PyTorch-BigGraph (PBG), an embedding system that incorporates several modifications to traditional multi-relation embedding systems that allow it to scale to graphs with billions of nodes and trillions of edges. PBG uses graph partitioning to train arbitrarily large embeddings on either a single machine or in a distributed environment. We demonstrate comparable performance with existing embedding systems on common benchmarks, while allowing for scaling to arbitrarily large graphs and parallelization on multiple machines. We train and evaluate embeddings on several large social network graphs as well as the full Freebase dataset, which contains over 100 million nodes and 2 billion edges.
BibTeX
@inproceedings{lerer2019pytorch,
  author = {Adam Lerer and Ledell Wu and Jiajun Shen and Timothée Lacroix and Luca Wehrstedt and Abhijit Bose and Alexander Peysakhovich},
  title = {{PyTorch-BigGraph: A Large-scale Graph Embedding System}},
  booktitle = {MLSys},
  year = {2019},
  url = {https://openreview.net/forum?id=1ngAYINYBX},
}
Figure