In my convex optimization notes, it defines the max cut problem as $$\max_{x\in\Bbb{R}^n} \hspace{.1 in} x^TL_Gx\hspace{.5 in} \text{subject to}\ \ x_i\in \{-1,1\},\ i=1,\cdots,n$$
where $L_G$ is a matrix called the Laplacian of the graph $G$.
In reality, we are maximizing the expression $$\dfrac{1}{2}\sum_{i,j\in V}w_{ij}(x_i-x_j)^2 \propto \dfrac{1}{2}\sum_{i,j\in V}w_{ij}(1-x_ix_j) ,\hspace{.5 in}x\in \{-1,1\}^n.$$ Can someone explain/derive how the two expressions are equal? ie the form of $L_G$ such that $$\dfrac{1}{2}\sum_{i,j\in V}w_{ij}(x_i-x_j)^2=x^TL_Gx$$ or such that $$\dfrac{1}{2}\sum_{i,j\in V}w_{ij}(1-x_ix_j)=x^TL_Gx$$ because clearly $x^TAx=\sum_{ij}A_{ij}x_ix_j$, but that's not the form we have above.
From the second form, I see that we almost get there: $$\dfrac{1}{2}\sum_{i,j\in V}w_{ij}(1-x_ix_j)= \dfrac{1}{2}\sum_{i,j\in V}w_{ij} -\dfrac{1}{2}\sum_{i,j\in V}w_{ij}x_ix_j =\dfrac{1}{2}\sum_{i,j\in V}w_{ij} -\dfrac{1}{2}x^TWx $$ but the first term confuses me.
Simple case & intuitive explanation
The elements of the (simple -- i.e., weights $0$ or $1$) graph Laplacian are given by (from Wikipedia): $$ L_{ij}:= \begin{cases} \deg(v_i),& \text{if } i=j;\\ -1, & \text{if }i\sim j\textrm{ (is connected);}\\ 0, & \text{otherwise.} \end{cases} $$ So an example graph Laplacian might look like: $$ L_{\text{example}}=\begin{bmatrix} 2&-1&-1&0 \\ -1&3&-1&-1\\ -1&-1&2&0\\ 0&-1&0&1 \end{bmatrix} $$ Notice how each row sums to zero because the diagonal element is the number of connected vertices and the off-diagonal elements subtract $1$ for every connected vertex. The exact same reason is why each column sums to zero (i.e., the matrix is symmetric).
Now let $x\in \{-1,1\}^n$, where $x_i$ represents whether vertex $i$ is on one side of the cut or the other. One example could be: $$ x_{\text{example}}=\begin{bmatrix} 1\\ -1\\ -1\\ 1 \end{bmatrix} $$ so computing $L_{\text{example}}x_{\text{example}}$ would return a column vector. Each $i$th element in this column vector would be calculated by taking the degree of vertex $i$, adding $1$ for each connected vertex on the other side of the cut, and subtracting $1$ for each connected vertex on the same side of the cut, then arbitrarily multiplying by $-1$ if it’s on a specific side of the cut. This arbitrary multiplication doesn’t matter though, because the purpose of computing $x_{\text{example}}^TL_{\text{example}}x_{\text{example}}$ is to cancel out these minus signs. For the example above, $$ x_{\text{example}}^TL_{\text{example}}x_{\text{example}}= \begin{bmatrix} 1& -1& -1& 1 \end{bmatrix} \begin{bmatrix} 4\\ -4\\ -2\\ 2 \end{bmatrix} =12 $$
Thus, it’s easy to see that element $i$ in $Lx$ gives (up to $-1$): $$ (Lx)_i= \deg(v_i)+\Bigg(\sum_{ \substack{j\sim i,\\ j\text{ other side}} }1\Bigg) -\Bigg(\sum_{\substack{j\sim i,\\ j\text{ same side}} }1\Bigg)$$ We also see that $x^TLx$ gives the sum of these: $$ \begin{align} x^TLx&=\sum_{i\in V}\deg(v_i)+2(\text{# edges crossing cut})-2(\text{# edges not crossing cut})\\ &=2(\text{# edges}+\text{# edges crossing cut}-\text{# edges not crossing cut})\\ &=4(\text{# edges crossing cut}) \end{align}$$ because $$ \text{# edges}=\text{# edges crossing cut}+\text{# edges not crossing cut}. $$ Thus, this representation with $L$ (specifically $x^TLx$) is useful in convex optimization/max cut because it is optimizing something proportional to the number of edges crossing the cut.
Clearly this is the result for an unweighted graph Laplacian. The generalization to a graph with weighted edges is simple and left as an exercise for the reader.
General graph Laplacian with weights in $\mathbb{R}_+$
I omit the lengthy explanation, as that is very similar to the above. Here is the math:
$$ L_{G_{ij}}:= \begin{cases} \sum_{k\in V}w_{ik}, & \text{if } i=j;\\ -w_{ij}, & \text{if }i\neq j; \end{cases} $$ where we take $w_{ij}=0$ if $i,j$ are not connected. We also define $w_{ii}=0$ because no edges exist from one node to itself. \begin{align} \implies \left\lvert\big[L_Gx\big]_i\right\rvert &= \sum_{k\in V}w_{ik} -\sum_{\substack{k\in V,\\ \text{same side}}}w_{ik} +\sum_{\substack{k\in V,\\ \text{other side}}}w_{ik} \\ &= 2\sum_{\substack{k\in V,\\ \text{other side}}}w_{ik} \\ \implies x^TL_Gx &= 2\sum_{i\in V}\sum_{\substack{k\in V,\\ \text{other side}}}w_{ik} \\ &= 2\sum_{i\in V}\sum_{j\in V}w_{ij}(x_i-x_j)^2/4 \\ &= \dfrac{1}{2}\sum_{i,j\in V}w_{ij}(x_i-x_j)^2 \end{align} This answers the original question in full.