GraphDETR을 이용한 엔드투엔드 (End-to-End) 서브그래프 탐지

서브그래프 탐지 (Subgraph detection)는 더 큰 그래프 내에서 쿼리 패턴 (query patterns)의 인스턴스가 발생하는지 여부와 그 위치를 식별하는 것을 목표로 합니다. 이 문제는 과학적 영역 전반에 걸쳐 근본적이며, NP-완전 (NP-complete) 문제인 서브그래프 동형성 (subgraph isomorphism)과 밀접하게 관련되어 있어, 조합론적 접근 방식 (combinatorial approaches)은 작은 패턴이나 중간 크기의 그래프로 제한됩니다. 우리는 객체 탐지 (object detection)에서의 DETR과 유사하게 서브그래프 탐지를 집합 예측 문제 (set prediction problem)로 공식화하는 딥러닝 프레임워크인 GraphDETR을 소개합니다. GraphDETR은 그래프 신경망 (GNN)을 사용하여 대상 그래프를 인코딩하며, 트랜스포머 디코더 (transformer decoder)를 통해 디코딩되는 학습 가능한 쿼리 벡터 (query vectors)의 고정된 집합을 사용하여 단 한 번의 순전파 (forward pass) 과정에서 모든 패턴의 발생을 공동으로 예측합니다. 이는 이분 매칭 (bipartite matching)을 통해 모델을 엔드투엔드 (end-to-end)로 학습함으로써 가능해집니다. 정확한 구조적 매칭 (exact structural matching)만을 해결하는 전통적인 조합론적 방법과 달리, GraphDETR은 근사 매칭 (approximate matching)으로 자연스럽게 확장되어 정확한 패턴 대응을 넘어선 탐지를 가능하게 합니다. 실증적으로, 우리는 GraphDETR이 최대 1,000개의 노드를 가진 대상 그래프에서 분자 구조 (molecular structures), 사이클 (cycles), 클리크 (cliques), 그리고 최대 50개의 노드로 구성된 퍼지 패턴 (fuzzy patterns)과 같은 다양한 패턴을 탐지할 수 있음을 보여줍니다. 나아가 우리는 ChEMBL 데이터셋을 통한 분자 작용기 탐지 (molecular functional group detection) 실험을 수행하였으며, 여기서 GraphDETR은 분자당 작용기의 전체 집합을 예측하여 $\text{AP}_{100} = 91.2$라는 강력한 성능을 달성했습니다.