gnn_1

Graph Neural Network (1)

What is Graph

A Graph \(\mathcal{G} = (\mathcal{V}, \mathcal{E})\) is defined by a set of nodes \(\mathcal{V}\) and a set of edges \(\mathcal{E}\) between these nodes. We denote an edge going from node \(u \in \mathcal{V}\) to node \(v \in \mathcal{V}\) as \((u, v) \in \mathcal{E}\). A simple graph has at most one edge between each pair of nodes, no edges between a node and itself and the edges are all undirected (i.e., \((u, v) \in \mathcal{E} \longleftrightarrow (v, u) \in \mathcal{E}\)).

A convenient way to represent graphs is through an adjacency matrix \(\mathbf{A} \in \mathbb{R}^{|\mathcal{V}| \times |\mathcal{V}|}\). We can then represent the presence of edges as entries in this matrix: \(\mathbf{A}[u, v] = 1\) if \((u, v) \in \mathcal{E}\), \(0\) otherwise. If the graph contains only undirected edges then \(\mathbf{A}\) will be a symmetric matrix. Some graphs can also have weighted edges, where the entries in the adjacency matrix are arbitrary real-values rather than \(\{0, 1\}\).

Multi-relational Graphs

Beyond weighted, directed, undirected edges, we also consider graphs that have different types of edges. In this case, we can construct the edge notation to include an edge or relation type \(\tau\), that is \((u, \tau, v) \in \mathcal{E}\), and we can define one adjacency matrix \(\mathbf{A}_\tau\) per edge type. We call such graphs multi-relational. The entire graph can be summarized by an adjacency tensor \(\mathcal{A} \in \mathbb{R}^{|\mathcal{V}| \times |\mathcal{R}| \times |\mathcal{V}|}\) where \(\mathcal{R}\) is the set of relations. There are two important subsets of multi-relational graphs:

1. Heterogeneous graphs: In heterogeneous graphs, nodes also have types, that is we can partition the set of nodes into disjoint sets: \(\mathcal{V} = \mathcal{V}_1 \bigcup \mathcal{V}_2 \bigcup .... \bigcup \mathcal{V}_k\) where \(\mathcal{V}_i \bigcap \mathcal{V}_j = \emptyset, \quad \forall i \neq j\). Edges in heterogeneous graphs generally satisfy constraints according to the node types. For example, \((u, \tau_i, v) \in \mathcal{E} \implies u \in \mathcal{V}_j, \; v \in \mathcal{V}_k\), the edge of type \(\tau_i\) only connects nodes with type \(\mathcal{V}_i\) and \(\mathcal{V}_j\). Multipartite graphs are special case of heterogeneous graphs, where edges can only connect nodes that have different types, \((u, \tau_i, v) \in \mathcal{E} \implies u \in \mathcal{V}_j, v \in \mathcal{V}_k \cap j \neq k\).
2. Multiplex graphs: In multiplex graphs we assume the graphs can be decomposed into a set of \(k\) layers. Every node is assumed to belong to every layer, and each layer corresponds to a unique relation, representing the intra-layer edge type for that layer (edge relation between nodes in the same layer). We assume that inter-layer edges types can exist, which connect the same node across layers (edge relation between different layers of the same node).

Feature Information

There are also attribute or feature information associated with a graph. Most often are node-level attributes that we represent with a feature matrix \(\mathbf{X}^{|\mathcal{V}| \times m}\) (The order of nodes is consistent with the adjacency matrix).

REF

Graph Representation Learning By William L. Hamilton