Learning patterns in dynamic graphs with application to biological networks.

摘要

We propose dynamic graph-based relational mining approach to learn structural patterns in graphs or networks as they change over time. There are a huge amount of data that can be represented as graphs, and a majority of the data have dynamic properties as well as structural properties. Most current graph-based data mining approaches focus on only static graphs, but few approaches address dynamic graphs. Our approach analyzes a dynamic graph containing a sequence of graphs, and discovers rules that capture the changes that occur between pairs of graphs in the sequence. These rules represent the graph rewrite rules that the first graph must go through to be isomorphic to the second graph. Then, our approach feeds the graph rewrite rules into a machine learning system that learns general transformation rules describing the types of changes that occur for a class of dynamic graphs. The discovered graph-rewriting rules show how graphs change over time, and the transformation rules show the repeated patterns in the structural changes.;We apply our approach to the analysis of the dynamics of biological networks with the cell. A cell is not only a basic unit to a life, but also an optimal system. This system is well-organized so that it can be represented as biological networks, which include various molecules and relationships between them. Moreover, biological networks also change their structure over time to express dynamics of the biological systems. In our research, we apply the dynamic graph-based relational mining approach to biological networks to understand how the biosystems change over time. We evaluate our results using coverage and prediction metrics, and compare our results to those in biological literature. Our results show important patterns in the dynamics of biological networks, for example, discovering known patterns in the biological networks. Results also show the learned rules accurately predict future changes in the networks.;We also evaluate our approach using two other data: synthetic data and Enron email data. We apply our approach to the synthetic data with several varied conditions, such as noise, size and density ratio. We also apply our approach to the Enron email data, and compare to an alternative approach.