A key challenge in structural pattern recognition is quantifying the dissimilarity or similarity between graphs. Traditional methods that solve this challenge, such as the graph edit distance, assign costs to structural differences of the graphs to measure their dissimilarity. More recent approaches leverage graph kernels or graph neural networks for the same task. In the present paper, we propose a novel framework for graph dissimilarity computation that consists of three major steps. Using GNNs, we first embed graphs into real vector spaces. Then, in a second step, we construct convex hulls from these embeddings. In the third step, we extract geometric features from these hulls, from which we finally derive dissimilarity values between the graphs. The experimental evaluation on a few data sets demonstrates that our novel approach achieves comparable classification performance to that of reference systems. At the same time, we observe substantial reductions of the computation time.