Graph Classification via Graph Structure Learning
Pages 269 - 281
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 classification methods based on substructures such as graph kernels or ones based on frequent subgraph mining. Graph kernels use handcraft features, hence it is so poor generalization. The process of frequent subgraph mining is NP-complete because we need to test isomorphism subgraph, so methods based on frequent subgraph mining are ineffective. To address this limitation, in this work, we proposed novel graph classification via graph structure learning, which automatically learns hidden representations of substructures. Inspired by doc2vec, a successful and efficient model in Natural Language Processing, graph embedding uses rooted subgraph and topological features to learn representations of graphs. Then, we can easily build a Machine Learning model to classify them. We demonstrate our method on several benchmark datasets in comparison with state-of-the-art baselines and show its advantages for classification tasks.
References
[1]
Szklarczyk D et al. STRING v11: protein–protein association networks with increased coverage, supporting functional discovery in genome-wide experimental datasets Nucleic Acids Res. 2019 47 D1 D607-D613
[2]
Trinajstic, N.: Chemical Graph Theory. CRC Press (2018)
[3]
Siew CS, Wulff DU, Beckage NM, and Kenett YN Cognitive network science: a review of research on cognition through the lens of network representations, processes, and dynamics Complexity 2019 2019 2108423
[4]
Lanciano, T., Bonchi, F., Gionis, A.: Explainable classification of brain networks via contrast subgraphs. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 3308–3318 (2020)
[5]
Tabassum S, Pereira FS, Fernandes S, and Gama J Social network analysis: an overview Wiley Interdisc. Rev.: Data Min. Knowl. Discovery 2018 8 5
[6]
Chen X, Jia S, and Xiang Y A review: knowledge reasoning over knowledge graph Expert Syst. Appl. 2020 141
[7]
Domingo-Fernández D et al. COVID-19 knowledge graph: a computable, multi-modal, cause-and-effect knowledge model of COVID-19 pathophysiology Bioinformatics 2021 37 9 1332-1334
[8]
Shervashidze N, Schweitzer P, Van Leeuwen EJ, Mehlhorn K, and Borgwardt KM Weisfeiler-lehman graph kernels J. Mach. Learn. Res. 2011 12 9 2539-2561
[9]
Kriege NM, Johansson FD, and Morris C A survey on graph kernels Appl. Netw. Sci. 2019 5 1 1-42
[10]
Chang CC and Lin CJ LIBSVM: a library for support vector machines ACM Trans. Intell. Syst, Technol. (TIST) 2011 2 3 1-27
[11]
Vishwanathan SVN, Schraudolph NN, Kondor R, and Borgwardt KM Graph kernels J. Mach. Learn. Res. 2010 11 1201-1242
[12]
Borgwardt, K.M., Kriegel, H.P.: Shortest-path kernels on graphs. In: Fifth IEEE International Conference on Data Mining (ICDM’05), pp. 8-pp. IEEE (2005)
[13]
Nikolentzos, G., Meladianos, P., Rousseau, F., Stavrakas, Y., Vazirgiannis, M.: Shortest-path graph kernels for document similarity. In: Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 1890–1900 (2017)
[14]
Horváth, T., Gärtner, T., Wrobel, S.: Cyclic pattern kernels for predictive graph mining. In: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 158–167 (2004)
[15]
Shervashidze, N., Vishwanathan, S. V. N., Petri, T., Mehlhorn, K., Borgwardt, K.: Efficient graphlet kernels for large graph comparison. In: Artificial Intelligence and Statistics, pp. 488–495. PMLR (2009)
[16]
Ramon, J., Gärtner, T.: Expressivity versus efficiency of graph kernels. In: Proceedings of the First International Workshop on Mining Graphs, Trees and Sequences, pp. 65–74 (2003)
[17]
Fei, H., Huan, J.: Structure feature selection for graph classification. In: Proceedings of the 17th ACM Conference on Information and Knowledge Management, pp. 991–1000 (2008)
[18]
Kong, X., Yu, P.S.: Semi-supervised feature selection for graph classification. In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 793–802 (2010)
[19]
Schöning U Graph isomorphism is in the low hierarchy J. Comput. Syst. Sci. 1988 37 3 312-323
[20]
Le, Q., Mikolov, T.: Distributed representations of sentences and documents. In: International Conference on Machine Learning, pp. 1188–1196. PMLR (2014)
[21]
Yanardag, P., Vishwanathan, S.V.N.: Deep graph kernels. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365–1374 (2015)
[22]
Al-Rfou, R., Perozzi, B., Zelle, D.: Ddgk: Learning graph representations for deep divergence graph kernels. In: The World Wide Web Conference, pp. 37–48 (2019)
[23]
Ivanov, S., Burnaev, E.: Anonymous walk embeddings. In: International conference on machine learning, pp. 2186–2195. PMLR (2018)
[24]
Rousseau, F., Kiagias, E., Vazirgiannis, M.: Text categorization as a graph classification problem. In: Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 1702–1712 (2015)
[25]
Wang H et al. Incremental subgraph feature selection for graph classification IEEE Trans. Knowl. Data Eng. 2016 29 1 128-142
[26]
Yan, X., Han, J.: gSpan: graph-based substructure pattern mining. In: 2002 IEEE International Conference on Data Mining, 2002 Proceedings, pp. 721–724. IEEE (2002)
[27]
Huan, J., Wang, W., Prins, J.: Efficient mining of frequent subgraphs in the presence of isomorphism. In: Third IEEE International Conference on Data Mining, pp. 549–552. IEEE (2003)
Index Terms
- Graph Classification via Graph Structure Learning
Index terms have been assigned to the content through auto-classification.
Recommendations
Boosting for graph classification with universum
Recent years have witnessed extensive studies of graph classification due to the rapid increase in applications involving structural data and complex relationships. To support graph classification, all existing methods require that training graphs should ...
Discriminating Frequent Pattern Based Supervised Graph Embedding for Classification
Advances in Knowledge Discovery and Data MiningAbstractGraph 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
Nov 2022
765 pages
ISBN:978-3-031-21966-5
DOI:10.1007/978-3-031-21967-2
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2022.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 28 November 2022
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Dec 2024