Randomized Generation of Adversary-aware Fake Knowledge Graphs to Combat Intellectual Property Theft

Snow Kang, Cristian Molinaro, Andrea Pugliese, V. S. SubrahmanianAAAI 2021 · DOI

Introduction

Intellectual property (IP) theft is a massive economic burden, costing hundreds of billions of dollars annually. As sensitive information—ranging from biomedical designs to financial structures—is increasingly stored in the form of Knowledge Graphs (KGs), these structures have become primary targets for cyber-attacks. Traditional defenses like encryption and access control are reactive; once a breach occurs, the data is compromised.

A more proactive defense involves "poisoning the well" by generating fake versions of the data. If a thief exfiltrates a set of files containing one real KG and several fakes, they face the challenge of identifying the ground truth. However, simple randomization is insufficient against a sophisticated adversary who might know the generation algorithm. This paper, presented at AAAI-21, introduces CLIQUE-FAKEKG, a "security-first" approach designed to generate fake KGs that are mathematically indistinguishable from the original, even under full algorithmic transparency.

The Challenge: Adversary-Awareness

The core difficulty in generating fake data is balancing three often-conflicting requirements:

  1. Believability: The fakes must look like real data to avoid immediate detection.
  2. Incorrectness: The fakes must be different enough from the original to be useless for IP theft.
  3. Adversary-Awareness: The set of KGs must be structurally symmetric such that an attacker cannot use statistical or algorithmic analysis to identify the original.

Without adversary-awareness, a thief could exploit biases in the generation process. For instance, if an algorithm consistently produces fakes with more nodes than the original, the attacker simply identifies the KG with the fewest nodes. CLIQUE-FAKEKG solves this by ensuring that every KG in the output set has the exact same relationship to every other KG.

The CLIQUE-FAKEKG Algorithm

The researchers formalize the generation of adversary-aware fakes as the FAKEKG problem and prove it is NP-hard. To solve it, they employ a graph-theoretic strategy centered on the concept of cliques.

The process begins by constructing a "distance graph." In this meta-graph, each node represents a potential Knowledge Graph. An edge is drawn between two nodes if their structural distance (e.g., Jaccard distance) falls within a specific "Goldilocks" interval $\tau = [\ell, u]$. This interval ensures that fakes are close enough to be believable but far enough to be functionally wrong.

Illustration of a distance graph where nodes represent potential Knowledge Graphs and edges denote distances within a specified range. The algorithm identifies cliques to ensure indistinguishability.

The algorithm then searches for a clique—a subset of nodes where every node is connected to every other node—that includes the original KG. By selecting a subset of this clique uniformly at random, the system guarantees that any node in the final set could have served as the starting point. To an observer, the structural relationships between all KGs in the set are identical, achieving true mathematical indistinguishability.

Experimental Setup

The authors validated CLIQUE-FAKEKG using three diverse real-world datasets:

  • Nation: International relations between countries.
  • UMLS (Unified Medical Language System): Biomedical relations.
  • FB15K-237: General-world knowledge from Freebase.

From these datasets, 22 original KGs were extracted, and 9 fakes were generated for each, resulting in 66 test cases. These were then presented to 10 human experts (Masters/PhDs in Engineering) for evaluation. The experts were tasked with identifying the real KG among the nine fakes using both structural and semantic reasoning.

Key Results

The human evaluation demonstrated the high effectiveness of the CLIQUE-FAKEKG approach. Despite their expertise, the participants struggled significantly to distinguish the real data from the fakes.

Average deception rates across human expert evaluations, showing that fakes were selected as the primary choice in over 85% of tests.

The study revealed a deception rate of 86.8%, meaning that in the vast majority of cases, the KG selected by experts as their top choice was actually a fake. Even when allowed to pick their "Top 3" guesses, the experts failed to include the original KG 62.7% of the time. Overall, the probability of a human correctly identifying the original was only 13.2%, which is only marginally better than a blind random guess (10%).

Conclusion and Future Work

CLIQUE-FAKEKG represents a significant step forward in proactive data defense. By grounding the generation of fake Knowledge Graphs in the mathematical properties of cliques, the authors provide a defense that remains robust even when the adversary has full knowledge of the defensive algorithm.

While highly effective, the authors note that the current pipeline focuses on the graph structure. Future work includes improving the generation of natural-sounding technical documents from these fake graphs and integrating external world knowledge to prevent attackers from debunking fakes through cross-referencing with public data sources.

Summary updated

BibTeX
@inproceedings{kang2021randomized,
  author = {Snow Kang and Cristian Molinaro and Andrea Pugliese and V. S. Subrahmanian},
  title = {{Randomized Generation of Adversary-aware Fake Knowledge Graphs to Combat Intellectual Property Theft}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i5.16538},
}
Figure