diff --git a/java/server/src/main/java/org/softwareheritage/graph/Graph.java b/java/server/src/main/java/org/softwareheritage/graph/Graph.java
--- a/java/server/src/main/java/org/softwareheritage/graph/Graph.java
+++ b/java/server/src/main/java/org/softwareheritage/graph/Graph.java
@@ -3,6 +3,7 @@
 import java.io.IOException;
 
 import it.unimi.dsi.big.webgraph.BVGraph;
+import it.unimi.dsi.big.webgraph.LazyLongIterator;
 
 import org.softwareheritage.graph.Node;
 import org.softwareheritage.graph.SwhId;
@@ -139,6 +140,17 @@
     return graph.successorBigArray(nodeId);
   }
 
+  /**
+   * Returns lazy iterator of successors of a node.
+   *
+   * @param nodeId node specified as a long id
+   * @return lazy iterator of successors of the node, specified as a <a
+   * href="http://webgraph.di.unimi.it/">WebGraph</a> LazyLongIterator
+   */
+  public LazyLongIterator lazySuccessors(long nodeId) {
+    return graph.successors(nodeId);
+  }
+
   /**
    * Returns the outdegree of a node.
    *
@@ -153,13 +165,24 @@
    * Returns list of predecessors of a node.
    *
    * @param nodeId node specified as a long id
-   * @return list of successors of the node, specified as a <a
+   * @return list of predecessors of the node, specified as a <a
    * href="http://fastutil.di.unimi.it/">fastutil</a> LongBigArrays
    */
   public long[][] predecessors(long nodeId) {
     return graphTransposed.successorBigArray(nodeId);
   }
 
+  /**
+   * Returns lazy iterator of predecessors of a node.
+   *
+   * @param nodeId node specified as a long id
+   * @return lazy iterator of predecessors of the node, specified as a <a
+   * href="http://webgraph.di.unimi.it/">WebGraph</a> LazyLongIterator
+   */
+  public LazyLongIterator lazyPredecessors(long nodeId) {
+    return graphTransposed.successors(nodeId);
+  }
+
   /**
    * Returns the indegree of a node.
    *
@@ -182,14 +205,26 @@
   }
 
   /**
-   * Returns the neighbors of a node, depending on graph orientation.
+   * Returns the neighbors of a node (as a list), depending on graph orientation.
    *
    * @param nodeId node specified as a long id
    * @param useTransposed boolean value to use transposed graph
-   * @return list of successors of the node, specified as a <a
+   * @return list of neighbors of the node, specified as a <a
    * href="http://fastutil.di.unimi.it/">fastutil</a> LongBigArrays
    */
   public long[][] neighbors(long nodeId, boolean useTransposed) {
     return (useTransposed) ? predecessors(nodeId) : successors(nodeId);
   }
+
+  /**
+   * Returns the neighbors of a node (as a lazy iterator), depending on graph orientation.
+   *
+   * @param nodeId node specified as a long id
+   * @param useTransposed boolean value to use transposed graph
+   * @return lazy iterator of neighbors of the node, specified as a <a
+   * href="http://webgraph.di.unimi.it/">WebGraph</a> LazyLongIterator
+   */
+  public LazyLongIterator lazyNeighbors(long nodeId, boolean useTransposed) {
+    return (useTransposed) ? lazyPredecessors(nodeId) : lazySuccessors(nodeId);
+  }
 }
diff --git a/java/server/src/main/java/org/softwareheritage/graph/benchmark/AccessEdge.java b/java/server/src/main/java/org/softwareheritage/graph/benchmark/AccessEdge.java
new file mode 100644
--- /dev/null
+++ b/java/server/src/main/java/org/softwareheritage/graph/benchmark/AccessEdge.java
@@ -0,0 +1,49 @@
+package org.softwareheritage.graph.benchmark;
+
+import java.io.IOException;
+import java.util.ArrayList;
+
+import it.unimi.dsi.big.webgraph.LazyLongIterator;
+
+import org.softwareheritage.graph.Graph;
+import org.softwareheritage.graph.utils.Random;
+import org.softwareheritage.graph.utils.Statistics;
+import org.softwareheritage.graph.utils.Timing;
+
+/**
+ * Benchmark to time edge access time.
+ *
+ * @author Thibault Allançon
+ * @version 0.0.1
+ * @since 0.0.1
+ */
+
+public class AccessEdge {
+  /**
+   * Main entrypoint.
+   *
+   * @param args command line arguments
+   */
+  public static void main(String[] args) throws IOException {
+    String path = args[0];
+    Graph graph = new Graph(path);
+
+    final long seed = 42;
+    final long nbNodes = 1_000_000;
+    Random random = new Random(seed);
+    long[] nodeIds = random.generateNodeIds(graph, nbNodes);
+
+    ArrayList<Double> timings = new ArrayList<>();
+    for (long nodeId : nodeIds) {
+      long startTime = Timing.start();
+      LazyLongIterator neighbors = graph.lazySuccessors(nodeId);
+      long firstNeighbor = neighbors.nextLong();
+      double duration = (double) Timing.stop(startTime);
+      timings.add(duration);
+    }
+
+    System.out.println("Used " + nbNodes + " random edges (results are in seconds):");
+    Statistics stats = new Statistics(timings);
+    stats.printAll();
+  }
+}
diff --git a/java/server/src/main/java/org/softwareheritage/graph/utils/Random.java b/java/server/src/main/java/org/softwareheritage/graph/utils/Random.java
new file mode 100644
--- /dev/null
+++ b/java/server/src/main/java/org/softwareheritage/graph/utils/Random.java
@@ -0,0 +1,43 @@
+package org.softwareheritage.graph.utils;
+
+import org.softwareheritage.graph.Graph;
+
+/**
+ * Random related utility class.
+ *
+ * @author Thibault Allançon
+ * @version 0.0.1
+ * @since 0.0.1
+ */
+
+public class Random {
+  /** Internal pseudorandom generator */
+  java.util.Random random;
+
+  /**
+   * Constructor.
+   */
+  public Random() {
+    this.random = new java.util.Random();
+  }
+
+  /**
+   * Constructor.
+   *
+   * @param seed random generator seed
+   */
+  public Random(long seed) {
+    this.random = new java.util.Random(seed);
+  }
+
+  /**
+   * Generates random node ids.
+   *
+   * @param graph graph from which node ids will be picked
+   * @param nbNodes number of node ids to generate
+   * @return an array of random node ids
+   */
+  public long[] generateNodeIds(Graph graph, long nbNodes) {
+    return random.longs(nbNodes, 0, graph.getNbNodes()).toArray();
+  }
+}
diff --git a/java/server/src/main/java/org/softwareheritage/graph/utils/Statistics.java b/java/server/src/main/java/org/softwareheritage/graph/utils/Statistics.java
new file mode 100644
--- /dev/null
+++ b/java/server/src/main/java/org/softwareheritage/graph/utils/Statistics.java
@@ -0,0 +1,89 @@
+package org.softwareheritage.graph.utils;
+
+import java.util.ArrayList;
+
+/**
+ * Compute various statistics on a list of values.
+ *
+ * @author Thibault Allançon
+ * @version 0.0.1
+ * @since 0.0.1
+ */
+
+public class Statistics {
+  /** Input values */
+  ArrayList<Double> values;
+
+  /**
+   * Constructor.
+   *
+   * @param values input values
+   */
+  public Statistics(ArrayList<Double> values) {
+    this.values = values;
+  }
+
+  /**
+   * Returns the minimum value.
+   *
+   * @return minimum value
+   */
+  public double getMin() {
+    double min = Double.POSITIVE_INFINITY;
+    for (double v : values) {
+      min = Math.min(min, v);
+    }
+    return min;
+  }
+
+  /**
+   * Returns the maximum value.
+   *
+   * @return maximum value
+   */
+  public double getMax() {
+    double max = Double.NEGATIVE_INFINITY;
+    for (double v : values) {
+      max = Math.max(max, v);
+    }
+    return max;
+  }
+
+  /**
+   * Computes the average.
+   *
+   * @return average value
+   */
+  public double getAverage() {
+    double sum = 0;
+    for (double v : values) {
+      sum += v;
+    }
+    return sum / (double) values.size();
+  }
+
+  /**
+   * Computes the standard deviation.
+   *
+   * @return standard deviation value
+   */
+  public double getStandardDeviation() {
+    double average = getAverage();
+    double variance = 0;
+    for (double v : values) {
+      variance += (v - average) * (v - average);
+    }
+    variance /= (double) values.size();
+    return Math.sqrt(variance);
+  }
+
+  /**
+   * Computes and prints all statistical values.
+   */
+  public void printAll() {
+    System.out.println("min value: " + getMin());
+    System.out.println("max value: " + getMax());
+    System.out.println("average: " + getAverage());
+    System.out.println("standard deviation: " + getStandardDeviation());
+  }
+}