More Web Proxy on the site http://driver.im/

research-article

Free access

Towards Graph Watermarks

Authors:

Ben Y. ZhaoAuthors Info & Claims

COSN '15: Proceedings of the 2015 ACM on Conference on Online Social Networks

Pages 101 - 112

https://doi.org/10.1145/2817946.2817956

Published: 02 November 2015 Publication History

Abstract

From network topologies to online social networks, many of today's most sensitive datasets are captured in large graphs. A significant challenge facing the data owners is how to share sensitive graphs with collaborators or authorized users, e.g. ISP's network topology graphs with a third party networking equipment vendor. Current tools can provide limited node or edge privacy, but significantly modify the graph reducing its utility.

In this work, we propose a new alternative in the form of graph watermarks. Graph watermarks are small graphs tailor-made for a given graph dataset, a secure graph key, and a secure user key. To share a sensitive graph G with a collaborator C, the owner generates a watermark graph W using G, the graph key, and C's key as input, and embeds W into G to form G'. If G' is leaked by C, its owner can reliably determine if the watermark W generated for C does in fact reside inside G', thereby proving C is responsible for the leak. Graph watermarks serve both as a deterrent against data leakage and a method of recourse after a leak. We provide robust schemes for embedding and extracting watermarks, and use analysis and experiments on large real graphs to show that they are unique and difficult to forge. We study the robustness of graph watermarks against both single and powerful colluding attacker models, then propose and evaluate mechanisms to dramatically improve resilience.

References

[1]

Agrawal, R., and Kiernan, J. Watermarking relational databases. In Proc. of VLDB (2002).

Digital Library

[2]

Albert, R., Jeong, H., and Barabási, A.-L. Internet: Diameter of the world-wide web. Nature 401, 6749 (1999), 130--131.

[3]

Arrington, M. How "dirty" mp3 files are a back door into cloud drm. TechCrunch, April 2010.

[4]

Backstrom, L., Dwork, C., and Kleinberg, J. Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In WWW (2007).

Digital Library

[5]

Bender, W., Gruhl, D., Morimoto, N., and Lu, A. Techniques for data hiding. IBM systems journal (1996), 313--336.

Digital Library

[6]

Cho, E., Myers, S. A., and Leskovec, J. Friendship and mobility: user movement in location-based social networks. In KDD (2011).

Digital Library

[7]

Collberg, C. S., Kobourov, S. G., Carter, E., and Thomborson, C. D. Graph-based approaches to software watermarking. In WG (2003).

[8]

Cook, S. A. The complexity of theorem-proving procedures. In STOC (1971).

Digital Library

[9]

Gilbert, E. N. Random graphs. The Annals of Mathematical Statistics (1959), 1141--1144.

[10]

Hanhijärvi, S., Garriga, G. C., and Puolamäki, K. Randomization techniques for graphs. In SDM (2009).

[11]

Hay, M., Miklau, G., Jensen, D., Towsley, D., and Weis, P. Resisting structural re-identification in anonymized social networks.

[12]

Hay, M., Miklau, G., Jensen, D., Weis, P., and Srivastava, S. Anonymizing social networks. Tech. Rep. 07--19, UMass, 2007.

[13]

Kamran, M., et al. A robust, distortion minimizing technique for watermarking relational databases using once-for-all usability constraints. IEEE TKDE (2012).

Digital Library

[14]

Lee, S.-J., and Jung, S.-H. A survey of watermarking techniques applied to multimedia. In ISIE (2001).

[15]

Leskovec, J., Adamic, L. A., and Huberman, B. A. The dynamics of viral marketing. TWEB (2007).

Digital Library

[16]

Leskovec, J., et al. Statistical properties of community structure in large social and information networks. In WWW (2008).

Digital Library

[17]

Leskovec, J., Huttenlocher, D., and Kleinberg, J. Predicting positive and negative links in online social networks. In WWW (2010).

Digital Library

[18]

Leskovec, J., Kleinberg, J., and Faloutsos, C. Graphs over time: densification laws, shrinking diameters and possible explanations. In KDD (2005).

Digital Library

[19]

Leskovec, J., Kleinberg, J., and Faloutsos, C. Graph evolution: Densification and shrinking diameters. TKDD (2007).

Digital Library

[20]

Leskovec, J., Lang, K. J., Dasgupta, A., and Mahoney, M. W. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics 6, 1 (2009), 29--123.

[21]

Leskovec, J., and Mcauley, J. J. Learning to discover social circles in ego networks. In Advances in neural information processing systems (2012), pp. 539--547.

Digital Library

[22]

Li, Y., Swarup, V., and Jajodia. Fingerprinting relational databases: Schemes and specialties. IEEE TDSC 2, 1 (2005), 34--45.

Digital Library

[23]

Liu, K., and Terzi, E. Towards identity anonymization on graphs. In SIGMOD (2008).

Digital Library

[24]

Macq, B. M., and Quisquater, J.-J. Cryptology for digital tv broadcasting. Proceedings of the IEEE (1995), 944--957.

[25]

Menezes, A. J., Oorschot, P. v., and Vanstone, S. Handbook of Applied Cryptography. CRC Press, Inc., 1996.

Digital Library

[26]

Mislove, A., Marcon, M., Gummadi, K., Druschel, P., and Bhattacharjee, B. Measurement and analysis of online social networks. In IMC (2007).

Digital Library

[27]

Narayanan, A., and Shmatikov, V. De-anonymizing social networks. In Proc. of IEEE S&P (May 2009).

Digital Library

[28]

Narayanan, A., and Shmatikov, V. Link prediction by de-anonymization: How we won the kaggle social network challenge. In IJCNN (2011).

[29]

Ohbuchi, R., Ueda, H., and Shuh, E. Robust watermarking of vector digital maps. In ICME (2002).

[30]

Ohbuchi, R., Ueda, H., and Shuh, E. Watermarking 2d vector maps in the mesh-spectral domain. In Shape Modeling International (2003).

Digital Library

[31]

Qu, G., and Potkonjak, M. Analysis of watermarking techniques for graph coloring problem. In ICCAD (1998).

Digital Library

[32]

Richardson, M., Agrawal, R., and Domingos, P. Trust management for the semantic web. In The Semantic Web-ISWC 2003. Springer, 2003, pp. 351--368.

[33]

Robshaw, M. J. B. MD2, MD4, MD5, SHA and other hash functions. Tech. Rep. TR-101, RSA Laboratories, 1995. v. 4.0.

[34]

Ruanaidh, J. O., Dowling, W., and Boland, F. Phase watermarking of digital images. In ICIP (1996).

[35]

Sala, A., Cao, L., Wilson, C., Zablit, R., Zheng, H., and Zhao, B. Y. Measurement-calibrated graph models for social network experiments. In Proc. of WWW (2010).

Digital Library

[36]

Sala, A., Zhao, X., Wilson, C., Zheng, H., and Zhao, B. Y. Sharing graphs using differentially private graph models. In IMC (2011).

Digital Library

[37]

Steve, W. Information authentication for a slippery new age. Dr. Dobbs Journal (1995), 18--26.

[38]

Takac, L., and Zabovsky, M. Data analysis in public social networks. In International Scientific Conference AND International Workshop Present Day Trends of Innovations (2012).

[39]

Venkatesan, R., Vazirani, V., and Sinha, S. A graph theoretic approach to software watermarking. In Information Hiding (2001).

Digital Library

[40]

Wilson, C., Sala, A., Puttaswamy, K. P. N., and Zhao, B. Y. Beyond social graphs: User interactions in online social networks and their implications. ACM Trans. on the Web 6, 4 (2012).

Digital Library

[41]

Wolfe, G., Wong, J. L., and Potkonjak, M. Watermarking graph partitioning solutions. In DAC (2001).

Digital Library

[42]

Xia, X.-G., Boncelet, C. G., and Arce, G. R. A multiresolution watermark for digital images. In ICIP (1997).

Digital Library

[43]

Yang, J., and Leskovec, J. Defining and evaluating network communities based on ground-truth. In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics (2012), ACM, p. 3.

Digital Library

[44]

Ying, X., and Wu, X. Randomizing social networks: a spectrum preserving approach. In SDM (2008).

[45]

Zhao, X., Liu, Q., Zhou, L., Zheng, H., and Zhao, B. Y. Graph watermarks. Arxiv preprint arXiv:1506.00022 (2015).

[46]

Zhou, B., et al. Preserving privacy in social networks against neighborhood attacks. In Proc. of ICDE (2008).

Digital Library

[47]

Zhu, W., Thomborson, C., and Wang, F.-Y. A survey of software watermarking. In ISI. 2005.

Digital Library

[48]

Zou, L., Chen, L., and Özsu, M. T. K-automorphism: A general framework for privacy preserving network publication. In VLDB (2009).

Digital Library

Cited By

Liu YWu HZhang X(2024)Robust and Imperceptible Black-Box DNN Watermarking Based on Fourier Perturbation Analysis and Frequency Sensitivity ClusteringIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.338441621:6(5766-5780)Online publication date: Nov-2024
https://doi.org/10.1109/TDSC.2024.3384416
Chen SMalik AZhang XFeng GWu H(2023)A Fast Method for Robust Video Watermarking Based on Zernike MomentsIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.328161833:12(7342-7353)Online publication date: Dec-2023
https://doi.org/10.1109/TCSVT.2023.3281618
Yilmaz EAyday E(2023)Probabilistic Fingerprinting Scheme for Correlated DataData and Applications Security and Privacy XXXVII10.1007/978-3-031-37586-6_5(69-90)Online publication date: 12-Jul-2023
https://doi.org/10.1007/978-3-031-37586-6_5
Show More Cited By

Index Terms

Towards Graph Watermarks
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Data types and structures

Recommendations

Some forbidden subgraph conditions for a graph to have a k-contractible edge
Special issue: Combinatorics 2000

An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. Let K"n^- stand for the graph obtained from K"n by removing one edge. Let G be a k-connected graph (k>=5). It is known that if ...
Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture

An H-decomposition of a graph G=(V,E) is a partition of E into subgraphs isomorphic to H. Given a fixed graph H, the H-decomposition problem is to determine whether an input graph G admits an H-decomposition.In 1980, Holyer conjectured that H-...
The bondage and connectivity of a graph

Let G =(V,E) be a simple graph. A subset S of V is a dominating set of G if for any vertex v ∈ V - S, there exists some vertex u ∈ S such that uv ∈ E(G). The domination number, denoted by γ(G), is the cardinality of a minimum dominating set of G. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

COSN '15: Proceedings of the 2015 ACM on Conference on Online Social Networks

November 2015

280 pages

ISBN:9781450339513

DOI:10.1145/2817946

General Chair:
Aneesh Sharma
Twitter, USA
,
Program Chairs:
Rakesh Agrawal
Data Insights Laboratories, USA
,
Matthias Grossglauser
EPFL, Switzerland

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

ACM: Association for Computing Machinery

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 November 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

COSN'15

Sponsor:

ACM

COSN'15: Conference on Online Social Networks

November 2 - 3, 2015

California, Palo Alto, USA

Acceptance Rates

COSN '15 Paper Acceptance Rate 22 of 82 submissions, 27%;

Overall Acceptance Rate 69 of 307 submissions, 22%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
752
Total Downloads

Downloads (Last 12 months)240
Downloads (Last 6 weeks)25

Reflects downloads up to 02 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu YWu HZhang X(2024)Robust and Imperceptible Black-Box DNN Watermarking Based on Fourier Perturbation Analysis and Frequency Sensitivity ClusteringIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.338441621:6(5766-5780)Online publication date: Nov-2024
https://doi.org/10.1109/TDSC.2024.3384416
Chen SMalik AZhang XFeng GWu H(2023)A Fast Method for Robust Video Watermarking Based on Zernike MomentsIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.328161833:12(7342-7353)Online publication date: Dec-2023
https://doi.org/10.1109/TCSVT.2023.3281618
Yilmaz EAyday E(2023)Probabilistic Fingerprinting Scheme for Correlated DataData and Applications Security and Privacy XXXVII10.1007/978-3-031-37586-6_5(69-90)Online publication date: 12-Jul-2023
https://doi.org/10.1007/978-3-031-37586-6_5
Wu H(2022)Graph Models in Information HidingRecent Applications in Graph Theory10.5772/intechopen.98592Online publication date: 18-May-2022
https://doi.org/10.5772/intechopen.98592
Sarcevic TMayer RRauber A(2022)Adaptive Attacks and Targeted Fingerprinting of Relational Data2022 IEEE International Conference on Big Data (Big Data)10.1109/BigData55660.2022.10020266(5792-5801)Online publication date: 17-Dec-2022
https://doi.org/10.1109/BigData55660.2022.10020266
Li YWang HBarni M(2021)A survey of Deep Neural Network watermarking techniquesNeurocomputing10.1016/j.neucom.2021.07.051461:C(171-193)Online publication date: 21-Oct-2021
https://dl.acm.org/doi/10.1016/j.neucom.2021.07.051
Al-Khafaji HAbhayaratne C(2019)Graph Spectral Domain Blind WatermarkingICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP.2019.8683753(2492-2496)Online publication date: May-2019
https://doi.org/10.1109/ICASSP.2019.8683753
Mauw SRamírez-Cruz YTrujillo-Rasua R(2019)Robust active attacks on social graphsData Mining and Knowledge Discovery10.1007/s10618-019-00631-5Online publication date: 25-Apr-2019
https://doi.org/10.1007/s10618-019-00631-5
Le Merrer EPérez PTrédan G(2019)Adversarial frontier stitching for remote neural network watermarkingNeural Computing and Applications10.1007/s00521-019-04434-zOnline publication date: 17-Aug-2019
https://doi.org/10.1007/s00521-019-04434-z
Al-khafaji HAbhayaratne C(2017)Graph spectral domain watermarking for unstructured data from sensor networks2017 22nd International Conference on Digital Signal Processing (DSP)10.1109/ICDSP.2017.8096148(1-5)Online publication date: Aug-2017
https://doi.org/10.1109/ICDSP.2017.8096148
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten