Timezone: »
With the emergence of big graphs in a variety of real applications like social networks, machine learning based on distributed graph-computing~(DGC) frameworks has attracted much attention from big data machine learning community. In DGC frameworks, the graph partitioning~(GP) strategy plays a key role to affect the performance, including the workload balance and communication cost. Typically, the degree distributions of natural graphs from real applications follow skewed power laws, which makes GP a challenging task. Recently, many methods have been proposed to solve the GP problem. However, the existing GP methods cannot achieve satisfactory performance for applications with power-law graphs. In this paper, we propose a novel vertex-cut method, called \emph{degree-based hashing}~(DBH), for GP. DBH makes effective use of the skewed degree distributions for GP. We theoretically prove that DBH can achieve lower communication cost than existing methods and can simultaneously guarantee good workload balance. Furthermore, empirical results on several large power-law graphs also show that DBH can outperform the state of the art.
Author Information
Cong Xie (Shanghai Jiao Tong University)
Ling Yan (Shanghai Jiao Tong University)
Wu-Jun Li (Nanjing University)
Zhihua Zhang (Shanghai Jiao Tong University)
More from the Same Authors
-
2021 Poster: Faster Directional Convergence of Linear Neural Networks under Spherically Symmetric Data »
Dachao Lin · Ruoyu Sun · Zhihua Zhang -
2021 Poster: Greedy and Random Quasi-Newton Methods with Faster Explicit Superlinear Convergence »
Dachao Lin · Haishan Ye · Zhihua Zhang -
2018 Poster: Proximal SCOPE for Distributed Sparse Learning »
Shenyi Zhao · Gong-Duo Zhang · Ming-Wei Li · Wu-Jun Li -
2012 Poster: Nonconvex Penalization, Levy Processes and Concave Conjugates »
Zhihua Zhang · Bojun Tu -
2012 Poster: A Scalable CUR Matrix Decomposition Algorithm: Lower Time Complexity and Tighter Bound »
Shusen Wang · Zhihua Zhang -
2012 Poster: Isotropic Hashing »
Weihao Kong · Wu-Jun Li -
2009 Poster: Probabilistic Relational PCA »
Wu-Jun Li · Dit-Yan Yeung · Zhihua Zhang -
2009 Spotlight: Probabilistic Relational PCA »
Wu-Jun Li · Dit-Yan Yeung · Zhihua Zhang -
2009 Poster: Optimal Scoring for Unsupervised Learning »
Zhihua Zhang · guang dai -
2008 Poster: Posterior Consistency of the Silverman g-prior in Bayesian Model Choice »
Zhihua Zhang · Michael Jordan · Dit-Yan Yeung -
2008 Spotlight: Posterior Consistency of the Silverman g-prior in Bayesian Model Choice »
Zhihua Zhang · Michael Jordan · Dit-Yan Yeung