DOGT: Double-Order Graph Transformers With Adaptive Node-Group Learning

Graph transformers (GTs) have recently attracted considerable attention for graph representation learning (GRL). However, the existing methods often neglect hyper-order structures that arise from implicit node-groups within graphs. More critically, many approaches construct hyper-order structures by using predefined heuristics or clustering algorithms, resulting in a disjointness between hypergraph construction and downstream optimization objectives. To this end, this article proposes double-order GTs (DOGT), a novel framework that dynamically incorporates hyper-order features into graph representations through adaptive node-group (ANG) learning. Specifically, DOGT uses a learnable discriminative mask matrix to infer hyper-order edges, i.e., groups of nodes, followed by building a hyper-order graph (HOG). HOGs are then extracted from the HOG using a new double-order attention (DoA) integrated with a graph neural network (GNN), and meanwhile, raw-order graph features are obtained from another separate GNN branch. Finally, DOGT creates a feature pyramid from the double-order graphs, comprising both the GNN-based and attention-derived representations, to achieve the fused graph representation. This study contributes via ANG, adaptively seeking hyper-order edges instead of using traditional predefined rules, and DoA, computing weights along the transformation from raw-order to HOGs rather than just one of them. Extensive experiments on real-world graph datasets manifest that DOGT not only achieves rapid convergence but also outperforms state-of-the-art (SOTA) methods on graph-level classification and regression tasks.