GSCAN: Graph Stability Clustering für Anwendungen mit Rauschen unter Verwendung von edge-aware Excess-of-Mass

Graph-Clustering ist erforderlich, um Gemeinschaften und Gruppen innerhalb eines gegebenen Netzwerks zu identifizieren. In den letzten Jahren wurden verschiedene Ansätze unternommen, um hierfür geeignete Werkzeuge zu entwickeln. Zuletzt basieren diese Bemühungen auf den neuesten Fortschritten im Bereich des Deep Learning, insbesondere in Graph Neural Networks (GNN). Während einige Methoden die inhärente topologische Struktur des Graphen durchgängig berücksichtigen, ignorieren die führenden Clustering-Verfahren diese im letzten Schritt der Clusterzuweisung, was zu suboptimalen Ergebnissen führt. In diesem Paper stellen wir GSCAN vor: einen Graph-Stabilitäts-Clustering-Ansatz für Anwendungen mit Rauschen, der sowohl auf Knotenmerkmalen als auch auf der Graphstruktur basiert. Unser Ansatz baut auf der bekannten Methode des Excess-of-Mass (EoM) auf, die auf dem Prinzip der Maximierung der Clusterstabilität beruht. Diese Methode weist zusätzliche wünschenswerte Eigenschaften auf, wie Robustheit gegenüber Ausreißern und die Tatsache, dass keine vorab festgelegte Anzahl von Clustern erforderlich ist. Wir erweitern EoM, sodass es die inhärente Struktur des Graphen vollständig berücksichtigt, und schlagen zwei mögliche Nachbearbeitungsverfahren vor, um eine Schwäche von EoM zu beheben – die Neigung, Datenpunkte übermäßig als Ausreißer zu kennzeichnen. Diese Nachbearbeitungsverfahren nutzen die Graphtopologie und führen zu überlegener Leistung, selbst im Vergleich zu führenden Clustering-Ansätzen, die end-to-end trainiert wurden. Wir zeigen, dass der vorgeschlagene Ansatz effizient und skalierbar implementiert werden kann. Unsere Behauptungen werden anhand dreier bekannter Benchmark-Datensätze belegt. Der Quellcode ist hier verfügbar: https://github.com/GraphEoM/GSCAN