GINs are maximally powerful for anonymous input graphs

[[concept]]

Takeaway

A GIN is a maximally powerful GNN in graph-level tasksfor anonymous inputs (ie $\vec{x}=1$ )

As long as we have an injective function from multisets to embeddings, we are able to distinguish between multisets.

We can then look at the graph level readout. In the original paper, this is defined at each layer as $Y_{\ell }=\text{CONCAT}(\text{readout}(\{(x_{\ell }{)}_v:v\in V\})|\ell =1,2,\dots ,L)$

Demonstration

Can a GIN tell them apart? We assume $W_0=1,{\epsilon }_0=0$. At the first layer, we take the sum of each node’s neighbors’ embedding and add it to the node’s embedding.

$j=1$ $G_1$

• $x_1=1+1=2$
• $x_2=1+1+1=3$
• $x_3=2$
• output is $\{2,3,2\}$
• readout is $[3|7]$

$G_2$ $x_1=x_2=x_3=3$

• output is $\{3,3,3\}$

• readout is $[3|9]$

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