Differentiation of functions over graphs

Question

---

In short: There are various ways to define differentiation over a graph. I am trying to get the big picture, like a more complete and structured bestiary.

---

Definitions.

Let $G=(V,E)$ be a directed weighted graph; we denote by $\omega(u,v)$ the weight of edge $(u,v)$, with $\omega(u,v) = 0$ if $(u,v) \not\in E$. We consider undirected and unweighted graphs as special cases.

For any $v$ in $V$, let $d(v)$ denote the (weighted) (out-)degree of $v$: $d(v) = \sum_{u\in V} \omega(v,u)$.

Let $f$ be a function with domain $V$, which we call a graph function: $f$ associates a value to each vertex. Equivalently, a graph function may be seen as a vector $\mathbf{x}$ with $\mathbf{x}_v = f(v)$ for all $v\in V$.

Let $\mathbf{A}$ denote the adjacency matrix of $G$: $\mathbf{A}_{uv} = \omega(u,v)$ for all $u$ and $v$ in $V$. Let $\mathbf{D}$ denote the diagonal matrix such that $\mathbf{D}_{vv} = d(v)$.

There are several ways to define a (discrete) derivative $f'$ of $f$ over $G$ or, equivalently, the derived vector $\mathbf{y}$ associated to $\mathbf{x}$ (with $\mathbf{y}_v = f'(v)$).

Shift+difference approach.

A natural approach consists in saying that differentiating a graph function is just shifting its values and making their component-wise difference: $f'(v) = f(v) - \overline{f}(v)$ where $\overline{f}$ denotes a shifted $f$. Then, defining a derivative boils down to defining a shift.

Several shift operators may be defined, for instance:

• $\overline{f}(v) = \sum_u \omega(u,v)\cdot f(u)$: the shifted value at $v$ is the (weighted) sum of the value at its neighbors. Equivalently, $\mathbf{\overline{x}} = \mathbf{A}\cdot \mathbf{x}$ and so this shift is called the adjacency shift.
• $\overline{f}(v) = \sum_u \omega(u,v)\cdot \frac{f(u)}{d(u)}$: the shifted value at $v$ is the (weighted) sum of the value at its neighbors divided by their (weighted) (outgoing) degree. Equivalently, $\mathbf{\overline{x}} = \mathbf{R}\cdot \mathbf{x}$, where $\mathbf{R}= \mathbf{D}^{-1}\cdot \mathbf{A}$ denotes the (weighted) random walk transition matrix of $G$, and so this shift is called the random walk shift.

Direct matrix approach.

Another approach directly defines matrix operators.

The most classical probably is the graph Laplacian $\mathbf{L} = \mathbf{D}-\mathbf{A}$. Then, $\mathbf{y} = \mathbf{L}\cdot \mathbf{x}$ means that $f'(v) = \sum_u \omega(u,v)\cdot (f(v)-f(u))$: the differentiated value at $v$ is the (weighted) sum of the differences between the value at $v$ and the one at its neighbors.

Several variants of this Laplacian operator exist. In particular, the random walk Laplacian defined as $\mathbf{D}^{-1}\cdot \mathbf{L}$ is nothing but the random walk differentiation, based on the random walk shift above.

Questions and hints.

All these differentiation definitions are used in the literature, as well as others.

What other differentiation operators do you know? Which are your favorite ones? Why?

Is there any meaningful classification of these operators? Which criteria are the most relevant?

The classification may be property-oriented. For instance, some shifts preserve the global sum, others the global energy.

The classification may rely on the operator form, like for instance the class of generalized Laplacians (for all $u\ne v$: $\mathbf{Q}_{uv}<0$ if $(u,v)\in E$, $\mathbf{Q}_{uv}=0$ otherwise; and $\mathbf{Q}_{vv}$ equal to any number).

Similarly, one may distinguish operators having a matrix expression from operators having a shift+difference expression. Some may have both kinds of expression, and others none. For instance:

• the adjacency operator and the random walk operator above have both a matrix and a shift+difference expression.
• the Laplacian operator above is defined by a matrix expression but it does not seem to have a shift+difference expression, since it leads to $f'(v) = d(v)\cdot f(v) - \sum_u \omega(u,v)\cdot f(u)$.
• if instead we define $\mathbf{L'}=(\mathbf{D}^{-1}\cdot \mathbf{L})^\top$, then $\mathbf{y} = \mathbf{L'}\cdot \mathbf{x}$ leads to $f'(v) = f(v) - \sum_u \omega(v,u)\cdot \frac{f(u)}{d(v)}$; this operator is close to the Laplacian one, but it has a shift+difference expression.

I am personally most interested by operators having a shift+difference expression and wonder if there are contexts where other kinds of differentiation operators make more sense.

Answer 1

I don't have enough reputation for a comment, but I'll give you my two cents. You already mentioned operators that rely on shifting and differentiating. I would like to point here towards some definitions that motivate the graph Laplacian as the discrete analog of the continuous Laplacian and allow to define other high-order differential operators on graphs.

Differential operators in euclidean spaces

Let $f$ be a scalar function in $\mathbb{R}^n$ and $\mathbf{F} = [F_1, F_2, \cdots, F_n]$ be a vector valued function in $\mathbb{R}^n$. We have the following definitions:

• Gradient: $\nabla f = \left[ \frac{\partial f}{\partial x_1}, \dots , \frac{\partial f}{\partial x_n}\right]^T$.
• Divergence: $\text{div}~ \mathbf{F} = \nabla \cdot \mathbf{F} = \sum_{i = 1}^{n} \frac{ \partial F_i }{\partial x_i}$.
• Laplacian: $\Delta f = \text{div}~ \nabla f = \nabla \cdot \nabla f = \sum_{i = 1}^{n} \frac{\partial^2 f}{\partial^2 x_i}$

A nice connection between the gradient and the divergence operators is that one is the adjoint of the other. This is, we have that $\langle - \text{div}~ \mathbf{F}, f \rangle = \langle \mathbf{F}, \nabla f \rangle$. This last equality implies that we can relate the regularity to $f$ to the Laplacian Dirichlet energy through the equality: \begin{equation} \frac{1}{2} \int \| \nabla f \|^2 dx = - \frac{1}{2} \int f \Delta f dx \end{equation}

Differential operators in Graphs

Let $G(V, E)$ be a graph, $f: V \to \mathbb{R}$ a function defined on the vertices, and $h: E \to \mathbb{R}$ a function defined on the edges. The building block for differentiation in graphs is the edge derivative given as \begin{equation} (df)_{uv} = \sqrt{w_{uv}}(f_v - f_u). \end{equation} Even though $f$ is a function defined on the vertices, the derivative $(df)_{uv}$ lives in the space of edge functions. However, we can see that any vertex $v$ plays a role in the edge derivative of all its incident edges. Thus, all those derivatives can be stack in a vector associated to $v$ that can be interpreted as the gradient of $f$ at vertex $v$: \begin{equation}\label{eq.gradient.graphs} (\nabla f)_v = [(df)_{uv}, ... , ] \hspace{10pt} \forall u \sim v \end{equation} Now, to define divergence in graphs we exploit the fact that it is the adjoint operator of the gradient. This is, the divergence is the operator $d^*$ that satisfies $\langle \nabla f, h \rangle = \langle f, -d^*h \rangle$. Observe that $\nabla$ sends functions from the space of vertices to the space of edges, while $d^*$ does the converse. By developing the inner products we have that \begin{equation}\label{} \sum_{v \in V} \sum_{u \sim v} (df)_{uv} h_{uv} = - \sum_{v \in V} f_v (d^*h)_v. \end{equation} After developing the sum for all $v$, the terms can be rearranged and the equation rewritten as \begin{equation}\label{} \sum_{v \in V} \sum_{u \sim v} f_v \sqrt{w_{uv}} (h_{uv} - h_{vu}) = - \sum_{v \in V} f_v (d^*h)_v. \end{equation} We can thus see that the divergence evaluated at $v$ is given as \begin{equation}\label{eq.div.graphs} (d^*h)_v = \sum_{u \sim v} \sqrt{w_{uv}} (h_{uv} - h_{vu}). \end{equation} Having the gradient and divergence defined, now the graph Laplacian follows in the standard way: $\Delta f = d^*(\nabla f)$. Substituting the expressions for the gradient and the divergence in the Laplacian definition we obtain the classical expression of $\Delta f$ at a vertex $v$ as \begin{equation}\label{} (\Delta f)_v = \sum_{u \sim v} w_{uv} (f_v - f_u), \end{equation} which you already introduced in matrix form. Then, it also becomes possible to assess the regularity of a function $f$ by means of a discrete analog of the Laplacian Dirichlet energy as follows: \begin{equation}\label{} \langle f, \Delta f \rangle = \frac{1}{2} \sum_{v \in V} ( \nabla f )_v^2 = \sum_{(u,v) \in \mathcal{E}} w_{uv} (f_v - f_u)^2. \end{equation} This quadratic form is widely used in regularization problems on graphs and has been used as the basis to define other types of operators to assess the regularity of $f$ See Smola, et al.. Also from these definitions it is straightforward to motivate high-order differential operators like the $p$-Laplacians and $\infty$-Laplacians see Elmoataz, et al., or Iterated Laplacians see Zhou, et al.. Moreover, these are not the only definitions of the edge-derivative, gradients, etc. see Zhou, et al..

Hope this helps!

Answer 2

This is just the tip of the iceberg so to speak, but let me add to your bestiary of discrete derivatives the David-Eynard $\nabla$-operator as defined in https://arxiv.org/pdf/1307.3123.pdf. Briefly, the picture is this:

Begin with an abstract triangulation $T$, in other words an abstract graph with vertex and edge sets $\mathrm{V}(T)$ and $\mathrm{E}(T)$ together with an face set $\mathrm{F}(T)$ consisting of vertex triples ("triangles"). The triangulation is usually assumed to be locally finite in the sense each vertex $\mathrm{v} \in \mathrm{V}(T)$ participates as an end-point in only finitely many edges (and consequently finitely many triangles). Now let us assume we may equip $T$ with an polygonal embedding into the plane, namely an injective, complex-valued function $z: \mathrm{V}(T) \longrightarrow \Bbb{C}$. We interpret the embedding as mapping edges to straight line segments and we require (!) that these line segements are pairwise non-crossing, i.e. the interior of any line segment does not intersect the closure of any other line segment. Clearly each abstract triangle $\mathrm{f} = \{ \mathrm{u}, \mathrm{v}, \mathrm{w}\}$ is mapped to an actual planar triangle $z(\mathrm{f})$ with vertices $\{z(\mathrm{u}), z(\mathrm{v}), z(\mathrm{w})\}$ under this set-up. We'll orient an abstract triangle $\mathrm{f} = \{ \mathrm{u}, \mathrm{v}, \mathrm{w}\}$, i.e. read it as an ordered triple $\mathrm{f}^\circlearrowleft = ( z(\mathrm{u}), z(\mathrm{v}), z(\mathrm{w}) )$ up to a cyclic shirt, according to whether the area of $z(\mathrm{f})$ is calculated by the determinant

\begin{equation} A(\mathrm{f}) = {1 \over {4 \mathrm{i}}} \, \det \, \begin{pmatrix} 1 & 1 & 1 \\ \overline{z}(\mathrm{u}) &\overline{z}(\mathrm{v}) &\overline{z}(\mathrm{w}) \\ z(\mathrm{u}) &z(\mathrm{v}) &z(\mathrm{w}) \end{pmatrix} \end{equation}

with the correct sign. In other words orientation is determined by reading triangles in the plane counter-clockwise.

Now given any complex-valued function $\phi: \mathrm{V}(T) \longrightarrow \Bbb{C}$ we may defined its discrete derivative $\nabla \phi: \mathrm{F}(T) \longrightarrow \Bbb{C}$ by

\begin{equation} \nabla \phi(\mathrm{f}) \ := \ {1 \over {4 \mathrm{i} A(\mathrm{f})}} \, \det \, \begin{pmatrix} 1 & 1 & 1 \\ \overline{z}(\mathrm{u}) &\overline{z}(\mathrm{v}) &\overline{z}(\mathrm{w}) \\ \phi(\mathrm{u}) &\phi(\mathrm{v}) &\phi(\mathrm{w}) \end{pmatrix} \end{equation}

where $\mathrm{f}^\circlearrowleft = ( z(\mathrm{u}), z(\mathrm{v}), z(\mathrm{w}))$. One can similiarly define a complex conjugate $\overline{\nabla}$-operator by making the substitution $z(\mathrm{p}) \mapsto \overline{z}(\mathrm{p})$ for each vertex $\mathrm{p} \in \mathrm{f}$ occuring the formula for the $\nabla$-operator. Given a smooth, complex-valued function $g: \Bbb{C} \longrightarrow \Bbb{C}$ we may restrict it to vertices $\mathrm{v} \in \mathrm{V}(T)$ by setting

\begin{equation} g(\mathrm{v}) \ := \ g(z(\mathrm{v})) \end{equation}

If we do this then clearly

\begin{equation} \begin{array}{ll} \nabla \, g = 1 &\nabla \, \overline{g} = 0 \\ \overline{\nabla} \, g = 0 &\overline{\nabla} \, \overline{g} = 1 \end{array} \end{equation}

where $g(w) = w$ for $w \in \Bbb{C}$. So $\nabla$ and $\overline{\nabla}$ agree with the continuous Wirtinger derivatives $\partial_w$ and $\overline{\partial}_w$ respectively up to linear functions in the global coordinates $w, \bar{w}$. If the polygonal embedding of $T$ has the added property that the circumcenter of each embedded triangle $z(\mathrm{f})$ is contained in its closure $\overline{z(\mathrm{f})}$ then on can define a postive semi-definite Laplace operator $\Delta: \Bbb{C}^{\mathrm{V}(T)} \longrightarrow \Bbb{C}^{\mathrm{V}(T)}$ by

\begin{equation} \Delta = 4 \, {\frak{Re}} \Big[ \overline{\nabla}^{\scriptscriptstyle \top} A \, \nabla \Big] \end{equation}

where $\Bbb{C}^{\mathrm{V}(T)}$ and $\Bbb{C}^{\mathrm{V}(F)}$ are the vector spaces of all complex-valued functions $\phi: \mathrm{V}(T) \longrightarrow \Bbb{C}$ and $\psi: \mathrm{V}(F) \longrightarrow \Bbb{C}$ respectively and where $A: \Bbb{C}^{\mathrm{V}(F)} \longrightarrow \Bbb{C}^{\mathrm{V}(F)}$ is the area operator defined by $A \phi (\mathrm{f}) := A(\mathrm{f}) \, \phi(\mathrm{f})$ for $\phi \in \Bbb{C}^{\mathrm{V}(F)}$ and $\mathrm{f} \in \mathrm{F}(T)$. One can show that $\Delta$ satisfies an adjunction formula (with respect to an appropriately defined inner product on $\Bbb{C}^{\mathrm{V}(T)}$) which justifies the view that $\Delta$ is the correct analogue of the Beltrami-Laplace operator in the polygonal setting (with the condition about circumcenters added).

ines.