A Gentle Introduction to Graph Neural Networks
2 minute read ∼ Filed in : A paper notehttps://distill.pub/2021/gnn-intro/
Introduction
Usage
GNN can be used in fake news detection, traffic prediction, and recommendation systems, physics simulations.
Contributions
The paper mainly introduces 3 parts
- What kinds of data are most naturally phrased as a graph.
- What makes graphs different from other types of data.
- GNN models architecture.
Graph
V Node, E Edge, U Global.
data as Graphs
Img to graph
Each pixel in the image can be a node, and connect to other nodes via an edge.
Text to graph
Social network to Graph
Problems in Graph data
Node classification, link prediction, and clustering.
graph level
Predict which graph has a specific property. Graph classification
Node-level
Predict which party the node belongs to.
Edge-level
Find the relation between two nodes.
ML for Graph
Represent graph to be compatible with NN.
- The graph has nodes, edges, global context, and connectivity.
- Different forms of graphs must be recognized as the same inputs.
GNN
-
A GNN is an optimizable transformation on all attributes of the graph (nodes, edges, global context) that preserves graph symmetries (permutation invariances)
- Build with Message passing
- Adopt a graph as input, and produce an output graph. The connectivity of the input graph will not be changed.
In prediction, apply a linear classifier to each node. All nodes will share the weight of the classifier.
Pooling
If a node has no embedding, we could generate an embedding for it by adding all edge’s embeddings around it.
We cloud also add node’s embeddings to generate embeddings of one edge.
Passing message
SImple GNN only considers the information of nodes and edges separately.
“Passing message” can take the information of connectivity into consideration.
-
Edges to nodes
-
nodes to edges
Global representations. U
Add a master node or virtual node, which connects all nodes and edges.
Performance
Passing message in the whole graph has the best AUC.
Problems
- GNN/GCN has a large network, and it’s hard to optimize the computation. As a result, it’s hard to compute in CPU/GPU.
- GNN/GCN is sensitive to hyperparameters, sample methods etc.