Deep Topology Classification: A New Approach for Massive Graph Classification

Bonner, S.; Brennan, J.; Theodoropoulos, G.; McGough, S.; Kureshi, I.; Joshi, James; Karypis, George; Liu, Ling; Hu, Xiaohua; Ak, Ronay; Xia, Yinglong; Xu, Weijia; Sato, Aki-Hiro; Rachuri, Sudarsan; Ungar, Lyle; Yu, Philip S.; Govindaraju, Rama; Suzumura, Toyotaro

Abstract

The classification of graphs is a key challenge within many scientific fields using graphs to represent data and is an active area of research. Graph classification can be critical in identifying and labelling unknown graphs within a dataset and has seen application across many scientific fields. Graph classification poses two distinct problems: the classification of elements within a graph and the classification of the entire graph. Whilst there is considerable work on the first problem, the efficient and accurate classification of massive graphs into one or more classes has, thus far, received less attention. In this paper we propose the Deep Topology Classification (DTC) approach for global graph classification. DTC extracts both global and vertex level topological features from a graph to create a highly discriminate representation in feature space. A deep feed-forward neural network is designed and trained to classify these graph feature vectors. This approach is shown to be over 99% accurate at discerning graph classes over two datasets. Additionally, it is shown to be more accurate than current state of the art approaches both in binary and multi-class graph classification tasks.

Citation

Bonner, S., Brennan, J., Theodoropoulos, G., McGough, S., Kureshi, I., Joshi, J., Karypis, G., Liu, L., Hu, X., Ak, R., Xia, Y., Xu, W., Sato, A.-H., Rachuri, S., Ungar, L., Yu, P. S., Govindaraju, R., & Suzumura, T. (2016, February). Deep Topology Classification: A New Approach for Massive Graph Classification. Presented at IEEE International Conference on Big Data, Washington D.C

• Presentation Conference Type: Conference Paper (published)
• Conference Name: IEEE International Conference on Big Data
• Acceptance Date: Nov 6, 2016
• Online Publication Date: Feb 6, 2017
• Publication Date: Feb 6, 2017
• Deposit Date: Nov 7, 2016
• Publicly Available Date: Mar 21, 2017
• Publisher: Institute of Electrical and Electronics Engineers
• Pages: 3290-3297
• Book Title: IEEE International Conference on Big Data ; proceedings
• ISBN: 9781467390057
• DOI: https://doi.org/10.1109/bigdata.2016.7840988
• Public URL: https://durham-repository.worktribe.com/output/1150912