Mining rich graphs: a graph transformation approach

There have been a large number of studies mining graph patterns, however, most of them only process graphs with nodes and edges having a single label. Often there is a need to represent a rich dataset as graphs with nodes and edges having multiple labels - each label representing a feature in the dataset. For example, in a social network, multiple features could be associated to individuals (e.g., age, address, etc.) and their relationships (e.g., friend, foe, send message, etc.). To analyze these rich datasets, there is a need to extend existing graph mining algorithms to also mine rich graphs with nodes and edges having multiple labels. In this paper, we propose a novel algorithm and framework to transform richly labeled graphs (i.e., graphs with nodes and edges having multiple labels) to an equivalent set of simple labeled graphs (i.e., graphs with nodes and edges having single labels). The resultant simple graphs could be fed to most of the available graph mining algorithms to produce simple graph patterns. A reverse translation process is then employed to recover rich graph patterns from the simple graph patterns. We demonstrate that our proposed algorithm is scalable on various synthetic and real datasets. We experiment with three notable graph mining algorithms which are gSpan, CloseGraph, and Top-k LEAP algorithms. We show that our algorithm and framework could complement existing simple graph mining algorithms to allow them to mine rich graphs.