7
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ Not sure how it fits your big picture (and I don't have time for a proper answer right now), but if your graph is the covering relation of a partial order (poset), its Zeta and Möbius transforms are kind of summation and difference operators, respectively. Indeed if your poset is a chain, the Möbius transform is simply the sequential difference operator. Kennes and Smets's paper may be of interest: arxiv.org/abs/1304.1122 $\endgroup$ May 11 at 7:46
  • 1
    $\begingroup$ @JukkaKohonen This is interesting, thank you! I am not used to the notations of this paper and find them a little confusing, but the considered operators seem very close to the "adjacency" operator defined in my post: it makes the sum of values at incoming neighbours, right? $\endgroup$ May 11 at 10:28
  • 1
    $\begingroup$ Some answers I gave to (this)[mathoverflow.net/questions/368963/… or (that)[mathoverflow.net/questions/357751/… question might be related. The TLDR: I think it is not optimal to define the difference on the vertices, it should be defined on the edges. So work with the incidence matrix not the adjacency matrix. On the other side, if you define a different "energy function", you get different "Laplacians". $\endgroup$
    – ARG
    May 11 at 11:01
  • 1
    $\begingroup$ Thank your @ARG, interesting answers indeed. I am thinking a lot about the incidence matrix currently (see, e.g., the accepted answer to my question on line graphs there: mathoverflow.net/questions/389839/…), and edge-defined differentiation may make a meaningful category in my classification. $\endgroup$ May 11 at 13:24
5
$\begingroup$

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!

$\endgroup$
1
  • 1
    $\begingroup$ Thank you for this nice contribution! It makes clearer why the Laplacian is a good operator. The connection with energy is interesting and the references too! The curvature operator defined in Zhou, et al, is particularly appealing for exploring the diversity of operators. $\endgroup$ May 12 at 6:50
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks Ines, this is a nice addition to my collection! I guess there is a class of operators that rely on embeddings making generalization of various geometrical operators natural. $\endgroup$ May 18 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.