Lovasz extension of undirected graph cuts

Question

It is known that the Lovasz extension for the cut function on the simple undirected graph $G=(V,E)$ is given by the graph total variation,

$$ f(x) = \frac{ \sum_{i,j \in E} |x_i-x_j| }{2},$$ for a real valued vector $x \in \mathbb{R}_{+}^{|V|}$.

My understanding is that this comes from the Choquet integral for the cut function, i.e., $ \int_{\mathbb{R}}\text{cut}(\{x\geq t \})dt, $ where $ \{x \geq t\} $ gives us the level set for the various choices of t.

Let $t_{1}>t_{2},>\dots> t_{k} \geq 0 $ be the sorted entries of x. It is also known that for a set function $ F: 2^S \rightarrow \mathbb{R}_{+} \cup \{ +\infty \} $ on arbitrary nonempty set $S$, and $t_{k+1}=0$, the Choquet integral yields: $$ \int_{\mathbb{R}} F\{x\geq t \} dt = \sum_{i=1}^{k}(t_{i}-t_{i+1})F(\{x \geq t_i \}), $$ which is the definition of the Lovasz extension. Now I can sort of see that the sum could possibly be rearranged in such a way that you could pair up all the terms corresponding to edges as differences to get the graph TV. However, it's not obvious to me exactly how, and if this derivation can come naturally from some kind of property of the cut function (or submodularity), or if it's just a matter of laboriously arranging the terms until we get what we want.

Am I missing something simple here? Are there any straightforward derivations for the graph total variation from this definition of the Lovasz extension?

As an extra piece of info, in the supplementary material of "Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts", Hein and Setzer provide a derivation of the Choquet integral of the cut from the graph total variation (so they're working backwards). That derivation is helpful but I still have trouble connecting it to the definition above.

Answer 1

So I was able to come up with a somewhat simple derivation.

We're going to use a slightly different but equivalent definition of the Lovasz extension. First, let $ S_i = \{x>t_i\} $ be the level sets and

$$ f^{L}(t)= \sum_{i=1}^{|V|}t_i(F(S_i)-F(S_{i-1})) $$ is going to be the formulation of the Lovasz extension that we're going to use. For the cut function this means we have $$ f^{L}_{\text{cut}}(t) \triangleq \sum_{i=1}^{|V|}t_i(\text{cut}(S_i)-\text{cut}(S_{i-1})) $$ I should mention that $\text{cut}(S_i)$ is an abuse of notation and means taking the cutset between $S_i$ and its complement $\bar{S}_i$ i.e., $\text{cut}(S_i) = \text{cut}(S_i,\bar{S}_i) $. Next, we can make the following observation: $$ \text{cut}(S_{i}) = \text{cut}(S_{i-1}) + d_{i} - 2\text{cut}(S_{i-1},v_i). $$ This observation takes advantage of the shared structure in the chain of level sets. That is, we express the cut of a given level set, through the cut of the level set that came before it, i.e., the level set that has all the vertices of $S_i$ except for $v_i$.
Here $v_i$ is just the node indexed by $i$ and $d_i$ the degree of $v_i$. Using the above definition of $f^L_{\text{cut}}(t)$ and the aforementioned cut property of level sets we obtain: $$ \begin{align*} f^L_{\text{cut}}(t) &= \sum_{i=1}^{|V|}t_i( \text{cut}(S_{i-1}) + d_{i} - 2\text{cut}(S_{i-1},v_i)-\text{cut}(S_{i-1})) \\ &=\sum_{i=1}^{|V|}t_i(d_{i} - 2\text{cut}(S_{i-1},v_i)) \\ &=\sum_{i=1}^{|V|}t_i(\sum_{v_j \in E}w_{ij} - 2\sum_{v_j \in S_{i-1}}w_{ij}) \\ &=\sum_{i=1}^{|V|}t_i(\sum_{v_j \notin S_{i-1}}w_{ij} - \sum_{v_j \in S_{i-1}}w_{ij}) \\ &=\sum_{i=1}^{|V|}t_i(\sum_{t_j \leq t_i}w_{ij} - \sum_{t_j > t_i}w_{ij}) \\ &=\sum_{t_i>t_j}(t_i-t_j)w_{ij} \end{align*} $$ With this kind of derivation it becomes more apparent that, for each edge, each term $t_i$ will appear in the summation scaled by the edge weight and with sign that depends on the relative ranking of the nodes in the edge. Then, grouping the $t_i$ values based on the edges just leads to the total variation of the graph.

This is still kind of laborious compared to the proof in the paper by Hein, but it works strictly with the properties of the cut function on the level sets and does not involve any integration tricks.

I will leave the question open in case somebody can provide an alternative derivation.