  Community detection in graphs, data clustering, and local pattern mining are
three mature fields of data mining and machine learning. In recent years,
attributed subgraph mining is emerging as a new powerful data mining task in
the intersection of these areas. Given a graph and a set of attributes for each
vertex, attributed subgraph mining aims to find cohesive subgraphs for which (a
subset of) the attribute values has exceptional values in some sense. While
research on this task can borrow from the three abovementioned fields, the
principled integration of graph and attribute data poses two challenges: the
definition of a pattern language that is intuitive and lends itself to
efficient search strategies, and the formalization of the interestingness of
such patterns. We propose an integrated solution to both of these challenges.
The proposed pattern language improves upon prior work in being both highly
flexible and intuitive. We show how an effective and principled algorithm can
enumerate patterns of this language. The proposed approach for quantifying
interestingness of patterns of this language is rooted in information theory,
and is able to account for prior knowledge on the data. Prior work typically
quantifies interestingness based on the cohesion of the subgraph and for the
exceptionality of its attributes separately, combining these in a parametrized
trade-off. Instead, in our proposal this trade-off is implicitly handled in a
principled, parameter-free manner. Extensive empirical results confirm the
proposed pattern syntax is intuitive, and the interestingness measure aligns
well with actual subjective interestingness.
