{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/113092"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/113092","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Inference in Ising models by graph neural networks with structural features","abstract":"Probabilistic graphical models (PGMs) are powerful frameworks for modeling interactions between random variables. The two major inference tasks on PGMs are marginal probability inference and maximum-a-posteriori (MAP) inference. Exact inference on PGMs is intractable, hence approximation algorithms, such as belief propagation, are proposed for practical applications. Recently Graphical Neural Networks (GNNs) are shown to outperform BP on small-scale loopy graphs. GNN computes a more general function on each node using neural networks, and learns the exact distribution of small loop-free and loopy graphs. As BP is exact on loop-free graphs and graphs with exactly one loop, GNN performs worse than BP on these graphs, but outperforms BP on graphs with more loops as BP’s performance degrades. We propose a simplified GNN architecture, GNN-Mimic-BP, which outperforms GNN by orders of magnitude on loop-free graphs. In fact, with the simplification, GNN-Mimic-BP enables the architecture to mimic BP exactly on loop-free graphs. We then combine the simplified architecture with enhanced information of short loops in the graph. The resulting architecture outperforms the original GNN on both classic graphs ranging from loop-free to complete, as well as random graphs with a wide range of edge density.","abstract_html":"Probabilistic graphical models (PGMs) are powerful frameworks for modeling interactions between random variables. The two major inference tasks on PGMs are marginal probability inference and maximum-a-posteriori (MAP) inference. Exact inference on PGMs is intractable, hence approximation algorithms, such as belief propagation, are proposed for practical applications. Recently Graphical Neural Networks (GNNs) are shown to outperform BP on small-scale loopy graphs. GNN computes a more general function on each node using neural networks, and learns the exact distribution of small loop-free and loopy graphs. As BP is exact on loop-free graphs and graphs with exactly one loop, GNN performs worse than BP on these graphs, but outperforms BP on graphs with more loops as BP’s performance degrades. We propose a simplified GNN architecture, GNN-Mimic-BP, which outperforms GNN by orders of magnitude on loop-free graphs. In fact, with the simplification, GNN-Mimic-BP enables the architecture to mimic BP exactly on loop-free graphs. We then combine the simplified architecture with enhanced information of short loops in the graph. The resulting architecture outperforms the original GNN on both classic graphs ranging from loop-free to complete, as well as random graphs with a wide range of edge density.","abstract_has_math":false,"creators":["Huynh, Hieu Tri"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Lu, Yi"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-08","date_published":"2021-08","updated_at":"2026-07-22T22:24:53Z","subjects":["Inference, Probabilistic graphical models, Graph neural networks"],"languages":["en"],"rights":["Copyright 2021 Hieu Huynh"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/113092","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Lu, Yi"]},{"key":"dc:creator","label":"Author","values":["Huynh, Hieu Tri"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021-08","2022-01-12T21:47:00Z","2021-07-22"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Inference, Probabilistic graphical models, Graph neural networks"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Hieu Huynh"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/113092"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Probabilistic graphical models (PGMs) are powerful frameworks for modeling interactions between random variables. The two major inference tasks on PGMs are marginal probability inference and maximum-a-posteriori (MAP) inference. Exact inference on PGMs is intractable, hence approximation algorithms, such as belief propagation, are proposed for practical applications. Recently Graphical Neural Networks (GNNs) are shown to outperform BP on small-scale loopy graphs. GNN computes a more general function on each node using neural networks, and learns the exact distribution of small loop-free and loopy graphs. As BP is exact on loop-free graphs and graphs with exactly one loop, GNN performs worse than BP on these graphs, but outperforms BP on graphs with more loops as BP’s performance degrades. We propose a simplified GNN architecture, GNN-Mimic-BP, which outperforms GNN by orders of magnitude on loop-free graphs. In fact, with the simplification, GNN-Mimic-BP enables the architecture to mimic BP exactly on loop-free graphs. We then combine the simplified architecture with enhanced information of short loops in the graph. The resulting architecture outperforms the original GNN on both classic graphs ranging from loop-free to complete, as well as random graphs with a wide range of edge density.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-01-12 without embargo terms","The student, Hieu Huynh, accepted the attached license on 2021-07-21 at 18:42.","The student, Hieu Huynh, submitted this Thesis for approval on 2021-07-21 at 19:38.","This Thesis was approved for publication on 2021-07-22 at 09:33.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17057 on 2022-01-12 at 12:46:39","Made available in DSpace on 2022-01-12T21:47:00Z (GMT). No. of bitstreams: 2 HUYNH-THESIS-2021.pdf: 460971 bytes, checksum: 15fd97054ff30a751bb8cef66a915178 (MD5) LICENSE.txt: 4207 bytes, checksum: 5e21c1077615c507e32fdd64ab8c9403 (MD5) Previous issue date: 2021-07-22"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Inference in Ising models by graph neural networks with structural features"]}]}],"canonical_facts":{"dc:contributor":["Lu, Yi"],"dc:creator":["Huynh, Hieu Tri"],"dc:date":["2021-08","2022-01-12T21:47:00Z","2021-07-22"],"dc:description":["Probabilistic graphical models (PGMs) are powerful frameworks for modeling interactions between random variables. The two major inference tasks on PGMs are marginal probability inference and maximum-a-posteriori (MAP) inference. Exact inference on PGMs is intractable, hence approximation algorithms, such as belief propagation, are proposed for practical applications. Recently Graphical Neural Networks (GNNs) are shown to outperform BP on small-scale loopy graphs. GNN computes a more general function on each node using neural networks, and learns the exact distribution of small loop-free and loopy graphs. As BP is exact on loop-free graphs and graphs with exactly one loop, GNN performs worse than BP on these graphs, but outperforms BP on graphs with more loops as BP’s performance degrades. We propose a simplified GNN architecture, GNN-Mimic-BP, which outperforms GNN by orders of magnitude on loop-free graphs. In fact, with the simplification, GNN-Mimic-BP enables the architecture to mimic BP exactly on loop-free graphs. We then combine the simplified architecture with enhanced information of short loops in the graph. The resulting architecture outperforms the original GNN on both classic graphs ranging from loop-free to complete, as well as random graphs with a wide range of edge density.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-01-12 without embargo terms","The student, Hieu Huynh, accepted the attached license on 2021-07-21 at 18:42.","The student, Hieu Huynh, submitted this Thesis for approval on 2021-07-21 at 19:38.","This Thesis was approved for publication on 2021-07-22 at 09:33.","DSpace SAF Submission Ingestion Package generated from Vireo submission #17057 on 2022-01-12 at 12:46:39","Made available in DSpace on 2022-01-12T21:47:00Z (GMT). No. of bitstreams: 2 HUYNH-THESIS-2021.pdf: 460971 bytes, checksum: 15fd97054ff30a751bb8cef66a915178 (MD5) LICENSE.txt: 4207 bytes, checksum: 5e21c1077615c507e32fdd64ab8c9403 (MD5) Previous issue date: 2021-07-22"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/113092"],"dc:language":["en"],"dc:rights":["Copyright 2021 Hieu Huynh"],"dc:subject":["Inference, Probabilistic graphical models, Graph neural networks"],"dc:title":["Inference in Ising models by graph neural networks with structural features"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:53Z"}