diff --git a/java/server/src/main/java/org/softwareheritage/graph/AllowedEdges.java b/java/server/src/main/java/org/softwareheritage/graph/AllowedEdges.java
--- a/java/server/src/main/java/org/softwareheritage/graph/AllowedEdges.java
+++ b/java/server/src/main/java/org/softwareheritage/graph/AllowedEdges.java
@@ -18,9 +18,10 @@
   Graph graph;
   /**
    * 2D boolean matrix storing access rights for all combination of src/dst node types (first
-   * dimension is source, second dimension is destination)
+   * dimension is source, second dimension is destination), when edge restriction is not enforced
+   * this array is set to null for early bypass.
    */
-  boolean[][] allowed;
+  public boolean[][] restrictedTo;
 
   /**
    * Constructor.
@@ -32,17 +33,14 @@
     this.graph = graph;
 
     int nbNodeTypes = Node.Type.values().length;
-    this.allowed = new boolean[nbNodeTypes][nbNodeTypes];
+    this.restrictedTo = new boolean[nbNodeTypes][nbNodeTypes];
     // Special values (null, empty, "*")
     if (edgesFmt == null || edgesFmt.isEmpty()) {
       return;
     }
     if (edgesFmt.equals("*")) {
-      for (int i = 0; i < nbNodeTypes; i++) {
-        for (int j = 0; j < nbNodeTypes; j++) {
-          allowed[i][j] = true;
-        }
-      }
+      // Allows for quick bypass (with simple null check) when no edge restriction
+      restrictedTo = null;
       return;
     }
 
@@ -59,7 +57,7 @@
       ArrayList<Node.Type> dstTypes = Node.Type.parse(nodeTypes[1]);
       for (Node.Type srcType : srcTypes) {
         for (Node.Type dstType : dstTypes) {
-          allowed[srcType.ordinal()][dstType.ordinal()] = true;
+          restrictedTo[srcType.ordinal()][dstType.ordinal()] = true;
         }
       }
     }
@@ -75,7 +73,7 @@
   public boolean isAllowed(long srcNodeId, long dstNodeId) {
     Node.Type srcType = graph.getNodeType(srcNodeId);
     Node.Type dstType = graph.getNodeType(dstNodeId);
-    return isAllowed(srcType, dstType);
+    return restrictedTo[srcType.ordinal()][dstType.ordinal()];
   }
 
   /**
@@ -85,6 +83,6 @@
    * @see AllowedEdges#isAllowed(long, long)
    */
   public boolean isAllowed(Node.Type srcType, Node.Type dstType) {
-    return allowed[srcType.ordinal()][dstType.ordinal()];
+    return restrictedTo[srcType.ordinal()][dstType.ordinal()];
   }
 }
diff --git a/java/server/src/main/java/org/softwareheritage/graph/Neighbors.java b/java/server/src/main/java/org/softwareheritage/graph/Neighbors.java
--- a/java/server/src/main/java/org/softwareheritage/graph/Neighbors.java
+++ b/java/server/src/main/java/org/softwareheritage/graph/Neighbors.java
@@ -64,8 +64,18 @@
       this.neighbors = graph.neighbors(srcNodeId, useTransposed);
     }
 
-    // Look ahead because with edge restriction not all neighbors are considered
     public boolean hasNext() {
+      // No edge restriction case: bypass type checks and skip to next neighbor
+      if (edges.restrictedTo == null) {
+        if (nextNeighborIdx + 1 < nbNeighbors) {
+          nextNeighborIdx++;
+          return true;
+        } else {
+          return false;
+        }
+      }
+
+      // Edge restriction case: look ahead for next neighbor
       for (long lookAheadIdx = nextNeighborIdx + 1; lookAheadIdx < nbNeighbors; lookAheadIdx++) {
         long nextNodeId = LongBigArrays.get(neighbors, lookAheadIdx);
         if (edges.isAllowed(srcNodeId, nextNodeId)) {
diff --git a/java/server/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java b/java/server/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java
--- a/java/server/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java
+++ b/java/server/src/test/java/org/softwareheritage/graph/AllowedEdgesTest.java
@@ -3,7 +3,7 @@
 import java.util.ArrayList;
 
 import org.junit.Test;
-import static org.junit.Assert.assertTrue;
+import org.junit.Assert;
 
 import org.softwareheritage.graph.AllowedEdges;
 import org.softwareheritage.graph.GraphTest;
@@ -43,7 +43,7 @@
           }
         }
 
-        assertTrue("Edge type: " + src + " -> " + dst, isAllowed == isExpected);
+        Assert.assertTrue("Edge type: " + src + " -> " + dst, isAllowed == isExpected);
       }
     }
   }
@@ -96,7 +96,6 @@
   public void allEdges() {
     Graph graph = getGraph();
     AllowedEdges edges = new AllowedEdges(graph, "*:*");
-    AllowedEdges edges2 = new AllowedEdges(graph, "*");
     ArrayList<EdgeType> expected = new ArrayList<>();
     for (Node.Type src : Node.Type.values()) {
       for (Node.Type dst : Node.Type.values()) {
@@ -104,7 +103,10 @@
       }
     }
     assertEdgeRestriction(edges, expected);
-    assertEdgeRestriction(edges2, expected);
+
+    // Special null value used to quickly bypass edge check when no restriction
+    AllowedEdges edges2 = new AllowedEdges(graph, "*");
+    Assert.assertNull(edges2.restrictedTo);
   }
 
   @Test