Graph Condensation via Homophily Node Refining and Fine-Grained Distribution Matching

Area of Science:

• Graph Neural Networks (GNNs)
• Machine Learning
• Data Science

Background:

• Training large-scale graphs with GNNs incurs high computational and memory costs.
• Graph condensation aims to create smaller synthetic graphs preserving original data characteristics.
• Accurately aligning data distribution structures between original and synthetic graphs is crucial.

Purpose of the Study:

• To address limitations in current graph condensation methods, specifically overlooking heterophilic nodes and coarse-grained distribution matching.
• To propose a novel graph condensation method, GCRD, for improved synthetic graph generation.
• To enhance the accuracy of preserving essential graph characteristics in smaller, synthetic graphs.

Main Methods:

• Distinguishing between homophilic and heterophilic nodes in the original graph.
• Adaptively assigning node weights to refine class distribution patterns.
• Implementing a fine-grained distribution matching objective to align subclass structures.

Main Results:

• The proposed GCRD method refines class distribution patterns by considering node homophily.
• Fine-grained distribution matching improves the alignment of local distribution structures within classes.
• Theoretical analysis confirms the effectiveness of GCRD in learning class information.

Conclusions:

• GCRD offers a superior approach to graph condensation compared to existing methods.
• The method achieves state-of-the-art classification and cross-architecture generalization performance.
• GCRD effectively tackles challenges posed by heterophilic nodes and complex data distributions in large graphs.