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

Article

Cyclic pattern kernels for predictive graph mining

Authors:

Tamás Horváth,

Thomas Gärtner,

Stefan WrobelAuthors Info & Claims

KDD '04: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 158 - 167

https://doi.org/10.1145/1014052.1014072

Published: 22 August 2004 Publication History

Abstract

With applications in biology, the world-wide web, and several other areas, mining of graph-structured objects has received significant interest recently. One of the major research directions in this field is concerned with predictive data mining in graph databases where each instance is represented by a graph. Some of the proposed approaches for this task rely on the excellent classification performance of support vector machines. To control the computational cost of these approaches, the underlying kernel functions are based on frequent patterns. In contrast to these approaches, we propose a kernel function based on a natural set of cyclic and tree patterns independent of their frequency, and discuss its computational aspects. To practically demonstrate the effectiveness of our approach, we use the popular NCI-HIV molecule dataset. Our experimental results show that cyclic pattern kernels can be computed quickly and offer predictive performance superior to recent graph kernels based on frequent patterns.

References

[1]

R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A. I. Verkamo. Fast discovery of association rules. In U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, editors, Advances in Knowledge Discovery and Data Mining, Chapter 12, pages 307 -- 328. AAAI/MIT Press, Cambridge, USA, 1996.

Digital Library

[2]

H. Alt, U. Fuchs, and K. Kriegel. On the number of simple cycles in planar graphs. Combinatorics, Probability & Computing, 8(5):397--405, 1999.

Digital Library

[3]

Asai, Arimura, Uno, and Nakano. Discovering frequent substructures in large unordered trees. In Proc. of the 6th International Conference on Discovery Science, volume 2843 of LNAI, pages 47--61. Springer Verlag, 2003.

[4]

C. Borgelt and M. R. Berthold. Mining molecular fragments: Finding relevant substructures of molecules. In Proc. of the 2002 IEEE International Conference on Data Mining, pages 51--58. IEEE Computer Society, 2002.

Digital Library

[5]

B. E. Boser, I. M. Guyon, and V. N. Vapnik. A training algorithm for optimal margin classifiers. In D. Haussler, editor, Proc. of the 5th Annual ACM Workshop on Computational Learning Theory, pages 144--152. ACM Press, 1992.

Digital Library

[6]

M. Collins and N. Duffy. Convolution kernels for natural language. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems, volume 14. MIT Press, 2002.

[7]

C. Cortes, P. Haffner, and M. Mohri. Positive definite rational kernels. In Learning Theory and Kernel Machines, 16th Annual Conference on Learning Theory and 7th Kernel Workshop, Proceedings. volume 2843 of LNAI, pages 41--56. Springer Verlag, 2003.

[8]

M. Deshpande, M. Kuramochi, and G. Karypis. Automated approaches for classifying structures. In Proc. of the 2nd ACM SIGKDD Workshop on Data Mining in Bioinformatics, 2002.

[9]

M. Deshpande, M. Kuramochi, and G. Karypis. Frequent sub-structure based approaches for classifying chemical compounds. In Proc. of the 3rd IEEE International Conference on Data Mining, pages 35--42. IEEE Computer Society, 2003.

Digital Library

[10]

R. Diestel. Graph theory. 2nd edition, Springer Verlag, 2000.

[11]

H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Perspectives in Mathematical Logic. 2nd edition, Springer Verlag, 1999.

[12]

M. Fürer. Graph isomorphism testing without numberics for graphs of bounded eigenvalue multiplicity. In Proc. of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 624--631. ACM Press, 1995.

Digital Library

[13]

T. Gärtner. Exponential and geometric kernels for graphs. In NIPS Workshop on Unreal Data: Principles of Modeling Nonvectorial Data, 2002.

[14]

T. Gärtner, K. Driessens, and J. Ramon. Graph kernels and gaussian processes for relational reinforcement learning. In Proc. of the 13th International Conference on Inductive Logic Programming, volume 2835 of LNAI, pages 146--163. Springer Verlag, 2003.

[15]

T. Gärtner, P. A. Flach, and S. Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning Theory and Kernel Machines, 16th Annual Conference on Learning Theory and 7th Kernel Workshop, Proceedings. volume 2843 of LNAI, pages 129--143. Springer Verlag, 2003.

[16]

T. Graepel. PAC-Bayesian Pattern Classification with Kernels. PhD thesis, TU Berlin, 2002.

[17]

D. Haussler. Convolution kernels on discrete structures. Technical report, Department of Computer Science, University of California at Santa Cruz, 1999.

[18]

T. Joachims. Making large--scale SVM learning practical. In B. Schölkopf, C. J. C. Burges, and A. J. Smola, editors, Advances in Kernel Methods --- Support Vector Learning, pages 169--184. MIT Press, 1999.

Digital Library

[19]

H. Kashima, K. Tsuda, and A. Inokuchi. Marginalized kernels between labeled graphs. In Proc. of the 20th International Conference on Machine Learning, pages 321--328. AAAI Press, 2003.

[20]

S. Kramer, L. D. Raedt, and C. Helma. Molecular feature mining in HIV data. In Proc. of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 136--143. ACM Press, 2001.

Digital Library

[21]

S. R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal. The web as a graph. In Proc. of the 19th ACM Symposium on Principles of Database Systems, pages 1--10. ACM Press, 2000.

Digital Library

[22]

M. Kuramochi and G. Karypis. Frequent subgraph discovery. In Proc. of the IEEE International Conference on Data Mining, pages 313--320, IEEE Computer Society, 2001.

Digital Library

[23]

C. Leslie and R. Kuang. Fast kernels for inexact string matching. In Learning Theory and Kernel Machines, 16th Annual Conference on Learning Theory and 7th Kernel Workshop, Proceedings. volume 2843 of LNAI, pages 114--128. Springer Verlag, 2003.

[24]

H. Lodhi, J. Shawe-Taylor, N. Christianini, and C. Watkins. Text classification using string kernels. In T. Leen, T. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems, volume 13. MIT Press, 2001.

[25]

F. Provost, T. Fawcett, and R. Kohavi. The case against accuracy estimation for comparing induction algorithms. In Proc. of the 15th International Conference on Machine Learning, pages 445--453. Morgan Kaufmann, 1998.

Digital Library

[26]

F. J. Provost and T. Fawcett. Robust classification for imprecise environments. Machine Learning, 42(3):203--231, 2001.

Digital Library

[27]

R. C. Read and R. E. Tarjan. Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks, 5(3):237--252, 1975.

Digital Library

[28]

B. Schölkopf and A. J. Smola. Learning with Kernels. MIT Press, 2002.

[29]

R. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146--160, 1972.

Digital Library

[30]

L. G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410--421, 1979.

Digital Library

[31]

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

Digital Library

[32]

P. Vismara. Union of all the minimum cycle bases of a graph. The Electronic Journal of Combinatorics, 4(1):73--87, 1997.

[33]

C. Watkins. Kernels from matching operations. Technical report, Department of Computer Science, Royal Holloway, University of London, 1999.

[34]

M. Zaki. Efficiently mining frequent trees in a forest. In Proc. of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 71--80. ACM Press, 2002.

Digital Library

Cited By

Kuhar YČibej U(2024)Symmetry Kernel for Graph ClassificationProceedings of the 32nd International Conference on Information Systems Development10.62036/ISD.2024.102Online publication date: 2024
https://doi.org/10.62036/ISD.2024.102
Bhattarai BHuang H(2024)Prov2vec: Learning Provenance Graph Representation for Anomaly Detection in Computer SystemsProceedings of the 19th International Conference on Availability, Reliability and Security10.1145/3664476.3664494(1-14)Online publication date: 30-Jul-2024
https://dl.acm.org/doi/10.1145/3664476.3664494
Qian CTang HLiang HLiu YBaeza-Yates RBonchi F(2024)Reimagining Graph Classification from a Prototype View with Optimal Transport: Algorithm and TheoremProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671696(2444-2454)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671696
Show More Cited By

Index Terms

Cyclic pattern kernels for predictive graph mining
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
        Supervised learning by classification
    2. Machine learning approaches
      1. Classification and regression trees
2. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Mining frequent cross-graph quasi-cliques

Joint mining of multiple datasets can often discover interesting, novel, and reliable patterns which cannot be obtained solely from any single source. For example, in bioinformatics, jointly mining multiple gene expression datasets obtained by different ...
Mining Frequent Subgraph Patterns from Uncertain Graph Data

In many real applications, graph data is subject to uncertainties due to incompleteness and imprecision of data. Mining such uncertain graph data is semantically different from and computationally more challenging than mining conventional exact graph ...
On mining cross-graph quasi-cliques
KDD '05: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining

Joint mining of multiple data sets can often discover interesting, novel, and reliable patterns which cannot be obtained solely from any single source. For example, in cross-market customer segmentation, a group of customers who behave similarly in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '04: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining

August 2004

874 pages

ISBN:1581138881

DOI:10.1145/1014052

General Chairs:
Won Kim
Cyber Database Solutions
,
Ronny Kohavi
Amazon.com
,
Program Chairs:
Johannes Gehrke
Cornell University
,
William DuMouchel
AT&T Labs Research

Copyright © 2004 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: 22 August 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

KDD04

Sponsor:

KDD04: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 22 - 25, 2004

WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

184
Total Citations
View Citations
2,188
Total Downloads

Downloads (Last 12 months)53
Downloads (Last 6 weeks)5

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kuhar YČibej U(2024)Symmetry Kernel for Graph ClassificationProceedings of the 32nd International Conference on Information Systems Development10.62036/ISD.2024.102Online publication date: 2024
https://doi.org/10.62036/ISD.2024.102
Bhattarai BHuang H(2024)Prov2vec: Learning Provenance Graph Representation for Anomaly Detection in Computer SystemsProceedings of the 19th International Conference on Availability, Reliability and Security10.1145/3664476.3664494(1-14)Online publication date: 30-Jul-2024
https://dl.acm.org/doi/10.1145/3664476.3664494
Qian CTang HLiang HLiu YBaeza-Yates RBonchi F(2024)Reimagining Graph Classification from a Prototype View with Optimal Transport: Algorithm and TheoremProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671696(2444-2454)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671696
Zhang JLei YWang YZhou CSheng V(2024)Hierarchical Graph Capsule Networks for Molecular Function Classification With Disentangled RepresentationsIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2022.323335421:4(1072-1082)Online publication date: Jul-2024
https://doi.org/10.1109/TCBB.2022.3233354
Ye WTian HChen Q(2024)Multiscale Wasserstein Shortest-Path Graph Kernels for Graph ClassificationIEEE Transactions on Artificial Intelligence10.1109/TAI.2023.33338305:6(2973-2984)Online publication date: Jun-2024
https://doi.org/10.1109/TAI.2023.3333830
Aboulfath YBougueroua SCimas ABarth DGaigeot M(2024)Time-Resolved Graphs of Polymorphic Cycles for H-Bonded Network Identification in Flexible BiomoleculesJournal of Chemical Theory and Computation10.1021/acs.jctc.3c0103120:3(1019-1035)Online publication date: 18-Jan-2024
https://doi.org/10.1021/acs.jctc.3c01031
Welke PThiessen MJogl FGärtner TKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Expectation-complete graph representations with homomorphismsProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619944(36910-36925)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3619944
Zheng YZhang ZLuo QXie ZYu D(2023)A Truss-Based Framework for Graph Similarity ComputationJournal of Database Management10.4018/JDM.32208734:1(1-18)Online publication date: 25-Apr-2023
https://dl.acm.org/doi/10.4018/JDM.322087
Besta MRenc PGerstenberger RSylos Labini PZiogas AChen TGianinazzi LScheidl FSzenes KCarigiet AIff PKwasniewski GKanakagiri RGe CJaeger SWąs JVella FHoefler TMohror KArnold DBadia R(2023)High-Performance and Programmable Attentional Graph Neural Networks with Global Tensor FormulationsProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3581784.3607067(1-16)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3581784.3607067
Bouritsas GFrasca FZafeiriou SBronstein M(2023)Improving Graph Neural Network Expressivity via Subgraph Isomorphism CountingIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2022.315431945:1(657-668)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TPAMI.2022.3154319
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