Machine Learning Approaches and Faithfulness Metrics for Evaluating Graph Drawing

Abstract

Evaluating graph drawing algorithms is important to ensure they are both effective and efficient in showing the structure of graphs. Human quantitative evaluation of graph drawings is well studied, using controlled experiments with human preference or task performance. Understanding which drawings humans prefer is challenging due to complex visual perception and cognition systems in human brain. This thesis presents the first machine learning approach for predicting human preference for human quantitative evaluation of graph drawings. Specifically, we propose M+HP (a CNN-Siamese-based neural network) to predict human preference from a pair of drawings of the same graph. Experimental results using ground truth data sets show our model can successfully predict human preference.

Finding a shortest path is one of the fundamental tasks for human quantitative evaluation of graph drawings. This thesis presents the first machine learning approach for predicting human shortest path task performance. Specifically, we propose MSP (a CNN-based neural network) to predict accuracy, response time, and mental effort from drawings with highlighted shortest paths. Experimental results using the ground truth data sets show our model can successfully predict shortest path task performance.

Many readability metrics (or aesthetic criteria) are proposed for quantitatively evaluating graph drawings. However, these metrics are less effective in evaluating big complex graph drawings. Recently, faithfulness metrics are proposed to effectively evaluate big complex graph drawings. This thesis presents DNC (Dynamic Neighbourhood Change), a general framework for neighbourhood change faithfulness metrics, which measure how faithfully the ground truth neighbourhood change in dynamic graphs is displayed in the geometric neighbourhood change in drawings. Experimental results show our metrics can effectively measure neighbourhood change faithfulness in dynamic graph drawings.