A
finite weighted graph G is defined as a triple G = (V, E, w) for which • V = \{x_1, \dots, x_n\}, n\in\mathbb{N}, is a finite set of indices denoted as
graph vertices or
nodes, • E \subset V \times V is a finite set of (directed)
graph edges connecting a subset of vertices, • w \colon E \rightarrow \mathbb{R} is an
edge weight function defined on the edges of the graph. In a
directed graph, each edge (x_i,x_j)\in E has a
start node x_i\in V and an
end node x_j\in V. In an
undirected graph for every edge (x_i,x_j) there exists an edge (x_j,x_i) and the weight function is required to be symmetric, i.e., w(x_i,x_j) = w(x_j,x_i). On the remainder of this page, the graphs will be assumed to be undirected, unless specifically stated otherwise. Many of the ideas presented on this page can be generalized to directed graphs. The
edge weight function w associates to every edge (x_i,x_j) \in E a real value w(x_i,x_j) > 0. For both mathematical and application specific reasons, the weight function on the edges is often required to be strictly positive and on this page it will be assumed to be so unless specifically stated otherwise. Generalizations of many of the ideas presented on this page to include negatively weighted edges are possible. Sometimes an extension of the domain of the edge weight function to V\times V is considered (with the resulting function still being called the
edge weight function) by setting w(x_i,x_j)=0 whenever (x_i,x_j) \not\in E. In applications each
graph vertex x \in V usually represents a single entity in the given data, e.g., elements of a finite data set, pixels in an image, or users in a social network. A
graph edge represents a relationship between two entities, e.g. pairwise interactions or similarity based on comparisons of geometric neighborhoods (for example of pixels in images) or of another feature, with the edge weight encoding the strength of this relationship. Most commonly used weight functions are normalized to map to values between 0 and 1, i.e., w : E \rightarrow (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(x_i,x_i) (which would be nonzero in the presence of self-loops) appears in the presence of another factor which disappears when i=j (see
the section on differential graph operators below), and edge weights can encode similar information as multiple edges could.
Neighborhood A node x_j \in V is a
neighbor of the node x_i \in V if there exists an edge (x_i,x_j) \in E. In terms of notation this relationship can be abbreviated by x_j \sim x_i, which should be read as "x_j is a neighbor of x_i". Otherwise, if x_j is not a neighbor of x_i one writes x_j\not\sim x_i. The
neighborhood \mathcal N(x_i) of a vertex x_i \in V is simply the set of neighbors \mathcal{N}(x_i) := \{ x_j\in V \colon x_j \sim x_i \}. The
degree of a vertex x_i \in V is the weighted size of its neighborhood: : \deg(x_i) := \sum_{j\,:\,x_j \sim x_i} w(x_i,x_j). Note that in the special case where w\equiv 1 on E (i.e. the graph is
unweighted) we have \deg(x_i) := |\mathcal{N}(x_i)|.
Space of real vertex functions Let \mathcal{H}(V) := \{f : V \rightarrow \mathbb{R} \} be the
space of (real) vertex functions. Since V is a finite set, any vertex function f\in \mathcal{H}(V) can be represented as a n-dimensional vector f \in \mathbb{R}^n (where n:= |V|) and hence the space of vertex functions \mathcal{H}(V) can be identified with an n-dimensional
Hilbert space: \mathcal{H}(V) \cong \mathbb{R}^n. The inner product of \mathcal{H}(V) is defined as: : \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 f \in \mathcal{H}(V) the \ell_p-norm and \ell_\infty-norm of f are defined as: : \|f\|_p = \begin{cases} \left( \sum_{x_i\in V} |f(x_i)|^p \right)^\frac{1}{p}, &\text{ for } 1 \leqslant p The \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.
Space of real edge functions Analogously to real vertex functions, one can introduce the
space of real edge functions \mathcal{H}(E) := \{F:E \rightarrow \mathbb{R} \}. As any edge function F is defined on a finite set of edges E, it can be represented as a m-dimensional vector F \in \mathbb{R}^{m}, where m := |E|. Hence, the space of edge functions \mathcal{H}(E) can be identified as a m-dimensional Hilbert space, i.e., \mathcal{H}(E) \cong \mathbb{R}^{m}. One special case of an edge function is the
normalized edge weight function w \colon E \rightarrow (0, 1] introduced above in the
section on basic definitions. Similar to that function, any edge function F can be trivially extended to V \times V by setting F(x_i, x_j) := 0 if (x_i, x_j) \not\in E. The space of those extended edge functions is still denoted by \mathcal{H}(E) and can be identified with \mathbb{R}^m, where now m := |V|^2. The inner product of \mathcal{H}(E) is defined as: : \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 F \in \mathcal{H}(V) the \ell_p-norm and \ell_\infty-norm of F are defined as: : \|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 The \ell_2-norm is induced by the inner product. If one extends the edge set E in a way such that E = V \times V than it becomes clear that \mathcal{H}(E) \cong \mathbb{R}^{n \times n} because \mathcal{H}(V) \cong \mathbb{R}^n. This means that each edge function can be identified with a linear matrix operator. == Differential graph operators ==