Xiaohan Zhao
Ben Y. Zhao
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.
- Agrawal, R., and Kiernan, J. Watermarking relational databases. In Proc. of VLDB (2002). Google Scholar
Digital Library
- Albert, R., Jeong, H., and Barabási, A.-L. Internet: Diameter of the world-wide web. Nature 401, 6749 (1999), 130--131.Google ScholarCross Ref
- Arrington, M. How "dirty" mp3 files are a back door into cloud drm. TechCrunch, April 2010.Google Scholar
- Backstrom, L., Dwork, C., and Kleinberg, J. Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography. In WWW (2007). Google ScholarDigital Library
- Bender, W., Gruhl, D., Morimoto, N., and Lu, A. Techniques for data hiding. IBM systems journal (1996), 313--336. Google ScholarDigital Library
- Cho, E., Myers, S. A., and Leskovec, J. Friendship and mobility: user movement in location-based social networks. In KDD (2011). Google ScholarDigital Library
- Collberg, C. S., Kobourov, S. G., Carter, E., and Thomborson, C. D. Graph-based approaches to software watermarking. In WG (2003).Google Scholar
- Cook, S. A. The complexity of theorem-proving procedures. In STOC (1971). Google ScholarDigital Library
- Gilbert, E. N. Random graphs. The Annals of Mathematical Statistics (1959), 1141--1144.Google ScholarCross Ref
- Hanhijärvi, S., Garriga, G. C., and Puolamäki, K. Randomization techniques for graphs. In SDM (2009).Google Scholar
- Hay, M., Miklau, G., Jensen, D., Towsley, D., and Weis, P. Resisting structural re-identification in anonymized social networks.Google Scholar
- Hay, M., Miklau, G., Jensen, D., Weis, P., and Srivastava, S. Anonymizing social networks. Tech. Rep. 07--19, UMass, 2007.Google Scholar
- Kamran, M., et al. A robust, distortion minimizing technique for watermarking relational databases using once-for-all usability constraints. IEEE TKDE (2012). Google ScholarDigital Library
- Lee, S.-J., and Jung, S.-H. A survey of watermarking techniques applied to multimedia. In ISIE (2001).Google Scholar
- Leskovec, J., Adamic, L. A., and Huberman, B. A. The dynamics of viral marketing. TWEB (2007). Google ScholarDigital Library
- Leskovec, J., et al. Statistical properties of community structure in large social and information networks. In WWW (2008). Google ScholarDigital Library
- Leskovec, J., Huttenlocher, D., and Kleinberg, J. Predicting positive and negative links in online social networks. In WWW (2010). Google ScholarDigital Library
- Leskovec, J., Kleinberg, J., and Faloutsos, C. Graphs over time: densification laws, shrinking diameters and possible explanations. In KDD (2005). Google ScholarDigital Library
- Leskovec, J., Kleinberg, J., and Faloutsos, C. Graph evolution: Densification and shrinking diameters. TKDD (2007). Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarDigital Library
- Li, Y., Swarup, V., and Jajodia. Fingerprinting relational databases: Schemes and specialties. IEEE TDSC 2, 1 (2005), 34--45. Google ScholarDigital Library
- Liu, K., and Terzi, E. Towards identity anonymization on graphs. In SIGMOD (2008). Google ScholarDigital Library
- Macq, B. M., and Quisquater, J.-J. Cryptology for digital tv broadcasting. Proceedings of the IEEE (1995), 944--957.Google ScholarCross Ref
- Menezes, A. J., Oorschot, P. v., and Vanstone, S. Handbook of Applied Cryptography. CRC Press, Inc., 1996. Google ScholarDigital Library
- Mislove, A., Marcon, M., Gummadi, K., Druschel, P., and Bhattacharjee, B. Measurement and analysis of online social networks. In IMC (2007). Google ScholarDigital Library
- Narayanan, A., and Shmatikov, V. De-anonymizing social networks. In Proc. of IEEE S&P (May 2009). Google ScholarDigital Library
- Narayanan, A., and Shmatikov, V. Link prediction by de-anonymization: How we won the kaggle social network challenge. In IJCNN (2011).Google Scholar
- Ohbuchi, R., Ueda, H., and Shuh, E. Robust watermarking of vector digital maps. In ICME (2002).Google Scholar
- Ohbuchi, R., Ueda, H., and Shuh, E. Watermarking 2d vector maps in the mesh-spectral domain. In Shape Modeling International (2003). Google ScholarDigital Library
- Qu, G., and Potkonjak, M. Analysis of watermarking techniques for graph coloring problem. In ICCAD (1998). Google ScholarDigital Library
- Richardson, M., Agrawal, R., and Domingos, P. Trust management for the semantic web. In The Semantic Web-ISWC 2003. Springer, 2003, pp. 351--368.Google Scholar
- Robshaw, M. J. B. MD2, MD4, MD5, SHA and other hash functions. Tech. Rep. TR-101, RSA Laboratories, 1995. v. 4.0.Google Scholar
- Ruanaidh, J. O., Dowling, W., and Boland, F. Phase watermarking of digital images. In ICIP (1996).Google Scholar
- 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). Google ScholarDigital Library
- Sala, A., Zhao, X., Wilson, C., Zheng, H., and Zhao, B. Y. Sharing graphs using differentially private graph models. In IMC (2011). Google ScholarDigital Library
- Steve, W. Information authentication for a slippery new age. Dr. Dobbs Journal (1995), 18--26.Google Scholar
- Takac, L., and Zabovsky, M. Data analysis in public social networks. In International Scientific Conference AND International Workshop Present Day Trends of Innovations (2012).Google Scholar
- Venkatesan, R., Vazirani, V., and Sinha, S. A graph theoretic approach to software watermarking. In Information Hiding (2001). Google ScholarDigital Library
- 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). Google ScholarDigital Library
- Wolfe, G., Wong, J. L., and Potkonjak, M. Watermarking graph partitioning solutions. In DAC (2001). Google ScholarDigital Library
- Xia, X.-G., Boncelet, C. G., and Arce, G. R. A multiresolution watermark for digital images. In ICIP (1997). Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Ying, X., and Wu, X. Randomizing social networks: a spectrum preserving approach. In SDM (2008).Google Scholar
- Zhao, X., Liu, Q., Zhou, L., Zheng, H., and Zhao, B. Y. Graph watermarks. Arxiv preprint arXiv:1506.00022 (2015).Google Scholar
- Zhou, B., et al. Preserving privacy in social networks against neighborhood attacks. In Proc. of ICDE (2008). Google ScholarDigital Library
- Zhu, W., Thomborson, C., and Wang, F.-Y. A survey of software watermarking. In ISI. 2005. Google ScholarDigital Library
- Zou, L., Chen, L., and Özsu, M. T. K-automorphism: A general framework for privacy preserving network publication. In VLDB (2009). Google ScholarDigital Library
Index Terms
- Towards Graph Watermarks
Recommendations
Some forbidden subgraph conditions for a graph to have a k-contractible edge
Special issue: Combinatorics 2000An 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