where y δ = ∣ ne[n] ∣ · z′(t), and is a vector that stores in the position corresponding to i, j, that is, . Thus, in linear GNNs, d is computed by calling the backpropagation procedure on each arc and node.

Time complexity of the GNN model: Formally, the complexity is easily derived from Table 5.2: it is for positional GNNs, for nonlinear GNNs, and for linear GNNs. In practice, the cost of the test phase is mainly due to the repeated computation of the state x (t). The cost of each iteration is linear with respect to both the dimension of the input graph (the number of edges) and the dimension of the employed FNNs and the state, with the sole exception of linear GNNs, whose single iteration cost is quadratic with respect to the state. The number of iterations required for the convergence of the state depends on the problem at hand, but Banach’s theorem ensures that the convergence is exponentially fast, and experiments have shown that 5–15 iterations are generally sufficient to approximate the fixed point [1].

      In positional and nonlinear GNNs, the transition function must be activated it_f · ∣ N∣ and it_f · ∣ E∣ times, respectively. Even if such a difference may appear significant, in practice, the complexity of the two models is similar, because the network that implements the f_w is larger than the one that implements h_w . In fact, f_w has M(s + l_E) input neurons, where M is the maximum number of neighbors for a node, whereas h_w has only s +l_E input neurons. A significant difference can be noticed only for graphs where the number of neighbors of nodes is highly variable, since the inputs of f_w must be sufficient to accommodate the maximum number of neighbors, and many inputs may remain unused when f_w is applied. On the other hand, it is observed that in the linear model the FNNs are used only once for each iteration, so that the complexity of each iteration is O(s² ∣ E∣) instead of . Note that holds, when h_w is implemented by a three‐layered FNN with hi_h hidden neurons. In practical cases, where hi_h is often larger than s, the linear model is faster than the nonlinear model. As confirmed by the experiments, such an advantage is mitigated by the smaller accuracy that the model usually achieves.

In GNNs, the learning phase requires much more time than the test phase, mainly due to the repetition of the forward and backward phases for several epochs. The experiments have shown that the time spent in the forward and backward phases is not very different. Similarly, to the forward phase, the cost of the function BACKWARD is mainly due to the repetition of the instruction that computes z(t). Theorem 5.2 ensures that z(t) converges exponentially fast, and experiments have confirmed that it_b is usually a small number.

      Formally, the cost of each learning epoch is given by the sum of all the instructions times the iterations in Table 5.2. An inspection of the table shows that the cost of all instructions involved in the learning phase are linear with respect to both the dimension of the input graph and of the FNNs. The only exceptions are due to the computation of z(t + 1) = z(t) · A + b, (∂F_w/∂x)(x, l) and ∂p_w/w, which depend quadratically on s.

      The most expensive instruction is apparently the computation of ∂p_w/w in nonlinear GNNs, which costs O On the other hand, the experiments have shown [1] that t_R is usually a small number. In most epochs, t_R is 0, since the Jacobian does not violate the imposed constraint, and in the other cases, t_R is usually in the range 1–5. Thus, for a small state dimension s, the computation of ∂p_w/w requires few applications of backpropagation on h and has a small impact on the global complexity of the learning process. On the other hand, in theory, if s is very large, it might happen that and at the same time t_R ≫ 0, causing the computation of the gradient to be very slow.

Appendix 5.A Notes on Graph Laplacian

      Let G = (V, E) be an undirected graph with vertex set V = {v₁, …, v_n}. In the following, we assume that the graph G is weighted, that is, each edge between two vertices v_i and v_j carries a non‐negative weight w_ij ≥ 0. The weighted adjacency matrix of the graph is the matrix W = (w_ij)_{i, j = 1, …, n} . If w_ij = 0, this means that the vertices v_i and v_j are not connected by an edge. As G is undirected, we require w_ij = w_ji . The degree of a vertex v_i ∈ V is defined as