You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@mahout.apache.org by Sebastian Schelter <ss...@apache.org> on 2011/11/02 10:24:44 UTC
Goodbye graph algorithms
As you might know I recently started an experimental graph mining
module. I was already concerned at the beginning of this whether
MapReduce is really a suitable platform for (most) graph algorithms.
I'm not content with the performance of the algorithms after some
testing and I'm pretty sure the future of large scale graph processing
is not on MapReduce (but hopefully on a Pregel like platform such as
Giraph).
As we're currently removing clutter and trying to concentrate on the
core algorithms, I suggest to remove all graph algorithms with the
exception of PageRank.
If no one objects with this, I'll start the cleanup in a few days.
--sebastian
Re: Goodbye graph algorithms
Posted by Sebastian Schelter <ss...@apache.org>.
Regarding the graph code I would suggest to just remove it. I doubt
anyone will continue to work on that branch.
--sebastian
On 02.11.2011 14:38, Grant Ingersoll wrote:
> Perhaps it would make sense to move them to a branch? I know we never released them, but it seems a shame for them to be buried in SVN history.
>
> Perhaps we should have an "attic" branch or a "sandbox" branch, where things like this (and Watchmaker) can go to age w/o necessarily being relegated to the big bitbucket in the sky that is previous revisions. I suspect it will be easier for someone to pick up should things improve later than having to dig through SVN history. Besides, one might be careful about drawing conclusions on performance just yet given the state of Hadoop. As the overhead issues get worked through, some of this stuff may not be as bad. I guess the question is, is it the paradigm that is slow or the implementation of the paradigm? (That being said, I do think it's likely the case that this stuff moves to Giraph)
>
>
> On Nov 2, 2011, at 8:49 AM, Sebastian Schelter wrote:
>
>> I was refering to the class of "classical" graph algorithms (like
>> shortest path, min cut, betweeness, triangle enumeration, etc) that Jake
>> was also talking about.
>>
>> --sebastian
>>
>> On 02.11.2011 13:13, Dan Brickley wrote:
>>> On 2 November 2011 10:24, Sebastian Schelter <ss...@apache.org> wrote:
>>>> As you might know I recently started an experimental graph mining
>>>> module. I was already concerned at the beginning of this whether
>>>> MapReduce is really a suitable platform for (most) graph algorithms.
>>>>
>>>> I'm not content with the performance of the algorithms after some
>>>> testing and I'm pretty sure the future of large scale graph processing
>>>> is not on MapReduce (but hopefully on a Pregel like platform such as
>>>> Giraph).
>>>>
>>>> As we're currently removing clutter and trying to concentrate on the
>>>> core algorithms, I suggest to remove all graph algorithms with the
>>>> exception of PageRank.
>>>>
>>>> If no one objects with this, I'll start the cleanup in a few days.
>>>
>>> It all depends what you mean by 'graph algorithms', as Jake more or
>>> less says. I take your point re shortest paths etc. However it would
>>> be a mistake I think to send out a message that Mahout isn't good for
>>> consuming graph data, even while Hadoop certainly has issues with some
>>> kinds of graph-processing.
>>>
>>> All this can be something of a matter of perspective and descriptive
>>> gloss. Much of the work of the recommender / Taste component of Mahout
>>> can be thought of (and marketed as?) consuming a specialist flavour of
>>> graph data. Something like an 'interest graph' (a
>>> http://en.wikipedia.org/wiki/Bipartite_graph) where the nodes are
>>> items or users, and the affinities/associations are indications of
>>> interest (possibly date-stamped, possibly weighted).
>>>
>>> I work a lot with factual graph data expressed in W3C RDF form; in
>>> this case our 'graph' has nodes that are entities or atomic values,
>>> and links that are different typed links, representing relationship
>>> types, attributes/properties etc. Depending on the task in hand this
>>> can be consumed in Mahout by munging it into recommendations format
>>> input, or as with CSV input, into vectors, etc. So again it's 'graph'
>>> data processing even if the processing paradigm isn't from graph
>>> theory.
>>>
>>> Finally the spectral clustering piece of Mahout also takes graph input
>>> (affinities) and there are decades of research papers that account for
>>> this in terms of eigenvectors/values of laplacian representations of
>>> the graph affinity matrix; so I'd also count that as a Mahout tool for
>>> (I guess 'lossy' in Jake's terminology) graph processing.
>>>
>>> Or am I being too marketing-minded here? Is it fair to say "Mahout is
>>> a toolkit that can do specific useful things with various forms of
>>> graph-shaped data, but isn't a general-purpose graph processing
>>> environment"?
>>>
>>> Dan
>>
>
> --------------------------------------------
> Grant Ingersoll
> http://www.lucidimagination.com
>
>
>
>
Re: Goodbye graph algorithms
Posted by Grant Ingersoll <gs...@apache.org>.
WFM - works for me.
On Nov 2, 2011, at 11:30 AM, Sebastian Schelter wrote:
> On 02.11.2011 16:04, Jake Mannix wrote:
>> On Wed, Nov 2, 2011 at 6:38 AM, Grant Ingersoll <gs...@apache.org> wrote:
>>
>>> Perhaps it would make sense to move them to a branch? I know we never
>>> released them, but it seems a shame for them to be buried in SVN history.
>>>
>>
>> It would be a shame, but if the code can maybe get turned into a patch,
>> stuffed onto a JIRA ticket, and removed from the source tree (except for
>> history), it ironically may live longer, as it could get applied to trunk
>> in the future (esp. if it's code which lives on it's own, vs. modifications
>> of current code). A branch will never track trunk, and rapidly go totally
>> out of date.
>
> +1 on taking that approach
>
>>
>> -jake
>>
>
Re: Goodbye graph algorithms
Posted by Sebastian Schelter <ss...@apache.org>.
On 02.11.2011 16:04, Jake Mannix wrote:
> On Wed, Nov 2, 2011 at 6:38 AM, Grant Ingersoll <gs...@apache.org> wrote:
>
>> Perhaps it would make sense to move them to a branch? I know we never
>> released them, but it seems a shame for them to be buried in SVN history.
>>
>
> It would be a shame, but if the code can maybe get turned into a patch,
> stuffed onto a JIRA ticket, and removed from the source tree (except for
> history), it ironically may live longer, as it could get applied to trunk
> in the future (esp. if it's code which lives on it's own, vs. modifications
> of current code). A branch will never track trunk, and rapidly go totally
> out of date.
+1 on taking that approach
>
> -jake
>
Re: Goodbye graph algorithms
Posted by Jake Mannix <ja...@gmail.com>.
On Wed, Nov 2, 2011 at 6:38 AM, Grant Ingersoll <gs...@apache.org> wrote:
> Perhaps it would make sense to move them to a branch? I know we never
> released them, but it seems a shame for them to be buried in SVN history.
>
It would be a shame, but if the code can maybe get turned into a patch,
stuffed onto a JIRA ticket, and removed from the source tree (except for
history), it ironically may live longer, as it could get applied to trunk
in the future (esp. if it's code which lives on it's own, vs. modifications
of current code). A branch will never track trunk, and rapidly go totally
out of date.
-jake
Re: Goodbye graph algorithms
Posted by Grant Ingersoll <gs...@apache.org>.
Perhaps it would make sense to move them to a branch? I know we never released them, but it seems a shame for them to be buried in SVN history.
Perhaps we should have an "attic" branch or a "sandbox" branch, where things like this (and Watchmaker) can go to age w/o necessarily being relegated to the big bitbucket in the sky that is previous revisions. I suspect it will be easier for someone to pick up should things improve later than having to dig through SVN history. Besides, one might be careful about drawing conclusions on performance just yet given the state of Hadoop. As the overhead issues get worked through, some of this stuff may not be as bad. I guess the question is, is it the paradigm that is slow or the implementation of the paradigm? (That being said, I do think it's likely the case that this stuff moves to Giraph)
On Nov 2, 2011, at 8:49 AM, Sebastian Schelter wrote:
> I was refering to the class of "classical" graph algorithms (like
> shortest path, min cut, betweeness, triangle enumeration, etc) that Jake
> was also talking about.
>
> --sebastian
>
> On 02.11.2011 13:13, Dan Brickley wrote:
>> On 2 November 2011 10:24, Sebastian Schelter <ss...@apache.org> wrote:
>>> As you might know I recently started an experimental graph mining
>>> module. I was already concerned at the beginning of this whether
>>> MapReduce is really a suitable platform for (most) graph algorithms.
>>>
>>> I'm not content with the performance of the algorithms after some
>>> testing and I'm pretty sure the future of large scale graph processing
>>> is not on MapReduce (but hopefully on a Pregel like platform such as
>>> Giraph).
>>>
>>> As we're currently removing clutter and trying to concentrate on the
>>> core algorithms, I suggest to remove all graph algorithms with the
>>> exception of PageRank.
>>>
>>> If no one objects with this, I'll start the cleanup in a few days.
>>
>> It all depends what you mean by 'graph algorithms', as Jake more or
>> less says. I take your point re shortest paths etc. However it would
>> be a mistake I think to send out a message that Mahout isn't good for
>> consuming graph data, even while Hadoop certainly has issues with some
>> kinds of graph-processing.
>>
>> All this can be something of a matter of perspective and descriptive
>> gloss. Much of the work of the recommender / Taste component of Mahout
>> can be thought of (and marketed as?) consuming a specialist flavour of
>> graph data. Something like an 'interest graph' (a
>> http://en.wikipedia.org/wiki/Bipartite_graph) where the nodes are
>> items or users, and the affinities/associations are indications of
>> interest (possibly date-stamped, possibly weighted).
>>
>> I work a lot with factual graph data expressed in W3C RDF form; in
>> this case our 'graph' has nodes that are entities or atomic values,
>> and links that are different typed links, representing relationship
>> types, attributes/properties etc. Depending on the task in hand this
>> can be consumed in Mahout by munging it into recommendations format
>> input, or as with CSV input, into vectors, etc. So again it's 'graph'
>> data processing even if the processing paradigm isn't from graph
>> theory.
>>
>> Finally the spectral clustering piece of Mahout also takes graph input
>> (affinities) and there are decades of research papers that account for
>> this in terms of eigenvectors/values of laplacian representations of
>> the graph affinity matrix; so I'd also count that as a Mahout tool for
>> (I guess 'lossy' in Jake's terminology) graph processing.
>>
>> Or am I being too marketing-minded here? Is it fair to say "Mahout is
>> a toolkit that can do specific useful things with various forms of
>> graph-shaped data, but isn't a general-purpose graph processing
>> environment"?
>>
>> Dan
>
--------------------------------------------
Grant Ingersoll
http://www.lucidimagination.com
Re: Goodbye graph algorithms
Posted by Sebastian Schelter <ss...@apache.org>.
I was refering to the class of "classical" graph algorithms (like
shortest path, min cut, betweeness, triangle enumeration, etc) that Jake
was also talking about.
--sebastian
On 02.11.2011 13:13, Dan Brickley wrote:
> On 2 November 2011 10:24, Sebastian Schelter <ss...@apache.org> wrote:
>> As you might know I recently started an experimental graph mining
>> module. I was already concerned at the beginning of this whether
>> MapReduce is really a suitable platform for (most) graph algorithms.
>>
>> I'm not content with the performance of the algorithms after some
>> testing and I'm pretty sure the future of large scale graph processing
>> is not on MapReduce (but hopefully on a Pregel like platform such as
>> Giraph).
>>
>> As we're currently removing clutter and trying to concentrate on the
>> core algorithms, I suggest to remove all graph algorithms with the
>> exception of PageRank.
>>
>> If no one objects with this, I'll start the cleanup in a few days.
>
> It all depends what you mean by 'graph algorithms', as Jake more or
> less says. I take your point re shortest paths etc. However it would
> be a mistake I think to send out a message that Mahout isn't good for
> consuming graph data, even while Hadoop certainly has issues with some
> kinds of graph-processing.
>
> All this can be something of a matter of perspective and descriptive
> gloss. Much of the work of the recommender / Taste component of Mahout
> can be thought of (and marketed as?) consuming a specialist flavour of
> graph data. Something like an 'interest graph' (a
> http://en.wikipedia.org/wiki/Bipartite_graph) where the nodes are
> items or users, and the affinities/associations are indications of
> interest (possibly date-stamped, possibly weighted).
>
> I work a lot with factual graph data expressed in W3C RDF form; in
> this case our 'graph' has nodes that are entities or atomic values,
> and links that are different typed links, representing relationship
> types, attributes/properties etc. Depending on the task in hand this
> can be consumed in Mahout by munging it into recommendations format
> input, or as with CSV input, into vectors, etc. So again it's 'graph'
> data processing even if the processing paradigm isn't from graph
> theory.
>
> Finally the spectral clustering piece of Mahout also takes graph input
> (affinities) and there are decades of research papers that account for
> this in terms of eigenvectors/values of laplacian representations of
> the graph affinity matrix; so I'd also count that as a Mahout tool for
> (I guess 'lossy' in Jake's terminology) graph processing.
>
> Or am I being too marketing-minded here? Is it fair to say "Mahout is
> a toolkit that can do specific useful things with various forms of
> graph-shaped data, but isn't a general-purpose graph processing
> environment"?
>
> Dan
Re: Goodbye graph algorithms
Posted by Dan Brickley <da...@danbri.org>.
On 2 November 2011 10:24, Sebastian Schelter <ss...@apache.org> wrote:
> As you might know I recently started an experimental graph mining
> module. I was already concerned at the beginning of this whether
> MapReduce is really a suitable platform for (most) graph algorithms.
>
> I'm not content with the performance of the algorithms after some
> testing and I'm pretty sure the future of large scale graph processing
> is not on MapReduce (but hopefully on a Pregel like platform such as
> Giraph).
>
> As we're currently removing clutter and trying to concentrate on the
> core algorithms, I suggest to remove all graph algorithms with the
> exception of PageRank.
>
> If no one objects with this, I'll start the cleanup in a few days.
It all depends what you mean by 'graph algorithms', as Jake more or
less says. I take your point re shortest paths etc. However it would
be a mistake I think to send out a message that Mahout isn't good for
consuming graph data, even while Hadoop certainly has issues with some
kinds of graph-processing.
All this can be something of a matter of perspective and descriptive
gloss. Much of the work of the recommender / Taste component of Mahout
can be thought of (and marketed as?) consuming a specialist flavour of
graph data. Something like an 'interest graph' (a
http://en.wikipedia.org/wiki/Bipartite_graph) where the nodes are
items or users, and the affinities/associations are indications of
interest (possibly date-stamped, possibly weighted).
I work a lot with factual graph data expressed in W3C RDF form; in
this case our 'graph' has nodes that are entities or atomic values,
and links that are different typed links, representing relationship
types, attributes/properties etc. Depending on the task in hand this
can be consumed in Mahout by munging it into recommendations format
input, or as with CSV input, into vectors, etc. So again it's 'graph'
data processing even if the processing paradigm isn't from graph
theory.
Finally the spectral clustering piece of Mahout also takes graph input
(affinities) and there are decades of research papers that account for
this in terms of eigenvectors/values of laplacian representations of
the graph affinity matrix; so I'd also count that as a Mahout tool for
(I guess 'lossy' in Jake's terminology) graph processing.
Or am I being too marketing-minded here? Is it fair to say "Mahout is
a toolkit that can do specific useful things with various forms of
graph-shaped data, but isn't a general-purpose graph processing
environment"?
Dan
Re: Goodbye graph algorithms
Posted by Robert Burrell Donkin <ro...@gmail.com>.
On Wed, Nov 2, 2011 at 9:37 AM, Jake Mannix <ja...@gmail.com> wrote:
> I think if you focus on the "lossless" graph algorithms, most of
> them will indeed scale pretty poorly on MapReduce. If you're willing
> to do lossy stuff, like doing straightforward dimensional reduction on
> the adjacency matrix and analyzing the geometry of the projected graph,
> there is still lots of stuff you can do via MR, but for traditional things
> like
> "shortest path", finding min-cuts, hubs and cycles, etc, MR can
> incur a lot of overhead, esp. as the graph size grows to the point at
> which doing it in memory on a single machine is impossible (ie the
> point at which MR is even supposed to be used).
FWIW on modern multicore processors, we (quite unexpectedly) found
that MR's more efficient use of cache outperformed state of the art
concurrent minimal spanning tree algorithms. Quite large intermediate
volumes of data are generated, though. Too much to stream successfully
across a network. So machine-local storage would be needed...
Robert
Re: Goodbye graph algorithms
Posted by Jake Mannix <ja...@gmail.com>.
I think if you focus on the "lossless" graph algorithms, most of
them will indeed scale pretty poorly on MapReduce. If you're willing
to do lossy stuff, like doing straightforward dimensional reduction on
the adjacency matrix and analyzing the geometry of the projected graph,
there is still lots of stuff you can do via MR, but for traditional things
like
"shortest path", finding min-cuts, hubs and cycles, etc, MR can
incur a lot of overhead, esp. as the graph size grows to the point at
which doing it in memory on a single machine is impossible (ie the
point at which MR is even supposed to be used).
+1
-jake
On Wed, Nov 2, 2011 at 2:24 AM, Sebastian Schelter <ss...@apache.org> wrote:
> As you might know I recently started an experimental graph mining
> module. I was already concerned at the beginning of this whether
> MapReduce is really a suitable platform for (most) graph algorithms.
>
> I'm not content with the performance of the algorithms after some
> testing and I'm pretty sure the future of large scale graph processing
> is not on MapReduce (but hopefully on a Pregel like platform such as
> Giraph).
>
> As we're currently removing clutter and trying to concentrate on the
> core algorithms, I suggest to remove all graph algorithms with the
> exception of PageRank.
>
> If no one objects with this, I'll start the cleanup in a few days.
>
> --sebastian
>