길리랩blog

스펙트럴 클러스터링과 DeepWalk로 그래프 구조 활용하기

스펙트럴 클러스터링과 DeepWalk의 원리, 그래프 군집화와 임베딩 활용 방식, 운영 시 고려할 확장성·평가 기준을 정리한다.

2026-08-14 · 최초 발행 2024-04-29

그래프 구조를 군집과 벡터로 다루는 방법

대규모 그래프에서 커뮤니티 구조를 찾거나 링크 예측의 정밀도를 높이려면, 관계 자체를 군집 결정에 쓰거나 모델 입력용 벡터로 바꿔야 한다. 스펙트럴 클러스터링은 라플라시안의 고유공간을 활용해 정점을 군집으로 나누고, DeepWalk는 무작위 보행과 스킵그램 학습으로 정점 표현을 만든다.

전자는 분리와 경계의 해석에 적합하다. 후자는 분류, 링크 예측, 검색처럼 여러 다운스트림 태스크에 재사용할 수 있는 범용 피처를 제공한다.

스펙트럴 클러스터링은 그래프 라플라시안의 저차 고유벡터 공간으로 정점을 옮긴 뒤, 그 유클리드 공간에서 k-means 같은 전통적 클러스터링을 수행한다. 라플라시안은 L = D − A로 나타낼 수 있고, 대각정규화 형태는 L_sym = I − D^−1/2 A D^−1/2다. 무향 그래프에서는 양의 반정정부호 성질을 가진다.

DeepWalk는 그래프에서 다수의 짧은 무작위 보행 시퀀스를 만든 뒤, 자연어 처리의 skip-gram with negative sampling으로 정점 임베딩을 학습한다. 이렇게 얻은 밀집 벡터는 지역 연결성과 동시출현 문맥을 보존하며, 임의의 다운스트림 모델에 입력할 수 있다.

라플라시안과 무작위 보행이 만드는 서로 다른 결과

스펙트럴 클러스터링의 흐름은 그래프 구성, 라플라시안 계산, 고유벡터 k개 추출, k-means 적용으로 이어진다. 불균형한 차수를 가진 그래프에서는 정규화 라플라시안이 안정성을 높일 수 있다. 병목은 희소 n×n 라플라시안의 부분 고유분해이며, 복잡도는 O(nnz(A)·k·t)다. Lanczos/ARPACK, Nyström, 랜덤화 SVD를 이용해 근사 속도를 높일 수 있다.

DeepWalk는 각 노드에서 길이 t의 무작위 보행을 r회 생성하고, 윈도우 w 안의 공기 단어를 예측하는 스킵그램(NS)을 학습한다. 결과는 d차 임베딩이다. walk length(t), walks per node(r), window size(w), embedding dim(d), negatives(k)가 주요 하이퍼파라미터이며, 멀티프로세스 샘플링과 Word2Vec 스레딩으로 스케일아웃할 수 있다.

군집 자체를 설명해야 한다면 스펙트럴 클러스터링의 출력 레이블이 더 직관적이다. 군집 수(k)와 고유값 간격(eigengap)을 통해 구조를 파악할 수도 있다. 반대로 여러 모델과 태스크에서 피처를 공유해야 한다면 DeepWalk 임베딩의 재사용성이 유리하다. 초대형 그래프에서는 근사나 분산 처리 없이 스펙트럴 방식의 비용이 커질 수 있고, DeepWalk는 선형적 샘플링과 Word2Vec 최적화로 처리하기 쉽다.

그래프를 준비할 때는 다중간선과 가중치를 정규화하고 고립 노드를 어떻게 처리할지 정해야 한다. 방향 그래프는 무향화하거나 쌍대화하는 선택지가 있다. 군집 결과는 NMI, ARI, Modularity, Silhouette로 평가할 수 있으며, 임베딩은 링크 예측 AUC, 노드 분류 F1, 리드-타임, 메모리로 평가한다.

커뮤니티 운영부터 이상 탐지까지

통신·소셜·협업 네트워크에서는 스펙트럴 클러스터링으로 커뮤니티를 도출해 리텐션 캠페인 타게팅에 활용할 수 있다. 라우팅이나 권한 설정에서도 커뮤니티 기반 정책은 정책 구성을 단순화하는 데 쓰인다.

추천과 링크 예측에서는 DeepWalk 임베딩을 최근접 이웃 탐색이나 점수화 모델에 넣어 콜드스타트를 완화할 수 있다. A/B 테스트에서 CTR과 Conversion 개선을 검증하고, 샌드박스의 오프라인 AUC를 온라인 KPI와 연결하는 흐름도 가능하다.

권한 그래프나 결제 그래프에서는 임베딩 거리와 재구성 오류를 이상치 점수로 사용할 수 있다. 스펙트럴 임계값을 기반으로 소수 군집을 찾으면 내부침해 조기 경보에도 연결할 수 있다.

⤢✕예외처리입력: 그래프 G(V,E)전처리: 중복/가중치 정규화,고립 노드 처리분기스펙트럴: L 계산→상위 k고유벡터→k-meansDeepWalk: 무작위 보행생성→Skip-gram(NS) 학습출력1: 군집 레이블출력2: 노드 임베딩 R^{|V|×d}다운스트림: 커뮤니티분석/정책다운스트림: 분류/링크예측/검색연결성 확인, 수치 불안정 시정규화/근사 사용
관점 스펙트럴 클러스터링 DeepWalk
성능(정확도) 명확한 커뮤니티 구조에서 군집 품질 우수 다양한 태스크에서 일관된 상향, 링크 예측/분류 강점
확장성 대규모 시 근사/분산 필요 샘플링·Word2Vec로 선형 확장 용이
일관성 하이퍼파라미터 영향 중간, eigengap로 k 선택 가능 하이퍼파라미터 민감, 재현성 위해 시드·학습률 고정 필요
안정성 정규화 라플라시안으로 수치 안정성 제고 고차수 허브 편향 가능, 네거티브 샘플링으로 보정
운영 편의 출력이 레이블로 직관적, 해석 쉬움 임베딩 재사용·캐싱 용이, 다목적 활용성 높음

카라테 클럽 그래프로 확인하는 스펙트럴 군집

환경/버전

  • Python 3.10+, numpy 1.24+, networkx 3.2+, scikit-learn 1.3+, gensim 4.3+

무향 가중 그래프와 메모리 내 처리를 가정한다. 더 큰 그래프에서는 샘플링이나 근사를 검토한다.

# python -m pip install numpy networkx scikit-learn
import networkx as nx
import numpy as np
from sklearn.cluster import KMeans
from scipy.sparse import csgraph
from scipy.sparse.linalg import eigsh

# 1) 데이터 준비
G = nx.karate_club_graph()

# 2) 인접행렬과 정규화 라플라시안
A = nx.to_scipy_sparse_array(G, dtype=float, format='csr')
L = csgraph.laplacian(A, normed=True)

# 3) 고유벡터 k개 추출 (가장 작은 고유값부터)
k = 2
vals, vecs = eigsh(L, k=k, which='SM')  # ARPACK 사용, 희소행렬 대응

# 4) 행 단위 정규화 후 k-means
X = vecs / (np.linalg.norm(vecs, axis=1, keepdims=True) + 1e-12)
labels = KMeans(n_clusters=k, n_init='auto', random_state=42).fit_predict(X)

# 5) 결과 확인
print({node: int(labels[i]) for i, node in enumerate(G.nodes())})

그래프가 비연결 상태라면 컴포넌트별로 처리하거나 정규화 라플라시안 사용을 검토한다. 수치적으로 불안정하면 eigsh의 tol을 높이고 maxiter를 조정하며, k에 비해 충분한 갭이 있는지 확인한다.

무작위 보행으로 학습하는 DeepWalk 임베딩

# python -m pip install numpy networkx gensim
import random
import networkx as nx
from gensim.models import Word2Vec

random.seed(42)

G = nx.karate_club_graph()

def random_walk(G, start, walk_length=40):
    walk = [start]
    for _ in range(walk_length - 1):
        cur = walk[-1]
        nbrs = list(G.neighbors(cur))
        if not nbrs:
            break
        walk.append(random.choice(nbrs))
    return list(map(str, walk))  # Word2Vec는 str 토큰 기대

# 1) 보행 시퀀스 생성
walks = []
num_walks = 10
walk_length = 40
nodes = list(G.nodes())
for _ in range(num_walks):
    random.shuffle(nodes)
    for v in nodes:
        walks.append(random_walk(G, v, walk_length))

# 2) Skip-gram(NS) 학습
model = Word2Vec(
    sentences=walks,
    vector_size=64, window=5,
    sg=1, negative=5,
    min_count=0, workers=4,
    epochs=5
)

# 3) 임베딩 추출
emb = {int(k): model.wv[k] for k in model.wv.key_to_index.keys()}

# 4) 간단 군집화/최근접 이웃 테스트
from sklearn.cluster import KMeans
import numpy as np
X = np.vstack([emb[i] for i in sorted(emb)])
labels = KMeans(n_clusters=2, n_init='auto', random_state=42).fit_predict(X)
print(labels[:10])

고차수 허브 편향이 문제라면 edge sampling 가중치를 균등화하거나 walk restart를 도입할 수 있다. 재현성이 필요하면 random.seed와 workers=1을 설정하고 gensim의 hash 시드를 고정한다.

그래프 규모와 운영 제약에 맞춘 선택

가중치 스케일은 정규화하고 self-loop 사용 여부를 명시한다. 방향 그래프는 양방향화하거나 전이확률 행렬로 변환할 수 있다. 고립 노드는 별도 클러스터로 분리하거나 임베딩 평균 또는 영벡터를 할당한다.

스펙트럴 방식은 Nyström 근사로 표본 노드 c개를 사용해 O(nc^2)로 처리할 수 있다. Lanczos 블록 반복이나 그래프 파티셔닝 후 메타-그래프 병합도 선택지다. DeepWalk에서는 보행 샘플링을 멀티프로세스로 수행하고, Word2Vec 네거티브 샘플링과 subsampling으로 빈도 편향을 제어한다.

즉시 해석할 수 있는 세그먼트 운영이 목적이면 스펙트럴 클러스터링이 먼저다. 여러 목적의 피처 허브를 구축한다면 DeepWalk가 더 맞는다. DeepWalk 임베딩에 k-means나 스펙트럴 방식을 후단으로 적용하면 군집 안정성과 다운스트림 성능을 함께 확보할 수 있다.

커뮤니티 라벨이 있는 데이터를 기준으로 단순 k-means on degree/attributes와 비교하면 NMI/ARI 1530%p 개선을 기대할 수 있다. 행렬분해/공통이웃 대비 링크 예측 AUC는 0.050.15p 개선되고, 추천 CTR은 38% 개선 사례가 보고됐다. Nyström/Lanczos를 도입하면 메모리를 3060% 절감하고 학습 시간을 40~70% 단축할 수 있다.

이 접근은 구조적 패턴을 가시화해 이해도를 높이고 비정상 행위 탐지의 민감도를 높인다. 임베딩을 재사용하면 팀 간 피처 중복 구축을 줄이고 실험 주기를 단축할 수 있다.

스펙트럴 클러스터링DeepWalk그래프 임베딩커뮤니티 탐지링크 예측