Robust Fingerprinting of Graphs With Fing

Graphs have become fundamental for carrying invaluable insights into numerous scientific disciplines. Controlling if they are further shared and modified is essential when sharing such graphs. This control is typically achieved using digital watermarking by embedding identification information in the graph structure. In this paper, we propose the first approach to fingerprinting graphs by associating a characteristic signature of these graphs that can be extracted later as proof of ownership. This work provides the same guarantees as watermarking while avoiding the need to modify the graph, instead by exporting the fingerprint to an external timestamped database. We present the novel fingerprinting scheme Fing. Fing relies on the Factor-r Sum Subsets problem to create a digital fingerprint. This problem is <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N P$</tex>-hard, so it is easy to create and extract for the graph originator while being intractable for an attacker. We provide an analysis of the robustness of FING facing a wide range of attacks that aim at removing or extracting the fingerprint. Finally, we empirically show FING's scalability. A fingerprint can be created in around four minutes on a single core for 10 million node graphs and is robust against attacks removing thousands of edges, for instance.