Paper Info
Title
Learning from graph data by putting graphs on the lattice
Abstract
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.
Year
DOI
Venue
2012
10.1016/j.eswa.2012.03.035
Expert Syst. Appl.
Keywords
Field
DocType
application domain,graph classification,intrinsic complex structure,statistical learning purpose,formal concept analysis,common practice,concept lattice,similarity measure,graph data,lattice structure
Comparability graph,Line graph,Graph property,Forbidden graph characterization,Computer science,Null graph,Artificial intelligence,Universal graph,Lattice graph,Graph (abstract data type),Machine learning
Journal
Volume
Issue
ISSN
39
12
0957-4174
Citations 
PageRank 
References 
3
0.37
36
Authors
2
Name
Order
Citations
PageRank
Viet Anh Nguyen112719.08
Akihiro Yamamoto213526.84