While I understand how arrows on the end of the edge is a bad idea, especially if you have a lot of edges on one node; what about having arrows blended in the edge itself?
Something like this (beware the ASCII art):
o---->----o
I often do this in hand-drawn graphs for my own consumption, when the line is very long (sometimes using three arrowheads): o-->---------->----------->o
BTW: paper mentions the problem of visual clutter of the arrowhead itself.
Something like this (beware the ASCII art): o---->----o