Calculus on finite weighted graphs
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. Basic definitions. A finite weighted graph formula_1 is defined as a triple formula_2 for which In a directed graph, each edge formula_6 has a start node formula_7 and an end node formula_8. In an undirected graph for every edge formula_9 there exists an edge formula_10 and the weight function is required to be symmetric, i.e., formula_11. 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" formula_12 associates to every edge formula_13 a real value formula_14. 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 formula_15 is considered (with the resulting function still being called the "edge weight function") by setting  formula_16 whenever formula_17. In applications each "graph vertex" formula_18 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., formula_19. 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 formula_20 (which would be nonzero in the presence of self-loops) appears in the presence of another factor which disappears when formula_21 (see the section on differential graph operators below), and edge weights can encode similar information as multiple edges could. Neighborhood. A node formula_22 is a neighbor of the node formula_23 if there exists an edge formula_13. In  terms of notation this relationship can be abbreviated by formula_25, which should be read as "formula_26 is a neighbor of formula_27". Otherwise, if formula_26 is not a neighbor of formula_27 one writes formula_30. The neighborhood formula_31 of a vertex formula_23 is simply the set of neighbors formula_33. The degree of a vertex formula_23 is the weighted size of its neighborhood: Note that in the special case where formula_36 on formula_37 (i.e. the graph is unweighted) we have formula_38. Space of real vertex functions. Let formula_39 be the space of (real) vertex functions. Since formula_40 is a finite set, any vertex  function formula_41 can be represented as a formula_42-dimensional vector formula_43 (where formula_44) and hence the space of vertex functions formula_45 can be identified with an formula_42-dimensional Hilbert space: formula_47. The inner product of formula_45 is defined as: Furthermore, for any vertex function formula_50 the formula_51-norm and formula_52-norm of formula_53 are defined as: The formula_55-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 formula_56. As any edge function formula_57 is defined on a finite set of edges formula_37, it can be represented as a formula_59-dimensional vector formula_60, where formula_61. Hence, the space of edge functions formula_62 can be identified as a formula_59-dimensional Hilbert space, i.e., formula_64. One special case of an edge function is the "normalized edge weight function" formula_65 introduced above in the section on basic definitions. Similar to that function, any edge function formula_57 can be  trivially extended to formula_67 by setting formula_68 if formula_69. The space of those extended edge functions is still denoted by formula_62 and can be identified with formula_71, where now formula_72. The inner product of formula_62 is defined as: Additionally, for any edge function formula_75 the formula_51-norm and formula_52-norm of formula_57 are defined as: The formula_55-norm is induced by the inner product. If one extends the edge set formula_37 in a way such that formula_82 than it becomes clear that formula_83 because formula_47. This means that each edge function can be identified with a linear matrix operator. Differential  graph operators. 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. First-order differential operators . Weighted differences. Let formula_85 be a finite weighted graph and let formula_41 be a vertex function. Then the weighted difference (or weighted graph derivative) of formula_53 along a directed edge formula_13 is For any weighted difference the following properties hold: Weighted gradient. Based on the notion of weighted differences one defines the weighted gradient operator on graphs formula_93 as This is a linear operator. To measure the "local variation" of a vertex function formula_53 in a vertex formula_23 one can restrict the gradient formula_97 of formula_53 to all directed edges starting in formula_27 and using the formula_51-norm of this  edge function, i.e., Weighted divergence. The adjoint operator formula_102 of the weighted gradient operator is a linear operator defined by For undirected graphs with a symmetric weight function formula_104 the adjoint operator formula_105 of a function formula_106 at a vertex formula_7 has the following form: One can then define the weighted divergence operator on graphs via the adjoint operator as formula_109. The divergence on a graph measures the net outflow of an edge function in each vertex of the graph. Second-order differential operators. Graph Laplace operator. The weighted graph Laplacian formula_110 is a well-studied operator in the graph  setting. Mimicking the relationship formula_111 of the Laplace operator in the continuum setting, the weighted graph Laplacian can be derived for any vertex formula_23 as: Note that one has to assume that the graph formula_1 is undirected and has a symmetric weight function formula_115 for this representation. Graph p-Laplace operators. The continuous formula_116-Laplace operator is a second-order differential operator that can be well-translated to finite weighted graphs. It allows the translation of various partial differential equations, e.g., the heat equation, to the graph setting. Based on the first-order partial difference operators on graphs one can  formally derive a family of weighted graph formula_116-Laplace operators formula_118 for formula_119 by minimization of the discrete formula_116-Dirichlet energy functional The necessary optimality conditions for a minimizer of the energy functional formula_37 lead to the following definition of the graph formula_116-Laplacian: Note that the graph Laplace operator is a special case of the graph formula_116-Laplace operator for formula_126, i.e., Applications. 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: