Geometric graphs from data to aid classification tasks with Graph Convolutional Networks

Yifan Qian; Paul Expert; Pietro Panzarasa; Mauricio Barahona

doi:10.1016/j.patter.2021.100237

Geometric graphs from data to aid classification tasks with Graph Convolutional Networks

Patterns (N Y). 2021 Apr 9;2(4):100237. doi: 10.1016/j.patter.2021.100237.

Authors

Yifan Qian¹, Paul Expert^{2

3}, Pietro Panzarasa¹, Mauricio Barahona⁴

Affiliations

¹ School of Business and Management, Queen Mary University of London, London, UK.
² Global Digital Health Unit, School of Public Health, Imperial College London, London, UK.
³ World Research Hub Initiative, Tokyo Institute of Technology, Tokyo, Japan.
⁴ Department of Mathematics, Imperial College London, London, UK.

Abstract

Traditional classification tasks learn to assign samples to given classes based solely on sample features. This paradigm is evolving to include other sources of information, such as known relations between samples. Here, we show that, even if additional relational information is not available in the dataset, one can improve classification by constructing geometric graphs from the features themselves, and using them within a Graph Convolutional Network. The improvement in classification accuracy is maximized by graphs that capture sample similarity with relatively low edge density. We show that such feature-derived graphs increase the alignment of the data to the ground truth while improving class separation. We also demonstrate that the graphs can be made more efficient using spectral sparsification, which reduces the number of edges while still improving classification performance. We illustrate our findings using synthetic and real-world datasets from various scientific domains.

Keywords: Graph Convolutional Networks; Graph Neural Networks; classification tasks; data science; geometric deep learning; graph construction; graph sparsification; graph theory; machine learning; network science.