Provable Filter for Real-World Graph Clustering.

Area of Science:

• Computer Science
• Artificial Intelligence
• Graph Theory

Background:

• Graph clustering is a key unsupervised learning task.
• Existing methods often fail on real-world graphs due to limitations in handling both homophily and heterophily.
• This necessitates advanced techniques for practical graph analysis.

Purpose of the Study:

• To develop a principled graph clustering method for diverse real-world graphs.
• To address the limitations of existing methods that focus solely on homophilic or heterophilic structures.
• To improve the applicability and performance of graph clustering algorithms.

Main Methods:

• Constructing two distinct graphs to represent homophilic and heterophilic properties.
• Utilizing low-pass and high-pass filters derived from these graphs for holistic information capture.
• Incorporating a squeeze-and-excitation (SE) block to enhance important features.
• Providing theoretical analysis linking filter properties to clustering performance.

Main Results:

• The proposed method demonstrates superior performance on both homophilic and heterophilic graphs.
• Achieved average accuracy improvements of 1.82% on heterophilic and 0.83% on homophilic graphs over state-of-the-art baselines.
• Validated effectiveness through extensive experiments and a co-saliency detection application.

Conclusions:

• The novel approach offers a robust solution for graph clustering in practical scenarios.
• The method effectively captures information from both homophilic and heterophilic graph structures.
• This work advances graph clustering by providing a unified framework for diverse graph types.