Lec 09 Theory
1. how a GNN captures local neighborhood structures ?
(1) GNN captures local neighborhood structures by computational graph
(2) The key point of GNN expression is the aggregation function. In other word, most expressive GNN would use an injective function at each step.
2. Most Powerful GNN : GIN
Observation : Neighbor aggregation can be abstracted as a function over a multi-set
Problem of GCN and GraphSAGE
can’t distinguish different multi-sets
Injective Multi-Set Function
General injective multi-set function formulation
$$
\Phi(\sum_{x\in S}f(x))
$$
where $f(x)$ produces one-hot encodings of colors.
Universal Approximation Theorem
1-hidden layer MLP with sufficiency-large hidden dimensionality and appropriate non-linearity can approximate any continuous function to an arbitrary accuracy
Graph Isomorphism Network
$$
MLP_{\Phi}(\sum_{x\in S}MLP_f(x))
$$
GIN is the most expressive GNN in the class of message-passing GNNs.
3. Full Model of GIN
General injective function over tuple formulation
$$
MLP_{\Phi}((1+\epsilon)\cdot MLP_f(c^{(k)}(v))+\sum_{u\in N(v)}MLP_f(c^{(k)}(u)))
$$
where $\epsilon$ is learn-able scalar
GIN’s node updates
assign an initial vector $c^{(0)}(v)$ to each node $v$
Iteratively update node vectors by
$$
c^{(k+1)}(v) = GINCONV({c^{(k)}(v),{c^{(k)}(u)}_{u\in N(v)}})
$$
where GINConv maps different inputs to different embeddings.after K steps, $c^{(k)}(k)$ summarizes the structure of K-hop neighborhood
Improve GNN’s Power
There are basic graph structures that existing GNN framework cannot distinguish, such as difference in cycles.