Legal AI systems trained in one country often fail in another. One of the few structural signals that ties jurisdictions together is the network of cross-border citations: Indian and Canadian courts citing English decisions, or European courts citing each other's human-rights rulings. Suppose that network, or a confidential analogue of it such as a consortium's internal record of which authorities were relied on in unpublished briefs, must be released under differential privacy. Differential privacy is a guarantee that the output barely changes if any single record is added or removed; here the record is one citation edge. Known error bounds for private graph algorithms say that noise hurts most where the graph is sparse. Our observation is that in a multi-jurisdiction legal graph, the sparsest part is the part that matters most for transfer. Citations inside a jurisdiction form dense clusters. Citations across jurisdictions form a thin cut between those clusters. Standard private mechanisms will therefore keep domestic precedent structure roughly intact while erasing cross-border authority.
We propose to measure this effect directly and then remove it with a simple mechanism. The mechanism rests on one fact that the generic private-graph literature does not use: a case's jurisdiction is public metadata. Because the partition into jurisdictions is known in advance, the graph can be split along it without spending any privacy budget. Cross-border citation mass can then be released at a coarser granularity, court-pair to court-pair, where counts are large enough to survive noise. Fine-grained cross-border edges are released only where the coarse counts justify it. The claim is testable in two parts. First, existing private mechanisms fail specifically on cross-jurisdiction edges, not uniformly. Second, a partition-aware release recovers cross-border precedent retrieval at privacy levels (ε ≤ 1) where those mechanisms fail.
Core Claim
The sparsity penalty is well documented. Local sensitivity can exceed the true value of a quantity on sparse graphs (Karwa et al.). Private Personalized PageRank (PPR) needs a high minimum degree to be accurate (Epasto et al.). PPR is a relevance score computed from random walks that restart at a query node. Private message passing in graph neural networks collapses on sparse graphs (Wu et al.). These results are stated for whole graphs. Our contribution is to show where the penalty falls when the graph has known block structure, and to exploit that structure.
The core arithmetic is short. Take two jurisdictions $A$ and $B$ with $|A|$ and $|B|$ cases and true cross-citation count $w_{AB}$. Releasing every potential edge with independent noise of scale $1/\epsilon$ gives an aggregate error on the cut of order $\sqrt{|A||B|}/\epsilon$. That figure comes from summing $|A||B|$ independent noise terms. Releasing the single aggregate count instead gives error of order $1/\epsilon$. The relative errors are therefore
$$ \text{flat: } \frac{\sqrt{|A||B|}}{\epsilon\, w_{AB}}, \qquad \text{aggregated: } \frac{1}{\epsilon\, w_{AB}}. $$
Cross-border cuts have $w_{AB} \ll |A||B|$, so flat noise drives the signal-to-noise ratio below one exactly on these cuts. Within-jurisdiction blocks are much denser and keep a usable ratio. Aggregating to courts rather than whole jurisdictions interpolates between the two regimes. This trades resolution for signal, and the experiments quantify that trade.
Relation to Prior Work
Three papers supply the method and constrain it.
Aamand et al. break the $n^{1.5}$ additive-error barrier for efficient private cut sparsification, reaching $n^{1.25+o(1)}/\epsilon$. They do this by privately computing an expander decomposition: they find dense well-connected pieces that tolerate noise and treat the few edges between pieces separately. We borrow the dense/sparse split. We differ in two ways. We do not search for the decomposition privately, because legal metadata hands it to us for free. We also target the inter-block edges as the object of interest rather than as a residual to keep small. The research file also notes that such decomposition methods can underperform plain noise addition on low-density networks, which is a reason to test rather than assume.
Epasto et al. make PPR edge-private by capping the flow each node can push, through a procedure they call PUSHFLOWCAP. They reach near-optimal error when the minimum degree is high. We reuse PUSHFLOWCAP inside dense jurisdiction blocks. Our addition is a way to handle the low-degree cross-border edges that PUSHFLOWCAP's guarantee explicitly does not cover.
Imola et al. prove an $\Omega(n^2/\epsilon)$ lower bound for private hierarchical clustering. They also show that near-optimal trees are achievable only under planted block models. This constrains us: we do not claim to recover arbitrary fine structure, only structure that is aligned with a known partition.
On the legal side, ProMALex builds a jurisdiction "family tree" from dataset embedding similarity to decide how adapters branch. LeXFiles shows that single-jurisdiction training traps models, with US-only PoL-BERT falling below general RoBERTa on LexGLUE. Both papers motivate the need for cross-jurisdictional signal but use only text. Neither touches citation structure or privacy. Law-Match and Elem4LCR show that structure beyond surface text, in the form of statutes and legal elements, improves case matching within Chinese civil law. That supports our premise that citation structure carries information text does not, though so far only within one jurisdiction.
Research Program
We first build the testbed. From LeXFiles case-law sub-corpora covering the EU, the Council of Europe (ECtHR), the UK, Canada, India and the US, we will extract citations to cases in the same or other sub-corpora. Each case is labelled with its public jurisdiction and court. No multi-jurisdiction citation graph is reported on Lacuna, so this construction is itself a deliverable, and we will release its extraction precision on a hand-checked sample.
We are candid about the privacy model. Published citations are public. We use them as a proxy for structurally similar confidential graphs, such as unpublished briefing citations or matter-to-authority links in firms exchanging data across borders under incompatible regimes of the kind highlighted by the BRIDGE pilot. The public version is useful precisely because it lets us measure error against ground truth.
The analysis stage applies randomized response, flat-noise release, PUSHFLOWCAP, and a practical implementation of private expander decomposition to this graph. It reports relative error broken down by edge type: within-jurisdiction, cross-jurisdiction, and endpoint degree bucket. This tests the first half of the claim.
The mechanism stage has three steps.
- We release noisy court-by-court cross-jurisdiction citation counts with the Laplace mechanism. Each edge lies in exactly one court pair, so parallel composition applies.
- Within each jurisdiction block we run PUSHFLOWCAP.
- For court pairs whose noisy count clears a threshold chosen by the sparse vector technique, we release fine cross-border edges using a small reserved share of the budget. For the remaining pairs, cross-border PPR mass is spread uniformly across the member cases of the court pair.
Downstream PPR is computed on the reconstructed graph, which is pure post-processing and so costs no additional privacy. The guarantee is edge-level differential privacy under basic composition across the three steps. Node-level privacy is out of scope. We also assume that a case's jurisdiction and court are not themselves secret.
Baselines
The naive reference point is a text-only retriever that uses no graph and therefore spends no privacy budget. We use both BM25 and a dense encoder built on LexLM, the model introduced with LeXFiles. This baseline is the real test of whether private graph structure is worth releasing at all. LexGLUE reports that TF-IDF with an SVM beat several Transformers on SCOTUS, so lexical methods are not a straw man in this domain.
The non-private ceiling is exact PPR on the true graph.
The weakest private baseline is randomized response, which flips each potential edge independently. On Blogcatalog, Epasto et al. report that it stays flat at roughly 14 Micro-F1 in node classification across ε.
The strongest existing private competitor is PUSHFLOWCAP from the same paper. On Blogcatalog it reaches roughly 18–20 Micro-F1 across ε, and it keeps high Recall@100 and NDCG at ε < 1. We will first reproduce these Blogcatalog numbers to validate our implementation. We found no reported result on Lacuna for any private PPR method on legal citation graphs. We will also run private expander decomposition following Aamand et al. where it is computationally feasible. If it is not, we will say so rather than substitute a weaker proxy.
All private methods receive identical total ε values (0.5, 1, 2, 4) on the same graph and the same query set. Each gets the same hyperparameter grid, covering caps, thresholds and budget splits, which is tuned on a held-out validation jurisdiction pair. Results are averaged over ten noise seeds.
Two ablations isolate the key ingredient. In the first, we replace the jurisdiction partition with a random partition that has the same block sizes. If the gain comes from aligning noise with the true sparse cut, it should vanish. In the second, we drop the fine-edge step to measure how much the coarse aggregates carry on their own.
To count as beating PUSHFLOWCAP, the method must improve cross-jurisdiction Recall@100 at ε = 1 by more than the across-seed spread. It must do so without losing more than a small margin on within-jurisdiction retrieval, and the random-partition ablation must not match it.
Why not just…?
Why not just use randomized response, which is trivially private? On sparse graphs it creates a dense background of false edges, which is roughly quadratic in the number of nodes. Epasto et al. found it often no better than random for ranking. The arithmetic above predicts it will be worst on cross-border cuts. We include it anyway so that the per-edge-type error breakdown shows this directly.
Why not just run PUSHFLOWCAP at a larger ε, or drop low-degree cases? Dropping low-degree cases discards the cross-border citations, and many of those are the rarely cited decisions that establish narrow exceptions. Raising ε weakens the guarantee without addressing why the error is concentrated. The degree-bucketed error curves will show whether PUSHFLOWCAP's loss is spread evenly, which would make ε tuning a fair answer, or concentrated on cross edges, which is our prediction.
Why not just retrieve foreign precedent from text and skip the graph? This is the most serious threat. If the text-only dense retriever matches private PPR on cross-jurisdiction Recall@100, then releasing the graph is not worth its privacy cost for this task, and we will report that. The evidence that structure beyond text helps comes from within Chinese law (Law-Match raises Sentence-BERT on ELAM from 68.83% to 73.15%) and has not been shown across borders. We will therefore also evaluate a hybrid that combines text and PPR scores. The hybrid is the fairer test of whether graph signal adds anything beyond text.
Why not just privatize ProMALex's jurisdiction tree instead? That tree has fewer than ten leaves, and each is built from thousands of documents. Adding Gaussian noise to per-jurisdiction mean embeddings would already give an accurate private tree, so the sparsity lower bounds of Imola et al. barely bite there. We set it aside because the easy solution probably works. As a secondary result, we will report whether the privately released court-pair citation counts induce a jurisdiction tree that agrees with ProMALex's embedding-based one.
Proposed Experiments and Decisive Checks
The first check is diagnostic. On the full citation graph at ε = 1, we plot relative error against endpoint degree separately for within-jurisdiction and cross-jurisdiction edges, under each baseline. The core claim is falsified if cross edges show no excess error once degree is controlled for. That outcome would mean the problem is ordinary low degree, which PUSHFLOWCAP-style caps already address. The accompanying check is quantitative: whether the observed cut-level error follows the $\sqrt{|A||B|}/(\epsilon w_{AB})$ scaling across jurisdiction pairs of different sizes.
The second check is the main task, cross-border precedent retrieval. We hold out 20% of cross-jurisdiction citations. For each citing case, we rank candidate cases in the cited jurisdiction by private PPR, then report Recall@100 and NDCG as in Epasto et al., across the ε sweep. Within-jurisdiction retrieval is reported alongside as a guard against robbing one to pay the other. The third check runs the random-partition and no-fine-edge ablations on the same queries. The fourth sweeps aggregation granularity from court level to whole-jurisdiction level, tracing the resolution-versus-signal curve the arithmetic predicts.
A result is decisive in favour of the proposal only if three conditions hold together. The partition-aware release must beat PUSHFLOWCAP on cross-border retrieval at ε ≤ 1. The random-partition ablation must lose that gain. The hybrid of text and private graph must beat text alone.
References
- Private Analysis of Graph Structure
- Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank
- Privacy-preserving design of graph neural networks with applications to vertical federated learning
- Breaking the n1.5 Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
- Differentially Private Hierarchical Clustering with Provable Approximation Guarantees
- ProMALex: Progressive Modular Adapters for Multi-Jurisdictional Legal Language Modeling
- LeXFiles and LegalLAMA: Facilitating English Multinational Legal Language Model Development
- Law Article-Enhanced Legal Case Matching: A Causal Learning Approach
- An Element is Worth a Thousand Words: Enhancing Legal Case Retrieval by Incorporating Legal Elements
- BRIDGE pilot study: a bilateral regulatory investigation of data governance and exchange
- LexGLUE: A Benchmark Dataset for Legal Language Understanding in English