Deep Learning of Graphs with Ngram Convolutional Neural Networks.

Convolutional Neural Network (CNN) has gained attractions in image analytics and speech recognition in recent years. However, employing CNN for classification of graphs remains to be challenging. This paper presents the Ngram graph-block based convolutional neural network model for classification of graphs. Our Ngram deep learning framework consists of three novel components. First, we introduce the concept of $n$ <alternatives><inline-graphic xlink:href="luo-ieq1-2720734.gif"/></alternatives>-gram block to transform each raw graph object into a sequence of $n$ <alternatives><inline-graphic xlink:href="luo-ieq2-2720734.gif"/></alternatives>-gram blocks connected through overlapping regions. Second, we introduce a diagonal convolution step to extract local patterns and connectivity features hidden in these $n$<alternatives> <inline-graphic xlink:href="luo-ieq3-2720734.gif"/></alternatives>-gram blocks by performing $n$<alternatives> <inline-graphic xlink:href="luo-ieq4-2720734.gif"/></alternatives>-gram normalization. Finally, we develop deeper global patterns based on the local patterns and the ways that they respond to overlapping regions by building a $n$<alternatives> <inline-graphic xlink:href="luo-ieq5-2720734.gif"/></alternatives>-gram deep learning model using convolutional neural network. We evaluate the effectiveness of our approach by comparing it with the existing state of art methods using five real graph repositories from bioinformatics and social networks domains. Our results show that the Ngram approach outperforms existing methods with high accuracy and comparable performance. [ABSTRACT FROM PUBLISHER]