Substitution matrices, which are crafted to quantify the functional impact of substitutions or deletions in biomolecules, are central component of remote homology detection, functional element discovery, and structure prediction algorithms. However, they are often limited to sequence data and the conditioning on external priors can only be given implicitly through the curation of the ground-truth alignments they are crafted on.Here we propose an algorithmic framework, based on regularized optimal transport, for learning graph-based substitution matrices from data, conditioned on any functional knowledge.In particular, our graph-neural-network-based model learns to produce substitution matrices and graph matchings suchthat the resulting metric correlates with the functional prior at hand.Our method shows promising performance in functional similarity classification and shows potential for interpreting the functional importance of molecular substructures.