Extracting multiple layers from data having graph structures

Much data such as geometric image data and drawings have graph structures. Such data are called graph structured data. In order to manage efficiently such graph structured data, we need to analyze and abstract graph structures of such data. The purpose of this paper is to find knowledge representations which indicate plural abstractions of graph structured data. Firstly, we introduce a term graph as a graph pattern having structural variables, and a substitution over term graphs which is graph rewriting system. Next, for a graph G, we define a multiple layer (g, (θ1,…,θk)) of G as a pair of a term graph g and a list of k substitutions θ1,…,θk such that G can be obtained from g by applying substitutions θ1…,θk to g. In the same way, for a set S of graphs, we also define a multiple layer for S as a pair (D,Θ) of a set D of term graphs and a list Θ of substitutions. Secondly, for a graph G and a set S of graphs, we present effective algorithms for extracting minimal multiple layers of G and S which give us stratifying abstractions of G and S, respectively. Finally, we report experimental results obtained by applying our algorithms to both artificial data and drawings of power plants which are real world data.

Extracting multiple layers from data having graph structures