{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:14:12Z","timestamp":1779174852074,"version":"3.51.4"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,10,7]],"date-time":"2014-10-07T00:00:00Z","timestamp":1412640000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"University Graduate Fellowship"},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000169","name":"Division of Behavioral and Cognitive Sciences","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000169","id-type":"DOI","asserted-by":"publisher"}]},{"name":"College of Engineering Fellowship"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2014,10,7]]},"abstract":"<jats:p>\n            We present efficient algorithms for releasing useful statistics about graph data while providing rigorous privacy guarantees. Our algorithms work on datasets that consist of relationships between individuals, such as social ties or email communication. The algorithms satisfy\n            <jats:italic>edge differential privacy<\/jats:italic>\n            , which essentially requires that the presence or absence of any particular relationship be hidden.\n          <\/jats:p>\n          <jats:p>\n            Our algorithms output approximate answers to\n            <jats:italic>subgraph counting queries<\/jats:italic>\n            . Given a query graph\n            <jats:italic>H<\/jats:italic>\n            , for example, a triangle,\n            <jats:italic>k<\/jats:italic>\n            -star, or\n            <jats:italic>k<\/jats:italic>\n            -triangle, the goal is to return the number of edge-induced isomorphic copies of\n            <jats:italic>H<\/jats:italic>\n            in the input graph. The special case of triangles was considered by Nissim et al. [2007] and a more general investigation of arbitrary query graphs was initiated by Rastogi et al. [2009]. We extend the approach of Nissim et al. to a new class of statistics, namely\n            <jats:italic>k<\/jats:italic>\n            -star queries. We also give algorithms for\n            <jats:italic>k<\/jats:italic>\n            -triangle queries using a different approach based on the higher-order local sensitivity. For the specific graph statistics we consider (i.e.,\n            <jats:italic>k<\/jats:italic>\n            -stars and\n            <jats:italic>k<\/jats:italic>\n            -triangles), we significantly improve on the work of Rastogi et al.: our algorithms satisfy a stronger notion of privacy that does not rely on the adversary having a particular prior distribution on the data, and add less noise to the answers before releasing them.\n          <\/jats:p>\n          <jats:p>\n            We evaluate the accuracy of our algorithms both theoretically and empirically, using a variety of real and synthetic datasets. We give explicit, simple conditions under which these algorithms add a small amount of noise. We also provide the average-case analysis in the Erd\u0151s-R\u00e9nyi-Gilbert\n            <jats:italic>G<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ,\n            <jats:italic>p<\/jats:italic>\n            ) random graph model.\n          <\/jats:p>\n          <jats:p>\n            Finally, we give hardness results indicating that the approach Nissim et al. used for triangles cannot easily be extended to\n            <jats:italic>k<\/jats:italic>\n            -triangles (hence justifying our development of a new algorithmic approach).\n          <\/jats:p>","DOI":"10.1145\/2611523","type":"journal-article","created":{"date-parts":[[2014,10,7]],"date-time":"2014-10-07T12:57:47Z","timestamp":1412686667000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":70,"title":["Private Analysis of Graph Structure"],"prefix":"10.1145","volume":"39","author":[{"given":"Vishesh","family":"Karwa","sequence":"first","affiliation":[{"name":"The Pennsylvania State University, University Park, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sofya","family":"Raskhodnikova","sequence":"additional","affiliation":[{"name":"The Pennsylvania State University, University Park, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Smith","sequence":"additional","affiliation":[{"name":"The Pennsylvania State University, University Park, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grigory","family":"Yaroslavtsev","sequence":"additional","affiliation":[{"name":"The Pennsylvania State University, University Park, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,10,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"N. Alon and J. Spencer. 2000. The Probabilistic Method 2nd Ed. Wiley-Interscience.  N. Alon and J. Spencer. 2000. The Probabilistic Method 2 nd Ed. Wiley-Interscience.","DOI":"10.1002\/0471722154"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242598"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465304"},{"key":"e_1_2_1_5_1","volume-title":"Dimacs workshop on recent work on differential privacy across computer science. http:\/\/dimacs.rutgers.edu\/Workshops\/DifferentialPrivacy.","author":"DIMACS.","year":"2012"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_29"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_29"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536466"},{"key":"e_1_2_1_11_1","first-page":"2","article-title":"Differential privacy for statistics: What we know and what we want to learn","volume":"1","author":"Dwork C.","year":"2009","journal-title":"J. Privacy Confidential."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"J.\n       \n      Gehrke E.\n       \n      Lui and \n      \n      \n      R.\n       \n      Pass\n      \n  \n  . \n  2011\n  . Towards privacy for social networks: A zero-knowledge based definition of privacy. In Proceedings of the 8th Conference on Theory of Cryptography (TCC'11). Y. Ishai Ed. Lecture Notes in Computer Science vol. \n  6597 Springer 432--449.   J. Gehrke E. Lui and R. Pass. 2011. Towards privacy for social networks: A zero-knowledge based definition of privacy. In Proceedings of the 8 th Conference on Theory of Cryptography (TCC'11). Y. Ishai Ed. Lecture Notes in Computer Science vol. 6597 Springer 432--449.","DOI":"10.1007\/978-3-642-19571-6_26"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000005"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_19"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.11"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2006.08.005"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402749"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33627-0_21"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806795"},{"key":"e_1_2_1_21_1","unstructured":"S. P. Kasiviswanathan and A. Smith. 2008. A note on differential privacy: Defining resistance to arbitrary side information. https:\/\/eprint.iacr.org\/2008\/144.pdf.  S. P. Kasiviswanathan and A. Smith. 2008. A note on differential privacy: Defining resistance to arbitrary side information. https:\/\/eprint.iacr.org\/2008\/144.pdf."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989345"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"E. D. Kolaczyk. 2009. Statistical Analysis of Network Data: Methods and Models. Springer.   E. D. Kolaczyk. 2009. Statistical Analysis of Network Data: Methods and Models. Springer.","DOI":"10.1007\/978-0-387-88146-1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463721"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557090"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2320765.2320818"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2009.22"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559812"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2006.08.002"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM Press","author":"Ross K. A."},{"key":"e_1_2_1_32_1","unstructured":"A. Roth. 2011. The algorithmic foundations of differential privacy. http:\/\/www.cis.upenn.edu\/&sim;aaroth\/courses\/privacyF11.html.  A. Roth. 2011. The algorithmic foundations of differential privacy. http:\/\/www.cis.upenn.edu\/&sim;aaroth\/courses\/privacyF11.html."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509013.2509016"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9531.2006.00176.x"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10032"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1540276.1540279"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2611523","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2611523","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:33Z","timestamp":1750230093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2611523"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,7]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,10,7]]}},"alternative-id":["10.1145\/2611523"],"URL":"https:\/\/doi.org\/10.1145\/2611523","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,7]]},"assertion":[{"value":"2012-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}