A novel multidimensional distance measure for graphs

We introduce a novel multidimensional distance measure between graphs that extends our previously defined Vectorial Tree Distance (VTD) to general undirected, unweighted graphs. We name the new measure ’Vectorial Graph Distance’ (VGD). The method converts each graph into a unique tree by combining a bounded quotient graph, constructed using node-betweenness centrality, with a modified breadth-first search (BFS) that ensures uniqueness. Once converted, the resulting trees are compared using the VTD, yielding a structured vector-valued distance that reflects hierarchical differences between graphs. We demonstrate the utility of the VGD to separate molecular graphs taken from the ENZYMES (BRENDA) and Proteins (Protein Data Bank) datasets. We further show that the VGD successfully partitions graphs with different hierarchical structure. The approach captures meaningful structural distinctions and provides an interpretable, multi-level measure of graph similarity.