When OCR Errors Split People: Structural Re-identification of Pseudonymized Scanned Archives

Scanned archives such as the tobacco-industry collection behind FUNSD, DocVQA and RVL-CDIP are now being pseudonymized before release: detected names are swapped for fake ones, and the fakes are drawn back into the page image. That protects against someone reading a name off the page. It does not obviously protect against a different attack. Who writes to whom, who is copied on which memo, and who signs alongside whom forms a network, and network research has shown that such networks work like fingerprints. An adversary holding a second, named corpus can line up the two networks and recover identities without reading any removed text. Scanned archives add a complication that this theory never modeled. OCR errors do not just add or drop links. They split one person into several graph nodes ("Smith, J." and "Srnith J."), and sometimes merge two people into one. They also cause the name detector to miss mentions, so some real names leak through unreplaced.

This note proposes to measure and exploit that complication. Our central claim is that OCR noise affects structural re-identification mainly by fragmenting nodes, not by perturbing edges. We further claim that an attacker who treats "which mentions are the same person" as a latent variable, inferred jointly with the alignment, recovers most of the identifiability that a fix-then-match pipeline loses. The same analysis gives archive publishers something they currently lack: an estimate of structural re-identification risk as a function of character error rate. It also says which people, typically those with many correspondents, stay exposed after text-level pseudonymization.

Core Claim

Two results in graph re-identification theory treat the node set as fixed and model noise as independent edge flips. On the privacy of anonymized networks shows perfect matching becomes possible once average degree grows slightly faster than $\log N$. A Concentration of Measure Approach to Correlated Graph Matching casts alignment as channel decoding over correlated random graphs. Both motivate the attack and constrain our predictions. Neither covers a channel that changes the vertex set.

Fragmentation has a simple first-order consequence. Suppose a person of true degree $d$ is split into $m$ fragments. Each fragment carries roughly $d/m$ edges, so its degree falls toward or below the $\log N$ regime. People with many correspondents should stay re-identifiable under heavy OCR noise, while people with few should drop out abruptly. Uniform edge noise at the same total corruption would not produce this pattern.

We therefore predict three things. First, re-identification accuracy under realistic OCR noise falls faster than under an edge-flip model matched on the number of corrupted edges. Second, the loss concentrates in low-degree identities. Third, jointly inferring fragment merges with the alignment closes most of that gap.

We also predict a counterintuitive interaction with pseudonymization. De-Identification of Sensitive Personal Data in Datasets Derived from IIT-CDIP reports that off-the-shelf detectors miss up to 30% of some PII types on these scans. Every missed name is a free anchor point for the attacker, which turns a seed-free matching problem into a seeded one.

Research Program

The work has three parts: an adversary model, a noise-aware matcher, and a measurement study.

Adversary model. The target is a pseudonymized person-document graph built from scanned records. OCR runs first. The PII detector then assigns pseudonyms, one per distinct detected string, so an OCR variant of a name gets its own pseudonym. This produces splits on the target side that carry no string evidence at all. The auxiliary graph comes from a disjoint set of named documents. Its nodes are OCR'd name strings, so it also contains splits, but here string similarity is evidence. The attacker's goal is to map target identities to auxiliary identities.

Matcher. The matcher alternates two steps.

In the structural step, identities are embedded from their $k$-hop neighborhoods. We use a graph attention network trained with a triplet ranking loss, as in Interaction data are identifiable even across long periods of time. That method supplies the architecture; unlike it, we must handle unknown node identity. Candidate pairs are then ranked with the diversity and popularity scores of Blind De-anonymization Attacks using Social Networks.

In the merge step, fragments are proposed for merging on each side:

  • Auxiliary side. The score combines a character-confusion likelihood with structural agreement. The confusion likelihood is estimated by comparing Tesseract and Textract transcriptions of the same pages. Structural agreement asks whether the fragments' neighbors map to the same or neighboring identities in the other graph.
  • Target side. Pseudonyms carry no string signal, so merges rest on structure alone. The evidence is that two fragments co-occur with overlapping neighbors, never co-occur in one document, and jointly match a single auxiliary identity better than either does alone.

Leaked real names are used as seeds when present.

Measurement study. We will chart re-identification accuracy against character error rate, broken down by true degree. We will also fit the fragmentation-adjusted degree to the $\log N$ threshold to test the first-order prediction above.

Baselines

Naive reference. Random assignment, plus the leaked-name-only attack. The latter simply maps every unredacted real name that survives pseudonymization. It measures how much the 30% detector miss rate alone gives away, before any structural reasoning.

Pipeline attack. This is the strongest existing method adapted to the setting. First, resolve entities on each side with fuzzy string clustering at a threshold tuned on held-out data. Second, run the blind attack of Blind De-anonymization Attacks using Social Networks, with the leaked names given to it as seeds. Third, run the triplet-trained graph attention matcher of Interaction data are identifiable even across long periods of time. Blind de-anonymization reports roughly a tenfold improvement over prior attacks under noisy conditions on a 36,458-scientist co-authorship graph, and 81% to 89% accuracy on Gowalla cross-domain matching. The graph-attention attack reports 52.4% top-1 and 77.2% top-10 accuracy at $k=2$ with a one-week delay on 40,000 phone subscribers. Neither number was obtained under OCR noise. We found no reported result on Lacuna for any structural re-identification attack on OCR-derived graphs.

These methods are the right competitors because they are exactly what a capable attacker would run today. For fairness, the pipeline and our matcher share the same graphs, the same encoder architecture and training budget, and the same number of hyperparameter trials. The pipeline's string threshold is tuned on the same validation split we use.

What counts as beating them. We need a top-1 gain large enough to exceed the variation across five random document splits and to hold across at least three noise levels. The gain must be concentrated where the theory predicts, in low- and mid-degree identities.

Ablations. Three ablations isolate the key ingredient. The first disables target-side structural merging. The second disables auxiliary-side merging. The third replaces the learned confusion likelihood with plain edit distance. If the gain disappears only when merging is disabled, joint identity inference is the mechanism rather than the encoder.

Why not just…?

Why not just look up the document text in the public archive? For IIT-CDIP-derived data this is a real threat. The source collection is public, and full-text retrieval of a document's non-PII body would likely find its original and undo pseudonymization outright. We will measure this with BM25 against OCR-IDL, and we expect it to succeed often. We will report that openly as a finding about text-level pseudonymization. Our threat model deliberately excludes it: target and auxiliary documents are disjoint, so the attacker must link people across different documents. This is the realistic case when the auxiliary corpus is a different archive, and it is where structure has to do the work.

Why not just match people by the text around their mentions, using noise-robust embeddings? Cheap Character Noise for OCR-Robust Multilingual Embeddings shows that fine-tuning with 5% synthetic character noise makes embeddings robust, including a gain of over 4 points on a Blackletter retrieval task. We will train exactly such an embedding on pooled mention contexts and use it as a non-structural baseline, and also as an extra node feature for our matcher. If context text alone matches structure, the claim that topology carries the identity signal fails. The design is set up to show that.

Why not just clean the OCR or the images first and then run a standard matcher? This is the pipeline baseline above, using the best available engine. OCR-IDL: OCR Annotations for Industry Document Library Dataset documents that commercial engines far outperform Tesseract, yet FUNSD: A Dataset for Form Understanding in Noisy Scanned Documents still reports only 94.4% Levenshtein similarity even for Google Vision. Residual splits are therefore unavoidable. More importantly, target-side splits come from pseudonymization itself and cannot be fixed by better OCR once pseudonyms have been assigned. We will run the Textract-quality condition as the pipeline's best case.

Proposed Experiments

Controlled tier. We use the co-authorship graph from Blind De-anonymization Attacks using Social Networks, where true identities are known exactly.

  • Author names are rendered as page images, degraded with Augraphy as in the IIT-CDIP de-identification work, and re-OCR'd with Tesseract at graded degradation levels.
  • The graph is split into a target and an auxiliary copy, and the target is pseudonymized with Faker using per-string pseudonyms and a simulated detector miss rate.
  • The decisive check compares two conditions matched on the number of corrupted edges: this realistic fragmentation channel, and an edge-flip channel.

We will report top-1 and top-10 accuracy by degree bin. The core claim is supported if fragmentation hurts low-degree identities disproportionately and our matcher recovers most of the difference. It is refuted if the two channels hurt equally.

Realistic tier. We use OCR-IDL. From memo and letter headers we build person-document graphs over sender, recipient, cc and signatory roles, split them into disjoint document sets, and compare Textract and Tesseract transcriptions of the same pages. Ground truth comes from Textract-based entity resolution, with a manually verified sample of several hundred identities used to estimate label noise.

Defensive readout. We will report the fraction of identities still re-identifiable after Larson-style pseudonymization at each character error rate.

Transfer test. The auxiliary-side confusion model is fitted on one OCR engine and evaluated on the other.