Papers › GSCAN: Graph Stability Clustering for Applications With Noise Using Edge-Aware Excess-of-Mass

GSCAN: Graph Stability Clustering for Applications With Noise Using Edge-Aware Excess-of-Mass

17 Apr 2024Proceedings of the Second Learning on Graphs Conference, PMLR, 2024 2024 4archive 2025-07-28

Etzion Harari, Naphtali Abudarham, Roee Litman

Graph Clustering is required for the identification of communities and groups within a given network. In recent years, various attempts have been made to develop tools suitable for this purpose. Most recently, these attempts are based on the latest advancements in deep learning and especially in Graph Neural Networks (GNN). While some methods take into account the graph intrinsic topological structure throughout, surprisingly, the leading clustering methods ignore this during the final cluster assignment stage, which leads to sub-optimal results. In this paper, we propose GSCAN: a Graph Stability Clustering for Applications with Noise, which is based both on node features and on the graph structure. We base our approach on the celebrated method of Exess-of-Mass (EoM), which is based the principle of maximizing cluster stability. This method has additional desirable properties like resilience to outliers and the fact it doesn’t require an a-priory definition of the number of clusters. We extend EoM to work on the \ast intrinsic\ast graph structure and propose two possible post-processes to deal with one of EoM’s shortcomings - its tendency to over-flagging data-points as outliers. These post processes harness the graph topology and lead to superior performance, even compared to leading clustering approaches that are trained end-to-end. We show that the proposed approach can be implemented in a fast and scalable manner. Our claims are backed on three well-known benchmark datasets. Our code is available here: https://github.com/GraphEoM/GSCAN

Code

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

Results from the paper archive 2025-07-28

Ranks are positions in the archive's leaderboards as they stood at the 2025-07-28 snapshot. Results published since then are not among these rows, so a rank here is not a current standing.

Methods

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections