{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:00:16Z","timestamp":1760148016645,"version":"build-2065373602"},"reference-count":49,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2023,3,20]],"date-time":"2023-03-20T00:00:00Z","timestamp":1679270400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Natural Science Foundation of China","award":["U20A20161"],"award-info":[{"award-number":["U20A20161"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The order reduction method is an important approach to optimize higher-order binary Markov random fields (HoMRFs), which are widely used in information theory, machine learning and image analysis. It transforms an HoMRF into an equivalent and easier reduced first-order binary Markov random field (RMRF) by elaborately setting the coefficients and auxiliary variables of RMRF. However, designing order reduction methods is difficult, and no previous study has investigated this design issue. In this paper, we propose an order reduction design framework to study this problem for the first time. Through study, we find that the design difficulty mainly lies in that the coefficients and variables of RMRF must be set simultaneously. Therefore, the proposed framework decomposes the design difficulty into two processes, and each process mainly considers the coefficients or auxiliary variables of RMRF. Some valuable properties are also proven. Based on our framework, a new family of 14 order reduction methods is provided. Experiments, such as synthetic data and image denoising, demonstrate the superiority of our method.<\/jats:p>","DOI":"10.3390\/e25030535","type":"journal-article","created":{"date-parts":[[2023,3,21]],"date-time":"2023-03-21T03:15:03Z","timestamp":1679368503000},"page":"535","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Order Reduction Design Framework for Higher-Order Binary Markov Random Fields"],"prefix":"10.3390","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5314-1435","authenticated-orcid":false,"given":"Zhuo","family":"Chen","sequence":"first","affiliation":[{"name":"Sichuan University National Key Laboratory of Fundamental Science on Synthetic Vision, Sichuan University, No. 29 Wangjiang Road, Chengdu 610065, China"}]},{"given":"Hongyu","family":"Yang","sequence":"additional","affiliation":[{"name":"Sichuan University National Key Laboratory of Fundamental Science on Synthetic Vision, Sichuan University, No. 29 Wangjiang Road, Chengdu 610065, China"}]},{"given":"Yanli","family":"Liu","sequence":"additional","affiliation":[{"name":"College of Computer Science, Sichuan University, No. 29 Wangjiang Road, Chengdu 610065, China"}]}],"member":"1968","published-online":{"date-parts":[[2023,3,20]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Ishikawa, H. (2009, January 20\u201325). Higher-order clique reduction in binary graph cut. Proceedings of the CVPR, Miami, FL, USA.","DOI":"10.1109\/CVPR.2009.5206689"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1234","DOI":"10.1109\/TPAMI.2010.91","article-title":"Transformation of general binary MRF minimization to the first-order case","volume":"33","author":"Ishikawa","year":"2011","journal-title":"IEEE TPAMI"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Fix, A., Gruber, A., Boros, E., and Zabih, R. (2011, January 6\u201313). A graph cut algorithm for higher-order Markov Random Fields. Proceedings of the ICCV, Barcelona, Spain.","DOI":"10.1109\/ICCV.2011.6126347"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1387","DOI":"10.1109\/TPAMI.2014.2382109","article-title":"A Hypergraph-Based Reduction for Higher-Order Binary Markov Random Fields","volume":"37","author":"Fix","year":"2015","journal-title":"IEEE TPAMI"},{"key":"ref_5","first-page":"4911","article-title":"Higher Order Energies for Image Segmentation","volume":"26","author":"Shen","year":"2017","journal-title":"IEEE TIP"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Messaoud, S., Kumar, M., and Schwing, A.G. (2020, January 14\u201319). Can We Learn Heuristics for Graphical Model Inference Using Reinforcement Learning?. Proceedings of the CVPR, Seattle, WA, USA.","DOI":"10.1109\/CVPR42600.2020.00761"},{"key":"ref_7","first-page":"6909","article-title":"An ILP Model for Multi-Label MRFs With Connectivity Constraints","volume":"29","author":"Shen","year":"2020","journal-title":"IEEE TIP"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Cofr\u00e9, R., and Maldonado, C. (2018). Information Entropy Production of Maximum Entropy Markov Chains from Spike Trains. Entropy, 20.","DOI":"10.20944\/preprints201806.0114.v1"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Auzina, I.A., and Tomczak, J.M. (2021). Approximate Bayesian Computation for Discrete Spaces. Entropy, 23.","DOI":"10.3390\/e23030312"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Romanov, E., and Ordentlich, O. (2021). On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel. Entropy, 23.","DOI":"10.3390\/e23050605"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Sioofy Khoojine, A., Shadabfar, M., and Edrisi Tabriz, Y. (2022). A Mutual Information-Based Network Autoregressive Model for Crude Oil Price Forecasting Using Open-High-Low-Close Prices. Mathematics, 10.","DOI":"10.3390\/math10173172"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"104001","DOI":"10.1088\/1361-6633\/ac8c54","article-title":"Quantum Annealing for Industry Applications: Introduction and Review","volume":"85","author":"Yarkoni","year":"2022","journal-title":"Rep. Prog. Phys."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"120621","DOI":"10.1016\/j.apenergy.2022.120621","article-title":"Quantum computing for future real-time building HVAC controls","volume":"334","author":"Deng","year":"2023","journal-title":"Appl. Energy"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1016\/j.ins.2022.11.083","article-title":"What perceptron neural networks are (not) good for?","volume":"621","author":"Calude","year":"2023","journal-title":"Inf. Sci."},{"key":"ref_15","unstructured":"Freedman, D., and Drineas, P. (2005, January 20\u201326). Energy minimization via graph cuts: Settling what is possible. Proceedings of the CVPR, San Diego, CA, USA."},{"key":"ref_16","unstructured":"Gruber, A. (2015). Algorithmic and Complexity Results for Boolean and Pseudo-Boolean Functions. [Ph.D. Thesis, New Brunswick Rutgers, The State University of New Jersey]."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.dam.2016.01.001","article-title":"Quadratization of symmetric pseudo-Boolean functions","volume":"203","author":"Anthony","year":"2016","journal-title":"Discret. Appl. Math."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s10107-016-1032-4","article-title":"Quadratic reformulations of nonlinear binary optimization problems","volume":"162","author":"Anthony","year":"2017","journal-title":"Math. Program."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0166-218X(01)00341-9","article-title":"Pseudo-boolean optimization","volume":"123","author":"Boros","year":"2002","journal-title":"Discret. Appl. Math."},{"key":"ref_20","unstructured":"Yip, K.W., Xu, H., Koenig, S., and Kumar, T.K.S. (2019). Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 16th International Conference, CPAIOR 2019, Proceedings 16, Thessaloniki, Greece, 4\u20137 June 2019, Springer."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Boros, E., Crama, Y., and Rodr\u00edguez-Heck, E. (2018, January 3\u20135). Quadratizations of symmetric pseudo-Boolean functions: Sub-linear bounds on the number of auxiliary variables. Proceedings of the International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, FL, USA.","DOI":"10.1007\/s10878-019-00511-0"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1007\/s10878-019-00511-0","article-title":"Compact quadratizations for pseudo-Boolean functions","volume":"39","author":"Boros","year":"2020","journal-title":"J. Comb. Optim."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1222","DOI":"10.1109\/34.969114","article-title":"Fast approximate energy minimization via graph cuts","volume":"23","author":"Boykov","year":"2001","journal-title":"IEEE TPAMI"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Lempitsky, V., Rother, C., and Blake, A. (2007, January 14\u201321). LogCut\u2014Efficient Graph Cut Optimization for Markov Random Fields. Proceedings of the ICCV, Rio De Janeiro, Brazil.","DOI":"10.1109\/ICCV.2007.4408907"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1392","DOI":"10.1109\/TPAMI.2009.143","article-title":"Fusion Moves for Markov Random Field Optimization","volume":"32","author":"Lempitsky","year":"2010","journal-title":"IEEE TPAMI"},{"key":"ref_26","unstructured":"Schlesinger, D., and FLACH, B. (2006). Transforming an Arbitrary Minsum Problem into a Binary One, Dresden University of Technology. Technical Report TUD-FI06-01."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1557","DOI":"10.1007\/s11590-019-01460-7","article-title":"Optimal quadratic reformulations of fourth degree Pseudo-Boolean functions","volume":"14","author":"Verma","year":"2020","journal-title":"Optim. Lett."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1109\/TPAMI.2004.1262177","article-title":"What energy functions can be minimized via graph cuts","volume":"26","author":"Kolmogorov","year":"2004","journal-title":"IEEE TPAMI"},{"key":"ref_29","first-page":"71","article-title":"Reduction of bivalent maximization to the quadratic case","volume":"17","author":"Rosenberg","year":"1975","journal-title":"Cah. Cent. Tudes Rech. Op\u00e9R"},{"key":"ref_30","unstructured":"Bardet, M. (2002, January 25). On the Complexity of a Grobner Basis Algorithm. Proceedings of the Algorithms Seminar, Le Chesnay-Rocquencourt, France."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Ishikawa, H. (2014, January 23\u201328). Higher-Order Clique Reduction without Auxiliary Variables. Proceedings of the CVPR, Columbus, OH, USA.","DOI":"10.1109\/CVPR.2014.177"},{"key":"ref_32","unstructured":"Tanburn, R., Lunt, O., and Dattani, N.S. (2015). Crushing runtimes in adiabatic quantum computation with Energy Landscape Manipulation (ELM): Application to Quantum Factoring. arXiv."},{"key":"ref_33","unstructured":"Tanburn, R., Okada, E., and Dattani, N. (2015). Reducing multi-qubit interactions in adiabatic quantum computation without adding auxiliary qubits. Part 1: The \u2019deduc-reduc\u2019 method and its application to quantum factorization of numbers. arXiv."},{"key":"ref_34","unstructured":"Okada, E., Tanburn, R., and Dattani, N.S. (2015). Reducing multi-qubit interactions in adiabatic quantum computation without adding auxiliary qubits. Part 2: The \u2019split-reduc\u2019 method and its application to quantum determination of Ramsey numbers. arXiv."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"100757","DOI":"10.1016\/j.disopt.2022.100757","article-title":"A polyhedral study of lifted multicuts","volume":"47","author":"Andres","year":"2023","journal-title":"Discret. Optim."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Arora, C., Banerjee, S., Kalra, P., and Maheshwari, S.N. (2012, January 7\u201313). Generic Cuts: An Efficient Algorithm for Optimal Inference in Higher Order MRF-MAP. Proceedings of the ECCV, Florence, Italy.","DOI":"10.1007\/978-3-642-33715-4_2"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1323","DOI":"10.1109\/TPAMI.2014.2388218","article-title":"Generalized Flows for Optimal Inference in Higher Order MRF-MAP","volume":"37","author":"Arora","year":"2015","journal-title":"IEEE TPAMI"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Shanu, I., Arora, C., and Maheshwari, S. (2018, January 18\u201322). Inference in Higher Order MRF-MAP Problems with Small and Large Cliques. Proceedings of the CVPR, Salt Lake City, UT, USA.","DOI":"10.1109\/CVPR.2018.00822"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Shanu, I., Bharti, S., Arora, C., and Maheshwari, S.N. (2020, January 23\u201328). An Inference Algorithm for Multi-label MRF-MAP Problems with Clique Size 100. Proceedings of the ECCV, Glasgow, UK.","DOI":"10.1007\/978-3-030-58565-5_16"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Kahl, F., and Strandmark, P. (2011, January 6\u201313). Generalized roof duality for pseudo-boolean optimization. Proceedings of the ICCV, Barcelona, Spain.","DOI":"10.1109\/ICCV.2011.6126250"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Kannan, H., Komodakis, N., and Paragios, N. (2017, January 21\u201326). Newton-Type Methods for Inference in Higher-Order Markov Random Fields. Proceedings of the CVPR, Honolulu, HI, USA.","DOI":"10.1109\/CVPR.2017.764"},{"key":"ref_42","unstructured":"Ke, C., and Honorio, J. (2023). Exact Inference in High-order Structured Prediction. arXiv."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/s10898-020-00972-2","article-title":"Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation","volume":"80","author":"Elloumi","year":"2021","journal-title":"J. Glob. Optim."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1568","DOI":"10.1109\/TPAMI.2006.200","article-title":"Convergent tree-reweighted message passing for energy minimization","volume":"28","author":"Kolmogorov","year":"2006","journal-title":"IEEE TPAMI"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1109\/TPAMI.2014.2363465","article-title":"A New Look at Reweighted Message Passing","volume":"37","author":"Kolmogorov","year":"2015","journal-title":"IEEE TPAMI"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Gallagher, A.C., Batra, D., and Parikh, D. (2011, January 20\u201325). Inference for order reduction in Markov random fields. Proceedings of the CVPR, Colorado Springs, CO, USA.","DOI":"10.1109\/CVPR.2011.5995452"},{"key":"ref_47","unstructured":"Roth, S., and Black, M.J. (2005, January 20\u201326). Fields of Experts: A framework for learning image priors. Proceedings of the CVPR, San Diego, CA, USA."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s11263-008-0197-6","article-title":"Fields of Experts","volume":"82","author":"Roth","year":"2009","journal-title":"IJCV"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"898","DOI":"10.1109\/TPAMI.2010.161","article-title":"Contour Detection and Hierarchical Image Segmentation","volume":"33","author":"Arbelaez","year":"2011","journal-title":"IEEE TPAMI"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/3\/535\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:59:37Z","timestamp":1760122777000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/25\/3\/535"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,20]]},"references-count":49,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["e25030535"],"URL":"https:\/\/doi.org\/10.3390\/e25030535","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2023,3,20]]}}}