Interpretable Prototype-based Graph Information Bottleneck (PGIB) 논문 읽기

 

 한 줄 요약

ProtGNN 같은 프로토타입 기반 XAI는 그래프 “전체 임베딩”으로 프로토타입을 학습해서, 진짜 중요한 서브구조(예: MUTAG의 NO2)를 놓치고 흔한 구조(예: ring)에 끌리는 문제가 있다.

PGIB는 Information Bottleneck(IB) 방식으로 라벨에 필요한 핵심 subgraph GsubG_{sub}Gsub​만 남기고, 그걸 기준으로 프로토타입을 학습하게 만들어서 설명도 좋아지고 정확도도 올라가게 만든 프레임워크이다.

 

---

1. 기존 방법(ProtGNN)의 구체적인 문제: “프로토타입이 ‘흔한 구조’를 대표해버림”

ProtGNN은 “그래프 전체 임베딩” zG를 만든 뒤, 프로토타입 벡터들과 유사도를 비교해서 예측하고, 프로토타입을 가장 가까운 training graph로 projection해서 설명한다.
근데 이 방식의 함정이 뭐냐면:

• 그래프에 자주 등장하는 구조(링 같은) = 전체 임베딩에 크게 반영된다.
• 하지만 라벨 결정적인 국소 구조(MUTAG의 NO2)는 전체 임베딩에서 묻힐 수 있다.

그래서 ProtGNN이 뽑은 prototype graph Gp가 ring 위주로 잡히고 NO2를 빼먹는 사례가 논문 Fig.1에서 바로 나온다.

 

PGIB가 해결하려는 핵심 질문은 이거다:

“프로토타입이 그래프 전체가 아니라 라벨에 중요한 subgraph만 보고 학습되면 안 되나?”

---

2. PGIB의 전체 아키텍처 흐름

논문 Fig.2 흐름을 말로 풀면 이렇게 진행된다. 

 

1. GNN encoder로 노드 임베딩 hi​ 생성
2. Subgraph extraction layer에서 “중요한 노드는 살리고, 덜 중요한 노드는 노이즈로 망가뜨림”
3. 그 결과 노드 표현을 pooling 해서 subgraph embedding zGsub 생성
4. Prototype layer에서 zGsub​​ ↔ 각 prototype zGpm​ 유사도 계산
5. 유사도 벡터 + zGsub​​로 분류 (prediction layer)
6. 학습 중간중간 프로토타입 merge로 중복 줄임
7. 마지막에 프로토타입 projection(MCTS) 해서 사람이 볼 수 있는 실제 subgraph로 바꿔준다.

---

3. 수식이 “흐름”을 어떻게 강제하는지 (핵심은 Eq.4 ~ Eq.16)

3.1 IB 기본기: “라벨 정보는 남기고, 입력 정보는 버려라”

IB의 기본 형태는:

• I(Y;Z)는 크게(라벨 예측에 유용)
• I(X;Z)는 작게(불필요 정보 압축)

그래프 버전(GIB)은:

즉 “라벨에 필요한 subgraph만 남겨라”가 목표이다. (Eq.3)

 

---

3.2 PGIB가 한 “핵심 트릭”: IB 목적에 프로토타입을 끼워 넣음

PGIB는 Eq.3을 그냥 쓰지 않고, 프로토타입 GpG_pGp​가 학습에 개입하도록 체인룰로 분해한다:

(Eq.4)

 

여기서 중요한 해석은 이거다:

• βI(G;Gsub): subgraph를 작게/핵심만 만들기
• −I(Y;Gsub,Gp): subgraph + prototype이 라벨 예측에 도움 되게 하기
• I(Y;Gp∣Gsub): 이걸 그대로 다 쓰면 복잡해지는데, 논문은 여기서 “해석가능성 때문에” 일부 항을 빼고 핵심만 최적화한다.(뒤에서 설명)

---

4. “중요한 subgraph만 남기는 방법”이 수식으로 어떻게 구현되나?

4.1 노드별 확률로 “살릴지/노이즈로 죽일지” 결정 (Eq.5)

각 노드 임베딩 hi에 대해:

• 중요도 확률 pi=σ(MLP(hi))
• λi∼Bernoulli(pi)
• 최종 표현:

(Eq.5)

 

직관:

• λi=1\lambda_i=1λi​=1이면 “이 노드는 중요 → 원래 정보 유지”
• λi=0\lambda_i=0λi​=0이면 “안 중요 → 노이즈로 대체”

즉, 중요한 노드/구조만 정보가 살아남도록 학습되는 구조이다.

4.2 I(G;Gsub)는 직접 계산 못 하니 upper bound를 최소화 (Eq.6)

논문은 I(G;Gsub)I(G;G_{sub})I(G;Gsub​)의 upper bound를:

로 두고 (Eq.6) 이걸 최소화해.

Interpretable Prototype-based G…

이게 “IB 압축”의 구현체라고 이해할 수 있다.:

• 너무 많은 노드가 살아남으면 I(G;Gsub) 커짐 → loss 커짐
• 핵심만 남기면 loss 작아짐

그리고 노이즈 주입 후, pooling(max/sum 등)으로:

• zGsub​​를 만든다고 명시된다.

 

---

5. 프로토타입은 “subgraph에서 뽑는 게 아니라”, 학습되는 대표 벡터다

5.1 프로토타입 유사도 함수 (Eq.7)

​

(Eq.7)

 

이게 “서브그래프 임베딩이 이 프로토타입과 얼마나 비슷한가”를 수치로 만들어주는 함수고,
이 유사도들이 모여서 “유사도 벡터 r”가 된다. (Eq.12~prediction으로 연결)

 

5.2 라벨 예측은 결국 cross entropy로 구현됨 (Eq.8, Eq.12)

논문은

• I(Y;Gsub,Gp)를 직접 maximize 하기 어렵다 → lower bound로 바꿔서
• 결국 “분류 loss 최소화”로 연결된다고 보여준다. (Eq.8)

 

그리고 prediction layer에서:

• 유사도 벡터 r + zGsubz​​를 linear+softmax로 예측하고
• cross entropy를 Lcls​로 둔다. (Eq.12)

 

---

6. “subgraph ↔ prototype” 결합을 강하게 만드는 핵심 항: I(Gsub;Gp)

6.1 논문이 중요한 선택을 함: I(Y;Gp∣Gsub)를 분해하고 일부를 제외

(Eq.9)

 

논문이 말하는 포인트:

• I(Gp;Y,Gsub)까지 넣으면 prototype이 오히려 해석이 나빠질 수 있어서
  → 이 항은 학습에서 제외한다.
• 대신 −I(Gsub;Gp)만 최적화해서
  → subgraph 정보가 prototype으로 잘 전달되게 만듦

이게 PGIB의 “설명 개선”을 만드는 핵심 선택 중 하나이다.

 

6.2 그걸 구현하는 두 가지 방법 (Eq.10 variational / Eq.11 contrastive)

• PGIB: variational bound

(Eq.10)

 

• PGIBcont: contrastive(InfoNCE 느낌)

(Eq.11)

 

논문 실험에서도 PGIBcont가 더 잘 나오는 경향이 있다고 말한다. (Table 1 근처 설명)

 

---

7. “해석가능성 안정화”: merge, projection, connectivity

7.1 프로토타입 merge (Eq.13)

프로토타입이 많으면 중복이 생기고 설명이 지저분해질 수 있으니, “비슷한 프로토타입끼리 합침”.

(Eq.13)

 

말로 하면:

• “모든 training subgraph에 대해 두 프로토타입의 유사도 반응이 거의 같으면”
• 그 둘은 의미가 비슷하니 하나로 merge해라.

논문은 상위 ξ%가장 비슷한 쌍을 합친다고 했고, 실험 설정에서 30% merge 언급한다.

 

7.2 프로토타입 projection (Eq.14) + MCTS

프로토타입은 벡터라서 사람이 못 봄 → 그래서 “같은 클래스 training subgraph 중에서 가장 가까운 subgraph”로 바꿔준다:

(Eq.14)

 

그리고 이걸 찾을 때 MCTS로 training subgraph들을 탐색한다고 명시되어있다.

 

7.3 connectivity loss (Eq.15)

마스크가 들쑥날쑥하면 GsubG_{sub}Gsub​가 조각나서 해석이 안 좋아질 수 있음 → 그래서 “서브그래프가 연결되고 compact해지게” 유도하는 loss:

​

(Eq.15)

 

---

8. 최종 목적함수는 이렇게 합쳐짐 (Eq.16)

​

(Eq.16)

 

여기서 각각의 의미를 “행동”으로 번역하면:

• Lcls=​: 분류는 잘해라
• α1LMI1=: subgraph를 너무 크게 만들지 말자(압축)
• α2LMI2=​: subgraph 정보가 prototype에 잘 반영되게 해라(정렬)
• α3Lcon=​: subgraph를 끊어먹지 말고 연결되게 해라

논문 실험 설정에서 α1=0.0001, α2=0.01∼0.1, α3=5같은 값도 구체적으로 적혀 있다.

 

---

9. PGIB의 “개선점”을 딱 3개로 정리하면

개선점 1) “프로토타입이 전체 그래프가 아니라 핵심 subgraph에 기반하게 됨”

ProtGNN의 가장 큰 약점(전체 임베딩 때문에 NO2 같은 핵심이 묻힘)을
IB 기반 subgraph 추출(Eq.5~6)로 해결하였다.

 

→ 결과적으로 Fig.1(b)처럼 NO2가 포함된 Gsub​를 찾고 그 기반으로 프로토타입이 학습되었다

 

개선점 2) “설명(해석)과 성능을 동시에 올림”

Table 1에서 PGIB/PGIBcont가 기존 GNN/ProtGNN/IB 계열(GIB/VGIB/GSAT)보다 전체적으로 정확도가 좋다고 보고함.

또 Fidelity 지표(Table 2)에서도 PGIBcont가 좋은 편이고, merge까지 하면 더 좋아짐을 보여준다.

 

개선점 3) “설명 복잡도 줄이기(merge) + 사람이 볼 수 있게 만들기(projection)”

• merge(Eq.13)로 중복 prototype 제거 → 설명이 덜 지저분해짐
• projection(Eq.14)로 prototype을 실제 training subgraph로 바꿔서 “이게 이 프로토타입이다”라고 말할 수 있게 됨
• connectivity(Eq.15)로 subgraph가 연결되게 만들어 시각적으로도 납득 가능하게 함

---

10. 개인적으로 느낀 이 논문의 포인트

처음 GNN 논문이면 수식에 빠지기 쉬운데, 이 논문은 이렇게 보면 그나마 이해하기 편한 것 같다.

1. 왜 ProtGNN이 실패하는지 (Fig.1: ring vs NO2)

   

2. Fig.2 아키텍처를 말로 설명할 수 있게 만들기

   

3. Eq.16에서 loss 항 4개를 각각 “행동”으로 번역하기
4. merge/projection/connectivity가 “해석 안정화”를 어떻게 보장하는지 보기

 

 

수식 유도(appendix)는 처음엔 굳이 안 따라가도 될 것 같다. 본문 Eq.5~16 의미만 제대로 잡으면 충분히 이해가능할 것 같다.