Preliminaries
Graph
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
GraphSAGE
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)
