{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:02Z","timestamp":1750220642488,"version":"3.41.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T00:00:00Z","timestamp":1591401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007515","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1617306, CCF-1563838, CCF-1318374"],"award-info":[{"award-number":["CCF-1617306, CCF-1563838, CCF-1318374"]}],"id":[{"id":"10.13039\/100007515","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,7,31]]},"abstract":"<jats:p>We study the following structure learning problem for<jats:italic>H<\/jats:italic>-colorings. For a fixed (and known) constraint graph<jats:italic>H<\/jats:italic>with<jats:italic>q<\/jats:italic>colors, given access to uniformly random<jats:italic>H<\/jats:italic>-colorings of an unknown graph<jats:italic>G=(V,E)<\/jats:italic>, how many samples are required to learn the edges of\u00a0<jats:italic>G<\/jats:italic>? We give a characterization of the constraint graphs\u00a0<jats:italic>H<\/jats:italic>for which the problem is identifiable for every\u00a0<jats:italic>G<\/jats:italic>and show that there are identifiable constraint graphs for which one cannot hope to learn every graph\u00a0<jats:italic>G<\/jats:italic>efficiently. We provide refined results for the case of proper vertex<jats:italic>q<\/jats:italic>-colorings of graphs of maximum degree\u00a0<jats:italic>d<\/jats:italic>. In particular, we prove that in the tree uniqueness region (i.e., when<jats:italic>q\u2264 d<\/jats:italic>), the problem is identifiable and we can learn<jats:italic>G<\/jats:italic>in poly(<jats:italic>d,q<\/jats:italic>)\u00d7 O(n<jats:sup>2<\/jats:sup>log<jats:italic>n<\/jats:italic>) time. In the tree non-uniqueness region (i.e., when q\u2264 d), we show that the problem is not identifiable and thus<jats:italic>G<\/jats:italic>cannot be learned. Moreover, when<jats:italic>q \u2264 d<\/jats:italic>- \u221ad + \u0398 (1), we establish that even learning an equivalent graph (any graph with the same set of<jats:italic>H<\/jats:italic>-colorings) is computationally hard\u2014sample complexity is exponential in<jats:italic>n<\/jats:italic>in the worst case. We further explore the connection between the efficiency\/hardness of the structure learning problem and the uniqueness\/non-uniqueness phase transition for general<jats:italic>H<\/jats:italic>-colorings and prove that under a well-known uniqueness condition in statistical physics, we can learn<jats:italic>G<\/jats:italic>in poly(<jats:italic>d,q<\/jats:italic>)\u00d7 O(n<jats:sup>2<\/jats:sup>log<jats:italic>n<\/jats:italic>) time.<\/jats:p>","DOI":"10.1145\/3382207","type":"journal-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T00:47:00Z","timestamp":1591490820000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Structure Learning of H-Colorings"],"prefix":"10.1145","volume":"16","author":[{"given":"Antonio","family":"Blanca","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zongchen","family":"Chen","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"\u0160tefankovi\u00e8","sequence":"additional","affiliation":[{"name":"University of Rochester"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Vigoda","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,6]]},"reference":[{"key":"e_1_2_1_1_1","article-title":"Learning factor graphs in polynomial time and sample complexity","author":"Abbeel Pieter","year":"2006","journal-title":"Journal of Machine Learning Research 7"},{"volume-title":"Kakade","year":"2012","author":"Anandkumar Anima","key":"e_1_2_1_2_1"},{"volume-title":"Proceedings of the 31st Conference on Learning Theory (COLT\u201919)","year":"2019","author":"Bez\u00e1kov\u00e1 Ivona","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746631"},{"key":"e_1_2_1_5_1","unstructured":"Guy Bresler David Gamarnik and Devavrat Shah. 2014. Hardness of parameter estimation in graphical models. In Advances in Neural Information Processing Systems (NeurIPS\u201914). 1062--1070. Guy Bresler David Gamarnik and Devavrat Shah. 2014. Hardness of parameter estimation in graphical models. In Advances in Neural Information Processing Systems (NeurIPS\u201914). 1062--1070."},{"key":"e_1_2_1_6_1","unstructured":"Guy Bresler David Gamarnik and Devavrat Shah. 2014. Structure learning of antiferromagnetic Ising models. In Advances in Neural Information Processing Systems (NeurIPS\u201914). 2852--2860. Guy Bresler David Gamarnik and Devavrat Shah. 2014. Structure learning of antiferromagnetic Ising models. In Advances in Neural Information Processing Systems (NeurIPS\u201914). 2852--2860."},{"key":"e_1_2_1_7_1","unstructured":"Guy Bresler and Mina Karzand. 2016. Learning a tree-structured Ising model in order to make predictions. arXiv:1604.06749. Guy Bresler and Mina Karzand. 2016. Learning a tree-structured Ising model in order to make predictions. arXiv:1604.06749."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/100796029"},{"key":"e_1_2_1_9_1","first-page":"247","article-title":"Random colorings of a Cayley tree","volume":"10","author":"Brightwell Graham R.","year":"2002","journal-title":"Contemporary Combinatorics"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.028"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054142"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/009053605000000912"},{"volume-title":"Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI\u201999)","year":"1999","author":"Dasgupta Sanjoy","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1214\/12-AOP828"},{"volume-title":"The description of a random field by means of conditional probabilities and conditions of its regularity. Theory of Probability 8 Its Applications 13, 2","year":"1968","author":"Dobrushin R. L.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"R. L. Dobrushin and S. B. Shlosman. 1985. Constructive criterion for the uniqueness of Gibbs field. In Statistical Physics and Dynamical Systems. Vol. 10. Birkh\u00e4user Boston Boston MA 347--370. R. L. Dobrushin and S. B. Shlosman. 1985. Constructive criterion for the uniqueness of Gibbs field. In Statistical Physics and Dynamical Systems. Vol. 10. Birkh\u00e4user Boston Boston MA 347--370.","DOI":"10.1007\/978-1-4899-6653-7_20"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009437"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W"},{"volume-title":"Mixing in time and space for lattice spin systems: A combinatorial view. Random Structures 8 Algorithms 24, 4","year":"2004","author":"Dyer Martin","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0900282106"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003678"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1020551"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2785964"},{"volume-title":"De Gruyter Studies in Mathematics","author":"Georgii Hans-Otto","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509917"},{"key":"e_1_2_1_27_1","unstructured":"Linus Hamilton Frederic Koehler and Ankur Moitra. 2017. Information theoretic properties of Markov random fields and their algorithmic applications. In Advances in Neural Information Processing Systems (NeurIPS\u201917). 2460--2469. Linus Hamilton Frederic Koehler and Ankur Moitra. 2017. Information theoretic properties of Markov random fields and their algorithmic applications. In Advances in Neural Information Processing Systems (NeurIPS\u201917). 2460--2469."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"volume-title":"Oxford Lecture Series in Mathematics and Its Applications","author":"Hell Pavol","key":"e_1_2_1_29_1"},{"volume-title":"Bollback","year":"2001","author":"Huelsenbeck John P.","key":"e_1_2_1_30_1"},{"volume-title":"Proceedings of the 14th International Conference on Artificial Intelligence and Statistics. 378--387","year":"2011","author":"Jalali Ali","key":"e_1_2_1_31_1"},{"volume-title":"Uniqueness of uniform random colorings of regular trees. Statistics 8 Probability Letters 57, 3","year":"2002","author":"Jonasson Johan","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.39"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Su-In Lee Varun Ganapathi and Daphne Koller. 2007. Efficient structure learning of Markov networks using -regularization. In Advances in Neural Information Processing Systems (NeurIPS\u201907). 817--824. Su-In Lee Varun Ganapathi and Daphne Koller. 2007. Efficient structure learning of Markov networks using -regularization. In Advances in Neural Information Processing Systems (NeurIPS\u201907). 817--824.","DOI":"10.7551\/mitpress\/7503.003.0107"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.5"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth.2016"},{"volume-title":"Fast mixing for independent sets, colorings, and other models on trees. Random Structures 8 Algorithms 31, 2","year":"2007","author":"Martinelli Fabio","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380840"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1111471108"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1214\/09-AOS691"},{"volume":"2","volume-title":"Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201905)","author":"Roth Stefan","key":"e_1_2_1_41_1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature04701"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/080736697"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.34"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.56"},{"volume-title":"Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (UAI\u201901)","year":"2001","author":"Srebro Nathan","key":"e_1_2_1_46_1"},{"key":"e_1_2_1_47_1","unstructured":"Marc Vuffray Sidhant Misra Andrey Lokhov and Michael Chertkov. 2016. Interaction screening: Efficient and sample-optimal learning of Ising models. In Advances in Neural Information Processing Systems (NeurIPS\u201916). 2595--2603. Marc Vuffray Sidhant Misra Andrey Lokhov and Michael Chertkov. 2016. Interaction screening: Efficient and sample-optimal learning of Ising models. In Advances in Neural Information Processing Systems (NeurIPS\u201916). 2595--2603."},{"volume-title":"Combinatorial criteria for uniqueness of Gibbs measures. Random Structures 8 Algorithms 27, 4","year":"2005","author":"Weitz Dror","key":"e_1_2_1_48_1"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132538"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382207","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3382207","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:09Z","timestamp":1750197729000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,6]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,7,31]]}},"alternative-id":["10.1145\/3382207"],"URL":"https:\/\/doi.org\/10.1145\/3382207","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2020,6,6]]},"assertion":[{"value":"2018-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}