diff --git a/swh/web/api/views/graph.py b/swh/web/api/views/graph.py
--- a/swh/web/api/views/graph.py
+++ b/swh/web/api/views/graph.py
@@ -6,6 +6,7 @@
 from distutils.util import strtobool
 import json
 from typing import Dict, Iterator, Union
+from urllib.parse import quote
 
 import requests
 
@@ -135,7 +136,7 @@
                 "You do not have permission to perform this action.", status=403
             )
     graph_query_url = get_config()["graph"]["server_url"]
-    graph_query_url += graph_query
+    graph_query_url += quote(graph_query)
     if request.GET:
         graph_query_url += "?" + request.GET.urlencode(safe="/;:")
     response = requests.get(graph_query_url, stream=True)
diff --git a/swh/web/tests/api/views/test_graph.py b/swh/web/tests/api/views/test_graph.py
--- a/swh/web/tests/api/views/test_graph.py
+++ b/swh/web/tests/api/views/test_graph.py
@@ -6,6 +6,7 @@
 import hashlib
 import json
 import textwrap
+from urllib.parse import quote
 
 from hypothesis import given
 
@@ -86,11 +87,14 @@
         """
     )
 
-    requests_mock.get(
-        get_config()["graph"]["server_url"] + graph_query,
-        text=response_text,
-        headers={"Content-Type": "text/plain", "Transfer-Encoding": "chunked"},
-    )
+    # ensure compatibility with all requests-mock versions
+    # https://github.com/jamielennox/requests-mock/commit/f072845
+    for path in (graph_query, quote(graph_query)):
+        requests_mock.get(
+            get_config()["graph"]["server_url"] + path,
+            text=response_text,
+            headers={"Content-Type": "text/plain", "Transfer-Encoding": "chunked"},
+        )
 
     url = reverse("api-1-graph", url_args={"graph_query": graph_query})
 
@@ -148,14 +152,17 @@
         """
     )
 
-    requests_mock.get(
-        get_config()["graph"]["server_url"] + graph_query,
-        text=response_ndjson,
-        headers={
-            "Content-Type": "application/x-ndjson",
-            "Transfer-Encoding": "chunked",
-        },
-    )
+    # ensure compatibility with all requests-mock versions
+    # https://github.com/jamielennox/requests-mock/commit/f072845
+    for path in (graph_query, quote(graph_query)):
+        requests_mock.get(
+            get_config()["graph"]["server_url"] + path,
+            text=response_ndjson,
+            headers={
+                "Content-Type": "application/x-ndjson",
+                "Transfer-Encoding": "chunked",
+            },
+        )
 
     url = reverse("api-1-graph", url_args={"graph_query": graph_query})
 
@@ -205,11 +212,14 @@
         # set two lines response to check resolved origins cache
         response_text = response_text + response_text
 
-        requests_mock.get(
-            get_config()["graph"]["server_url"] + graph_query,
-            text=response_text,
-            headers={"Content-Type": content_type, "Transfer-Encoding": "chunked"},
-        )
+        # ensure compatibility with all requests-mock versions
+        # https://github.com/jamielennox/requests-mock/commit/f072845
+        for path in (graph_query, quote(graph_query)):
+            requests_mock.get(
+                get_config()["graph"]["server_url"] + path,
+                text=response_text,
+                headers={"Content-Type": content_type, "Transfer-Encoding": "chunked"},
+            )
 
         url = reverse(
             "api-1-graph",