GDL 기반 GNN 설명 기법

1. 문제 (Problem)

GNN 설명(GNN Explanation) 은 GNN이 특정 예측을 내린 근거를 사람이 이해할 수 있는 형태로 제시하는 문제이다. 신약 개발, 의료 진단, 프로그램 분석, 사기 탐지 등 의사결정이 중요한 도메인에서 GNN을 실제로 배치하기 위한 전제 조건이다.

지금까지 제안된 대부분의 GNN 설명 기법은 subgraph(부분 그래프) 또는 subgraph 위의 가중치(edge/feature mask) 를 설명의 단위로 사용한다.

• Post-hoc 방법: GNNExplainer, PGExplainer, SubgraphX, GraphMask, PGM-Explainer, CF-GNNExplainer, RCExplainer 등
• Rationale 기반 intrinsic 방법: GSAT, GIB-subgraph, DIR, ProtGNN 등
• Global explanation 방법: XGNN, GNNInterpreter, GCFExplainer 등

그러나 subgraph/edge mask를 설명 언어로 사용하는 접근법은 다음과 같은 근본적 한계를 가진다.

• Instance-level isolation: 각 인스턴스마다 독립적으로 subgraph가 생성되어, 데이터셋 전반에서 공유되고 재사용 가능한 설명 단위가 없다. 같은 현상을 설명하는 두 그래프에 대해 서로 다른 subgraph가 제시되는 설명의 불안정성(instability) 이 자주 관찰된다.
• 표현력 부족: Subgraph는 고정된 feature 값으로만 패턴을 기술한다. “탄소 개수가 3~5인 고리”와 같이 feature 값 범위(range) 로 표현되는 일반화된 설명은 subgraph로는 직접 표현 불가능하다.
• Soft mask의 해석 어려움: 많은 방법들은 edge/node에 [0, 1] 값을 부여하는데, 이를 사람이 이해 가능한 규칙으로 변환하는 데는 추가적 해석 단계(thresholding 등)가 필요하며 faithfulness가 저하된다.
• Dataset-level 설명 부재: 사용자는 종종 “이 모델은 전체적으로 어떤 종류의 패턴에 반응하는가?”를 알고 싶어 하지만, 대다수 기법은 단일 인스턴스 설명만 제공한다.
• Faithfulness와 accuracy의 trade-off: 강한 GNN의 정확도를 유지하는 설명 기법은 설명이 약하고 불안정한 반면, 본질적으로 해석 가능한 symbolic 방법은 정확도를 희생한다.

최근 PL4XGL [Jeon, Park, Oh, PLDI 2024]과 ProgNet [Anonymous, KDD’26 under review]이 GDL(Graph Description Language) 을 분류의 근거 언어로 도입하였다. GDL program은 node x <φ> / edge (x,y) <φ> / target 으로 구성되며 feature 값을 interval(구간) 로 기술하는 declarative 패턴 언어이고, subgraph보다 엄격히 더 표현력이 강하다. 특히 PL4XGL은 구조적으로 Fidelity = 0 을 보장한다 (Theorem 6.1).

그러나 두 연구 모두 GDL을 특정 모델 구조에 내장하여 사용한다. 즉 임의의 사전 학습된 GNN을 그대로 두고 GDL을 설명 언어로 덧씌우는 model-agnostic 프레임워크는 부재하다. PL4XGL 저자들은 §8에서 “GDL can be employed in ... GNN explanation techniques” 라고 이 방향을 직접적으로 제안하였으나, 실제로 구현한 연구는 아직 없다.

2. 목표 (Goal)

Subgraph 대신 GDL program을 설명의 단위로 사용하는 GNN explanation 프레임워크를 개발한다.

• Interval-aware 설명: 설명이 “이러이러한 feature 범위를 만족하는 패턴이 존재할 때 예측이 y가 된다”의 형태로 자연스럽게 기술됨
• Dataset-level 재사용성: 동일 또는 유사한 현상을 설명하는 GDL program이 여러 인스턴스에 걸쳐 공유되어, 설명의 일관성과 안정성 확보
• 모델 독립성(model-agnostic): 임의의 GCN/GIN/GAT/Graph Transformer 등에 사후적으로 적용 가능한 post-hoc 버전과, 학습 시 내재화된 intrinsic 버전을 모두 지원
• Faithfulness 보장: 생성된 GDL 기반 설명으로부터 subgraph를 instance-grounding하여, Fidelity(−) / Fidelity(+) 등 표준 지표에서 기존 방법보다 우수
• 인간 친화적 표현: 도메인 전문가가 GDL program을 읽고 수정할 수 있는 수준의 간결성과 표현력

3. 기본 접근 방법 (Basic Approach)

(1) 설명 언어로서의 GDL

• GDL program P = (δV, δE, τ): 노드/엣지 기술 + target symbol τ ∈ {node x, edge (x,y), graph} — node / edge / graph 분류 설명을 모두 지원
• Interval <φ>은 open bound 포함 ([-∞, 0.3], [5, ∞])
• 기존 subgraph 설명은 interval 폭이 0인 특수 케이스
• 설명은 단일 GDL program 또는 program들의 집합(vocabulary) 로 구성
• PL4XGL의 원래 설계 철학인 “설명이 곧 분류 경로” (Theorem 6.1 Fidelity = 0)를 post-hoc 환경에서도 최대한 근사

(2) Post-hoc GDL Explainer

사전 학습된 임의의 GNN f와 입력 그래프 G가 주어졌을 때:

1. Candidate program 생성: G를 기반으로 후보 GDL program 집합 PG 생성. PL4XGL의 top-down(specialize) / bottom-up(generalize) program synthesis를 재사용
2. Program scoring: 각 program P에 대해 GNN 예측 기여도 s(P) 계산 — GNNExplainer 스타일의 mutual information, PGExplainer 스타일의 parameterized scorer, 또는 SubgraphX 스타일의 Shapley value를 GDL 공간으로 확장
3. Program selection: f(G)의 예측을 유지하는 최소의 program 집합을 선택 (e.g., Fidelity(−) 최소화)
4. Instance grounding: 선택된 program들을 만족시키는 concrete subgraph G' ⊆ G를 iterative refinement로 추출

(3) Intrinsic GDL Rationale

학습 과정에 GDL 기반 rationale을 내재화하는 방법:

• GDL-aware attention: GSAT의 stochastic attention을 GDL program activation으로 대체
• Information bottleneck on GDL: I(P; Y) - β I(P; G)를 최적화하여 task-relevant한 최소 GDL program 집합 학습
• Prototype-based: ProtGNN의 prototype을 GDL program으로 대체하여 prototype을 사람이 읽을 수 있게 만듦

(4) Global Explanation via GDL Vocabulary

• 학습 데이터에서 추출된 GDL program 중 coverage와 diversity가 높은 부분집합 Q를 선택
• 각 클래스 c에 대해 positive/negative attribution이 큰 program들을 식별하여 “모델이 클래스 c를 어떻게 인식하는가” 에 대한 전역 설명 제공
• XGNN/GNNInterpreter가 graph 생성으로 global explanation을 시도한 것에 비해, GDL은 실제 데이터에서 유래한 grounded global explanation 을 제공

(5) Counterfactual GDL Explanation

• “어떤 program의 활성화가 사라지면 예측이 바뀌는가?” — CF-GNNExplainer / RCExplainer의 counterfactual 개념을 GDL 공간으로 확장
• 최소 program 수정 ΔP로 예측이 변하는 counterfactual 설명 제공

(6) 평가 프로토콜

• Fidelity(−) / Fidelity(+): 설명만 남겼을 때 / 설명을 제거했을 때 예측 일치도
• Sparsity: 설명의 크기 (GDL program 수, 또는 grounding된 subgraph 크기)
• Stability / Consistency: 유사한 입력에 대해 유사한 설명이 나오는가
• Plausibility: 도메인 ground truth motif와의 일치도
• Human evaluation: 전문가의 가독성·유용성 평가

4. 후보 벤치마크 (Candidate Benchmarks)

실세계 분자 그래프

• MUTAG — NO₂, aromatic ring이 known ground-truth motif
• Mutagenicity, BBBP, BACE, NCI1, PTC (MR), PROTEINS
• OGB-MolHIV, OGB-MolPCBA — 대규모 평가용
• ClinTox, Tox21, SIDER — 독성/부작용 예측

합성 벤치마크 (ground-truth motif가 명시된 설명 전용)

• BA-2Motifs — house-shape vs. 5-cycle motif
• BA-Shapes, BA-Community, Tree-Cycles, Tree-Grids
• SpMotif — spurious correlation이 통제된 설명 평가
• MNIST-75sp, Graph-SST2/SST5

Heterophilic / 표현력 한계 스트레스 테스트

• Cora, Citeseer, Pubmed — homophilic citation network
• Wisconsin, Texas, Cornell — heterophilic web graph

프로그램 분석 / 보안

• Devign, Big-Vul, Reveal — C 취약점 탐지 code property graph
• Joern / CPG

사기 / 금융

• Elliptic Bitcoin, YelpChi, DGraph-Fin

Explanation 평가 전용 벤치마크 스위트

• GraphXAI [Agarwal et al., NeurIPS 2022]
• SHAPEGGen [Agarwal et al., 2023]
• TUDataset [Morris et al., 2020]

5. 후보 베이스라인 (Candidate Baselines)

5.1 Post-hoc: Mask / Perturbation 기반

• GNNExplainer [Ying et al., NeurIPS 2019]
• PGExplainer [Luo et al., NeurIPS 2020]
• GraphMask [Schlichtkrull et al., ICLR 2021]
• GNN-LRP / Excitation BP [Schnake et al., IEEE TPAMI 2022]
• DEGREE [Feng et al., ICLR 2022]

5.2 Post-hoc: Search / Game-Theoretic 기반

• SubgraphX [Yuan et al., ICML 2021]
• SAME [Ye et al., NeurIPS 2023]
• GStarX [Zhang et al., NeurIPS 2022]

5.3 Post-hoc: Surrogate / Probabilistic 기반

• GraphLIME [Huang et al., IEEE TKDE 2022]
• PGM-Explainer [Vu & Thai, NeurIPS 2020]
• GraphChef [Müller et al., ICML IMLH 2023]

5.4 Post-hoc: Generative / RL 기반

• GEM (Gem) [Lin, Lan, Li, ICML 2021]
• RG-Explainer [Shan et al., NeurIPS 2021]
• OrphicX [Lin, Lan, Li, Chen, CVPR 2022]

5.5 Counterfactual Explanation

• CF-GNNExplainer [Lucic et al., AISTATS 2022]
• RCExplainer [Bajaj et al., NeurIPS 2021]
• CLEAR [Ma et al., NeurIPS 2022]
• GCFExplainer [Huang et al., WSDM 2023]

5.6 Intrinsic / Rationale-Based

• GSAT [Miao, Liu, Li, ICML 2022]
• GIB / IB-subgraph [Yu et al., NeurIPS 2022; Wu et al., ICLR 2022]
• DIR [Wu et al., ICLR 2022]
• ProtGNN [Zhang et al., AAAI 2022]
• SE-GNN [Dai & Wang, IEEE TKDE 2022]
• KerGNNs [Feng et al., AAAI 2022]

5.7 Global Explanation

• XGNN [Yuan et al., KDD 2020]
• GNNInterpreter [Wang & Shen, ICLR 2023]
• GLGExplainer [Azzolin et al., ICLR 2023]
• D4Explainer [Chen et al., NeurIPS 2023]

5.8 Concept-Based

• GCExplainer [Magister et al., 2021]
• GCI [Xuanyuan et al., ICML 2023]

5.9 Symbolic / Program-Based (GDL과 가장 밀접)

• PL4XGL [Jeon, Park, Oh, PLDI 2024] — GDL 언어의 원출처. Fidelity = 0 보장. 한계: neural GNN에 적용 불가, homophily 미기술, training 비효율. 저자들이 §8에서 GDL을 GNN 설명에 직접 활용할 것을 제안 — 본 연구의 핵심 motivation
• ProgNet [Anonymous, KDD’26 under review] — GDL vocabulary를 GNN 인코더와 결합한 intrinsic 설명
• Logic Explained Networks (LEN) [Ciravegna et al., AAAI 2023]

5.10 평가 프로토콜 관련

• GraphXAI [Agarwal et al., NeurIPS 2022]
• Amara et al., GraphLearn 2022 — “GraphFramEx”
• Faber et al., KDD 2021
• ROAR / RemOve-And-Retrain 스타일 faithfulness 평가

5.11 Survey

• Yuan, Yu, Gui, Ji, Explainability in GNNs: A Taxonomic Survey, IEEE TPAMI 2022
• Kakkad, Jannu, Sharma, Aggarwal, Medya, arXiv 2023
• Li, Zhou, Lin, Liu, Du, Zhu, arXiv 2022
• Longa et al., ACM CSUR 2024

평가 지표

• Fidelity(−) / Fidelity(+)
• Sparsity: 설명 크기
• Accuracy on ground-truth motifs: 합성 데이터에서 motif recall/precision
• Stability, Consistency, Contrastivity, Plausibility
• Human evaluation: 전문가 가독성·유용성

연구 지형 요약 (Research Landscape Summary)

GDL 기반 GNN explanation은 interval-aware 설명 언어의 표현력과 dataset-level 재사용성을 모두 확보하면서도, 임의의 사전 학습 GNN에 적용 가능한 post-hoc 프레임워크 영역을 메운다.

GDL 확장 방향 (Open Problems)

• Homophily / heterophily: 이웃 label 분포 기술
• Aggregate 술어: “oxygen > chlorine 개수”, “이웃 degree 평균 ≥ k”
• Recursive / path 제약: RPQ 스타일 경로 술어로 message-passing 깊이 표현
• 변수 간 비교: x.f ≤ y.f 같은 symbolic 비교
• Soft activation: 이진 activation을 확률적으로 완화하여 미분 가능한 post-hoc 최적화 지원