Learning from graph data by putting graphs on the lattice

Graph data have been of common practice in many application domains. However, it is very difficult to deal with graphs due to their intrinsic complex structure. In this paper, we propose to apply Formal Concept Analysis (FCA) to learning from graph data. We use subgraphs appearing in each of graph data as its attributes and construct a lattice based on FCA to organize subgraph attributes which are too numerous. For statistical learning purpose, we propose a similarity measure based on the concept lattice, taking into account the lattice structure explicitly. We prove that, the upper part of the lattice can provide a reliable and feasible way to compute the similarity between graphs. We also show that the similarity measure is rich enough to include some other measures as subparts. We apply the measure to a transductive learning algorithm for graph classification to prove its efficiency and effectiveness in practice. The high accuracy and low running time results confirm empirically the merit of the similarity measure based on the lattice.

► We study the correlations between graphs within the theory of Formal Concept Analysis. ► We present an efficient method for building the lattice of graph patterns. ► We propose a reliable and feasible graph similarity measure based on the lattice. ► We apply the measure to the problem of graph classification to show its effectiveness. ► Our method outperforms other state-of-art algorithms on various real-world datasets.