LITMIR.BIZ

Скачать книгу

by selecting from y the components related to the node (the edges) in S.

      For example, l_ne[n] stands for the vector containing the labels of all the neighbors of n. Labels usually include features of objects related to nodes and features of the relationships between the objects. No assumption is made regarding the arcs: directed and undirected edges are both permitted. However, when different kinds of edges coexist in the same dataset, it is necessary to distinguish them. This can be easily achieved by attaching a proper label to each edge. In this case, different kinds of arcs turn out to be just arcs with different labels.

      The considered graphs may be either positional or nonpositional. Nonpositional graphs are those that have been described thus far; positional graphs differ from them since a unique integer identifier is assigned to each neighbor of a node n to indicate its logical position. Formally, for each node n in a positional graph, there exists an injective function ν_n : ne[n] → {1, …, ∣ N∣}, which assigns to each neighbor u of n a position ν_n(u).

      The domain is the set of pairs of a graph and a node, that is, , where is a set of the graphs and is a subset of their nodes. We assume a supervised learning framework with the learning set

(5.73)

where n_{i, j} ∈ N_i denotes the j‐th node in the set and t_{i, j} is the desired target associated with n_{i, j} . Finally, and q_i ≤ ∣ N_i∣. All the graphs of the learning set can be combined into a unique disconnected graph, and therefore one might think of the learning set as the pair , where G = (N, E) is a graph and is a set of pairs {(n_i, t_i) ∣ n_i ∈ N, t_i ∈ R^m, 1 ≤ i ≤ q}. It is worth mentioning that this compact definition is useful not only for its simplicity, but that it also directly captures the very nature of some problems where the domain consists of only one graph, for instance, a large portion of the Web (see Figure 5.8).

The model: As before, the nodes in a graph represent objects or concepts, and edges represent their relationships. Each concept is naturally defined by its features and the related concepts. Thus, we can attach a state x_n ∈ R^s to each node n that is based on the information contained in the neighborhood of n (see Figure 5.9). The state x_n contains a representation of the concept denoted by n and can be used to produce an output o, that is, a decision about the concept. Let f_w be a parametric function, called the local transition function, that expresses the dependence of a node n on its neighborhood, and let g_w be the local output function that describes how the output is produced. Then, x_n and o_n are defined as follows:

(5.74)

      where l_n, l_co[n], x_ne[n] , and l_ne[n] are the label of n, the labels of its edges, the states, and the labels of the nodes in the neighborhood of n, respectively.

Let x, o, l and l_N be the vectors constructed by stacking all the states, all the outputs, all the labels, and all the node labels, respectively. Then, a compact form of Eq. (5.74) becomes

(5.75)

where F_w , the global transition function, and G_w , the global output function, are stacked versions of ∣N∣ instances of f_w and g_w , respectively. For us, the case of interest is when x, o are uniquely defined and Eq. (5.75) defines a map ϕ_w : that takes a graph as input and returns an output o_n for each node. Banach’s fixed‐point theorem [62] provides a sufficient condition for the existence and uniqueness of the solution of a system of equations. According to Banach’s theorem, Eq. (5.75) has a unique solution provided that F_w is a contraction map with respect to the state; that is, there exists μ, 0 ≤ μ < 1 such that ‖F_w(x, l) − F_w(y, l)‖ ≤ μ‖x − y‖ holds for any x, y, where ‖ . ‖ denotes a vectorial norm. Thus, for the moment, let us assume that F_w is a contraction map. Later, we will show that, in GNNs, this property is enforced by an appropriate implementation of the transition function.

Figure 5.8 A subset of the Web.

Figure 5.9 Graph and the neighborhood of a node. The state x₁ of node 1 depends on the information contained in its neighborhood.

      Source: Scarselli et al. [1].

      For positional graphs, f_w must receive the positions of the neighbors as additional inputs. In practice, this can be easily achieved provided that information contained in x_ne[n], l_co[n] , and l_ne[n] is sorted according to neighbors’ positions and is appropriately padded with special null values in positions corresponding to nonexistent neighbors. For example, x_ne[n] = [y₁, …, y_M], where M = max_{n, u} v_n(u) is the maximum number of neighbors of a node; y_i = x_u holds, if u is the i‐th neighbor of n(ν_n(u) = i); and y_i = x₀ , for some predefined null state x₀ , if there is no i‐th neighbor.

      For nonpositional graphs, it is useful to replace function f_w of Eq.

Скачать книгу