Abstract: We introduce security and algorithmic foundations for graph watermarking. Our foundations are based on characterizing the feasibility of graph watermarking in terms of keygen, marking, and identification functions defined over graph families with known distributions. We demonstrate the strength of this approach with exemplary watermarking schemes for two random graph models, both of which are used to model real-world networks. In addition, unlike previous marking/de-anonymization schemes based on adding new vertices, our framework supports effective graph watermarking schemes that use only edge flipping.
Joint work with David Eppstein, Michael T. Goodrich, and Michael Mitzenmacher