{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/117770"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/117770","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Learning on graphs: from theory to practice","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-04-12 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-04-12 without embargo terms","abstract_has_math":false,"creators":["Chien, I"],"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","Hajek, Bruce","Raginsky, Maxim","Schwing, Alexander","Li, Pan"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-12","date_published":"2022-12","updated_at":"2026-07-22T22:24:56Z","subjects":["Graphs","Machine Learning","Graph Neural Networks"],"languages":["en","eng"],"rights":["Copyright 2022 I Chien"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/117770","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Milenkovic, Olgica","Hajek, Bruce","Raginsky, Maxim","Schwing, Alexander","Li, Pan"]},{"key":"dc:creator","label":"Author","values":["Chien, I"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-12","2022-11-23"]},{"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":["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":["Graphs","Machine Learning","Graph Neural Networks"]}]},{"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 2022 I Chien"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/117770"]}]},{"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 2023-04-12 without embargo terms","The student, I Chien, accepted the attached license on 2022-11-21 at 14:50.","The student, I Chien, submitted this Dissertation for approval on 2022-11-21 at 15:00.","This Dissertation was approved for publication on 2022-11-23 at 13:48.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18609 on 2023-04-12 at 07:29:24","Learning on graphs has raised massive attention in the machine-learning community due to various real-world applications. Random walks on graphs, or say graph propagation, have been one of the most popular core ideas in many graph-learning methods. Examples range from classical methods such as PageRank and label propagation to graph convolution and message-passing mechanisms in Graph Neural Networks (GNNs). While there are plenty of graph learning problems such as link predictions and graph classifications, we mainly focus on node-level tasks such as seed-expansion community detection and node classification problems. These tasks aim to recover the underlying node labels (communities) based on an input graph and potentially with node features and attributes. We propose a series of innovative graph-learning methods and relevant analysis for the node-level tasks. We first study the Generalized PageRank (GPR) method, which unifies many PageRank variants as its special cases via different choices of GPR weights. These include Personalized PageRank (PPR), Heat-kernel PageRank (HPR) and many others. Despite the expressiveness of GPR, previous works in the area have mostly focused on evaluating suitable GPR weights. Only a few studies have attempted to determine the optimal weights of GPR for a given application. We take a step forward in this direction by analyzing the behavior of GPR on random graph models such as stochastic block models. We provide non-asymptotic analysis for GPR which characterizes its first and second moments. Based on our analysis, we propose a new GPR termed Inverse PR (IPR). We demonstrate the superiority of IPR compared to other GPRs via extensive experiments on seed-expansion community detection tasks. We next address two fundamental issues in GNNs, namely lacking universality and the over-smoothing problem. Here, universality refers to independence on homophily and heterophily graph assumptions. We address these issues by introducing a novel GPR-GNN architecture that adaptively learns the GPR weights so as to jointly optimize node feature and topological information extraction. We show that learned GPR weights can automatically adjust to the node label pattern, no matter if it is homophilic or heterophilic. Thus, GPR-GNN is a universal graph learning model. We further show that learning GPR weights allows one to prevent feature over-smoothing, a process that renders feature information nondiscriminative, without containing the depth of the model. Our theoretical analysis rigorously validates on not only real-world datasets but also the novel synthetic benchmark datasets generated by the contextual stochastic block model. Finally, we observe that the standard GNN pipeline requires input data consisting of an input graph and \\emph{numerical} node features for node classification tasks. However, we have only raw node attributes such as text, images and audio in many real-world applications. The common way of obtaining \\emph{numerical} node features from raw data is applying \\emph{graph agnostic} methods for node feature extraction. Notably, recent works exploring the correlation between numerical node features and graph structure via self-supervised learning have paved the way for further performance improvement of GNNs. Under this viewpoint, leveraging \\emph{graph agnostic} node feature extraction methods is suboptimal, as they prevent one from fully utilizing potential correlations between node attributes and graph topology. We propose Graph Information Aided Node feature exTraction (GIANT) to mitigate this issue. Our first contribution is the proposal of a new graph self-supervised learning task named \\emph{neighborhood prediction}. We show that our neighborhood prediction task is universal and related to the eXtreme Multilabel Classification (XMC) problem. Based on this connection to XMC, we leverage the state-of-the-art XMC solver to fine-tune the language model based on graph information and scales to large datasets. GIANT achieves new state-of-the-art results for the node classification task on large-scale datasets that contains more than $100$ million of nodes with significant gain."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Learning on graphs: from theory to practice"]}]}],"canonical_facts":{"dc:contributor":["Milenkovic, Olgica","Hajek, Bruce","Raginsky, Maxim","Schwing, Alexander","Li, Pan"],"dc:creator":["Chien, I"],"dc:date":["2022-12","2022-11-23"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2023-04-12 without embargo terms","The student, I Chien, accepted the attached license on 2022-11-21 at 14:50.","The student, I Chien, submitted this Dissertation for approval on 2022-11-21 at 15:00.","This Dissertation was approved for publication on 2022-11-23 at 13:48.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18609 on 2023-04-12 at 07:29:24","Learning on graphs has raised massive attention in the machine-learning community due to various real-world applications. Random walks on graphs, or say graph propagation, have been one of the most popular core ideas in many graph-learning methods. Examples range from classical methods such as PageRank and label propagation to graph convolution and message-passing mechanisms in Graph Neural Networks (GNNs). While there are plenty of graph learning problems such as link predictions and graph classifications, we mainly focus on node-level tasks such as seed-expansion community detection and node classification problems. These tasks aim to recover the underlying node labels (communities) based on an input graph and potentially with node features and attributes. We propose a series of innovative graph-learning methods and relevant analysis for the node-level tasks. We first study the Generalized PageRank (GPR) method, which unifies many PageRank variants as its special cases via different choices of GPR weights. These include Personalized PageRank (PPR), Heat-kernel PageRank (HPR) and many others. Despite the expressiveness of GPR, previous works in the area have mostly focused on evaluating suitable GPR weights. Only a few studies have attempted to determine the optimal weights of GPR for a given application. We take a step forward in this direction by analyzing the behavior of GPR on random graph models such as stochastic block models. We provide non-asymptotic analysis for GPR which characterizes its first and second moments. Based on our analysis, we propose a new GPR termed Inverse PR (IPR). We demonstrate the superiority of IPR compared to other GPRs via extensive experiments on seed-expansion community detection tasks. We next address two fundamental issues in GNNs, namely lacking universality and the over-smoothing problem. Here, universality refers to independence on homophily and heterophily graph assumptions. We address these issues by introducing a novel GPR-GNN architecture that adaptively learns the GPR weights so as to jointly optimize node feature and topological information extraction. We show that learned GPR weights can automatically adjust to the node label pattern, no matter if it is homophilic or heterophilic. Thus, GPR-GNN is a universal graph learning model. We further show that learning GPR weights allows one to prevent feature over-smoothing, a process that renders feature information nondiscriminative, without containing the depth of the model. Our theoretical analysis rigorously validates on not only real-world datasets but also the novel synthetic benchmark datasets generated by the contextual stochastic block model. Finally, we observe that the standard GNN pipeline requires input data consisting of an input graph and \\emph{numerical} node features for node classification tasks. However, we have only raw node attributes such as text, images and audio in many real-world applications. The common way of obtaining \\emph{numerical} node features from raw data is applying \\emph{graph agnostic} methods for node feature extraction. Notably, recent works exploring the correlation between numerical node features and graph structure via self-supervised learning have paved the way for further performance improvement of GNNs. Under this viewpoint, leveraging \\emph{graph agnostic} node feature extraction methods is suboptimal, as they prevent one from fully utilizing potential correlations between node attributes and graph topology. We propose Graph Information Aided Node feature exTraction (GIANT) to mitigate this issue. Our first contribution is the proposal of a new graph self-supervised learning task named \\emph{neighborhood prediction}. We show that our neighborhood prediction task is universal and related to the eXtreme Multilabel Classification (XMC) problem. Based on this connection to XMC, we leverage the state-of-the-art XMC solver to fine-tune the language model based on graph information and scales to large datasets. GIANT achieves new state-of-the-art results for the node classification task on large-scale datasets that contains more than $100$ million of nodes with significant gain."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/117770"],"dc:language":["en","eng"],"dc:rights":["Copyright 2022 I Chien"],"dc:subject":["Graphs","Machine Learning","Graph Neural Networks"],"dc:title":["Learning on graphs: from theory to practice"],"dc:type":["text","Thesis"],"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:56Z"}