  Structural Entropy (SE) measures the structural information contained in a
graph. Minimizing or maximizing SE helps to reveal or obscure the intrinsic
structural patterns underlying graphs in an interpretable manner, finding
applications in various tasks driven by networked data. However, SE ignores the
heterogeneity inherent in the graph relations, which is ubiquitous in modern
networks. In this work, we extend SE to consider heterogeneous relations and
propose the first metric for multi-relational graph structural information,
namely, Multi-relational Structural Entropy (MrSE). To this end, we first cast
SE through the novel lens of the stationary distribution from random surfing,
which readily extends to multi-relational networks by considering the choices
of both nodes and relation types simultaneously at each step. The resulting
MrSE is then optimized by a new greedy algorithm to reveal the essential
structures within a multi-relational network. Experimental results highlight
that the proposed MrSE offers a more insightful interpretation of the structure
of multi-relational graphs compared to SE. Additionally, it enhances the
performance of two tasks that involve real-world multi-relational graphs,
including node clustering and social event detection.
