I am trying to formulate the following program into a minimum cut formulation:
$$\text{minimize}_{y\in \left\{0,1\right\}^V} \sum_{i\in V}\sum_{j\in V} d_{i,j}y_i(1-y_j) + \sum_{i\in V}f_iy_i.$$
Where $d_{i,j} \ge 0$ and $f_i$ can be negative. I suspect that it is possible to formulate this porblem as minimum cut problem on a graph with nonnegative capacities. However, until now the only graph I can think about it is : $$G = \left(V\cup \{s\}, E, c\right),\quad c_{i,j} = \begin{cases}d_{i,j}& \text{if $i, j \in V$}\\ f_i & \text{if $j=s$}\\ 0 & \text{otherwise}\end{cases}.$$ The problem with this graph is that the capacities are not all nonnegative.
So I am asking here it anyone can help me to find a formulation of this problem such that it can be solved with polynomial time algorithm.
You are almost there. The additional observation / trick you need is that if we let $S = \sum_{f_i < 0}f_i$ be the sum of the negative $f_i$-s, then for any $I \subseteq V$ we have $$ \sum_{i \in I}f_i = \sum_{i \in I, f_i > 0} f_i + \sum_{i \in I, f_i < 0} f_i = \sum_{i \in I, f_i > 0} f_i + S + \sum_{i \not \in I, f_i < 0} |f_i|. $$
Note that $S$ is a constant and does not depend on $I$. Another way to phrase this is that by setting $g_i = \max(0,f_i)$ and $h_i = \max(0,-f_i)$, your problem can be equivalently stated as
$$\text{minimize}_{y\in \left\{0,1\right\}^V} \sum_{i\in V}\sum_{j\in V} d_{i,j}y_i(1-y_j) + \sum_{i\in V}g_iy_i + \sum_{i \in V}h_i(1-y_i),$$
and here we do have $g_i, h_i \geq 0$. Now, can you see how to formulate this as a minimum cut problem?