기술 요약: 관계형 데이터베이스를 위한 심층 동형사상 네트워크의 표현력

문제 제기

메시지 전달 메커니즘에 기반한 표준 그래프 신경망 (GNN) 은 1 차원 와이스펠러 - 레만 (1-WL) 테스트로 제한되는 표현력의 한계를 지니고 있습니다. 그 결과, 분자 특성 예측 및 관계형 데이터베이스 분석과 같은 분야에서 종종 결정적인 역할을 하는 삼각형, 클릭 (clique), 또는 고정 길이의 사이클과 같은 기본 그래프 속성을 탐지하지 못합니다. 기존 접근법들은 특징 증강 (예: 정점에 동형사상 개수를 추가) 이나 고차원 아키텍처를 통해 이를 극복하려 시도하지만, 이러한 방법들은 관계형 데이터베이스 이론과의 원칙적인 연결이 부족한 경우가 많습니다. 구체적으로, 관계형 데이터베이스를 GNN 처리를 위해 그래프로 변환하는 과정은 의미론적 불일치를 초래하며, 증강된 GNN 의 표현력이 표준 데이터베이스 쿼리 언어와 관련하여 완전히 이해되지 않고 있습니다.

방법론

본 논문은 작은 "패턴" 데이터베이스에서 정의된 **동형사상 (homomorphisms)**을 따른 메시지 전달을 표준 엣지 기반 메시지 전달로 대체함으로써 GNN 을 일반화하는 **심층 동형사상 네트워크 (Deep Homomorphism Networks, DHNs)**를 소개하고 분석합니다. DHNs 는 그래프 변환의 필요성을 피하고 관계형 데이터베이스에서 직접 작동합니다.

저자들은 DHN 의 정확한 표현력을 결정하기 위해 논리적 특징화 접근법을 사용합니다. 그들은 집계 함수 (최대, 합, 평균) 가 다른 DHN 을 1 차 논리 (First-Order Logic, FO) 및 SQL의 특정 단편 및 확장과 연관시킵니다:

1. 논리적 프레임워크: 연구는 일항 부정 단편 (UNFO), 카운팅 양화사를 포함한 그 확장 (UNFOC), 그리고 동형사상 모달 논리 (HML) 를 활용합니다. 합-aggregation 의 경우, **FO 의 일항 양화사 교번 단편 (UQAFO)**과 **임베딩 모달 논리 (EML)**를 도입합니다. 평균-aggregation 의 경우, **비율 동형사상 모달 논리 (RHML)**를 정의합니다.
2. 정적 분석: 논리적 특징화는 공허성 문제(DHN 이 데이터베이스를 수용하는가?) 와 포함 문제(한 DHN 의 분류기가 다른 것보다 더 일반적인가?) 와 같은 기본 정적 분석 문제의 결정 가능성을 조사하는 데 사용됩니다.
3. 이론적 경계: 저자들은 동형사상과 임베딩을 연관시키기 위해 로바츠 (Lovász) 의 동형사상 카운팅 정리를 활용하여, 제한되지 않은 차수의 데이터베이스에서 합-DHN 의 표현력에 대한 하한과 상한을 확립합니다.
4. 실험적 검증: 특정 이론적 분리를 테스트하기 위해 합성 데이터셋이 구축되었습니다:
   • 국소 전이성 (Local Transitivity): 합-DHN 으로 표현 가능하지만 최대-DHN 이나 UNFOC 로는 표현 불가능한 속성.
   • 선 (Sun) 속성: 모든 정점이 차수 1 인 이웃을 갖는 6-사이클 위의 정점으로 정의되는 속성으로, 합-DHN 으로 표현 가능하지만 초기 동형사상 개수로 증강된 GNN 으로는 표현 불가능한 속성.

주요 기여

1. 논리적 특징화

• 최대-DHN: 최대-DHN 의 표현력은 UNFO(및 HML) 와 정확히 동등합니다. 이는 완전하고 통일된 논리적 특징화를 제공합니다.
• 합-DHN (제한된 차수): 제한된 차수의 데이터베이스에서 연결된 합-DHN 은 UNFOC(및 연결된 GHML) 와 동등합니다.
• 합-DHN (제한되지 않은 차수): 저자들은 연결된 합-DHN 이 FO 로 정의 가능한 속성조차 UNFOC 보다 엄격하게 더 표현력이 있음을 증명합니다. 그들은 하한으로서 UQAFO를 도입하고, 표현력 있는 카운팅을 가진 동형사상 기반 논리를 상한으로 제시합니다.
• 평균-DHN: 제한된 차수의 데이터베이스에서 연결된 평균-DHN 은 비율 양화사를 포함하여 HML 을 확장한 논리인 RHML과 동등합니다.

2. 심층 임베딩 네트워크 (DENs)

본 논문은 일반적인 동형사상 대신 임베딩 (단사 동형사상) 을 사용하는 **심층 임베딩 네트워크 (Deep Embedding Networks, DENs)**를 소개합니다.

• 로바츠 정리를 사용하여, 저자들은 합-DEN과 합-DHN이 동일한 표현력을 가진다고 증명합니다.
• 최대-DEN은 최대-DHN(HML 에 대응하는 EML) 보다 엄격하게 더 표현력이 있음이 입증되었습니다.
• 이 구별은 전역 리드아웃 (global readout) 을 포함하더라도 DHN 과 초기 동형사상 개수가 포함된 GNN 사이의 엄격한 분리를 가능하게 합니다.

3. 정적 분석 및 결정 가능성

• 결정 가능: 최대-DHN에 대한 공허성 및 포함 문제는 결정 가능합니다 (UNFO 와의 동등성 때문). 제한된 차수 데이터베이스의 연결된 합-DHN의 경우, 이러한 문제는 결정 가능하며 CONEXPTIME-완전합니다.
• 결정 불가능: 합-DHN(연결된 것조차 포함) 에 대한 공허성 및 포함 문제는 제한되지 않은 그래프와 연결성이 요구되지 않는 경우 제한된 차수의 그래프에서도 결정 불가능합니다. 이는 이러한 문제들이 결정 가능한 단순 합-GNN 과 대조됩니다.

4. 실험 결과

합성 데이터셋에 대한 실험은 이론적 분리를 확인합니다:

• 국소 전이성: 합-DHN 은 F1 점수 0.98 및 AUROC 1.00 을 달성하여 최대-DHN(0.83/0.93) 과 표준 GNN(GCN, GraphSAGE, GIN) 을 크게 능가했습니다.
• 선 속성: 합-DHN 은 완벽한 성능 (1.00 F1/AUROC) 을 달성한 반면, 동형사상 개수를 포함한 GNN(전역 리드아웃 포함) 은 동일한 수준 (0.88/0.94) 에 도달하지 못하여, 합-DHN 이 동형사상 개수 증강 GNN 보다 엄격하게 더 표현력이 있다는 이론적 주장을 검증했습니다.

중요성 및 주장

본 논문은 DHN 이 관계형 데이터를 위한 자연스럽고 원칙적인 신경 아키텍처를 제공하며, 딥러닝과 데이터베이스 이론 간의 간극을 메운다고 주장합니다. DHN 을 동형사상에 기반함으로써, 이 모델은 SQL 의 핵심인 **결합 쿼리 (Conjunctive Queries, CQs)**와 직접 연결됩니다.

저자들은 그들의 작업이 다음과 같음을 강조합니다:

1. 표현 한계 명확화: 모호한 "GNN 보다 더 강력함"이라는 주장을 넘어 구체적인 논리적 동등성으로 다양한 신경 아키텍처가 학습할 수 있는 데이터베이스 속성과 그렇지 않은 속성을 정확하게 구분합니다.
2. 정적 분석 가능: 논리적 특징화는 모델 분석에서의 결정 가능성 연구를 가능하게 하여, 최대-DHN 은 정적 분석에 적합하지만 합-DHN 은 카운팅이 포함된 완전한 1 차 논리와 유사한 결정 불가능성을 도입함을 드러냅니다.
3. 이론적 격차 검증: 실험은 표현력의 이론적 차이가 국소 전이성 및 선 속성과 같은 표준 GNN 이나 심지어 동형사상 증강 GNN 이라도 신뢰성 있게 포착할 수 없는 특정 구조적 패턴 탐지가 필요한 작업에서 실질적인 성능 향상으로 이어짐을 확인시켜 줍니다.

본 논문은 DHN 이 관계형 딥러닝을 위한 강력한 이론적 기반을 제공하지만, 패턴의 체계적 선택과 합-aggregation 과 관련된 결정 불가능 정적 분석 문제에 대한 효율적 알고리즘 개발과 같은 과제가 남아있다고 결론지었습니다.