{"id":"20b4ee28-54a1-4509-ade5-1e6bc0655bfd","arxiv_id":"2502.04182","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"F&F watermarks unweighted graphs by inserting a Gaussian key into Fourier coefficients of the adjacency matrix and binarizing the result, achieving O(N^2 log N) embedding and extraction with robustness to random edge flips.","lead":"This paper adapts a classic image watermarking method to graphs by hiding a secret key in the Fourier transform of a graph's adjacency matrix. The method embeds and extracts watermarks in O(N^2 log N) time, allowing provenance checks on graphs with millions of vertices.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The extraction is coordinate-locked: Algorithm 1 compares Fourier coefficients position-by-position, so a relabeled watermarked graph cannot be recognized; the 'at least as well' robustness claim is untested against relabeling, which isomorphism-based baselines absorb.","rationale":"The reader's weakest assumption identifies the same load-bearing gap: the scheme is anchored to a deterministic vertex-to-matrix mapping, and all correctness and robustness evidence depends on that mapping being preserved. This is the most serious issue because it directly undermines the strongest comparative claim. A relabeling attack is a standard, low-cost way to strip provenance from a graph, and the two comparison methods—Eppstein et al. and Zhao et al.—are built on graph isomorphism or subgraph matching precisely to tolerate such structural ambiguity. F&F has no equivalent mechanism; extraction is a coordinate-wise spectral comparison. The paper's own proof of zero false negatives in the unattacked case relies on A* = A_W, an equality that fails under any nontrivial permutation. The experimental section is careful about edge flips but never tests label permutations, so the claimed parity with label-invariant baselines is not established. Secondary issues, such as the missing symmetrization step and the unsupported 100%-flip claim, are real reproducibility concerns, but they are less fundamental than the labeling assumption because they could in principle be fixed by implementation details. The appropriate verdict remains CONDITIONAL: the complexity result is credible and the engineering idea is interesting, but the robustness and comparison claims need to be scoped to label-preserving settings or extended with an alignment mechanism before the paper's headline claim is accepted.","tokens_in":15223,"tokens_out":8381,"duration_ms":92140,"concrete_test":"Take a graph from Table II (e.g., BA or Pokec) with its reported parameters, embed the watermark, then create 100 copies by applying independent uniformly random permutations to the vertex labels. Run Extract on each relabeled copy using the original key and the θ from Table II. If the success rate drops below 1.0 (or below the edge-flip success rate), F&F is not label-robust; report the success rate and the distribution of s/||W||_2 versus θ. If the scheme is meant only for label-preserving settings, the abstract and threat model must say so before the comparison to isomorphism-based methods.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section III explicitly assumes \"we can label the input graph arbitrarily, so that a deterministic mapping of its vertices in the adjacency matrix can be performed.\" This assumption is load-bearing because Extract computes W* = FT(A − A*) and compares it entrywise to W = FT(A − A_W). The watermarked graph is only a matrix in the owner's fixed labeling. For any suspected graph G* = P A_W P^T with P a nontrivial permutation, A − A* is not a sparse edge-difference in the original coordinates; its Fourier transform is a permuted-spectrum object, and the 2-norm criterion s ≤ θ||W||_2 has no invariance. The only proof of correctness (end of Section IV-B2) uses A* = A_W, which holds only when the graph is returned with unchanged labels. The robustness experiments (Figure 6b, Table II) flip edges only; no run applies a vertex permutation. Since the two baselines are subgraph/isomorphism-based, they are designed to be label-invariant, so the abstract's 'at least as well' comparison is made in a coordinate system that favors F&F. This does not disprove the O(N^2 log N) complexity contribution, but it makes the central performance claim conditional on an unstated, non-adversarial labeling assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes F&F, a graph watermarking scheme that embeds a Gaussian key into selected Fourier coefficients of a graph's adjacency matrix, then binarizes the inverse transform to recover an unweighted graph. Extraction compares the Fourier-domain difference between the original and suspected graph against a threshold. The authors claim an O(N^2 log N) complexity (or O(N0^2 log N0) after dimensionality reduction), and present experiments on synthetic and large real-world graphs to support low distortion, uniqueness, low false positives/negatives, robustness to edge flips, and runtime advantages over the subgraph-based schemes of Zhao et al. and Eppstein et al.","tokens_in":15562,"tokens_out":2617,"duration_ms":29933,"significance":"If the central claims held, the paper would make an important practical contribution: it would reduce graph watermarking from NP-hard subgraph/isomorphism-based methods to fast Fourier operations, and it would scale to graphs with millions of vertices, as demonstrated on several SNAP and Network Repository instances. The paper deserves credit for a simple, reproducible core construction, for benchmarking against the two main baselines on real graphs, and for extending the evaluation beyond edge flips to a GNN-based undetectability test. However, the significance is conditional on the coordinate-locked labeling assumption and on threshold parameters that are fitted to produce the reported behavior; both issues affect the head-to-head comparison and the robustness claims.","major_comments":[{"comment":"Algorithm 1's Embed function binarizes A' but never symmetrizes the result, even though the paper states in Section III that binarization and symmetrization are required to return an undirected graph and Figure 7 depicts a symmetric adjacency matrix. As written, line 11 can produce a directed binary matrix, making the watermarked graph ill-defined and the edit distances reported in Tables I and II inconsistent.","section":"Section III, Algorithm 1"},{"comment":"The binarization threshold uses av(A) = |E|/N^2, but for an undirected graph with zero diagonal the average of the adjacency matrix is 2|E|/N^2. This factor of two propagates into Equation (2), the density-collision discussion, and the claim that densities below 2 are atypical; the quantitative uniqueness conclusions are therefore not supported by the stated formula.","section":"Appendix C, Section IV-C"},{"comment":"Extraction is coordinate-locked: Section III assumes a deterministic vertex labeling, and the proof at the end of Section IV-B2 uses A* = A_W, which holds only when the suspected graph is presented in the same labeling. For a relabeled watermarked graph G* = P A_W P^T, the matrix A - A* is not a sparse edge difference and the norm criterion s <= theta ||W||_2 has no invariance. Since both baselines are subgraph/isomorphism-based and hence label-invariant, the abstract's claim of performing 'at least as well' is tested only in a coordinate system that favors F&F; no experiment applies a vertex permutation.","section":"Section III and Section IV-B2"},{"comment":"The key parameters sigma and theta are chosen by dichotomous search to achieve the target distortion and the target attack resistance (Section IV-C; Figure 5 and Table II). Consequently, the reported robustness is a property of the fitted thresholds rather than an independent prediction of the scheme. The statement in Section IV-B2 that setting theta to tolerate 10% edge flips guarantees no false negatives below 10% flips is an assertion by construction, not a demonstrated property over graph distributions, and the false-positive study in Figure 3 covers only one generator (BA) at one density.","section":"Section IV-C and Section IV-F3"}],"minor_comments":[{"comment":"The definition says ED is the percentage of edges that distinguish two graphs, but the examples and figures use ED as a ratio (e.g., 100% flips, 1000% of flips in Section V-C); please make the percentage-versus-ratio convention consistent throughout.","section":"Section IV-A, Definition of edit distance"},{"comment":"The text states that F&F extraction is 'almost constant after 10k vertices,' but the log-scale plot and the O(N^2 log N) complexity do not support a constant asymptotic claim; please clarify whether this refers to measured wall-clock time on a specific implementation rather than complexity.","section":"Section V-B, Figure 6a"},{"comment":"The adapted Embed complexity is given as O((N + N0^2) log N0), but selecting the top N0 highest-degree vertices from N vertices requires at least O(N log N) or O(N + N0 log N) operations if done by partial sorting; please specify the selection algorithm and its cost.","section":"Appendix D, Table IV"},{"comment":"The row for kron-g500-logn20 lists m = 71128, which appears inconsistent with the other key lengths and with the claim that m follows Eppstein et al.'s density-based guideline; please double-check this value and the associated threshold.","section":"Table II"},{"comment":"The x-axis of Figure 5 is labeled 'ED' in the caption, but the text describes varying the percentage of edge flips for which theta is calibrated; please correct the labeling to avoid confusing edit distance with flip percentage.","section":"Figure 5"}],"recommendation":"major_revision","confidential_remarks":"The paper would be strengthened by either (i) justifying the deterministic-labeling assumption as part of the threat model and explicitly stating that F&F is not label-invariant, or (ii) providing an alignment/registration procedure for relabeled graphs. The current comparison against isomorphism-based baselines is arguably unfair without this. The threshold-fitting issue also deserves a clearer separation between calibration and evaluation. I would not reject the paper, since the complexity contribution and the experimental scope are valuable, but the central robustness and comparison claims need to be re-scoped or re-tested."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a real new application—porting Cox et al.'s spectral image watermarking to unweighted graphs via FFT and binarization—with a genuine complexity win (O(N^2 log N) vs NP-hard subgraph matching). But the paper's headline \"at least as well\" robustness claim doesn't survive contact with relabeling, and the authors tune their thresholds to fit the attacks they report. It's a decent first cut at a niche problem, not a settled result.\n\nWhat's new: no one in the graph watermarking literature embeds in the Fourier domain of the adjacency matrix. The formal uniqueness analysis in Appendix C is a nice addition, and the GNN undetectability attack is a sensible extra goal. The complexity analysis is straightforward and credible.\n\nSoft spots, in order: (1) The load-bearing label assumption. Extraction compares Fourier coefficients position-by-position. A relabeled watermarked graph P A_W P^T will not be recognized; the only proof of correctness assumes A* = A_W, i.e., same labels. Baselines (Zhao, Eppstein) are isomorphism-based and label-invariant, so the benchmark in Fig 6b is tilted. The paper doesn't test vertex permutations. This is not minor; it changes the scope of the \"at least as well\" claim. (2) Algorithm 1 omits symmetrization although the text says it happens. As written, AW is not symmetric. Also av(A) = |E|/N^2 is off by a factor of 2 for undirected graphs (should be 2|E|/N^2), which affects the binarization threshold. (3) Robustness numbers are threshold-fit: theta is set by dichotomous search to resist 10% flips, so the observed success is partly built in. The 100% edge-flip extraction claim is striking but unsupported by analysis or code. No code or data is released, so these numbers are not reproducible.\n\nNone of this kills the complexity contribution, which stands on its own. But the paper overclaims in the abstract. With corrections and code, this would be a credible new application. Who it's for: researchers in graph provenance/watermarking who want an FFT-based alternative to subgraph matching. Deserves a serious referee—the core idea is sound and fixable.","headline":"Porting Cox spectral image watermarking to adjacency matrices is a genuine new idea with real complexity gains, but the robustness claims hinge on an untested label-fixed assumption and fitted thresholds.","tokens_in":16064,"tokens_out":2596,"would_cite":true,"duration_ms":25349,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that graph watermarking can be made practical for very large graphs by embedding a Gaussian key into the Fourier spectrum of the adjacency matrix and binarizing the result, yielding $O(N^2 \\log N)$ time and robustness to…","keywords":["graph watermarking","Fourier transform","adjacency matrix","spread spectrum","provenance","large graphs","edge flip attack","binarization"],"falsifier":"Take a watermarked graph, apply a random permutation to its vertex labels, and run the extraction: if the watermark is unrecoverable after this relabeling while an edge-flip attack of the same magnitude is survived, the scheme's robustness claim fails for relabeling attacks. A second decisive test is to measure the false-positive rate on graphs with density below 2, where the paper itself reports collisions between distinct keys.","tokens_in":15000,"feed_emoji":"🔒","tokens_out":6292,"duration_ms":53947,"temperature":0.7,"pith_summary":"This paper claims that graph watermarking can be made practical for very large graphs by treating the adjacency matrix as an image and embedding the watermark in its Fourier spectrum. The resulting scheme, F&F, runs in $O(N^2 \\log N)$ time for an $N$-vertex graph, far below the NP-complete complexity of the two existing graph-watermarking methods. If the claim holds, owners of million-vertex graphs can embed and verify provenance efficiently, with robustness to random edge flips that matches or exceeds the state of the art.","feed_headline":"Fourier-domain watermarking scales graphs to millions of vertices","feed_subtitle":"F&F embeds a key in a graph's spectrum, beating subgraph-matching schemes on speed and edge-flip resilience.","key_machinery":"The scheme's central object is the discrete Fourier transform of the binary adjacency matrix $A$. A Gaussian key of length $m$ is added to the $m$ smallest-amplitude Fourier coefficients, the inverse transform is applied, and the result is binarized by thresholding at the average value of $A$, producing the watermarked adjacency matrix $A_W$. Because this binarization spreads the key across all coefficients, extraction compares the full spectral difference between the original and suspect matrices rather than only the $m$ modified locations.","core_discovery":"The central claim is that the in-spectrum watermarking technique of Cox et al., originally designed for images, transfers to unweighted undirected graphs once the adjacency matrix is treated as a pixel matrix and the watermarked spectrum is binarized back to $\\{0,1\\}$. The authors prove that an unattacked watermarked graph always passes extraction when the threshold is zero, derive a closed-form probability that two independent keys produce distinct watermarked graphs, and report experimental resilience to edge flips beyond 100% of the edge count on several million-vertex real graphs. In a head-to-head benchmark, F&F matches or beats the subgraph-matching scheme of Zhao et al. and the isomorphism-based scheme of Eppstein et al. in robustness while being fast enough to watermark graphs an order of magnitude or more larger within the same timeout.","pith_inferences":["Because the scheme is not invariant to vertex relabeling, an adversary who permutes labels could strip the watermark; testing this attack would likely expose the main practical gap.","The binarization step limits capacity: key length and $\\sigma$ must be retuned for each graph density, so transferring the scheme to directed, weighted, or extremely sparse graphs is not automatic.","The reported survival of 100% edge flips is surprising and likely reflects the watermark's spread across the whole spectrum; a theoretical account of this robustness would strengthen the claim.","The undetectability result was obtained only on Barabási-Albert graphs, so it remains open whether the watermark is equally invisible in other graph families."],"forward_implications":["Graph owners can embed provenance watermarks into graphs with millions of vertices in minutes rather than running intractable subgraph searches.","The scheme withstands random edge-flip attacks at least up to 100% of the edge count, an intensity the paper argues already destroys the attacked graph's utility.","Extraction time does not grow with the intensity of the attack, so F&F's extraction is effectively constant for large graphs, unlike matching-based methods.","The threshold $\\theta$ can be chosen per graph model and density so that no false positives occur for $\\theta \\leq 5$ on Barabási-Albert graphs."],"supporting_citations":[{"why":"Supplies the original in-spectrum image watermarking scheme that F&F adapts to graphs.","marker":"[4]"},{"why":"One of the two baseline graph-watermarking schemes; its key-length guidance and NP-complete complexity are used as comparison points.","marker":"[13]"},{"why":"The other baseline, based on subgraph matching; F&F is benchmarked against it in runtime and robustness.","marker":"[38]"},{"why":"Source of the large real-world graphs (e.g., Pokec) used in the experiments.","marker":"[24]"},{"why":"Source of additional large real graphs (e.g., Flickr) used in the experiments.","marker":"[32]"}],"fun_headline_variants":["Fourier watermarking: graphs at million-vertex scale","In-spectrum graph watermarking beats subgraph matching","FFG: Fast graph watermarking via Fourier transform","Graph watermarking scales to millions with Fourier keys","Faster graph watermarking through spectral embedding"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The scheme requires that the suspect graph's vertices carry the same fixed labels used at embedding time, so that its adjacency matrix lines up entry-by-entry with the watermarked one; if a graph is relabeled or its vertex order is unknown, the Fourier comparison cannot be aligned and the watermark cannot be found.","fun_headline_variants_meta":{"raw":{"variants":["Fourier watermarking: graphs at million-vertex scale","In-spectrum graph watermarking beats subgraph matching","FFG: Fast graph watermarking via Fourier transform","Graph watermarking scales to millions with Fourier keys","Faster graph watermarking through spectral embedding"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000137,"raw_usage":{"total_tokens":1099,"prompt_tokens":843,"completion_tokens":256,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":459,"completion_tokens_details":{"reasoning_tokens":181}},"tokens_in":459,"tokens_out":256,"duration_ms":2917,"temperature":1.0,"reasoning_tokens":181,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T23:14:04.813325+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a watermarked graph, apply a random permutation to its vertex labels, and run the extraction: if the watermark is unrecoverable after this relabeling while an edge-flip attack of the same magnitude is survived, the scheme's robustness claim fails for relabeling attacks. A second decisive test is to measure the false-positive rate on graphs with density below 2, where the paper itself reports collisions between distinct keys.","supporting_citations":[{"cited_title":"Secure spread spectrum watermarking for multimedia","cited_arxiv_id":null,"evidence_quote":"Supplies the original in-spectrum image watermarking scheme that F&F adapts to graphs."},{"cited_title":"Goodrich, Jenny Lam, Nil Mamano, Michael Mitzenmacher, and Manuel Torres","cited_arxiv_id":null,"evidence_quote":"One of the two baseline graph-watermarking schemes; its key-length guidance and NP-complete complexity are used as comparison points."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The other baseline, based on subgraph matching; F&F is benchmarked against it in runtime and robustness."},{"cited_title":"Rossi and Nesreen K","cited_arxiv_id":null,"evidence_quote":"Source of additional large real graphs (e.g., Flickr) used in the experiments."}],"review_version":1}