본 문서에서는 2022년 TKDD journal에 발표된 "Finding Key Structures in MMORPG Graph with Hierarchical Graph Summarization" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.
- Title: Finding Key Structures in MMORPG Graph with Hierarchical Graph Summarization
- Authors: Jun-Gi Jang, Chaeheum Park, Changwon Jang, Geonsoo Kim, and U Kang
- Journal: ACM Transactions on Knowledge Discovery from Data (TKDD), Feb., 2022.
MMORPG Graph Summarization
대규모 실세계 MMORPG(Massive Multiplayer Online Role-Playing Game) 그래프에 존재하는 주요 구조는 무엇일까요? 계층적 노드 레이블(hierarchical node label)을 가지는 MMORPG 그래프를 서로 다른 계층의 하위 구조를 고려하여 요약할 수 있는 방법은 무엇일까요? MMORPG에는 계층 구조의 레이블을 가지는 이질적인 객체간의 많은 상호작용들이 존재하며 이는 이기종 그래프(hierarchical heterogeneous graph)로 표현할 수 있습니다. 그림 1에서의 예와 같이 사용자는 여러 캐릭터들을 가지고 있으며, 다양한 장비를 갖춘 각 캐릭터는 다양한 던전을 방문합니다. 또한, 각 객체는 계층적 레이블(예: character-dealer-destroyer and equipment-weapon)을 가지고 있습니다. 계층적 노드 레이블을 가지는 이기종 그래프를 요약하는 것은 복잡한 이기종 그래프의 특성을 이해하는데 있어 중요한 문제입니다. 실제 동종 그래프 혹은 동적 그래프로부터 유의미한 구조(예: star, chain, clique 등)를 찾아 주어진 그래프를 요약하는 몇 가지 접근 방식이 제안되었습니다. 하지만, 기존 방법들은 모두 레이블의 다름이나 레이블의 계층을 고려하지 않기 때문에 계층적 레이블을 가지는 이기종 그래프를 요약하지 못합니다.
그림 1. Blade & Soul 게임의 그래프 예시. 노드 레이블에 계층이 있는 이기종 그래프입니다.
Vocabulary-based summarization of Graphs (VoG)
제안하는 방법을 설명함에 앞서 그래프의 핵심 구조를 찾아 동종 그래프(homogeneous graph)를 요약하는 VoG을 소개합니다. 실세계 그래프에는 다음과 같이 대표적인 6가지 구조 유형이 존재합니다. Star, clique, near clique, bipartite core, near bipartite core, 그리고 chain. VoG는 무손실 압축을 제공하는 최고의 모델을 찾는 방법인 MDL (Minimum Description Length)을 기반으로 6가지 핵심 구조 유형을 활용하여 그래프를 요약합니다. 예를 들어, clique 구조는 주어진 그래프의 정점들이 모두 서로 연결되어 있는 구조이며 인접행렬(adjacency matrix)은 모든 값이 1로 가득찬 행렬로 표현됩니다. 이 때, clique라는 정보만 잘 인코딩한다면 1로 가득찬 인접행렬을 표현하는 비트 수보다 훨씬 작은 비트 수로 해당 부분 그래프를 나타낼 수 있습니다. 구체적인 예시는 본 논문과 VoG 논문을 참조하시길 바랍니다. VoG는 MDL을 기반으로 각 구조별 연결성의 인코딩 비용을 정의합니다. 그리고, 주어진 큰 그래프를 여러 부분 그래프로 효율적으로 분해하며, 각 분해된 그래프를 압축율을 최대화할 수 있는 핵심 구조로 인코딩합니다. 각 부분 그래프의 인코딩된 결과는 단순히 인접행렬로 표현되는 것보다 훨씬 더 적은 비트 수를 필요로 합니다. 또한, 에러에 대한 처리를 하여 무손실 압축을 수행합니다.
GSHL (Graph Summarization with Hierarchical Labels)
본 논문에서는 계층적 노드 레이블을 가지는 이기종 그래프를 요약하는 GSHL (Graph Summarization with Hierarchical Labels) 방법을 제안합니다. 본 논문에서는 먼저 MDL을 기반으로 계층적 노드 레이블이 있는 이기종 그래프에 대한 인코딩 비용을 명확하게 정의합니다. 그다음, GSHL은 그래프 분해 방법을 사용하여 이기종 그래프를 부분 그래프들로 분해하고 각 부분 그래프별로 6가지 핵심 구조(예: 별, 클리크, 이분 코어, 체인 등) 중 가장 적합한 구조를 찾습니다. 그리고, GSHL은 찾은 구조를 노드의 계층적 레이블을 고려하여 추가로 세분화함으로써 인코딩 비용을 추가적으로 줄이는 방향으로 주어진 그래프를 요약합니다.
가장 먼저 GSHL은 각 계층의 레이블 일관성을 고려하여 각 구조의 레이블 인코딩 비용을 정의합니다. 기존 방법들에서는 구조의 연결성에 대한 인코딩 비용은 정의되었으나, 레이블에 대한 구체적인 비용은 정의되지 않았습니다. 그렇기 때문에, 레이블에 대한 인코딩 비용을 정의하여야 하며, 레이블의 일관성에 따라 비용이 달라질 수 있으므로, 주요 일관성 유형별로 인코딩 비용을 정의해야 합니다. 본 논문에서는 레이블 일관성이 높으면 높을수록 적은 인코딩 비용을 필요로 하는 식을 제공합니다. 예를 들어, 주어진 부분 그래프에서 1) 모든 노드들의 레이블이 모든 계층에서 동일한 경우, 2) 상위 계층의 레이블은 동일하나 하위 계층의 레이블은 일치하지 않는 경우, 3) 상위 계층 레이블과 하위 계층 레이블이 모두 일치하지 않은 경우를 비교해본다고 가정합니다. 그러면, 1-2-3 순서대로 적은 인코딩 비용을 필요로 합니다. 또한, 각 계층의 일관성에 대해서는 1) 노드의 역할에 상관없이 모든 레이블이 일치하는 경우, 2) 부분 그래프의 구조 내에서 역할이 같은 노드들 간의 레이블만 일치하는 경우, 3) 레이블이 일치하지 않는 경우 순으로 인코딩 비용이 적게 필요합니다. 각 부분 그래프의 구조에서 위와 같은 일관성을 판단하여 인코딩하면 효과적으로 각 부분 그래프들을 요약할 수 있습니다. 구체적인 내용은 본 논문의 3.3절을 참고하시길 바랍니다.
인코딩 비용을 정의한 후 GSHL은 구조의 연결성 및 계층 레이블의 인코딩 비용간의 트레이드 오프(trade-off)를 고려하여 각 계층에서 구조를 세분화합니다. 일관성 없는 구조를 일관성이 있는 여러 구조로 분할하면 연결성 비용은 높아지지만 레이블 비용은 낮아집니다. 세분화 전후의 인코딩 비용을 비교하여 세분화 여부를 신중하게 결정합니다. 그림 2는 세분화에 대한 구체적인 예시를 보여줍니다. 왼쪽과 같이 Star 구조가 주어지고, 이 구조는 첫번째 계층은 일관성이 있으나, 두번째 계층에서는 레이블 일관성이 없습니다. 하위 계층에서의 일관성을 높이기 위해 오른쪽과 같이 두 구조로 분할을 할 수 있으며, 세분화할 경우 연결성에 대한 인코딩 비용은 높아지나 레이블에 대한 인코딩 비용은 낮아집니다. 그러므로, 세분화 전후의 인코딩 비용을 비교하여 세분화를 할지를 결정합니다. 구체적인 내용은 본 논문의 3.4절을 참고하시길 바랍니다.
그림 2. Star 구조의 세분화. 2번째 계층의 일관성에 따라 세분화할 수 있습니다. 세분화 전후의 인코딩 비용을 비교하여 세분화 여부를 결정합니다.
Experiment
본 실험에서는 NC소프트에서 개발한 Blade & Soul 게임에서 얻은 데이터를 계층적 노드 레이블을 가지는 이기종 그래프로 표현하여 분석합니다. 상위 계층의 레이블은 account, character, equipment, dungeon이 있으며, 각 레이블별로 다른 하위 계층들을 가집니다. 구체적인 데이터 설명은 본 논문을 참고하시길 바랍니다. 그림 3과 4에서와 같이, GSHL은 흥미로운 발견들을 제공합니다. 그림 2는 저희의 동기와도 관련이 깊습니다. 만약, 계층적 레이블 정보를 무시된다면, 그림 3의 왼쪽 (a)에 나타낸 구조를 찾습니다. 이 구조는 Soul 장비가 특정 캐릭터 그룹에서 공유되고 있다는 정보 정도만을 제공합니다. 반면에, 계층적 레이블 정보를 고려할 때, 우리가 찾아낸 구조는 세 개의 세분화된 구조들이며, 여기서 각 구조는 장비와 캐릭터의 직업 사이의 관계를 더 명확하게 나타내줍니다. 예를 들어, Soul을 가장 많이 사용하는 직업은 Zen Archer이며, Dealer 플레이스타일의 캐릭터(그림 3(b,c))는 Tanker 및 Buffer 플레이스타일의 캐릭터(그림 3(d))보다 Soul 장비를 더 많이 사용하는 것을 확인할 수 있습니다.
그림 3. 계층적 라벨 정보를 고려한 발견. GSHL은 캐릭터 그룹을 세 개의 주요 하위 구조로 분해합니다.
그림 4는 데이터 내 비슷한 계정(account)을 찾습니다. GSHL로 찾은 구조들을 기반으로 목표 계정 0번과 가장 유사한 두 계정 9번와 3602번을 찾았습니다. 계정 9번의 캐릭터들은 목표 계정 0번의 캐릭터들과 공통적인 던전 방문과 장비들을 가지고 있는 것을 확인할 수 있습니다. 계정 3602과 계정 0번 사이에는 연결된 공통 계정들이 많이 존재하며, 캐릭터들이 같은 던전 및 같은 장비들을 가지고 있는 것을 확인할 수 있습니다. 이와 같이 여러 계정에 대해 유사한 계정들을 찾아 게임에서 더 나은 서비스를 제공할 수 있습니다.
그림 4. 계정 0과 가장 가까운 두 계정 9번와 3602번을 찾았습니다. 그들은 공통적인 장비, 던전, 계정을 가집니다.
Conclusion
본 문서에서는 TKDD journal 2022에서 발표된 Finding Key Structures in MMORPG Graph with Hierarchical Graph Summarization 논문을 소개하였습니다. 본 논문에서는 계층적 노드 레이블이 있는 이기종 그래프를 위한 새로운 그래프 요약 알고리즘인 GSHL을 제안합니다. 먼저, MDL에 따라 연결성과 레이블에 대한 인코딩 비용을 정의합니다. 그다음, GSHL은 이기종 그래프를 부분 그래프로 분해합니다. 그리고, GSHL은 정의된 인코딩 비용들을 기반으로 각 부분 그래프를 핵심 구조로 식별하고 노드의 계층적 레이블을 고려하여 각 구조를 추가적으로 세분화함으로써 주어진 그래프를 효과적으로 요약합니다. 대규모 실제 MMORPG 그래프에 대한 실험을 통해 GSHL이 그래프 요약을 위한 유용하고 확장 가능한 도구임을 보여줍니다. GSHL 덕분에 MMORPG 그래프에서 흥미로운 패턴들을 발견할 수 있었습니다.
Blade & Soul 뿐만 아니라 다양한 MMORPG 게임들에서 계층적 노드 레이블이 있는 이기종 그래프를 생성할 수 있기 때문에, GSHL은 각 게임별로 흥미로운 패턴들을 찾아 게임 내 상호 작용에서 의미 있는 통찰력을 얻고 게임에서 더 나은 사용자 경험을 설계하는데 도움이 될 수 있습니다.
(이 연구는 NC소프트의 지원으로 진행되었습니다.)