Graph partition optimization with weights on edges and vertices
(not quite an answer, but too long for a comment)

Given your new cost function, I'm wondering if there's a simpler formulatio. Let $W = \sum_{(i,j) \in E} w_{ij}$. Now your goal is to maximize

\[ W - \sum_{|\{i,j\} \cap S| = 1} w_{ij} + \sum_{|\{i,j\} \cap S| = 1} w_{ij}u_j\]

Collecting terms, your goal is then to minimize

\[ \sum_{|\{i,j\} \cap S| = 1} w_{ij} (u_j - 1)\]

Setting $w&#39;_{ij} = w_{ij}(u_j - 1)$, your problem now becomes a min cut problem with the twist that it's not a typical min cut (you're not counting edges going from one side to the other, but both sides)