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
@@ -21,6 +21,8 @@
    * dimension is source, second dimension is destination)
    */
   boolean[][] allowed;
+  /** When no edge restriction is enforced, bypass the type check code logic */
+  boolean bypassRestriction;
 
   /**
    * Constructor.
@@ -38,6 +40,7 @@
       return;
     }
     if (edgesFmt.equals("*")) {
+      this.bypassRestriction = true;
       for (int i = 0; i < nbNodeTypes; i++) {
         for (int j = 0; j < nbNodeTypes; j++) {
           allowed[i][j] = true;
@@ -66,6 +69,15 @@
   }
 
   /**
+   * Checks if all edges can be used or if edge restriction is enforced.
+   *
+   * @return true if edges=* and false otherwise
+   */
+  public boolean hasNoRestriction() {
+    return bypassRestriction;
+  }
+
+  /**
    * Checks if a given edge can be followed during graph traversal.
    *
    * @param srcNodeId edge source node
@@ -75,7 +87,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 allowed[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.hasNoRestriction()) {
+        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)) {