Certainly! We provide such a comparison below. We will elaborate upon this point in the revised manuscript; thank you for the question!
For a two-dimensional grid graph with $N$ vertices, a message-passing GNN can be viewed as a CNN. Given $I \\subseteq [N]$, recall that $C_I$ denotes the boundary of the partition induced by $I$, i.e. the set of vertices with an edge crossing the partition. The $L - 1$ walk index of $I$ in the grid graph satisfies $| C_I | \\cdot 3^{L - 1} \\leq WI_{L - 1} (I) \\leq |C_I| \\cdot 5^{L - 1}$ (this is because each vertex has degree $5$ including self-loops, except those on the edge or corner of the grid which are of degree $3$ or $4$ respectively). Hence, Theorem 1 implies that the separation rank of the analyzed GNN with respect to $I$ is at most $D_h^{O (|C_I| \cdot 5^{L - 1})}$, where $D_h$ is the network’s width.
Similarly, for a chain graph with $N$ vertices, a message-passing GNN can be viewed as a bidirectional RNN. Given a partition induced by $I \\subseteq [N]$, the $L - 1$ walk index of $I$ in the chain graph satisfies $| C_I | \\cdot 2^{L - 1} \\leq WI_{L - 1} (I) \\leq |C_I| \\cdot 3^{L - 1}$ (this is because each vertex has degree $3$ including self-loops, except those on the endpoints which are of degree $2$). Thus, Theorem 1 implies that the separation rank of the analyzed GNN with respect to $I$ is at most $D_h^{O( |C_I| \cdot 3^{L - 1} )}$.
The above results — special cases of our theory — extend those of [1,2,3,4], which study the separation rank of certain CNNs and RNNs. In particular, the results extend the CNN framework of [1,2] by introducing overlaps to convolution windows,$^\dagger$ and the RNN framework of [3,4] by introducing bidirectionality. Given that the models analyzed in [1,2,3,4] are weaker, the corresponding bounds on separation rank developed in these papers are lower.
Consider for example the “odd-even” and “low-high” partitions from Figure 1(c) of [1]. Denote the subsets yielding these partitions by $I_{odd}$ and $I_{low}$ respectively. Applying our CNN result to $I_{odd}$ and $I_{low}$ yields upper bounds of $D_h^{O (N \cdot 5^{L - 1})}$ and $D_h^{O( \sqrt{N} \cdot 5^{L - 1} )}$ respectively. In contrast, the bounds in [1,2] (which were derived for a weaker model) are $D_h^{O(N)}$ and $D_h$ respectively.
Similarly, for a chain graph, consider the “odd-even” partition induced by $I_{odd} := \\{ 1, 3, …, N \\}$ and the “low-high” partition induced by $I_{low} := \\{1, \ldots, N / 2 \\}$. Applying our RNN result to $I_{odd}$ and $I_{low}$ yields upper bounds of $D_h^{O (N \\cdot 3^{L - 1})}$ and $D_h^{O( 3^{L - 1} )}$ respectively. In contrast, the bounds in [3,4] (which were derived for a weaker model) are $D_h^{O(N)}$ and $D_h$ respectively.
We hope the above fully addresses your question. If not please let us know and we will happily expand!
---
$\dagger$ Note that CNNs with overlapping windows were studied in [5], but this paper did not provide upper bounds on the separation rank.
[1] Cohen, Nadav, and Amnon Shashua. "Inductive bias of deep convolutional networks through pooling geometry." ICLR (2017)
[2] Levine, Yoav, et al. "Deep learning and quantum entanglement: Fundamental connections with implications to network design." ICLR (2018)
[3] Khrulkov, Valentin, Alexander Novikov, and Ivan Oseledets. "Expressive power of recurrent neural networks." ICLR (2018)
[4] Levine, Yoav, Or Sharir, and Amnon Shashua. "Benefits of depth for long-term memory of recurrent networks." (2018)
[5] Sharir, Or, and Amnon Shashua. "On the expressive power of overlapping architectures of deep learning." ICLR (2018).