We present a machine-checkable sufficient condition for relative termination of double-pushout graph rewriting systems with injective rules on edge-labeled multigraphs. Our method defines a graph’s weight as the sum of weights of occurrences of a set of graphs within it. By ensuring (1) every rewriting step using rules in a set A strictly decreases the host graph’s weight, and (2) every rewriting step using rules in a set B never increases it, we guarantee that rules in the set A can be applied only finitely many times in any rewriting sequence with rules in the union of A and B. Our method resolves termination cases that prior interpretation-based methods cannot. We also propose an implementation of our technique.