하이퍼그래프(Hypergraph) - 그래프를 확장한 집합적 연결 표현

그래프는 두 개의 점을 선으로 연결한다. Alice와 Bob이 친구면 두 사람을 선 하나로 잇는다. 간단하고 직관적이다.

 

문제는 현실이 항상 이렇지 않다는 것이다. 회의실 예약을 생각해보자.

 

Alice, Bob, Charlie가 월요일 오전 회의에 참석한다면, 이 관계를 어떻게 표현할까? 그래프로는 각자 회의와 따로 연결된다. 하지만 실제로는 세 사람이 동시에 있어야 회의가 성립한다. Alice 혼자서는 회의가 아니다.

이게 그래프의 근본적 한계다. 항상 둘씩만 연결하기 때문에 "함께"를 표현할 수 없다.

 

1. 그래프로 표현할 수 없는 것들

이 문제는 여러 곳에서 나타난다. 요리 레시피를 보자. 카레를 만들려면 감자, 당근, 양파, 고기가 모두 필요하다. 감자만으로는 안 된다. 넷이 함께 있어야 카레가 된다. 그래프로 그리면 각 재료가 따로따로 카레와 연결된다. "네 가지를 함께 넣어야 한다"는 핵심 정보가 사라진다.

 

수강신청도 마찬가지다. 자료구조 수업에 50명이 신청했다면, 이 50명을 어떻게 표현할까? 쌍으로 연결하면 1,225개 선이 필요하다. 문제는 개수가 아니다. "같은 수업을 듣는다"는 의미가 흐려진다.

 

1960년, Claude Berge가 이 문제의 해법을 제시했다. 해법은 단순했다. "선이 2개만 연결해야 한다는 규칙을 없애자." 하이퍼그래프에서는 하나의 선(하이퍼엣지)이 원하는 만큼의 점을 연결할 수 있다. 회의 예시라면 {Alice, Bob, Charlie}를 하나로 묶어 표현한다. "셋이 함께 회의한다"는 의미가 명확해진다.

 

2. 왜 더 좋은가

표현만 달라지는 게 아니다. 실제 문제를 풀 때 성능이 달라진다. 칩 설계 문제를 보자. 신호선 하나가 3개 게이트를 연결한다고 하자. 이 게이트들을 두 그룹으로 나누면, 그래프에서는 간선 2개가 잘린다고 계산한다. 하지만 실제로 잘린 신호선은 1개다. 목표 함수가 틀렸다.

 

하이퍼그래프는 신호선 하나를 하이퍼엣지 하나로 표현한다. 잘린 하이퍼엣지 1개 = 실제 신호선 1개. 목표가 정확히 일치한다. 데이터 구조도 간결하다. 100개 게이트를 연결하는 신호선을 그래프로 표현하면 4,950개 간선이 필요하다. 하이퍼그래프는 하이퍼엣지 1개로 끝난다.

 

3. 칩 설계와 분할 문제

1970년대 후반, 칩 설계자들은 수만 개 게이트를 여러 칩으로 나누는 문제에 직면했다. 칩 사이 연결선이 많아질수록 신호 지연이 커지고 비용도 증가했다. 특히 클럭 신호가 문제였다. 클럭은 100개 이상 게이트에 동시에 전달되어야 한다. 이걸 하이퍼그래프로 표현하면 하나의 하이퍼엣지로 끝난다. 실제 물리적 신호선이 그대로 하이퍼엣지 하나로 대응된다.

 

문제를 정확히 정의하자. 하이퍼그래프 H = (V, E)를 k개 그룹으로 나눈다. 각 그룹 크기는 비슷해야 하고(균형 제약), 잘리는 하이퍼엣지 수를 최소화한다. 이 문제는 NP-hard다. 최적해를 찾는 시간이 기하급수적으로 증가한다.

 

간단한 예로 시작한다. 게이트 6개(A, B, C, D, E, F)를 2개 칩으로 나눈다. 신호선은 4개다: net1={A,B,C}, net2={B,D}, net3={C,E,F}, net4={D,E}.

 

무작위로 나누면 칩1={A,B,C}, 칩2={D,E,F}가 된다. net2와 net3이 잘린다. 2개다. 다르게 배치해도 역시 2개가 잘린다. 6개를 3개씩 나누는 경우의 수는 20가지라 전부 시도할 수 있다. 하지만 100만 개에서는 불가능하다.

 

3.1. Kernighan-Lin 알고리즘

전체를 탐색하는 대신 현재 배치를 조금씩 개선한다. 일단 아무렇게나 나눈다. 게이트를 옮기며 상황을 개선한다. "개선"을 판단하는 기준은 간단하다. 게이트를 옮기면 어떤 신호선은 복구되고 어떤 신호선은 새로 잘린다. 복구되면 +1, 잘리면 -1, 변화 없으면 0이다. 이 점수들의 합을 이득이라 한다.

 

위 회로에서 A와 D를 교환해보자. net1이 새로 잘리고(-1), net2가 복구되고(+1), net3은 변화 없고(0), net4가 새로 잘린다(-1). 총 이득은 -1이다. 음수니까 하지 않는다. B와 D를 교환하면 총 이득 -2다. C와 E를 교환해도 -2다. 모든 교환이 상황을 악화시킨다. 이 경우는 초기 분할이 이미 최선이었다.

 

실제 큰 회로에서는 다르다. 수만 개 게이트에서는 개선 여지가 충분하다. 이득이 양수인 교환을 찾아 실제로 수행하고, 더 이상 개선이 없을 때까지 반복한다.

KernighanLin(H, k):
    partition ← 각 게이트를 k개 그룹 중 하나에 랜덤 배치
    
    improved ← true
    while improved:
        improved ← false
        
        for each 게이트 v:
            current_group ← partition[v]
            
            for each 다른 그룹 p:
                gain ← ComputeGain(v, current_group, p)
                
                if gain > 0 and 균형 제약 만족:
                    partition[v] ← p
                    improved ← true
                    break
    
    return partition

ComputeGain(v, from_group, to_group):
    gain ← 0
    
    for each 하이퍼엣지 e containing v:
        before_cut ← e가 현재 잘리는가?
        after_cut ← v를 옮긴 후 e가 잘리는가?
        
        if before_cut and not after_cut:
            gain ← gain + 1
        else if not before_cut and after_cut:
            gain ← gain - 1
    
    return gain

 

시간복잡도는 O(V² × E)다. 1980년대 칩 규모(수만 개)에서는 실용적이었다.

 

3.2. Multilevel 방법

1990년대 문제가 생겼다. Intel Pentium은 300만 개 이상의 트랜지스터를 가졌다. Kernighan-Lin은 O(n²)이라 너무 느렸다. 1998년 Karypis와 Kumar가 다른 접근을 제시했다. 큰 문제를 작게 만들어 풀고, 다시 키우며 개선하는 것이다.

 

생각해보자. 서울 전체 지도에서 강남에서 종로까지 길을 찾는다고 하자. 모든 골목길을 고려하면 복잡하다. 먼저 "강남→용산→종로" 같은 큰 그림을 잡는다. 그 다음 각 구역 내부에서 세부 경로를 찾는다. Multilevel이 이 방식이다.

 

첫 단계는 조대화(Coarsening)다. 100만 개 게이트를 점진적으로 줄인다. 같은 신호선을 많이 공유하는 게이트끼리 합친다. 위 회로에서 A와 B는 net1을 공유하니 슈퍼노드 AB로 합친다. D와 E는 net4를 공유하니 DE로 합친다. 이렇게 레벨 1을 만든다. 다시 합쳐서 레벨 2를 만든다. 실제로는 100만 개를 약 10단계로 1,000개까지 줄인다.

 

두 번째 단계는 초기 분할이다. 작은 하이퍼그래프를 분할한다. 레벨 2에서 칩1={ABC}, 칩2={DEF}로 나눈다.

 

세 번째 단계는 복원 및 정제다. 거꾸로 올라가며 개선한다. 레벨 1로 돌아가면 ABC가 AB와 C로 나뉜다. ABC가 칩1에 있었으니 AB와 C를 칩1에 배치한다. 여기서 Kernighan-Lin으로 개선을 시도한다. 레벨 0까지 내려가면 최종 분할이 완성된다.

 

실제 성능은 어땠을까? Karypis와 Kumar는 1999년 ISPD98 벤치마크로 테스트했다. 18개 회로, 13,000개부터 210,000개까지 다양한 크기였다. 결과는 명확했다. 잘리는 신호선 수가 눈에 띄게 줄었고, 실행 시간은 대규모 회로에서 훨씬 빨랐다.

 

시간복잡도를 보자. 기존 방법은 O(n²)다. Multilevel은 O(n log n)이다. 100만 개 게이트를 분할한다고 하자. 기존은 1조 번 연산이 필요하다. Multilevel은 약 2천만 번이다. 이론적으로 수백 배 차이가 난다.

 

더 나은 분할을 찾는 이유도 있다. 작은 문제에서는 전체 구조를 볼 수 있다. "ABC와 DEF는 거의 연결이 없으니 분리하자"는 큰 그림을 먼저 잡는다. 기존 방법을 큰 문제에 바로 쓰면 지역 최적해에 갇힌다. 게이트 하나씩만 옮겨서는 개선이 안 되는 상황 말이다. Multilevel은 전역적 관점에서 시작해 지역적으로 정제한다.

MultilevelPartition(H, k):
    // 1단계: Coarsening
    levels ← []
    H_current ← H
    
    while |V(H_current)| > threshold:
        levels.append(H_current)
        H_current ← Coarsen(H_current)
    
    // 2단계: Initial Partitioning
    partition ← KernighanLin(H_current, k)
    
    // 3단계: Uncoarsening & Refinement
    for i = |levels| - 1 down to 0:
        partition ← Project(partition, levels[i])
        partition ← Refine(levels[i], partition)
    
    return partition

Coarsen(H):
    matching ← FindSimilarPairs(H)
    H_coarse ← empty hypergraph
    
    for each (u, v) in matching:
        super_node ← Merge(u, v)
        H_coarse에 super_node 추가
    
    for each 하이퍼엣지 e in H:
        e_coarse ← e에 포함된 게이트들을 슈퍼노드로 변환
        H_coarse에 e_coarse 추가
    
    return H_coarse

FindSimilarPairs(H):
    matching ← []
    
    for each 게이트 쌍 (u, v):
        similarity ← u와 v가 공유하는 하이퍼엣지 개수
        if similarity가 높으면:
            matching에 (u, v) 추가
    
    return matching

Project(partition_coarse, H_fine):
    partition_fine ← empty
    
    for each 슈퍼노드 s:
        group ← partition_coarse[s]
        for each s를 구성하는 원래 게이트 v:
            partition_fine[v] ← group
    
    return partition_fine

Refine(H, partition):
    return KernighanLin(H, partition) 사용하여 개선

 

이 방법은 현재 모든 칩 설계 도구의 표준이다. Cadence, Synopsys 같은 상용 도구와 hMETIS, PaToH 같은 연구용 도구가 모두 이 방법을 쓴다. 칩 설계뿐 아니라 병렬 컴퓨팅, 희소 행렬 분할, 그래프 데이터베이스 샤딩에도 쓰인다.

 

4. 다른 분야

칩 설계만이 아니다. "여럿이 함께"라는 구조는 생물학, 최적화, 인공지능 등 여러 곳에서 나타난다.

 

4.1. Spectral Clustering

생물학에서 단백질들은 모여 복합체를 이룬다. RNA Polymerase II는 12개 단백질로 구성된다. 이 12개가 함께 전사를 수행한다. 단백질 상호작용 네트워크에서 이런 복합체를 찾는 것이 클러스터링 문제다.

 

그래프로 표현하면 12개 단백질을 완전 그래프로 연결한다. 66개 간선이 생긴다. "12개가 함께 복합체"라는 정보가 흐려진다. 하이퍼그래프로는 복합체={단백질1, ..., 단백질12}로 끝이다. 하나의 하이퍼엣지가 전체를 표현한다.

 

Spectral Clustering은 라플라시안 행렬의 고유벡터를 이용한다. 하이퍼그래프 라플라시안은 이렇게 정의된다.

 

먼저 접속 행렬 H를 만든다. H[i,e]=1이면 점 i가 하이퍼엣지 e에 속한다. 크기는 (점 개수)×(하이퍼엣지 개수)다.

L = I - D_v^(-1/2) · H · W · D_e^(-1) · H^T · D_v^(-1/2)

 

여기서 I는 단위 행렬, D_v는 점의 degree, D_e는 하이퍼엣지 크기, W는 하이퍼엣지 가중치다. 모두 대각 행렬이다.

SpectralClustering(H, k):
    H ← 접속 행렬 구성
    L ← 라플라시안 계산
    
    (eigenvalues, eigenvectors) ← L을 고유값 분해
    U ← 최하위 k개 고유벡터 선택
    
    clusters ← K-means를 U에 적용
    
    return clusters

시간은 O(|V|³)이 걸린다. 고유값 분해가 병목이다.

 

 

그래프는 쌍별 상호작용만 본다. 12개 단백질을 완전 그래프로 연결하면 66개 간선이 생긴다. 각 간선은 두 단백질의 관계만 본다. 실제 복합체는 12개 전체가 함께 작동한다. 하이퍼그래프 라플라시안은 복합체 전체를 하나의 하이퍼엣지로 표현한다. 고유벡터가 이 "집단적 작동" 패턴을 직접 포착한다. 클러스터링 정확도가 크게 향상된다.

 

4.2. 최소 횡단 문제

학교에 동아리가 여러 개 있다. 로봇동아리={Alice, Bob, Charlie}, 밴드동아리={Bob, Dave, Eve}, 영화동아리={Charlie, Eve, Frank}. 축제 준비위원을 선발한다. 각 동아리에서 최소 한 명은 참여해야 한다. 최소 몇 명이 필요할까?

 

Bob과 Eve를 선택하면 모든 동아리를 커버한다. 2명으로 충분하다. 이게 최소 횡단(Minimum Transversal) 문제다. 모든 하이퍼엣지와 최소 한 개의 교집합을 가지는 가장 작은 점 집합을 찾는다.

 

이 문제는 NP-complete다. 정확한 답을 빠르게 찾을 수 없으니 근사 알고리즘을 쓴다.

GreedyHittingSet():
    S ← 빈 집합
    uncovered ← 모든 하이퍼엣지
    
    while uncovered가 비지 않음:
        for each 점 v:
            count[v] ← v가 커버하는 uncovered 엣지 개수
        
        v_max ← count가 최대인 점
        S에 v_max 추가
        uncovered에서 v_max를 포함하는 엣지 제거
    
    return S

 

동아리 예시로 따라가자. 먼저 모든 점의 커버 개수를 센다. Bob은 2개(로봇, 밴드), Charlie도 2개(로봇, 영화), Eve도 2개(밴드, 영화)를 커버한다. Bob을 선택한다. Bob이 속한 동아리(로봇, 밴드)를 제거한다. 남은 건 영화동아리다. Charlie, Eve, Frank 중 하나를 선택한다. Charlie를 선택한다. 완료다. S={Bob, Charlie}로 2명이다. 최적해도 2명이니 이번에는 최적이다.

 

이 알고리즘은 최적해의 H_n=O(log n)배를 보장한다. n은 하이퍼엣지의 최대 크기다. 동아리가 최대 10명이면 H_10≈2.9배 이내다. 센서 배치, 테스트 케이스 선택, 광고 타겟팅 등에 쓰인다.

 

4.3. 딥러닝

2010년대 후반, 하이퍼그래프는 딥러닝과 만났다.

 

2017년 Graph Neural Network(GNN)가 등장했다. 핵심 아이디어는 간단하다. 각 점은 이웃들의 정보를 모아서 자신을 업데이트한다. SNS에서 Alice의 친구들이 모두 음악을 좋아하면 Alice도 음악을 좋아할 가능성이 높다는 식이다. 하지만 GNN은 쌍별 관계만 본다. Alice-Bob, Bob-Charlie, Alice-Charlie 이렇게 하나씩 따로 본다.

 

2019년 Feng 등이 Hypergraph Neural Network(HGNN)를 제안했다. GNN은 "내 친구들의 정보를 모은다"이고, HGNN은 "내가 속한 그룹들의 정보를 모은다"이다.

 

팀 프로젝트 상황을 생각하자. 팀1={Alice, Bob, Charlie}, 팀2={Bob, Dave}다. Bob은 두 팀에 속한다.

 

GNN에서 Bob은 Alice, Charlie, Dave 각각으로부터 정보를 받는다. 개별적인 연결만 본다. 하지만 실제로 Bob이 받는 영향은 다르다. Alice와 Charlie는 Bob에게 "팀1의 맥락"에서 영향을 준다. Dave는 "팀2의 맥락"에서 영향을 준다. 같은 팀원이라는 사실이 중요하다.

 

HGNN은 이를 반영한다. 먼저 각 팀의 "팀 특성"을 계산한다. 팀1 특성=(Alice+Bob+Charlie)/3이고, 팀2 특성=(Bob+Dave)/2다. Bob의 새 정보는 팀1 특성+팀2 특성이다. Bob은 "Alice와 Charlie가 함께 있는 팀"이라는 맥락과 "Dave와 함께 있는 팀"이라는 맥락을 모두 받는다.

 

이미지 인식에서 차이가 더 명확하다. 얼굴을 인식하려면 눈, 코, 입이 특정 위치에 함께 있어야 한다. 눈 하나만 봐서는 얼굴인지 모른다. 셋이 "함께" 특정 배치를 이루어야 얼굴이다.

 

GNN은 눈-코, 코-입, 눈-입의 관계를 각각 따로 학습한다. 눈과 코가 가까우면 +1점, 코와 입이 세로로 배치되면 +1점 이런 식이다. 하지만 "눈 두 개가 위에 있고, 코가 중간에 있고, 입이 아래에 있다"는 전체 패턴은 세 개의 쌍별 관계로는 포착하기 어렵다.

 

HGNN은 {눈, 코, 입}을 하나의 하이퍼엣지로 묶는다. "이 세 요소가 함께 이런 패턴을 이룬다"를 직접 학습한다. 세 요소의 공간적 배치를 통째로 본다. 이게 GNN과 HGNN의 본질적 차이다.

 

현재 HGNN은 추천 시스템, 약물 발견, 교통 예측 등에 쓰인다. 사용자-아이템-맥락을 함께 고려하거나, 분자 내 원자 그룹의 집단적 효과를 모델링하거나, 여러 도로의 동시 혼잡 패턴을 예측하는 데 적합하다.

 

5. 정리

하이퍼그래프의 발전을 시간순으로 정리하면 이렇다.

연대	알고리즘	핵심	응용
1970	Kernighan-Lin	반복적 교환	초기 칩 설계
1970s	Greedy Hitting Set	탐욕적 커버	커버리지 최적화
1998	Multilevel	축소-분할-복원	대규모 VLSI
2007	Spectral	고유벡터 클러스터링	단백질 복합체
2019	HGNN	집단 상호작용 학습

하이퍼그래프가 그래프보다 나은 이유는 "함께"를 직접 표현하기 때문이다. 칩의 클럭 신호는 100개 게이트에 동시 전달된다. 단백질 복합체는 12개 단백질이 함께 작동한다.

 

사용자는 여러 상품을 함께 구매한다. 이런 것들을 쌍으로 쪼개면 본질이 사라진다. 하이퍼그래프는 "여럿이 함께"를 그대로 담는다. 그 결과 더 정확하고, 때로는 더 빠른 알고리즘이 된다.

---

참고문헌

[1] Berge, C. (1970). Graphes et hypergraphes. Dunod, Paris.

[2] Kernighan, B. W., & Lin, S. (1970). An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49(2), 291-307.

[3] Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of Computer Computations (pp. 85-103). Plenum Press, New York.

[4] Johnson, D. S. (1974). Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3), 256-278.

[5] Lovász, L. (1975). On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13(4), 383-390.

[6] Alpert, C. J. (1998). The ISPD98 circuit benchmark suite. In Proceedings of the International Symposium on Physical Design (pp. 80-85).

[7] Karypis, G., Aggarwal, R., Kumar, V., & Shekhar, S. (1999). Multilevel hypergraph partitioning: Application in VLSI domain. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7(1), 69-79.

[8] Karypis, G., & Kumar, V. (1999). Multilevel k-way hypergraph partitioning. In Proceedings of the 36th Annual ACM/IEEE Design Automation Conference (pp. 343-348).

[9] Zhou, D., Huang, J., & Schölkopf, B. (2006). Learning with hypergraphs: Clustering, classification, and embedding. In Advances in Neural Information Processing Systems 19 (pp. 1601-1608).

[10] Feng, Y., You, H., Zhang, Z., Ji, R., & Gao, Y. (2019). Hypergraph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 33, No. 01, pp. 3558-3565).