{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/49470"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/49470","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Lifted probabilistic relational inference for uncertain networks","abstract":"Probabilistic Relational Graphical Model (PRGM) is a popular tool for modeling uncertain relational knowledge, of which the set of uncertain relational knowledge is usually assumed to be independent with the domain of the application. One common application of PRGM is to model complex networks using structural features. Efficient and accurate inference algorithms that can handle models with non-trivial structural features (e.g., transitive relations) are important for applications of this kind. In this thesis, (1) we provide new algorithm for efficient and accurate inference on PRGMs with structural features; (2) we show a counter example to the domain-independence assumption of PRGM. A PRGM is a set of uncertain relational knowledge, which translates to Probabilistic Graphical Models (PGM) on different domains of discourse. Lifted inference and domain-independence assumption are two important concepts for PRGM. Domain-independence assumption separates the uncertain relational knowledge of a PRGM from its domains of application, therefore distinguishes PRGM from propositional PGM. Lifted inference techniques try to speedup inference on PRGM by lifting the computation from propositional level to relational level. However, these techniques are not designed to handle complex structural features, therefore lack efficiency and accuracy in the presence of these features. In this thesis, we propose a deterministic approximate inference algorithm for Exponential Random Graph Model (ERGM) -- a family of statistical models, which are closely related to PRGM. An ERGM defines a probabilistic distribution of all graphs of $n$ nodes using a set of subgraph statistics. The main insight enabling this advance is that subgraph statistics are sufficient to derive a lower bound for partition functions of ERGM when the model of interests is not dominated by a few graphs. We then show that a class of PRGMs with structural features can be converted to ERGM, which leads to an approximate lifted inference algorithm for PRGM. Theoretical and experimental results show that the proposed algorithms are scalable, stable, and precise enough for inference tasks. Lastly, we show a counter example of the domain-independence assumption. In general, PRGM parameters fitted to one network data cannot be extrapolated to other networks of different sizes.","abstract_html":"Probabilistic Relational Graphical Model (PRGM) is a popular tool for modeling uncertain relational knowledge, of which the set of uncertain relational knowledge is usually assumed to be independent with the domain of the application. One common application of PRGM is to model complex networks using structural features. Efficient and accurate inference algorithms that can handle models with non-trivial structural features (e.g., transitive relations) are important for applications of this kind. In this thesis, (1) we provide new algorithm for efficient and accurate inference on PRGMs with structural features; (2) we show a counter example to the domain-independence assumption of PRGM. A PRGM is a set of uncertain relational knowledge, which translates to Probabilistic Graphical Models (PGM) on different domains of discourse. Lifted inference and domain-independence assumption are two important concepts for PRGM. Domain-independence assumption separates the uncertain relational knowledge of a PRGM from its domains of application, therefore distinguishes PRGM from propositional PGM. Lifted inference techniques try to speedup inference on PRGM by lifting the computation from propositional level to relational level. However, these techniques are not designed to handle complex structural features, therefore lack efficiency and accuracy in the presence of these features. In this thesis, we propose a deterministic approximate inference algorithm for Exponential Random Graph Model (ERGM) -- a family of statistical models, which are closely related to PRGM. An ERGM defines a probabilistic distribution of all graphs of $n$ nodes using a set of subgraph statistics. The main insight enabling this advance is that subgraph statistics are sufficient to derive a lower bound for partition functions of ERGM when the model of interests is not dominated by a few graphs. We then show that a class of PRGMs with structural features can be converted to ERGM, which leads to an approximate lifted inference algorithm for PRGM. Theoretical and experimental results show that the proposed algorithms are scalable, stable, and precise enough for inference tasks. Lastly, we show a counter example of the domain-independence assumption. In general, PRGM parameters fitted to one network data cannot be extrapolated to other networks of different sizes.","abstract_has_math":true,"creators":["Pu, Wen"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Amir, Eyal","Roth, Dan","DeJong, Gerald F.","Hunter, David"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-05-30T16:45:54Z","date_published":"2014-05-30T16:45:54Z","updated_at":"2026-07-22T22:25:38Z","subjects":["Exponential Random Graph Model","Markov Logic Network","Lifted Inference","Approximate Probabilistic Inference"],"languages":["en"],"rights":["Copyright 2014 Wen Pu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/49470","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Amir, Eyal","Roth, Dan","DeJong, Gerald F.","Hunter, David"]},{"key":"dc:creator","label":"Author","values":["Pu, Wen"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-05-30T16:45:54Z","2014-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"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":["Exponential Random Graph Model","Markov Logic Network","Lifted Inference","Approximate Probabilistic Inference"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2014 Wen Pu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/49470"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Probabilistic Relational Graphical Model (PRGM) is a popular tool for modeling uncertain relational knowledge, of which the set of uncertain relational knowledge is usually assumed to be independent with the domain of the application. One common application of PRGM is to model complex networks using structural features. Efficient and accurate inference algorithms that can handle models with non-trivial structural features (e.g., transitive relations) are important for applications of this kind. In this thesis, (1) we provide new algorithm for efficient and accurate inference on PRGMs with structural features; (2) we show a counter example to the domain-independence assumption of PRGM. A PRGM is a set of uncertain relational knowledge, which translates to Probabilistic Graphical Models (PGM) on different domains of discourse. Lifted inference and domain-independence assumption are two important concepts for PRGM. Domain-independence assumption separates the uncertain relational knowledge of a PRGM from its domains of application, therefore distinguishes PRGM from propositional PGM. Lifted inference techniques try to speedup inference on PRGM by lifting the computation from propositional level to relational level. However, these techniques are not designed to handle complex structural features, therefore lack efficiency and accuracy in the presence of these features. In this thesis, we propose a deterministic approximate inference algorithm for Exponential Random Graph Model (ERGM) -- a family of statistical models, which are closely related to PRGM. An ERGM defines a probabilistic distribution of all graphs of $n$ nodes using a set of subgraph statistics. The main insight enabling this advance is that subgraph statistics are sufficient to derive a lower bound for partition functions of ERGM when the model of interests is not dominated by a few graphs. We then show that a class of PRGMs with structural features can be converted to ERGM, which leads to an approximate lifted inference algorithm for PRGM. Theoretical and experimental results show that the proposed algorithms are scalable, stable, and precise enough for inference tasks. Lastly, we show a counter example of the domain-independence assumption. In general, PRGM parameters fitted to one network data cannot be extrapolated to other networks of different sizes.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2014-04-23T14:55:36Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Pu_Wen.pdf: 181821 bytes, checksum: 4a6b85904bda8a32ab2781a0e15727fa (MD5) Pu_Wen.pdf: 785457 bytes, checksum: bd92e01044a81bf36b55b148fdac2fae (MD5)","Made available in DSpace on 2014-05-30T16:45:54Z (GMT). No. of bitstreams: 2 Wen_Pu.pdf: 785539 bytes, checksum: cd44b11b62919501a1ea150564197c90 (MD5) license.txt: 4054 bytes, checksum: 85d657bd876d82660870c3b19bfea12f (MD5)"]},{"key":"dc:title","label":"Title","values":["Lifted probabilistic relational inference for uncertain networks"]}]}],"canonical_facts":{"dc:contributor":["Amir, Eyal","Roth, Dan","DeJong, Gerald F.","Hunter, David"],"dc:creator":["Pu, Wen"],"dc:date":["2014-05-30T16:45:54Z","2014-05"],"dc:description":["Probabilistic Relational Graphical Model (PRGM) is a popular tool for modeling uncertain relational knowledge, of which the set of uncertain relational knowledge is usually assumed to be independent with the domain of the application. One common application of PRGM is to model complex networks using structural features. Efficient and accurate inference algorithms that can handle models with non-trivial structural features (e.g., transitive relations) are important for applications of this kind. In this thesis, (1) we provide new algorithm for efficient and accurate inference on PRGMs with structural features; (2) we show a counter example to the domain-independence assumption of PRGM. A PRGM is a set of uncertain relational knowledge, which translates to Probabilistic Graphical Models (PGM) on different domains of discourse. Lifted inference and domain-independence assumption are two important concepts for PRGM. Domain-independence assumption separates the uncertain relational knowledge of a PRGM from its domains of application, therefore distinguishes PRGM from propositional PGM. Lifted inference techniques try to speedup inference on PRGM by lifting the computation from propositional level to relational level. However, these techniques are not designed to handle complex structural features, therefore lack efficiency and accuracy in the presence of these features. In this thesis, we propose a deterministic approximate inference algorithm for Exponential Random Graph Model (ERGM) -- a family of statistical models, which are closely related to PRGM. An ERGM defines a probabilistic distribution of all graphs of $n$ nodes using a set of subgraph statistics. The main insight enabling this advance is that subgraph statistics are sufficient to derive a lower bound for partition functions of ERGM when the model of interests is not dominated by a few graphs. We then show that a class of PRGMs with structural features can be converted to ERGM, which leads to an approximate lifted inference algorithm for PRGM. Theoretical and experimental results show that the proposed algorithms are scalable, stable, and precise enough for inference tasks. Lastly, we show a counter example of the domain-independence assumption. In general, PRGM parameters fitted to one network data cannot be extrapolated to other networks of different sizes.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2014-04-23T14:55:36Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 2 Pu_Wen.pdf: 181821 bytes, checksum: 4a6b85904bda8a32ab2781a0e15727fa (MD5) Pu_Wen.pdf: 785457 bytes, checksum: bd92e01044a81bf36b55b148fdac2fae (MD5)","Made available in DSpace on 2014-05-30T16:45:54Z (GMT). No. of bitstreams: 2 Wen_Pu.pdf: 785539 bytes, checksum: cd44b11b62919501a1ea150564197c90 (MD5) license.txt: 4054 bytes, checksum: 85d657bd876d82660870c3b19bfea12f (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/49470"],"dc:language":["en"],"dc:rights":["Copyright 2014 Wen Pu"],"dc:subject":["Exponential Random Graph Model","Markov Logic Network","Lifted Inference","Approximate Probabilistic Inference"],"dc:title":["Lifted probabilistic relational inference for uncertain networks"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:38Z"}