How to understand the combinatorial Laplacian $\Delta$ which is defined on the graph?

Just to add an (in my opinion important) piece of information. Say $F$ is a function on the vertices of a graph, so $F:V \to \mathbb{R}$. Then $\nabla F$ is a function from the edges to $\mathbb{R}$ (here I see an edge as a pair of vertices $(x,y)$, so edges are oriented): $$\nabla F (x,y) := F(y) - F(x)$$ Now this definition is very natural in many ways. For example, you would expect that the integral of the gradient of a function along a path is just the difference of the values of the function at the end of this path. And this holds here: if $\vec{p}$ is an oriented path (say from $a$ to $b$) then $\sum_{\vec{e} \in \vec{p}} \nabla F(\vec{e}) = F(b) - F(a)$. You can add a weight to the edges, but this is (in my opinion) not the important point for intuition.

Here is the important piece of information: if your graph has bounded degree$^*$, $\nabla$ defines an operator from $\ell^2V$ to $\ell^2E$. (The pairing on $\ell^2V$ is just $\langle f \mid g \rangle_V = \sum_{v \in V} f(v)g(v)$. Same pairing on $\ell^2E$ just that the sum is over the edges) So you may ask, what is the adjoint of this operator? Well the defining property can be tested on Dirac masses (which are a nice basis of our spaces): $$ \langle \nabla^* \delta_{\vec{e}} \mid \delta_x \rangle = \langle \delta_{\vec{e}} \mid \nabla\delta_x \rangle $$ So this is $+1$ if $\vec{e}$ has $x$ as target, $-1$ if $x$ is the source and 0 otherwise. Extended by linearity this gives: (here $G(x,y)$ is a function on the edges) $$ \nabla^* G(x) = \sum_{y \in N(x)} G(x,y) - \sum_{y \in N(x)} G(y,x) $$ where $y \in N(x)$ means $y$ is a neighbour of $x$. (If your edges are not oriented, it is natural to consider only alternating functions on the edges, that is $G(x,y) = -G(y,x)$; the above expression simplifies then a bit)

The rest is just a computation: $$ \begin{array}{rl} \nabla^* \nabla F(x) &= \displaystyle \sum_{y \in N(x)} \nabla F(x,y) - \sum_{y \in N(x)} \nabla F(y,x) \\ &= \displaystyle \bigg( \sum_{y \in N(x)} [F(y) - F(x)] \bigg) - \bigg( \sum_{y \in N(x)} [F(x) - F(y)] \bigg) \\ &= \displaystyle 2 \bigg( \sum_{y \in N(x)} [F(y) - F(x)] \bigg) \\ &= \displaystyle 2 \bigg( \big[ \sum_{y \in N(x)} F(y) \big] - \deg(x) F(x) \bigg) \\ \end{array} $$ And that's the formula for the Laplacian (when the conductance is 1). Note that I got a difference of a factor of 2 (because my definition of divergence is a bit different). But having a divergence which is the adjoint of the gradient, is a very important point, in my opinion.

If you add a weight to the edges, the computation are slightly more complicated, but it's just [possibly painful] bookkeeping.

$^*$ if you have weighted edges you could have an infinite number of edges as long as their weight is bounded

EDIT: a small addendum, for the case where the edge have a weight, as I realised there are many ways to add a weight in the above setup:

• you can add it to the definition of the gradient (but then the property that the integral along a curve is the difference of the values at the ends fail)

• you can add it to the definition of the divergence

• you can add it to the norm on $\ell^2E$

I would recommend doing using the third one (which is the most natural: since the edge have a weight, incorporate it the norm in $\ell^2E$). This means the inner product on $\ell^2E$ is $$\langle f \mid g \rangle = \sum_{\vec{e} \in E} c(\vec{e}) f(\vec{e}) g(\vec{e}) $$ Because edges can be written as pair of vertices $(x,y)$ this reads $$\langle f \mid g \rangle = \sum_{(x,y) \in E} c(x,y) f(x,y) g(x,y) $$ [In your context, you probably want $c(x,y) = c(y,x)$.]

Now if you look at $$ \langle \nabla^* \delta_{\vec{e}} \mid \delta_x \rangle = \langle \delta_{\vec{e}} \mid \nabla\delta_x \rangle $$ then this is $c(y,x)$ if $\vec{e}$ has $x$ as target, $-c(x,y)$ if $x$ is the source and 0 otherwise. Extended by linearity this gives: (here $G(x,y)$ is a function on the edges) $$ \nabla^* G(x) = \sum_{y \in N(x)} c(x,y) G(x,y) - \sum_{y \in N(x)} c(y,x) G(y,x) $$ If you assume $c(x,y) = c(y,x)$ and $G(x,y) = -G(y,x)$ (as you should in the unoriented case), you get: $$ \nabla^* G(x) = 2 \sum_{y \in N(x)} c(x,y) G(x,y) $$ Then, direct computation yields $$ \begin{array}{rl} \nabla^* \nabla F(x) &= \displaystyle 2 \sum_{y \in N(x)} c(x,y) \nabla F(x,y) \\ &= \displaystyle 2 \bigg( \sum_{y \in N(x)} c(x,y) [F(y) - F(x)] \bigg) \\ &= \displaystyle 2 \bigg( \sum_{y \in N(x)} [ c(x,y) F(y) - c(x,y) F(x)] \bigg) \\ &= \displaystyle 2 \bigg( \big[ \sum_{y \in N(x)} c(x,y) F(y) \big] - \big[ \sum_{y \in N(x)} c(x,y) \big] F(x) \bigg) \\ &= \displaystyle 2 \bigg( \big[ \sum_{y \in N(x)} c(x,y) F(y) \big] - c(x) F(x) \bigg) \\ \end{array} $$ where $c(x)$ is a short-hand for $\sum_{y \in N(x)} c(x,y)$.

This is the Laplacian (up to a sign). The fact that you put a "$-$" sign or not depends entirely on your taste: if you want a Laplacian with negative spectrum, you should put a "$-$", otherwise don't (it's a standard trick to see that $A^*A$ has positive spectrum).

Fix a vertex $v$. Then $$ \nabla F(uv) = c(u,v)\big(F(v)-F(u)\big) $$ for $u$ adjacent to $v$. Now \begin{align*} \nabla\cdot\nabla F(v) &= \sum_{uv} c(v,u)\big(F(u)-F(v)\big)\\ &= -F(v)\left(\sum_u c(v,u)\right) + \sum_u c(v,u) F(u)\\ &= -\sum_u \big(c(u)\mathbb{1}_{u=v}-c(v,u)\big)F(u)\\ &=-\sum_u \Delta(v,u)F(u) \end{align*} where the sums are always over $u$ adjacent to $v$, and I assume $c(u)=\sum_u c(v,u)$.