Name
Title | ||
|---|---|---|
A hypergraph-partitioned vertex programming approach for large-scale consensus optimization |
Abstract | ||
|---|---|---|
In modern data science problems, techniques for extracting value from big data require performing large-scale optimization over heterogenous, irregularly structured data. Much of this data is best represented as multi-relational graphs, making vertex-programming abstractions such as those of Pregel and GraphLab ideal fits for modern large-scale data analysis. In this paper, we describe a vertex-programming implementation of a popular consensus optimization technique known as the alternating direction method of multipliers (ADMM) [1]. ADMM consensus optimization allows the elegant solution of complex objectives such as inference in rich probabilistic models. We also introduce a novel hypergraph partitioning technique that improves over the state-of-the-art vertex programming framework and significantly reduces the communication cost by reducing the number of replicated nodes by an order of magnitude. We implement our algorithm in GraphLab and measure scaling performance on a variety of realistic bipartite graphs and a large synthetic voter-opinion analysis application. We show a 50% improvement in running time over the current GraphLab partitioning scheme. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/BigData.2013.6691623 | BigData Conference |
Keywords | DocType | Volume |
optimisation,probabilistic models,multirelational graphs,alternating direction method of multipliers,large scale consensus optimization,hypergraph partitioned vertex programming framework,big data,vertex programming,data structures,data analysis,large scale optimization,admm consensus optimization,large synthetic voter opinion analysis application,large-scale optimization,structured data,realistic bipartite graphs,graphlab partitioning scheme,data science problems,vertex programming abstractions,graph theory,hypergraph partitioning,partitioning methods,large scale data analysis,graphs,consensus optimization | Journal | abs/1308.6823 |
ISSN | Citations | PageRank |
2639-1589 | 6 | 0.47 |
References | Authors | |
10 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hui Miao | 1 | 59 | 7.53 |
| Xiangyang Liu | 2 | 11 | 1.60 |
| Bert Huang | 3 | 563 | 39.09 |
| Lise Getoor | 4 | 4365 | 320.21 |