Scalable Graph-Parallel Inference Algorithms and Systems
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
New parallel algorithms combine an asynchronous splash primitive with prioritization, coloring and locking to make loopy belief propagation and Gibbs sampling both faster and correct; a system called graphlab implements these ideas with automatic graph transforms and serializability guarantees. Results include PageRank on a 40M‑user, 1.4B‑edge graph at order‑of‑magnitude speedups, LDA on 2.6M documents (500M tokens) reaching ~110M tokens/sec on 64 machines, and counting 34.8 billion triangles in 15 seconds on 64 machines versus 423 minutes on 1,500.
AI-written summary · about
chapters (28)
- 0:00Start
- 1:18Graphical models provide a common representation
- 1:45Parallel and Distributed Algorithms for Probabilistic Inference
- 2:00Loopy Belief Propagation (Loopy BP)
- 3:32Sequential Computational Structure
- 3:57Hidden Sequential Structure
- 5:04Optimal Sequential Algorithm Running Time
- 6:25Role of model Parameters on Sequential Sub-Problems
- 7:15Optimal Parallel Scheduling
- 8:19The Splash Operation • Generalize the optimal chain algorithm
- 9:20Priorities Determine the Roots
- 10:20Adaptive Belief Propagation
- 11:51Representative Results
- 13:12Gibbs Sampling [Geman & Geman, 1984]
- 14:22The Problem with
- 15:37Three Convergent Parallel Samplers [AISTATS'11]
- 16:52Theorem: Chromatic Sampler
- 17:38Splash Gibbs Sampler
- 19:00Dynamically Prioritized Sampling
- 20:47Structure of Computation
- 21:43The Graph-Parallel Abstraction
- 22:46GraphLab Asynchronous Execution The scheduler determines the order that vertices are executed
- 23:40GraphLab is Serializable
- 24:33Power-Law Degree Distribution
- 26:29Machine Learning and Data-Mining Toolkits
- 26:52PageRank on Twitter Follower Graph
- 27:21Gibbs Sampling for LDA
- 28:18Triangle Counting on Twitter 40M Users, 1.4 Billion Links
related talks
56mGraph Analytic Systems
24mLarge Scale Graph Computation with Apache Giraph
18mEhtsham Elahi, Senior Research Engineer, Netflix @ MLconf SEA
39mThorny path to the Large Scale Graph Processing
44mScalable Algorithmic Primitives for Data Science
11mA Design for Massively Parallel Gibbs Sampling on the GPU via Static and Dynamic(…)
39mThorny path to the Large Scale Graph Processing
29mTed Willke, Senior Principal Engineer & GM, Datacenter Group, Intel