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

research-article

Graph classification based on pattern co-occurrence

Authors:

Wei WangAuthors Info & Claims

CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge management

Pages 573 - 582

https://doi.org/10.1145/1645953.1646027

Published: 02 November 2009 Publication History

Abstract

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-occurrence to derive graph classification rules. Our method employs a pattern exploration order such that the complementary discriminative patterns are examined first. Patterns are grouped into co-occurrence rules during the pattern exploration, leading to an integrated process of pattern mining and classifier learning. By taking advantage of co-occurrence information, our method can generate strong features by assembling weak features. Unlike previous methods that invoke the pattern mining process repeatedly, our method only performs pattern mining once. In addition, our method produces a more interpretable classifier and shows better or competitive classification effectiveness in terms of accuracy and execution time.

References

[1]

C. Borgelt and M.R. Berhold. Mining molecular fragments: Finding relevant substructures of molecules. In ICDM'02.

Digital Library

[2]

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.

[3]

D. Bandyopadhyay and J. Snoeyink. "Almost Delaunay Simplices: Nearest Neighbor Relations for Imprecise Points". ACM-SIAM Symposium On Discrete Algorithms (SODA 2004), New Orleans, Jan 11--13, 2004, pages 403--412.

Digital Library

[4]

L. Breiman. "Random Forests". Machine Learning 45 (1): 5--32, 2001.

Digital Library

[5]

C. Chang and C. Lin. LIBSVM: a library for support vector machines, 2001. Software available at: http://www.csie.ntu.edu.tw/~cjlin/libsvm/

[6]

C. Chen, C. X. Lin, X. Yan, and J. Han, On Effective Presentation of Graph Patterns: A Structural Representative Approach, in Proc. 2008 ACM Conf. on Information and Knowledge Management (CIKM'08), Napa Valley, CA, Oct. 2008.

Digital Library

[7]

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

[8]

R. Goldman and J. Widom. Dataguides: Enabling query formulation and optimization in semistructured databases. In VLDB'97.

Digital Library

[9]

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.

[10]

J. Huan, W. Wang, D. Bandyopadhyay, J. Snoeyink, J. Prins, and A. Tropsha. Mining spatial motifs from protein structure graphs, Proceedings of the 8th Annual International Conference on Research in Computational Molecular Biology (RECOMB), pp. 308--315, 2004.

Digital Library

[11]

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

[12]

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

[13]

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

Digital Library

[14]

T. Kudo, E. Maeda, and Y. Matsumoto. An application of boosting to graph classification. In Advances in Neural Information Processing Systems 17, pages 729--736. MIT Press, 2005.

[15]

J. Kazius, S. Nijssen, J. Kok, and T. Back A.P. Ijzerman. Substructure mining using elaborate chemical representation. J. Chem. Inf. Model., 46:597--605, 2006.

[16]

S. Nowozin, K. Tsuda, T. Uno, T. Kudo, and G. Bakir. Weighted substructure mining for image analysis. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), IEEE Computer Society, 2007.

[17]

S. Raghavan and H. Garcia-Molina, Representing web graphs. In Proceedings of the IEEE Intl. Conference on Data Engineering, 2003.

[18]

H. Saigo, T. Kadowaki, and K. Tsuda. A linear programming approach for molecular QSAR analysis. In International Workshop on Mining and Learning with Graphs (MLG), pages 85--96, 2006.

[19]

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

[20]

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.

[21]

V. Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag, 1995.

Digital Library

[22]

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

[23]

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

[24]

F. Zhu, X. Yan, J. Han, and P. S. Yu, gPrune: A Constraint Pushing Framework for Graph Pattern Mining, in Proc. 2007 Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD'07), Nanjing, China, May 2007.

Digital Library

Cited By

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
Zhang XWang HYu JChen CWang XZhang W(2022)Bipartite graph capsule networkWorld Wide Web10.1007/s11280-022-01009-226:1(421-440)Online publication date: 14-Feb-2022
https://doi.org/10.1007/s11280-022-01009-2
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
Show More Cited By

Index Terms

Graph classification based on pattern co-occurrence
1. Computing methodologies
  1. Machine learning
2. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

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 ...
On extending extreme learning machine to non-redundant synergy pattern based graph classification

Graph patterns are widely used to define the feature space for building an efficient graph classification model. Synergy graph patterns refer to those graphs, where the relationships among the nodes are highly inseparable. Compared with the general graph ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge management

November 2009

2162 pages

ISBN:9781605585123

DOI:10.1145/1645953

General Chairs:
David Cheung
University of Hong Kong, Hong Kong
,
Il-Yeol Song
Drexel University, USA
,
Program Chairs:
Wesley Chu
UCLA, USA
,
Xiaohua Hu
Drexel University, USA
,
Jimmy Lin
University of Maryland, USA

Copyright © 2009 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 November 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CIKM '09

Sponsor:

CIKM '09: Conference on Information and Knowledge Management

November 2 - 6, 2009

Hong Kong, China

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
735
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Zhang XWang HYu JChen CWang XZhang W(2022)Bipartite graph capsule networkWorld Wide Web10.1007/s11280-022-01009-226:1(421-440)Online publication date: 14-Feb-2022
https://doi.org/10.1007/s11280-022-01009-2
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
Matsuyama KOzaki T(2021)Heuristic extraction of co-occurrence patterns for effective construction of graph-based interpretable decision sets2021 Ninth International Symposium on Computing and Networking Workshops (CANDARW)10.1109/CANDARW53999.2021.00033(159-165)Online publication date: Nov-2021
https://doi.org/10.1109/CANDARW53999.2021.00033
Joaristi MPurohit SDeshmukh RChin G(2020)Data-Driven Template Discovery Using Graph Convolutional Neural Networks2020 IEEE International Conference on Big Data (Big Data)10.1109/BigData50022.2020.9378318(2534-2538)Online publication date: 10-Dec-2020
https://doi.org/10.1109/BigData50022.2020.9378318
Paranjape PDhabu MDeshpande P(2020)A novel classifier for multivariate instance using graph class signaturesFrontiers of Computer Science10.1007/s11704-019-8263-514:4Online publication date: 3-Jan-2020
https://doi.org/10.1007/s11704-019-8263-5
Bellodi ESatoh KSugiyama M(2019)Summarizing significant subgraphs by probabilistic logic programmingIntelligent Data Analysis10.3233/IDA-18433923:6(1299-1312)Online publication date: 8-Nov-2019
https://doi.org/10.3233/IDA-184339
Saidi RDhifli WMaddouri MMephu Nguifo E(2019)Efficiently Mining Recurrent Substructures from Protein Three-Dimensional Structure GraphsJournal of Computational Biology10.1089/cmb.2018.017126:6(561-571)Online publication date: Jun-2019
https://doi.org/10.1089/cmb.2018.0171
Nguyen VNguyen L(2018)An efficient heuristic approach for learning a set of composite graph classification rulesIntelligent Data Analysis10.3233/IDA-16334322:3(581-596)Online publication date: 9-May-2018
https://doi.org/10.3233/IDA-163343
Hegde KMagdon-Ismail M(2018)Separating Terrorist-Like Topological Signatures Embedded in Benign NetworksMILCOM 2018 - 2018 IEEE Military Communications Conference (MILCOM)10.1109/MILCOM.2018.8599854(1-9)Online publication date: Oct-2018
https://doi.org/10.1109/MILCOM.2018.8599854
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