Add a strongly connected components example

[amatsukawa]

Add a distributed algorithm for computing strongly connected components as an example.

This looks promising: http://www.sandia.gov/~sjplimp/papers/jpdc05.pdf. Rather than use DFS which is hard to parallelize, it finds SCCs using the intuition that the SCC that a vertex belongs to is the intersection of the set of vertices that can reach it and the set of vertices that it can reach.

[amatsukawa]

Three questions:

(1) Where should this code go? Analytics.scala seems to be the closest, but perhaps we should start an example package for graphx like there is for spark? (That file also needs to be cleaned up, which I'm happy to do too)

(2) Is it more idiomatic when writing algorithms to directly use the Graph interface, or to write these algorithms using the Pregel or GraphLab implementations?

(3) Do we have test graphs? #11 seems related.

[jegonzal]

(1) The SCC code should go in Analytics which definitely needs a cleaning. We have a slightly cleaner version in the benchmarks branch.

(2) We had originally planned to implement things on top of GraphLab/Pregel interface but the cool part about GraphX is you can (and should) use whatever is easiest. The GraphOps.scala file contains a collection of other helper functions and if there is a common function you like we can put it in there for others to use as well.

(3) For test graphs we have been using the graphs hosted here: http://snap.stanford.edu (web-Google and soc-Livejournal)

One more thing, we have been doing some refactoring which affects the graph interface (though mostly minor renaming) in the indexedrdd_graphx branch that we hope to merge back to master in the next few days. If you are interested you can work in that branch as well and post any issues you find.

[jegonzal]

Also I think @semihsalihoglu had published some work on a scalable (map-reduce) implementation of SCC and so he may be able to suggest some algorithms.

[jegonzal]

After going over Semih's code some more it looks like he already built an implementation on top of a slightly earlier version of GraphX:

https://github.com/semihsalihoglu/graphx-primitives/blob/graph/graph/src/main/scala/spark/graph/examples/ExampleAlgorithms.scala#L115

It might make sense to collaborate with him on developing the Analytics package further. He is visiting the AMPLab next week so we can help coordinate from Berkeley.

[semihsalihoglu]

Hi everyone,

The tech report that Joey has in mind is this:
http://ilpubs.stanford.edu:8090/1077/ It contains an SCC algorithm and some
optimizations for it for Pregel-like systems. Another algorithm you can
consider implementing is the DCSC algorithm from here:
http://ipdps.cc.gatech.edu/2000/irreg/18000506.pdf, though it won't perform
well on many real-world graphs.

I would be very happy to meet whoever is interested next week when I visit
Berkeley about what I have done and to see what you're working on.

Best,

semih

On Tue, Oct 15, 2013 at 2:41 AM, Joey [email protected] wrote:

After going over Semih's code some more it looks like he already built an
implementation on top of a slightly earlier version of GraphX:

https://github.com/semihsalihoglu/graphx-primitives/blob/graph/graph/src/main/scala/spark/graph/examples/ExampleAlgorithms.scala#L115

It might make sense to collaborate with him on developing the Analytics
package further. He is visiting the AMPLab next week so we can help
coordinate from Berkeley.

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/24#issuecomment-26321300
.

[amatsukawa]

Ah, excellent I will definitely give the tech report a read. The paper I linked is the DCSC algorithm, and a trim step. I would love to meet, if we can figure out a day ahead of time I can actually come to Berkeley and join you in person.

[amatsukawa]

Ok, jotting down more thoughts after taking a look at the algorithms mentioned above and the implementations. The graph-coloring based SCC algorithm is a similar algorithm to SCDC algorithm originally linked in this issue but with greater parallelism, I think it's a great candidate for implementation here.

Taking a look at implementations in Semih's repository, it seems that the algorithms are implemented without using the provided Pregel or GraphLab implementations, but rather directly using an extended Graph interface (with many new methods added to Graph laying on top). For example, one message-passing iteration is implemented here: https://github.com/semihsalihoglu/graphx-primitives/blob/graph/graph/src/main/scala/spark/graph/impl/GraphImplWithPrimitives.scala#L311.

While I think this is a great starting point to use as reference, I am personally more inclined to implement these algorithms on top of the Pregel or GraphLab implementations. I think the latter is a cleaner approach to the problem that frames the algorithm in a view that is more familiar to people.

I am, however, a fan of defining primitive functions/operations commonly seen in graph algorithms (but again, in terms of Pregel or GraphLab). For instance a propagateUntilConvergence(update) function that takes a predicate update: (aggVal, currVal) => boolean that indicates whether we should update the value of a vertex given output from the gather phase, and propagates this updated value to neighbors if appropriate.

What are your thoughts? I'll try to come up with a preliminary implementation of the SCC algorithm as I've framed above by Thursday so we can compare/discuss in person.

[semihsalihoglu]

For the SCC algorithm: I have tried both the DCSC algorithm and Coloring
and ran them on multiple graphs up to 6-7B edges and 500M vertices.
Although both are implementable in a vertex-centric parallel fashion, my
suggestion is to go with Coloring. It converges much faster on real graphs.

For the primitives: I think all the primitives can be implemented on top of
the Pregel and probably GraphLab methods/primitives in GraphX. I am new to
Spark and GraphX, so to familiarize myself with Spark I currently have my
own implementations using Spark primitives but any implementation of the
primitives would work. As a matter of fact, as you say they're actually the
most commonly used Pregel operations that we've used and they can express
the 19 algorithms I've listed in the excel sheet. That's how we derived
them. So one way to think of them is the common compute() functions that
we've seen and a lot of algorithms are just a combination of these
primitives one way or another. We've identified a total of 7 primitives,
and I'm writing up a text and changing my implementation in GraphX to
converge to these 7. I can go over them in our meeting. But overall the
point of the primitives is that it gives those common compute() functions a
higher-level meaningful name, and makes reading and writing the code in our
opinion easier for some primitives (e.g. some of the update functions, such
as updateAnotherVertexBasedOnSelf, or formSupervertices). But of course,
the Pregel primitive is more powerful than the primitives. Again the
primitives can be thought of commonly appearing compute()
functions/operations in distributed algorithms (maybe I should say
distributed bsp algorithms).

I'll have a more detailed writeup and table on the primitives by Thursday.

On Mon, Oct 21, 2013 at 8:01 PM, Akihiro Matsukawa <[email protected]

wrote:

Ok, jotting down more thoughts after taking a look at the algorithms
mentioned above and the implementations. The graph-coloring based SCC
algorithm is a similar algorithm to SCDC algorithm originally linked in
this issue but with greater parallelism, I think it's a great candidate for
implementation here.

Taking a look at implementations in Semih's repository, it seems that the
algorithms are implemented without using the provided Pregel or GraphLab
implementations, but rather directly using an extended Graph interface
(with many new methods added to Graph laying on top). For example, one
message-passing iteration is implemented here:
https://github.com/semihsalihoglu/graphx-primitives/blob/graph/graph/src/main/scala/spark/graph/impl/GraphImplWithPrimitives.scala#L311
.

While I think this is a great starting point to use as reference, I am
personally more inclined to implement these algorithms on top of the
Pregel or GraphLab implementations. I think the latter is a cleaner
approach to the problem that frames the algorithm in a view that is more
familiar to people.

I am, however, a fan of defining primitive functions/operations
commonly seen in graph algorithms (but again, in terms of Pregel or
GraphLab). For instance a propagateUntilConvergence(update) function that
takes a predicate update: (aggVal, currVal) => boolean that indicates
whether we should update the value of a vertex given output from the gather
phase, and propagates this updated value to neighbors if appropriate.

What are your thoughts? I'll try to come up with a preliminary
implementation of the SCC algorithm as I've framed above by Thursday so we
can compare/discuss in person.

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/24#issuecomment-26773974
.