Learning Attributed Graphlets: Predictive Graph Mining by Graphlets with Trainable Attribute
Pages 2830 - 2841
Abstract
The graph classification problem has been widely studied; however, achieving an interpretable model with high predictive performance remains a challenging issue. This paper proposes an interpretable classification algorithm for attributed graph data, called LAGRA (Learning Attributed GRAphlets). LAGRA learns importance weights for small attributed subgraphs, called attributed graphlets (AGs), while simultaneously optimizing their attribute vectors. This enables us to obtain a combination of subgraph structures and their attribute vectors that strongly contribute to discriminating different classes. A significant characteristics of LAGRA is that all the subgraph structures in the training dataset can be considered as a candidate structures of AGs. This approach can explore all the potentially important subgraphs exhaustively, but obviously, a naïve implementation can require a large amount of computations. To mitigate this issue, we propose an efficient pruning strategy by combining the proximal gradient descent and a graph mining tree search. Our pruning strategy can ensure that the quality of the solution is maintained compared to the result without pruning. We empirically demonstrate that LAGRA has superior or comparable prediction performance to the standard existing algorithms including graph neural networks, while using only a small number of AGs in an interpretable manner.
Supplemental Material
MP4 File - KDD 2024 promotion video
Short promotion video for the following KDD 2024 research track paper: Title: Learning Attributed Graphlets: Predictive Graph Mining by Graphlets with Trainable Attribute Authors: Shinji Tajima, Ren Sugihara, Ryota Kitahara, Masayuki Karasuyama (Nagoya Institute of Technology) Speaker: Masayuki Karasuyama (https://www-als.ics.nitech.ac.jp/~karasuyama/index_E.html) The graph classification problem has been widely studied, but achieving an interpretable model with high predictive performance remains challenging. We propose LAGRA (Learning Attributed GRAphlets), an interpretable classification algorithm for attributed graph data. A key idea is to combine the proximal gradient based sparse optimization and graph mining, by which a small number of important attributed subgraphs can be identified.
- Download
- 103.50 MB
References
[1]
Amir Beck and Marc Teboulle. 2009. A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems. SIAM Journal on Imaging Sciences, Vol. 2, 1 (2009), 183--202.
[2]
Felix A. Faber, Luke Hutchison, Bing Huang, Justin Gilmer, Samuel S. Schoenholz, George E. Dahl, Oriol Vinyals, Steven Kearnes, Patrick F. Riley, and O. Anatole von Lilienfeld. 2017. Prediction Errors of Molecular Machine Learning Models Lower than Hybrid DFT Error. Journal of Chemical Theory and Computation, Vol. 13, 11 (2017), 5255--5264.
[3]
Aosong Feng, Chenyu You, Shiqiang Wang, and Leandros Tassiulas. 2022. KerGNNs: Interpretable Graph Neural Networks with Graph Kernels. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI. AAAI Press, 6614--6622.
[4]
Aasa Feragen, Niklas Kasenburg, Jens Petersen, Marleen de Bruijne, and Karsten Borgwardt. 2013. Scalable kernels for graphs with continuous attributes. In Advances in Neural Information Processing Systems. 216--224.
[5]
Jerome Friedman, Trevor Hastie, Holger Höfling, and Robert Tibshirani. 2007. Pathwise coordinate optimization. The Annals of Applied Statistics, Vol. 1, 2 (12 2007), 302--332.
[6]
Josif Grabocka, Nicolas Schilling, Martin Wistuba, and Lars Schmidt-Thieme. 2014. Learning Time-Series Shapelets. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, New York, NY, USA, 392^^e2^^80^^93401.
[7]
Katarzyna Janocha and Wojciech Marian Czarnecki. 2016. On Loss Functions for Deep Neural Networks in Classification. Schedae Informaticae, Vol. 25 (2016), 49.
[8]
Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24--26, 2017, Conference Track Proceedings. OpenReview.net.
[9]
Risi Kondor and Horace Pan. 2016. The multiscale Laplacian graph kernel. In Advances in Neural Information Processing Systems. 2990--2998.
[10]
Nils M. Kriege, Fredrik D. Johansson, and Christopher Morris. 2020. A survey on graph kernels. Applied Network Science, Vol. 5 (2020), 6.
[11]
Steph-Yves Louis, Yong Zhao, Alireza Nasiri, Xiran Wang, Yuqi Song, Fei Liu, and Jianjun Hu. 2020. Graph convolutional neural networks with global attention for improved materials property prediction. Phys. Chem. Chem. Phys., Vol. 22 (2020), 18141--18148. Issue 32.
[12]
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. 2020. TUDataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL 2020). www.graphlearning.io
[13]
Kazuya Nakagawa, Shinya Suzumura, Masayuki Karasuyama, Koji Tsuda, and Ichiro Takeuchi. 2016. Safe pattern pruning: An efficient approach for predictive pattern mining. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1785--1794.
[14]
Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting. 2016. Propagation kernels: efficient graph kernels from propagated information. Machine Learning, Vol. 102, 2 (2016), 209--245.
[15]
N. Prvzulj. 2007. Biological network comparison using graphlet degree distribution. Bioinformatics, Vol. 23, 2 (2007), e177--e183.
[16]
Liva Ralaivola, Sanjay J. Swamidass, Hiroto Saigo, and Pierre Baldi. 2005. Graph kernels for chemical informatics. Neural Networks, Vol. 18, 8 (2005), 1093--1110.
[17]
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. 2009. Efficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics. 488--495.
[18]
Giannis Siglidis, Giannis Nikolentzos, Stratis Limnios, Christos Giatsidis, Konstantinos Skianis, and Michalis Vazirgiannis. 2020. GraKeL: A Graph Kernel Library in Python. Journal of Machine Learning Research, Vol. 21, 54 (2020), 1--5.
[19]
Marc Teboulle. 2017. A simplified view of first order methods for optimization. Mathematical Programming, Vol. 170 (2017), 67--96.
[20]
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018. Graph Attention Networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net.
[21]
Tian Xie and Jeffrey C. Grossman. 2018. Crystal Graph Convolutional Neural Networks for an Accurate and Interpretable Prediction of Material Properties. Phys. Rev. Lett., Vol. 120 (2018), 145301. Issue 14.
[22]
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In International Conference on Learning Representations.
[23]
Yangyang Xu and Wotao Yin. 2017. A Globally Convergent Algorithm for Nonconvex Optimization Based on Block Coordinate Update. Journal of Scientific Computing, Vol. 72 (2017), 700--734.
[24]
Xifeng Yan and Jiawei Han. 2002. gSpan: Graph-based substructure pattern mining. In Proceedings. 2002 IEEE International Conference on Data Mining. IEEE, 721--724.
[25]
J. You, J. M. Gomes-Selman, R. Ying, and J Leskovec. 2021. Identity-aware Graph Neural Networks. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 10737--10745.
[26]
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. 2020. XGNN: Towards Model-Level Explanations of Graph Neural Networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, New York, NY, USA, 430--438.
[27]
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. 2022. Explainability in Graph Neural Networks: A Taxonomic Survey. IEEE Transactions on Pattern Analysis and Machine Intelligence (2022).
[28]
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. 2018. An end-to-end deep learning architecture for graph classification. In Proceedings of AAAI Conference on Artificial Inteligence.
[29]
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. 2020. Graph neural networks: A review of methods and applications. AI Open, Vol. 1 (2020), 57--81.
Index Terms
- Learning Attributed Graphlets: Predictive Graph Mining by Graphlets with Trainable Attribute
Index terms have been assigned to the content through auto-classification.
Recommendations
Attributed Graph Mining and Matching: An Attempt to Define and Extract Soft Attributed Patterns
CVPR '14: Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern RecognitionGraph matching and graph mining are two typical areas in artificial intelligence. In this paper, we define the soft attributed pattern (SAP) to describe the common subgraph pattern among a set of attributed relational graphs (ARGs), considering both the ...
Graph Classification via Graph Structure Learning
Intelligent Information and Database SystemsAbstractWith 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 ...
On augmenting topological graph representations for attributed graphs▪
AbstractGraph representations based on embedding methods allow for easier analysis of the network structure and can be used for a variety of tasks, such as link prediction and node classification. These methods have been shown to be effective ...
Highlights- This study proposes an attributed graph augmentation framework for attributed graphs
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2024
6901 pages
Copyright © 2024 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 the author(s) 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: 24 August 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- International Joint Usage/Research Project with ICR, Kyoto University
- MEXT KAKENHI
Conference
KDD '24: The 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
August 25 - 29, 2024
Barcelona, Spain
Acceptance Rates
Overall Acceptance Rate 1,133 of 8,635 submissions, 13%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 80Total Downloads
- Downloads (Last 12 months)80
- Downloads (Last 6 weeks)19
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in