An Efficient Loop and Clique Coarsening Algorithm for Graph Classification
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929620246331392 |
|---|---|
| author | Qi, Xiaorui Bai, Qijie Wen, Yanlong Zhang, Haiwei Yuan, Xiaojie |
| author_facet | Qi, Xiaorui Bai, Qijie Wen, Yanlong Zhang, Haiwei Yuan, Xiaojie |
| contents | Graph Transformers (GTs) have made remarkable achievements in graph-level tasks. However, most existing works regard graph structures as a form of guidance or bias for enhancing node representations, which focuses on node-central perspectives and lacks explicit representations of edges and structures. One natural question arises as to whether we can leverage a hypernode to represent some structures. Through experimental analysis, we explore the feasibility of this assumption. Based on our findings, we propose an efficient Loop and Clique Coarsening algorithm with linear complexity for Graph Classification (LCC4GC) on GT architecture. Specifically, we build three unique views, original, coarsening, and conversion, to learn a thorough structural representation. We compress loops and cliques via hierarchical heuristic graph coarsening and restrict them with well-designed constraints, which builds the coarsening view to learn high-level interactions between structures. We also introduce line graphs for edge embeddings and switch to edge-central perspective to alleviate the impact of coarsening reduction. Experiments on eight real-world datasets demonstrate the improvements of LCC4GC over 31 baselines from various architectures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_11869 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Efficient Loop and Clique Coarsening Algorithm for Graph Classification Qi, Xiaorui Bai, Qijie Wen, Yanlong Zhang, Haiwei Yuan, Xiaojie Machine Learning Social and Information Networks Graph Transformers (GTs) have made remarkable achievements in graph-level tasks. However, most existing works regard graph structures as a form of guidance or bias for enhancing node representations, which focuses on node-central perspectives and lacks explicit representations of edges and structures. One natural question arises as to whether we can leverage a hypernode to represent some structures. Through experimental analysis, we explore the feasibility of this assumption. Based on our findings, we propose an efficient Loop and Clique Coarsening algorithm with linear complexity for Graph Classification (LCC4GC) on GT architecture. Specifically, we build three unique views, original, coarsening, and conversion, to learn a thorough structural representation. We compress loops and cliques via hierarchical heuristic graph coarsening and restrict them with well-designed constraints, which builds the coarsening view to learn high-level interactions between structures. We also introduce line graphs for edge embeddings and switch to edge-central perspective to alleviate the impact of coarsening reduction. Experiments on eight real-world datasets demonstrate the improvements of LCC4GC over 31 baselines from various architectures. |
| title | An Efficient Loop and Clique Coarsening Algorithm for Graph Classification |
| topic | Machine Learning Social and Information Networks |
| url | https://arxiv.org/abs/2404.11869 |