{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:43Z","timestamp":1787340343305,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>A $k$-disc around a vertex $v$ of a graph $G=(V,E)$ is the subgraph induced by all vertices of distance at most $k$ from $v$. We show that the structure of a planar graph on $n$ vertices, and with constant maximum degree $d$, is determined, up to the modification (insertion or deletion) of at most $\\epsilon d n$ edges, by the frequency of $k$-discs for certain $k=k(\\epsilon,d)$ that is independent of the size of the graph. We can replace planar graphs by any hyperfinite class of graphs, which includes, for example, every graph class that does not contain a set of forbidden minors. A pure combinatorial consequence of this result is that two $d$-bounded degree graphs that have similar frequency vectors (that is, the $\\ell_1$ difference between the frequency vectors is small) are close to isomorphic (where close here means that by inserting or deleting not too many edges in one of them, it becomes isomorphic to the other). We also obtain the following new results in the area of property testing, which are essentially equivalent to the above statement. We prove that (a) graph isomorphism is testable for every class of hyperfinite graphs, (b) every graph property is testable for every class of hyperfinite graphs, (c) every hyperfinite graph property is testable in the bounded degree graph model, (d) A large class of graph parameters is approximable for hyperfinite graphs. Our results also give a partial explanation of the success of motifs in the analysis of complex networks.<\/jats:p>","DOI":"10.1137\/120890946","type":"journal-article","created":{"date-parts":[[2013,6,14]],"date-time":"2013-06-14T15:26:25Z","timestamp":1371223585000},"page":"1095-1112","source":"Crossref","is-referenced-by-count":41,"title":["Every Property of Hyperfinite Graphs Is Testable"],"prefix":"10.1137","volume":"42","author":[{"given":"Ilan","family":"Newman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,6,13]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"N. Alon, E. Fischer, I. Newman, and A. Shapira,\n                      A combinatorial characterization of the testable graph properties: It's all about regularity\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), 2006, pp. 251-260.","DOI":"10.1145\/1132516.1132555"},{"key":"atypb2","unstructured":"N. Alon and J. Spencer,\n                      The Probabilistic Method\n                      , John Wiley, New York, 1992."},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"N. Alon, P. Seymour, and R. Thomas,\n                      A separator theorem for graphs with an excluded minor and its applications\n                      , in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), 1990, pp. 293-299.","DOI":"10.1145\/100216.100254"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"I. Benjamini, O. Schramm, and A. Shapira,\n                      Every minor-closed property of sparse graphs is testable\n                      , in Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), 2008, pp. 393-402.","DOI":"10.1145\/1374376.1374433"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/070681831"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2008.01.010"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20308"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"G. Elek,\n                      Finite Graphs and Amenability\n                      , arXiv:1204.0449v2, 2012.","DOI":"10.1016\/j.jfa.2012.08.021"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0078-7"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"A. Hassidim, J. A. Kelner, H. N. Nguyen, and K. Onak,\n                      Local graph partitions for approximation and testing\n                      , in Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), 2009, pp. 22-31.","DOI":"10.1109\/FOCS.2009.77"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80048-5"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"H. Nguyen and K. Onak,\n                      Constant-time approximation algorithms via local improvements\n                      , in Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (FOCS), 2008, pp. 327-336.","DOI":"10.1109\/FOCS.2008.81"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"I. Newman and C. Sohler,\n                      Every property of hyperfinite graphs is testable\n                      , in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), 2011, pp. 675-684.","DOI":"10.1145\/1993636.1993726"},{"key":"atypb18","unstructured":"K. Onak,\n                      New Sublinear Methods in the Struggle Against Classical Problems\n                      , Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, 2010."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"atypb20","unstructured":"S. Raskhodnikova and A. Smith,\n                      A note on adaptivity in testing properties in bounded degree graphs\n                      , Electronic Colloquium on Computational Complexity, TR06-089, 2006."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120890946","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:31:04Z","timestamp":1787337064000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120890946"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/120890946"],"URL":"https:\/\/doi.org\/10.1137\/120890946","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}