Fast and Scalable Hashing-Based Universal Graph Coarsening.

Area of Science:

• Graph theory and network analysis
• Machine learning and data mining
• Computational science and engineering

Background:

• Large graphs are prevalent, posing computational challenges for data processing and analysis.
• Graph coarsening methods condense large graphs but often neglect node features and structural information simultaneously.
• Existing methods are computationally expensive, unsuitable for streaming graphs, and primarily designed for homophilic datasets.

Purpose of the Study:

• To develop a fast, scalable, and universal graph coarsening framework.
• To integrate node features and structural information effectively during graph coarsening.
• To address limitations of existing methods concerning computational intensity and applicability to heterophilic and streaming graphs.

Main Methods:

• Introduction of a Universal Graph Coarsening (UGC) framework utilizing locality-sensitive hashing and feature augmentation.
• An optimization-based framework to minimize constrained epsilon similarity between original and coarsened graphs (epsilon between 0 and 1).
• Implementation of a hashing-based approach for efficient graph condensation.

Main Results:

• UGC demonstrates exceptional speed and ease of implementation.
• The framework effectively handles homophilic, heterophilic, and streaming graphs.
• Experiments show improved runtime complexity and generalization capabilities on real and synthetic datasets.

Conclusions:

• The UGC framework offers a universal solution for graph coarsening, overcoming limitations of prior methods.
• It provides significant advantages in terms of speed, scalability, and applicability to diverse graph types.
• Demonstrated utility in downstream tasks, particularly for training graph neural networks on large, complex datasets.