Gelly, problem vertex centric iteration

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

Gelly, problem vertex centric iteration

Yi ZHOU-2
Hello everyone,
I need some suggestions about debuging the Affinity Appropogation
algorithm for gelly.

In my implementation, there is a problem with the MessagingFunction in
Vertex Centric Iteration

The test graph is a completed directed graph (25 vertices in total),
i.e. there are two opposite directed edges between every two vertices.
The value of each vertex is a hashmap, in which contians information of
all of the vertex's neigbor vertices.

My MessagingFunction is implemented as follow,

            if (getSuperstepNumber() % 2 == 1){
                 /*Odd step: Propagate availability*/
                 int msgCnt = 0;     //Debug variable, count out going
edge number
                 for (Edge<Long, Double> e: getOutgoingEdges()){
                     Long dest = e.getTarget();
                     sendMessageTo(dest, new Tuple2<Long,
Double>(vertexKey, vertexValue.get(dest).f2));
                     msgCnt++;
                 }
                 System.err.format("Step %d: Vertex %d send %d\n",
getSuperstepNumber(), vertexKey, msgCnt);
            }else{
                 /*Even step: propagate responsibility*/
                 for (Edge<Long, Double> e: getOutgoingEdges()){
                     Long dest = e.getTarget();
                     sendMessageTo(dest, new Tuple2<Long,
Double>(vertexKey, vertexValue.get(dest).f1));
                 }
             }

I use a msgCnt for conuting the neigbor edges in the odd step. However,
even during the 1st super step , the result is quite strange. For some
vertices, they appropogate messages to all the adjacent vertices.
however, for serveral other vertices, they send nothing or only part of
their neighbors. i.e the getOutgoingEdges() returns none.

Step 1: Vertex 3 send 0
Step 1: Vertex 1 send 0
Step 1: Vertex 5 send 0
Step 1: Vertex 8 send 0
Step 1: Vertex 14 send 0
Step 1: Vertex 16 send 0
Step 1: Vertex 2 send 24
Step 1: Vertex 7 send 18
Step 1: Vertex 9 send 24
Step 1: Vertex 6 send 24
Step 1: Vertex 11 send 0
Step 1: Vertex 15 send 0
Step 1: Vertex 12 send 0
Step 1: Vertex 21 send 0
Step 1: Vertex 13 send 0
Step 1: Vertex 25 send 0
Step 1: Vertex 22 send 24
Step 1: Vertex 18 send 0
Step 1: Vertex 23 send 24
Step 1: Vertex 19 send 0
Step 1: Vertex 20 send 0
Step 1: Vertex 24 send 24

I do not know how to detect the problem, can anyone give me some
suggestions?
I attached the code and data also. The iteration is loaded in line 118
in AffinityPropogation.java

Thank you
Best regards.

ZHOU Yi


AffinityPropogation.java (11K) Download Attachment
AffinityPropogationExample.java (3K) Download Attachment
pom.xml (5K) Download Attachment
ToyProblemPreferences.txt (512 bytes) Download Attachment
ToyProblemSimilarities.txt (14K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Gelly, problem vertex centric iteration

Vasiliki Kalavri
Hi Yi,

by debugging a bit your code, it seems that the problem is in the
pre-processing step and more specifically in the filtering you do on the
self edges, in the helper transferGraph method.

I will have to dig a bit more to figure out the issue, but until then you
should be able to work around this in one of the following ways:
- use the original Edge DataSet (distanceEdges) as the Edge DataSet of the
vertex-centric iteration input graph.
- skip the filter entirely and check for self-edges inside the messaging /
vertexUpdate functions, so that you do a no-op for these.

Let me know if any of these workarounds solve your problem!

Cheers,
-Vasia.

On 19 April 2015 at 15:00, Yi ZHOU <[hidden email]> wrote:

> Hello everyone,
> I need some suggestions about debuging the Affinity Appropogation
> algorithm for gelly.
>
> In my implementation, there is a problem with the MessagingFunction in
> Vertex Centric Iteration
>
> The test graph is a completed directed graph (25 vertices in total), i.e.
> there are two opposite directed edges between every two vertices.
> The value of each vertex is a hashmap, in which contians information of
> all of the vertex's neigbor vertices.
>
> My MessagingFunction is implemented as follow,
>
>            if (getSuperstepNumber() % 2 == 1){
>                 /*Odd step: Propagate availability*/
>                 int msgCnt = 0;     //Debug variable, count out going edge
> number
>                 for (Edge<Long, Double> e: getOutgoingEdges()){
>                     Long dest = e.getTarget();
>                     sendMessageTo(dest, new Tuple2<Long,
> Double>(vertexKey, vertexValue.get(dest).f2));
>                     msgCnt++;
>                 }
>                 System.err.format("Step %d: Vertex %d send %d\n",
> getSuperstepNumber(), vertexKey, msgCnt);
>            }else{
>                 /*Even step: propagate responsibility*/
>                 for (Edge<Long, Double> e: getOutgoingEdges()){
>                     Long dest = e.getTarget();
>                     sendMessageTo(dest, new Tuple2<Long,
> Double>(vertexKey, vertexValue.get(dest).f1));
>                 }
>             }
>
> I use a msgCnt for conuting the neigbor edges in the odd step. However,
> even during the 1st super step , the result is quite strange. For some
> vertices, they appropogate messages to all the adjacent vertices. however,
> for serveral other vertices, they send nothing or only part of their
> neighbors. i.e the getOutgoingEdges() returns none.
>
>
> Step 1: Vertex 3 send 0
> Step 1: Vertex 1 send 0
> Step 1: Vertex 5 send 0
> Step 1: Vertex 8 send 0
> Step 1: Vertex 14 send 0
> Step 1: Vertex 16 send 0
> Step 1: Vertex 2 send 24
> Step 1: Vertex 7 send 18
> Step 1: Vertex 9 send 24
> Step 1: Vertex 6 send 24
> Step 1: Vertex 11 send 0
> Step 1: Vertex 15 send 0
> Step 1: Vertex 12 send 0
> Step 1: Vertex 21 send 0
> Step 1: Vertex 13 send 0
> Step 1: Vertex 25 send 0
> Step 1: Vertex 22 send 24
> Step 1: Vertex 18 send 0
> Step 1: Vertex 23 send 24
> Step 1: Vertex 19 send 0
> Step 1: Vertex 20 send 0
> Step 1: Vertex 24 send 24
>
> I do not know how to detect the problem, can anyone give me some
> suggestions?
> I attached the code and data also. The iteration is loaded in line 118 in
> AffinityPropogation.java
>
> Thank you
> Best regards.
>
> ZHOU Yi
>
>