DeepGraphNet: Deep Learning Models in the Classification of Graphs

Abstract

The graph classification model is an image processing approach that has come into prominence as a new research area. Particularly preferred graphs to provide visualization and easy readability of data, third party office software which develops rapidly due to increasing the flexibility and visuality of programming languages, can create graphics of different visual types. The aim of this study is to propose a deep learning model that classifies the type of graph is given as an input. It is fed into deep learning models as the features, instead of applying low and high-level feature extraction algorithms to the analyzed images. The effectiveness of the models in graphical classification was compared using feature learning, transfer of shared classification weights and advanced image processing capabilities of deep learning algorithms. In this study, the performance of convolutional neural networks and deep belief networks models such as overall performance, sensitivity, specificity, positive predictive value, and negative predictive value were calculated. The dataset in the analyzes consists of a total number of 1200 images including an equal number of line graphs, column graphs, pie graphs and distribution graphs. Each graph was resized to 224x224 pixels and was converted to gray level image. In the classification process of the analysis, 5-fold cross validation algorithm was used to evaluate each image independently into test and training processes. The experimental results showed that the proposed convolutional neural networks model classifies four different graphs with an overall accuracy rate of 92.92% with low-, medium- and high-level feature extraction capacity, while deep belief networks reached to an overall accuracy rate of 90.04%. Although the generated new presentations of the input images depending on the statistical and energy status of the visible and hidden units have achieved lower classification performance than the representations of input data from definitive filters using convolution, high graph classification performances have been achieved using the proposed models for models with various hidden layers. Convolutional neural networks model, in which the predominant properties of the layers formed by tensors using the dominant pixels are transferred to the next layer by pooling, provides flexibility and effective use for image processing approaches.

Keywords

• Deep Learning
• graph classification
• Deep belief networks
• Convolutional Neural Networks

DeepGraphNet: Grafiklerin Sınıflandırılmasında Derin Öğrenme Modelleri

Öz

Grafik sınıflandırma modeli henüz yeni bir araştırma alanı olarak ön plana çıkan bir görüntü işleme yaklaşımıdır. Özellikle verilerin görselleştirilmesi ve kolay okunabilirliğini sağlamak için tercih edilen grafikler, programlama dillerinin esnekliğini ve görselliğini her geçen gün artırmasına bağlı olarak hızla gelişen üçüncü parti ofis yazılımları, farklı görsel türlerde grafikler oluşturabilmektedir. Bu çalışmanın amacı, farklı giriş olarak verilen grafiğin hangi tür bir grafik olduğunu belirlemeyen bir derin öğrenme modeli oluşturmaktır. Analiz edilen görüntülerine düşük ve yüksek seviye öznitelik çıkarma algoritmları uygulamak yerine, doğruda derin öğrenme modellerine giriş olarak verilmiştir. Derin öğrenme algoritmalarının öznitelik öğrenme, paylaşılmış sınıflandırma ağırlıklarının transferi ve kendi içerisindeki ileri seviyeli görüntü işleme kabiliyetlerini kullanılarak modellerin grafik sınıflandırmada ki etkinlikleri kıyaslanmıştır. Çalışmada konvolüsyonel sinir ağları ve derin inanç ağları modellerinin genel başarım, hassasiyet, özgünlük, pozitif öngörü değeri ve negatif öngörü değeri gibi sınıflandırıcı performansları hesaplanmıştır. Analizlerde kullanılan veriler, çizgi grafiği, sütun grafiği, pasta grafiği ve dağılım grafiğini eşit sayıda içerecek şekilde toplam 1200 resimden meydana gelmektedir. Herbir resim dosyası 224x224 boyutta yeniden boyutlandırılarak, gri seviye resme dönüştürülmüştür. Analizlerin sınıflama süreçlerinde 5-katlı çapraz doğrulama yöntemi kullanılarak herbir verinin birrbirinden bağımsız olarak test ve eğitim süreçlerine dâhil edilmesi sağlanmıştır. Deneysel çalışmalardan elde edilen sonuçlar göstermiştir ki önerilen konvolüsyonel sinir ağları düşük, orta ve yüksek seviyeli öznitelik çıkarma kapasitesiyle %92,92 genel başarımla dört farklı grafiği sınıflandırırken, derin inanç ağları %90,04 genel başarıma kadar ulaşabilmiştir. Görüntülerdeki verilerin istatistiksel ve enerji durumuna bağlı olarak yeniden oluşturulan yansımalar her ne kadar bu verilerin belirli filtrelerden konvolüsyon işlemi sonrası elde edilen yansımalarından daha düşük sınıflandırma başarımı elde etmiş olsa da denenen farklı katman sayısına sahip modeller için yüksek başarımlar elde edilmiştir. Tensörler haline getirilen katmanların en baskın özelliklerinin belirlenerek belirleyici piksel değerlerinin havuzlama ile bir sonraki katmana aktarıldığı konvolüsyonel sinir ağları modelleri, görüntü işleme yaklaşımları için esneklik ve etkin bir kullanım sağlamaktadır.

Anahtar Kelimeler

• Derin Öğrenme
• grafik sınıflandırma
• Derin inanç ağları
• Konvolüsyonel sinir ağı

Kaynakça

1. Abdel-Zaher, A. M., & Eldeib, A. M. (2016). Breast cancer classification using deep belief networks. Expert Systems with Applications. https://doi.org/10.1016/j.eswa.2015.10.015
2. Altan, G., Kutlu, Y., & Allahverdi, N. (2016a). A Multistage Deep Belief Networks Application on Arrhythmia Classification. International Journal of Intelligent Systems and Applications in Engineering, 4(Special Issue-1), 222–228. https://doi.org/10.18201/IJISAE.270367
3. Altan, G., Kutlu, Y., & Allahverdi, N. (2016b). Deep Belief Networks Based Brain Activity Classification Using EEG from Slow Cortical Potentials in Stroke. International Journal of Applied Mathematics, Electronics and Computers. https://doi.org/10.18100/ijamec.270307
4. Amara, J., Kaur, P., Owonibi, M., & Bouaziz, B. (2017). Convolutional Neural Network Based Chart Image Classification. In 25th International Conference in Central Europe on Computer Graphics, Visualization and Computer Visionin co-operation with EUROGRAPHICS Association (pp. 83–88).
5. Butler, G., Grogono, P., Shinghal, R., & Tjandra, I. (1995). Analyzing the logical structure of data flow diagrams in software documents. In Proceedings of the International Conference on Document Analysis and Recognition, ICDAR. https://doi.org/10.1109/ICDAR.1995.601962
6. Cireşan, Dan C., Meier, U., Masci, J., Gambardella, L. M., & Schmidhuber, J. (2011). Flexible, high performance convolutional neural networks for image classification. In IJCAI International Joint Conference on Artificial Intelligence. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-210
7. Cireşan, Dan C., Meier, U., Gambardella, L. M., & Schmidhuber, J. (2011). Convolutional neural network committees for handwritten character classification. In Proceedings of the International Conference on Document Analysis and Recognition, ICDAR. https://doi.org/10.1109/ICDAR.2011.229
8. Dai, W., Wang, M., Niu, Z., & Zhang, J. (2018). Chart decoder: Generating textual and numeric information from chart images automatically. Journal of Visual Languages and Computing. https://doi.org/10.1016/j.jvlc.2018.08.005

9. Duda, R. O., Hart, P. E., & Stork, D. G. (2000). Pattern Classification. New York: John Wiley, Section. https://doi.org/10.1038/npp.2011.9
10. Hinton, G. (2009). Deep belief networks. Scholarpedia, 4(5), 5947. https://doi.org/10.4249/scholarpedia.5947
11. Hinton, G. E., Osindero, S., & Teh, Y.-W. (2006). A fast learning algorithm for deep belief nets. Neural Computation, 18(7), 1527–1554. https://doi.org/10.1162/neco.2006.18.7.1527
12. Huang, G. B., Lee, H., & Learned-Miller, E. (2012). Learning hierarchical representations for face verification with convolutional deep belief networks. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. https://doi.org/10.1109/CVPR.2012.6247968
13. Huang, W., Zong, S., & Tan, C. L. (2007). Chart image classification using multiple-instance learning. In Proceedings - IEEE Workshop on Applications of Computer Vision, WACV 2007. https://doi.org/10.1109/WACV.2007.17
14. Jung, D., Kim, W., Song, H., Hwang, J., Lee, B., Kim, B., & Seo, J. (2017). ChartSense: Interactive Data Extraction from Chart Images. Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems - CHI ’17. https://doi.org/10.1145/3025453.3025957
15. Kaggle. (2019). CNN tutorial. Retrieved from https://www.kaggle.com/nhlr21/deep-keras-cnn-tutorial
16. Kalchbrenner, N., Grefenstette, E., & Blunsom, P. (2014). A Convolutional Neural Network for Modelling Sentences. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). https://doi.org/10.3115/v1/P14-1062
17. Karpathy, A., Toderici, G., Shetty, S., Leung, T., Sukthankar, R., & Li, F. F. (2014). Large-scale video classification with convolutional neural networks. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. https://doi.org/10.1109/CVPR.2014.223
18. Karthikeyani, V., & Nagarajan, S. (2012). Machine Learning Classification Algorithms to Recognize Chart Types in Portable Document Format (PDF) Files. International Journal of Computer Applications. https://doi.org/10.5120/4789-6997
19. Kim, Y. (2014). Convolutional Neural Networks for Sentence Classification. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP). https://doi.org/10.3115/v1/D14-1181
20. Krizhevsky, A., Sutskever, I., & Hinton, G. E. (2012). ImageNet Classification with Deep Convolutional Neural Networks. Advances In Neural Information Processing Systems. https://doi.org/http://dx.doi.org/10.1016/j.protcy.2014.09.007
21. Mohamed, A. R., Dahl, G. E., & Hinton, G. (2012). Acoustic modeling using deep belief networks. IEEE Transactions on Audio, Speech and Language Processing. https://doi.org/10.1109/TASL.2011.2109382
22. Poco, J., & Heer, J. (2017). Reverse-Engineering Visualizations: Recovering Visual Encodings from Chart Images. Computer Graphics Forum. https://doi.org/10.1111/cgf.13193
23. Savva, M., Kong, N., Chhajta, A., Li, F.-F., Agrawala, M., & Heer, J. (2011). ReVision: Automated classification, analysis and redesign of chart images. In UIST’11 - Proceedings of the 24th Annual ACM Symposium on User Interface Software and Technology. https://doi.org/10.1145/2047196.2047247
24. Shadish, W. R., Brasil, I. C. C., Illingworth, D. A., White, K. D., Galindo, R., Nagler, E. D., & Rindskopf, D. M. (2009). Using UnGraph to extract data from image files: Verification of reliability and validity. Behavior Research Methods. https://doi.org/10.3758/BRM.41.1.177
25. Siddiqui, S. A., Salman, A., Malik, M. I., Shafait, F., Mian, A., Shortis, M. R., & Harvey, E. S. (2018). Automatic fish species classification in underwater videos: Exploiting pre-trained deep neural network models to compensate for limited labelled data. ICES Journal of Marine Science. https://doi.org/10.1093/icesjms/fsx109
26. Tang, B., Liu, X., Lei, J., Song, M., Tao, D., Sun, S., & Dong, F. (2016). DeepChart: Combining deep convolutional networks and deep belief networks in chart classification. Signal Processing. https://doi.org/10.1016/j.sigpro.2015.09.027
27. Yan Ping Zhou, & Chew Lim Tan. (2002). Hough technique for bar charts detection and recognition in document images. https://doi.org/10.1109/icip.2000.899506
28. Yang, L., Huang, W., & Tan, C. L. (2006). Semi-automatic Ground Truth Generation for Chart Image Recognition. https://doi.org/10.1007/11669487_29
29. Yu, J., Tao, D., & Wang, M. (2012). Adaptive hypergraph learning and its application in image classification. IEEE Transactions on Image Processing. https://doi.org/10.1109/TIP.2012.2190083
30. Zhou, Y., & Tan, C. L. (2001). Chart analysis and recognition in document images. In 12th Proceedings of the International Conference on Document Analysis and Recognition, ICDAR (p. 1055). https://doi.org/10.1109/ICDAR.2001.953947