research-article

Public Access

Graph Classification using Structural Attention

Authors:

Xiangnan KongAuthors Info & Claims

KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

Pages 1666 - 1674

https://doi.org/10.1145/3219819.3219980

Published: 19 July 2018 Publication History

Abstract

Graph classification is a problem with practical applications in many different domains. To solve this problem, one usually calculates certain graph statistics (i.e., graph features) that help discriminate between graphs of different classes. When calculating such features, most existing approaches process the entire graph. In a graphlet-based approach, for instance, the entire graph is processed to get the total count of different graphlets or subgraphs. In many real-world applications, however, graphs can be noisy with discriminative patterns confined to certain regions in the graph only. In this work, we study the problem of attention-based graph classification. The use of attention allows us to focus on small but informative parts of the graph, avoiding noise in the rest of the graph. We present a novel RNN model, called the Graph Attention Model (GAM), that processes only a portion of the graph by adaptively selecting a sequence of "informative" nodes. Experimental results on multiple real-world datasets show that the proposed method is competitive against various well-known methods in graph classification even though our method is limited to only a portion of the graph.

Supplementary Material

MP4 File (lee_graph_classification.mp4)

Download
324.71 MB

References

[1]

Nesreen K. Ahmed, Ryan A. Rossi, Rong Zhou, John Boaz Lee, Xiangnan Kong, Theodore L. Willke, and Hoda Eldardiry. 2018. Learning Role-based Graph Embeddings. In arXiv preprint arXiv:1802.02896.

[2]

Lars Backstrom and Jure Leskovec. 2011. Supervised random walks: predicting and recommending links in social networks. In Proceedings of the Fourth International Conference on Web Search and Web Data Mining. 635--644.

Digital Library

[3]

Jie Bao, Tianfu He, Sijie Ruan, Yanhua Li, and Yu Zheng. 2017. Planning Bike Lanes based on Sharing-Bikes' Trajectories Proceedings of the Twenty-Second ACM SigKDD International Conference on Knowledge Discovery and Data Mining.

Digital Library

[4]

Karsten M. Borgwardt and Hans-Peter Kriegel. 2005. Shortest-Path Kernels on Graphs. In Proceedings of the Fifth IEEE International Conference on Data Mining. 74--81.

Digital Library

[5]

Karsten M. Borgwardt, Cheng Soon Ong, Stefan Schonauer, S. V. N. Vishwanathan, Alex J. Smola, and Hans-Peter Kriegel. 2005. Protein function prediction via graph kernels. Bioinformatics Vol. 21, 1 (2005), i47--i56.

Digital Library

[6]

Duen Horng Chau, Carey Nachenberg, Jeffrey Wilhelm, Adam Wright, and Christos Faloutsos. 2011. Polonium: Tera-Scale Graph Mining for Malware Detection Proceedings of the Eleventh SIAM International Conference on Data Mining. 131--142.

[7]

Kan Chen, Jiang Wang, Liang-Chieh Chen, Haoyuan Gao, Wei Xu, and Ram Nevatia. 2015. ABC-CNN: An Attention Based Convolutional Neural Network for Visual Question Answering arXiv preprint arXiv:1511.05960v2.

[8]

Dong-Yeon Cho, Yoo-Ah Kim, and Teresa M. Przytycka. 2012. Chapter 5: Network Biology Approach to Complex Diseases. PLOS Computational Biology Vol. 8 (2012), e1002820.

[9]

Edward Choi, Mohammad Taha Bahadori, Le Song, Walter F. Stewart, and Jimeng Sun. 2017. GRAM: Graph-based Attention Model for Healthcare Representation Learning Proceedings of the Twenty-Third ACM SigKDD International Conference on Knowledge Discovery and Data Mining. 787--795.

Digital Library

[10]

Gabriel Dulac-Arnold, Richard Evans, Hado van Hasselt, Peter Sunehag, Timothy Lillicrap, Jonathan Hunt, Timothy Mann, Theophane Weber, Thomas Degris, and Ben Coppin. 2015. Deep reinforcement learning in large discrete action spaces arXiv preprint arXiv:1512.07679.

[11]

David K. Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik, and Ryan P. Adams. 2015. Convolutional networks on graphs for learning molecular fingerprints Proceedings of the Twenty-Eight Annual Conference on Neural Information Processing Systems. 2224--2232.

Digital Library

[12]

Felix Gers, Jurgen Schmidhuber, and Fred Cummins. 1999. Learning to forget: continual prediction with LS™ Proceedings of the Tenth International Conference on Artificial Neural Networks. 850--855.

[13]

Xin Hu, Tzi cker Chiueh, and Kang G. Shin. 2009. Large-scale malware indexing using function-call graphs Proceedings of the Sixteenth ACM Conference on Computer and Communications Security. 611--620.

Digital Library

[14]

Diederik P. Kingma and Jimmy Lei Ba. 2015. Adam: A method for stochastic optimization. In Proceedings of the Third International Conference on Learning Representations.

[15]

Risi Kondor and Horace Pan. 2016. The Multiscale Laplacian Graph Kernel. In Proceedings of the Twenty-Ninth Annual Conference on Neural Information Processing Systems. 2982--2990.

Digital Library

[16]

Xiangnan Kong, Wei Fang, and Philip S. Yu. 2011. Dual active feature and sample selection for graph classification Proceedings of the Seventeenth ACM SigKDD International Conference on Knowledge Discovery and Data Mining. 654--662.

Digital Library

[17]

Thang Luong, Hieu Pham, and Christopher D. Manning. 2015. Effective Approaches to Attention-based Neural Machine Translation Proceedings of the Thirteenth Conference on Empirical Methods in Natural Language Processing. 1412--1421.

[18]

Volodymyr Mnih, Nicolas Heess, Alex Graves, and Koray Kavukcuoglu. 2014. Recurrent models of visual attention. In Proceedings of the Twenty-Seventh Annual Conference on Neural Information Processing Systems. 2204--2212.

Digital Library

[19]

Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. 2016. Learning Convolutional Neural Networks for Graphs. In Proceedings of the Thirty-Third International Conference on Machine Learning. 2014--2023.

Digital Library

[20]

Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. 2017. Matching Node Embeddings for Graph Similarity. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence. 2429--2435.

[21]

Shirui Pan, Jia Wu, Xingquan Zhu, and Chengqi Zhang. 2015. Graph Ensemble Boosting for Imbalanced Noisy Graph Stream Classification. IEEE Transactions on Cybernetics Vol. 45, 5 (2015), 940--954.

[22]

Aaditya Prakash, Siyuan Zhao, Sadid A. Hasan, Vivek Datla, Kathy Lee, Ashequl Qadir, Joey Liu, and Oladimeji Farri. 2017. Condensed Memory Networks for Clinical Diagnostic Inferencing Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence. 3274--3280.

[23]

David Rogers and Mathew Hahn. 2010. Extended-connectivity fingerprints. Journal of Chemical Information and Modeling Vol. 50, 5 (2010), 742--754.

[24]

Ryan A. Rossi, Rong Zhou, and Nesreen K. Ahmed. 2017. Estimation of graphlet statistics. In arXiv preprint arXiv:1701.01772.

[25]

Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. 2011. Weisfeiler-Lehman Graph Kernels. Journal of Machine Learning Research Vol. 12 (2011), 2539--2561.

Digital Library

[26]

Nino Shervashidze, S. V. N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M. Borgwardt. 2009. Efficient graphlet kernels for large graph comparison Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics. 488--495.

[27]

Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston, and Rob Fergus. 2015. End-To-End memory networks. In Proceedings of the Twenty-Eight Annual Conference on Neural Information Processing Systems. 2440--2448.

Digital Library

[28]

Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph Attention Networks. In arXiv preprint arXiv:1710.10903v2.

[29]

David Weininger. 1988. SMILES, a chemical language and information system. Journal of Chemical Information and Modeling Vol. 28 (1988), 31--36.

Digital Library

[30]

Jason Weston, Sumit Chopra, and Antoine Bordes. 2014. Memory Networks. In Proceedings of the Second International Conference on Learning Representations.

[31]

Daan Wierstra, Alexander Forster, Jan Peters, and Jurgen Schmidhuber. 2007. Solving deep memory POMDPs with recurrent policy gradients Proceedings of the Seventeenth International Conference on Artificial Neural Networks. 697--706.

Digital Library

[32]

Ronald J. Williams. 1992. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning Vol. 8, 3 (1992), 229--256.

Digital Library

[33]

Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron C. Courville, Ruslan Salakhutdinov, Richard S. Zemel, and Yoshua Bengio. 2015. Show, Attend and Tell: Neural Image Caption Generation with Visual Attention Proceedings of the Thirty-Second International Conference on Machine Learning. 2048--2057.

Digital Library

[34]

Pinar Yanardag and S. V. N. Vishwanathan. 2015. Deep Graph Kernels. In Proceedings of the Twenty-First ACM SigKDD International Conference on Knowledge Discovery and Data Mining. 1365--1374.

Digital Library

[35]

Jingyuan Zhang, Bokai Cao, Sihong Xie, Chun-Ta Lu, Philip S. Yu, and Ann B. Ragin. 2016. Identifying Connectivity Patterns for Brain Diseases via Multi-side-view Guided Deep Architectures. In Proceedings of the Sixteenth SIAM International Conference on Data Mining. 36--44.

Cited By

Bongini PPancino NBendjeddou AScarselli FMaggini MBianchini M(2024)Composite Graph Neural Networks for Molecular Property PredictionInternational Journal of Molecular Sciences10.3390/ijms2512658325:12(6583)Online publication date: 14-Jun-2024
https://doi.org/10.3390/ijms25126583
Korfmann KSellinger TFreund FFumagalli MTellier A(2024)Simultaneous Inference of Past Demography and Selection from the Ancestral Recombination Graph under the Beta CoalescentPeer Community Journal10.24072/pcjournal.3974Online publication date: 18-Mar-2024
https://doi.org/10.24072/pcjournal.397
Shim SKim JPark KKang U(2024)Accurate graph classification via two-staged contrastive curriculum learningPLOS ONE10.1371/journal.pone.029617119:1(e0296171)Online publication date: 3-Jan-2024
https://doi.org/10.1371/journal.pone.0296171
Show More Cited By

Index Terms

Graph Classification using Structural Attention

Recommendations

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 ...
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 ...
Hierarchical Graph Representation Learning with Structural Attention for Graph Classification
Artificial Intelligence
Abstract
Recently, graph neural networks (GNNs) exhibit strong expressive power in modeling graph structured data and have been shown to work effectively for graph classification tasks. However, existing GNN models for predicting graph categories ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

KDD '18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining

July 2018

2925 pages

ISBN:9781450355520

DOI:10.1145/3219819

General Chairs:
Yike Guo
Imperial College London
,
Faisal Farooq
IBM

Copyright © 2018 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: 19 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

KDD '18

Sponsor:

KDD '18: The 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 19 - 23, 2018

London, United Kingdom

Acceptance Rates

KDD '18 Paper Acceptance Rate 107 of 983 submissions, 11%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

161
Total Citations
View Citations
8,963
Total Downloads

Downloads (Last 12 months)1,048
Downloads (Last 6 weeks)135

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bongini PPancino NBendjeddou AScarselli FMaggini MBianchini M(2024)Composite Graph Neural Networks for Molecular Property PredictionInternational Journal of Molecular Sciences10.3390/ijms2512658325:12(6583)Online publication date: 14-Jun-2024
https://doi.org/10.3390/ijms25126583
Korfmann KSellinger TFreund FFumagalli MTellier A(2024)Simultaneous Inference of Past Demography and Selection from the Ancestral Recombination Graph under the Beta CoalescentPeer Community Journal10.24072/pcjournal.3974Online publication date: 18-Mar-2024
https://doi.org/10.24072/pcjournal.397
Shim SKim JPark KKang U(2024)Accurate graph classification via two-staged contrastive curriculum learningPLOS ONE10.1371/journal.pone.029617119:1(e0296171)Online publication date: 3-Jan-2024
https://doi.org/10.1371/journal.pone.0296171
陈丹(2024)Algorithm Research of Attention Mechanism in Graph Neural Network ModelModeling and Simulation10.12677/MOS.2024.13102213:01(225-238)Online publication date: 2024
https://doi.org/10.12677/MOS.2024.131022
Patel MJariwala KChattopadhyay C(2024)A Systematic Review on Graph Neural Network-based Methods for Stock Market ForecastingACM Computing Surveys10.1145/369641157:2(1-38)Online publication date: 10-Oct-2024
https://dl.acm.org/doi/10.1145/3696411
Yang ZZhang GWu JYang JSheng QXue SZhou CAggarwal CPeng HHu WHancock ELiò P(2024)State of the Art and Potentialities of Graph-level LearningACM Computing Surveys10.1145/369586357:2(1-40)Online publication date: 10-Oct-2024
https://dl.acm.org/doi/10.1145/3695863
Fang YZhao XXiao Wde Rijke M(2024)Few-shot Learning for Heterogeneous Information NetworksACM Transactions on Information Systems10.1145/364931142:4(1-24)Online publication date: 27-Feb-2024
https://dl.acm.org/doi/10.1145/3649311
Zhao TKang JCheng LBaeza-Yates RBonchi F(2024)Conformalized Link Prediction on Graph Neural NetworksProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3672061(4490-4499)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3672061
Gao YLu JLi SLi YDu S(2024)Hypergraph-Based Multi-View Action Recognition Using Event CamerasIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2024.338211746:10(6610-6622)Online publication date: Oct-2024
https://doi.org/10.1109/TPAMI.2024.3382117
Fan SWang XShi CCui PWang B(2024)Generalizing Graph Neural Networks on Out-of-Distribution GraphsIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2023.332109746:1(322-337)Online publication date: Jan-2024
https://doi.org/10.1109/TPAMI.2023.3321097
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents