Graph Convolutional Networks (GCN)
Given an input graph network G, where V is the vertex set, A is the adjacency matrix, X is a matrix of node features. Also, v : a node in V, N(v) : the set of neighbors of v.
Objective
To learn the node embeddings such that similarity in the embedding space approximates similarity in the network.
Key Components
Encoder - map a node to a d-dimensional vector : ENC(v) = Zv
Similarity Function - defines how relationships in the input network map to relationships in the embedding space : similarity(u,v) ~ transpose(Zv).Zu
Embedding Matrix and Shallow Encoding
Encoder is just an embedding-lookup.
Limitations of shallow encoding
Need O(|V|) parameters since there is no sharing of parameters between nodes
Inherently transductive i.e., can not generate embeddings for nodes that are not seen during training
Do not incorporate node features
From Images to Graphs
Single Convolutional Neural Network (CNN) layer with 3x3 filter :
Graph Convolutional Network
Generates node embeddings based on local network neighborhood
Nodes aggregate information from their neighbors using neural networks
Network neighborhood defines the computation graph
Training
Average neighbor messages and apply a neural network
Model Parameters
We can feed these embeddings into any loss function and run stochastic gradient descent to train the weight parameters.