Summary
This work considers the problem of message-passing in large graphs, where a sampled mini-batch of nodes, $\mathcal{B}$, aggregates information from exponentially growing neighborhood sizes, $\mathcal{N}\_{\mathcal{B}}^c = \mathcal{N}\_{\mathcal{B}} \setminus \mathcal{B}$. To tackle the inefficiency and/or limited performance of existing sampling based methods designed to tackle this problem, a technique called *Tological Compensation* (TOP) is presented, which captures information from out-of-batch neighbors, while limiting the message-passing to the in-batch nodes.
The authors start by hypothesizing an invariant structure in the node representations, such that the hidden representations satisfy $\mathbf{H}^{(l)}\_{\mathcal{N}\_{\mathcal{B}}^c} \approx \mathbf{R} \mathbf{H}^{(l)}\_{\mathcal{B}}$, for some linear transformation $\mathbf{R} \in \mathbb{R}^{|\mathcal{N}\_{\mathcal{B}}^c| \times |\mathcal{B}|}$ learnt during pre-processing. This allows information from $\mathcal{N}\_{\mathcal{B}}^c$ to be efficiently incorporated into a message passing scheme over just $\mathcal{B}$. Specifically, they augment the original propagation matrix as $\tilde{\mathbf{A}}\_{\mathcal{B},\mathcal{B}} + \tilde{\mathbf{A}}\_{\mathcal{B},\mathcal{N}\_{\mathcal{B}}^c} \mathbf{R}$, and then simply propagate messages over $\mathcal{B}$.
On a range of large real-world datasets (169K-111M nodes, 1.1M-1.6B edges), they demonstrate that TOP can stay competitive with the full-batch gradient descent, and outperforms other baselines. They also show that, at convergence, the approximation error in node representations using TOP is less than 5%, adding support for the invariant structure in the node representations. Theoretically, they show that the convergence rate of TOP is $\mathcal{O}(\epsilon^{-4})$, same as node-wise sampling algorithms, and better than $\mathcal{O}(\epsilon^{-6})$ rate for subgraph sampling algorithms.
Strengths
1. The idea of using an invariant structure to approximate messages from out-of-batch nodes to in-batch nodes is unique and interesting.
2. It boasts an $\mathcal{O}(N^{-4})$ convergence rate in the number of iterations $N$, equal to node sampling methods (Section 5.3).
3. The message invariance structure is demonstrated in some dummy cases (Section 4.2), and then validated via experiments (Section 5.2). As simple as a linear approximation is competitive on several large datasets, outperforming several baselines (Section 6).
4. The memory cost of the method scales very slowly with the number of layers in the GNN, unlike other baselines compared (Figure 5).
5. The variance of this method is also low (Figure 3), making it a reliable choice.
Weaknesses
My rating for the work is low right now primarily because the presentation can be significantly improved. I also includes suggestions here, since I think some of them are weaknesses in the manuscript.
1. The citation (Ma & Tang, 2021), near line 46, is a book on graph deep learning, which is too general. I assume you wish to direct the reader to chapter 7 in it. It would be helpful to specify that along with the citation.
2. There seems to be some inconsistency in the definition of the edge set and corresponding matrices: if $(i,j) \in \mathcal{E}$ denotes an edge from $i$ to $j$, then $\mathcal{N}\_i$ is the out-neighborhood of node $i$, i.e. the nodes it *sends messages to* (not receives from), which I believe is not the intended definition. Similarly, $\mathbf{A}\_{ij} = 1$ if $(i,j) \in \mathcal{E}$, then the $i^{\text{th}}$ row of $\mathbf{A}$ whether nodes *receive messages from* node $i$ (which makes the GCN definition in equation (1) wrong). Also, you should mention that $\mathbf{D}$ is the in-degree matrix. Of course, all this can be avoided by assuming you're working with undirected graphs, but it will be more helpful to make the notation consistent for directed graphs.
3. The estimation of topological compensation is arbitrary: Definition 4.1 requires $g$ to satisfy $\mathbf{H}^{(l)}_{\mathcal{N}\_{\mathcal{B}}^c} = g(\mathbf{H}^{(l)}\_{\mathcal{B}})$, $\forall \mathcal{W}$, but the estimation of $\mathbf{R}$ is based on a randomly initialized parameter set. Again, there is no validation for the claim that this method is "very accurate", since the evaluation is on a single set of (learned) parameters. I do see that an alternative protocol proposed is to update $\mathbf{R}$ when the approximation errors increase, but that disagrees with Definition 4.1 (as I understand it, see questions).
4. The assumption of topological invariance in the node representations seems to be very strong, especially for it to hold for all layers ($\forall l\in[L]$) and for all parameter sets ($\forall \mathcal{W}$). It is also not verified in real-world settings. Figure 2(a)-(c) show that the *final node representations* are close to the full-batch representations *at the end of training*, i.e. for the set of learned parameters, and for a single layer; the assumption behind the theoretical motivation is much stronger.
5. About Figure 2, low relative error at the end of training is not sufficient empirical support for the claim of existence of invariance in node features; although, competitive performance on a range of benchmarks does provide a convincing argument. I recommend a rewording of the manuscript such that soundness is prioritized.
6. It is very hard to figure out the exact algorithm behind TOP, eg. how $\mathbf{R}$ is computed, partly because of the typos (see below for a non-exhaustive list). It becomes clear only in Section 5.1 (even then some questions remain). An algorithm block at some point might help with navigation, but I believe some restructuring is needed to improve clarity.
7. The architectures presented in the main text -- GCN and GCNII -- do not represent a wide class of GNNs. It will be more convincing to move the results for one of GAT or GraphSAGE to the main text, and one of GCN or GCNII to the appendix.
8. There is no discussion on the depth of the networks used in Section 6 -- since this method is designed to tackle the problem of exponentially growing neighborhoods, which is especially problematic when using deep networks for large graphs, it is important to understand how the performance is affected by the network depth.
9. For long-range tasks (which are the primary targets for learning with deep GNNs), it is important to capture long-range information. Since TOP estimates the message-invariant transformation $\mathbf{R}$ using only the input features of the batch-neighborhood, followed by message-passing with the 1-neighborhood of the batch, I believe it fails to capture any information from nodes 2-hops or further away (except, possibly, that learnt by $\mathbf{R}$ during pre-processing).
10. Since TOP is expected to have a fast convergence rate, I was hoping to see the plots of loss/accuracy against the number of iterations. The authors do present plots against physical time in Figure 3 and Figure 5, where TOP is competitive or much faster than other algorithms. However, Figure 4 shows that the per-epoch time of TOP is much smaller, implying that in the same physical time, it can get in more optimization steps. For that reason, I am interested in the plots of performance metrics against number of iterations or number of epochs.
Questions
1. Do you have any comments on the regularization effect of stochastic sampling methods, and why TOP outperforms them on test-sets despite (seemingly) not having any regularization mechanism?
2. In Definition 4.1, am I correct to assume that by "for any GNN parameters $\mathcal{W}$", you mean 'for all $\mathcal{W}$' and not 'for a given $\mathcal{W}$'?
3. Definition 4.1 says $g$ needs to satisfy $\mathbf{H}^{(l)}_{\mathcal{N}\_{\mathcal{B}}^c} = g(\mathbf{H}^{(l)}\_{\mathcal{B}})$. Is that supposed to be $\forall l\in[L]$ and $\forall \mathcal{B}\subset \mathcal{V}$?
4. I don't quite understand the argument in the paragraph starting at line 246. Can you elaborate?
5. In section 4.2.2, how valid is the assumption on full column-rank of the convolved feature matrices?
6. The objective near line 262, $\\\|\mathbf{Z}^{(l)}\_{\mathcal{N}\_{\mathcal{B}}^c}-\mathbf{R}\mathbf{Z}^{(l)}\_{\mathcal{B}}\\\|$, what is $l$ here and what is $\mathcal{B}$?
7. The second equality near line 264, that need not be true unless the minimum of the objective $\min\_{\mathbf{R}} \\\|\mathbf{Z}^{(l)}\_{\mathcal{N}\_{\mathcal{B}}^c}-\mathbf{R}\mathbf{Z}^{(l)}\_{\mathcal{B}}\\\| = 0$. Is it 0 because of the full column-rank?
8. In the computation of $\mathbf{R}$ in line 294, what is $\mathcal{B}$ supposed to be?
9. Am I correct to understand that the proof of Theorem 5.1 only uses the unbiasedness of TOP gradients, as shown in Theorem D.1? Doesn't the part after that closely follow the proof of Theorem 2 in Appendix C.4 of Chen et al. (2018a)? If so, this should be emphasized; continue to keep it in the appendix for completeness, though.
10. Possible typos (correct me if I am wrong; in that case, I may have read the related parts wrongly):
- In definition 4.1, $g$ should be a map from $\mathbb{R}^{|\mathcal{B}|\times d}$ to $\mathbb{R}^{|\mathcal{N}_{\mathcal{B}}^c|\times d}$.
- In line 258, supposed to be $\mathbf{Z}^{(l)}\_{\mathcal{B}}$ instead of $\mathbf{X}^{(l)}\_{\mathcal{B}}$.
- The objective near line 262 should be $\\\|\mathbf{Z}^{(l)}\_{\mathcal{N}\_{\mathcal{B}}^c}-\mathbf{R}\mathbf{Z}^{(l)}\_{\mathcal{B}}\\\|$.
- In line 294, $\bar{\mathbf{H}}\_{\mathcal{N}\_{\mathcal{B}}^c}$ instead of $\bar{\mathbf{H}}\_{\mathcal{N}\_{\mathcal{B}}}$.
- In line 1269, $\bar{\mathbf{H}}\_{\mathcal{N}\_{\mathcal{B}}^c}$ instead of $\bar{\mathbf{H}}\_{\mathcal{N}\_{(\mathcal{B})^c}}$.
- In line 1300 (and others below), $\mathbf{d}\_{\mathcal{W}^{(k)}}$ instead of $\mathbf{d}\_{\mathcal{W}}^{(k)}$.
- Not completely sure, but the second expression in line 1314 seems to be a typo (I can understand what was intended, though).
- In line 1320 (and following), $\mathcal{W}^{(1)}$ instead of $\mathcal{W}^1$; similarly for $\mathcal{W}^{N+1}$ and $\mathcal{W}^R$.