TopoX: Topology Refactorization for Distributed Graph Partitioning and Computation

## Overview

Graph-structured computation is central to applications ranging from language processing to social networks. Natural graphs have skewed power-law distributions of vertex degrees, leading to inefficient partitioning and computation for traditional graph-parallel systems. To address this problem, we design TopoX, a distributed graph processing system that refactorizes the topology of a skewed graph to obtain a more uniform topology suitable for partitioning.

TopoX performs the fusion operation on low-degree vertices that merges a set of neighboring low-degree vertices into a super-vertex (which will be assigned to one machine) to eliminate its inner communication; and performs the fission operation on high-degree vertices that splits a high-degree vertex into a set of sibling sub-vertices (each of which will be assigned to one machine) to evenly distribute the load. TopoX designs the delta-based GAS model to further reduce communication. TopoX is implemented as a separate computation engine of PowerGraph.

## Downloads

Download the source code of TopoX.

## Funding

This work was supported by ...

## Contact us

We welcome feedback, suggestions, patches, and so forth. Send them to ...

Last modified: 13 July, 2017 /