Paper Info
Title
Extensions To Agrap Algorithm For Finding A Reduced Set Of Inexact Graph Patterns
Abstract
Most algorithms to mine graph patterns, during the searching process, require a pattern to be identical to its occurrences, relying on the graph isomorphism problem. However, in recent years, there has been interest in the case in which it is acceptable to have some differences between a pattern and its occurrences, whether these differences are in labels or in structure. Allowing some differences and using inexact matching to measure the similarity between graphs lead to the discovery of new patterns, but some important challenges, such as the increment on the number of found patterns, make the post-mining analysis harder. In this work we focus on two extensions of the AGraP algorithm, which mines inexact patterns, addressing the issue of reducing the output pattern set while trying to retain the useful information gained through the use of inexact matching. First, exploring a traditional approach, we propose the CloseAFG algorithm that focuses on closed patterns. Then, we propose the IntAFG algorithm to find a subset of patterns covering the original pattern set, while lessening redundancy among selected patterns. We show the performance of our approaches through some experiments on synthetic databases; additionally, we also show the usefulness of the reduced pattern sets for image classification.
Year
DOI
Venue
2018
10.1142/S0218001418600121
INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE
Keywords
Field
DocType
Closed frequent pattern, inexact matching, approximate patterns, frequent patterns in a single graph, interesting patterns
Graph,Graph patterns,Algorithm,Artificial intelligence,Mathematics,Graph isomorphism problem,Machine learning
Journal
Volume
Issue
ISSN
32
1
0218-0014
Citations 
PageRank 
References 
0
0.34
25
Authors
3
Name
Order
Citations
PageRank
Marisol Flores-Garrido1262.15
J. Ariel Carrasco-Ochoa223312.86
José Fco. Martínez-Trinidad318619.87