What is Graph?

A data structure consisting of two components: nodes(vertices) and edges
G = (V,E)
V: the set of nodes, E: the edges between them

Why Graph?

A graph can represent things like social media networks, or molecules(nodes → users // edges → connections)

How to represent Graph?

A graph is often represented by A, an adjacency matrix
A graph that has n nodes ⇒ A has a dimension of (n x n)
When the nodes have a set of features (e.g., a user profile), in this case, f number of features ⇒ The node feature matrix X has a dimension of (n x f)

Graph Neural Network (GNN)

What is GNN?

Graph Neural Networks
A class of deep learning methods designed to perform inference on data described by graphs

Why GNN? (Why CNNs fail on graphs?)

To handle complex graph data with conventional machine learning and deep learning tools
Conventional ML and DL tools are specialized in simple data types
E.g., images with the same structure and size ⇒ We can think of as fixed-size grid graphs
E.g., text and speech ⇒ We can think of them as line graphs(reference)

With GNN we can do

Node classification
Graph classification
Graph visualization
Link prediction
Graph clustering

Graph Convolutional Networks (GCN)

What is GCN?

First introduced in “Spectral Networks and Deep Locally Connected Networks on Graphs” (Bruna et al, 2014)
A method for applying neural networks to graph-structured data
The core concept behind CNNs:
Hidden convolution and pooling layers to identify spatially localized features via a set of receptive fields in kernel form
This leads to a problem that:
Convolution takes a little sub-patch of the image (a little rectangular part of the image), applies a function to it, and produces a new part (a new pixel)

Why GCN?

It is difficult to perform CNN on graphs because of
The arbitrary size of the graph and the complex topology (which means there is no spatial locality)
There is unfixed node ordering (Graphs are invariant to node ordering, so we want to get the same result regardless of how we order the nodes)
⇒ A method for applying neural networks to graph-structured data is required

How to represent a graph in GCN?

G = (A, X)
⇒ An adjacency matrix which represents the links between each node
⇒ Node Node feature matrix (N: # of node in a graph, d: # of node features → dimension of node feature vector)

Structure of GCN

Graph convolution layer & fully connected layer
GCN consists of
Graph Convolution
Linear layer
Nonlinear activation


What is GraphSAGE?

First introduced in Hamilton et al., NIPS 2017
A representation learning technique for dynamic graphs
A framework for inductive representation learning on large graphs

Why GraphSAGE?

Low-dimensional vector embeddings of nodes in large graphs have numerous applications in ML (e.g., node classification, clustering, link prediction, etc.)
However, most embedding frameworks are 1) inherently transductive, and 2) can only generate embeddings for a single fixed graph
These transductive approaches 1) do not efficiently generalize to unseen nodes (e.g., in evolving graphs), and 2) cannot learn to generalize across different graphs
⇒ GraphSAGE is an inductive framework that leverages node attribute information to efficiently generate representations on previously unseen data
⇒ GraphSAGE can predict the embedding of a new node, without a re-training procedure(reference)

What’s different in GraphSAGE?

GraphSAGE is useful for graphs that have rich node attribute information (Why?)

Graph Attention Network (GAT)

What is GAT?

First introduced in (Velickovic et al., ICLR 2018)

Why GAT?