In mathematics, calculus on finite weighted graphs is a discrete calculus for functions whose domain is the vertex set of a graph with a finite number of vertices and weights associated to the edges. This involves formulating discrete operators on graphs which are analogous to differential operators in calculus, such as graph Laplacians (or discrete Laplace operators) as discrete versions of the Laplacian, and using these operators to formulate differential equations, difference equations, or variational models on graphs which can be interpreted as discrete versions of partial differential equations or continuum variational models. Such equations and models are important tools to mathematically model, analyze, and process discrete information in many different research fields, e.g., image processing, machine learning, and network analysis.
In applications, finite weighted graphs represent a finite number of entities by the graph's vertices, any pairwise relationships between these entities by graph edges, and the significance of a relationship by an edge weight function. Differential equations or difference equations on such graphs can be employed to leverage the graph's structure for tasks such as image segmentation (where the vertices represent pixels and the weighted edges encode pixel similarity based on comparisons of Moore neighborhoods or larger windows), data clustering, data classification, or community detection in a social network (where the vertices represent users of the network, the edges represent links between users, and the weight function indicates the strength of interactions between users).
The main advantage of finite weighted graphs is that by not being restricted to highly regular structures such as discrete regular grids, lattice graphs, or meshes, they can be applied to represent abstract data with irregular interrelationships.
If a finite weighted graph is geometrically embedded in a Euclidean space, i.e., the graph vertices represent points of this space, then it can be interpreted as a discrete approximation of a related nonlocal operator in the continuum setting.
A finite weighted graph
G
G=(V,E,w)
V=\{x1,...,xn\},n\inN
E\subsetV x V
w\colonE → R
In a directed graph, each edge
(xi,xj)\inE
xi\inV
xj\inV
(xi,xj)
(xj,xi)
w(xi,xj)=w(xj,xi)
The edge weight function
w
(xi,xj)\inE
w(xi,xj)>0
V x V
w(xi,xj)=0
(xi,xj)\not\inE
In applications each graph vertex
x\inV
w:E → (0,1]
In the following it is assumed that the considered graphs are connected without self-loops or multiple edges between vertices. These assumptions are mostly harmless as in many applications each connected component of a disconnected graph can be treated as a graph in its own right, each appearance of
w(xi,xi)
i=j
A node
xj\inV
xi\inV
(xi,xj)\inE
xj\simxi
xj
xi
xj
xi
xj\not\simxi
lN(xi)
xi\inV
l{N}(xi):=\{xj\inV\colonxj\simxi\}
xi\inV
\deg(xi):=
\sum | |
j:xj\simxi |
w(xi,xj).
Note that in the special case where
w\equiv1
E
\deg(xi):=|l{N}(xi)|
Let
l{H}(V):=\{f:V → R\}
V
f\inl{H}(V)
n
f\inRn
n:=|V|
l{H}(V)
n
l{H}(V)\congRn
l{H}(V)
\langlef,g\ranglel{H(V)}:=
\sum | |
xi\inV |
f(xi)g(xi), \forallf,g\inl{H}(V).
Furthermore, for any vertex function
f\inl{H}(V)
\ellp
\ellinfty
f
\|f\|p=\begin{cases} \left(
\sum | |
xi\inV |
p | |
|f(x | |
i)| |
| ||||
\right) |
,&for1\leqslantp<infty ,\\
max | |
xi\inV |
|f(xi)|,&forp=infty . \end{cases}
The
\ell2
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
l{H}(E):=\{F:E → R\}
F
E
m
F\inRm
m:=|E|
l{H}(E)
m
l{H}(E)\congRm
One special case of an edge function is the normalized edge weight function
w\colonE → (0,1]
F
V x V
F(xi,xj):=0
(xi,xj)\not\inE
l{H}(E)
Rm
m:=|V|2
The inner product of
l{H}(E)
\langleF,G\ranglel{H(E)}:=
\sum | |
(xi,xj)\inE |
F(xi,xj)G(xi,xj), \forallF,G\inl{H}(E).
Additionally, for any edge function
F\inl{H}(V)
\ellp
\ellinfty
F
\|F\|p=\begin{cases}
\left(\sum | |
(xi,xj)\inE |
|F(xi,
p\right) | |
x | |
j)| |
| ||||
&for1\leqslantp<infty ,\\
max | |
(xi,xj)\inE |
|F(xi,xj)|,&forp=infty . \end{cases}
The
\ell2
If one extends the edge set
E
E=V x V
l{H}(E)\congRn
l{H}(V)\congRn
An important ingredient in the calculus on finite weighted graphs is the mimicking of standard differential operators from the continuum setting in the discrete setting of finite weighted graphs.This allows one to translate well-studied tools from mathematics, such as partial differential equations and variational methods, and make them usable in applications which can best be modeled by a graph.The fundamental concept which makes this translation possible is the graph gradient, a first-order difference operator on graphs. Based on this one can derive higher-order difference operators, e.g., the graph Laplacian.
Let
G=(V,E,w)
f\inl{H}(V)
f
(xi,xj)\inE
\partial | |
xj |
f(xi) := \sqrt{w(xi,xj)}\left(f(xj)-f(xi)\right).
For any weighted difference the following properties hold:
\partial | |
xi |
f(xj)=
-\partial | |
xj |
f(xi),
\partial | |
xi |
f(xi)=0,
f(xi)=f(xj) ⇒
\partial | |
xj |
f(xi)=0.
Based on the notion of weighted differences one defines the weighted gradient operator on graphs
\nablaw:l{H}(V) → l{H}(E)
(\nablawf)(xi,xj) =
\partial | |
xj |
f(xi).
This is a linear operator.
To measure the local variation of a vertex function
f
xi\inV
\nablawf
f
xi
\ellp
\|(\nablawf)(xi, ⋅ )\|
\ellp |
=\begin{cases}
\left(\sum | |
xj\simxi |
w(xi,
| ||||
x | ||||
j) |
|f(xj)-
p\right) | |
f(x | |
i)| |
| ||||
&for1\leqp<infty,\\
max | |
xj\simxi |
\sqrt{w(xi,xj)}|f(xj)-f(xi)|&forp=infty. \end{cases}
The adjoint operator
*\colonl{H}(E) → l{H}(V) | |
\nabla | |
w |
\langle\nablawf,G\ranglel{H(E)}=\langle
*G\rangle | |
f,\nabla | |
l{H |
(V)} forallf\inl{H}(V),G\inl{H}(E).
For undirected graphs with a symmetric weight function
w\inl{H}(E)
* | |
\nabla | |
w |
F\inl{H}(E)
xi\inV
*F\right)(x | |
\left(\nabla | |
i) |
=
1 | |
2 |
\sum | |
xj\simxi |
{\sqrt{w(xi,xj)}(F(xj,xi)-F(xi,xj))}.
One can then define the weighted divergence operator on graphs via the adjoint operator as
\operatorname{div}w:=
* | |
-\nabla | |
w |
The weighted graph Laplacian
\Deltaw:l{H}(V) → l{H}(V)
\operatorname{div}(\nablaf)=\Deltaf
xi\inV
\begin{align} (\operatorname{div}w(\nablawf))(xi) &=
1 | |
2 |
\sum | |
xj\simxi |
\sqrt{w(xi,xj)}(\nablawf(xj,xi)-\nablawf(xi,xj))\\ &=
1 | |
2 |
\sum | |
xj\simxi |
\sqrt{w(xi,xj)}\left(\sqrt{w(xi,xj)}(f(xj)-f(xi))-\sqrt{w(xj,xi)}(f(xi)-f(xj))\right)\\ &=
1 | |
2 |
\sum | |
xj\simxi |
w(xi,xj)(2f(xj)-2f(xi))\\ &=
\sum | |
xj\simxi |
w(xi,xj)(f(xj)-f(xi)) =: (\Deltawf)(xi). \end{align}
Note that one has to assume that the graph
G
w(xi,xj)=w(xj,xi)
The continuous
p
Based on the first-order partial difference operators on graphs one can formally derive a family of weighted graph
p
\Deltaw,p\colonl{H}(V) → l{H}(V)
1\leqp<infty
p
E(f) :=
1 | |
p |
\sum | |
xi\inV |
\|\nablawf(xi, ⋅ )\|
p. | |
\ellp |
The necessary optimality conditions for a minimizer of the energy functional
E
p
(\Deltaw,pf)(xi) :=
\sum | |
xj\simxi |
w(xi,
| ||||
x | ||||
j) |
|f(xj)-
p-2 | |
f(x | |
i)| |
(f(xj)-f(xi)).
Note that the graph Laplace operator is a special case of the graph
p
p=2
(\Deltaw,2f)(xi) = (\Deltawf)(xi) =
\sum | |
xj\simxi |
w(xi,xj)(f(xj)-f(xi)).
Calculus on finite weighted graphs is used in a wide range of applications from different fields such as image processing, machine learning, and network analysis.A non-exhaustive list of tasks in which finite weighted graphs have been employed is:
1.Note that a slightly different definition of undirected graph is also in use, which considers an undirected edge to be a two-set (set with two distinct elements)
\{xi,xj\}
(xi,xj)
(xj,xi)
l{H}(E)
(xi,xj)
(xj,xi)