diff --git a/swh/provenance/graph.py b/swh/provenance/graph.py
--- a/swh/provenance/graph.py
+++ b/swh/provenance/graph.py
@@ -9,6 +9,7 @@
 import os
 from typing import Any, Dict, Optional, Set
 
+from swh.core.statsd import statsd
 from swh.model.hashutil import hash_to_hex
 from swh.model.model import Sha1Git
 
@@ -47,6 +48,10 @@
 
 
 class HistoryGraph:
+    @statsd.timed(
+        metric="swh_provenance_graph_accesstime_seconds",
+        tags={"method": "build_history_graph"},
+    )
     def __init__(
         self,
         archive: ArchiveInterface,
@@ -131,6 +136,9 @@
         return self._dbdate
 
     def invalidate(self) -> None:
+        statsd.increment(
+            metric="swh_provenance_graph", tags={"method": "invalidate_frontier"}
+        )
         self._dbdate = None
         self.maxdate = None
         self.known = False
@@ -162,6 +170,10 @@
         return hash((self.entry, self.depth, self.path))
 
 
+@statsd.timed(
+    metric="swh_provenance_graph_accesstime_seconds",
+    tags={"method": "build_isochrone_graph"},
+)
 def build_isochrone_graph(
     archive: ArchiveInterface,
     provenance: ProvenanceInterface,