지식 그래프 엣지 가중치, 무엇으로 잴 것인가: Co-occurrence vs Jaccard vs NPMI

들어가며: 엣지를 얼마나 굵게 그릴 것인가

뉴스 키워드 지식 그래프를 만들다 보면 결국 한 가지 질문에 부딪힙니다. "두 키워드 사이의 선(edge)을 얼마나 굵게 그릴 것인가?" 우리 그래프 UI에는 Co-occur, NPMI, Jaccard 세 가지 토글이 있는데, 같은 데이터라도 어떤 지표를 켜느냐에 따라 그래프의 "모양"이 완전히 달라집니다. 이 글에서는 세 지표가 각각 무엇을 재는지, 왜 다른 결과를 내는지를 정리합니다.

한 줄 요약 (BLUF)

세 지표는 모두 "두 노드가 얼마나 함께 등장하는가"를 재지만, 기준선(null model)을 무엇으로 두느냐가 핵심 차이입니다.

Co-occurrence는 날 것의 빈도를 셉니다.
Jaccard는 합집합 대비 겹침 비율을 봅니다.
NPMI는 우연(독립 가정) 대비 초과 연관을 측정합니다.

결정적 차이는 NPMI만 "우연이라면 이만큼 함께 나왔을 것"이라는 확률적 귀무 모델(null model)을 갖는다는 점입니다. 우리 UI 설명에 적힌 "인기 키워드일수록 굵음(허브 편향)"이라는 문구가 바로 Co-occurrence의 약점을 정확히 지적하고 있고, 이를 보정하려고 NPMI와 Jaccard가 함께 제공되는 구조입니다.

0. 공통 전제: 무엇을 "문맥(context)"으로 볼 것인가

세 지표를 비교하려면 먼저 단위를 맞춰야 합니다. 우리 그래프는 "같은 기사에 함께 등장"을 동시 출현(co-occurrence)의 단위로 삼습니다. 즉 문맥(context) = 기사 1건입니다.

정의 (전체 기사 수 = N)
─────────────────────────────────────
count(x)      : 키워드 x가 등장한 기사 수
count(y)      : 키워드 y가 등장한 기사 수
count(x, y)   : x와 y가 "같은 기사"에 함께 등장한 기사 수
─────────────────────────────────────
P(x)   = count(x) / N
P(y)   = count(y) / N
P(x,y) = count(x, y) / N

이 네 가지 값(N, count(x), count(y), count(x,y))만 있으면 세 지표를 모두 계산할 수 있습니다. 차이는 이 재료를 어떻게 조합하느냐에서 나옵니다.

1. Co-occurrence (동시 출현 빈도)

Intuition

두 노드가 같은 문맥(여기서는 기사) 안에 함께 나타난 횟수 그 자체입니다. 가장 단순하고 해석이 직관적입니다 — "이 둘은 같은 기사에 48번 같이 나왔다." 하지만 빈출 키워드가 모든 것과 함께 나오는 문제에 그대로 노출됩니다.

Mathematical Formulation

\text{Cooc}(x, y) = \text{count}(x, y)

범위: $[0, \infty)$ , 비정규화(unnormalized)
대칭(symmetric): $\text{Cooc}(x,y) = \text{Cooc}(y,x)$

특성

삼성전자, AI처럼 거의 모든 기사에 등장하는 고빈도 키워드는 어떤 키워드와도 높은 co-occurrence를 갖습니다. 그래서 빈도 편향(frequency bias) 때문에 진짜 의미 있는 관계와 그냥 흔해서 같이 나온 관계를 구분하지 못합니다. UI 설명의 "인기 키워드일수록 굵음(허브 편향)"이 바로 이 현상입니다 — 허브 노드가 중앙에 뭉치고 선이 굵어지지만, 그 굵기가 곧 의미는 아닙니다.

2. Jaccard (자카드 유사도)

Intuition

"두 노드가 등장한 기사들을 모두 합쳤을 때, 그중 둘 다 등장한 비율은 얼마인가?"를 봅니다. 집합 겹침(set overlap) 관점의 지표입니다. 직관적으로는 "두 키워드의 사용 범위(coverage)가 얼마나 포개지는가"를 묻습니다.

Mathematical Formulation

$x$ 가 등장한 기사 집합을 $X$ , $y$ 가 등장한 기사 집합을 $Y$ 라 하면:

\text{Jaccard}(x, y) = \frac{|X \cap Y|}{|X \cup Y|} = \frac{\text{count}(x, y)}{\text{count}(x) + \text{count}(y) - \text{count}(x, y)}

범위: $[0, 1]$ , 대칭
분모(합집합)가 정규화 역할을 하므로, 한 노드가 너무 많은 기사에 등장하면 점수가 희석됩니다.

특성

빈도 정규화는 되지만, "우연 대비"라는 개념이 없습니다. 단순히 겹친 비율만 보기 때문에, 두 키워드가 통계적으로 독립인 경우에도 0이 아닌 값을 줄 수 있습니다(아래 Case B 참고). 이것이 NPMI와 갈라지는 결정적 지점입니다.

3. NPMI (Normalized Pointwise Mutual Information)

Intuition

"두 노드가 독립이라면 우연히 이만큼 함께 나왔을 텐데, 실제로는 그보다 얼마나 더(혹은 덜) 함께 나오는가?"를 측정합니다. UI 설명("기대(우연) 대비 함께 나오는 정도, 우연한 동시등장 제거")과 정확히 일치하는 정의입니다.

Mathematical Formulation

먼저 PMI(Pointwise Mutual Information)부터 봅니다:

\text{PMI}(x, y) = \log \frac{P(x, y)}{P(x)\,P(y)}

여기서 분모 $P(x)P(y)$ 가 독립 가정 하의 기대 동시 출현 확률, 즉 귀무 모델입니다. "둘이 아무 관계 없이 각자 등장한다면 우연히 겹칠 확률"을 뜻합니다. 다만 PMI는 범위가 무한하고, 희귀 쌍(rare pair)에 과도하게 큰 값을 주는 단점이 있습니다.

이를 $-\log P(x,y)$ 로 나눠 $[-1, 1]$ 범위로 정규화한 것이 NPMI입니다:

\text{NPMI}(x, y) = \frac{\text{PMI}(x, y)}{-\log P(x, y)}

특성

$+1$ : 항상 함께 등장 (완전한 연관)
$\ \ 0$ : 독립 (딱 우연 수준)
$-1$ : 절대 함께 등장하지 않음 (상호 배척)

빈출 노드와의 "흔한 동시등장"은 기대치 $P(x)P(y)$ 가 크기 때문에 자동으로 깎여 나가고, 드물지만 특이하게 강한 관계가 부각됩니다. 또한 세 지표 중 유일하게 음의 관계(서로 배척)를 표현할 수 있습니다.

한눈에 보는 비교

구분	Co-occurrence	Jaccard	NPMI
측정 대상	날 것의 동시 빈도	합집합 대비 겹침 비율	우연(독립) 대비 초과 연관
수식 핵심	$\text{count}(x,y)$	$\frac{\lvert X \cap Y \rvert}{\lvert X \cup Y \rvert}$	$\frac{\log[P(x,y)/P(x)P(y)]}{-\log P(x,y)}$
범위	$[0, \infty)$	$[0, 1]$	$[-1, 1]$
귀무 모델(null model)	없음	없음	독립 가정 $P(x)P(y)$
빈도 편향(허브 편향)	매우 큼	완화됨	완화됨
음의 관계(반발) 표현	불가	불가 (0이 최소)	가능 ( $-$ 값)
희귀 쌍 민감도	낮음	중간	높음 (저빈도 시 극단값)
해석 한 줄	"몇 번 같이 나왔나"	"얼마나 겹치나"	"우연보다 얼마나 특이한가"

핵심을 보여주는 두 가지 예시

전체 기사 수 $N = 1000$ 이라고 가정합니다.

Case A — 빈도 편향 확인 (raw count가 속는 경우)

흔한 단어 하나를 섞어보겠습니다.

the(900회) — neural(50회): 동시 48회
neural(50회) — network(60회): 동시 45회

지표           the–neural        neural–network
─────────────────────────────────────────────────
Co-occurrence  48                45        ← raw count는 the쌍이 더 강해 보임 (오판)
Jaccard        48/902 ≈ 0.053    45/65 ≈ 0.69
NPMI           ≈ 0.02            ≈ 0.87    ← neural–network를 강한 관계로 정확히 식별

Co-occurrence는 빈출어 the 때문에 오판하지만, Jaccard와 NPMI는 둘 다 neural–network를 옳게 잡아냅니다. 여기까지만 보면 "Jaccard로 충분하지 않나?" 싶지만, 다음 예시가 둘을 갈라놓습니다.

Case B — Jaccard와 NPMI가 갈라지는 경우 (귀무 모델의 유무)

$x$ (500회), $y$ (500회), 동시 250회
기대 동시 출현 = $P(x) \times P(y) \times N = 0.5 \times 0.5 \times 1000 = 250$ → 정확히 우연 수준(독립)

지표      값        해석
─────────────────────────────────────────────────────
Jaccard   0.333    "33% 겹침" → 어느 정도 연관 있어 보임 (오해 소지)
NPMI      0.000    "딱 우연 수준" → 통계적으로 독립이라고 정확히 판정

같은 데이터인데 Jaccard는 0.33으로 연관처럼 보이고, NPMI는 0으로 독립이라고 말합니다. Jaccard는 겹침의 절대 비율만 보고, NPMI는 그 겹침이 기대치를 넘는지를 봅니다. 이것이 "귀무 모델이 있느냐 없느냐"의 실질적 결과입니다.

정리: 언제 무엇을 쓰나

Co-occurrence — 빠른 탐색용 baseline. 데이터 감을 잡거나 "절대 노출량"이 궁금할 때. 단, 허브 편향이 그대로 드러나므로 최종 가중치로는 부적합합니다.
Jaccard — "두 개념의 사용 범위가 얼마나 겹치는가"가 본질인 질문(태그 유사도, 추천, 클러스터링)에 적합. 단 우연 여부는 판정하지 못합니다.
NPMI — "특이하고 의미 있는 관계만 남기고 싶다", "음의 관계(서로 배척)도 보고 싶다", "엣지 가중치를 우연 제거 기준으로 주고 싶다"면 가장 적합합니다. 다만 저빈도 쌍에서 노이즈가 커지므로 최소 동시 출현 횟수(count threshold)를 함께 거는 것이 일반적입니다.

우리 지식 그래프 UI의 의도("우연한 동시등장 제거, 의미 있는 특이 관계 강조")를 기준으로 하면, NPMI를 기본값으로 두되 저빈도 엣지를 잘라내는 cutoff를 함께 적용하는 구성이 가장 잘 맞습니다. Co-occur는 탐색용, Jaccard는 "키워드 사용 범위 비교"라는 다른 관점을 보고 싶을 때 보조로 켜는 식이 자연스럽습니다.

이 글에서 다루지 못한 세부 주제

NPMI는 강력하지만 저빈도 쌍에서 극단값을 내는 약점이 있어, 실무에서는 이를 완화하는 스무딩 기법을 함께 씁니다. 이 글에서는 다루지 않았으나 같은 맥락에서 이어지는 두 주제를 남겨 둡니다.

Smoothed PMI — 분모에 $\alpha$ 를 더해 희귀 쌍의 분산을 억제하는 기법.
Context distribution smoothing — $P(y)^{0.75}$ (word2vec에서 차용)으로 빈출어의 영향력을 완만하게 보정하는 기법.