Если бы это была метка головы или хвостовая метка, вы можете попробовать установить значение labeldistance в ноль, чтобы метка была нарисована на краю, но, как я понимаю, вы имеете в виду метку края (та, что в середине края ). В документации совершенно четко говорится, что labeldistance влияет только на метки меток фар и хвостовых меток, но вы можете попытать счастья.
Еще одна вещь, которую вы можете попробовать, - создать прозрачный промежуточный узел с меткой на нем. Это может выглядеть так, как вы хотите ... Но если вы сильно полагаетесь на алгоритм размещения узлов, может быть неприемлемо создавать эти «искусственные» узлы. В этом случае я призываю вас присоединиться к разработчикам Graphviz и добавить нужную вам функцию;) Серьезно, это очень приятно.
Если вы найдете другое решение, пожалуйста, опубликуйте его. Я столкнусь с подобной проблемой в ближайшем будущем.