More Web Proxy on the site http://driver.im/

research-article

GAIA: graph classification using evolutionary computation

Authors:

Wei WangAuthors Info & Claims

SIGMOD '10: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data

Pages 879 - 890

https://doi.org/10.1145/1807167.1807262

Published: 06 June 2010 Publication History

Abstract

Discriminative subgraphs are widely used to define the feature space for graph classification in large graph databases. Several scalable approaches have been proposed to mine discriminative subgraphs. However, their intensive computation needs prevent them from mining large databases. We propose an efficient method GAIA for mining discriminative subgraphs for graph classification in large databases. Our method employs a novel subgraph encoding approach to support an arbitrary subgraph pattern exploration order and explores the subgraph pattern space in a process resembling biological evolution. In this manner, GAIA is able to find discriminative subgraph patterns much faster than other algorithms. Additionally, we take advantage of parallel computing to further improve the quality of resulting patterns. In the end, we employ sequential coverage to generate association rules as graph classifiers using patterns mined by GAIA. Extensive experiments have been performed to analyze the performance of GAIA and to compare it with two other state-of-the-art approaches. GAIA outperforms the other approaches both in terms of classification accuracy and runtime efficiency.

References

[1]

D. Bandyopadhyay, J. Huan, J. Liu, J. Prins, J. Snoeyink, W. Wang, and A. Tropsha. Structure-based function inference using protein family-specific fingerprints, Protein Science, vol. 15, pp. 1537--1543, 2006.

[2]

C. Chen, C. X. Lin, M. Fredrikson, M. Christodorescu, X. Yan, J. Han. Mining Graph Patterns Efficiently via Randomized Summaries, in Proceedings of the 35th International Conference on Very Large Data Bases (VLDB'09), 2009.

Digital Library

[3]

H. Cheng, D. Lo, Y. Zhou, X. Wang and X. Yan, Identifying Bug Signatures Using Discriminative Graph Mining, Proceedings of the 2009 International Symposium on Software Testing and Analysis (ISSTA 09), Chicago, IL, July 2009.

Digital Library

[4]

K. A. De Jong, Evolutionary Computation: A Unified Approach. Cambridge, MA, USA: MIT Press, 2006, p 71--113, p 130--132.

[5]

M. Deshpande, M. Kuramochi, N. Wale, and G. Karypis. Frequent Sub-structure Based Approaches for Classifying Chemical Compounds. IEEE Trans. Knowl. Data Eng. 17(8): 1036--1050, 2005.

Digital Library

[6]

M. A. Hasan and M. J. Zaki. Output Space Sampling for Graph Patterns, in Proceedings of the 35th International Conference on Very Large Data Bases (VLDB'09), 2009.

Digital Library

[7]

C. Helma, T. Cramer, S. Kramer, and L. D. Raedt. Data mining and machine learning techniques for the identification of mutagenicity inducing substructures and structure activity relationships of noncongeneric compounds. J. Chem. Inf. Comput. Sci., 44:1402--1411, 2004.

[8]

J. Huan, W. Wang, and J. Prins. Efficient mining of frequent subgraph in the presence of isomorphism, Proceedings of the 3rd IEEE International Conference on Data Mining (ICDM), pp. 549--552, 2003.

Digital Library

[9]

J. Huan, W. Wang, J. Prins, J. Yang. SPIN: Mining maximal frequent subgraphs from graph databases, in Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD), pp. 581--586, 2004.

Digital Library

[10]

A. Inokuchi, T. Washio, and H. Motoda. An apriori-based algorithm for mining frequent substructures from graph data. In Proc. of 2000 European Symp. Principle of Data Mining and Knowledge Discovery, pages 13--23, 2000.

Digital Library

[11]

N. Jin, C. Young and W. Wang, Graph Classification Based on Pattern Co-occurrence, in Proceedings of the ACM 18th Conference on Information and Knowledge Management (CIKM), Hongkong, 2009.

Digital Library

[12]

M. Kuramochi and G. Karypis. Frequent subgraph discovery. In Proc. of ICDM, pages 313--320, 2001.

Digital Library

[13]

S. Ranu and A. K. Singh. GraphSig: A Scalable Approach to Mining Significant Subgraphs in Large Graph Databases, in Proceedings of the 25th International Conference on Data Engineering (ICDE), April, 2009.

Digital Library

[14]

H. Saigo, N. Kraemer and K. Tsuda: Partial Least Squares Regression for Graph Mining, In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD2008), 578--586, 2008.

Digital Library

[15]

M. Thoma, H. Cheng, A. Gretton, J. Han, H. Kriegel, A. Smola, L. Song, P. Yu, X. Yan, K. Borgwardt. "Near-optimal supervised feature selection among frequent subgraphs", In SDM 2009, Sparks, Nevada, USA.

[16]

J. R. Ullmann. An algorithm for Subgraph Isomorphism. Journal of ACM, 23(1):31--42, 1976.

Digital Library

[17]

X. Yan, H. Cheng, J. Han, and P. S. Yu. Mining significant graph patterns by leap search. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 433--444, 2008.

Digital Library

[18]

X. Yan and J. Han. gSpan: graph-based substructure pattern mining. In Proceedings of the 2002 IEEE International Conference on Data Mining, pages 721--724. IEEE Computer Society, 2002.

Digital Library

Cited By

Kikaj AMarra GDe Raedt L(2024)Subgraph Mining for Graph Neural NetworksAdvances in Intelligent Data Analysis XXII10.1007/978-3-031-58547-0_12(141-152)Online publication date: 16-Apr-2024
https://doi.org/10.1007/978-3-031-58547-0_12
Yu BHe XDai J(2023)CLIG: A classification method based on bidirectional layer information granularityInformation Sciences10.1016/j.ins.2023.119662(119662)Online publication date: Sep-2023
https://doi.org/10.1016/j.ins.2023.119662
Moon HCho S(2023)A Subgraph Embedded GIN with Attention for Graph ClassificationIntelligent Data Engineering and Automated Learning – IDEAL 202310.1007/978-3-031-48232-8_33(356-367)Online publication date: 15-Nov-2023
https://doi.org/10.1007/978-3-031-48232-8_33
Show More Cited By

Index Terms

GAIA: graph classification using evolutionary computation
1. Computing methodologies
  1. Machine learning
2. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Graph classification based on pattern co-occurrence
CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge management

Subgraph patterns are widely used in graph classification, but their effectiveness is often hampered by large number of patterns or lack of discrimination power among individual patterns. We introduce a novel classification method based on pattern co-...
Graph Classification via Graph Structure Learning
Intelligent Information and Database Systems
Abstract
With the ability of representing structures and complex relationships between data, graph learning is widely applied in many fields. The problem of graph classification is important in graph analysis and learning. There are many popular graph ...
Discriminating Frequent Pattern Based Supervised Graph Embedding for Classification
Advances in Knowledge Discovery and Data Mining
Abstract
Graph is used to represent various complex relationships among objects and data entities. One of the emerging and important problems is graph classification that has tremendous impacts on various real-life applications. A good number of approaches ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '10: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data

June 2010

1286 pages

ISBN:9781450300322

DOI:10.1145/1807167

General Chair:
Ahmed Elmagarmid
Purdue University, USA
,
Program Chair:
Divyakant Agrawal
University of California at Santa Barbara, USA

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Results Reproduced / v1.1

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS '10

Sponsor:

SIGMOD

SIGMOD/PODS '10: International Conference on Management of Data

June 6 - 10, 2010

Indiana, Indianapolis, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
753
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kikaj AMarra GDe Raedt L(2024)Subgraph Mining for Graph Neural NetworksAdvances in Intelligent Data Analysis XXII10.1007/978-3-031-58547-0_12(141-152)Online publication date: 16-Apr-2024
https://doi.org/10.1007/978-3-031-58547-0_12
Yu BHe XDai J(2023)CLIG: A classification method based on bidirectional layer information granularityInformation Sciences10.1016/j.ins.2023.119662(119662)Online publication date: Sep-2023
https://doi.org/10.1016/j.ins.2023.119662
Moon HCho S(2023)A Subgraph Embedded GIN with Attention for Graph ClassificationIntelligent Data Engineering and Automated Learning – IDEAL 202310.1007/978-3-031-48232-8_33(356-367)Online publication date: 15-Nov-2023
https://doi.org/10.1007/978-3-031-48232-8_33
Levinas IScherz RLouzoun Y(2022)BFS-based distributed algorithm for parallel local-directed subgraph enumerationJournal of Complex Networks10.1093/comnet/cnac05110:6Online publication date: 1-Dec-2022
https://doi.org/10.1093/comnet/cnac051
Dang XSingh ABogdanov PYou HHsu B(2022)Discriminative Subnetworks with Regularized Spectral Learning for Global-State Network DataMachine Learning and Knowledge Discovery in Databases10.1007/978-3-662-44848-9_19(290-306)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-662-44848-9_19
Nguyen LZelinka ISnasel VNguyen LVo B(2022)Subgraph mining in a large graph: A reviewWIREs Data Mining and Knowledge Discovery10.1002/widm.145412:4Online publication date: 8-Mar-2022
https://doi.org/10.1002/widm.1454
Paranjape PDhabu MDeshpande P(2021)dSubSign: Classification of Instance-Feature Data Using Discriminative Subgraphs as Class SignaturesInternational Journal of Software Engineering and Knowledge Engineering10.1142/S021819402150028531:07(917-947)Online publication date: 23-Jul-2021
https://doi.org/10.1142/S0218194021500285
Wang DZhang ZMa YZhao TJiang TChawla NJiang M(2021)Modeling Co-evolution of Attributed and Structural Information in Graph SequenceIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.3094332(1-1)Online publication date: 2021
https://doi.org/10.1109/TKDE.2021.3094332
Prateek AKhan AGoyal ARanu S(2020)Mining Top-k pairs of correlated subgraphs in a large networkProceedings of the VLDB Endowment10.14778/3397230.339724513:9(1511-1524)Online publication date: 26-Jun-2020
https://dl.acm.org/doi/10.14778/3397230.3397245
Paranjape PDhabu MDeshpande P(2020)A novel classifier for multivariate instance using graph class signaturesFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-019-8263-514:4Online publication date: 3-Jan-2020
https://dl.acm.org/doi/10.1007/s11704-019-8263-5
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents