Title:

From Closed Tree Mining to Closed DAG Mining

Authors:

Alexandre Termier, Yoshinori Tamada, Seiya Imoto, Takashi Washio, Tomoyuki Higuchi

Abstract:

We present in this article a method to extract closed frequent sub-DAGs from DAG input data. This is one of the first frequent DAG-mining methods, and to our knowledge the first closed DAG mining algorithm. Moreover, our algorithm is able to extract embedded sub-DAGs from the data, whereas existing graph-mining methods can at most extract induced sub-DAGs. Our algorithm builds up upon our DRYADE closed frequent embedded attribute sub-tree mining algorithm, and by postprocessing its outputs discovers closed frequent embedded attribute sub-DAGs with one root in the data. We have tested our method on artificial data to show its efficiency. We also have made tests with real-world gene networks data, and con.rmed the existence of specific embedded sub-DAGs patterns, that could not be found with previous algorithms limited to extracting induced sub-DAGs.