GSCAN: 노이즈가 있는 응용을 위한 엣지 인지형 초과질량 기반 그래프 안정성 클러스터링

그래프 클러스터링은 주어진 네트워크 내의 커뮤니티 및 그룹을 식별하는 데 필수적인 과정이다. 최근 들어 이러한 목적에 적합한 도구 개발을 위한 다양한 시도가 이루어져 왔다. 특히 최근에는 딥러닝, 특히 그래프 신경망(GNN)의 최신 발전을 기반으로 한 접근 방식들이 주목받고 있다. 그러나 일부 방법들은 그래프의 본질적인 위상 구조를 전반적으로 고려하는 반면, 주목할 만한 점은 최첨단 클러스터링 기법들이 최종 클러스터 할당 단계에서 이 구조를 무시한다는 점이다. 이는 최적의 성능을 달성하지 못하게 만든다. 본 논문에서는 노드 특성과 그래프 구조를 동시에 고려하는 ‘GSCAN: Noise를 고려한 그래프 안정성 클러스터링(Graph Stability Clustering for Applications with Noise)’을 제안한다. 본 연구는 클러스터 안정성을 극대화하는 원리를 기반으로 한 유명한 ‘질량과잉(EoM, Excess-of-Mass)’ 방법에 기반을 두고 있다. 이 방법은 이상치에 강건하며, 미리 클러스터 수를 정의할 필요가 없다는 추가적인 장점을 지닌다. 본 연구는 EoM 기법을 그래프의 본질적인 위상 구조에 맞게 확장하고, EoM의 주요 단점 중 하나인 과도하게 데이터 포인트를 이상치로 식별하는 경향을 보완하기 위한 두 가지 후처리 방식을 제안한다. 이러한 후처리 과정은 그래프의 위상 구조를 활용하여 기존의 엔드투엔드로 훈련되는 최첨단 클러스터링 방법보다도 우수한 성능을 달성한다. 또한 제안된 접근 방식이 빠르고 확장 가능한 방식으로 구현될 수 있음을 보여준다. 본 연구의 주장은 세 가지 잘 알려진 벤치마크 데이터셋을 통해 검증되었다. 코드는 다음과 같은 링크에서 공개되어 있다: https://github.com/GraphEoM/GSCAN