Abstract: Recently, approximate graph matching based on relaxing the permutation matrix to a doubly stochastic matrix has become an important and popular topic. The key point lies in which approximation over a continuous set is usually easier to implement than that over a discrete one. However, a consequent trouble related to such a relaxation is how to properly map the doubly stochastic matrix back to a permutation one. In the literature, a concave relaxation function for matching problem between the undirected graphs without self-loops was recently proposed, such that the doubly stochastic matrix can converge to a permutation one in a smooth way, and got a state-of-art performance on matching accuracy. Unfortunately, except for the undirected graphs without self-loops, there are no concave relaxation proposed for any other types of graph models. In this paper, we propose a concave relaxation for the directed graphs without self-loops, based on which a graph matching algorithm is then presented. Extensive experimental comparisons witness the validity of the proposed methods.