Efficient Graph Sequence Mining Using Reverse Search
Summary :
The mining of frequent subgraphs from labeled graph data has been studied extensively. Furthermore, much attention has recently been paid to frequent pattern mining from graph sequences. A method, called GTRACE, has been proposed to mine frequent patterns from graph sequences under the assumption that changes in graphs are gradual. Although GTRACE mines the frequent patterns efficiently, it still needs substantial computation time to mine the patterns from graph sequences containing large graphs and long sequences. In this paper, we propose a new version of GTRACE that permits efficient mining of frequent patterns based on the principle of a reverse search. The underlying concept of the reverse search is a general scheme for designing efficient algorithms for hard enumeration problems. Our performance study shows that the proposed method is efficient and scalable for mining both long and large graph sequence patterns and is several orders of magnitude faster than the original GTRACE.
- Publication
- IEICE TRANSACTIONS on Information Vol.E95-D No.7 pp.1947-1958
- Publication Date
- 2012/07/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E95.D.1947
- Type of Manuscript
- PAPER
- Category
- Artificial Intelligence, Data Mining
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Akihiro INOKUCHI, Hiroaki IKUTA, Takashi WASHIO, "Efficient Graph Sequence Mining Using Reverse Search" in IEICE TRANSACTIONS on Information,
vol. E95-D, no. 7, pp. 1947-1958, July 2012, doi: 10.1587/transinf.E95.D.1947.
Abstract: The mining of frequent subgraphs from labeled graph data has been studied extensively. Furthermore, much attention has recently been paid to frequent pattern mining from graph sequences. A method, called GTRACE, has been proposed to mine frequent patterns from graph sequences under the assumption that changes in graphs are gradual. Although GTRACE mines the frequent patterns efficiently, it still needs substantial computation time to mine the patterns from graph sequences containing large graphs and long sequences. In this paper, we propose a new version of GTRACE that permits efficient mining of frequent patterns based on the principle of a reverse search. The underlying concept of the reverse search is a general scheme for designing efficient algorithms for hard enumeration problems. Our performance study shows that the proposed method is efficient and scalable for mining both long and large graph sequence patterns and is several orders of magnitude faster than the original GTRACE.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E95.D.1947/_p
Copy
@ARTICLE{e95-d_7_1947,
author={Akihiro INOKUCHI, Hiroaki IKUTA, Takashi WASHIO, },
journal={IEICE TRANSACTIONS on Information},
title={Efficient Graph Sequence Mining Using Reverse Search},
year={2012},
volume={E95-D},
number={7},
pages={1947-1958},
abstract={The mining of frequent subgraphs from labeled graph data has been studied extensively. Furthermore, much attention has recently been paid to frequent pattern mining from graph sequences. A method, called GTRACE, has been proposed to mine frequent patterns from graph sequences under the assumption that changes in graphs are gradual. Although GTRACE mines the frequent patterns efficiently, it still needs substantial computation time to mine the patterns from graph sequences containing large graphs and long sequences. In this paper, we propose a new version of GTRACE that permits efficient mining of frequent patterns based on the principle of a reverse search. The underlying concept of the reverse search is a general scheme for designing efficient algorithms for hard enumeration problems. Our performance study shows that the proposed method is efficient and scalable for mining both long and large graph sequence patterns and is several orders of magnitude faster than the original GTRACE.},
keywords={},
doi={10.1587/transinf.E95.D.1947},
ISSN={1745-1361},
month={July},}
Copy
TY - JOUR
TI - Efficient Graph Sequence Mining Using Reverse Search
T2 - IEICE TRANSACTIONS on Information
SP - 1947
EP - 1958
AU - Akihiro INOKUCHI
AU - Hiroaki IKUTA
AU - Takashi WASHIO
PY - 2012
DO - 10.1587/transinf.E95.D.1947
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E95-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2012
AB - The mining of frequent subgraphs from labeled graph data has been studied extensively. Furthermore, much attention has recently been paid to frequent pattern mining from graph sequences. A method, called GTRACE, has been proposed to mine frequent patterns from graph sequences under the assumption that changes in graphs are gradual. Although GTRACE mines the frequent patterns efficiently, it still needs substantial computation time to mine the patterns from graph sequences containing large graphs and long sequences. In this paper, we propose a new version of GTRACE that permits efficient mining of frequent patterns based on the principle of a reverse search. The underlying concept of the reverse search is a general scheme for designing efficient algorithms for hard enumeration problems. Our performance study shows that the proposed method is efficient and scalable for mining both long and large graph sequence patterns and is several orders of magnitude faster than the original GTRACE.
ER -
English
