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

Area of Science:

• Artificial Intelligence
• Machine Learning
• Graph Representation Learning

Background:

• Graph Transformers (GTs) are popular for graph representation learning (GRL).
• Existing methods often overlook hyper-order structures (implicit node groups) in graphs.
• Current hypergraph construction methods are often heuristic and disconnected from optimization goals.

Purpose of the Study:

• Introduce Double-Order Graph Transformers (DOGT) for dynamic hyper-order feature incorporation.
• Develop an Adaptive Node-Group (ANG) learning mechanism for inferring hyper-order edges.
• Create a novel Double-Order Attention (DoA) mechanism for feature fusion.

Main Methods:

• DOGT employs a learnable mask matrix for ANG learning to identify hyper-order edges and construct hyper-order graphs (HOGs).
• A dual-branch architecture processes both HOGs (via DoA and GNN) and raw-order graph features (via GNN).
• A feature pyramid fuses representations from both branches for a comprehensive graph representation.

Main Results:

• DOGT demonstrates rapid convergence during training.
• The framework significantly outperforms state-of-the-art methods on graph-level classification and regression tasks.
• ANG and DoA mechanisms adaptively learn hyper-order structures, unlike traditional predefined rules.

Conclusions:

• DOGT offers a novel and effective approach to graph representation learning by integrating dynamic hyper-order structures.
• The adaptive learning of node groups and attention mechanisms enhances performance on downstream tasks.
• This framework advances GRL by bridging the gap between hypergraph construction and optimization objectives.