by selecting from y the components related to the node (the edges) in S.
For example, lne[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
where ni, j ∈ Ni denotes the j‐th node in the set
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 xn ∈ Rs to each node n that is based on the information contained in the neighborhood of n (see Figure 5.9). The state xn 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 fw be a parametric function, called the local transition function, that expresses the dependence of a node n on its neighborhood, and let gw be the local output function that describes how the output is produced. Then, xn and on are defined as follows:
where ln, lco[n], xne[n] , and lne[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 lN 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
where Fw , the global transition function, and Gw , the global output function, are stacked versions of ∣N∣ instances of fw and gw , respectively. For us, the case of interest is when x, o are uniquely defined and Eq. (5.75) defines a map ϕw :
Figure 5.8 A subset of the Web.
Figure 5.9 Graph and the neighborhood of a node. The state x1 of node 1 depends on the information contained in its neighborhood.
Source: Scarselli et al. [1].
For positional graphs, fw must receive the positions of the neighbors as additional inputs. In practice, this can be easily achieved provided that information contained in xne[n], lco[n] , and lne[n] is sorted according to neighbors’ positions and is appropriately padded with special null values in positions corresponding to nonexistent neighbors. For example, xne[n] = [y1, …, yM], where M = maxn, u vn(u) is the maximum number of neighbors of a node; yi = xu holds, if u is the i‐th neighbor of n(νn(u) = i); and yi = x0 , for some predefined null state x0 , if there is no i‐th neighbor.
For nonpositional graphs, it is useful to replace function fw of Eq.