← Back to Problem Bank
GDL In Progress

엣지 분류를 위한 PL4XGL

PL4XGL for Edge Classification

1. 문제 (Problem)

엣지 분류(Edge Classification) 는 그래프의 각 엣지에 대해 label을 예측하는 문제이다. 대표적인 형태로 (i) 링크 예측(link prediction) — 두 노드 사이에 엣지가 존재하는지 여부의 이진 분류, (ii) 엣지 타입 분류(edge type classification) — 지식 그래프의 관계 종류, 단백질 상호작용의 종류 등 다중 클래스 분류, (iii) 이상 엣지 탐지(anomalous edge detection) — 금융 거래 그래프의 fraud 엣지, 소셜 네트워크의 spam 엣지 식별 등이 있다. 추천 시스템, 지식 그래프 보강, 단백질 상호작용 예측, 보안 분석 등 결정의 근거가 중요한 도메인 전반에서 핵심 과제로 다뤄진다.

현재 엣지 분류의 주류 방법은 GNN 기반 접근이다. 두 endpoint 노드 임베딩 hu, hv 를 GNN으로 학습한 뒤, 이를 결합하여 (concat, Hadamard product, MLP 등) 엣지 label을 예측한다. R-GCN [Schlichtkrull et al., ESWC 2018], CompGCN [Vashishth et al., ICLR 2020], SEAL [Zhang & Chen, NeurIPS 2018] 등이 대표적이다. 이들은 높은 정확도를 보이지만 black-box이며, “왜 이 두 노드 사이에 이 엣지가 존재한다고 예측하는가” 에 대한 명시적 근거를 제공하지 못한다.

PL4XGL [Jeon, Park, Oh, PLDI 2024]은 GDL(Graph Description Language) program 집합을 분류기로 사용하는 symbolic, inherently interpretable 그래프 학습 기법이다. Fidelity = 0의 구조적 보장(Theorem 6.1)과 GDL의 human-readable 설명을 동시에 제공한다. 그러나 PL4XGL의 분류 단위는 노드(transductive node classification) 또는 전체 그래프(inductive graph classification)로 한정되어 있으며, 엣지를 분류 단위로 다루지 않는다.

PL4XGL의 엣지 분류 한계

  1. 분류 단위 불일치: PL4XGL의 GDL program은 단일 노드의 ego-subgraph를 기술하도록 설계되었다. 엣지 (u, v) 의 분류를 위해서는 두 endpoint u, v 의 결합 구조와 이들 사이의 관계적 맥락을 함께 표현해야 하지만, GDL은 이를 first-class로 지원하지 않는다.
  2. 관계적 패턴 미표현: 엣지 (u, v) 의 의미는 종종 u와 v의 공통 이웃(Adamic-Adar, Common Neighbors), 경로 패턴(meta-path), 커뮤니티 동질성에 의해 결정된다. 예를 들어 “두 단백질이 같은 complex에 속한다” 는 link prediction의 핵심 신호이지만, 현재 GDL은 두 노드의 결합 통계를 기술하는 술어를 갖지 않는다.
  3. 비대칭 / 방향 엣지 미지원: 지식 그래프의 관계는 본질적으로 비대칭(asymmetric) 이다 (예: (파리, capitalOf, 프랑스) 는 성립하지만 역방향은 다른 의미). PL4XGL은 무방향 그래프 가정 하에 설계되어, 엣지의 방향성과 비대칭 패턴을 다루지 못한다.
  4. Negative sampling 부재: 링크 예측은 본질적으로 positive 엣지(존재) vs. negative 엣지(부재) 의 이진 분류이며, negative 엣지는 명시적 sampling으로 생성된다. PL4XGL의 per-instance synthesis는 positive 인스턴스에서만 program을 합성하므로, “어떤 패턴이 엣지의 부재를 시사하는가” 를 학습할 수단이 없다.
  5. 다중 관계 타입 폭발: 지식 그래프(FB15k-237: 237 관계, WN18RR: 11 관계, OGB-BioKG: 51 관계)는 수십~수백 종의 엣지 타입을 가진다. PL4XGL을 그대로 적용하면 각 관계 타입마다 독립적으로 program을 합성해야 하므로 비용이 관계 수에 선형 이상으로 증가하며, 관계 간 공유 가능한 구조적 패턴을 활용하지 못한다.
  6. Edge feature 미통합: 실세계 엣지는 종종 자체 feature를 가진다 (거래 금액, 상호작용 강도, timestamp 등). PL4XGL의 GDL은 노드 feature에 대한 interval 술어만 지원하며, 엣지 feature를 first-class로 다루지 않는다.

연구 공백

GNN 기반 엣지 분류는 높은 정확도를 보이지만 설명이 black-box이다. 기존 link prediction explainer (PGExplainer, GNNExplainer를 엣지로 확장)는 post-hoc이며 faithfulness 보장이 없다. 반면 PL4XGL은 Fidelity = 0 보장을 가지지만 분류 단위가 엣지가 아니다.

즉 “엣지 분류에서 inherently interpretable하면서도 GNN 수준의 정확도를 달성하는 방법” 은 현재 부재하다. PL4XGL의 해석 가능성 보장을 유지하면서 엣지 분류의 핵심 원리 — 두 endpoint의 결합 구조, 관계적 패턴, 방향성, negative sampling, 다중 관계 타입, edge feature — 를 GDL 수준에서 통합하는 것이 이 공백을 메우는 방향이다.

2. 목표 (Goal)

PL4XGL의 해석 가능성 보장(Fidelity = 0, GDL의 human-readable 설명) 을 유지하면서, 엣지 분류 설정에서 GNN 수준의 정확도를 달성하는 프레임워크를 설계한다.