Flexible Diffusion Scopes with Parameterized Laplacian for Heterophilic Graph Learning
| Title: | Flexible Diffusion Scopes with Parameterized Laplacian for Heterophilic Graph Learning |
|---|---|
| Authors: | Lu, Qincheng, Zhu, Jiaqi, Luan, Sitao, Chang, Xiao-Wen |
| Publication Year: | 2024 |
| Collection: | Computer Science |
| Subject Terms: | Computer Science - Machine Learning, Computer Science - Social and Information Networks |
| More Details: | The ability of Graph Neural Networks (GNNs) to capture long-range and global topology information is limited by the scope of conventional graph Laplacian, leading to unsatisfactory performance on some datasets, particularly on heterophilic graphs. To address this limitation, we propose a new class of parameterized Laplacian matrices, which provably offers more flexibility in controlling the diffusion distance between nodes than the conventional graph Laplacian, allowing long-range information to be adaptively captured through diffusion on graph. Specifically, we first prove that the diffusion distance and spectral distance on graph have an order-preserving relationship. With this result, we demonstrate that the parameterized Laplacian can accelerate the diffusion of long-range information, and the parameters in the Laplacian enable flexibility of the diffusion scopes. Based on the theoretical results, we propose topology-guided rewiring mechanism to capture helpful long-range neighborhood information for heterophilic graphs. With this mechanism and the new Laplacian, we propose two GNNs with flexible diffusion scopes: namely the Parameterized Diffusion based Graph Convolutional Networks (PD-GCN) and Graph Attention Networks (PD-GAT). Synthetic experiments reveal the high correlations between the parameters of the new Laplacian and the performance of parameterized GNNs under various graph homophily levels, which verifies that our new proposed GNNs indeed have the ability to adjust the parameters to adaptively capture the global information for different levels of heterophilic graphs. They also outperform the state-of-the-art (SOTA) models on 6 out of 7 real-world benchmark datasets, which further confirms their superiority. Comment: arXiv admin note: substantial text overlap with arXiv:2403.01475 |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2409.09888 |
| Accession Number: | edsarx.2409.09888 |
| Database: | arXiv |
| FullText | Text: Availability: 0 CustomLinks: – Url: http://arxiv.org/abs/2409.09888 Name: EDS - Arxiv Category: fullText Text: View this record from Arxiv MouseOverText: View this record from Arxiv – Url: https://resolver.ebsco.com/c/xy5jbn/result?sid=EBSCO:edsarx&genre=article&issn=&ISBN=&volume=&issue=&date=20240915&spage=&pages=&title=Flexible Diffusion Scopes with Parameterized Laplacian for Heterophilic Graph Learning&atitle=Flexible%20Diffusion%20Scopes%20with%20Parameterized%20Laplacian%20for%20Heterophilic%20Graph%20Learning&aulast=Lu%2C%20Qincheng&id=DOI: Name: Full Text Finder (for New FTF UI) (s8985755) Category: fullText Text: Find It @ SCU Libraries MouseOverText: Find It @ SCU Libraries |
|---|---|
| Header | DbId: edsarx DbLabel: arXiv An: edsarx.2409.09888 RelevancyScore: 1112 AccessLevel: 3 PubType: Report PubTypeId: report PreciseRelevancyScore: 1112.25720214844 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Flexible Diffusion Scopes with Parameterized Laplacian for Heterophilic Graph Learning – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Lu%2C+Qincheng%22">Lu, Qincheng</searchLink><br /><searchLink fieldCode="AR" term="%22Zhu%2C+Jiaqi%22">Zhu, Jiaqi</searchLink><br /><searchLink fieldCode="AR" term="%22Luan%2C+Sitao%22">Luan, Sitao</searchLink><br /><searchLink fieldCode="AR" term="%22Chang%2C+Xiao-Wen%22">Chang, Xiao-Wen</searchLink> – Name: DatePubCY Label: Publication Year Group: Date Data: 2024 – Name: Subset Label: Collection Group: HoldingsInfo Data: Computer Science – Name: Subject Label: Subject Terms Group: Su Data: <searchLink fieldCode="DE" term="%22Computer+Science+-+Machine+Learning%22">Computer Science - Machine Learning</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+-+Social+and+Information+Networks%22">Computer Science - Social and Information Networks</searchLink> – Name: Abstract Label: Description Group: Ab Data: The ability of Graph Neural Networks (GNNs) to capture long-range and global topology information is limited by the scope of conventional graph Laplacian, leading to unsatisfactory performance on some datasets, particularly on heterophilic graphs. To address this limitation, we propose a new class of parameterized Laplacian matrices, which provably offers more flexibility in controlling the diffusion distance between nodes than the conventional graph Laplacian, allowing long-range information to be adaptively captured through diffusion on graph. Specifically, we first prove that the diffusion distance and spectral distance on graph have an order-preserving relationship. With this result, we demonstrate that the parameterized Laplacian can accelerate the diffusion of long-range information, and the parameters in the Laplacian enable flexibility of the diffusion scopes. Based on the theoretical results, we propose topology-guided rewiring mechanism to capture helpful long-range neighborhood information for heterophilic graphs. With this mechanism and the new Laplacian, we propose two GNNs with flexible diffusion scopes: namely the Parameterized Diffusion based Graph Convolutional Networks (PD-GCN) and Graph Attention Networks (PD-GAT). Synthetic experiments reveal the high correlations between the parameters of the new Laplacian and the performance of parameterized GNNs under various graph homophily levels, which verifies that our new proposed GNNs indeed have the ability to adjust the parameters to adaptively capture the global information for different levels of heterophilic graphs. They also outperform the state-of-the-art (SOTA) models on 6 out of 7 real-world benchmark datasets, which further confirms their superiority.<br />Comment: arXiv admin note: substantial text overlap with arXiv:2403.01475 – Name: TypeDocument Label: Document Type Group: TypDoc Data: Working Paper – Name: URL Label: Access URL Group: URL Data: <link linkTarget="URL" linkTerm="http://arxiv.org/abs/2409.09888" linkWindow="_blank">http://arxiv.org/abs/2409.09888</link> – Name: AN Label: Accession Number Group: ID Data: edsarx.2409.09888 |
| PLink | https://login.libproxy.scu.edu/login?url=https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edsarx&AN=edsarx.2409.09888 |
| RecordInfo | BibRecord: BibEntity: Subjects: – SubjectFull: Computer Science - Machine Learning Type: general – SubjectFull: Computer Science - Social and Information Networks Type: general Titles: – TitleFull: Flexible Diffusion Scopes with Parameterized Laplacian for Heterophilic Graph Learning Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Lu, Qincheng – PersonEntity: Name: NameFull: Zhu, Jiaqi – PersonEntity: Name: NameFull: Luan, Sitao – PersonEntity: Name: NameFull: Chang, Xiao-Wen IsPartOfRelationships: – BibEntity: Dates: – D: 15 M: 09 Type: published Y: 2024 |
| ResultId | 1 |