서브메뉴
검색
Accurate and Efficient Representation Learning on Large-Scale Graphs
Accurate and Efficient Representation Learning on Large-Scale Graphs
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20250211151121
- ISBN
- 9798382840352
- DDC
- 004
- 저자명
- Deng, Chenhui.
- 서명/저자
- Accurate and Efficient Representation Learning on Large-Scale Graphs
- 발행사항
- [Sl] : Cornell University, 2024
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2024
- 형태사항
- 203 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 85-12, Section: B.
- 주기사항
- Advisor: Zhang, Zhiru.
- 학위논문주기
- Thesis (Ph.D.)--Cornell University, 2024.
- 초록/해제
- 요약Recent years have witnessed a surge of interest in representation learning on graph-structured data, which are pervasive in diverse real-world domains, spanning fundamental physical interactions, biological systems, social networks, and logic circuits. However, there is a strong tension between the accuracy and efficiency of existing graph representation learning (GRL) models. Firstly, many real-world graphs (e.g. social networks and logic circuits) are notably large, comprising millions or even billions of nodes and edges, which poses a substantial challenge on model efficiency for training and deployment. Additionally, different domains have complex and diverse graph structures, which are also exposed to adversarial attacks that perturb graph topology via adding or removing nodes and edges. These graph properties necessitate sophisticated model architectures to produce high-quality graph representations, which often come with nontrivial computation cost and memory usage.In this dissertation, we present research solutions that cover scalable, hardware-friendly, expressive, and robust GRL models for accurate and efficient representation learning on large-scale graph applications. We firstly propose GraphZoom, a multi-level approach for fast and accurate GRL. GraphZoom leverages lightweight algorithms that iteratively reduce graph size for GRL and progressively refine graph representations with theoretical guarantees based upon spectral graph theory. This results in a 40.8x training speedup over prior arts with comparable or even better accuracy. Secondly, we develop HOGA for scalable and generalizable GRL on large-scale circuits, via adopting a hop-wise graph attention scheme. HOGA not only outperforms prior GRL models on challenging circuit problems, but is also friendly to distributed training by mitigating communication overhead caused by graph dependencies. This renders HOGA applicable to industrial-scale circuit applications. Thirdly, we introduce Polynormer, an expressive graph transformer model with linear complexity. We theoretically demonstrate the superior expressivity of Polynormer through the lens of polynomial functions. Our extensive experiments indicate that Polynormer not only achieves state-of-the-art results across a wide variety of mainstream graph datasets, but also outperforms a popular baseline model by 31.8% on an industrial-scale dataset provided by Google for predicting AI model runtime on TPU. Last but not least, we propose an efficient graph topology learning approach called GARNET for accurate GRL under graph adversarial attacks. We theoretically show that GARNET can effectively recover critical structures from an adversarial graph with nearly-linear complexity. This leads to an accuracy improvement of up to 10.23% over previous robust GRL models on a broad range of adversarial graphs.
- 일반주제명
- Computer science
- 일반주제명
- Computer engineering
- 일반주제명
- Electrical engineering
- 기타저자
- Cornell University Electrical and Computer Engineering
- 기본자료저록
- Dissertations Abstracts International. 85-12B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008250123s2024 us c eng d■001000017160815
■00520250211151121
■006m o d
■007cr#unu||||||||
■020 ▼a9798382840352
■035 ▼a(MiAaPQ)AAI31146412
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a004
■1001 ▼aDeng, Chenhui.▼0(orcid)0009-0006-6482-5855
■24510▼aAccurate and Efficient Representation Learning on Large-Scale Graphs
■260 ▼a[Sl]▼bCornell University▼c2024
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2024
■300 ▼a203 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 85-12, Section: B.
■500 ▼aAdvisor: Zhang, Zhiru.
■5021 ▼aThesis (Ph.D.)--Cornell University, 2024.
■520 ▼aRecent years have witnessed a surge of interest in representation learning on graph-structured data, which are pervasive in diverse real-world domains, spanning fundamental physical interactions, biological systems, social networks, and logic circuits. However, there is a strong tension between the accuracy and efficiency of existing graph representation learning (GRL) models. Firstly, many real-world graphs (e.g. social networks and logic circuits) are notably large, comprising millions or even billions of nodes and edges, which poses a substantial challenge on model efficiency for training and deployment. Additionally, different domains have complex and diverse graph structures, which are also exposed to adversarial attacks that perturb graph topology via adding or removing nodes and edges. These graph properties necessitate sophisticated model architectures to produce high-quality graph representations, which often come with nontrivial computation cost and memory usage.In this dissertation, we present research solutions that cover scalable, hardware-friendly, expressive, and robust GRL models for accurate and efficient representation learning on large-scale graph applications. We firstly propose GraphZoom, a multi-level approach for fast and accurate GRL. GraphZoom leverages lightweight algorithms that iteratively reduce graph size for GRL and progressively refine graph representations with theoretical guarantees based upon spectral graph theory. This results in a 40.8x training speedup over prior arts with comparable or even better accuracy. Secondly, we develop HOGA for scalable and generalizable GRL on large-scale circuits, via adopting a hop-wise graph attention scheme. HOGA not only outperforms prior GRL models on challenging circuit problems, but is also friendly to distributed training by mitigating communication overhead caused by graph dependencies. This renders HOGA applicable to industrial-scale circuit applications. Thirdly, we introduce Polynormer, an expressive graph transformer model with linear complexity. We theoretically demonstrate the superior expressivity of Polynormer through the lens of polynomial functions. Our extensive experiments indicate that Polynormer not only achieves state-of-the-art results across a wide variety of mainstream graph datasets, but also outperforms a popular baseline model by 31.8% on an industrial-scale dataset provided by Google for predicting AI model runtime on TPU. Last but not least, we propose an efficient graph topology learning approach called GARNET for accurate GRL under graph adversarial attacks. We theoretically show that GARNET can effectively recover critical structures from an adversarial graph with nearly-linear complexity. This leads to an accuracy improvement of up to 10.23% over previous robust GRL models on a broad range of adversarial graphs.
■590 ▼aSchool code: 0058.
■650 4▼aComputer science
■650 4▼aComputer engineering
■650 4▼aElectrical engineering
■653 ▼aElectronic design automation
■653 ▼aGraph representation learning
■653 ▼aSpectral graph theory
■653 ▼aGraph-structured data
■690 ▼a0984
■690 ▼a0464
■690 ▼a0544
■71020▼aCornell University▼bElectrical and Computer Engineering.
■7730 ▼tDissertations Abstracts International▼g85-12B.
■790 ▼a0058
■791 ▼aPh.D.
■792 ▼a2024
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17160815▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
