Abstract:
Knowledge Graphs (KGs) can be used to store information about software design, biomedical designs, and financial information---all domains where intellectual property and/or specialized knowledge must be kept confidential. Moreover, KGs can also be used to represent the content of technical documents. In order to deter theft of intellectual property via cyber-attacks, we consider the following problem: given a KG K0 (e.g., representing a software or biomedical device design or the content of a technical document), can we automatically generate a set of KGs that are similar enough to K0 (so they are hard to discern as synthetic) but sufficiently different (so as to be wrong)? If this is possible, then we will be one step closer to automatically generating fake KGs that an adversary has difficulty distinguishing from the original. We will also be closer to automatically generating documents corresponding to fake KGs so that an adversary who steals such documents has difficulty distinguishing the real from the fakes. We formally define this problem and prove that it is NP-hard. We show that obvious approaches to solving this problem do not satisfy a novel concept of "adversary-awareness" that we define. We provide a graph-theoretic characterization of the problem and leverage it to devise an "adversary-aware" algorithm. We validate the efficacy of our algorithm on 3 diverse real-world datasets, showing that it achieves high levels of deception.
