Comparing structured objects such as graphs is a fundamental operationinvolved in many learning tasks. To this end, the Gromov-Wasserstein (GW)distance, based on Optimal Transport (OT), has proven to be successful inhandling the specific nature of the associated objects. More specifically,through the nodes connectivity relations, GW operates on graphs, seen asprobability measures over specific spaces. At the core of OT is the idea ofconservation of mass, which imposes a coupling between all the nodes fromthe two considered graphs. We argue in this paper that this property can bedetrimental for tasks such as graph dictionary or partition learning, and werelax it by proposing a new semi-relaxed Gromov-Wasserstein divergence.Aside from immediate computational benefits, we discuss its properties, andshow that it can lead to an efficient graph dictionary learning algorithm.We empirically demonstrate its relevance for complex tasks on graphs such aspartitioning, clustering and completion.