title: Efficient controlled random walks in gremlin
body: <h2>Goal</h2>
  <p>The objective is to efficiently generate random walks on a relatively large graph with uneven probabilities of going through edges depending on their type.</p>
  <h2>Configuration</h2>
  <ul>
  <li>Ubuntu VM, 23Go RAM</li>
  <li>JanusGraph 0.6.1 full</li>
  <li>Local graph (default <code>conf/remote.yaml</code> file used)</li>
  <li>~1.8m vertices (~28k will be start nodes for the random walks)</li>
  <li>~21m relationships (they can all be used in the random walks)</li>
  </ul>
  <h2>What I am doing</h2>
  <p>I am currently generating random walks with the <code>sample</code> command:</p>
  <pre><code>g.V(&lt;startnode_id&gt;).
    repeat( local( both().sample(1) ) ).
      times(&lt;desired_randomwalk_length&gt;).
    path()
  </code></pre>
  <h2>What I tried</h2>
  <p>I tried using a gremlinpython script to create a random walk generator that would first get all edges connected to the current node, then pick randomly an edge to go through and repeat <code>&lt;desired_randomwalk_length&gt;</code> times.</p>
  <pre class="lang-py prettyprint-override"><code>from gremlin_python.driver.driver_remote_connection import DriverRemoteConnection
  from gremlin_python.process.anonymous_traversal import traversal
  from gremlin_python.structure.graph import Vertex
  from typing import List
  
  connection = DriverRemoteConnection(&lt;URL&gt;, &quot;g&quot;)
  g = traversal().withRemote(connection)
  
  def get_next_node(start:Vertex) -&gt; Vertex:
    next_vertices = g.V(start.id).both().fold().next()
    return next_vertices[randint(0, len(next_vertices)-1)]
  def get_random_walk(start:Vertex, length:int=10) -&gt; List[Vertex]:
    current_node = start
    random_walk = [current_node]
    for _ in range(length):
      current_node = get_next_node(current_node)
      random_walk.append(current_node)
    return random_walk
  </code></pre>
  <h2>Issues</h2>
  <p>While testing on a subset of the total graph (400k vertices, 1.5m rel), I got these results</p>
  <ul>
  <li>Sample query, <code>&lt;desired_randomwalk_length&gt;</code> of 10: 100k random walks in 1h10</li>
  <li>Gremlinpython function, <code>&lt;desired_randomwalk_length&gt;</code> of 4: 2k random walks in 1h+</li>
  </ul>
  <p>The sample command is really fast, but there are a few problems:</p>
  <ol>
  <li>It doesn't seem to truly be a uniform distribution pick amongst the edges (<a href="https://kelvinlawrence.net/book/Gremlin-Graph-Guide.html#_using_math_random_to_more_randomly_select_a_single_vertex" rel="nofollow noreferrer">it seems to be successive coin tosses</a>) which could lead to certain paths being taken more often, which then diminishes the interest of generating random walks. (I can't directly do what is recommended here as the nodes ids aren't in a sequence, thus I have to acquire them first.)</li>
  <li>I haven't found a way to give different probabilities to different types of relationships.</li>
  </ol>
  <p>Is there a better way to do random walks with Gremlin?<br />
  If there is none, is there a way to modify the sample query to rectify the assign probabilities to types of edges? Maybe even a way to have a better distribution of the sampling?<br />
  In last recourse, is there a way to improve the queries to make this &quot;by hand&quot; with a gremlinpython script?</p>
  <p>Thanks to everyone reading/replying!</p>
  <h2>EDIT</h2>
  <p>Is there a way to do the following:</p>
  <ul>
  <li>Given a <code>r_type1</code>, <code>r_type2</code>, <code>r_type3</code>, ... the acceptable relationship type for this random walk</li>
  <li>Given a <code>proba1</code>, <code>proba2</code>, <code>proba3</code>, ... the probabilities of going through these relationship types</li>
  </ul>
  <p>For each step</p>
  <ol>
  <li>Sample a node for each relationship type <code>r_type1</code>, <code>r_type2</code>, <code>r_type3</code>, ...</li>
  <li>Keep only one according to the probabilities <code>proba1</code>, <code>proba2</code>, <code>proba3</code>, ...</li>
  </ol>
  <p>I think the second step could be done be sampling multiple nodes for each relationships, in accordance with the probas (which could be done by using a <code>gremlinpython</code> script to build the query). This still leaves the question of how to sample on multiple relationships from a single node, and how to randomly pick one in the sampled nodes.</p>
  <p>I hope this is clear!</p>