  Graph pattern mining methods can extract informative and useful patterns from
large-scale graphs and capture underlying principles through the overwhelmed
information. Contrast analysis serves as a keystone in various fields and has
demonstrated its effectiveness in mining valuable information. However, it has
been long overlooked in graph pattern mining. Therefore, in this paper, we
introduce the concept of contrast subgraph, that is, a subset of nodes that
have significantly different edges or edge weights in two given graphs of the
same node set. The major challenge comes from the gap between the contrast and
the informativeness. Because of the widely existing noise edges in real-world
graphs, the contrast may lead to subgraphs of pure noise. To avoid such
meaningless subgraphs, we leverage the similarity as the cornerstone of the
contrast. Specifically, we first identify a coherent core, which is a small
subset of nodes with similar edge structures in the two graphs, and then induce
contrast subgraphs from the coherent cores. Moreover, we design a general
family of coherence and contrast metrics and derive a polynomial-time algorithm
to efficiently extract contrast subgraphs. Extensive experiments verify the
necessity of introducing coherent cores as well as the effectiveness and
efficiency of our algorithm. Real-world applications demonstrate the tremendous
potentials of contrast subgraph mining.
