0) 오늘의 문제: “라벨 일부만 알 때, 나머지는 어떻게 예측?”
그래프에서 일부 노드만 라벨이 있고, 나머지 노드는 라벨이 없다고 하자. 목표는 라벨 없는 노드들의 라벨을 예측하는 것. 이 문제를 강의에서는 semi-supervised node classification이라고 부른다.
예시(강의 동기):
- 네트워크에서 어떤 노드들은 fraudster(사기) / trusted(신뢰)로 이미 라벨이 있고,
- 나머지 노드들의 라벨을 찾아내고 싶다.
1) 왜 그래프에서 “전파”가 먹히나? (상관관계의 근원)
강의의 큰 직관은 한 줄로 요약된다:
네트워크에는 상관관계(correlation)가 있고, 가까운 노드들은 같은 색/클래스일 가능성이 높다.
이 상관관계가 생기는 대표 원인 두 가지:
- Homophily(동질성): 비슷한 사람끼리 연결되는 경향 (“Birds of a feather flock together”)
- Influence(영향): 연결이 개인의 성향/행동을 바꾸는 힘 (예: 음악 취향 전파)
그래서 등장하는 네트워크적 귀납편향(inductive bias):
- Guilt-by-association: “라벨 X인 노드와 연결되어 있으면 나도 X일 가능성이 높다.”
2) Collective Classification 프레임워크 (오늘 3개 방법의 공통 골격)
강의는 이를 **collective classification(집단적 분류)**로 묶어서 본다:
연결된 노드들을 “동시에” 분류하는 관점.
확률적 관점 + 마코프 가정:
- Markov assumption: 노드 의 라벨 Y는 이웃 의 라벨에 의존한다.
그리고 집단적 분류는 보통 3단계로 설명된다:
- Local classifier: 피처만으로 초기 라벨 예측(네트워크 미사용)
- Relational classifier: 이웃 라벨/피처를 이용해 업데이트(네트워크 사용)
- Collective inference: (2)를 전체 그래프에 반복 적용해 수렴시키기
3) 방법 1: Probabilistic Relational Classifier (피처 없이 “이웃 평균”으로 전파)
3.1 아이디어
이 방법은 아주 “구조+라벨” 중심이다:
- 노드 피처를 안 쓴다.
- 라벨(또는 라벨 확률)을 이웃들의 가중평균으로 업데이트한다.
업데이트(클래스 CC에 대한 확률):
(간선 가중치가 있으면 AuvA_{uv}가 “영향력”이 된다.)
3.2 초기화 & 반복
- 라벨 있는 노드: 정답 라벨로 고정(0 또는 1)
- 라벨 없는 노드: 예를 들어 0.5로 초기화 후 반복 업데이트
3.3 장난감 예시 흐름(강의 그대로)
- 1회차에 node 3 업데이트 예:
이웃 확률 평균으로 P3≈0.17P_3\approx 0.17 계산
- 이어 node 4 업데이트 예:
이웃 확률 평균으로 P4≈0.42P_4\approx 0.42
- … 이런 식으로 회색 노드만 계속 업데이트한다.
반복이 진행되면 몇몇 노드는 값이 더 이상 변하지 않고 “수렴(converge)”한다. 강의 예시에서는 4 iterations 후 예측이 안정화되며, 최종적으로 (예시 그래프에서)
- 4,5,8,9는 label=1,
- 3은 label=0
으로 정리된다.
3.4 한계
- 항상 수렴 보장 X
- 노드 피처를 못 쓴다 → “내용 정보(단어, 속성)가 중요한 문제”에서는 아쉬움
4) 방법 2: Iterative Classification (피처 + 이웃라벨요약 zz 결합)
Relational classifier의 약점을 보완하는 확장판이다.
4.1 핵심 아이디어
노드 vv를 분류할 때 입력을 두 덩어리로 본다:
- 노드 자체 피처 fv
- 이웃 라벨을 요약한 벡터 Zv
그리고 분류기 2개를 쓴다:
- : 피처만 보고 예측 (초기 라벨 부여)
- : 피처 + 요약 zz 로 예측 (반복 업데이트용)
4.2 zz는 어떻게 만들까?
강의에서의 대표 예: 히스토그램/비율 기반 요약
(이웃 중 클래스 0/1이 몇 명인지, 몇 %인지 등)
방향 그래프(웹페이지 링크) 예시에서는 zz를 더 구체적으로:
- : incoming 이웃 중 클래스 0/1이 “하나라도” 있는지
- : outgoing 이웃 중 클래스 0/1이 “하나라도” 있는지
4.3 알고리즘 흐름(Phase 1 / Phase 2)
Phase 1 (학습 + 초기화)
- 라벨 노드로 학습
- 로 전체 노드에 초기 예측 라벨 부여
- 라벨 노드에서 (fv,zv)를 만들고 학습
Phase 2 (반복 업데이트)
- 현재 예측 라벨로 재계산
- 로 라벨 업데이트
- 라벨이 바뀌면 도 바뀌므로 1)~2) 반복
- 라벨이 더 이상 안 변하거나, 최대 반복 횟수 도달 시 종료
4.4 이 방법의 포인트
- Relational classification보다 “현실적”: 피처도 쓰고, 구조도 쓴다
- 하지만 여전히 반복 과정이므로:
- 수렴 보장 이슈가 있을 수 있어 “최대 반복 횟수”를 둔다(강의에서도 이 관행을 강조)
5) 방법 3: (Loopy) Belief Propagation (BP) = 메시지 패싱의 정석 형태
강의 마지막은 “메시지 패싱”을 가장 교과서적으로 보여주는 belief propagation이다.
5.1 워밍업: 메시지 패싱이란?
강의는 직관을 위해 “노드 개수 세기”를 메시지 패싱으로 설명한다.
- 체인(line graph)에서는 왼쪽에서 오른쪽으로 “현재까지 개수 + 1” 메시지를 전달하면 끝 노드가 총 노드 수를 안다.
- 트리(tree)에서는 리프→루트로 “자식 서브트리 합 + 1”을 올리면 루트가 전체 개수를 안다.
핵심은 항상 동일:
이웃에게서 메시지를 받고 → 로컬 규칙으로 합치고/변형하고 → 다시 메시지를 보낸다.
5.2 라벨 예측으로 일반화: prior + potential + message
BP를 쓰려면 구성요소를 정의한다.
- Label-label potential matrix ψ\psi
이웃한 두 노드 라벨 사이의 “궁합/상관”을 담는다. (동질성이 강하면 대각이 큼)
- Prior belief ϕ\phi
노드 ii가 라벨 yi일 사전 믿음(비례)
- Message mi→j
노드 ii가 노드 jj에게 보내는 “jj의 라벨 분포에 대한 의견”
5.3 메시지 업데이트(핵심 수식의 의미)
초기 메시지는 보통 1로 초기화하고, 반복하면서 업데이트한다.
직관적으로, 메시지는 이렇게 계산된다:
- 의 prior
- i의 다른 이웃들이 i에게 보낸 메시지들의 곱(단, j는 제외)
- 로 ii의 라벨이 j의 라벨에 주는 영향을 반영
- 그리고 에 대해 합(sum)쳐서 jj의 라벨별 메시지를 만든다
반복이 수렴하면, 각 노드의 belief는 보통
처럼 “내 prior × 이웃들이 나에게 준 메시지”로 계산한다.
5.4 왜 “Loopy”가 문제인가?
트리에서는 BP가 깔끔하게 맞아떨어진다. 하지만 실제 그래프에는 사이클이 많다.
사이클이 있으면:
- 서로 다른 경로로 온 메시지들이 사실 같은 정보를 공유할 수 있어 독립성 가정이 깨지고
- 그 결과 믿음이 “중복 증거”처럼 누적되어 **증폭(amplify)**되거나
- 아예 수렴하지 않을 수 있다.
그럼에도 쓰는 이유(현업 감각):
- 현실 그래프는 “트리처럼” 보이는 구간이 많거나
- 약한 상관 구조에서는 짧게 돌려도 꽤 괜찮은 휴리스틱으로 작동한다는 경험적 이유가 있다.
6) 세 방법 비교
- Relational classification: 피처 없이 이웃 확률 평균으로 전파 (단순·빠름·하지만 정보 부족)
- Iterative classification: 피처 ff + 이웃요약 zz를 함께 쓰고 Φ2\Phi_2를 반복 적용 (현실적 결합)
- Loopy BP: prior/potential을 두고 “진짜 메시지 패싱” 형태로 확률을 주고받음 (표현력↑, 수렴/증폭 이슈)
7) 이게 왜 GNN 들어가기 전 “중간 단계”인가?
이 강의의 숨은 목적은 이거다:
GNN은 결국 “이웃 정보를 모아(aggregate) 내 표현/예측을 업데이트한다”는 메시지 패싱 철학을, 학습 가능한 함수로 일반화한 것.
오늘 본 것들은 모두 “규칙 기반/확률 기반”으로 메시지를 설계했다면,
GNN에서는 메시지/집계/업데이트 함수 자체를 학습(learn) 한다고 생각하면 연결이 된다.