{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/129837"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/129837","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Optimal graph learning","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-20 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-20 without embargo terms","abstract_has_math":false,"creators":["Xu, Zhe"],"institution":"University of Illinois Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Tong, Hanghang","Banerjee, Arindam","Chen, Yuzhong","Han, Jiawei"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-07-07","date_published":"2025-07-07","updated_at":"2026-07-22T22:25:05Z","subjects":["Graph Machine Learning","Graph Data Augmentation"],"languages":["en","eng"],"rights":["Copyright 2025 Zhe Xu"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/129837","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Tong, Hanghang","Banerjee, Arindam","Chen, Yuzhong","Han, Jiawei"]},{"key":"dc:creator","label":"Author","values":["Xu, Zhe"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2025-07-07","2025-08"]},{"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 Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph Machine Learning","Graph Data Augmentation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2025 Zhe Xu"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/129837"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-20 without embargo terms","The student, Zhe Xu, accepted the attached license on 2025-07-01 at 20:57.","The student, Zhe Xu, submitted this Dissertation for approval on 2025-07-01 at 21:12.","This Dissertation was approved for publication on 2025-07-07 at 12:37.","DSpace SAF Submission Ingestion Package generated from Vireo submission #22397 on 2025-10-20 at 16:57:24","The past decades have seen significant advancements in graph machine learning, with numerous sophisticated models and algorithms crafted for a variety of learning tasks, including ranking, classification, regression, and anomaly detection. Generally, most existing works focus on addressing the question: given a graph, what is the best way to mine it? Despite their remarkable achievements, little attention is paid to the graph data itself, which could be noisy, huge, and imbalanced at every stage of the data collection process. In this thesis, our focus is on the relatively unexplored realm of graph data, intending to enhance various downstream graph machine learning tasks. We term this line of research \"optimal graph learning\", aiming to identify the most effective graph data to improve efficiency, effectiveness, and expressiveness. However, some unique challenges arise. First (formulation), it is not clear how to formulate data optimization in a data-driven way, especially considering that the downstream tasks can be versatile. Second (volume), the sheer volume of graph datasets can result in significant time and space complexity for underlying optimization solutions. Third (pattern), capturing various essential graph patterns at different granularities presents a challenge. This thesis introduces our progress towards the optimal graph learning problem. Concretely, we categorize our work into three directions: graph refinement, graph augmentation, and graph distillation. For graph refinement, we developed (1) a pure data-driven solution named GaSoliNe against noisy data and (2) Stager, a solution tailored for addressing imbalanced data. For graph augmentation, we developed three augmentation solutions: (1) ALT, enhancing broad models' performance on graphs with arbitrary heterophily, (2) DisCo, which can generate realistic graphs based on the training graphs, and (3) AuGLM, which incorporates the graph structure into the textual input so that the language models can successfully handle the node classification task. For graph distillation, we developed (1) a bilevel optimization-based solution named KiDD to shrink the size of given graphs and, meanwhile, preserve the utility of training data and (2) graph rationale discovery framework named FIG, which can find the critical subgraph in every given graph to enhance the performance of graph-level performance. Collectively, these contributions establish foundational progress toward data-centric graph machine learning and demonstrate the value of optimizing graph data itself to improve downstream task performance."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Optimal graph learning"]}]}],"canonical_facts":{"dc:contributor":["Tong, Hanghang","Banerjee, Arindam","Chen, Yuzhong","Han, Jiawei"],"dc:creator":["Xu, Zhe"],"dc:date":["2025-07-07","2025-08"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-20 without embargo terms","The student, Zhe Xu, accepted the attached license on 2025-07-01 at 20:57.","The student, Zhe Xu, submitted this Dissertation for approval on 2025-07-01 at 21:12.","This Dissertation was approved for publication on 2025-07-07 at 12:37.","DSpace SAF Submission Ingestion Package generated from Vireo submission #22397 on 2025-10-20 at 16:57:24","The past decades have seen significant advancements in graph machine learning, with numerous sophisticated models and algorithms crafted for a variety of learning tasks, including ranking, classification, regression, and anomaly detection. Generally, most existing works focus on addressing the question: given a graph, what is the best way to mine it? Despite their remarkable achievements, little attention is paid to the graph data itself, which could be noisy, huge, and imbalanced at every stage of the data collection process. In this thesis, our focus is on the relatively unexplored realm of graph data, intending to enhance various downstream graph machine learning tasks. We term this line of research \"optimal graph learning\", aiming to identify the most effective graph data to improve efficiency, effectiveness, and expressiveness. However, some unique challenges arise. First (formulation), it is not clear how to formulate data optimization in a data-driven way, especially considering that the downstream tasks can be versatile. Second (volume), the sheer volume of graph datasets can result in significant time and space complexity for underlying optimization solutions. Third (pattern), capturing various essential graph patterns at different granularities presents a challenge. This thesis introduces our progress towards the optimal graph learning problem. Concretely, we categorize our work into three directions: graph refinement, graph augmentation, and graph distillation. For graph refinement, we developed (1) a pure data-driven solution named GaSoliNe against noisy data and (2) Stager, a solution tailored for addressing imbalanced data. For graph augmentation, we developed three augmentation solutions: (1) ALT, enhancing broad models' performance on graphs with arbitrary heterophily, (2) DisCo, which can generate realistic graphs based on the training graphs, and (3) AuGLM, which incorporates the graph structure into the textual input so that the language models can successfully handle the node classification task. For graph distillation, we developed (1) a bilevel optimization-based solution named KiDD to shrink the size of given graphs and, meanwhile, preserve the utility of training data and (2) graph rationale discovery framework named FIG, which can find the critical subgraph in every given graph to enhance the performance of graph-level performance. Collectively, these contributions establish foundational progress toward data-centric graph machine learning and demonstrate the value of optimizing graph data itself to improve downstream task performance."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/129837"],"dc:language":["en","eng"],"dc:rights":["Copyright 2025 Zhe Xu"],"dc:subject":["Graph Machine Learning","Graph Data Augmentation"],"dc:title":["Optimal graph learning"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:05Z"}