{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/105596"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/105596","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Learning on graphs with high-order relations: spectral methods, optimization and applications","abstract":"DSpace SAF Submission Ingestion Package generated from Vireo submission #14022 on 2019-11-26 at 12:49:35","abstract_html":"DSpace SAF Submission Ingestion Package generated from Vireo submission #14022 on 2019-11-26 at 12:49:35","abstract_has_math":false,"creators":["Li, Pan"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Milenkovic, Olgica","Han, Jiawei","Hajek, Bruce","He, Niao","Gleich, David"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019-11-26T20:33:38Z","date_published":"2019-11-26T20:33:38Z","updated_at":"2026-07-22T22:24:44Z","subjects":["hypergraph","spectral clustering","submodular function","Lovasz extension","semi-supervised learning","PageRank"],"languages":["en"],"rights":["Copyright 2019 Pan Li"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/105596","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Milenkovic, Olgica","Han, Jiawei","Hajek, Bruce","He, Niao","Gleich, David"]},{"key":"dc:creator","label":"Author","values":["Li, Pan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2019-11-26T20:33:38Z","2019-06-11","2019-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"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":["hypergraph","spectral clustering","submodular function","Lovasz extension","semi-supervised learning","PageRank"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2019 Pan Li"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/105596"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["DSpace SAF Submission Ingestion Package generated from Vireo submission #14022 on 2019-11-26 at 12:49:35","Learning on graphs is an important problem in machine learning, computer vision and data mining. Traditional algorithms for learning on graphs primarily take into account only low-order connectivity patterns described at the level of individual vertices and edges. However, in many applications, high-order relations among vertices are necessary to properly model a real-life problem. In contrast to the low-order cases, in-depth algorithmic and analytic studies supporting high-order relations among vertices are still lacking. To address this problem, we introduce a new mathematical model family, termed inhomogeneous hypergraphs, which captures the high-order relations among vertices in a very extensive and flexible way. Specifically, as opposed to classic hypergraphs that treat vertices within a high-order structure in a uniform manner, inhomogeneous hypergraphs allow one to model the fact that different subsets of vertices within a high-order relation may have different structural importance. We propose a series of algorithms and relevant analytic results for this new model. First, after we introduce the formal definitions and some preliminaries, we propose clustering algorithms over inhomogeneous hypergraphs. The first clustering method is based on a projection method, where we use graphs with pairwise relations to approximate high-order relations and then directly use spectral clustering methods over obtained graphs. For this type of method, we provide provable performance guarantee, which works for a sub-class of inhomogeneous hypergraphs that additionally impose constraints on the internal structures of high-order relations. Such constraints are related to submodular functions, so we term such a sub-class of inhomogeneous hypergraphs as submodular hypergraphs. Later, we study the Laplacian operators for these hypergraphs and generalize many important results in spectral theory for this setting including Cheeger's inequalities and discrete nodal domain theorems. Based on these new results, we further develop new clustering algorithms with tighter approximating properties than projection methods. Second, we propose some optimization algorithms for inhomogeneous hypergraphs. We first find that min-cut problems over submodular hypergraphs are closely related to an extensively studied optimization problem termed decomposable submodular hypergraph minimization (DSFM). Our contribution is how to leverage hypergraph structures to accelerate canonical solvers for DSFM problems. Later, we connect PageRank approaches to submodular hypergraphs and propose a new optimization problem termed quadratic decomposable submodular hypergraph minimization (QDSFM). For this new problem, we propose algorithms with first provable linear convergence guarantee and identify new relevant applications.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2019-11-26 without embargo terms","The student, Pan Li, accepted the attached license on 2019-06-08 at 01:41.","The student, Pan Li, submitted this Dissertation for approval on 2019-06-08 at 01:49.","This Dissertation was approved for publication on 2019-06-11 at 10:01.","Made available in DSpace on 2019-11-26T20:33:38Z (GMT). No. of bitstreams: 3 LI-DISSERTATION-2019.pdf: 2385927 bytes, checksum: e6449676014d40839212a61a7206984a (MD5) LICENSE.txt: 4203 bytes, checksum: 37cd6fa7dc12e3d6bd5bb071b574a229 (MD5) PROQUEST_LICENSE.txt: 4549 bytes, checksum: 4c97c0b47416a4c17c3f6434d468733b (MD5) Previous issue date: 2019-06-11"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Learning on graphs with high-order relations: spectral methods, optimization and applications"]}]}],"canonical_facts":{"dc:contributor":["Milenkovic, Olgica","Han, Jiawei","Hajek, Bruce","He, Niao","Gleich, David"],"dc:creator":["Li, Pan"],"dc:date":["2019-11-26T20:33:38Z","2019-06-11","2019-08"],"dc:description":["DSpace SAF Submission Ingestion Package generated from Vireo submission #14022 on 2019-11-26 at 12:49:35","Learning on graphs is an important problem in machine learning, computer vision and data mining. Traditional algorithms for learning on graphs primarily take into account only low-order connectivity patterns described at the level of individual vertices and edges. However, in many applications, high-order relations among vertices are necessary to properly model a real-life problem. In contrast to the low-order cases, in-depth algorithmic and analytic studies supporting high-order relations among vertices are still lacking. To address this problem, we introduce a new mathematical model family, termed inhomogeneous hypergraphs, which captures the high-order relations among vertices in a very extensive and flexible way. Specifically, as opposed to classic hypergraphs that treat vertices within a high-order structure in a uniform manner, inhomogeneous hypergraphs allow one to model the fact that different subsets of vertices within a high-order relation may have different structural importance. We propose a series of algorithms and relevant analytic results for this new model. First, after we introduce the formal definitions and some preliminaries, we propose clustering algorithms over inhomogeneous hypergraphs. The first clustering method is based on a projection method, where we use graphs with pairwise relations to approximate high-order relations and then directly use spectral clustering methods over obtained graphs. For this type of method, we provide provable performance guarantee, which works for a sub-class of inhomogeneous hypergraphs that additionally impose constraints on the internal structures of high-order relations. Such constraints are related to submodular functions, so we term such a sub-class of inhomogeneous hypergraphs as submodular hypergraphs. Later, we study the Laplacian operators for these hypergraphs and generalize many important results in spectral theory for this setting including Cheeger's inequalities and discrete nodal domain theorems. Based on these new results, we further develop new clustering algorithms with tighter approximating properties than projection methods. Second, we propose some optimization algorithms for inhomogeneous hypergraphs. We first find that min-cut problems over submodular hypergraphs are closely related to an extensively studied optimization problem termed decomposable submodular hypergraph minimization (DSFM). Our contribution is how to leverage hypergraph structures to accelerate canonical solvers for DSFM problems. Later, we connect PageRank approaches to submodular hypergraphs and propose a new optimization problem termed quadratic decomposable submodular hypergraph minimization (QDSFM). For this new problem, we propose algorithms with first provable linear convergence guarantee and identify new relevant applications.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2019-11-26 without embargo terms","The student, Pan Li, accepted the attached license on 2019-06-08 at 01:41.","The student, Pan Li, submitted this Dissertation for approval on 2019-06-08 at 01:49.","This Dissertation was approved for publication on 2019-06-11 at 10:01.","Made available in DSpace on 2019-11-26T20:33:38Z (GMT). No. of bitstreams: 3 LI-DISSERTATION-2019.pdf: 2385927 bytes, checksum: e6449676014d40839212a61a7206984a (MD5) LICENSE.txt: 4203 bytes, checksum: 37cd6fa7dc12e3d6bd5bb071b574a229 (MD5) PROQUEST_LICENSE.txt: 4549 bytes, checksum: 4c97c0b47416a4c17c3f6434d468733b (MD5) Previous issue date: 2019-06-11"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/105596"],"dc:language":["en"],"dc:rights":["Copyright 2019 Pan Li"],"dc:subject":["hypergraph","spectral clustering","submodular function","Lovasz extension","semi-supervised learning","PageRank"],"dc:title":["Learning on graphs with high-order relations: spectral methods, optimization and applications"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:44Z"}