  What are the key structures existing in a large real-world MMORPG (Massively
Multiplayer Online Role-Playing Game) graph? How can we compactly summarize an
MMORPG graph with hierarchical node labels, considering consistent
substructures at different levels of hierarchy? Recent MMORPGs generate complex
interactions between entities inducing a heterogeneous graph where each entity
has hierarchical labels. Succinctly summarizing a heterogeneous MMORPG graph is
crucial to better understand its structure; however it is a challenging task
since it needs to handle complex interactions and hierarchical labels
efficiently. Although there exist few methods to summarize a large-scale graph,
they do not deal with heterogeneous graphs with hierarchical node labels. We
propose GSHL, a novel method that summarizes a heterogeneous graph with
hierarchical labels. We formulate the encoding cost of hierarchical labels
using MDL (Minimum Description Length). GSHL exploits the formulation to
identify and segment subgraphs, and discovers compact and consistent structures
in the graph. Experiments on a large real-world MMORPG graph with multi-million
edges show that GSHL is a useful and scalable tool for summarizing the graph,
finding important and interesting structures in the graph, and finding similar
users.
