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$ )
^statement

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_{ℓ} = CONCAT (readout ({(x_{ℓ})_{v} : v \in V}) | ℓ = 1, 2, \dots, L)

Demonstration

Can a GIN tell them apart? We assume $W_{0} = 1, ε_{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

File
2025-03-03 graphs lecture 11