I am reading a paper known as GIN, How powerful are graph neural networks?, Xu et al. 2019

The paper, Lemma 5 and Corollary 6, introduces Graph Isomorphism Network (GIN).

In Lemma 5,

Moreover, any multiset function $g$ can be decomposed as $g (X) = \phi(\sum_{x\in X} f(x))$ for some function $\phi$

Similarly, in Corollary 6,

Moreover, any function $g$ over such pairs can be decomposed as $g (c, X) = \varphi((1+\epsilon) f(c)+ \sum_{x\in X} f(x))$ for some function $\varphi$.

Finally, it makes MLP by compositing $f^{(k+1)}$ and $\varphi^{(k)}$. i.e

$f^{(k+1)} \varphi^{(k)}$

I know that $h(X)$ or $h(c,X)$ is injective, because they are unique to $c$ and $X$(in Lemma 5 and Corollary 6, respectively).

What I don't understand is: in the statements in Lemma 5 and Cor 6, $\phi$ and $\varphi$, I don't know whether they are injective or not.

My question is then: why is GIN powerful? i.e, Why does GIN preserve injectivity?

This paper explains that injectivity should be preserved to get powerful GNN. How can I answer this question?



You must log in to answer this question.