.png){kind=icon}
Return
Distributed Hypergraph Processing Using Intersection Graphs
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2020.3022014.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The advent of online applications such as social networks has led to an unprecedented scale of data and complex relationships among data. Hypergraphs are introduced to represent complex relationships that may involve more than two entities. A hypergraph is a generalized form of a graph, where edges are generalized to hyperedges. Each hyperedge may consist of any number of vertices. The flexibility of hyperedges also brings challenges in distributed hypergraph processing. In particular, a hypergraph is more difficult to be partitioned and distributed among k workers with balanced partitions. In this paper, we propose to convert a hypergraph into an intersection graph before partitioning by leveraging the inherent shared relationships among hypergraphs. We explore the intersection graph construction method and the corresponding partition strategy which can achieve the goal of evenly distributing vertices and hyperedges across workers, while yielding a significant communication reduction. We also design a distributed processing framework named Hyraph that can directly run hypergraph analysis algorithms on our intersection graphs. Experimental results on real datasets confirm the effectiveness of our techniques and the efficiency of the Hyraph framework.
Keywords:
Hypergraphs
shared relationships
intersection graphs
distributed processing
graph processing
Journal
IF:
10.4
Papers:
6.9K
Citations:
3.2W
Organization
View more organizations
Cited Papers
A two-dimensional data distribution method for parallel sparse matrix-vector multiplication.png)
SIAM REVIEW
OAAI
SIAM REVIEWIF6.1
OAAIShareSaveShareSaveShareSaveShareSaveShareSave View more