{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T00:24:56Z","timestamp":1759883096372,"version":"build-2065373602"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2026,1,31]]},"abstract":"<jats:p>\n            We design the first node-differentially private algorithm for approximating the number of connected components in a graph. Given a database representing an\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( n \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -vertex graph\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( G \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and a privacy parameter\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\varepsilon\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , our algorithm runs in polynomial time and, with probability\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(1-o(1)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , has additive error\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\widetilde{O}(\\frac{\\Delta^{*}\\ln\\ln n}{\\varepsilon}),\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            where\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Delta^{*}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            is the smallest possible maximum degree of a spanning forest of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(G.\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            Node-differentially private algorithms are known only for a small number of database analysis tasks. A major obstacle for designing such an algorithm for the number of connected components is that this graph statistic is not robust to adding one node with arbitrary connections (a change that node-differential privacy is designed to hide):\n            <jats:italic toggle=\"yes\">every<\/jats:italic>\n            graph is a neighbor of a connected graph.\n          <\/jats:p>\n          <jats:p>\n            We overcome this by designing a family of efficiently computable Lipschitz extensions of the number of connected components or, equivalently, the size of a spanning forest. The construction of the extensions, which is at the core of our algorithm, is based on the forest polytope of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(G.\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            We prove several combinatorial facts about spanning forests, in particular, that a graph with no induced\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Delta\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -stars has a spanning forest of degree at most\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Delta\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . With this fact, we show that our Lipschitz extensions for the number of connected components equal the true value of the function for the largest possible monotone families of graphs. More generally, on all monotone sets of graphs, the\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\ell_{\\infty}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            error of our Lipschitz extensions is nearly optimal.\n          <\/jats:p>","DOI":"10.1145\/3762664","type":"journal-article","created":{"date-parts":[[2025,8,25]],"date-time":"2025-08-25T13:50:47Z","timestamp":1756129847000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Node-Differentially Private Estimation of the Number of Connected Components"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0995-6346","authenticated-orcid":false,"given":"Iden","family":"Kalemaj","sequence":"first","affiliation":[{"name":"Boston University, Boston, Massachusetts, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4902-050X","authenticated-orcid":false,"given":"Sofya","family":"Raskhodnikova","sequence":"additional","affiliation":[{"name":"Boston University, Boston, Massachusetts, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9393-1127","authenticated-orcid":false,"given":"Adam","family":"Smith","sequence":"additional","affiliation":[{"name":"Boston University, Boston, Massachusetts, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5591-3585","authenticated-orcid":false,"given":"Charalampos","family":"Tsourakakis","sequence":"additional","affiliation":[{"name":"Boston University, Boston, Massachusetts, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,10,7]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2019.2901716"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-014-0365-y"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1214\/10-AAP718"},{"key":"e_1_3_2_5_2","volume-title":"Geometric Nonlinear Functional Analysis\n                  Colloquium Publications","author":"Benyamini Yoav","year":"1998","unstructured":"Yoav Benyamini and Joram Lindenstrauss. 1998. Geometric Nonlinear Functional Analysis. Colloquium Publications, Vol. 48. American Mathematical Society, Providence, RI, USA."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.05.008"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.67"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.26"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-17142-5_14"},{"key":"e_1_3_2_11_2","first-page":"1369","volume-title":"Advances in Neural Information Processing Systems 28 (NIPS \u201915)","author":"Borgs Christian","year":"2015","unstructured":"Christian Borgs, Jennifer T. Chayes, and Adam D. Smith. 2015. Private graphon estimation for sparse graphs. In Advances in Neural Information Processing Systems 28 (NIPS \u201915). Curran Associates Inc., Red Hook, NY, USA, 1369\u20131377."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00057"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403244"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1214\/18-AOAS1163"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465304"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-26390-3_1"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.32"},{"key":"e_1_3_2_18_2","unstructured":"Ameya Daigavane Gagan Madan Aditya Sinha Abhradeep Guha Thakurta Gaurav Aggarwal and Prateek Jain. 2021. Node-level differentially private graph neural networks. arXiv:2111.15521. Retrieved from https:\/\/arxiv.org\/abs\/2111.15521"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2926745"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00077"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271736"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_29"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.v7i3.405"},{"key":"e_1_3_2_24_2","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s Paul","year":"1960","unstructured":"Paul Erd\u0151s and Alfr\u00e9d R\u00e9nyi. 1960. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5 (1960), 17\u201361.","journal-title":"Publications of the Mathematical Institute of the Hungarian Academy of Sciences"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129124"},{"issue":"4","key":"e_1_3_2_26_2","first-page":"177","article-title":"Estimation of the number of connected components in a graph by using a sampled subgraph","volume":"5","author":"Frank Ove","year":"1978","unstructured":"Ove Frank. 1978. Estimation of the number of connected components in a graph by using a sampled subgraph. Scandinavian Journal of Statistics 5, 4 (Dec. 1978), 177\u2013188.","journal-title":"Scandinavian Journal of Statistics"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729949"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_19"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.11"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.121"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2611523"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33627-0_21"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2670979.2670997"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.3150\/19-BEJ1147"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.3040077"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623683"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1934-05978-0"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.41"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_3_2_41_2","unstructured":"Tamara T. Mueller Dmitrii Usynin Johannes C. Paetzold Daniel Rueckert and Georgios Kaissis. 2022. SoK: Differential privacy on graph-structured data. arXiv:2203.09205. Retrieved from https:\/\/arxiv.org\/abs\/2203.09205"},{"key":"e_1_3_2_42_2","first-page":"247","volume-title":"Proceedings of the Workshops of the EDBT\/ICDT 2015 Joint Conference (EDBT\/ICDT Workshops \u201915)","author":"M\u00fclle Yvonne","year":"2015","unstructured":"Yvonne M\u00fclle, Chris Clifton, and Klemens B\u00f6hm. 2015. Privacy-integrated graph clustering through differential privacy. In Proceedings of the Workshops of the EDBT\/ICDT 2015 Joint Conference (EDBT\/ICDT Workshops \u201915). CEUR-WS.org, Aachen, Germany, 247\u2013254."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2994620.2994624"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73429-7"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-012-0428-1"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732296.2732300"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_549"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.60"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737405"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.745"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-42033-7_15"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37456-2_28"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-013-0127-7"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788671"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452756"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00701-5"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737785"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2927365"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM50108.2020.00184"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2022.37"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3762664","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T15:03:55Z","timestamp":1759849435000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3762664"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,7]]},"references-count":61,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1,31]]}},"alternative-id":["10.1145\/3762664"],"URL":"https:\/\/doi.org\/10.1145\/3762664","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,10,7]]},"assertion":[{"value":"2023-08-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-10","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}