Calculus on finite weighted graphs

A node ${\displaystyle x_{j}\in V}$ is a neighbor of the node ${\displaystyle x_{i}\in V}$ if there exists an edge ${\displaystyle (x_{i},x_{j})\in E}$. In terms of notation this relationship can be abbreviated by ${\displaystyle x_{j}\sim x_{i}}$, which should be read as "${\displaystyle x_{j}}$ is a neighbor of ${\displaystyle x_{i}}$". Otherwise, if ${\displaystyle x_{j}}$ is not a neighbor of ${\displaystyle x_{i}}$ one writes ${\displaystyle x_{j}\not \sim x_{i}}$. The neighborhood ${\displaystyle {\mathcal {N}}(x_{i})}$ of a vertex ${\displaystyle x_{i}\in V}$ is simply the set of neighbors ${\displaystyle {\mathcal {N}}(x_{i}):=\{x_{j}\in V\colon x_{j}\sim x_{i}\}}$. The degree of a vertex ${\displaystyle x_{i}\in V}$ is the weighted size of its neighborhood:

${\displaystyle \deg(x_{i}):=\sum _{j\,:\,x_{j}\sim x_{i}}w(x_{i},x_{j}).}$

Note that in the special case where ${\displaystyle w\equiv 1}$ on ${\displaystyle E}$ (i.e. the graph is unweighted) we have ${\displaystyle \deg(x_{i}):=|{\mathcal {N}}(x_{i})|}$.

Let ${\displaystyle {\mathcal {H}}(V):=\{f:V\rightarrow \mathbb {R} \}}$ be the space of (real) vertex functions. Since ${\displaystyle V}$ is a finite set, any vertex function ${\displaystyle f\in {\mathcal {H}}(V)}$ can be represented as a ${\displaystyle n}$-dimensional vector ${\displaystyle f\in \mathbb {R} ^{n}}$ (where ${\displaystyle n:=|V|}$) and hence the space of vertex functions ${\displaystyle {\mathcal {H}}(V)}$ can be identified with an ${\displaystyle n}$-dimensional Hilbert space: ${\displaystyle {\mathcal {H}}(V)\cong \mathbb {R} ^{n}}$. The inner product of ${\displaystyle {\mathcal {H}}(V)}$ is defined as:

${\displaystyle \langle f,g\rangle _{{\mathcal {H}}(V)}:=\sum _{x_{i}\in V}f(x_{i})g(x_{i}),\quad \forall f,g\in {\mathcal {H}}(V).}$

Furthermore, for any vertex function ${\displaystyle f\in {\mathcal {H}}(V)}$ the ${\displaystyle \ell _{p}}$-norm and ${\displaystyle \ell _{\infty }}$-norm of ${\displaystyle f}$ are defined as:

${\displaystyle \|f\|_{p}={\begin{cases}\left(\sum _{x_{i}\in V}|f(x_{i})|^{p}\right)^{\frac {1}{p}},&{\text{ for }}1\leqslant p<\infty \ ,\\\max _{x_{i}\in V}|f(x_{i})|,&{\text{ for }}p=\infty \ .\end{cases}}}$

The ${\displaystyle \ell _{2}}$-norm is induced by the inner product.

In applications vertex functions are useful to label the vertices of the nodes. For example, in graph-based data clustering, each node represents a data point and a vertex function is used to identify cluster membership of the nodes.

Analogously to real vertex functions, one can introduce the space of real edge functions ${\displaystyle {\mathcal {H}}(E):=\{F:E\rightarrow \mathbb {R} \}}$. As any edge function ${\displaystyle F}$ is defined on a finite set of edges ${\displaystyle E}$, it can be represented as a ${\displaystyle m}$-dimensional vector ${\displaystyle F\in \mathbb {R} ^{m}}$, where ${\displaystyle m:=|E|}$. Hence, the space of edge functions ${\displaystyle {\mathcal {H}}(E)}$ can be identified as a ${\displaystyle m}$-dimensional Hilbert space, i.e., ${\displaystyle {\mathcal {H}}(E)\cong \mathbb {R} ^{m}}$.

One special case of an edge function is the normalized edge weight function ${\displaystyle w\colon E\rightarrow (0,1]}$ introduced above in the section on basic definitions. Similar to that function, any edge function ${\displaystyle F}$ can be trivially extended to ${\displaystyle V\times V}$ by setting ${\displaystyle F(x_{i},x_{j}):=0}$ if ${\displaystyle (x_{i},x_{j})\not \in E}$. The space of those extended edge functions is still denoted by ${\displaystyle {\mathcal {H}}(E)}$ and can be identified with ${\displaystyle \mathbb {R} ^{m}}$, where now ${\displaystyle m:=|V|^{2}}$.

The inner product of ${\displaystyle {\mathcal {H}}(E)}$ is defined as:

${\displaystyle \langle F,G\rangle _{{\mathcal {H}}(E)}:=\sum _{(x_{i},x_{j})\in E}F(x_{i},x_{j})G(x_{i},x_{j}),\quad \forall F,G\in {\mathcal {H}}(E).}$

Additionally, for any edge function ${\displaystyle F\in {\mathcal {H}}(V)}$ the ${\displaystyle \ell _{p}}$-norm and ${\displaystyle \ell _{\infty }}$-norm of ${\displaystyle F}$ are defined as:

${\displaystyle \|F\|_{p}={\begin{cases}\left(\sum _{(x_{i},x_{j})\in E}|F(x_{i},x_{j})|^{p}\right)^{\frac {1}{p}}&{\text{ for }}1\leqslant p<\infty \ ,\\\max _{(x_{i},x_{j})\in E}|F(x_{i},x_{j})|,&{\text{ for }}p=\infty \ .\end{cases}}}$

The ${\displaystyle \ell _{2}}$-norm is induced by the inner product.

If one extends the edge set ${\displaystyle E}$ in a way such that ${\displaystyle E=V\times V}$ than it becomes clear that ${\displaystyle {\mathcal {H}}(E)\cong \mathbb {R} ^{n\times n}}$ because ${\displaystyle {\mathcal {H}}(V)\cong \mathbb {R} ^{n}}$. This means that each edge function can be identified with a linear matrix operator.

Let ${\displaystyle G=(V,E,w)}$ be a finite weighted graph and let ${\displaystyle f\in {\mathcal {H}}(V)}$ be a vertex function. Then the weighted difference (or weighted graph derivative) of ${\displaystyle f}$ along a directed edge ${\displaystyle (x_{i},x_{j})\in E}$ is

${\displaystyle \partial _{x_{j}}f(x_{i})\$ :=\ {\sqrt {w(x_{i},x_{j})}}\left(f(x_{j})-f(x_{i})\right).}

For any weighted difference the following properties hold:

• ${\displaystyle \partial _{x_{i}}f(x_{j})=-\partial _{x_{j}}f(x_{i}),}$
• ${\displaystyle \partial _{x_{i}}f(x_{i})=0,}$
• ${\displaystyle f(x_{i})=f(x_{j})\Rightarrow \partial _{x_{j}}f(x_{i})=0.}$

Based on the notion of weighted differences one defines the weighted gradient operator on graphs ${\displaystyle \nabla _{w}:{\mathcal {H}}(V)\rightarrow {\mathcal {H}}(E)}$ as

${\displaystyle (\nabla _{w}f)(x_{i},x_{j})\ =\ \partial _{x_{j}}f(x_{i}).}$

This is a linear operator.

To measure the local variation of a vertex function ${\displaystyle f}$ in a vertex ${\displaystyle x_{i}\in V}$ one can restrict the gradient ${\displaystyle \nabla _{w}f}$ of ${\displaystyle f}$ to all directed edges starting in ${\displaystyle x_{i}}$ and using the ${\displaystyle \ell _{p}}$-norm of this edge function, i.e.,

${\displaystyle \|(\nabla _{w}f)(x_{i},\cdot )\|_{\ell _{p}}={\begin{cases}\left(\sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})^{\frac {p}{2}}|f(x_{j})-f(x_{i})|^{p}\right)^{\frac {1}{p}}&{\text{ for }}1\leq p<\infty ,\\\max _{x_{j}\sim x_{i}}{\sqrt {w(x_{i},x_{j})}}|f(x_{j})-f(x_{i})|&{\text{ for }}p=\infty .\end{cases}}}$

The adjoint operator ${\displaystyle \nabla _{w}^{*}\colon {\mathcal {H}}(E)\rightarrow {\mathcal {H}}(V)}$ of the weighted gradient operator is a linear operator defined by

${\displaystyle \langle \nabla _{w}f,G\rangle _{{\mathcal {H}}(E)}=\langle f,\nabla _{w}^{*}G\rangle _{{\mathcal {H}}(V)}\quad {\text{ for all }}f\in {\mathcal {H}}(V),G\in {\mathcal {H}}(E).}$

For undirected graphs with a symmetric weight function ${\displaystyle w\in {\mathcal {H}}(E)}$ the adjoint operator ${\displaystyle \nabla _{w}^{*}}$ of a function ${\displaystyle F\in {\mathcal {H}}(E)}$ at a vertex ${\displaystyle x_{i}\in V}$ has the following form:

${\displaystyle \left(\nabla _{w}^{*}F\right)(x_{i})\ =\ {\frac {1}{2}}\sum _{x_{j}\sim x_{i}}{{\sqrt {w(x_{i},x_{j})}}(F(x_{j},x_{i})-F(x_{i},x_{j}))}.}$

One can then define the weighted divergence operator on graphs via the adjoint operator as ${\displaystyle \operatorname {div} _{w}:=-\nabla _{w}^{*}}$. The divergence on a graph measures the net outflow of an edge function in each vertex of the graph.

The weighted graph Laplacian ${\displaystyle \Delta _{w}:{\mathcal {H}}(V)\rightarrow {\mathcal {H}}(V)}$ is a well-studied operator in the graph setting. Mimicking the relationship ${\displaystyle \operatorname {div} (\nabla f)=\Delta f}$ of the Laplace operator in the continuum setting, the weighted graph Laplacian can be derived for any vertex ${\displaystyle x_{i}\in V}$ as:

${\displaystyle {\begin{aligned}(\operatorname {div} _{w}(\nabla _{w}f))(x_{i})&={\frac {1}{2}}\sum _{x_{j}\sim x_{i}}{\sqrt {w(x_{i},x_{j})}}(\nabla _{w}f(x_{j},x_{i})-\nabla _{w}f(x_{i},x_{j}))\\&={\frac {1}{2}}\sum _{x_{j}\sim x_{i}}{\sqrt {w(x_{i},x_{j})}}\left({\sqrt {w(x_{i},x_{j})}}(f(x_{j})-f(x_{i}))-{\sqrt {w(x_{j},x_{i})}}(f(x_{i})-f(x_{j}))\right)\\&={\frac {1}{2}}\sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})(2f(x_{j})-2f(x_{i}))\\&=\sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})(f(x_{j})-f(x_{i}))\ =:\ (\Delta _{w}f)(x_{i}).\end{aligned}}}$

Note that one has to assume that the graph ${\displaystyle G}$ is undirected and has a symmetric weight function ${\displaystyle w(x_{i},x_{j})=w(x_{j},x_{i})}$ for this representation.

The continuous ${\displaystyle p}$-Laplace operator is a second-order differential operator that can be well-translated to finite weighted graphs. It allows the translation of various partial differential equations, e.g., the heat equation, to the graph setting.

Based on the first-order partial difference operators on graphs one can formally derive a family of weighted graph ${\displaystyle p}$-Laplace operators ${\displaystyle \Delta _{w,p}\colon {\mathcal {H}}(V)\rightarrow {\mathcal {H}}(V)}$ for ${\displaystyle 1\leq p<\infty }$ by minimization of the discrete ${\displaystyle p}$-Dirichlet energy functional

${\displaystyle E(f)\$ :=\ {\frac {1}{p}}\sum _{x_{i}\in V}\|\nabla _{w}f(x_{i},\cdot )\|_{\ell _{p}}^{p}.}

The necessary optimality conditions for a minimizer of the energy functional ${\displaystyle E}$ lead to the following definition of the graph ${\displaystyle p}$-Laplacian:

${\displaystyle (\Delta _{w,p}f)(x_{i})\$ :=\ \sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})^{\frac {p}{2}}|f(x_{j})-f(x_{i})|^{p-2}(f(x_{j})-f(x_{i})).}

Note that the graph Laplace operator is a special case of the graph ${\displaystyle p}$-Laplace operator for ${\displaystyle p=2}$, i.e.,

${\displaystyle (\Delta _{w,2}f)(x_{i})\ =\ (\Delta _{w}f)(x_{i})\ =\ \sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})(f(x_{j})-f(x_{i})).}$