Graph Isomorphism Network

[[concept]]

Graph isomorphism network

A graph isomorphism network (GIN) layer is defined as $(x_{\ell }{)}_v=\sigma \left(W_{\ell }\left((1+{\epsilon }_{\ell })(x_{\ell -1}{)}_v+{\sum }_{u\in N(v)}(x_{\ell -1}{)}_u\right)\right)$ We can write this layer in terms of concatenate function $\phi$: $\phi (\{(x_{\ell -1}{)}_u:u\in N(v)\})={\sum }_{u\in N(v)}(x_{\ell -1}{)}_u$ And aggregate function $\varphi$ $\varphi ((x_{\ell -1}{)}_v,\phi (\cdot ))=W_{\ell }((1+{\epsilon }_{\ell })(x_{\ell -1}{)}_v+\phi (\cdot ))$ The motivation for this architecture comes from the fact that injective GNNs are as powerful as the WL test, which holds in this case as long as $\varphi ,\phi$ as defined above are injective.

notes

${\varphi }_{\ell }\circ \sum {\phi }_{\ell -1}$ is a perceptron or MLP over the neighborhood multiset

• Hornik 1989 says an MLP can model any injective function - this is due to the universal approximation theorem
• Injective ${\varphi }_{\ell }\circ {\sum }_X{\varphi }_{\ell -1}$ exist for multiset $X$ (proven in paper where GINs are introduced)

---

Review

dsg

What is the motivation for the Graph Isomorphism Network (GIN) architecture? -?- Injective GNNs are as powerful as the WL test, and we can define the update for GINs to be injective.

Mentions

TABLE
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link), 1, "") + choice(contains(author, this.file.link), 1, "") + choice(contains(director, this.file.link), 1, "") + choice(contains(source, this.file.link), 1, "") as direct_source
 
WHERE !direct_source