MPNNs can be expressed as graph convolutions

[[concept]]

Idea

Consider an MPNN. As long as $M_{\ell }$ is linear, the “message” can be expressed as a graph convolution.

Example

M_{\ell}[(x_{\ell})_{i}, (x_{\ell})_{j}, A_{ij}] &= \alpha \cdot(x_{\ell})_{i} + \beta \cdot A_{ij}(x_{\ell})_{j}\\ \implies m_{\ell} &= \alpha x_{\ell} + \beta Ax_{\ell} \end{aligned}$$

which is a graph convolution with $K=2,S=A,h_0=\alpha ,h_1=\beta$

As long as $U_{\ell }$ is the composition of a pointwise nonlinearity $\sigma$ with a linear function $M_{\ell }$, then $x_{\ell }$ can be expressed as a GNN layer

Example

\implies x_{\ell+1} &= \sigma([\alpha’+\beta’\alpha]x_{\ell} + \beta’\beta A x_{\ell}) \end{aligned}$$

Which is a graph convolution with $K=2,S=A,h_0={\alpha }^{\prime }+{\beta }^{\prime }\alpha ,h_1={\beta }^{\prime }\beta$

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