5 Graph Neural Networks

5.1 Concept of Graph Neural Network (GNN)

      As a start, in this section we present a brief overview of the and then in the subsequent sections discuss some of the most popular variants in more detail.

      The basic idea here is to extend existing neural networks for the purpose of processing the data represented in graph domains [1]. In a graph, each node is defined by its own features and the features of the related nodes. The target of GNN is to learn a state embedding h_v ∈ ℝ^s that contains information on the neighborhood for each node. The state embedding h_v is an s‐dimension vector of node v and can be used to produce an output o_v . Let f be a parametric function, called the local transition function, that is shared among all nodes and updates the node state according to the input neighborhood. Let g be the local output function that describes how the output is produced. Then, h_v and o_v are defined as

(5.1)

      where x_v, x_co[v], h_ne[v], and x_ne[v] are the features of v, the features of its edges, the states, and the features of the nodes in the neighborhood of v, respectively. If H, O, X, and X_N are the vectors constructed by stacking all the states, all the outputs, all the features, and all the node features, respectively, then we can write

(5.2)

In Eq. (5.2), F, the global transition function, and G, the global output function, are stacked versions of f and g for all nodes in a graph, respectively. The value of H is the fixed point of Eq. (5.2) and is uniquely defined with the assumption that F is a contraction map. GNN uses the following iterative scheme for computing the state (Banach’s fixed‐point theorem [2])

(5.3)

where H^t denotes the t‐th iteration of H. The dynamical system (Eq. (5.3)) converges exponentially fast to the solution of Eq. (5.2) for any initial value H(0) . Note that the computations described in f and g can be interpreted as feedforward neural networks (). Given the framework of GNN, how do we learn the parameters of f and g? With the target information (t_v for a specific node) for the supervision, the loss can be written as follows:

      (5.4)

where p is the number of supervised nodes. The learning algorithm is based on a gradient‐descent strategy and is composed of the following steps:

      1 The states are iteratively updated by Eq. (5.1) until a time T.They approach the fixed‐point solution of Eq. (5.2) H(T)≈ H.

      2 The gradient of weights W is computed from the loss.

      3 The weights W are updated according to the gradient computed in the last step.

      5.1.1 Classification of Graphs

      Directed graphs: Directed edges can yield more information than undirected edges. For example, in a knowledge graph where the edge starts from the head entity and ends at the tail entity, the head entity is the parent class of the tail entity, which suggests we should treat the information propagation process from parent classes and child classes differently. Here, we use two kinds of weight matrix, W_p and W_c , to incorporate more precise structural information. The propagation rule is [3]

      (5.5)

      where are the normalized adjacency matrix for parents and children, respectively, and σ denotes a nonlinear activation function.

      Heterogeneous graphs: These have several kinds of nodes. The simplest way to process heterogeneous graphs is to convert the type of each node to a one‐hot feature vector that is concatenated with the original feature. GraphInception [4] introduces the concept of metapath into propagation on the heterogeneous graph. With metapath, we can group neighbors according to their node types and distances. For each neighbor group, GraphInception treats it as a subgraph in a homogeneous graph to perform propagation and concatenates the propagation results from different homogeneous graphs to arrive at a collective node representation. In [5], the heterogeneous graph attention network (HAN) was proposed, which utilizes node‐level and semantic‐level attention. The model has the ability to consider node importance and meta‐paths simultaneously.

      Graphs with edge information: Here, each edge has additional information like the weight or the type of the edge. There are two ways to handle this kind of graph: