2
$\begingroup$

This might be moreof a question about nested function classes:

For k class node classification in a graph with n nodes, and d feature vector. I want to compare

Architecture I: the GCN model of Kipf/ Welling with two graph convolutional layers: $$ \mathbf{Y}=\operatorname{softmax}\left(\mathbf{A} \xi\left(\mathbf{A X W}_{1}\right) \mathbf{W}_{2}\right) $$

where $\mathbf{X}$ is $n \times d,$ $\mathbf{Y}$ is $n \times k, \mathbf{A}$ is a fixed $n \times n$ graph diffusion matrix, and $\mathbf{W}_{1}, \mathbf{W}_{2}$ are learnable weight matrices of size $d \times d^{\prime}$ and $d^{\prime} \times 2,$ respectively, shared across all nodes, and $\xi$ is a nonlinearity.

Architecture II: a single-layer graph neural network of the form: $$ \mathbf{Y}=\operatorname{softmax}\left(\mathbf{A}^{2} \mathbf{X W}\right) $$ where $\mathbf{W}$ is a learnable weight matrix of size $d \times 2$.


Now I'm wondering

  • $\operatorname{Can} \xi, d^{\prime}$ be chosen in a way that both architectures have the same expressive power? (i.e. can represent the same class of functions)?

  • $\operatorname{Can} \xi, d^{\prime}$ be chosen in a way that Architecture II is more expressive?

  • What would be the advantage in training complexity of Architecture II when applied to large-scale graphs.

$\endgroup$
1
  • $\begingroup$ Could you please focus on 1 specific question (eventually, you can add 1-2 more sub-questions, provided they are sub-questions and not distinct questions)? Then could you please put that specific question in the title? To me, it seems that your questions are quite distinct (and a bit broad) and require a lot of effort to answer properly. So, I actually suggest that you focus on 1 of those questions and remove the others. If you have more questions, ask them in other separate posts. $\endgroup$
    – nbro
    Jan 12 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.