이분 그래프 (Bipartite Graph)

한 줄 정의: 그래프의 모든 정점을 두 그룹으로 나누었을 때, 같은 그룹 안의 정점끼리는 절대 간선으로 연결되지 않고 서로 다른 그룹의 정점끼리만 연결되는 그래프입니다.

쉽게 풀면

소개팅 매칭 서비스를 생각해봅시다. 사람들을 남성 그룹과 여성 그룹으로 나누면, "이 둘을 연결해주자"는 관계(간선)는 항상 서로 다른 그룹 사이에서만 생깁니다. 같은 그룹 안, 즉 남성끼리나 여성끼리는 연결선이 생기지 않습니다. 이렇게 정점을 두 편으로 딱 나눌 수 있고 연결이 편과 편 사이에서만 일어나는 그래프를 이분 그래프라고 부릅니다. 흥미롭게도 어떤 그래프가 이분 그래프인지 아닌지는 "홀수 개의 정점으로 이루어진 고리(사이클)"가 하나라도 있는지만 확인하면 판별할 수 있습니다.

왜 중요한가

현실의 많은 관계는 애초에 서로 다른 두 종류의 대상 사이에서만 성립합니다. 사용자와 상품, 논문과 저자, 유전자와 질병처럼 이질적인 두 집합을 다룰 때 이분 그래프는 그 관계를 있는 그대로 표현할 수 있는 가장 자연스러운 구조입니다. 그래서 추천 시스템, 매칭 이론, 정보 검색, 생물정보학 등 다양한 분야의 논문에서 문제를 정의하는 출발점으로 자주 등장하며, 이분 그래프 위에서의 매칭·군집화·투영(projection) 같은 연산이 실제 알고리즘 설계로 이어집니다.

논문에서는 이렇게 쓰입니다

"구직자와 채용 공고를 두 개의 정점 집합으로 두고, 적합도가 높은 쌍을 연결한 이분 그래프 위에서 최적 매칭을 계산하였다."

이 문장은 사람과 일자리라는 서로 다른 두 종류의 대상을 이분 그래프로 표현하고, 그 안에서 가장 잘 맞는 짝을 찾는 알고리즘을 적용했다는 뜻입니다.

"사용자-아이템 이분 그래프에서 사용자 노드를 공통으로 갖는 아이템끼리 연결하는 투영을 수행하여 아이템 간 유사도 네트워크를 구성하였다."

추천 시스템 연구에서 흔히 쓰이는 표현으로, 사용자와 상품이라는 두 집합으로 이루어진 이분 그래프를 한쪽 집합만 남는 일반 그래프로 변환(투영)해 유사도를 분석했다는 뜻입니다.

"단백질과 도메인 사이의 관계를 이분 그래프로 나타내고, 두 종류의 정점에 서로 다른 임베딩 벡터를 학습시켜 상호작용을 예측하였다."

생물정보학 논문에서 볼 수 있는 예로, 서로 다른 성격의 두 대상(단백질과 도메인) 간의 관계를 이분 그래프로 모델링하고 이를 기계학습 입력으로 활용했다는 의미입니다.

조금 더 깊게 보면

이분 그래프를 다루는 논문에서는 두 정점 집합 중 하나를 기준으로 다른 집합을 압축해 표현하는 투영(projection) 연산이 자주 등장하며, 이 과정에서 원래 있던 정보가 일부 손실될 수 있다는 점이 함께 논의되곤 합니다. 또한 이분 그래프에서의 매칭 문제는 완전 매칭 여부를 판별하는 홀의 결혼 정리(Hall's theorem)나, 최대 매칭을 구하는 다양한 알고리즘과 연결됩니다. 최근에는 그래프 신경망(GNN) 계열 연구에서 이분 그래프의 두 정점 집합에 서로 다른 임베딩 공간을 부여하는 방식도 널리 쓰이고 있습니다.

주의할 점

이분 그래프는 정점을 몇 개의 그룹으로 나눌 수 있는가의 문제이며, 그래프 색칠에서 최소 몇 가지 색으로 모든 정점을 칠할 수 있는지(채색수)를 구하는 문제와 밀접하게 연결되어 있습니다. 실제로 어떤 그래프가 이분 그래프라는 것은 정확히 2가지 색으로 칠할 수 있다는 것과 같은 말입니다.