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
-
2022 Poster: SAPipe: Staleness-Aware Pipeline for Data Parallel DNN Training »
Yangrui Chen · Cong Xie · Meng Ma · Juncheng Gu · Yanghua Peng · Haibin Lin · Chuan Wu · Yibo Zhu -
2022 Spotlight: Lightning Talks 5A-4 »
Yangrui Chen · Zhiyang Chen · Liang Zhang · Hanqing Wang · Jiaqi Han · Shuchen Wu · shaohui peng · Ganqu Cui · Yoav Kolumbus · Noemi Elteto · Xing Hu · Anwen Hu · Wei Liang · Cong Xie · Lifan Yuan · Noam Nisan · Wenbing Huang · Yousong Zhu · Ishita Dasgupta · Luc V Gool · Tingyang Xu · Rui Zhang · Qin Jin · Zhaowen Li · Meng Ma · Bingxiang He · Yangyi Chen · Juncheng Gu · Wenguan Wang · Ke Tang · Yu Rong · Eric Schulz · Fan Yang · Wei Li · Zhiyuan Liu · Jiaming Guo · Yanghua Peng · Haibin Lin · Haixin Wang · Qi Yi · Maosong Sun · Ruizhi Chen · Chuan Wu · Chaoyang Zhao · Yibo Zhu · Liwei Wu · xishan zhang · Zidong Du · Rui Zhao · Jinqiao Wang · Ling Li · Qi Guo · Ming Tang · Yunji Chen -
2022 Spotlight: SAPipe: Staleness-Aware Pipeline for Data Parallel DNN Training »
Yangrui Chen · Cong Xie · Meng Ma · Juncheng Gu · Yanghua Peng · Haibin Lin · Chuan Wu · Yibo Zhu -
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