Link Inference Attack on Privacy-Preserving Knowledge Graphs

1 Introduction

• Graph owners seek to use knowledge graphs to train accurate machine-learning models without disclosing privacy-sensitive relations.A described protection practice publishes the graph after deleting sensitive edges.Source: §1 · pp. 1–2
• Even after a sensitive relation is deleted, the remaining graph structure can help an adversary recover its hidden links.One scenario uses all triples without semantic knowledge; the other targets links among entities already connected with sensitive relations.Source: §1 · p. 2
• The evaluated attacks produce significant leakage, and highly connected entities are more exposed than others.A structural analysis uses Principal Component Analysis to investigate which topological properties drive attack success.Source: §1 · p. 2
• The paper evaluates two attacks and analyzes structural properties associated with their success.The paper outline places attack description and evaluation in Section 4 and structural analysis in Section 5.Source: §1 · p. 2

2.1 Knowledge Graphs

• A knowledge graph represents directed, relation-labeled connections as triples of head entity, relation, and tail entity.The paper defines a graph as triples drawn from entities and relation types.Source: §2.1 · p. 2

2.2 Knowledge graph structural features

• Structural features include entity degree, counts of incident relation types, and Jaccard similarity between entity neighborhoods.Degree is divided into in-degree, out-degree, and total degree; Jaccard similarity ranges from no shared neighbors to identical neighborhoods.Source: Incident Relation Counts · p. 3, Node Degree · p. 3, Jaccard Similarity · p. 3

2.3 Knowledge Graph Embeddings

• Knowledge graph embeddings learn vector representations, and TransE's relation embeddings cluster semantically similar relations for use in Scenario 2.The embeddings represent entities and relations in R^d.Source: §2.3 · pp. 3–4

3 Related Work

• Prior graph-structure research showed that topology alone can reveal whether edges exist between targeted nodes in anonymized social networks.The passage describes this as a foundational result by Backstrom et al..Source: §3 · p. 4
• Prior knowledge-graph studies examined membership inference against KGE models, while other work targeted federated KGE models.The cited studies are Wang et al. [11] and Hu et al., respectively.Source: §3 · p. 4
• Unlike attacks on trained models, this work uses public graph structure to recover suppressed relations without model access.The paper distinguishes this goal from link prediction, which completes an incomplete graph, and notes that Scenario 2 uses relation-type semantics via KGE embeddings.Source: §3 · pp. 4–5

4.1 Threat Model

• The attacker observes the public graph’s full structure and a partial set of known target-relation triples, and seeks the remaining hidden triples.The two scenarios differ in candidate-space construction while using the same supervised training signal.Source: §4.1 · p. 5

4.2 Attack Description

• The attack learns structural features from known triples to classify candidate pairs, then ranks pairs by their predicted likelihood of being hidden edges.Structural traces include shared neighbors, co-occurrence in related relations, and comparable connectivity patterns.Source: §4.2 · pp. 5–6

4.3 The two attack scenarios

• The naïve scenario considers every entity pair co-occurring in a public-graph triple, creating a large, sparse candidate space for binary classification.On FB15k-237, this space reaches 283,831 pairs for a single relation, many of them trivially unrelated negatives.Source: §4.3 · p. 6, §4.4 · p. 8
• The semantic-aware scenario uses known target triples as seeds, ranks relations by TransE embedding similarity, and filters proxy relations by type overlap and minimum participant counts.The classifier ranks candidate tails for private heads; Hits@1 and MRR are its primary ranking metrics.Source: §4.3 · pp. 6–7

4.4 Experimental study

• AP = 0.949 and ROC-AUC = 0.999 for LightGBM in the naïve setting, while the semantic-aware attack reaches 74.07% Hits@1 on film genres.The naïve result holds with approximately 3% positive pairs.Source: Table 2 · p. 8, §4.4 · p. 8, Scenario 2: Semantic-Aware Attack · p. 8
• For /film/film/genre, candidate expansion raises recovered true head-entity coverage from 70.0% for seeds alone to 99.8%.Table 3 reports head and tail coverage across three target relations.Source: Scenario 2: Semantic-Aware Attack · p. 8, Table 3 · p. 9
• Semantic-aware success varies by relation frequency: Hits@1 is 45.54% for the high-frequency relation and 0% for the low-frequency relation.For the low-frequency relation, the graph contains only 122 triples and there are 3 evaluable private heads; MRR is 0.066.Source: Table 4 · p. 9, Scenario 2: Semantic-Aware Attack · p. 9

5.1 PCA on Structural Features

• Three principal components capture approximately 80% of the variance in the five structural features, indicating correlated information compressed into three latent dimensions.Source: Figure 1 · p. 10, §5.1 · p. 10
• The three structural axes are head–tail connectivity imbalance, overall endpoint connectivity, and neighborhood overlap.PC1 contrasts head and tail connectivity, PC2 captures connectivity of both entities, and PC3 is dominated by Jaccard similarity.Source: §5.1 · pp. 10–11

5.2 Privacy Risk Across Entities

• Mean tail degree measures the average connectivity of a head’s linked tails; Titanic’s mean genre degree is 635, compared with 215 for Double Indemnity.Their linked genres have degrees of 850 and 420 for Titanic, and 120 and 310 for Double Indemnity.Source: §5.2 · p. 11, Figure 2 · p. 11
• 92% Hits@1 and 95% MRR for high-popularity films, versus 43% Hits@1 and 59% MRR for low-popularity films, show attack success rises with genre popularity.The study reports this trend across Hits@1, MRR, and Average Precision; uniform edge removal therefore does not ensure uniform privacy.Source: Table 6 · p. 12, §5.2 · p. 12
• Mean genre degree across films is right-skewed: the mean is 434, median 393, and values range from the 25th percentile of 304 to a maximum of 1326.Most films have low-to-medium genre connectivity, while a minority are linked to very popular genres.Source: §5.2 · p. 12, Figure 3 · p. 12

6 Conclusion & Future Work

• Structural features extracted from the public graph alone are sufficient to infer hidden triples with high accuracy across the two attack scenarios.Source: §6 · pp. 12–13
• Entities connected to popular, high-degree tails are more vulnerable, so uniform edge suppression does not provide uniform privacy guarantees.Source: §6 · p. 13
• The evaluation uses a single dataset; validation on additional Knowledge Graphs, including biomedical or financial graphs, remains future work.Source: §6 · p. 13
• The paper identifies graph perturbation, structural anonymization, and differential privacy as defense directions, while noting that differential privacy for heterogeneous Knowledge Graphs remains open.Because privacy risk is non-uniform, the paper argues that effective defenses must be entity-adaptive rather than uniform.Source: §6 · p. 13

• Precision is the fraction of retrieved positives that are true positives, while recall is the fraction of true positives among true labels.TP, FP, and FN denote true positives, false positives, and false negatives, respectively.Source: A Evaluation Metrics · pp. 14–15
• Average Precision is the area under the precision-recall curve, summarizing performance across classification thresholds.At each threshold, the change in recall weights precision.Source: A Evaluation Metrics · p. 15
• ROC-AUC measures the probability that a randomly chosen positive instance is ranked above a randomly chosen negative one.The score is based on positive and negative instance sets and predicted instance scores.Source: A Evaluation Metrics · p. 15
• Hits@k counts queries with a true-positive candidate in the first k positions, while MRR averages the reciprocal rank of the first true positive.Rank is the position of the first true positive; a higher MRR indicates true positives are consistently ranked near the top.Source: A Evaluation Metrics · p. 15