Graph Convolutional Network

Definition

Graph convolutional network (GCN) is a CNN operating on Graph-structured data which takes two inputs: node features $X$ and its Adjacency Matrix $A$. GCN learns hidden layer vectors that encode both node features and local graph structures on a fixed graph.

GCN Layer

The GCN layer Is a function of node feature and adjacency matrix. $H^{(l+1)}=\sigma (A{H}^{(l)}{W}^{(l)})$ where:

• $H^{(l)}$ is the node feature matrix at layer $l$, $H^{(0)}$ is the node features.
• $A\in \mathbb{R}$ is the Adjacency Matrix of the graph
• $W^{(l)}$ is the learnable weight matrix for layer $l$ It works similar to the filter in CNN with $F^{\prime }$ channel size. It is shared across all nodes and independent on the graph size.
• $\sigma$ is a non-linear Activation Function

Normalized GCN Layer

To increase numerical stability by enforcing self-loop, the Adjacency Matrix $A$ is transformed by adding an identity matrix and normalizing with the Degree Matrix $D$. $H^{(l+1)}=\sigma (D^{-\frac{1}{2}}\tilde{A}{D}^{-\frac{1}{2}}{H}^{(l)}{W}^{(l)})$ where $\tilde{A}=A+I$

GCN Layer With Self-Transform Term

In some scenario, the self transformation term is added to the GCN layer to help preserve node-specific information $H^{(l+1)}=\sigma (A{H}^{(l)}{W}^{(l)}+H^{(l)}{B}^{(l)})$ where $B^{(l)}$ is the learnable self-transformation matrix for layer $l$

GCN Layer With Skip Connection

The skip connection can ease over-smoothing problem. $H^{(l+1)}=\sigma (A{H}^{(l)}{W}^{(l)}+H^{(l)})$

Neighborhood-Based approach

$h_i^{(l+1)}=\sigma \left(W^{(l)}\cdot \mathrm{AGG}(\{h_j^{(l)}|v_j\in \mathcal{N}(v_i)\})\right)$ where $\mathcal{N}(v_i)$ is the neighbors of the node $v_i$.

The aggregation function $\mathrm{AGG}$ could be a mean, sum, or max operation:

• ${\mathrm{AGG}}^{\text{mean}}(\{h_j^{(l)}|v_j\in \mathcal{N}(v_i)\})=\sum _{v_j\in \mathcal{N}(v_i)}\frac{h_j^{(l)}}{|\mathcal{N}(v_i)|}$
• ${\mathrm{AGG}}^{\text{sum}}(\{h_j^{(l)}|v_j\in \mathcal{N}(v_i)\})=\sum _{v_j\in \mathcal{N}(v_i)}{h}_j^{(l)}$
• ${\mathrm{AGG}}^{\text{max}}(\{h_j^{(l)}|v_j\in \mathcal{N}(v_i)\})=\underset{v_j\in \mathcal{N}(v_i)}{\max }{h}_j^{(l)}$

Facts

The output of a GCN is permutation invariant: invariant to the ordering of nodes in the input graph. The output of each layer in a GCN is permutation equivalent: equivalent to the permutation of nodes in the input graph.