**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.