Non-Graph Data Clustering via O(n) Bipartite Graph Convolution.

Area of Science:

• Machine Learning
• Graph Neural Networks
• Clustering Algorithms

Background:

• Graph-based clustering methods are limited by initial graph construction quality.
• Graph neural networks (GNNs) offer potential for improving clustering but face scalability challenges.
• Existing methods struggle with graph construction on non-graph data and high computational complexity (O(n^2)).

Purpose of the Study:

• To develop a novel clustering method, AnchorGAE, that integrates GNNs with efficient graph representation.
• To address the limitations of graph availability and computational inefficiency in graph-based clustering.
• To improve the representative capacity of clustering by leveraging high-level information from GNNs.

Main Methods:

• Introduced a generative graph model with anchors to construct a bipartite graph from non-graph data.
• Developed an efficient graph convolution method with reduced computational complexity from O(n^2) to O(n).
• Implemented a self-supervised learning paradigm with dynamic graph updates and a strategy to prevent model collapse.

Main Results:

• AnchorGAE successfully converts non-graph data into a graph dataset using anchors and a bipartite graph.
• The method achieves efficient graph convolution with O(n) complexity and O(n) clustering operations.
• Theoretical analysis and experiments demonstrate the effectiveness of the self-supervised approach and a strategy to prevent collapse, showing AnchorGAE's superiority.

Conclusions:

• AnchorGAE effectively combines GNNs with a novel bipartite graph construction for efficient and high-capacity clustering.
• The proposed method overcomes the scalability and graph construction limitations of traditional graph-based clustering.
• AnchorGAE offers a promising direction for advancing clustering techniques, particularly for large-scale and non-graph datasets.