Graph-Based Relational Learning with a Polynomial Time Projection Algorithm

Abstract : The paper presents a new projection operator for graphs, named AC- projection, which exhibits good complexity properties as opposed to the graph isomorphism (Θ-subsumption) operator typically used in graph mining. We study the size of the search space and some practical properties of the projection operator. These properties give us a specialization algorithm using simple local operations. Then we prove ex- perimentally that we can achieve an important performance gain (poly- nomial complexity projection) without or with non-significant loss of discovered patterns quality.
Document type :
Conference papers
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00757471
Contributor : Michel Liquiere <>
Submitted on : Tuesday, November 27, 2012 - 9:51:13 AM
Last modification on : Tuesday, October 9, 2018 - 9:59:13 PM
Long-term archiving on: Thursday, February 28, 2013 - 3:42:43 AM

File

ilp2011_submission_50.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00757471, version 1

Collections

Citation

Brahim Douar, Michel Liquière, Chiraz Latiri, Yahya Slimani. Graph-Based Relational Learning with a Polynomial Time Projection Algorithm. ILP: Inductive Logic Programming, Jul 2011, Cumberland Lodge, United Kingdom. pp.98-112. ⟨lirmm-00757471⟩

Share

Metrics

Record views

222

Files downloads

446