<figure><img src="image_1.png" /></figure>

HAL
open science

# Robust Fingerprinting of Graphs with FING

Odysseas Drosis, Jade Garcia Bourrée, Anne-Marie Kermarrec, Erwan Le Merrer, Othmane Safsafi

<figure><img src="image_2.png" /></figure>

## To cite this version:

Odysseas Drosis, Jade Garcia Bourrée, Anne-Marie Kermarrec, Erwan Le Merrer, Othmane Safsafi. Robust Fingerprinting of Graphs with FING. SRDS 2025 - Symposium on Reliable Distributed Systems, Sep 2025, Porto, Portugal. pp.1-11. hal-05267625

HAL Id: hal-05267625

https://hal.science/hal-05267625v1

Submitted on 18 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Robust Fingerprinting of Graphs with FING

Odysseas Drosis

EPFL, Switzerland

od84@cornell.edu

Jade Garcia Bourrée

Univ Rennes, Inria, CNRS, IRISA, France

jade.garcia-bourree@inria.fr

Anne-Marie Kermarrec

EPFL, Switzerland

anne-marie.kermarrec@epfl.ch

Erwan Le Merrer

Univ Rennes, Inria, CNRS, IRISA, France

erwan.le-merrer@inria.fr

Othmane Safsafi

EPFL, Switzerland

othmane.safsafi@epfl.ch

*Abstract*—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 NP-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.

*Index Terms*—Graphs, Fingerprinting, Traceability.

# I. INTRODUCTION

Graphs are ubiquitous data structures used across various scientific domains. A graph typically connects nodes (representing any object) with edges to model their pairwise relation. For instance, in K-NN (K-Nearest Neighbors) graph-based recommenders [1], nodes represent users (or items), and edges are weighted to represent the similarity score between them [2]. Such graphs are widely exploited today because they carry valuable and potentially sensitive information, such as friendship relations in a social network [3]. Therefore, it is of the utmost importance to trace the use of such graphs over time. For instance, some graphs might be shared among collaborators of the same company or with a restricted set of academics for evaluation, but should not be exposed to a broader audience. A use case is sharing graphs on public repositories such as SNAP [4] and KONECT [5]. Those initiatives provide numerous graph datasets, ranging from collaboration networks and web networks to peer-to-peer applications. Having a way to prove ownership is a desirable property [6], [7], as exemplified by works distributed freely with the Creative Commons license and leading to prosecution if that license is not respected [8]. However, very little atten-

tion has yet been paid to protecting graphs. Only watermarking has been adapted from different domains of computer science: applications, theory, and signal processing [6], [7], [9]. To provide a way to detect copyright infringements, watermarking schemes embed digital information in the object [7] so the watermarked graph is a modified copy of the original graph.

We argue that fingerprinting is a groundbreaking alternative to watermarking graphs, as fingerprinting does not modify objects to protect them: it is a signature *extraction* process.

In this paper, we present FING, the first approach to graph fingerprinting. Our fingerprinting scheme publishes a signature along with the graph itself to later prove the origin of a graph. The intuition behind our novel scheme is to extract some data structure from the graph and perform operations on it to produce a fingerprint. This fingerprint can be seen as a puzzle that needs to be solved to claim ownership. Solving that puzzle is a NP-hard problem [10] without detaining prior information, which only the originator possesses. The originator then publishes the graph alongside the puzzle created using her fingerprint. Those must be stored in an external, independent, and immutable timestamped (such as a blockchain) to track precedence and avoid the republishing of a similar graph with a different fingerprint.

Finally, this fingerprinting scheme must be robust against attacks on the fingerprinted graph by an attacker willing to remove or extract the fingerprint. Formally, we would like to prove ownership not only on the initial graph but also on a family of graphs whose *edit-distance* is small around the initial graph so that our scheme is robust against modifications of the graph structure.

In this paper, we make the following contributions:

1) We design the first graph fingerprinting scheme, FING, based on the Factor-r Sum Subsets NP-hard problem (Section III).

2) We provide a detailed analysis of the properties of our fingerprinting scheme (Section IV). The analysis proves that FING works as intended and ensures robustness against a wider range of attacks than the watermarking approaches.

3) We evaluate FING on real large graphs and show that the robustness is even better than what the theory suggests (Section V).
<figure><img src="image_4.png" /><figcaption>Fig. 1. A use case for FING: a graph to be protected for ownership is 1) processed to forge a unique fingerprint from some of its nodes. 2) The obtained fingerprint and associated puzzle are sent to a public timestamped database, such as a blockchain (this step is out of the scope of this paper). Finally, 3) Alice, the graph originator, can safely upload it to a public repository for research use and will be able to prove her ownership by solving the puzzle to demonstrate precedence, should a malicious claim happen.</figcaption></figure>

## II. GOALS AND ATTACK MODELS

### A. Problem Statement

Let's consider the following scenario. Alice (coined the graph originator) wants to share a graph $G$ in a public graph repository. This graph can be weighted or unweighted, directed or undirected. She only wants to allow people to use her graph under specific conditions (e.g., she wants them to credit her or use it for research purposes only). Bob, an attacker, downloads and modifies that shared graph $G$ to create a new graph $\tilde{G}$. Bob then uses $\tilde{G}$ non-compliantly. Alice must prove with a high level of confidence to any third party that Bob is using her graph $G$ in a prohibited way. This scenario is addressed by FING, as illustrated in Figure 1.

In this paper, we introduce the first graph fingerprinting approach: FING. FING produces a fingerprint composed of the fingerprint data structure $F_d$ (which is kept secret) and the fingerprint ratio $F_r$ (which is published by Alice in a timestamped database). Suppose a modified version of her graph is used without Alice's consent. She can use FING to claim ownership of this graph by demonstrating that $F_d$ solves the puzzle given by $F_r$ and showing that no other fingerprint from a close graph has been uploaded before hers. FING tackles the challenge of quickly recovering the fingerprint (solving the puzzle) while preventing Bob from doing so.

With fingerprinting, the puzzle is not inserted in the graph structure; instead, the chosen public timestamped database is an authority to assess that Alice uploaded a given graph first, which will preclude later claims.

### B. Desired Properties

The goal with FING is to design a graph fingerprinting scheme that provides the following three properties.

**Fingerprint Robustness:** A fingerprinting scheme must be able to extract a fingerprint in a graph, even if that graph has undergone modifications to prevent the originator from doing so. This is why, for instance, a simple hashing operation on the graph (e.g., with SHA-1) cannot be considered to produce robust graph fingerprints. The threshold on the intensity of tolerated modifications is related to the $d$ edit distance and

to a parameter $\delta$ introduced in the sequel. We call such modifications attacks and describe them in Section II-C.

**Fingerprint Undetectability:** An attacker must not devise an efficient fingerprint extraction method (Section III-A). Extracting a fingerprint from a graph $G(V, E)$ without knowing the data structure $F_d$ takes exponential time with respect to a parameter depending on the graph size.

**Fingerprint Uniqueness:** A fingerprinting scheme should produce fingerprints without collisions. If $\tilde{G}$ is different enough from $G$, it should be highly unlikely to find the fingerprint of $G$ in $\tilde{G}$. The graph difference is typically measured with the graph edit-distance (Definition 1). Thus, Alice wants to claim the fingerprint found in a graph and any variation under a $d$ edit-distance from the originally fingerprinted graph $G$. Yet there is a trade-off on $d$: with a high $d$, Alice can claim ownership of a larger superset of graphs. On the negative side, a high $d$ may allow Bob to create a dummy graph that exhibits the same fingerprint.

A theoretical value for $d$ is given in Theorem 3. An experimental study of the structural characteristics is provided as a function of the edit distance in Section V-B.

### C. Threat Model

We consider that Bob, the attacker, modifies the graph $G(V, E)$ into a new graph $\tilde{G}(\tilde{V}, \tilde{E})$. There is always an attack amplitude after which $\tilde{G}(\tilde{V}, \tilde{E})$ is too different from $G(V, E)$. It is no longer useful to try to extract a fingerprint in $\tilde{G}(\tilde{V}, \tilde{E})$ as the graphs can no longer be considered similar. In this work, we assume that $\tilde{G}(\tilde{V}, \tilde{E})$ is too different from $G(V, E)$ if the attack amplitude is over $d$ edit steps in the graph edit-distance metric which is defined as follows.

**Definition 1.** Let $G_1$ and $G_2$ be two unlabelled graphs. The graph edit-distance between $G_1$ and $G_2$ is:

$$d(G_1, G_2) = \min_{D \in \mathcal{P}(G_1, G_2)} |D|,$$

where $\mathcal{P}(G_1, G_2)$ denotes the set of edit paths transforming $G_1$ into a graph isomorphic to $G_2$. An edit path $D$ is a finite sequence of edit operations that transforms $G_1$ into $G_2$. It corresponds to a node and edge edit operation sequence, including deletions and insertions.

We will show that under suitable conditions, the fingerprinting scheme FING is analytically robust against the three following attacks. Bob multiplies any label $w_i$ by a constant $x_i$ such that $x_i \in [1/\tilde{\delta}, \tilde{\delta}]$, where $\tilde{\delta} \ge 1$ is a constant parameter (noise multiplication attack). Bob can remove a fraction of the nodes or edges of the graph (label removal attack). If this graph is weighted, Bob can multiply or divide a substantial fraction of the labels (scaling attack).

Comparing these attacks to the state-of-the-art works in graph watermarking [6], [9], [7], FING is robust against both label removal attacks and weight modification or any combination of the previous attacks.
### III. FINGERPRINTING GRAPHS WITH FING

#### A. FING in a Nutshell

FING exploits the Factor-r Sum Subsets problem. Given a set of positive numbers S and a rational number r, the puzzle to be solved to extract a fingerprint is to find two disjoint subsets $(S_1, S_2)$ of S such that: $\frac{\sum_{x \in S_1} x}{\sum_{y \in S_2} y} = r$. This problem is known to be NP-complete [11]. Thus, the problem is relaxed by only asking for an approximate solution up to a constant $\delta$. The theoretical analysis in Section IV shows that for a suitable $\delta$, extracting the fingerprint is still too hard to solve, even in the approximate case. The fingerprint is undetectable by construction.

FING proceeds as follows to create a graph fingerprint:

1) It takes a graph as input, be it weighted or unweighted, directed or undirected.

2) It labels the nodes of the graph if they are not labeled.

3) It creates a fingerprint data structure $F_d$: picks randomly two disjoint sets of unique labels denoted by $S_1$ and $S_2$.

4) It publishes the graph alongside the fingerprint ratio $F_r = \frac{\sum_{x \in S_1} x}{\sum_{y \in S_2} y}$, the fingerprint parameter $\delta$ and the edit-distance $d$.

In its simplest form, given a graph $G(V, E)$, FING creates a set $\bar{V}$ from the graph $G(V, E)$, which corresponds to the set S. FING then creates a fingerprint using $\bar{V}$. This fingerprint is composed of a public ratio $F_r$, and a data structure $F_d = (S_1, S_2)$. The sum of the labels in $S_1$ divided by the sum of the labels in $S_2$ gives $F_r$. The graph $G(V, E)$ is then published alongside $F_r$. We expose here the exact problem, but in the sequel, an approximation problem is also presented (using the value $\delta$). Extracting a fingerprint consists of finding two sets of nodes for which the ratio of the sum of the labels is $F_r$. If a modified version of $G(V, E)$ is circulating, it can be claimed by Alice by solving the related Factor-r Sum Subsets problem using her secret fingerprint data structure $F_d$. On the other hand, it takes exponential time in the size of $\bar{V}$ for Bob, who is unaware of $F_d$, to solve this puzzle [11].

Once the graph is published with the puzzle, the only way for Bob to steal the graph is either (i) to solve the NP-hard Factor-r Sum Subsets problem and extract a fingerprint data structure that satisfies the fingerprint ratio $F_r$, or (ii) to attack the graph to prevent Alice from extracting the fingerprint, so that she is unable to solve the puzzle.

The fingerprint extraction algorithm proceeds as follows:

1) Makes sure the given graph is at edit distance smaller than $d$ from the original graph $G(V, E)$.

2) computes the node labels if the graph is not labeled with numerical values.

3) Uses the stored sets $(S_1, S_2)$ as guidance to solve the Factor-r Sum Subsets puzzle.

4) Either solves the Factor-r Sum Subsets problem or fails in doing so (because that graph was not fingerprinted or was attacked over d edit steps).

In the sequel, for the sake of description simplicity, we assume that graphs given as inputs for fingerprint extraction are under d-edit steps.

#### B. Labeling Scheme

FING relies on the set $\bar{V}$ of unique node labels to create graph fingerprints. These labels are created as an initial step. While many labeling schemes have been introduced in the literature (see [12] or [13] for surveys), we use the following approach for its simplicity and its applicability to any graph. Let $\tilde{G}(V, E)$ be an edge-weighted graph with $n$ nodes and $m$ edges, FING constructs $G(V, E)$, a graph with node labels by simply assigning to each node in $\tilde{G}(V, E)$ its out-degree as a label (i.e., the sum of the weights of its outgoing edges). When the edges are unweighted, we assume their weight is 1 and follow the same labeling procedure for weighted graphs. In the case of directed graphs, the labeling scheme considers outgoing edges for its summation. The labeling algorithm does not rely on a fixed root or processing order. The fingerprinting algorithm relies on nodes having unique labels, but the graph itself may contain multiple nodes with the same degree.

The time complexity of the labeling scheme is $O(m + n)$. Moreover, given $\tilde{G}(V, E)$, anyone can reproduce the procedure and obtain $G(V, E)$, as there are no hidden or additional parameters. We assume that the labeled graph $G$ verifies the well-spaced property of parameter $\delta$ as defined below.

**Definition 2.** A graph $G(V, E)$ is said to verify the well-spaced property of parameter $\delta \ge 1$ if for any two labels $(a, b)$ in $V$, either $a = b$ or $a \notin [\frac{b}{\delta}, \delta b]$.

Verifying if a graph $G(V, E)$ has the well-spaced property for $\delta$ can be achieved in $O(n \log(n))$ time. For this, the node labels of $G$ are sorted in an order $n_1 \ge n_2 \ge n_3...$. This takes time $O(n \log(n))$. Then the property is verified for pairs of labels of the form $(n_i, n_{i+1})$. This takes time $O(n)$.

This property is required so that Bob cannot easily find replacements for labels after he removed some by attacking the graph. Section IV-C discusses how to deal with graphs not verifying this property.

#### C. Creating a Graph Fingerprint

The pseudo-code of the fingerprinting creation algorithm is given in Algorithm 1. The algorithm creates a fingerprint data structure from a graph $G(V, E)$ and a number $K$, which controls the expected number of labels used in this fingerprint.

$F_r$ corresponds to the ratio required to extract a fingerprint. When publishing the fingerprinted graph $G(V, E)$, the fingerprint ratio $F_r$ and a number $\delta \ge 1$ are also published. Anyone can extract a fingerprint from $G$ if she can find a couple of subsets $F'_d = (S'_1, S'_2) \in V^2$ such that: $S'_1 \cap S'_2 = \emptyset$, the nodes in $S'_1$ and $S'_2$ have unique labels, and:

$$ \frac{\sum_{x \in S'_1} x}{\sum_{y \in S'_2} y} \in \left[ \frac{F_r}{\delta}, \delta F_r \right]. \qquad (1) $$

Informally, $\delta > 1$ represents how much the fingerprinting scheme is robust against edge weights attacks (scaling or noise multiplication attacks).

Note that the parameter $\delta$ is used both for the well-spaced property and for the desired robustness against attacks on
**Algorithm 1: Fingerprint creation algorithm**

**input** : A graph $G(V, E)$ with a set of labeled nodes $V$, and a positive integer $K$.

**initialization:** $\tilde{V}$ is the list of unique labels in $V$, and $N = |\tilde{V}|$. s.t. $K \le N$.

**output** : A couple $F_d = (S_1, S_2)$ of disjoint subsets of $\tilde{V}$ and a number $F_r$.

$t_1 = 0;$

$t_2 = 0;$

while $t_1 = 0$ or $t_2 = 0$ do

$\tilde{S}_1 = \emptyset;$

$S_1 = \emptyset;$

$\tilde{S}_2 = \emptyset;$

$S_2 = \emptyset;$

for $j = 1$ to $N$ do

Add $\tilde{V}[j]$ to $\tilde{S}_1$ with probability $p = \frac{K}{N}$ independently of everything else;

Add $\tilde{V}[j]$ to $\tilde{S}_2$ with probability $p = \frac{K}{N}$ independently of everything else;

if $\tilde{V}[j] \in \tilde{S}_1$ then

Add $\tilde{V}[j]$ to $S_1$ with probability $1/2$ independently of everything else;

end

if $\tilde{V}[j] \in \tilde{S}_2$ and $\tilde{V}[j] \notin S_1$ then

Add $\tilde{V}[j]$ to $S_2$ with probability $1/2$ independently of everything else;

end

end

$t_1 = \sum_{x \in S_1} x;$

$t_2 = \sum_{x \in S_2} x;$

end

$F_d = (S_1, S_2);$

$F_r = t_1/t_2;$

return $(F_d, F_r)$.

weights. Having all the elements of the set of unique labels have the well-spaced property $\delta$ (Definition 1) means that there is no replacement for each element in this set. This prevents the case where each label had a multiplicity higher than 1, so Bob does not need to find the exact node FING leveraged (as there will be some replacements for it). Increasing $\delta$ makes the graph more robust against attacks that aim at destroying the fingerprint. Still, on the other hand, it reduces the cardinality of the set of unique labels: this is a trade-off that can be seen as an application-dependent hyperparameter. More details about $\delta$ are given in Section IV-E.

### D. Extracting a Fingerprint

The algorithm for extracting a fingerprint is presented in Algorithm 2. First, the graph is labeled with the labeling scheme presented in Section III-B. This labeled graph is denoted $\tilde{G}(\tilde{V}, \tilde{E})$ (which is thus a modified version of the initial labeled graph $G(V, E)$). The fingerprint $(F_d, F_r)$ is known and obtained by using Algorithm 1 on $G(V, E)$. The modification constant $\delta \ge 1$ is public. When possible, the fingerprint extraction algorithm produces $\tilde{F}_d = (\tilde{S}_1, \tilde{S}_2)$, which are two subsets of the set of unique labels in $\tilde{G}$ such that: $\frac{\sum_{x \in \tilde{S}_1} x}{\sum_{y \in \tilde{S}_2} y} \in [\frac{F_r}{\delta}, \delta F_r]$. For now, it is assumed that $G$ verifies the well-spaced property defined in Definition 2.

In Algorithm 2, the set $\alpha \tilde{V}$ is made of the elements of $\tilde{V}$ multiplied by $\alpha$. The Find algorithm 3 is used to find a specific

**Algorithm 2: Fingerprint extraction algorithm**

**input** : The original set of labeled nodes $V$. A set of labeled nodes $\tilde{V}$, $(S_1, S_2)$ which is a couple of lists of unique labels and $\delta = \delta^2 \ge 1$.

**initialization:** $\tilde{V} = (e_1, e_2, ..., e_{\tilde{N}})$ is the list of unique labels in $\tilde{V}$ it is of size $\tilde{N}$. $\tilde{V} = (u_1, u_2, ..., u_N)$ is the list of unique labels in $V$. Both lists are ordered increasingly.

**output** : A couple $\tilde{F}_d$ of subsets of $\tilde{V}$, fails if impossible.

for $i = 0$ to $\tilde{N}$ do

if $i = 0$ then

Take $e_0 = u_1$;

end

$\tilde{S}_1 = \emptyset;$

$\tilde{S}_2 = \emptyset;$

if $e_i \ne 0$ then

$\alpha = u_1/e_i;$

$\mathcal{V} = \alpha * \tilde{V};$

for $j \in S_1$ do

Add the node Find($j, \mathcal{V}, \delta$) to $\tilde{S}_1$;

Exception: Break;

end

if $|\tilde{S}_1| = |S_1|$ then

for $j \in S_2$ do

Add the node Find($j, \mathcal{V}, \delta$) to $\tilde{S}_2$;

Exception: Break;

end

end

if $|\tilde{S}_2| = |S_2|$ then

return $(\tilde{F}_d = (\tilde{S}_1, \tilde{S}_2))$;

end

end

end

return "Fingerprint extraction failure."

label in the modified graph. This algorithm takes as input a label $j$, a set of labeled nodes $S$, and a constant $\delta$, and it returns a node in $S$ which has a label $\tilde{j}$ such that $\tilde{j} \in [\frac{j}{\delta}, \delta j]$. The algorithm deletes this label from $S$. The algorithm returns an exception if such a label does not exist, leading to a fingerprint extraction failure. If labels exist that solve the puzzle, then Algorithm 2 returns them as proof.

**Algorithm 3: Find algorithm**

**input** : A label $j$, a list $S$ of constants, and a constant $\delta \ge 1$.

**output** : A label $\tilde{j}$ in $S$ such that $\tilde{j} \in [\frac{j}{\delta}, \delta j]$ if such an element exists or an error otherwise.

for $k \in S$ do

if $k \in [\frac{j}{\delta}, \delta j]$ then

Remove $k$ from $S$;

return: $k$;

end

end

return "No element found."

## IV. THEORETICAL ANALYSIS

We start by giving sufficient conditions on the parameters of FING to be robust against different types of attacks. This analysis yields theoretical bounds on the graph sizes where FING meets its desired properties.

### A. Resilience Analysis to Considered Attacks

Attacks consist of graph modifications of $G(V, E)$ into a graph $\tilde{G}(\tilde{V}, \tilde{E})$ at most $d$ edit-distance away from $G(V, E)$.
They can have two goals: to either enable Bob to extract a fingerprint from $\tilde{G}(\tilde{V}, \tilde{E})$ (steal the graph) or to prevent Alice from extracting a fingerprint from $\tilde{G}(\tilde{V}, \tilde{E})$ based on her prior knowledge ($F_d$ and $F_r$).

The robustness of FING is analyzed regarding these attacks:

a) **Noise multiplication attack:** The attacker can multiply any unique label by an amount $t \in [1/\tilde{\delta}, \tilde{\delta}]$, with $\tilde{\delta} \ge 1$ being a parameter set in advance.

b) **Label removal attack:** label removal attack on nodes or edges can be generalized through the analysis of the unique labels removal attack. The attacker can remove a number $R$ of unique labels from $G$ to obtain $\tilde{G}$. This can be achieved by removing a fraction of edges or nodes from the graph.

c) **Scaling attack:** the attacker can multiply or divide a very large fraction of the labels of weighted graphs.

These are generalizations of typical attacks, and we will discuss later how they apply to real-world situations.

a) **Analysis of the noise multiplication attack:** This attack aims at preventing the fingerprint extraction by Alice. Bob can also conduct it to steal the graph.

**Theorem 1.** Suppose that the graph $G(V, E)$ was finger-printed by Algorithm 1 and recall the definition of $\delta$ from Equation (1). Bob uses the noise multiplication attack described in IV-A on $G$ to obtain a modified graph $\tilde{G}$. If:

$$ \delta \ge \tilde{\delta}^2, \qquad (2) $$

then Alice can still prove ownership of $\tilde{G}$ with her fingerprint.

The proof is deferred to Appendix B.

This result indicates that FING is robust against the noise multiplication attack until $\delta \ge \tilde{\delta}^2$.

b) **Analysis of the label removal attack:** Since the sizes of the sets, $S_1$ and $S_2$ are generally very small compared to $N$, the condition $S_1 \cap S_2 = \emptyset$ can be omitted. If Bob removes labels without removing any unique label in $S_1$ or $S_2$, Alice can still extract a graph fingerprint. Since the sets $S_1$ and $S_2$ are composed of nodes picked uniformly at random, it is assumed that the labels removed in this attack are also chosen uniformly at random.<fnref n="1" />

To determine the number of removed labels, $R$, we study the probability of removing a label from $S_1$ or $S_2$ when removing a label uniformly from $\tilde{V}$.

**Theorem 2.** Consider a graph $G(V, E)$. With the notations of Algorithm 1, if $R$ unique labels are randomly uniformly removed from $G(V, E)$ such that $RK = o(N)$, then the fingerprint is still present in the graph with probability asymptotically equivalent to $1 - \frac{RK}{N}$.

The proof is deferred to Appendix A.

We now relate the unique label removal and noise multiplication attacks to more practical attacks.

**Edge removal attack:** In FING's labeling scheme, the weights on the edges of $G(V, E)$ are used to create the node labels. This happens in cases where there are no numerical labels already present on $G$'s nodes or when the existing labels do not create a big enough set to apply the fingerprint on. This also depends on the application, as it is directly connected to the complexity needed for an attacker to find the fingerprint in the graph, even with a brute force algorithm. Removing an edge $e$ alters two nodes (the two endpoints of the edge). Hence, removing $R'$ edges can be seen as removing at most $2R'$ unique labels from the set of unique labels $\tilde{V}$. This represents the worst-case scenario; in most cases, $2R'$ is smaller than $R$, either because multiple nodes have the same label (i.e. this label has high multiplicity) or because the $R'$ edges contain self-loops.

**Node removal attack:** Removing a node is equivalent to removing all of its edges. If the node labels were constructed using the edge weights, then removing one node not only deletes its label but also alters the labels of all of its neighbors. Hence, in that case, removing nodes ($v_1, v_2, ..., v_{R'}$) deletes or alters at most $\sum_{k=1}^{R'} (\deg(v_k) + 1)$ unique labels, where $\deg(v_i)$ is the degree of node ($v_i$). Again, in most cases, this alters less unique labels.

c) **Analysis of the scaling attack:** This attack can be seen as a label removal attack through nodes. Indeed, Algorithm 2 rescales all the graph labels to retrieve the original scaling factor used in the scaling attack. It is clear from this algorithm that this operation is equivalent to removing the labels of some of the nodes. These nodes are exactly the ones that were not scaled in the scaling attack. Hence, scaling $|V| - R'$ node labels by the same factor $\alpha$ is equivalent to removing at most $R'$ unique labels from the graph. Consequently, label removal and scaling attacks can be analyzed as unique label removals (Section IV-A).

The robustness of the fingerprinting scheme under structural changes is formally bounded by Theorem 2. Empirically, the method remains effective under significant but random changes. To our knowledge, no prior work has proposed attacks involving extensive or targeted structural modifications, including in the graph watermarking literature.

## B. Complexity analysis: a practical setting

The complexity analysis presented in Appendix C shows that there is a trade-off between the robustness of the unique label removal attack versus the robustness of the noise multiplication attack, using Theorems 1, 2, and Equation (6). For instance, if $N$ is large enough, $K = \log(N)$, $R = \frac{N}{\log(N)^2}$, and $\delta = \sqrt{\frac{N^4}{264}} + 1$, so FING should be robust against an extensive array of attacks.

With this parameter setting, a straightforward analysis indicates that the time complexity for running Algorithm 2 is $O(n + \log(n)^2)$.

## C. Well-spaced Graphs

We now consider the cases where the graph $G(V, E)$ does not verify the well-spaced property of a certain parameter

<footnote n="1">¹At the time of writing this paper, no algorithm exists for finding one element of $S_1 \cup S_2$ more rapidly than finding $(S_1, S_2)$ entirely. This justifies the assumption.</footnote>
<table><caption>**Algorithm 4: Well-spacing algorithm**</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>input</td><td>: A set of labels <span style="text-decoration: overline;">V̄</span>, and a constant δ ≥ 1.</td></tr><tr><td>output</td><td>: A list of unique labels <i>U</i> with the the well-spaced property (Def. 2) with parameter δ.</td></tr><tr><td>initialization:</td><td><i>U'</i> and <i>U</i> are lists of ordered elements of <span style="text-decoration: overline;">V̄</span> from smallest to largest.</td></tr><tr><td>t = <i>U'</i>[0];</td><td></td></tr><tr><td>for <i>k</i> ∈ <i>U'</i> do</td><td></td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;if <i>k</i> ≤ δ<i>t</i> then</td><td></td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Delete <i>k</i> from <i>U</i>;</td><td></td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;else</td><td></td></tr><tr><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<i>t</i> = <i>k</i>;</td><td></td></tr><tr><td>end</td><td></td></tr><tr><td>return <i>U</i> transformed into a set.</td><td></td></tr></tbody></table>

δ ≥ 1 as defined in Definition 2. This means that there exist two labels (a, b) such that $a \in [\frac{b}{\delta}, \delta b]$. In that case, by Equation (2), the noise multiplication attack leads to a modified graph $\tilde{G}(\tilde{V}, \tilde{E})$ in which the labels a and b are transformed respectively to two labels $\tilde{a}$ and $\tilde{b}$ such that $\tilde{a} \in [\frac{\tilde{b}}{\delta}, \tilde{\delta}b]$. This is problematic as Algorithm 3 might end up choosing $\tilde{b}$ as corresponding to a instead of taking $\tilde{a}$. To deal with this issue, Alice must first create a subset of the nodes of G, which verifies the well-spaced property, and then build the fingerprint from this subset with Algorithm 4.

To fingerprint any graph G, Algorithm 4 is applied to the labels of G to obtain a set of unique labels U. This takes time $O(n \log(n))$. Then the set V is replaced by U in Algorithm 1 to create the fingerprint. The fingerprint extraction process remains unchanged (Algorithm 2), and the theoretical analysis holds.

### D. Setting the Tolerated Edit-distance

We now question whether the maximum value of d should be tolerated. On the one hand, making d too small allows an attacker just to modify a bit G and make it unclaimable. On the other hand, making d too large means that the problem of using dummy graphs to claim ownership for a target graph is still present. One way of setting d is to make it large to the point where the owner is still robust against attacks, but still relatively small compared to the edit distance of the graph G from the empty graph. Recall the definition of R from Subsection IV-A. Each edit operation removes at most 2 unique labels. Hence, taking $d = 2R$ is good enough. However, d should be slightly larger, for instance, $3R$, since the computed edit distances are only approximated. Using the values given at the end of Section IV-B leads to the following theorem.

**Theorem 3.** Suppose that the graph $G(V, E)$ was finger-printed (Algorithm 1) by Alice with $K = \log(N)$ and $\delta = \sqrt{\frac{N^4}{2\delta^4} + 1}$, Then with

$$d = \frac{3N}{\log(N)^2}, \qquad (3)$$

any graph $\tilde{G}(\tilde{V}, \tilde{E})$ obtained resulting from label removal attacks, scaling attacks, or noise multiplication attacks is at most at $d$ edit-distance from $G(V, E)$

### E. Multiplicity and Benefit of δ

As a last contribution to the analysis, we discuss some additional benefits of FING. These benefits partially explain why experimental results are better than what is expected theoretically.

**Label multiplicity:** In the theoretical discussion, we considered the attack where unique labels are removed and linked this attack to edge or node removal attacks. We now consider the impact of label multiplicity. A label $l$ has multiplicity $M$ in a graph $G$ if there are exactly $M$ nodes in $G$ with the label $l$.

For Bob to remove a unique label, he must delete all occurrences of that label in the graph. If the multiplicity $M$ of the graph (for that label) is large enough, this might mean significantly altering the graph's structure to the point where it is no longer considered relevant.

**Definition 3.** Let $G(V, E)$ be a labeled graph. For an integer $M \ge 1$, the M-multiplicity set of $G$ is the subset of $V$, that contains only nodes of multiplicity $M$ or greater. It is denoted by $V_M(G)$ or simply $V_M$ if the context is clear. The multiplicity of $G$ is the largest $M$ such that $V_M(G) = V$.

If a graph has multiplicity $M$, then it might take up to $M$ edge removals to remove a single unique label. If the multiplicity of $G(V, E)$ is 1, but the graph is large enough, Algorithm 1 can be modified to extract a fingerprint on $V_M$ for some large $M$. Thus, FING is much more robust against label removal attacks at the cost of some added complexity.

**Side effects of having $\delta > 1$:** Another positive effect is related to setting $\delta > 1$. Suppose that the graph $G$ does not verify the well-spaced property. In that case, Algorithm 4 is used before Algorithm 1 to fingerprint $G$. Recall that $F_d = (S_1, S_2)$ is a couple of sets that constitute FING's fingerprint data structure, and suppose that Bob removed $a \in S_1$ in his attack. Looking at the theoretical study, the fingerprint should not be retrieved in the attacked graph $\tilde{G}$. But since $G$ did not verify the well-spaced property, and since $\delta > 1$ it might be able to find $a' \in \tilde{G}$ such that: $a' \in [\frac{a}{\delta}, \tilde{\delta}a]$, $a'$ becomes a suitable replacement for $a$, and in that case, Alice can still prove ownership of $\tilde{G}$, albeit not with the original set of nodes from $G$. This shows that not verifying the well-spaced property has an advantage. Each time Bob deletes a label $a$, he must modify or delete all the labels $a'$ that are in the vicinity of $a$, i.e., in $a'$. This means further modifying and degrading the graph.

## V. EXPERIMENTAL STUDY

### A. FING's Scalability

To assess FING's scalability, we generate Barabási–Albert random graphs, widely used to model real graphs such as web graphs [14]. Graphs are generated with fixed parameters: each node connects to 3 existing nodes in the Barabási–Albert
<figure><img src="image_5.png" /><figcaption>Fig. 2. Scaling of the FING timings (in seconds) on Barabási–Albert random graphs (sizes $10^2$ to $10^7$).</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 3. Amount of false positives fingerprint extractions (x-axis), for various amounts of unique label averages (y-axis) extracted from generated Barabási–Albert random graphs.</figcaption></figure>

generative process. Concurrently, the number of nodes fluctuates between $10^2$ and $10^7$. Note that our implementation is not performance-oriented (in Python 3.8, using the NetworkX 2.5 library to generate and manipulate graphs) and runs on a single Intel Xeon Gold 6136 core at 3.00GHz. Three independent runs per point are considered for plotting the standard deviation.

Figure 2 shows a linear scaling of both the fingerprint creation and fingerprinting extraction regarding *n* on the x-axis (note the log scales on both axes). The graph is loaded in memory before performing both operations. Timings on the y-axis, for instance, depict a relatively modest 264-second fingerprinting time for the $10^7$ node graph, while the fingerprint extraction is more than 1000× faster (around 0.08 seconds). This highlights the practicality of our approach, as the extraction process remains extremely fast even for large-scale graphs, making it suitable for real-time or resource-constrained applications.

## B. Uniqueness of the Fingerprint

This aspect is as critical as it is difficult to assess. We design an experiment in which a fingerprint is extracted from a generated graph; we then check whether that particular fingerprint also appears in other graphs created from the same generative process. This constitutes arguably a hard case for a fingerprinting scheme, as graphs are, by definition, close, as linked by the same generative method and parameters.

As previously, we conduct experiments on Barabási–Albert random graphs. The experiment is performed as follows: one graph is generated ($n = 10^4$, $m \approx 30,000$), from which the fingerprint is extracted with Algorithm 2. 100 other graphs with the same generative process and parameters are created, on which the fingerprint extraction is performed. The amount of unique labels the graphs have is controlled by randomly assigning edge weights among a set of integer values in either [0, 2], [0, 999] or [0, 9999] (these three sets lead to amounts of unique labels of around 86, 4, 351 and 9, 872 respectively). The whole process is run 30 times; results are depicted in Figure 3. The figure plots the false positive rate, corresponding to the number of times the fingerprint is found in other generated graphs. These graphs are small compared to modern

graphs, so to be protected, we expect real-life scenarios to showcase even larger sets of label diversities.

We observe that false positives exist for graphs generated with a low amount of unique labels (164 and 100 false positives for 86 and 4, 351 unique labels, respectively). Zero false positives were found in the graph containing 9, 872 labels. This stresses the importance of the number of unique labels for FING: the larger their quantity, the larger the probability of fingerprint uniqueness.

## C. Fingerprintable Graphs

At the core of FING is the ability of Algorithm 1 to choose a large set of unique labels to obtain the NP-hardness characteristic that will prevent attackers from extracting a fingerprint. We consider four real graphs that have discriminant characteristics. The Bitcoin graph corresponds to a who-trusts-whom network of crypto asset users who trade using Bitcoin on a Bitcoin OTC platform; edge weights represent ratings in [−10, 10] (the graph is thus weighted with signed integers and directed). An approximated K-NN graph has been computed using a state-of-the-art approach [15] on the notorious Movielens 10M dataset [16] containing ratings for movies; each node is a user, and its outgoing edges are the 20 closest other users according to a *k*-nearest neighbors similarity approach (it is weighted with floats and directed). The Wikipedia clickstream FR graph [17] represents Wikipedia pages in French, where each edge weight corresponds to how often people navigate from one page to another (it is thus weighted with integers and directed). Finally, the YouTube graph represents users who declared friendships; it is unweighted and undirected.

Table I presents the number of labels of these four graphs. We obtain many unique labels when the considered graph edges have a large set of different values. In an extreme case, for instance, weights consisting of float values that are close to unique, we are in the situation observed for the K-NN graph: the amount of unique labels, 69, 769, is close to the total number of graph nodes (69, 792). This is an ideal case for FING, as the fingerprint can be built from an extensive set of labels. To a lesser extent, the clickstream graph also provides a large number of unique labels (16, 547). In that graph, the
<table><caption>TABLE I
AMOUNT OF UNIQUE LABELS IN 4 GRAPHS. GREYED ROWS ARE NOT SUITABLE FOR FING DUE TO LOW LABEL COUNTS.</caption><thead><tr><th>Graph</th><th>Characteristics</th><th># unique labels</th></tr></thead><tbody><tr><td>bitcoinotc [18]</td><td>dir., weight., sign.<br>n = 69, 792</td><td>268</td></tr><tr><td>Movielens 10M K-NN [15]</td><td>dir., weight.<br>n = 1, 039, 606</td><td>69, 769</td></tr><tr><td>Wikip. clickstream FR [17]</td><td>direct., weight.<br>n = 1, 134, 890</td><td>16, 547</td></tr><tr><td>YouTube [19]</td><td>undir., unweight.</td><td>978</td></tr></tbody></table>

<figure><img src="image_7.png" /><figcaption>Fig. 4. Success rate (y-axis) as a function of an attack on weights for the K-NN graph (20 runs average). Weights are multiplied by a perturbation (x-axis) following two probability distributions.</figcaption></figure>

fact that weights are integers is balanced by the large number of edges (around $2M$), which causes enough label diversity.

At the other end of the spectrum, when we consider non-weighted graphs, FING's labeling scheme sets a weight of 1 on every edge, limiting the diversity in labels, even if the number of edges is generally very large. This is what we observe with the YouTube graph, which exhibits only 978 unique labels despite having close to three million edges.

The Bitcoinotc graph, despite being signed and weighted, has a low number of labels (268): this is due to the low range of possible values for weights, integers from -10 to 10. These two last graphs can be directly discarded as unsuitable for FING, solely based on this limited amount of labels.

These observations underscore that FING performs best when edge weights induce a rich label space, making label diversity a key criterion for selecting suitable graphs.

### D. Robustness to Noise Multiplication

Figures 4 and 5 present such an attack for weight perturbation following two statistical distributions: Gaussian and exponential with $\delta = 1.01$ and $K = \log N$. Each point is obtained

<figure><img src="image_8.png" /><figcaption>Fig. 5. Success rate (y-axis) as a function of an attack on weights for the clickstream graph (20 runs average). Weights are multiplied by a perturbation (x-axis) following two probability distributions.</figcaption></figure>

by performing 20 independent runs of the experiment. Every edge weight in the graph is independently multiplied by a random value given by the distribution: the perturbation value $x$ corresponds to the standard deviation $\sigma$ of the Gaussian distribution (the expectation $\mu$ is set to 1). In the case of the exponential distribution, it corresponds to $\beta = x + 1$ with $\beta$ being the distribution expectation (i.e., $\beta = 1/\lambda$).

We observe that the extraction success rate is affected by increasing perturbations, as one would expect. Increased perturbations are preventing Algorithm 2 from retrieving the fingerprint. Yet, the extraction still works more than 50% of the time despite high perturbations. This is due to the relative proximity of weights, which causes replacement weights to satisfy conditions in Algorithm 3 (see Section IV-E).

We stress that with a value of $\delta = 1.01$, a perturbation value of $x = 0.01$ is 100 times higher than the value $\delta$ that we theoretically proved FING to be robust to (see Theorem 1). This is indeed the case in practice.

### E. Robustness to Edge Removal

**A threshold on attacks:** As a preamble, we question the number of edges the attack removes. Since our work aims to extract a graph fingerprint, if a large amount modifies this graph, then the question of whether this attacked graph maintains the characteristics of the original one is central. Alice wants to claim ownership of an attacked graph that is at most $d$ edit-steps away from the original one for a reasonable $d$, otherwise the resulting graph is no longer considered a variant of Alice's graph.

Figure 8 displays a simple function run on the Movielens K-NN graph: the ranking of the top-1000 nodes according to the degree centrality [20]. This function attributes higher values to the most central nodes in the graph due to their degree. The figure plots the changes in this ranking, according to the classic Spearman metric [21]. It measures the correlation between two rankings of the top nodes (on the original graph $G$ and on the attacked version $\tilde{G}$).

We increase the number of edges removed: the correlation drops dramatically to around 30%, even after 2,000 deleted edges (over a total of 2,090,726 possible). After 10,000 edge removals, the correlation is close to zero, meaning that the ranking of the top nodes in the attacked graph has no relation to the node ranking in the original one. An edit distance of $d = 1,000$ edges is a proper setting in this precise scenario. This value is significantly less than the bound given by Theorem 3, which will enforce realistic use cases.

**The random edge removal attack:** In Figures 6 and 7, we now plot this random edge removal attack, with the success rate presented on the y-axis over 30 fingerprint extraction attempts. Despite the discussion on a $d$ set to $10^3$, we push the attack up to $10^4$ to observe an extreme setting.

The considered parameters are $\delta$ and $K \in [3, \log n, 50]$. We first observe that for $\delta = 1$ and both graphs, the value of $K$ is decisive: the larger $K$'s value, the more sensitive to the attack. Small values of $K$ make it robust. Effectively, the larger $K$, the higher the probability that an edge removal affects the
<figure><img src="image_9.png" /><figcaption>Fig. 6. Edge removal attack (K-NN graph) with various values of $\delta$. Success rate (y-axis) for 10 runs as a function of the number of edges removed (x-axis).</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 7. Edge removal attack (Wikipedia graph) with various values of $\delta$. Success rate (y-axis) for 10 runs, as a function of edges removed (x-axis).</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Fig. 8. The effect of an edge removal attack on the Movielens 10M K-NN graph, regarding the degree centrality of the top-1000 most central nodes. The number of edges removed appears on the x-axis, while the Spearman correlation of the top-1000 ranking appears on the y-axis.</figcaption></figure>

summation building node labels for at least one node involved in $K$. For instance, we observe a high success rate for the K-NN graph when $K = 3$, while it drops to 0 very quickly when $K = 50$.

We now study the sensitivity to $\delta$. While introduced initially for sustaining the scaling attack (see Section II), allowing its use in the general case yields crucial performance gains when tackling the edge removal attack. With three values of $\delta \in [1 + 10^{-5}, 1 + 10^{-4}, 1 + 10^{-3}]$ in Figure 6, we observe a slight improvement with $10^{-5}$, to more successful fingerprint extractions for the three values of $K$ when $\delta = 1 + 10^{-3}$. Observations are the same for the clickstream graph in Figure 7 with $\delta \in [1 + 10^{-4}, 1 + 10^{-3}, 1 + 10^{-2}]$. We note that the scaling of $\delta$ is to be chosen depending on the scale of the weights carried by the graph edges, i.e., $\delta$ is chosen small when there are large weights on edges, and conversely.

We conclude that for a tolerance set to $d = 10^3$, the robustness of FING is effectively very high.

## VI. RELATED WORK

a) Graph summarization and fingerprinting relational databases: The domain of graph summarization [22] aims at reducing the input graph size so that an analysis can be performed efficiently on the summarized graph structure. Such techniques produce representative graphs with sizes in the

order of the original ones, which differs from the objective of producing a small fingerprint.

A similar approach is taken in relational databases, where fingerprinting techniques have been widely used to minimize the time and memory needed to store information in a database [23]. Fingerprinting has also been used in databases for security [24] for identifying nonlegitimate accesses: here, users are fingerprinted for tracking leaks, not the data per se.

b) The use of hash functions: On the contrary, a naïve approach could be to use hash functions [25] to produce a fingerprint from a graph. A classic algorithm, such as SHA-1, can take as input a representation of the graph and output a short string representation. Yet, by definition, a single modification to the graph (node/edge addition/deletion) will modify the hash [26] and prevent further identification. This constitutes the worst-case scenario for robustness and thus motivates robust fingerprinting methods [26].

c) Watermarking: Watermarking was introduced in the signal processing domain [27], [28] and is now a well-established field [29]. As with other digital objects, graphs have also been considered in three research works on watermarking. Eppstein et al. [7] propose some formal guarantees on two graph models: Erdos-Renyi and power law graphs. They aim at embedding a mark by flipping edges from some sets of nodes in the high-degree and medium-degree nodes. Zhao et al. [6] use a computational puzzle to prevent attackers from finding the mark: they rely on subgraph isomorphism, a well-known NP-complete problem. For doing so, a subgraph of the key size to embed is selected in the graph; an XOR operation is then performed between the key and the subgraph, modifying edges in the graph. More generally, we see that the complexity required to solve NP-hard problems is core to applications in the field of security [30]. The third work [9] is converting graphs in the spectral domain to use techniques from signal processing to mark them. FING complements this ongoing research yet does not alter the graph structure it aims to protect. The paper addresses a different problem from prior work. Existing techniques focus on related but distinct objectives. Consequently, direct experimental comparisons are not applicable.
VII. CONCLUSION

FING is the first approach to the robust fingerprinting of graphs. It is a signature extraction process based on the resolution of a NP-hard puzzle (the Factor-r Sum Subsets problem) to prove the origin of graphs. Unlike prior graph watermarking, it does not rely on modifying the original graph. FING is simple, scalable, and highly robust against various attacks, with strong empirical support from extensive experiments on synthetic and real-world graphs.

This work significantly advances the state of the art by demonstrating that robustness in graph fingerprinting can be achieved through hard combinatorial problems rather than structural alterations. While FING performs well under diverse scenarios, its effectiveness depends on sufficient label diversity in the graph — a limitation that restricts applicability to certain graph types. Future work could explore hybrid approaches that extend robustness to low-diversity graphs or further generalize the use of hardness-based methods.

APPENDIX

A. *Proof of Theorem 2*

*Proof.* Let $x$ be a random element of $\bar{V}$. $x$ is in $S_1$ if it has been chosen to be in $\bar{S}_1$ in the first step of Algorithm 1. It happens with probability $K/N$ according to Algorithm 1. Then, conditionally on that, $x$ should have stayed in $S_1$ in the second step of our algorithm, this happens with probability $1/2$. We thus get: $\mathbb{P}(x \notin (S_1 \cup S_2)) = (1 - \frac{K}{2N})^2$.

If we draw $(x_1, ..., x_R)$ elements from $\bar{V}$ without replace-
ment the probability that none of them is in $S_1 \cup S_2$ is:
$\mathbb{P}(\forall i \in \{1, ..., R\} \ x_i \notin (S_1 \cup S_2)) = (1 - \frac{K}{2N})^{2R}$.

If RK is order N then this expression will be asymp-
totically strictly smaller than 1. In that case, the first attack
will successfully remove elements from S₁ ∪ S₂ with positive
probability. If RK = o(N) then: P(∀i ∈ {1, ..., k} xᵢ ∉
(S₁ ∪ S₂)) ~ 1 - RK/N. □

B. *Proof of Theorem 1*

*Proof.* Suppose that Bob modifies $G(V, E)$ using this attack and obtains a new graph $\tilde{G}(\tilde{V}, \tilde{E})$. Then the two sets $(S_1, S_2)$ in $G(V, E)$ will be transformed into two new sets $(\tilde{S}_1, \tilde{S}_2)$ in $\tilde{G}(\tilde{V}, \tilde{E})$. We have, by definition of the attack, for $i \in \{1, 2\}$: $\sum_{x \in \tilde{S}_i} x \in [\frac{\sum_{x \in S_i} x}{\delta}, \delta(\sum_{x \in S_i} x)]$. Hence: $\frac{\sum_{x \in \tilde{S}_1} x}{\sum_{y \in \tilde{S}_2} y} \in [\frac{F_r}{\delta^2}, \delta^2 F_r]$.

This computation shows that there is a direct relation
between $\delta$ and $\tilde{\delta}$.

C. *Detailed Complexity Analysis*

We only do the analysis for $\delta > 1$, as the problem is
known to be NP-hard for $\delta = 1$ (Theorem 6 in [11]).

Theoretical robustness of FING: Recall the definition of the sets (S̄₁, S̄₂) from Algorithm 1. First, suppose that Bob knows (S̄₁, S̄₂). Then he will still have to find the sets S₁ and S₂ such that $\frac{\sum_{x \in S_1} x}{\sum_{y \in S_2} y} \in [\frac{F_r}{\delta}, \delta F_r]$. The state-of-the-art algorithm for solving such a problem (presented in [31]) does so in $K^4/(\delta - 1)$ steps in the special case when $F_r = 1$. It is sufficient to have:

$$
\frac{K^4}{(\delta - 1)} \geq 2^{64}, \qquad (4)
$$

in order for our algorithm to be considered hard to solve<fnref n="2" />.
Using this equation, one can choose the values of $K = o(N)$
and $\delta \ge 1$. Then we obtain the $\tilde{\delta} = \sqrt{\delta}$ modification up to
which FING is robust and the number $R$ of edge removals
FING can withstand by using Theorems 2 and 1.

This first analysis uses two major simplifications, the first
one is that we omit the possibility of Bob using the noise
multiplication attack in order to make solving the problem a
little easier for him.

We prove that if we allow the *noise multiplication attack*
then the complexity condition in Equation (4) becomes:

$$
\frac{K^4}{(\tilde{\delta}^2 \delta - 1)} \geq 2^{64}. \qquad (5)
$$

The second simplification is: Bob has no way of knowing
($\tilde{S}_1, \tilde{S}_2$). If he uses a brute force algorithm where he tries all
possible combinations of sets ($\tilde{S}_1, \tilde{S}_2$), then the complexity
will become $\frac{((K^N)^2 K^4)}{((\tilde{\delta}\delta)^2 - 1)}$. Since we have $K = o(N)$ in general,
this quantity is larger than the complexity of the state-of-the-
art algorithm in (5).

Hence, the best Bob can do is use the state-of-the-art
algorithm of [31] on the $N$ unique labels. This, and the fact
that $\tilde{\delta}^2 = \delta$, yields the following complexity

$$
\frac{N^4}{(\delta^2 - 1)}. \qquad (6)
$$

REFERENCES

[1] Y. Park, S. Park, W. Jung, and S.-g. Lee, "Reversed cf: A fast col-
laborative filtering algorithm using a k-nearest neighbor graph," *Expert
Systems with Applications*, vol. 42, no. 8, pp. 4022–4028, 2015.

[2] B. Pfitzmann and M. Waidner, “Anonymous fingerprinting,” in *EUROCRYPT*, 1997.

[3] A.-L. Barabási, H. Jeong, Z. Néda, E. Ravasz, A. Schubert, and T. Vicsek, “Evolution of the social network of scientific collaborations,” *Physica A: Statistical mechanics and its applications*, vol. 311, no. 3-4, pp. 590–614, 2002.

[4] J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/data, Jun. 2014.

[5] J. Kunegis, “The konect project,” http://konect.cc/.

[6] X. Zhao, Q. Liu, H. Zheng, and B. Y. Zhao, “Towards graph water-
marks,” in *COSN*, 2015.

[7] D. Eppstein, M. T. Goodrich, J. Lam, N. Mamano, M. Mitzenmacher, and M. Torres, “Models and algorithms for graph watermarking,” in *Information Security*, M. Bishop and A. C. A. Nascimento, Eds., 2016.

[8] V. Legal, “Is violation of creative commons license a breach of contract or copyright infringement?” https://www.vondranlegal.com/is-violation-of-creative-commons-license-a-breach-of-contract-or-copyright-infringement.

<footnote n="2">²For this threshold, we refer to the domain of cryptography and to what is assumed to be computationally hard in practice: authors proposed in [32] a brute force attack of 2⁶³.¹ calls to the SHA-1 function that found a collision and took 6,500 CPU years and 100 GPU years.</footnote>
[9] H. Al-Khafaji and C. Abhayaratne, "Graph spectral domain blind watermarking," in *ICASSP*, 2019.

[10] M. R. Garey and D. S. Johnson, *Computers and Intractability: A Guide to the Theory of NP-Completeness*. USA: W. H. Freeman & Co., 1979.

[11] M. Cieliebak, S. J. Eidenbenz, A. Pagourtzis, and K. Schlude, "On the complexity of variations of equal sum subsets." *Nord. J. Comput.*, vol. 14, no. 3, pp. 151-172, 2008.

[12] D. Gonçalves, "On the l(p,1)-labelling of graphs," vol. 308, no. 8, 2008.

[13] J. Gallian, "A dynamic survey of graph labeling," *Electron J Combin DS6*, vol. 19, 11 2000.

[14] A.-L. Barabási, R. Albert, and H. Jeong, "Scale-free characteristics of random networks: the topology of the world-wide web," *Physica A: Statistical Mechanics and its Applications*, vol. 281, pp. 69-77, 2000.

[15] G. Giakkoupis, A.-M. Kermarrec, O. Ruas, and F. Taïani, "Cluster-and-conquer: When randomness meets graph locality," in *ICDE*, 2021.

[16] F. M. Harper and J. A. Konstan, "The movielens datasets: History and context," *ACM Trans. Interact. Intell. Syst.*, vol. 5, no. 4, Dec. 2015.

[17] D. T. Ellery Wulczyn, "Wikipedia clickstream, the clickstream-frwiki-2020-08 file," https://meta.wikimedia.org/wiki/Research:WikipediaClickstream.

[18] S. Kumar, F. Spezzano, V. Subrahmanian, and C. Faloutsos, "Edge weight prediction in weighted signed networks," in *ICDM*, 2016.

[19] J. Yang and J. Leskovec, "Defining and evaluating network communities based on ground-truth," *Knowl. Inf. Syst.*, vol. 42, p. 181-213, 2015.

[20] K. Das, S. Samanta, and M. Pal, "Study on centrality measures in social networks: a survey," *Social network analysis and mining*, vol. 8, no. 1, pp. 1-11, 2018.

[21] P. Diaconis and R. L. Graham, "Spearman's footrule as a measure of disarray," *Journal of the Royal Statistical Society: Series B (Methodological)*, vol. 39, no. 2, pp. 262-268, 1977.

[22] Y. Liu, T. Safavi, A. Dighe, and D. Koutra, "Graph summarization methods and applications: A survey," *ACM Comput. Surv.*, vol. 51, 2018.

[23] J. Feng and A. Jain, "Filtering large fingerprint database for latent matching," 12 2008, pp. 1-4.

[24] S. Y. Lee, W. L. Low, and P. Y. Wong, "Learning fingerprints for a database intrusion detection system," in *ESORICS*, 2002.

[25] L. Chi and X. Zhu, "Hashing techniques: A survey and taxonomy," *ACM Comput. Surv.*, vol. 50, no. 1, Apr. 2017.

[26] V. Roussev, "Hashing and data fingerprinting in digital forensics," *IEEE Security Privacy*, vol. 7, no. 2, pp. 49-55, 2009.

[27] R. B. Wolfgang and E. J. Delp, "A watermark for digital images," in *ICIP*, 1996.

[28] I. J. Cox, J. Kilian, F. T. Leighton, and T. Shamoon, "Secure spread spectrum watermarking for multimedia," *IEEE Transactions on Image Processing*, vol. 6, pp. 1673-1687, 1997.

[29] V. M. Potdar, S. Han, and E. Chang, "A survey of digital image watermarking techniques," in *INDIN*, 2005.

[30] L. Evain, "Knapsack cryptosystems built on np-hard instance," *CoRR*, vol. abs/0803.0845, 2008.

[31] N. Melissinos and A. Pagourtzis, "A faster fptas for the subset-sums ratio problem," *Computing and Combinatorics*, p. 602-614, 2018.

[32] M. Stevens, E. Bursztein, P. Karpman, A. Albertini, Y. Markov, and H. Shacham, "The first collision for full sha-1," in *CRYPTO*, 2017.