Graph structure reforming framework enhanced by commute time distance for graph classification.

Area of Science:

• Graph Data Mining
• Machine Learning
• Network Science

Background:

• Graph classification is crucial for data mining and has wide applications.
• Graph Neural Networks (GNNs), specifically Message Passing Neural Networks (MPNNs), are mainstream but suffer from over-squashing and limited expressiveness.
• Existing solutions address these issues separately, lacking a comprehensive approach.

Purpose of the Study:

• To address information loss from local aggregation and the inability to capture higher-order structures in GNNs.
• To propose a novel, plug-and-play framework that comprehensively tackles these GNN limitations.
• To enhance the expressive power of GNNs for improved graph classification performance.

Main Methods:

• Developed a framework based on Commute Time Distance (CTD) for information propagation within CTD neighborhoods.
• Evaluated CTD by considering both local and global graph connections, path length, and the number of paths.
• Introduced Commute Time Distance-based Message Passing Neural Networks (CTD-MPNNs) to capture higher-order structural information via commute paths.

Main Results:

• The CTD-MPNN framework effectively propagates and aggregates messages from important neighbors.
• The framework enhances GNNs' expressive power, leading to more robust models.
• Extensive experiments on real-world graph classification benchmarks demonstrated the framework's effectiveness.

Conclusions:

• The proposed CTD-MPNN framework offers a comprehensive solution to existing GNN limitations.
• This approach significantly improves graph classification performance by capturing richer structural information.
• The plug-and-play nature of the framework allows for easy integration and enhanced GNN modeling.