Given an undirected graph $\mathcal{G=(V,E)}$, where $\mathcal{V}$ is the set of nodes and $\mathcal{E}$ is the set of edges, the max-cut problem asks to partition $\mathcal{V}$ into two disjoint sets, say $\mathcal{S}$ and $\mathcal{T}$, such that the sum of the weights of the
edges---called the cut value---of edges between $\mathcal{S}$ and $\mathcal{T}$ maximized.
The max-cut problem has important applications in various fields, including computer vision, statistical physics, and computational biology. It is also known to be NP-hard, which means that it is computationally difficult to solve optimally for large instances of the problem. Therefore, various approximation algorithms and heuristics have been developed to tackle the problem.
Minimizer Neural Network (MNN)
We are using Multi-Layer Perceptron (MLP) as our Minimizer Neural Network. The MLP takes an $m$-component learnable vector $\textbf{x}$ as input, passes it through $L$ layers with learnable parameters
$\boldsymbol{\theta}:=(\theta^{1},\cdots,\theta^{L})$, and gives an
$n$-component output vector $\textbf{z}$. Each component of $\textbf{z}$ lies in the interval
$[-1, 1]$. As a whole, Multi-Layer Perceptron acts as a continuous (differentiable) function
$f: \mathbb{R}^K \longrightarrow [-1,1]$ such that
$f(\textbf{x},\boldsymbol{\theta})=\textbf{z}$ and $K$ is the total number of learnable parameters.
We feed the output $\textbf{z}$ into the $\text{loss}(\textbf{x},\boldsymbol{\theta})=\text{energy}(\textbf{z})$ and minimize it with Adam optimizer.
After minimization, we got $\textbf{z}_{\text{out}}$, whose components we map to discrete values as
$z \longrightarrow 1$ and $-1$ for $z>0$ and $z\leq0$, respectively
to achieve a max-cut solution (for example, displayed by the graph below).