Finding Key Structures in MMORPG Graph with Hierarchical Graph Summarization

Blade & Soul entails multiple characters simultaneously interacting with each other in an open-world environment. Each character carries a variety of equipment acquired throughout its playtime; it enters various dungeons with other characters in order to acquire new equipment or items. Such game design encourages users to repetitively visit dungeons.

A user associated with an account can possess multiple in-game characters with different jobs. These jobs are divided into three types of play-styles: dealer, tanker, and buffer. A dealer mainly afflicts damage to the enemies of its party (a group of multiple characters), while a tanker taunts enemies so the party members can freely afflict damage, and a buffer aids other party members. A party needs to have balanced types of jobs to successfully enter a dungeon and fight with enemies.

We collect $3$ months of data from January to March in 2019, and extract the following four relationships.

• •

  account - character: which character(s) each account possesses.

• •

  account - account: friendship between accounts.

• •

  character - dungeon: which dungeons each character visited.

• •

  character - equipment: which equipment each character is equipped with.

We extract $4$ types of entities: account, character, dungeon and equipment. An account represents a user, and a user can have multiple characters. A dungeon entity belongs to a type based on its difficulty where an advanced dungeon is a more difficult version of the corresponding normal dungeon.

Our goal is to construct a concise summary of an MMORPG graph with hierarchical node labels. There are several challenges for the goal.

How can we summarize an MMORPG graph with a few key subgraphs (vocabularies)?

In designing an optimization objective for the summary, how can we incorporate hierarchical node labels?

Given a subgraph, how can we extract consistent substructures at different levels of hierarchy?

Our ideas to solve the challenges are as follows.

Exploiting Minimum Description Length (MDL) allows us to extract key structures (e.g., clique, star, bipartite core, etc.) from the MMORPG graph. We add the formulation for hierarchical labels while exploiting the formulation for structures used in VoG [1].

Considering label consistency of structures enables us to evaluate various structures in depth. We carefully formulate label consistency for each key structure.

Segmenting labels of an inconsistent structure from higher to lower levels generates consistent substructures. By determining segmentation at each level of the hierarchy, we extract pivotal structures from a heterogeneous graph.

In the following sections, we present the problem formulation for heterogeneous graph summarization based on the MDL, and how to design an optimization objective for the summary. We describe how to encode the connectivity of each structure, hierarchical labels, and errors. Then, we describe how to generate a summary of the graph based on the formulation. We describe subgraph generation, subgraph identification based on the encoding cost of structures, structure segmentation for label consistent structures by considering hierarchical labels, and model construction approaches. Table 3 shows the symbols used.

Minimum Description Length (MDL)  [6] is a model selection method where the best model $\hat{M}$ is the one that gives the best lossless compression:

$M$ is a model, $\mathcal{M}$ is the set of all possible models, $D$ is the given data, $L(M)$ is the length in bits of $M$, and $L(D|M)$ is the length in bits of $D$ when encoded using $M$.

Our target model $M\in\mathcal{M}$ is an ordered list of graph structures each having a type from $\Omega$ [1]. Each structure $s\in M$ corresponds to a certain portion of the adjacency matrix $\mathbf{A}$ describing its node’s labels and interconnectivity; there may be overlapped nodes between different structures, but there is no edge overlap. Each node has a hierarchical label (e.g., Table 1).

Following the MDL principle, our method for transmitting the adjacency matrix $\mathbf{A}$ is the following. We 1) transmit model $M$, 2) induce the approximate adjacency matrix $\mathbf{M}$ of $\mathbf{A}$ by filling out the connectivity of each structure in $M$, 3) transmit the error $\mathbf{E}$ which is derived from taking the exclusive OR between $\mathbf{M}$ and $\mathbf{A}$ as MDL requires lossless encoding, and 4) transmit labeling error $\mathbf{E}^{a}$ which is the label information for nodes not included in model $M$. We opt for a model $M$ that minimizes the encoding length of model $M$, error $\mathbf{E}$, and labeling error $\mathbf{E}^{a}$. Our problem definition is as follows.

Full encoding length of a model $M\in\mathcal{M}$ is the following:

We encode 1) the total number of structures in $M$ using $L_{\mathbb{N}}$, Rissanen’s optimal encoding [7] for integers greater than $0$, 2) the number of structures for each type using an index over a weak number composition for each structure type $x\in\Omega$ in model $M$, and 3) the structure type $x(s)$ for each structure $s\in M$ using optimal prefix code, 4) its connectivity $L_{t}(s)$, and 5) the hierarchical labels $L_{a}(s)$ of nodes in it. The detailed encodings for connectivity and hierarchical labels are described in the following two sections, respectively.

We describe how to encode the connectivity of each structure $s$ and derive its cost $L_{t}(s)$.

We describe how to encode the hierarchical labels for the nodes in a structure $s$ and derive its cost $L_{a}(s)$. Each node in our target graph has a hierarchical label: e.g., a character node may have a three-level hierarchical label ”character-tanker-blade master”. Furthermore, we assume that a different node may have a different depth of its label: e.g., a dungeon node may have only two-levels of hierarchy, like ”dungeon-advanced”. When transmitting a graph to the recipient, we assume that the recipient also knows how the hierarchical labels are structured. We start by formalizing label encoding costs for node labels in level-$k$, and describe a full label encoding cost $L_{a}(s)$ for hierarchical labels.

Base encoding. In level-$k$, the base label encoding cost of a structure $s$ is given by

where $|s|$ represents the number of nodes in the structure $s$. $l^{b}_{k,m}$ is the number of unique sibling labels for the level-$k$ label of the $m$-th node of the structure, where sibling labels of a label are those with the same upper level label (e.g. dealer, tanker, and buffer are sibling labels as they branch from character). For example, $l^{b}_{1,m}$, $l^{b}_{2,m}$, and $l^{b}_{3,m}$ are $4$, $3$ and $5$, respectively, when the labels of the $m$-th node are character-dealer-destroyer (see Table  1).

Label consistency. We define the label encoding costs for two special cases: 1) consistent structure, and 2) role-consistent structure. The two special cases allow us to reduce the label encoding cost. A consistent structure is the one containing only nodes with the same label, as shown in Fig. 5(a). A role-consistent structure is the one where nodes with the same role have the same label, as shown in Fig. 5(b). We define 4 roles in this work: 1) hub in a star structure, 2) spoke (neighbor of a star) in a star structure, 3) node belonging to the first set in a bipartite core, and 4) node belonging to the second set in a bipartite core. An inconsistent structure is the one that is neither consistent nor role-consistent, as shown in Fig. 5(c).

The label encoding cost for a consistent structure in level-$k$ is given by

where $l^{c}_{k}$ of a consistent structure is the number of unique sibling labels for the level-$k$ label. For a consistent structure, substituting $L^{c}_{a}(s,k)$ for $L^{base}_{a}(s,k)$ reduces the label encoding cost.

Next, the label encoding cost for a role-consistent structure in level-$k$ is given by

where $l^{rc}_{k,1}$ and $l^{rc}_{k,2}$ of a role-consistent structure are the number of unique sibling labels for the level-$k$ labels of the two roles that a role-consistent structure can have, respectively. For a role-consistent structure, substituting $L^{rc}_{a}(s,k)$ for $L_{a}(s,k)$ reduces the label encoding cost.

Hierarchical label. We define the full encoding cost $L_{a}(s)$ for hierarchical labels as follows:

where $h_{1}$ and $h_{2}$ mark the level in which consistent and role-consistent structures end, respectively; $h_{1}$ and $h_{2}$ are set to $0$ when consistent and role-consistent cases do not exist, respectively. $l_{1}$ is the number of unique labels in level-$1$ and $h$ is the number of levels. We encode 1) the number of each label at level-$1$ by using an index over a weak number composition, 2) consistent cases’ labels from level-$1$ to level-$h_{1}$, 3) role-consistent cases’ labels from level-$(h_{1}+1)$ to level-$h_{2}$, 4) remaining levels using the base encoding for inconsistent cases, and 5) $h_{1}$ and $h_{2}$. We consider the cases in the order of consistent, role-consistent, and inconsistent cases when moving from higher (e.g. level-1) to lower (e.g. level-3) levels.

Given the summary $M$ of $G$, it is vital to encode edges that are under or over-modeled by the model $M$ which we refer to as errors. Specifically, there are two types of errors to consider. The first type of error transpires in connectivity; if $area(s)$ is not identical to the regarding patch in $\mathbf{A}$, we encode the relevant errors. Another error type arises from labeling, where nodes that failed to be included in at least a structure lack label information.

We first decompose a given large graph into several subgraphs using a graph decomposition algorithm. We leverage SlashBurn [4] whose complexity is $O(T(m+n\log n))$ to generate subgraphs, where $m$ is the number of edges, $n$ is the number of nodes, and $T$ is the number of SlashBurn iterations. SlashBurn has been used for many graph tasks [8, 9, 10]; [1, 3] demonstrate that SlashBurn successfully decomposes real-world graphs for graph summarization. However, using other algorithms like SUBDUE [11] and BIGCLAM [12] is possible.

For each generated subgraph, we find an appropriate structure in $\Omega$ to minimize the encoding cost. For each subgraph, we 1) compute the encoding cost for all structure types, 2) compare the encoding costs, and 3) encode the subgraph as the structure type with the minimum encoding cost. We assume that each subgraph corresponds to one structure among the six ones.

We determine the role of each node in a given subgraph to encode the subgraph as one of the structure types. For example, which node is the hub of a star? Which nodes are included in set A or set B of a bipartite core? How to determine the order of nodes in a chain? We determine the role of each node in the following ways.

After obtaining the structures from a subgraph, we compute and compare the encoding costs of them. Given a subgraph $G^{\prime}$, we compute the local cost $L(M_{s})+L(\mathbf{E}_{M_{s}})$ [1, 3] to encode it as a structure $s$, where $M_{s}$ is the model consisting only of the subgraph $G^{\prime}$ encoded as $s$, and $\mathbf{E}_{M_{s}}$ is the error matrix derived by $\mathbf{E}_{M_{s}}=\mathbf{M}_{s}\oplus\mathbf{A}_{G^{\prime}}$. $\mathbf{A}_{G^{\prime}}$ is the adjacency matrix of the subgraph $G^{\prime}$ and $\mathbf{M}_{s}$ is the approximate adjacency matrix of $\mathbf{A}_{G^{\prime}}$ induced by $M_{s}$. Note that the labeling errors are ignored since nodes in a structure are connected and thus there are no uncovered nodes inside the structure. We compute $L(M_{s})$ by adding $L_{t}(s)$ and $L_{a}(s)$ (e.g., $L_{t}(st)+L_{a}(st)$ for $st$). The remaining terms except for $L_{t}(s)$ and $L_{a}(s)$ in Equation (1) are negligible, since $M_{s}$ consists only of the structure $s$. $L(\mathbf{E}_{M_{s}})$ is equal to $L(E^{+}_{M_{s}})+L(E^{-}_{M_{s}})$; $L(E^{+}_{M_{s}})$ and $L(E^{-}_{M_{s}})$ are the error encoding costs for $E^{+}_{M_{s}}$ and $E^{-}_{M_{s}}$, respectively, which are edges being over-modeled and under-modeled in the given subgraph $G^{\prime}$, respectively.

We add the best structure $s$ minimizing the local encoding cost $L(M_{s})+L(\mathbf{E}_{M_{s}})$ to the set $\mathcal{C}$ of structures.

We describe the segmentation of a structure considering hierarchical labels of nodes. The objective is to further reduce the label encoding cost for a structure considering the consistency of labels. Fig. 6 shows an example of comparison between a large inconsistent structure and small consistent structures. The inconsistent star graph in the left with 9 nodes has a low structure encoding cost, but a high label encoding cost. In contrast, the two decomposed star structures in the right have higher total structure encoding costs, but a lower total label encoding costs than the left case. We compare the total encoding costs before and after segmentation, and determine whether to segment or not by selecting the option leading to the minimum cost. We describe how to segment each structure, and how to extend the segmentation idea to hierarchical labels in the following two subsection, respectively.

We construct the final model which summarizes the given heterogeneous graph by carefully selecting structures among the candidate structures $\mathcal{C}$. Finding the best model exactly by exploring all possible subsets of candidate structures is intractable. Thus we propose the following heuristics to choose a subset of candidate structures in a scalable way.

• •

  Vanilla: All candidate structures are included in our summary, thus $M$ is equals to the set $C$ of the candidate structures.

• •

  Top-k: We pick the top-$k$ structures by sorting the local encoding gains of candidate structures in descending order. A local encoding gain is the number of bits reduced by encoding a subgraph as a structure $x$.

• •

  Benefit: We pick all structures whose local encoding gains are greater than zero.

GSHL uses the above approaches to finalize the model.

We evaluate the description cost and edge coverage of Blade & Soul graph by GSHL. Our baseline is Original model where the original edges are encoded with $L(\mathbf{E}^{-})$ and the labels are encoded with $L(\mathbf{E}^{a})$.

Table 4 compares the number of structures, the description cost, and the ratio of unexplained edges by Original and the three proposed models (GSHL-Vanilla, GSHL-Top-100, and GSHL-Benefit). GSHL-Vanilla summarizes the given graph with only $49\%$ of the bits w.r.t. Original and explains all but $1\%$ of the edges which are not modeled by $M$. GSHL-Top-100 explains $44\%$ of the edges and summarizes the given graph with $71\%$ of the bits w.r.t. Original, while containing only $100$ structures out of $25,740$ structures. Each structure in GSHL-Top-100 contains a larger number of nodes and edges compared to the structures not included. Compared to GSHL-Vanilla, GSHL-Top-100 has fewer number of structures but a larger cost. GSHL-Benefit shows a reasonable balance between the description cost and the number of structures. Compared to GSHL-Vanilla, it has a similar description cost, but contains $5.9\times$ smaller number of structures.

We present the discovery results of Blade & Soul graph using GSHL.

How can we exploit the result of summarization for finding similar accounts in Blade & Soul? We measure account similarities as follows:

1. 1.

   Matrix construction. Given the found structures, we first construct a node-structure matrix $\mathbf{B}$. The $(i,s)$-th element of the matrix $\mathbf{B}$ is set to a value $\gamma^{\alpha_{i,s}}$ where $\gamma$ is set to $0.7$ in this experiment and $\alpha_{i,s}$ is the minimum length of the shortest paths between account $i$ and nodes in structure $s$. If node $i$ is in structure $s$, $\alpha_{i,s}$ is set to $0$.

2. 2.

   Randomized SVD for features. We compute a randomized SVD for the matrix $\mathbf{B}$ to obtain features of accounts.

3. 3.

   Cosine similarity. We compute the cosine similarity of the two account feature vectors.

We pick a target account with id $0$, and find the two most similar accounts which have ids 3602 and 9. We observe that they share common characters, equipment, and often friends. Fig. 2(a) shows the relation of accounts 0 and 3602. Note that they have the characters with the same jobs (destroyer and blade master). The corresponding characters have common equipment and visited the same dungeons; e.g., the two destroyers have $21$ identical equipment, and visited $12$ identical dungeons. Fig. 2(b) shows the relation of accounts 0 and 9. We observe the similar patterns of characters and their related equipment and dungeons. They also share 18 common friends as well.

We measure the running times of GSHL varying the number of edges for scalability experiments. We generate 4 synthetic subgraphs using Forest Fire Sampling (FFS) [14], where (# of nodes, # of edges) are $(34203,78000)$, $(62339,246480)$, $(109764,780000)$, $(162759,2464800)$ and $(249455,7885487)$. Note that FFS enables generated subgraphs to follow the properties of real world graphs: heavy-tailed distributions, densification law, effective shrinking diameters [14]. As shown in Fig. 9, GSHL scales near-linearly with the number of edges.