  The analysis of signals defined over a graph is relevant in many
applications, such as social and economic networks, big data or biological
networks, and so on. A key tool for analyzing these signals is the so called
Graph Fourier Transform (GFT). Alternative definitions of GFT have been
suggested in the literature, based on the eigen-decomposition of either the
graph Laplacian or adjacency matrix. In this paper, we address the general case
of directed graphs and we propose an alternative approach that builds the graph
Fourier basis as the set of orthonormal vectors that minimize a continuous
extension of the graph cut size, known as the Lov\'{a}sz extension. To cope
with the non-convexity of the problem, we propose two alternative iterative
optimization methods, properly devised for handling orthogonality constraints.
Finally, we extend the method to minimize a continuous relaxation of the
balanced cut size. The formulated problem is again non-convex and we propose an
efficient solution method based on an explicit-implicit gradient algorithm.
