tinkerpop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ok...@apache.org
Subject [03/11] tinkerpop git commit: Added epsilon-based convergence. If the user does not specify a times() to iterate, then it will use epislon which is 10-6 for convergence.
Date Fri, 22 Sep 2017 14:50:00 GMT
Added epsilon-based convergence. If the user does not specify a times() to iterate, then it
will use epislon which is 10-6 for convergence.


Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/3bc830fd
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/3bc830fd
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/3bc830fd

Branch: refs/heads/master
Commit: 3bc830fd09edb5c0c82479d174a447af3aa6ac63
Parents: db7d996
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Authored: Tue Sep 19 10:47:20 2017 -0600
Committer: Marko A. Rodriguez <okrammarko@gmail.com>
Committed: Tue Sep 19 10:47:20 2017 -0600

----------------------------------------------------------------------
 CHANGELOG.asciidoc                              |  1 +
 docs/src/upgrade/release-3.3.x.asciidoc         |  8 +-
 .../ranking/pagerank/PageRankVertexProgram.java | 89 +++++++++++---------
 .../step/map/PageRankVertexProgramStep.java     |  2 +-
 .../pagerank/PageRankVertexProgramTest.java     |  2 +-
 5 files changed, 59 insertions(+), 43 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/3bc830fd/CHANGELOG.asciidoc
----------------------------------------------------------------------
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index c8a1c7d..87899ce 100644
--- a/CHANGELOG.asciidoc
+++ b/CHANGELOG.asciidoc
@@ -28,6 +28,7 @@ TinkerPop 3.3.1 (Release Date: NOT OFFICIALLY RELEASED YET)
 
 This release also includes changes from <<release-3-2-7, 3.2.7>>.
 
+* Added support for epsilon-based convergence in `PageRankVertexProgram` (no longer manually
capped by iterations).
 * Fixed two major bugs in how PageRank was being calculated in `PageRankVertexProgram`.
 * Added `Io.requiresVersion(Object)` to allow graph providers a way to check the `Io` type
and version being constructed.
 * Defaulted `IoCore.gryo()` and `IoCore.graphson()` to both use their 3.0 formats which means
that `Graph.io()` will use those by default.

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/3bc830fd/docs/src/upgrade/release-3.3.x.asciidoc
----------------------------------------------------------------------
diff --git a/docs/src/upgrade/release-3.3.x.asciidoc b/docs/src/upgrade/release-3.3.x.asciidoc
index e215dca..43d9ccd 100644
--- a/docs/src/upgrade/release-3.3.x.asciidoc
+++ b/docs/src/upgrade/release-3.3.x.asciidoc
@@ -37,8 +37,7 @@ PageRankVertexProgram
 
 There were two major bugs in the way in which PageRank was being calculated in `PageRankVertexProgram`.
First, teleportation
 energy was not being distributed correctly amongst the vertices at each round. Second, terminal
vertices (i.e. vertices
-with no outgoing edges) did not have their full gathered energy distributed via teleportation.
As a secondary benefit,
-`PageRankVertexProgram` also always calculates the vertex count and no longer requires the
user to specify the vertex count.
+with no outgoing edges) did not have their full gathered energy distributed via teleportation.
 
 For users upgrading, note that while the relative rank orders will remain "the same," the
actual PageRank values will differ
 from prior TinkerPop versions.
@@ -65,6 +64,11 @@ Normalization preserved through computation:
 ==>1.00000000000000018
 ```
 
+Two other additions to `PageRankVertexProgram` were provided as well.
+
+1. It now calculates the vertex count and thus, no longer requires the user to specify the
vertex count.
+2. It now allows the user to leverage an epsilon-based convergence instead of having to specify
the number of iterations to execute.
+
 IO Defaults
 ^^^^^^^^^^^
 

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/3bc830fd/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
index e92f0a8..81468d4 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgram.java
@@ -58,17 +58,20 @@ public class PageRankVertexProgram implements VertexProgram<Double>
{
     private static final String PROPERTY = "gremlin.pageRankVertexProgram.property";
     private static final String VERTEX_COUNT = "gremlin.pageRankVertexProgram.vertexCount";
     private static final String ALPHA = "gremlin.pageRankVertexProgram.alpha";
+    private static final String EPSILON = "gremlin.pageRankVertexProgram.epsilon";
     private static final String TOTAL_ITERATIONS = "gremlin.pageRankVertexProgram.totalIterations";
     private static final String EDGE_TRAVERSAL = "gremlin.pageRankVertexProgram.edgeTraversal";
     private static final String INITIAL_RANK_TRAVERSAL = "gremlin.pageRankVertexProgram.initialRankTraversal";
     private static final String TELEPORTATION_ENERGY = "gremlin.pageRankVertexProgram.teleportationEnergy";
+    private static final String CONVERGENCE_ERROR = "gremlin.pageRankVertexProgram.convergenceError";
 
     private MessageScope.Local<Double> incidentMessageScope = MessageScope.Local.of(__::outE);
     private MessageScope.Local<Double> countMessageScope = MessageScope.Local.of(new
MessageScope.Local.ReverseTraversalSupplier(this.incidentMessageScope));
     private PureTraversal<Vertex, Edge> edgeTraversal = null;
     private PureTraversal<Vertex, ? extends Number> initialRankTraversal = null;
     private double alpha = 0.85d;
-    private int totalIterations = 30;
+    private double epsilon = 0.00001d;
+    private int totalIterations = -1;
     private String property = PAGE_RANK;
     private Set<VertexComputeKey> vertexComputeKeys;
     private Set<MemoryComputeKey> memoryComputeKeys;
@@ -86,23 +89,26 @@ public class PageRankVertexProgram implements VertexProgram<Double>
{
             this.incidentMessageScope = MessageScope.Local.of(() -> this.edgeTraversal.get().clone());
             this.countMessageScope = MessageScope.Local.of(new MessageScope.Local.ReverseTraversalSupplier(this.incidentMessageScope));
         }
-        this.alpha = configuration.getDouble(ALPHA, 0.85d);
-        this.totalIterations = configuration.getInt(TOTAL_ITERATIONS, 30);
+        this.alpha = configuration.getDouble(ALPHA, this.alpha);
+        this.epsilon = configuration.getDouble(EPSILON, this.epsilon);
+        this.totalIterations = configuration.getInt(TOTAL_ITERATIONS, -1);
         this.property = configuration.getString(PROPERTY, PAGE_RANK);
         this.vertexComputeKeys = new HashSet<>(Arrays.asList(
                 VertexComputeKey.of(this.property, false),
                 VertexComputeKey.of(EDGE_COUNT, true)));
         this.memoryComputeKeys = new HashSet<>(Arrays.asList(
                 MemoryComputeKey.of(TELEPORTATION_ENERGY, Operator.sum, true, true),
-                MemoryComputeKey.of(VERTEX_COUNT, Operator.sum, true, true)));
+                MemoryComputeKey.of(VERTEX_COUNT, Operator.sum, true, true),
+                MemoryComputeKey.of(CONVERGENCE_ERROR, Operator.sum, false, true)));
     }
 
     @Override
     public void storeState(final Configuration configuration) {
         VertexProgram.super.storeState(configuration);
         configuration.setProperty(ALPHA, this.alpha);
-        configuration.setProperty(TOTAL_ITERATIONS, this.totalIterations);
+        configuration.setProperty(EPSILON, this.epsilon);
         configuration.setProperty(PROPERTY, this.property);
+        configuration.setProperty(TOTAL_ITERATIONS, this.totalIterations);
         if (null != this.edgeTraversal)
             this.edgeTraversal.storeState(configuration, EDGE_TRAVERSAL);
         if (null != this.initialRankTraversal)
@@ -155,8 +161,9 @@ public class PageRankVertexProgram implements VertexProgram<Double>
{
 
     @Override
     public void setup(final Memory memory) {
-        memory.set(TELEPORTATION_ENERGY, 0.0d);
+        memory.set(TELEPORTATION_ENERGY, null == this.initialRankTraversal ? 1.0d : 0.0d);
         memory.set(VERTEX_COUNT, 0.0d);
+        memory.set(CONVERGENCE_ERROR, 1.0d);
     }
 
     @Override
@@ -164,52 +171,51 @@ public class PageRankVertexProgram implements VertexProgram<Double>
{
         if (memory.isInitialIteration()) {
             messenger.sendMessage(this.countMessageScope, 1.0d);
             memory.add(VERTEX_COUNT, 1.0d);
-        } else if (1 == memory.getIteration()) {
-            final double vertexCount = memory.<Double>get(VERTEX_COUNT);
-            double initialPageRank = null == this.initialRankTraversal ?
-                    1.0d / vertexCount :
-                    TraversalUtil.apply(vertex, this.initialRankTraversal.get()).doubleValue();
-            vertex.property(VertexProperty.Cardinality.single, this.property, initialPageRank);
-            final double edgeCount = IteratorUtils.reduce(messenger.receiveMessages(), 0.0d,
(a, b) -> a + b);
-            vertex.property(VertexProperty.Cardinality.single, EDGE_COUNT, edgeCount);
-            memory.add(TELEPORTATION_ENERGY, (1.0d - this.alpha) * initialPageRank);
-            initialPageRank = this.alpha * initialPageRank;
-            if (!this.terminate(memory)) { // don't send messages if this is the last iteration
-                if (edgeCount > 0.0d)
-                    messenger.sendMessage(this.incidentMessageScope, initialPageRank / edgeCount);
-                else
-                    memory.add(TELEPORTATION_ENERGY, initialPageRank);
-            }
         } else {
             final double vertexCount = memory.<Double>get(VERTEX_COUNT);
-            double newPageRank = IteratorUtils.reduce(messenger.receiveMessages(), 0.0d,
(a, b) -> a + b);
-            final double terminalEnergy = memory.get(TELEPORTATION_ENERGY);
-            if (terminalEnergy > 0.0d) {
-                final double localTerminalEnergy = terminalEnergy / vertexCount;
-                newPageRank = newPageRank + localTerminalEnergy;
-                memory.add(TELEPORTATION_ENERGY, -localTerminalEnergy);
+            final double edgeCount;
+            double pageRank;
+            if (1 == memory.getIteration()) {
+                edgeCount = IteratorUtils.reduce(messenger.receiveMessages(), 0.0d, (a, b)
-> a + b);
+                vertex.property(VertexProperty.Cardinality.single, EDGE_COUNT, edgeCount);
+                pageRank = null == this.initialRankTraversal ?
+                        0.0d :
+                        TraversalUtil.apply(vertex, this.initialRankTraversal.get()).doubleValue();
+            } else {
+                edgeCount = vertex.value(EDGE_COUNT);
+                pageRank = IteratorUtils.reduce(messenger.receiveMessages(), 0.0d, (a, b)
-> a + b);
             }
-            vertex.property(VertexProperty.Cardinality.single, this.property, newPageRank);
-            memory.add(TELEPORTATION_ENERGY, (1.0d - this.alpha) * newPageRank);
-            newPageRank = this.alpha * newPageRank;
-            final double edgeCount = vertex.<Double>value(EDGE_COUNT);
-            if (!this.terminate(memory)) { // don't send messages if this is the last iteration
-                if (edgeCount > 0.0d)
-                    messenger.sendMessage(this.incidentMessageScope, newPageRank / edgeCount);
-                else
-                    memory.add(TELEPORTATION_ENERGY, newPageRank);
+            //////////////////////////
+            final double teleporationEnergy = memory.get(TELEPORTATION_ENERGY);
+            if (teleporationEnergy > 0.0d) {
+                final double localTerminalEnergy = teleporationEnergy / vertexCount;
+                pageRank = pageRank + localTerminalEnergy;
+                memory.add(TELEPORTATION_ENERGY, -localTerminalEnergy);
             }
+            final double previousPageRank = vertex.<Double>property(this.property).orElse(0.0d);
+            memory.add(CONVERGENCE_ERROR, Math.abs(pageRank - previousPageRank));
+            vertex.property(VertexProperty.Cardinality.single, this.property, pageRank);
+            memory.add(TELEPORTATION_ENERGY, (1.0d - this.alpha) * pageRank);
+            pageRank = this.alpha * pageRank;
+            if (edgeCount > 0.0d)
+                messenger.sendMessage(this.incidentMessageScope, pageRank / edgeCount);
+            else
+                memory.add(TELEPORTATION_ENERGY, pageRank);
         }
     }
 
     @Override
     public boolean terminate(final Memory memory) {
-        return memory.getIteration() >= this.totalIterations;
+        // System.out.println(memory.<Double>get(CONVERGENCE_ERROR));
+        memory.set(CONVERGENCE_ERROR, 0.0d);
+        return -1 == this.totalIterations ?
+                memory.<Double>get(CONVERGENCE_ERROR) < this.epsilon :
+                memory.getIteration() >= this.totalIterations;
     }
 
     @Override
     public String toString() {
-        return StringFactory.vertexProgramString(this, "alpha=" + this.alpha + ", iterations="
+ this.totalIterations);
+        return StringFactory.vertexProgramString(this, "alpha=" + this.alpha + ", iterations="
+ this.totalIterations + ", epsilon=" + this.epsilon);
     }
 
     //////////////////////////////
@@ -239,6 +245,11 @@ public class PageRankVertexProgram implements VertexProgram<Double>
{
             return this;
         }
 
+        public Builder epsilon(final double epsilon) {
+            this.configuration.setProperty(EPSILON, epsilon);
+            return this;
+        }
+
         public Builder edges(final Traversal.Admin<Vertex, Edge> edgeTraversal) {
             PureTraversal.storeState(this.configuration, EDGE_TRAVERSAL, edgeTraversal);
             return this;

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/3bc830fd/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/PageRankVertexProgramStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/PageRankVertexProgramStep.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/PageRankVertexProgramStep.java
index 364d092..d67faf3 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/PageRankVertexProgramStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/PageRankVertexProgramStep.java
@@ -47,7 +47,7 @@ public final class PageRankVertexProgramStep extends VertexProgramStep implement
 
     private PureTraversal<Vertex, Edge> edgeTraversal;
     private String pageRankProperty = PageRankVertexProgram.PAGE_RANK;
-    private int times = 30;
+    private int times = -2;
     private final double alpha;
 
     public PageRankVertexProgramStep(final Traversal.Admin traversal, final double alpha)
{

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/3bc830fd/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgramTest.java
----------------------------------------------------------------------
diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgramTest.java
b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgramTest.java
index 8612cb6..459c688 100644
--- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgramTest.java
+++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/computer/ranking/pagerank/PageRankVertexProgramTest.java
@@ -38,7 +38,7 @@ public class PageRankVertexProgramTest extends AbstractGremlinProcessTest
{
     @LoadGraphWith(MODERN)
     public void shouldExecutePageRank() throws Exception {
         if (graphProvider.getGraphComputer(graph).features().supportsResultGraphPersistCombination(GraphComputer.ResultGraph.NEW,
GraphComputer.Persist.VERTEX_PROPERTIES)) {
-            final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).program(PageRankVertexProgram.build().create(graph)).submit().get();
+            final ComputerResult result = graph.compute(graphProvider.getGraphComputer(graph).getClass()).program(PageRankVertexProgram.build().iterations(30).create(graph)).submit().get();
             result.graph().traversal().V().forEachRemaining(v -> {
                 assertEquals(3, v.keys().size()); // name, age/lang, pageRank
                 assertTrue(v.keys().contains("name"));


Mime
View raw message