diff --git a/swh/graph/luigi.py b/swh/graph/luigi.py
--- a/swh/graph/luigi.py
+++ b/swh/graph/luigi.py
@@ -641,6 +641,12 @@
                 header = next(csv_reader)
                 assert header == ["origin_SWHID", "person_id"], header
                 for (origin_swhid, person_id) in csv_reader:
+                    if person_id == "null":
+                        # FIXME: workaround for a bug in contribution graphs generated
+                        # before 2022-12-01. Those were only used in tests and never
+                        # published, so the conditional can be removed when this is
+                        # productionized
+                        continue
                     (name, escaped_name) = person_id_to_names[int(person_id)]
                     base64_name = base64.b64encode(name).decode("ascii")
                     csv_writer.writerow((origin_swhid, base64_name, escaped_name))
diff --git a/swh/graph/tests/dataset/compressed/example-labelled.labelobl b/swh/graph/tests/dataset/compressed/example-labelled.labelobl
new file mode 100644
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example-labelled.labeloffsets b/swh/graph/tests/dataset/compressed/example-labelled.labeloffsets
--- a/swh/graph/tests/dataset/compressed/example-labelled.labeloffsets
+++ b/swh/graph/tests/dataset/compressed/example-labelled.labeloffsets
@@ -1,2 +1 @@
-„í
-Âpæ)í š
\ No newline at end of file
+ úh*…¸~±tÐV
\ No newline at end of file
diff --git a/swh/graph/tests/dataset/compressed/example-labelled.labels b/swh/graph/tests/dataset/compressed/example-labelled.labels
--- a/swh/graph/tests/dataset/compressed/example-labelled.labels
+++ b/swh/graph/tests/dataset/compressed/example-labelled.labels
@@ -1 +1 @@
-D¤º%B](P(iõ‚¢
\ No newline at end of file
+§	BaéÂQ@RB@Ri
ПD
\ No newline at end of file
diff --git a/swh/graph/tests/dataset/compressed/example-labelled.properties b/swh/graph/tests/dataset/compressed/example-labelled.properties
--- a/swh/graph/tests/dataset/compressed/example-labelled.properties
+++ b/swh/graph/tests/dataset/compressed/example-labelled.properties
@@ -1,3 +1,3 @@
 graphclass = it.unimi.dsi.big.webgraph.labelling.BitStreamArcLabelledImmutableGraph
-labelspec = org.softwareheritage.graph.labels.SwhLabel(DirEntry,6)
+labelspec = org.softwareheritage.graph.labels.SwhLabel(DirEntry,7)
 underlyinggraph = example
diff --git a/swh/graph/tests/dataset/compressed/example-transposed-labelled.labelobl b/swh/graph/tests/dataset/compressed/example-transposed-labelled.labelobl
new file mode 100644
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example-transposed-labelled.labeloffsets b/swh/graph/tests/dataset/compressed/example-transposed-labelled.labeloffsets
--- a/swh/graph/tests/dataset/compressed/example-transposed-labelled.labeloffsets
+++ b/swh/graph/tests/dataset/compressed/example-transposed-labelled.labeloffsets
@@ -1,2 +1 @@
- šB•!B…
-(P¡‚”
\ No newline at end of file
+Ô.I,*0Z…‹èX
\ No newline at end of file
diff --git a/swh/graph/tests/dataset/compressed/example-transposed-labelled.labels b/swh/graph/tests/dataset/compressed/example-transposed-labelled.labels
--- a/swh/graph/tests/dataset/compressed/example-transposed-labelled.labels
+++ b/swh/graph/tests/dataset/compressed/example-transposed-labelled.labels
@@ -1,2 +1 @@
- P:¢RH•
-jºP u‚¢
\ No newline at end of file
+§â”%!P
£I

¢HJaА
\ No newline at end of file
diff --git a/swh/graph/tests/dataset/compressed/example-transposed-labelled.properties b/swh/graph/tests/dataset/compressed/example-transposed-labelled.properties
--- a/swh/graph/tests/dataset/compressed/example-transposed-labelled.properties
+++ b/swh/graph/tests/dataset/compressed/example-transposed-labelled.properties
@@ -1,3 +1,3 @@
 graphclass = it.unimi.dsi.big.webgraph.labelling.BitStreamArcLabelledImmutableGraph
-labelspec = org.softwareheritage.graph.labels.SwhLabel(DirEntry,6)
+labelspec = org.softwareheritage.graph.labels.SwhLabel(DirEntry,7)
 underlyinggraph = example-transposed
diff --git a/swh/graph/tests/dataset/compressed/example-transposed.graph b/swh/graph/tests/dataset/compressed/example-transposed.graph
--- a/swh/graph/tests/dataset/compressed/example-transposed.graph
+++ b/swh/graph/tests/dataset/compressed/example-transposed.graph
@@ -1 +1 @@
-^®—t5Òízèí
½®Ö…zºZá:¨»]À
\ No newline at end of file
+®¥òâ7ö/—Ë¥Úý:ÕÒõt´+Fº[#ê«ÅÐ
\ No newline at end of file
diff --git a/swh/graph/tests/dataset/compressed/example-transposed.obl b/swh/graph/tests/dataset/compressed/example-transposed.obl
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example-transposed.offsets b/swh/graph/tests/dataset/compressed/example-transposed.offsets
--- a/swh/graph/tests/dataset/compressed/example-transposed.offsets
+++ b/swh/graph/tests/dataset/compressed/example-transposed.offsets
@@ -1 +1,2 @@
-Š)	(P€ˆ‘‚†Š8&(R
\ No newline at end of file
+¡H48P¡B…E
+4h¡Ã¡@
\ No newline at end of file
diff --git a/swh/graph/tests/dataset/compressed/example-transposed.properties b/swh/graph/tests/dataset/compressed/example-transposed.properties
--- a/swh/graph/tests/dataset/compressed/example-transposed.properties
+++ b/swh/graph/tests/dataset/compressed/example-transposed.properties
@@ -1,35 +1,35 @@
 #BVGraph properties
-#Wed Mar 30 17:33:29 CEST 2022
-bitsforreferences=28
-avgbitsforintervals=0.762
+#Thu Dec 01 10:50:01 CET 2022
+bitsforreferences=31
+avgbitsforintervals=0.833
 graphclass=it.unimi.dsi.big.webgraph.BVGraph
-avgdist=0.429
-successoravggap=4.261
-residualexpstats=5,8,3,2,1
-arcs=23
+avgdist=0.417
+successoravggap=6.518
+residualexpstats=8,5,8,3,0,1
+arcs=28
 minintervallength=4
-bitsforoutdegrees=61
-residualavgloggap=2.076977934449935
-avgbitsforoutdegrees=2.905
-bitsforresiduals=85
-successoravgloggap=1.9987119736846723
+bitsforoutdegrees=68
+residualavgloggap=2.2068709506771227
+avgbitsforoutdegrees=2.833
+bitsforresiduals=115
+successoravgloggap=2.3010835643149283
 maxrefcount=3
-successorexpstats=7,9,4,2,1
-residualarcs=19
-avgbitsforresiduals=4.048
-avgbitsforblocks=0.19
+successorexpstats=9,5,8,4,1,1
+residualarcs=25
+avgbitsforresiduals=4.792
+avgbitsforblocks=0.125
 windowsize=7
-residualavggap=4.632
-copiedarcs=4
-avgbitsforreferences=1.333
+residualavggap=5.860
+copiedarcs=3
+avgbitsforreferences=1.292
 version=0
-compratio=1.53
-bitsperlink=8.435
+compratio=1.501
+bitsperlink=8.464
 compressionflags=
-nodes=21
-avgref=0.238
+nodes=24
+avgref=0.125
 zetak=3
-bitsforintervals=16
+bitsforintervals=20
 intervalisedarcs=0
-bitspernode=9.238
-bitsforblocks=4
+bitspernode=9.875
+bitsforblocks=3
diff --git a/swh/graph/tests/dataset/compressed/example.edges.count.txt b/swh/graph/tests/dataset/compressed/example.edges.count.txt
--- a/swh/graph/tests/dataset/compressed/example.edges.count.txt
+++ b/swh/graph/tests/dataset/compressed/example.edges.count.txt
@@ -1 +1 @@
-23
+28
diff --git a/swh/graph/tests/dataset/compressed/example.edges.stats.txt b/swh/graph/tests/dataset/compressed/example.edges.stats.txt
--- a/swh/graph/tests/dataset/compressed/example.edges.stats.txt
+++ b/swh/graph/tests/dataset/compressed/example.edges.stats.txt
@@ -1,8 +1,8 @@
 dir:cnt 8
 dir:dir 3
-ori:snp 1
-rel:rev 2
+ori:snp 2
+rel:rev 3
 rev:dir 4
 rev:rev 3
-snp:rel 1
-snp:rev 1
+snp:rel 3
+snp:rev 2
diff --git a/swh/graph/tests/dataset/compressed/example.graph b/swh/graph/tests/dataset/compressed/example.graph
--- a/swh/graph/tests/dataset/compressed/example.graph
+++ b/swh/graph/tests/dataset/compressed/example.graph
@@ -1 +1 @@
-}Ýø º]望˚étô]~[Ô1tޗ@
\ No newline at end of file
+]“؝~ÿåÓz]­
õY>ª¿.õ¤kºíè9Ñt
\ No newline at end of file
diff --git a/swh/graph/tests/dataset/compressed/example.indegree b/swh/graph/tests/dataset/compressed/example.indegree
--- a/swh/graph/tests/dataset/compressed/example.indegree
+++ b/swh/graph/tests/dataset/compressed/example.indegree
@@ -1,4 +1,5 @@
-2
+3
 16
-2
+4
+0
 1
diff --git a/swh/graph/tests/dataset/compressed/example.labels.count.txt b/swh/graph/tests/dataset/compressed/example.labels.count.txt
--- a/swh/graph/tests/dataset/compressed/example.labels.count.txt
+++ b/swh/graph/tests/dataset/compressed/example.labels.count.txt
@@ -1 +1 @@
-8
+9
diff --git a/swh/graph/tests/dataset/compressed/example.labels.csv.zst b/swh/graph/tests/dataset/compressed/example.labels.csv.zst
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.labels.fcl.bytearray b/swh/graph/tests/dataset/compressed/example.labels.fcl.bytearray
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.labels.fcl.pointers b/swh/graph/tests/dataset/compressed/example.labels.fcl.pointers
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.labels.fcl.properties b/swh/graph/tests/dataset/compressed/example.labels.fcl.properties
--- a/swh/graph/tests/dataset/compressed/example.labels.fcl.properties
+++ b/swh/graph/tests/dataset/compressed/example.labels.fcl.properties
@@ -1,2 +1,2 @@
-n=8
+n=9
 ratio=4
diff --git a/swh/graph/tests/dataset/compressed/example.labels.mph b/swh/graph/tests/dataset/compressed/example.labels.mph
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.mph b/swh/graph/tests/dataset/compressed/example.mph
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.node2swhid.bin b/swh/graph/tests/dataset/compressed/example.node2swhid.bin
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.node2type.map b/swh/graph/tests/dataset/compressed/example.node2type.map
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.nodes.count.txt b/swh/graph/tests/dataset/compressed/example.nodes.count.txt
--- a/swh/graph/tests/dataset/compressed/example.nodes.count.txt
+++ b/swh/graph/tests/dataset/compressed/example.nodes.count.txt
@@ -1 +1 @@
-21
+24
diff --git a/swh/graph/tests/dataset/compressed/example.nodes.csv.zst b/swh/graph/tests/dataset/compressed/example.nodes.csv.zst
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.nodes.stats.txt b/swh/graph/tests/dataset/compressed/example.nodes.stats.txt
--- a/swh/graph/tests/dataset/compressed/example.nodes.stats.txt
+++ b/swh/graph/tests/dataset/compressed/example.nodes.stats.txt
@@ -1,6 +1,6 @@
 cnt 7
 dir 6
-ori 1
-rel 2
+ori 2
+rel 3
 rev 4
-snp 1
+snp 2
diff --git a/swh/graph/tests/dataset/compressed/example.obl b/swh/graph/tests/dataset/compressed/example.obl
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.offsets b/swh/graph/tests/dataset/compressed/example.offsets
--- a/swh/graph/tests/dataset/compressed/example.offsets
+++ b/swh/graph/tests/dataset/compressed/example.offsets
@@ -1,2 +1,2 @@
-ŽA!B’‚i
-C‚B†
+Š
+(`¡¨rAD9E!A

\ No newline at end of file
diff --git a/swh/graph/tests/dataset/compressed/example.order b/swh/graph/tests/dataset/compressed/example.order
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.outdegree b/swh/graph/tests/dataset/compressed/example.outdegree
--- a/swh/graph/tests/dataset/compressed/example.outdegree
+++ b/swh/graph/tests/dataset/compressed/example.outdegree
@@ -1,4 +1,4 @@
 7
-6
+8
 7
-1
+2
diff --git a/swh/graph/tests/dataset/compressed/example.persons.mph b/swh/graph/tests/dataset/compressed/example.persons.mph
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.properties b/swh/graph/tests/dataset/compressed/example.properties
--- a/swh/graph/tests/dataset/compressed/example.properties
+++ b/swh/graph/tests/dataset/compressed/example.properties
@@ -1,35 +1,35 @@
 #BVGraph properties
-#Wed Mar 30 17:33:28 CEST 2022
-bitsforreferences=15
+#Thu Dec 01 10:50:00 CET 2022
+bitsforreferences=20
 avgbitsforintervals=0.667
 graphclass=it.unimi.dsi.big.webgraph.BVGraph
-avgdist=0.048
-successoravggap=3.935
-residualexpstats=8,9,2,2,1
-arcs=23
+avgdist=0.125
+successoravggap=5.125
+residualexpstats=4,9,8,4,1
+arcs=28
 minintervallength=4
-bitsforoutdegrees=51
-residualavgloggap=1.8895225435666037
-avgbitsforoutdegrees=2.429
-bitsforresiduals=98
-successoravgloggap=1.8859500382836039
+bitsforoutdegrees=62
+residualavgloggap=2.3484556402638956
+avgbitsforoutdegrees=2.583
+bitsforresiduals=122
+successoravgloggap=2.280971484604246
 maxrefcount=3
-successorexpstats=8,10,2,2,1
-residualarcs=22
-avgbitsforresiduals=4.667
-avgbitsforblocks=0.048
+successorexpstats=5,10,8,4,1
+residualarcs=26
+avgbitsforresiduals=5.083
+avgbitsforblocks=0.083
 windowsize=7
-residualavggap=4.000
-copiedarcs=1
-avgbitsforreferences=0.714
+residualavggap=5.385
+copiedarcs=2
+avgbitsforreferences=0.833
 version=0
-compratio=1.412
-bitsperlink=7.783
+compratio=1.406
+bitsperlink=7.929
 compressionflags=
-nodes=21
-avgref=0.048
+nodes=24
+avgref=0.083
 zetak=3
-bitsforintervals=14
+bitsforintervals=16
 intervalisedarcs=0
-bitspernode=8.524
-bitsforblocks=1
+bitspernode=9.25
+bitsforblocks=2
diff --git a/swh/graph/tests/dataset/compressed/example.property.author_id.bin b/swh/graph/tests/dataset/compressed/example.property.author_id.bin
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.property.author_timestamp.bin b/swh/graph/tests/dataset/compressed/example.property.author_timestamp.bin
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.property.author_timestamp_offset.bin b/swh/graph/tests/dataset/compressed/example.property.author_timestamp_offset.bin
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.property.committer_id.bin b/swh/graph/tests/dataset/compressed/example.property.committer_id.bin
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.property.committer_timestamp.bin b/swh/graph/tests/dataset/compressed/example.property.committer_timestamp.bin
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.property.committer_timestamp_offset.bin b/swh/graph/tests/dataset/compressed/example.property.committer_timestamp_offset.bin
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.property.content.is_skipped.bin b/swh/graph/tests/dataset/compressed/example.property.content.is_skipped.bin
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.property.content.length.bin b/swh/graph/tests/dataset/compressed/example.property.content.length.bin
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.property.message.bin b/swh/graph/tests/dataset/compressed/example.property.message.bin
--- a/swh/graph/tests/dataset/compressed/example.property.message.bin
+++ b/swh/graph/tests/dataset/compressed/example.property.message.bin
@@ -1,7 +1,9 @@
 VmVyc2lvbiAxLjA=
 VmVyc2lvbiAyLjA=
+VmVyc2lvbiAyLjAgYnV0IHdpdGggbm8gYXV0aG9y
 SW5pdGlhbCBjb21taXQ=
 QWRkIHBhcnNlcg==
 QWRkIHRlc3Rz
 UmVmYWN0b3IgY29kZWJhc2U=
 aHR0cHM6Ly9leGFtcGxlLmNvbS9zd2gvZ3JhcGg=
+aHR0cHM6Ly9leGFtcGxlLmNvbS9zd2gvZ3JhcGgy
diff --git a/swh/graph/tests/dataset/compressed/example.property.message.offset.bin b/swh/graph/tests/dataset/compressed/example.property.message.offset.bin
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.property.tag_name.bin b/swh/graph/tests/dataset/compressed/example.property.tag_name.bin
--- a/swh/graph/tests/dataset/compressed/example.property.tag_name.bin
+++ b/swh/graph/tests/dataset/compressed/example.property.tag_name.bin
@@ -1,2 +1,3 @@
 djEuMA==
 djIuMA==
+djIuMC1hbm9ueW1vdXM=
diff --git a/swh/graph/tests/dataset/compressed/example.property.tag_name.offset.bin b/swh/graph/tests/dataset/compressed/example.property.tag_name.offset.bin
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/compressed/example.stats b/swh/graph/tests/dataset/compressed/example.stats
--- a/swh/graph/tests/dataset/compressed/example.stats
+++ b/swh/graph/tests/dataset/compressed/example.stats
@@ -1,20 +1,20 @@
-nodes=21
-arcs=23
+nodes=24
+arcs=28
 loops=0
-successoravggap=4.588
-avglocality=2.522
+successoravggap=5.900
+avglocality=3.143
 minoutdegree=0
 maxoutdegree=3
-minoutdegreenode=1
-maxoutdegreenode=9
+minoutdegreenode=8
+maxoutdegreenode=1
 dangling=7
 terminal=7
-percdangling=33.333333333333336
-avgoutdegree=1.0952380952380953
-successorlogdeltastats=13,5,3,2
-successoravglogdelta=0.814
+percdangling=29.166666666666668
+avgoutdegree=1.1666666666666667
+successorlogdeltastats=13,9,3,2,1
+successoravglogdelta=0.880
 minindegree=0
-maxindegree=3
-minindegreenode=20
-maxindegreenode=17
-avgindegree=1.0952380952380953
+maxindegree=4
+minindegreenode=21
+maxindegreenode=3
+avgindegree=1.1666666666666667
diff --git a/swh/graph/tests/dataset/edges/origin/graph-all.edges.csv.zst b/swh/graph/tests/dataset/edges/origin/graph-all.edges.csv.zst
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/edges/origin/graph-all.nodes.csv.zst b/swh/graph/tests/dataset/edges/origin/graph-all.nodes.csv.zst
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/edges/release/graph-all.edges.csv.zst b/swh/graph/tests/dataset/edges/release/graph-all.edges.csv.zst
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/edges/release/graph-all.nodes.csv.zst b/swh/graph/tests/dataset/edges/release/graph-all.nodes.csv.zst
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/edges/snapshot/graph-all.edges.csv.zst b/swh/graph/tests/dataset/edges/snapshot/graph-all.edges.csv.zst
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/edges/snapshot/graph-all.nodes.csv.zst b/swh/graph/tests/dataset/edges/snapshot/graph-all.nodes.csv.zst
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/generate_dataset.py b/swh/graph/tests/dataset/generate_dataset.py
--- a/swh/graph/tests/dataset/generate_dataset.py
+++ b/swh/graph/tests/dataset/generate_dataset.py
@@ -1,6 +1,6 @@
 #!/usr/bin/env python3
 
-# Copyright (C) 2021  The Software Heritage developers
+# Copyright (C) 2021-2022  The Software Heritage developers
 # See the AUTHORS file at the top-level directory of this distribution
 # License: GNU General Public License version 3, or any later version
 # See top-level LICENSE file for more information
@@ -291,6 +291,16 @@
         message=b"Version 2.0",
         synthetic=False,
     ),
+    Release(
+        id=h(21),
+        name=b"v2.0-anonymous",
+        date=None,
+        author=None,
+        target_type=ObjectType.REVISION,
+        target=h(18),
+        message=b"Version 2.0 but with no author",
+        synthetic=False,
+    ),
     Snapshot(
         id=h(20),
         branches={
@@ -322,6 +332,40 @@
         metadata=None,
     ),
     Origin(url="https://example.com/swh/graph"),
+    Snapshot(
+        id=h(22),
+        branches={
+            b"refs/heads/master": SnapshotBranch(
+                target=h(9), target_type=TargetType.REVISION
+            ),
+            b"refs/tags/v1.0": SnapshotBranch(
+                target=h(10), target_type=TargetType.RELEASE
+            ),
+            b"refs/tags/v2.0-anonymous": SnapshotBranch(
+                target=h(21), target_type=TargetType.RELEASE
+            ),
+        },
+    ),
+    OriginVisit(
+        origin="https://example.com/swh/graph2",
+        date=datetime.datetime(
+            2013, 5, 7, 4, 20, 39, 369271, tzinfo=datetime.timezone.utc
+        ),
+        visit=1,
+        type="git",
+    ),
+    OriginVisitStatus(
+        origin="https://example.com/swh/graph2",
+        date=datetime.datetime(
+            2013, 5, 7, 4, 20, 41, 369271, tzinfo=datetime.timezone.utc
+        ),
+        visit=1,
+        type="git",
+        status="full",
+        snapshot=h(22),
+        metadata=None,
+    ),
+    Origin(url="https://example.com/swh/graph2"),
 ]
 
 
diff --git a/swh/graph/tests/dataset/img/example.dot b/swh/graph/tests/dataset/img/example.dot
--- a/swh/graph/tests/dataset/img/example.dot
+++ b/swh/graph/tests/dataset/img/example.dot
@@ -58,25 +58,34 @@
         node [shape=octagon];
         10 [label="rel:0x10"];
         19 [label="rel:0x19"];
+        21 [label="rel:0x21"];
 
         10 -> 09;
         19 -> 18;
+        21 -> 18;
     }
 
     subgraph cluster_snp {
         label="Snapshots";
         node [shape=doubleoctagon];
         20 [label="snp:0x20"];
+        22 [label="snp:0x22"];
 
         20 -> 09;
         20 -> 10;
+
+        22 -> 09;
+        22 -> 10;
+        22 -> 21;
     }
 
     subgraph cluster_ori {
         label="Origins";
         node [shape=egg];
-        21 [label="ori:0x21"];
+        ori1 [label="ori:8340"];
+        ori2 [label="ori:8f50"];
 
-        21 -> 20;
+        ori1 -> 20;
+        ori2 -> 22;
     }
 }
diff --git a/swh/graph/tests/dataset/orc/content/content-all.orc b/swh/graph/tests/dataset/orc/content/content-all.orc
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/orc/directory/directory-all.orc b/swh/graph/tests/dataset/orc/directory/directory-all.orc
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/orc/directory_entry/directory_entry-all.orc b/swh/graph/tests/dataset/orc/directory_entry/directory_entry-all.orc
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/orc/origin/origin-all.orc b/swh/graph/tests/dataset/orc/origin/origin-all.orc
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/orc/origin_visit/origin_visit-all.orc b/swh/graph/tests/dataset/orc/origin_visit/origin_visit-all.orc
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/orc/origin_visit_status/origin_visit_status-all.orc b/swh/graph/tests/dataset/orc/origin_visit_status/origin_visit_status-all.orc
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/orc/release/release-all.orc b/swh/graph/tests/dataset/orc/release/release-all.orc
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/orc/revision/revision-all.orc b/swh/graph/tests/dataset/orc/revision/revision-all.orc
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/orc/revision_extra_headers/revision_extra_headers-all.orc b/swh/graph/tests/dataset/orc/revision_extra_headers/revision_extra_headers-all.orc
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/orc/revision_history/revision_history-all.orc b/swh/graph/tests/dataset/orc/revision_history/revision_history-all.orc
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/orc/skipped_content/skipped_content-all.orc b/swh/graph/tests/dataset/orc/skipped_content/skipped_content-all.orc
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/orc/snapshot/snapshot-all.orc b/swh/graph/tests/dataset/orc/snapshot/snapshot-all.orc
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/dataset/orc/snapshot_branch/snapshot_branch-all.orc b/swh/graph/tests/dataset/orc/snapshot_branch/snapshot_branch-all.orc
index 0000000000000000000000000000000000000000..0000000000000000000000000000000000000000
GIT binary patch
literal 0
Hc$@<O00001

literal 0
Hc$@<O00001

diff --git a/swh/graph/tests/test_cli.py b/swh/graph/tests/test_cli.py
--- a/swh/graph/tests/test_cli.py
+++ b/swh/graph/tests/test_cli.py
@@ -54,5 +54,5 @@
         assert result.exit_code == 0, result
         properties = read_properties(Path(tmpdir) / "example.properties")
 
-    assert int(properties["nodes"]) == 21
-    assert int(properties["arcs"]) == 23
+    assert int(properties["nodes"]) == 24
+    assert int(properties["arcs"]) == 28
diff --git a/swh/graph/tests/test_grpc.py b/swh/graph/tests/test_grpc.py
--- a/swh/graph/tests/test_grpc.py
+++ b/swh/graph/tests/test_grpc.py
@@ -21,14 +21,14 @@
 
 def test_stats(graph_grpc_stub):
     stats = graph_grpc_stub.Stats(StatsRequest())
-    assert stats.num_nodes == 21
-    assert stats.num_edges == 23
+    assert stats.num_nodes == 24
+    assert stats.num_edges == 28
     assert isinstance(stats.compression_ratio, float)
     assert isinstance(stats.bits_per_node, float)
     assert isinstance(stats.bits_per_edge, float)
     assert isinstance(stats.avg_locality, float)
     assert stats.indegree_min == 0
-    assert stats.indegree_max == 3
+    assert stats.indegree_max == 4
     assert isinstance(stats.indegree_avg, float)
     assert stats.outdegree_min == 0
     assert stats.outdegree_max == 3
@@ -65,6 +65,7 @@
     )
     actual = [node.swhid for node in request]
     expected = [
+        "swh:1:snp:0000000000000000000000000000000000000022",
         "swh:1:snp:0000000000000000000000000000000000000020",
         "swh:1:rel:0000000000000000000000000000000000000010",
         "swh:1:rev:0000000000000000000000000000000000000013",
diff --git a/swh/graph/tests/test_http_client.py b/swh/graph/tests/test_http_client.py
--- a/swh/graph/tests/test_http_client.py
+++ b/swh/graph/tests/test_http_client.py
@@ -18,14 +18,14 @@
 
 def test_stats(graph_client):
     stats = graph_client.stats()
-    assert stats["num_nodes"] == 21
-    assert stats["num_edges"] == 23
+    assert stats["num_nodes"] == 24
+    assert stats["num_edges"] == 28
     assert isinstance(stats["compression_ratio"], float)
     assert isinstance(stats["bits_per_node"], float)
     assert isinstance(stats["bits_per_edge"], float)
     assert isinstance(stats["avg_locality"], float)
     assert stats["indegree_min"] == 0
-    assert stats["indegree_max"] == 3
+    assert stats["indegree_max"] == 4
     assert isinstance(stats["indegree_avg"], float)
     assert stats["outdegree_min"] == 0
     assert stats["outdegree_max"] == 3
@@ -69,6 +69,7 @@
         )
     )
     expected = [
+        "swh:1:snp:0000000000000000000000000000000000000022",
         "swh:1:snp:0000000000000000000000000000000000000020",
         "swh:1:rel:0000000000000000000000000000000000000010",
         "swh:1:rev:0000000000000000000000000000000000000013",
@@ -224,10 +225,15 @@
             "swh:1:dir:0000000000000000000000000000000000000002",
         ),
     ]
+
     # As there are four valid answers (up to reordering), we cannot check for
-    # equality. Instead, we check the client returned all edges but one.
+    # equality. Instead, we check the client returned either
+    # * all edges but one, or
+    # * all edges
+    # and the right answer depends on which edges were traversed, which is
+    # non-deterministic
     assert set(actual).issubset(set(expected))
-    assert len(actual) == 3
+    assert 3 <= len(actual) <= 4
 
 
 def test_visit_edges_diamond_pattern(graph_client):
@@ -384,7 +390,7 @@
     actual = graph_client.count_neighbors(
         "swh:1:rev:0000000000000000000000000000000000000009", direction="backward"
     )
-    assert actual == 3
+    assert actual == 4
 
 
 @pytest.mark.parametrize("max_matching_nodes", [0, 1, 2, 3, 4, 5, 10, 1 << 31])
diff --git a/swh/graph/tests/test_luigi.py b/swh/graph/tests/test_luigi.py
--- a/swh/graph/tests/test_luigi.py
+++ b/swh/graph/tests/test_luigi.py
@@ -26,8 +26,8 @@
 
     properties = read_properties(tmpdir / "compressed_graph" / "graph.properties")
 
-    assert int(properties["nodes"]) == 21
-    assert int(properties["arcs"]) == 23
+    assert int(properties["nodes"]) == 24
+    assert int(properties["arcs"]) == 28
 
     export_meta_path = tmpdir / "compressed_graph/meta/export.json"
     assert export_meta_path.read_bytes() == (DATA_DIR / "meta/export.json").read_bytes()
diff --git a/swh/graph/tests/test_origin_contributors.py b/swh/graph/tests/test_origin_contributors.py
--- a/swh/graph/tests/test_origin_contributors.py
+++ b/swh/graph/tests/test_origin_contributors.py
@@ -32,6 +32,10 @@
 origin_SWHID,person_id
 swh:1:ori:83404f995118bd25774f4ac14422a8f175e7a054,0
 swh:1:ori:83404f995118bd25774f4ac14422a8f175e7a054,2
+swh:1:ori:8f50d3f60eae370ddbf85c86219c55108a350165,0
+swh:1:ori:8f50d3f60eae370ddbf85c86219c55108a350165,null
+swh:1:ori:8f50d3f60eae370ddbf85c86219c55108a350165,1
+swh:1:ori:8f50d3f60eae370ddbf85c86219c55108a350165,2
 """
 
 DEANONYMIZATION_TABLE = """\
@@ -51,6 +55,9 @@
 origin_SWHID,person_base64,person_escaped
 swh:1:ori:83404f995118bd25774f4ac14422a8f175e7a054,SmFuZSBEb2UgPGpkb2VAZXhhbXBsZS5jb20+,Jane Doe <jdoe@example.com>
 swh:1:ori:83404f995118bd25774f4ac14422a8f175e7a054,Sm9obiBEb2UgPGpkb2VAZXhhbXBsZS5vcmc+,John Doe <jdoe@example.org>
+swh:1:ori:8f50d3f60eae370ddbf85c86219c55108a350165,SmFuZSBEb2UgPGpkb2VAZXhhbXBsZS5jb20+,Jane Doe <jdoe@example.com>
+swh:1:ori:8f50d3f60eae370ddbf85c86219c55108a350165,SmFuZSBEb2UgPGpkb2VAZXhhbXBsZS5uZXQ+,Jane Doe <jdoe@example.net>
+swh:1:ori:8f50d3f60eae370ddbf85c86219c55108a350165,Sm9obiBEb2UgPGpkb2VAZXhhbXBsZS5vcmc+,John Doe <jdoe@example.org>
 """  # noqa
 
 
diff --git a/swh/graph/tests/test_toposort.py b/swh/graph/tests/test_toposort.py
--- a/swh/graph/tests/test_toposort.py
+++ b/swh/graph/tests/test_toposort.py
@@ -11,16 +11,22 @@
 DATA_DIR = Path(__file__).parents[0] / "dataset"
 
 
+# FIXME: the order of sample ancestors should not be hardcoded
+# FIXME: swh:1:snp:0000000000000000000000000000000000000022,3,1,swh has three possible
+# sample ancestors; they should not be hardecoded here
 EXPECTED = """\
 SWHID,ancestors,successors,sample_ancestor1,sample_ancestor2
 swh:1:rev:0000000000000000000000000000000000000003,0,1,,
-swh:1:rev:0000000000000000000000000000000000000009,1,3,swh:1:rev:0000000000000000000000000000000000000003,
-swh:1:rel:0000000000000000000000000000000000000010,1,1,swh:1:rev:0000000000000000000000000000000000000009,
+swh:1:rev:0000000000000000000000000000000000000009,1,4,swh:1:rev:0000000000000000000000000000000000000003,
+swh:1:rel:0000000000000000000000000000000000000010,1,2,swh:1:rev:0000000000000000000000000000000000000009,
 swh:1:snp:0000000000000000000000000000000000000020,2,1,swh:1:rev:0000000000000000000000000000000000000009,swh:1:rel:0000000000000000000000000000000000000010
 swh:1:ori:83404f995118bd25774f4ac14422a8f175e7a054,1,0,swh:1:snp:0000000000000000000000000000000000000020,
 swh:1:rev:0000000000000000000000000000000000000013,1,1,swh:1:rev:0000000000000000000000000000000000000009,
-swh:1:rev:0000000000000000000000000000000000000018,1,1,swh:1:rev:0000000000000000000000000000000000000013,
+swh:1:rev:0000000000000000000000000000000000000018,1,2,swh:1:rev:0000000000000000000000000000000000000013,
 swh:1:rel:0000000000000000000000000000000000000019,1,0,swh:1:rev:0000000000000000000000000000000000000018,
+swh:1:rel:0000000000000000000000000000000000000021,1,1,swh:1:rev:0000000000000000000000000000000000000018,
+swh:1:snp:0000000000000000000000000000000000000022,3,1,swh:1:rev:0000000000000000000000000000000000000009,swh:1:rel:0000000000000000000000000000000000000010
+swh:1:ori:8f50d3f60eae370ddbf85c86219c55108a350165,1,0,swh:1:snp:0000000000000000000000000000000000000022,
 """
 
 
@@ -50,10 +56,12 @@
 
     assert rows.pop() == "", "Missing trailing newline"
 
-    # The only two possible last lines
+    # The only three possible last lines
     assert rows[-1] in [
         "swh:1:ori:83404f995118bd25774f4ac14422a8f175e7a054,1,0"
         ",swh:1:snp:0000000000000000000000000000000000000020,",
+        "swh:1:ori:8f50d3f60eae370ddbf85c86219c55108a350165,1,0"
+        ",swh:1:snp:0000000000000000000000000000000000000022,",
         "swh:1:rel:0000000000000000000000000000000000000019,1,0"
         ",swh:1:rev:0000000000000000000000000000000000000018,",
     ]