초록
전통적으로 그래프에서의 커뮤니티 탐지는 스펙트럼 방법 또는 확률적 그래픽 모델 하의 사후 추론을 사용하여 해결할 수 있습니다. 최근 연구에서는 스토캐스틱 블록 모델과 같은 무작위 그래프족에 초점을 맞추어 두 접근 방식을 통합하고, 신호 대 잡음 비율 측면에서 통계적 및 계산적 탐지 임계값을 식별하였습니다. 커뮤니티 탐지를 그래프 상의 노드별 분류 문제로 재구성함으로써, 우리는 이를 학습 관점에서 연구할 수도 있습니다. 본 논문에서는 감독된 학습 환경에서 커뮤니티 탐지 문제를 해결하기 위한 새로운 종류의 그래프 신경망(GNNs)을 제시합니다. 데이터 주도 방식으로 그리고 기저 생성 모델에 접근하지 않고, 이들은 이진 및 다중 클래스 스토캐스틱 블록 모델에서 벨리프 프로파게이션 알고리즘의 성능을 일치시키거나 심지어 능가할 수 있으며, 이는 계산적 임계값에 도달하는 것으로 알려져 있습니다. 특히, 우리는 에지 인접성(line graph of edge adjacencies) 위에서 정의된 비백트래킹 연산자(non-backtracking operator)를 GNNs에 추가하는 방법을 제안합니다. 우리의 모델은 실제 세계 데이터셋에서도 좋은 성능을 보입니다. 또한, 우리는 커뮤니티 탐지 문제를 위해 선형 GNNs를 훈련시키는 최적화 경계면에 대한 첫 번째 분석을 수행하였으며, 특정 단순화와 가정 하에서 로컬 최소점과 전역 최소점에서의 손실 값이 크게 차이 나지 않음을 입증하였습니다.