Abstract
Graph Transformers (GTs) have made remarkable achievements in graph-leveltasks. However, most existing works regard graph structures as a form ofguidance or bias for enhancing node representations, which focuses onnode-central perspectives and lacks explicit representations of edges andstructures. One natural question arises as to whether we can leverage ahypernode to represent some structures. Through experimental analysis, weexplore the feasibility of this assumption. Based on our findings, we proposean efficient Loop and Clique Coarsening algorithm with linear complexity forGraph Classification (LCC4GC) on GT architecture. Specifically, we build threeunique views, original, coarsening, and conversion, to learn a thoroughstructural representation. We compress loops and cliques via hierarchicalheuristic graph coarsening and restrict them with well-designed constraints,which builds the coarsening view to learn high-level interactions betweenstructures. We also introduce line graphs for edge embeddings and switch toedge-central perspective to alleviate the impact of coarsening reduction.Experiments on eight real-world datasets demonstrate the improvements of LCC4GCover 31 baselines from various architectures.