[Gelly] Vertex-centric iteration updateVertex does not get called

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

[Gelly] Vertex-centric iteration updateVertex does not get called

Hermann Gábor
Hi all,

I am implementing a simple triangle counting example for a workshop with
vertex-centric iteration and I found that the updateVertex method only gets
called if there are new messages for that vertex. Is it the expected
behavior?

I know that the iteration should stop for the given vertex when the we
don't change the vertex value but (at least in my case) it would be useful
if the updateVertex got called with an empty message iterator. I guess
receiving zero messages might have a meaning in other cases too, and the
user would like to update the vertex value.
Does changing the current behavior make sense?

Cheers,
Gabor
Reply | Threaded
Open this post in threaded view
|

Re: [Gelly] Vertex-centric iteration updateVertex does not get called

Andra Lungu
Hello Gabor,

Yes, currently updateVertex only gets called when a new message was
received.
Could you please describe the logic behind your triangle count? The one I
know is described at the beginning of page 1643 in this article:
http://www.cc.gatech.edu/~bader/papers/GraphBSPonXMT-MTAAP2013.pdf

As you can see, each time(for all the three supersteps), a message gets
sent.
Here is my suboptimal implementation of the algorithm in the paper (it's
supposed to prove that high degree nodes overload the system):
https://github.com/andralungu/gelly-partitioning/commit/224cb9b6917c2320e16a657a549b2a0313aeb300

It needs some serious rebasing. I'll get to it this weekend :).
Nevertheless, it should serve as a starting point for your implementation.

Let us know if you have further questions!
Andra

P.S. I'm not sure calling vertexUpdate with an empty message iterator would
be so straightforward to implement. I'll have to look into it a bit more
once I get some spare time :)



On Thu, Apr 16, 2015 at 9:44 PM, Hermann Gábor <[hidden email]> wrote:

> Hi all,
>
> I am implementing a simple triangle counting example for a workshop with
> vertex-centric iteration and I found that the updateVertex method only gets
> called if there are new messages for that vertex. Is it the expected
> behavior?
>
> I know that the iteration should stop for the given vertex when the we
> don't change the vertex value but (at least in my case) it would be useful
> if the updateVertex got called with an empty message iterator. I guess
> receiving zero messages might have a meaning in other cases too, and the
> user would like to update the vertex value.
> Does changing the current behavior make sense?
>
> Cheers,
> Gabor
>
Reply | Threaded
Open this post in threaded view
|

Re: [Gelly] Vertex-centric iteration updateVertex does not get called

Vasiliki Kalavri
In reply to this post by Hermann Gábor
Hi Gabor,

the vertex-centric iteration implements the Pregel model, according to
which a vertex is "active" during a superstep only when there are messages
for this vertex. So, the behavior you are seeing is intended, yes :-)

The logic behind this is that a vertex value gets updated by performing
some computation on the received messages. Thus, there would be no vertex
update if there are no new messages.

If you want to keep a vertex active even when there are no messages sent to
it, you could have it send a dummy message to itself.
However, if your algorithm requires all vertices to be active in all
supersteps, then you are probably looking for a bulk iteration instead.

Since you're mentioning that you're implementing triangle counting, note
that with Gelly you don't need to implement this as an iterative algorithm.
Actually, it is probably a bad idea.
In a system like Giraph, you don't have another choice because everything
has to follow the Pregel model and be expressed as a series of supersteps.
However, triangle counting is not an iterative algorithm; it consists of
well-defined steps which you can express with the neighborhood and join
functions of Gelly.

Finally, you might want to take a look at the Flink examples. There are two
implementations of triangle count there :-)

Cheers,
-Vasia.


On 16 April 2015 at 21:44, Hermann Gábor <[hidden email]> wrote:

> Hi all,
>
> I am implementing a simple triangle counting example for a workshop with
> vertex-centric iteration and I found that the updateVertex method only gets
> called if there are new messages for that vertex. Is it the expected
> behavior?
>
> I know that the iteration should stop for the given vertex when the we
> don't change the vertex value but (at least in my case) it would be useful
> if the updateVertex got called with an empty message iterator. I guess
> receiving zero messages might have a meaning in other cases too, and the
> user would like to update the vertex value.
> Does changing the current behavior make sense?
>
> Cheers,
> Gabor
>
Reply | Threaded
Open this post in threaded view
|

Re: [Gelly] Vertex-centric iteration updateVertex does not get called

Hermann Gábor
In reply to this post by Andra Lungu
Hey,

Thank you both for your help :)
I was missing this point in the Pregel model. I thought it would be
expected to receive empty message iterators.

Yes, I know it is not the best use-case for vertex-centric iteration as
there are well-defined steps, and also know the Flink examples. I only
wanted this as a demonstration for the participants of the workshop (among
other examples) of thinking in the vertex-centric Pregel model. Then I
would show them the other solution that fits the problem more.

Of course, I could implement triangle count with the vertex-centric
iteration too, but I ran into this behavior and was not sure if it was
expected. I might move on to other examples. Thanks anyway :)

Cheers,
Gabor