Messaging for large-scale distributed computation with factor graphs

We present a language for generic computation using Factor Graphs, a computationally convenient data structure abstraction that has been popularly utilized for efficient inference in the framework of probabilistic graphical models cf. [22, 15, 30]. We show that message passing over Factor Graphs is Turing-complete. As an important contribution of this work, we show that a Factor Graph can be realized using any Publisher-Subscriber (PubSub) infrastructure. The resulting computational framework has multiple desirable properties. We utilize different benchmark problems to demonstrate these properties of expressibility, ease of use, and performance, of our Factor Graph Computing framework: (a) Integer Optimization for hard problems, (b) Page-Rank, and (c) Singular Value Decomposition (SVD). We implement Factor Graph Computing on top of two different PubSub systems: Redis's out-of-the-box PubSub and a PubSub that we have built on top of the Ligra graph processing system[25]. Both of these offer single machine Pub- Sub implementations. We find that our single machine implementation is comparable to (a) state-of-the-art commercial optimization solvers [17] for challenge optimization benchmarks [18], (b) native Ligra [251 for large scale PageRank, and (c) a hardware optimized implementation over 68 machine cluster of Apache Spark for computing SVD [11]. In addition, we present a new algorithm for Integer Optimization problems using Belief Propagation, which is of independent interest. Our framework using Factor Graphs brings computation next to data: this removes the communication bottleneck present in modern distributed computation infrastructures

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2018

Author dc:creator

• Ramesh, Vinayak

Advisor dc:contributor.advisor

• Devavrat Shah.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/119774

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/119774