Who Leaked the Edge? Auditing Graph Anonymization When Nodes Carry Images and Text

Graph anonymization edits a network's connections before it is shared, adding, deleting or rewiring edges so that sensitive links and identities cannot be recovered while the graph stays useful. Nearly all of this work assumes the attacker sees only the graph's wiring plus a small bag of tabular features. Many graphs people now want to release are multimodal-attributed graphs, where each node also carries a product photo, a cover image, a post, or a description. Examples include co-purchase networks, book graphs and social image networks. On such graphs, two people's pictures and words may reveal that they are linked even after the link is deleted. Today's attackers for this setting are often multimodal language models, which bring two known problems of their own. They lean on text and underuse images, and they may have memorized the public benchmark graph during web-scale pretraining.

This note proposes an audit that splits an attacker's success at recovering hidden links into three sources: the remaining graph wiring, each content modality separately, and pretraining memorization. Memorization is isolated with "twin graphs." A twin keeps the real node content but has freshly sampled edges that match the original's statistics, so recalling the public edges is wrong on the twin. The audit tests two predictions. First, anonymizers tuned against structure-only attackers leave most link information readable from content. Second, raw audits by language-model attackers are miscalibrated in both directions: memorization makes them overstate leakage, and text bias makes them understate leakage in image-driven domains. As a constructive test of the audit, we extend plausible fake-edge generation so that decoy edges look realistic in content space as well as structurally.

Core Claim

Towards Plausible Graph Anonymization showed that fake edges which ignore local clustering can be separated from real ones with AUC above 0.95 using only structural node embeddings. Their fix samples fake edges from the original graph's structural-proximity distribution. We claim this fix is necessary but not sufficient on multimodal-attributed graphs. A decoy edge that is structurally plausible but joins two nodes whose images and text are unrelated is just as detectable, by an attacker that compares their image and text embeddings. A deleted sensitive edge between visually and semantically similar nodes is also recoverable from content alone.

The supporting evidence is indirect. Multimodal Graph Benchmark reports that adding visual features raises Amazon-Sports link prediction MRR from about 11.1 to about 30.45. That gain means content carries a large share of edge information. OpenMAG finds that text dominates in e-commerce graphs while images dominate in social media graphs. So which modality leaks should depend on the domain.

The second half of the claim concerns the auditor. Attention studies find that text tokens absorb about 75% of deep-layer attention in vision-language models (Mitigating Hallucination in Visual-Language Models via Re-Balancing Contrastive Decoding). Only about 15% of attention heads do real cross-modal work (Behind the Scene: Revealing the Secrets of Pre-trained Vision-and-Language Models). A text-biased auditor should therefore underestimate leakage carried by images. Separately, contamination studies such as DyVal show that static public benchmarks inflate model scores through memorization. Public graphs like Amazon co-purchases and Wikipedia-derived knowledge graphs are plausible targets for the same inflation, so an auditor may "recover" edges it simply remembers.

Relation to Prior Work

The privacy line supplies the threat models and the defenses we extend. Learning-Based Privacy-Preserving Graph Publishing Against Sensitive Link Inference Attacks, called PPGSL, treats the published adjacency matrix as a learnable object trained against a repeatedly retrained graph neural network attacker. Unveiling Privacy Vulnerabilities: Investigating the Role of Structure in Graph Data shows that structural roles leak attributes even between unconnected nodes, and it prunes risky edges with a learned sampler. Both use low-dimensional unimodal features, on graphs such as Cora and Pokec. We keep their attack-and-defend setup but move it to image-and-text nodes and add explicit modality and memorization controls.

The modality-bias line supplies diagnostic tools rather than the problem. We reuse two of them only to probe whether a language-model auditor is underusing images. The first is the inference-time decoding correction of Re-Balancing Contrastive Decoding (RBD). The second is the lightweight visual-token steering of LLaVA Steering, together with its layer-wise ratio of attention given to visual versus text tokens.

The contamination line motivates the twin-graph control. Dynamic Multimodal Evaluation via Knowledge-Enhanced Benchmark Evolution is the closest bridge. It rewrites visual question answering items as knowledge subgraphs and mutates them to escape memorization. However, its graph is only a scratchpad for generating questions. It does not study privacy, and it expands only through text triplets.

Our use of generated graphs differs in purpose. DyVal and KBE-DME generate new test items to measure reasoning. We regenerate edges around fixed real content to measure how much of an attacker's success is recall. Plausibility matters for the same reason Humbert et al. identified: a twin with implausible structure would itself be detectable.

Research Program

The work has three components.

Twin graph construction. For each dataset we fit an edge model on the original graph. It predicts an edge's probability from structural proximity, image-embedding similarity and text-embedding similarity. We sample a twin edge set that matches the degree sequence, clustering and content-similarity distribution of the original but overlaps it only partially. We check that twins pass the Humbert plausibility test: a structural-embedding detector trained to tell twin edges from original edges should sit near AUC 0.5.

Leakage decomposition. We designate 10% of edges as sensitive, as PPGSL does, apply an anonymizer, and run a family of attackers. The family includes a structure-only attacker, content-only attackers using image only, text only, and both, and combined attackers. It also includes a multimodal language model prompted with node pairs, run three ways: as is, with images blanked, and with visual steering applied. Running every attacker on both the original graph and its twins separates the sources. Attack AUC that falls on twins measures memorization. Gaps between modality ablations measure per-modality leakage. A gain from visual steering measures how much the auditor's text bias hid.

The memorization estimate needs care. The twin's sensitive edges are twin edges. A memorizing attacker given the twin graph will still rank original-only edges highly. We therefore report the score margin between original-only and twin-only candidate pairs. Graph neural network attackers trained from scratch serve as a control where this margin should be zero.

Content-plausible anonymization. We extend Humbert-style plausible sampling so that decoy edges are drawn from the joint distribution of structural and content similarity. Deletions of sensitive edges are paired with decoys among content-similar non-linked pairs, which makes content locally uninformative about which candidate pair is real.

Baselines

The naive reference point is releasing the graph with sensitive edges simply deleted and no other changes. This measures raw recoverability. On Amazon-Sports we expect content-only attackers to recover a large fraction of deleted edges, given MM-GRAPH's reported MRR jump from about 11.1 to about 30.45 when images are added.

The classical anonymizers are k-degree anonymity and SalaDP, each with and without Humbert's plausible edge generation. Humbert et al. report that the structural recovery attack exceeds AUC 0.95 against the plain versions and that plausible generation lowers it by up to 35% on Facebook. All anonymizers will be run at matched edit budgets.

The strongest competitor is PPGSL, given the same CLIP image and text embeddings as node features, its full retrain-the-attacker protocol, and the same tuning budget as our method. PPGSL reports sensitive-link attack AUC of about 0.50 with about 81% AUC on non-sensitive link prediction on Cora. On multimodal-attributed graphs there is no reported result found on Lacuna for PPGSL or any anonymizer.

Our method counts as beating PPGSL only if it dominates PPGSL's privacy-utility frontier. Concretely, at equal non-sensitive link prediction MRR it must achieve lower best-attacker AUC, where the best attacker is the maximum over our full family, including attackers PPGSL never trained against.

The key ablation is structure-only plausible sampling versus joint structure-and-content sampling at the same budget. It isolates whether content-space plausibility is the ingredient that matters.

For auditor baselines, a CLIP-feature GraphSAGE link predictor is the reference attacker. MM-GRAPH found this simple model beats specialized multimodal graph networks. The multimodal language model auditor must be compared against it on twins, where memorization cannot help.

Why not just…?

Why not just plug multimodal embeddings into PPGSL and call it solved? This is the real threat. PPGSL already optimizes against an attacker that uses node features. If its retrained attacker with CLIP features captures content leakage, our joint plausible sampler adds little. The baseline comparison settles this directly. Two outcomes remain informative even if PPGSL wins. One is whether its graph stays robust against content-only and language-model attackers it was not trained against. The other is whether its continuous edits produce implausible edges that a content-space plausibility detector flags. If PPGSL wins on both counts, the anonymization contribution reduces to the audit itself, and we will report it that way.

Why not just apply edge differential privacy and noise the embeddings? Humbert et al. show that differentially private edge addition, as in SalaDP, creates fake edges detectable at AUC above 0.95. Yuan et al. note that standard graph differential privacy destroys the clustering that downstream tasks need. Noising image and text embeddings independently should also break the cross-modal alignment that MM-GRAPH shows is responsible for most of the utility. We include an edge-plus-embedding noise baseline to measure this frontier rather than assume it.

Why not just use synthetic graphs to avoid contamination? Fully synthetic graphs drop the real relationship between content and edges, and that relationship is exactly the leakage under study. Twins keep the real images and text and resample only the edges. The twin plausibility check verifies that they are not trivially detectable.

Why not just caption the images and use a text-only attacker? MM-GRAPH documents a semantic gap: visual features add at least 6% over text-only models. OpenMAG shows that images drive social-network graphs. The image-blanked and caption-substituted auditor runs measure how much leakage this substitution hides.

Decisive Experiments

The datasets are Amazon-Sports, Amazon-Cloth and Goodreads-LP from MM-GRAPH, and Amazon Grocery, RedditS and Flickr30k from OpenMAG. These span text-dominated and image-dominated domains. They are public proxies for sensitive data, which is a stated limitation. Five checks decide the claims.

First, against Humbert-style anonymized graphs, content-only attackers should reach markedly higher sensitive-link AUC than the structural attack does after its 35% reduction. If they do not, the core claim fails.

Second, the language-model auditor's margin between original-only and twin-only edges should be positive on Amazon and MM-CoDEx-like graphs, and zero for from-scratch graph neural networks.

Third, visual steering should raise auditor AUC on RedditS and Flickr30k but not on Amazon. That pattern would confirm a domain-dependent text-bias blind spot.

Fourth, joint plausible sampling should beat structure-only plausible sampling at equal budget and equal utility, measured by MRR on non-sensitive links.

Fifth, the frontier comparison with PPGSL must hold under the maximum over all attackers.

All results will be reported with five seeds and twin draws per configuration.