FENNEL: Streaming graph partitioning for massive scale graphs

Charalampos Tsourakakis, Christos Gkantsidis, Bozidar Radunovic, Milan Vojnovic

    Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

    159 Citations (Scopus)

    Abstract

    Balanced graph partitioning in the streaming setting is a key problem to enable scalable and efficient computations on massive graph data such as web graphs, knowledge graphs, and graphs arising in the context of online social networks. Two families of heuristics for graph partitioning in the streaming setting are in wide use: place the newly arrived vertex in the cluster with the largest number of neighbors or in the cluster with the least number of non-neighbors. In this work, we introduce a framework which unifies the two seemingly orthogonal heuristics and allows us to quantify the interpolation between them. More generally, the framework enables a well principled design of scalable, streaming graph partitioning algorithms that are amenable to distributed implementations. We derive a novel one-pass, streaming graph partitioning algorithm and show that it yields significant performance improvements over previous approaches using an extensive set of real-world and synthetic graphs. Surprisingly, despite the fact that our algorithm is a one-pass streaming algorithm, we found its performance to be in many cases comparable to the de-facto standard offline software METIS and in some cases even superiror. For instance, for the Twitter graph with more than 1.4 billion of edges, our method partitions the graph in about 40 minutes achieving a balanced partition that cuts as few as 6.8% of edges, whereas it took more than 81/2 hours by METIS to produce a balanced partition that cuts 11.98% of edges. We also demonstrate the performance gains by using our graph partitioner while solving standard PageRank computation in a graph processing platform with respect to the communication cost and runtime.

    Original languageEnglish
    Title of host publicationWSDM 2014 - Proceedings of the 7th ACM International Conference on Web Search and Data Mining
    PublisherACM
    Pages333-342
    Number of pages10
    ISBN (Print)9781450323512
    DOIs
    Publication statusPublished - 2014
    MoE publication typeA4 Article in a conference publication
    EventACM International Conference on Web Search and Data Mining - New York, United States
    Duration: 24 Feb 201428 Feb 2014
    Conference number: 7

    Conference

    ConferenceACM International Conference on Web Search and Data Mining
    Abbreviated titleWSDM
    CountryUnited States
    CityNew York
    Period24/02/201428/02/2014

    Keywords

    • balanced graph partitioning
    • distributed computing
    • streaming

    Fingerprint Dive into the research topics of 'FENNEL: Streaming graph partitioning for massive scale graphs'. Together they form a unique fingerprint.

    Cite this