본 문서에서는 WSDM 2020에서 발표된 Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference 논문을 소개합니다. 논문에 대한 상세 정보는 다음과 같습니다.
- Title: Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference
- Authors: Jaemin Yoo, U Kang, Mauro Scanagatta, Giorgio Corani, and Marco Zaffalon
- ACM International Conference on Web Search and Data Mining (WSDM) 2020
Graph Sampling
그래프 샘플링(graph sampling)은 어떤 그래프가 주어졌을 때 해당 그래프의 특성을 보존하는 작은 서브그래프(subgraph)를 생성하는 문제입니다. 본 연구에서는 그래프 샘플링 중에서도 정점 집합을 유지하면서 간선 집합의 일부만을 선택하는 간선 샘플링(edge sampling) 문제를 다룹니다. 예를 들어 사용자간 관계를 설명하는 소셜 네트워크가 주어져 있다고 할 때, 간선 샘플링은 각 사용자의 정보는 유지한 채 사용자간 관계 정보만을 제거하여 서브그래프를 생성합니다.
간선 샘플링이 잘 이루어지면 그림 1과 같은 결과를 생성하게 됩니다. 그림에 나타난 그래프는 여러 개의 블로그와 블로그간 하이퍼링크를 나타내는 웹 그래프로, 각 정점의 색은 블로그의 정치 성향을 나타냅니다. 이때, 그림 왼쪽의 그래프는 동일한 성향의 블로그끼리 간선을 생성하는 동종 친화성(homophily) 특성을 보이는데, 이 특성이 그림 오른쪽의 서브그래프에서도 잘 보존되는 것을 확인할 수 있습니다. 이렇게 생성된 서브그래프는 실제 그래프의 특성을 보다 효율적으로 파악하기 위해 사용될 수 있습니다.
 |
| 그림 1. 간선 샘플링 결과의 예시. 왼쪽의 주어진 그래프에서 오른쪽의 서브그래프를 생성합니다. |
Graphical Inference
실세계 그래프를 이해하는 한 가지 방법은 주어진 그래프를 확률 그래프 모델(probabilistic graphical model)로 해석하는 것입니다. 이때, 각 정점은 이산 상태를 가지는 확률 변수로, 각 간선은 두 확률 변수의 상관 관계를 나타내는 것으로 해석됩니다. 그래프 추론(graphical inference) 문제는 그래프 모델과 각 변수의 사전 분포(prior distribution)가 주어졌을 때 변수의 사후 분포(posterior distribution)를 계산하는 문제입니다. 즉, 각 변수의 독립적인 정보와 그래프 구조를 관련지어 보다 정확한 확률 분포를 얻는 과정이라 할 수 있습니다.
실세계 그래프에 대한 추론 결과는 정점 분류(node classification) 문제에 바로 적용될 수 있습니다. 예를 들어 소셜 네트워크에서 일부의 사용자가 악성 사용자라는 것이 알려진 경우를 생각해 봅시다. 알려진 정보를 각 정점의 사전 분포로 표현한 뒤 (이때, 악성 사용자가 아닌 것이 확실한 사용자가 있다면 그러한 정보도 포함할 수 있습니다) 그래프 추론 알고리즘을 동작한다면 정보가 없는 사용자들 중 악성 사용자를 미리 찾아낼 수 있습니다. 이는 각 사용자가 악성 사용자일 가능성을 나타내는 사후 분포를 통해 이루어집니다. 그래프 추론의 장점은 동작 방식이 직관적이며 추가적인 파라미터 학습을 요구하지 않는다는 것입니다.
임의의 그래프 모델에 대한 추론은 NP-하드 문제입니다. 그런데, 그래프의 트리위드(treewidth)가 제한되어 있다면 그래프 추론이 선형 시간 내에 이루어진다는 사실이 잘 알려져 있습니다. 여기서 트리위드는 각 그래프가 갖는 고유한 성질로, 트리위드가 낮을수록 그래프는 트리 그래프(tree graph)에 가까워지고 트리위드가 높을수록 그래프는 복잡한 구조를 띄게 됩니다. 예를 들어, 그림 1에서 왼쪽 그래프는 약 24 정도의 높은 트리위드를 갖는 반면 오른쪽 그래프의 트리위드는 최솟값인 1로써 해당 그래프는 완전한 트리 구조를 가지고 있습니다.
Bounded Treewidth Sampling
본 연구에서는 효율적인 그래프 추론을 위한 새로운 샘플링 알고리즘인 Bounded Treewidth Sampling (BTW)을 제안합니다. BTW 알고리즘은 임의의 그래프와 인자 k가 주어졌을 때 트리위드가 항상 k보다 작거나 같은 서브그래프를 생성합니다. 이렇게 생성된 서브그래프에서는 효율적인 그래프 추론이 이루어질 수 있고, 결과적으로 원래 그래프에 근사 추론을 실행했을 때보다 더 정확한 사후 분포를 얻을 수 있습니다.
BTW 알고리즘의 핵심 아이디어는 먼저 k+1개의 정점을 가지는 작은 서브그래프를 생성한 뒤 트리위드를 증가시키지 않는 방향으로 정점을 한 개씩 서브그래프에 추가시키며 샘플링을 진행하는 것입니다. 각 반복(iteration)에서 선택되는 정점은 점수 함수(score function)에 의해 결정되며, 이 점수 함수를 변경함으로써 최종적인 서브그래프의 특성을 조절할 수 있습니다. 본 연구에서는 서브그래프의 간선 수를 그리디(greedy)한 방식으로 최대화하는 점수 함수를 사용합니다. 그 결과, 기존 그래프의 연결성(connectivity)이 서브그래프에서도 항상 유지되며, 샘플링 과정이 간선 수에 대해 선형적인 효율적인 시간 복잡도를 가집니다.
Experiments
실험은 네 종류의 실세계 그래프에 대한 정점 분류 문제를 통해 이루어집니다. 즉, 주어진 그래프에서 일부 정점의 클래스 정보가 주어져있을 때 이를 사전 분포로 모델링한 다음 그래프 추론 알고리즘을 수행합니다. 추론 결과 나머지 정점의 클래스를 분류하는 정확도(accuracy)가 여러 가지 모델을 비교하는 주 평가 지표로 사용됩니다. 여기서 클래스는 데이터셋에 따라 논문의 연구 분야나 (각 정점이 논문을 의미하는 경우) 블로그의 정치 성향 (각 정점이 웹 블로그를 의미하는 경우) 등을 의미합니다.
주 비교 대상은 원래 그래프에 근사 추론 알고리즘인 loopy belief propagation (LBP)을 수행하는 것입니다. LBP 알고리즘은 각 정점의 사후 분포를 효율적으로 계산할 수 있는 그래프 추론 알고리즘으로, 간선 개수에 선형적인 시간 복잡도를 가지기 때문에 특히 대용량 그래프에 자주 사용되어 왔습니다. LBP의 단점은 알고리즘의 수렴(convergence) 여부와 근사 추론 결과의 품질을 보장할 수 없다는 것입니다. 따라서, 본 연구는 제안된 BTW 알고리즘을 통해 서브그래프를 생성하고 이를 기반으로 정확한 추론을 수행했을 때 주어진 그래프에 대해 LBP를 수행하는 것보다 정확한 결과를 얻는 것을 일차적인 목표로 삼습니다.
그림 2는 실험 결과를 나타낸 것으로 주어진 그래프에 LBP를 수행한 경우 (빨간색 점선), 생성된 서브그래프에 LBP를 수행한 경우 (초록색 실선), 생성된 서브그래프에 정션 트리(junction tree) 알고리즘을 수행한 경우 (파란색 실선)를 각각 나타냅니다. 정션 트리 알고리즘은 대표적인 그래프 추론 알고리즘으로 LBP 알고리즘과는 달리 정확한 추론 결과를 계산하지만 수행 시간이 그래프의 트리위드에 지수적으로 비례합니다. 실험 결과, BTW에 의해 생성된 서브그래프에 정션 트리 알고리즘으로 그래프 추론을 수행했을 때 가장 높은 정확도를 보입니다. 또한, 생성된 서브그래프에 LBP를 수행했을 때 원래 그래프에 비해 높거나 비슷한 정확도를 보이는데, 이는 제안한 샘플링 기법이 전체적인 그래프 구조를 잘 보존한다는 것을 의미합니다.
 |
| 그림 2. 실세계 그래프에 대한 정점 분류 정확도. 공간이 부족해 세 개 데이터만 포함시켰습니다. |
Conclusion
본 문서에서는 WSDM 2020 학회에서 발표된 "Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference" 논문을 소개하였습니다. 해당 논문에서 제안하는 BTW (Bounded Treewidth Sampling) 알고리즘은 효율적인 그래프 추론을 위해 트리위드를 제한하는 서브그래프를 생성합니다. 또한, 생성된 서브그래프에 대해 그래프 추론을 진행한 결과, 기존 그래프에서 근사 추론을 했을 때보다 정점 분류 문제에 대해 더 높은 정확도를 보인다는 것을 실험적으로 보입니다.
최근에는 실세계 그래프의 크기가 방대해지고 있고, 이런 그래프에서는 복잡한 연산을 요구하는 그래프 추론 알고리즘이나 그래프 신경망을 사용하기 어렵습니다. 예를 들어, 대표적인 소셜 네트워크인 페이스북에서 친구 추천 알고리즘은 서비스의 질을 향상하는 데 매우 중요하지만, 20억 명 이상의 활성 사용자가 생성하는 대용량 그래프에서 복잡한 알고리즘을 수행하는 것은 매우 어렵습니다. 본 논문은 친구 추천 등 대용량 그래프에서 정점 분류(node classification) 문제를 풀 때 계산 효율성을 크게 높이고 수행 시간을 단축하는 데 유용하게 활용될 수 있습니다. 논문에 대한 상세 정보는 링크를 통해 확인할 수 있습니다.