A central challenge in structural pattern recognition is quantifying the similarity or dissimilarity of graphs. Classical approaches, such as Graph Edit Distance (GED), frame this challenge as a combinatorial optimization problem. GED, and similar methods, quantify the distance as the minimum cost of transforming one graph into another through a sequence of edit operations. In more recent work, data-driven alternatives to the idea of GED have been proposed, in particular Graph Neural Networks (GNNs). These methods aim to learn similarity metrics directly from graph data. In the present paper, we propose a novel framework for learning GED by computing convex combinations over a fixed pool of discrete permutation matrices. The key benefit of the proposed method is to bridge the gap between rigid combinatorial solvers and overly relaxed methods. The findings of the experimental evaluation are twofold. First, it shows that our novel approach performs competitively in terms of both MSE and runtime, and second, it gives new momentum to the interpretability of GNN-based GED.