Fast In-Spectrum Graph Watermarks
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908477430956032 |
|---|---|
| author | Bourrée, Jade Garcia Kermarrec, Anne-Marie Merrer, Erwan Le Safsafi, Othmane |
| author_facet | Bourrée, Jade Garcia Kermarrec, Anne-Marie Merrer, Erwan Le Safsafi, Othmane |
| contents | We address the problem of watermarking graph objects, which consists in hiding information within them, to prove their origin. The two existing methods to watermark graphs use subgraph matching or graph isomorphism techniques, which are known to be intractable for large graphs. To reduce the operational complexity, we propose FFG, a new graph watermarking scheme adapted from an image watermarking scheme, since graphs and images can be represented as matrices. We analyze and compare FFG, whose novelty lies in embedding the watermark in the Fourier transform of the adjacency matrix of a graph. Our technique enjoys a much lower complexity than that of related works (i.e. in $\mathcal{O}\left(N^2 \log N\right)$), while performing better or at least as well as the two state-of-the-art methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_04182 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast In-Spectrum Graph Watermarks Bourrée, Jade Garcia Kermarrec, Anne-Marie Merrer, Erwan Le Safsafi, Othmane Data Structures and Algorithms We address the problem of watermarking graph objects, which consists in hiding information within them, to prove their origin. The two existing methods to watermark graphs use subgraph matching or graph isomorphism techniques, which are known to be intractable for large graphs. To reduce the operational complexity, we propose FFG, a new graph watermarking scheme adapted from an image watermarking scheme, since graphs and images can be represented as matrices. We analyze and compare FFG, whose novelty lies in embedding the watermark in the Fourier transform of the adjacency matrix of a graph. Our technique enjoys a much lower complexity than that of related works (i.e. in $\mathcal{O}\left(N^2 \log N\right)$), while performing better or at least as well as the two state-of-the-art methods. |
| title | Fast In-Spectrum Graph Watermarks |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.04182 |