DFA-GNN: Forward Learning of Graph Neural Networks by Direct Feedback Alignment

We are grateful to the reviewer for the time taken to assess our work and for the valuable feedback. We address each point individually. “W/Q” numbers the weakness or question followed by our response.

$**\large Response to W1:**$

Thanks for your comments. Our method builds on some ingenious previous studies, especially $*Nøkland A. Direct feedback alignment provides learning in deep neural networks, NeurIPS 2016*$. However, our work is the first to systematically study DFA's applicability to GNNs with extensive ablation studies and to provide update formulas and convergence proof for DFA in GNNs. The addition of pseudo-error generation is another highlight that is entirely novel for DFA. Our work demonstrates the exciting potential of non-BP training in graph deep learning, offering potential directions for addressing challenging issues such as oversquashing, topology distortion, and label scarcity, which warrant further exploration in the future.

$**\large Response to W2 and Q3:**$

The time complexity of our method depends on the architecture of the GNN models. Given specific GNN layers with a defined forward propagation formula, the computational time cost of our method includes four parts: forward propagation (Eq.1), pseudo-error generating (Eqs.7, 8), node filtering (Eq.8) and direct feedback alignment (Eq.10). The complexity of forward propagation is the same as BP because our method makes no change in this process. Supposing the dimension of node features and hidden units is $d$, for the GCN model formulated in Eq.1 whose forward propagation formula for $i$-th layer is written as $**X**^{(i)}=relu(**S****X**^{(i-1)}**W**^{(i-1)})$, the complexity is $\mathcal{O}(n^{2}d+nd^{2})$, where $n$ denotes the number of nodes. Since $n\gg d$ holds in most datasets, the complexity can be approximated as $\mathcal{O}(n^{2}d)$. For direct feedback alignment, according to Eq.10, the time complexity for each layer is $\mathcal{O}(n_{f}^{2}c+dn_{f}c+d^{2}c)$ and is further approximated as $\mathcal{O}(n_{f}^{2}c)$ due to $n_{f}\gg d \gg c$, where $n_{f}$ is the number of nodes after filtering and $n_{f}<n$, $c$ the number of category. In comparison, BP for GCN model has a complexity of $\mathcal{O}(n^{2}d+nd^{2}+d^{3})$ for each layer, which could be approximated as $\mathcal{O}(n^{2}d)$. Although both the methods have a quadratic complexity related to the number of nodes, our method makes parallel update for each layer while BP has to run update layer by layer.

The other two components pseudo-error generator and node filter bring additional time cost to our method compared with BP. According to Eqs.7 and 8, the time complexity of the two parts is $\mathcal{O}(tcn^{2})$ and $\mathcal{O}(cn)$, respectively, where $t$ denotes the iteration epochs for error spreading. Although the two introduced parts result in increased time cost, they are essential for generalizing DFA to GNNs. The ablation study in Tab.2 demonstrates the significant contribution of these two components. Overall, our methods has the same quadratic time complexity as BP on GCN, which explains why our method has a consistent five to ten times consumption per epoch compared with BP, rather than an exponential difference, regardless of the dataset size.

$**\large Response to W3 and Q1:**$

Thanks for the suggestion, and we will add related discussion in the revised version.

Our method shows a much more significant accuracy improvement on relatively small datasets, such as Texas and Cornell. The reason mainly lies in that GNNs trained by BP often suffer from heavy overfitting due to the scarcity of supervision on small datasets, especially for semi-supervised tasks. By contrast, the pseudo error generated in our method not only is for gradient computation when adapting DFA to GNNs, but also serves as an data augmentation strategy, enhancing the robustness of GNNs (shown in Fig.3) and improving the ability for handling overfitting with scarce supervision. The gains derived from the pseudo-error strategy is not so significant on larger datasets (e.g., PubMed, Photo), but it still brings overall positive effects to our methods.

For Computer and Chameleon, our method does not outperform BP, however, the accuracy gap on Chameleon is quite small (only 0.09%). The testing accuracy depends on both the training algorithm and GNN model. Although our method underperforms BP for GCN on Computer, however, our method outperforms BP for SGC, GraphSage, APPNP and ChebyNet on this dataset as shown in Tab.3. Generally, our non-BP method has comparable results compared with BP and even show better performance on most experimental trails, which indicates our non-BP training method has the inspiring potential to become a substitute for BP in the field of graph deep learning.

$**\large Response to W4 and Q2:**$

Our method is well-suited for large datasets. When the graph scale is large, for memory saving we can use edge indices instead of an adjacency matrix to store the graph. For forward propagation (Eq.1), the space requirement for neighbor aggregation can be reduced from $\mathcal{O}(n^{2}+nd)$ to $\mathcal{O}(|\mathcal{E}|+nd)$, where $|\mathcal{E}|$ denotes the number of edges. For direct feedback alignment (Eq.10), as $(**S**^{\text{T}})^{k}\hat{**E**}$ is exactly the aggregation of errors for $k$ times, the space requirement can be reduced to $\mathcal{O}(|\mathcal{E}|+nc)$, without the need to store the $k$-th power of the adjacency matrix. Similarly, space requirement reduction can also be achieved in the node filtering process.

As for prediction accuracy, the experimental results on Flickr, Reddit, and ogbn-arxiv (shown in Tab.X in the supplementary PDF) demonstrate that our method obtains comparable results to BP (within 1% accuracy) and outperforms other non-BP methods with only a small memory cost (2049 MiB, 11675 MiB, 2277 MiB for the three datasets, respectively).

We apologize for the confusing expression. The standalone direct feedback alignment (DFA, $\mathcal{O}(n^{2})$) as formulated in Eqs. 5 and 6 of the manuscript can potentially be faster than backpropagation (BP, $\mathcal{O}(n^{2})$) since DFA directly calculates the parameter updates for each layer from the loss, allowing for improved training efficiency through parallelization. However, to generalize DFA for graph data, we introduced the pseudo-error generator as detailed in Sec. 4.2. Consequently, the main time cost of our method arises not only from DFA but also from the pseudo-error generation (Eqs. 7, 8) and node filtering (Eq. 9).

According to Eqs. 7 and 8, the time complexity of these two components is $\mathcal{O}(tcn^{2})$ and $\mathcal{O}(cn)$, respectively, where $t$, $c$, and $n$ denote the iteration epochs for error spreading, the number of categories, and the number of nodes, respectively (In our earlier analysis, we approximated the complexity of these components as $\mathcal{O}(n^{2})$ and $\mathcal{O}(n)$ to highlight that our method maintains the same quadratic complexity with respect to $n$, the most significant factor). When these two components are added, our method consistently incurs a time cost that is 5 to 10 times larger than that of BP even though they have the same order of complexity. Although these additional components increase the time cost, they are crucial for adapting DFA to GNNs and handling graph-structured data. The ablation study in Tab. 2 highlights the substantial contribution of these components.

Although our method has achieved significant practical time efficiency advantages over existing non-BP methods, we will continue to explore ways to further improve the time efficiency of our training algorithm in future work to bring it closer to that of BP, and we will revise the related sections of the article to reflect these nuances more accurately.

Thank you again for your attention and support.

Best regards,

Authors

Thank you once again for your valuable feedback on our paper.

1. The time comparison of our method is presented in Table 6 of Appendix A.6 in the original manuscript (for your convenience, we have displayed the table below). Here, we compare the training time per epoch of our method with BP and other state-of-the-art non-BP methods. For the semi-supervised node classification task, all methods are trained for 1000 epochs. During training, we calculate the prediction accuracy on the validation nodes after each epoch and save the model that achieves the highest validation accuracy. This saved model is then used to make predictions on the test nodes. This approach is standard in semi-supervised graph learning. Therefore, the overall training cost is simply one thousand times the numbers shown in Table 6.

2. As noted in our response to W2 and Q3, both BP and the DFA in our method have a complexity of $\mathcal{O}(n^{2})$. Besides, our method introduces an additional complexity of $\mathcal{O}(n^{2})$ due to the pseudo-error generator. As a result, the overall complexity for both our method and BP remains the same $\mathcal{O}(n^{2})$. This explains why our method consistently takes five to ten times longer per epoch compared with BP as shown in Table 6, rather than showing an exponential difference, regardless of dataset size. While BP benefits from decades of research and strong software and hardware support, our method has not yet reached comparable time efficiency of BP. However, our method demonstrates superior time efficiency compared with most non-BP state-of-the-art methods, and the current time cost difference compared with BP is not substantial. Additionally, the parallel update strategy employed by our method for each layer offers considerable potential for parallel computing, which could be further explored to enhance time efficiency.

3. We theoretically derive formulas to integrate the direct feedback alignment mechanism into GNNs, as DFA for fully connected layers is not directly applicable to graph data. Additionally, we provide theoretical proof of the convergence of our proposed method (as shown in Section 4.3 and Appendix A.3). Our work highlights the promising potential of non-BP training in graph deep learning and opens up avenues for tackling some challenges within graphs, which merit further exploration in future research.

If our rebuttal has satisfactorily addressed your concerns, we would greatly appreciate it if you could consider reevaluating the score of our paper. Regardless of your decision, we are truly grateful for your guidance and the time you have invested in reviewing our work.

Thank you again for your attention and support.

Best regards,

Authors

$\newline$

Table 6: Average running time per epoch (s). For layer-wise training methods like PEPITA, CaFo, FF, and SF, the total time taken by each layer per epoch is reported.

We appreciate your thoughtful comments and positive assessment of our work. After carefully reviewing your feedback, below we provide answers to the comments you raised.

$**\large Response to W1:**$

The standalone direct feedback alignment formulated in Eqs.5 and 6 could be faster than BP. However, to generalize DFA to graph data we introduce the pseudo-error generator as elaborated in Sec.4.2, and the main time cost comes from the pseudo-error generation (Eqs.7, 8) and node filtering (Eq.9). According to Eqs.7 and 8, the time complexity of the two parts is $\mathcal{O}(tcn^{2})$ and $\mathcal{O}(cn)$, respectively, where $t, c, n$ denote the iteration epochs for error spreading, the number of categories and the number of nodes, respectively. Although the two introduced parts result in increased time cost, they are essential for generalizing DFA to GNNs. The ablation study in Tab.2 demonstrates the significant contribution of these two components.

$**\large Response to W2 and Q3:**$

Thanks for your comments. For our semi-supervised node classification task, we train all the methods for 1000 epochs, calculating the prediction accuracy for validation nodes after each epoch and saving the model that achieves the highest validation accuracy. We use the saved model to make predictions for the test nodes. This is a common experimental setting in semi-supervised graph learning. Thus, the overall training cost is simply one thousand times the numbers shown in Tab.6.

To better illustrate the training convergence of our DFA-GNN, we plot the training and validation accuracy of the proposed DFA-GNN and BP over training epochs on three datasets, as shown in Fig. 4 in the supplementary PDF. In general, our method shows similar convergence as BP. For both BP and our method, the convergence of validation accuracy occurs much earlier than that of training accuracy due to overfitting. The validation convergent epoch of DFA-GNN is nearly the same as BP on Cora and CiteSeer (around 100 epochs), while it is 100 epochs later than BP on PubMed (around 200 epochs). Our method achieves better validation accuracy on all these datasets and suffers less from overfitting compared with BP.

In terms of training accuracy, our method exhibits slightly lower convergent value and lower convergence speed than BP. The reason is that our method considers both the errors of labeled nodes and pseudo errors of unlabeled nodes as supervision signals. However, this does not prevent our method from achieving better validation results.

We do not include other non-BP methods in Fig. 4 because these methods (i.e., SF, FF, CaFo, etc.) follow a layer-by-layer update according to local loss. Therefore, the convergence behaviors varies across different layers, and it is hard to directly visualize them in a global view.

$**\large Response to W3 and Q2:**$

Thanks for your interesting suggestion. Although the pseudo-error generation process is essential for our method, it is also an optional choice for BP. We try integrating this component into BP, and the experimental results in Tab.IX in the supplementary PDF show that this component does not positively enhance BP in general. It only contributes to BP on Cora and CiteSeer while degrading the performance on the other six datasets. By contrast, it benefits DFA remarkably across all datasets and makes our method finally outperform BP in most scenarios. The different suitabilities of the pseudo-error generation to BP and DFA mainly lie in that DFA is more noise-tolerant than BP where the generated pseudo error always contains different degrees of noise, which has been discussed in some previous studies [a,b].

[a]. R. Ohana et. al., Photonic Differential Privacy with Direct Feedback Alignment. NeurIPS 2021.

[b]. J. Lee and D. Kifer. Differentially Private Deep Learning with Direct Feedback Alignment. arXiv 2020.

$**\large Response to W4:**$

Thanks for the suggestion. We plot the prediction accuracy with the number of layers increasing from 2 to 10, as shown in Fig. 5 in the supplementary PDF. Both the BP and our method show a decrease in accuracy, but our method is less negatively affected and consistently outperforms BP. This superiority is derived from the fact that our method adopts direct feedback of errors for the update of each layer, reducing the problem of oversmoothing and other gradient issues caused by backward gradient accumulation. This observation indicates the potential of our method for deep GNN training.

$**\large Response to W5:**$

Thanks for your suggestion, we will explore the potential of DFA-GNN for graph-level and edge-level tasks in future work.

$**\large Response to Q1:**$

The pseudo error is essential for our method because the parameter update formula (Eqs.5 and 6) for each layer requires the error of all nodes. Spreading labels may not be well-suited to our update mechanism. Additionally, since the pseudo error depends on the prediction of each epoch, updating pseudo errors in real-time based on the results of forward propagation in each epoch is a more reasonable choice. Augmenting only once in an early epoch may lead to performance degradation of model.

$**\large Response to Limitations:**$

We apologize for the confusing expression. The efficiency advantage of our method is mainly reflected in the comparison with other non-BP algorithms, showing significant time superiority over CaFo, FF, and SF, as presented in Tab.6. As BP has been extensively researched for decades and benefits from robust software and hardware support, our method has not yet achieved comparable time efficiency of BP. However, the parallel update strategy for each layer in our method makes it more conducive to parallel computing, which has the potential to further improve time efficiency. We will revise the conclusion section of the article to make it more rigorous.

Thank you for your constructive feedback and positive assessment of our work. Below, we provide individual responses to your questions.

$**\large Response to W1:**$

We take the GCN with ReLU activation function as an example to elaborate on our method since GCN is one of the most classic GNN models and ReLU is the most popular activation function.

Considering another activation function $\sigma(\cdot)$ with a deterministic derivative function $\sigma^{'}(\cdot)$, Eq.4 can be modified as: $\delta**X**^{(2)}=**S**^{\text{T}}**EB**^{(2)}\odot\sigma'(**H**^{(1)}**W**^{(1)})$ and $\delta**X**^{(1)}$ is approximated as $(**S**^{\text{T}})^{2}**EB**^{(1)}\odot\sigma'(**H**^{(0)}**W**^{(0)})$, which is similar to DFA in MLPs. The symbol $\odot$ denotes element-wise multiplication, and $\sigma'(**H**^{(k)}**W**^{(k)})$ is computed during forward propagation. As shown in Tab.VIII in the supplementary PDF, our method is well integrated with different activation functions (e.g., Sigmoid, Tanh, ELU and LeakyReLU) and derives consistently excellent performance.

Regarding different GNN architectures, our method is portable to complex GNNs. Once $\delta**X**^{(k)}$ is derived in parallel, the parameters of each GNN layer can be computed by gradient descent. This adaptability ensures that our method remains effective while still eliminating the backpropagation of gradients among different GNN layers. The results in Tab.3 of Sec.5.4 demonstrate the excellent portability of our method.

$**\large Response to W2 and Limitations:**$

Thanks for your suggestion, and we will add more discussion in the revised version.

It is observed from Tab.1 that our method has overall superior performance than BP. In particular, our method shows a much more significant accuracy improvement on relatively small datasets, such as Texas and Cornell. The reason mainly lies in that GNNs trained by BP often suffer from heavy overfitting due to the scarcity of supervision on small datasets, especially for semi-supervised tasks. By contrast, the pseudo error generated in our method not only is for gradient computation when adapting DFA to GNNs, but also serves as a data augmentation strategy, enhancing the robustness of GNNs (shown in Fig.3) and improving the ability for handling overfitting with scarce supervision. The gains derived from the pseudo-error strategy is not so significant on larger datasets (e.g., PubMed, Photo), but it still brings overall positive effects to our methods. Interestingly, BP does not benefit from the same pseudo-error generation strategy (please see Tab.IX in the supplementary PDF, and refer to $**the response to reviewer buRu**$ for detailed discussion).

Additionally, from Tab.3, it is observed that our method shows greater superiority when the aggregation strategy of the GNN models is isotropic or the receptive field of aggregation is larger (e.g., GCN, SGC and ChebyNet). We attribute this phenomenon to the fact that isotropic and larger receptive field GNN layers can better utilize the direct feedback of errors. This is an interesting finding that deserves further exploration.

$**\large Response to W3:**$

Thanks for the suggestion. We will introduce more about the limitations of BP and the non-BP optimization methods in the introduction and related work in the revised version.

$**\large Response to W4:**$

Thanks for your suggestion, we will provide notations for this variable in revision.

$**\large Response to Q1:**$

Sorry for the typo, the $**W**$ in Eq.7 should be $**Z**$, which is the variable to be optimized.

$**\large Response to Q2**$

Sorry for the confusion caused. The alignment of $**W**$ and $**B**$ means the directions of the two variables tend to converge to within 90 degrees of each other (as shown in Fig.2 (a)) rather than being numerically similar. In fact, the initialization of $**B**$ is not completely random, but follows a normal distribution that satisfies $\mathbb{E}[**B****B**^{T}]\propto **I**$. Under such constraints, as discussed in Sec. 4.3, $**W**$ will converge to be alignment to $**B**$ even starting from a high point. We will add related description in the revised version for clarity.

$**\large Response to Q3:**$

DFA is BP-free training method that has not been fully explored yet. Intuitively, DFA updates model parameters via gradient computation that is similar to BP. But differently, DFA obtains approximate gradients directly from the loss rather than backpropagation layer-by-layer. As discussed in Sections 1 and 2, this difference makes DFA more biologically plausible and promising in terms of generalization and parallelism. In previous studies, DFA usually exhibits similar or inferior performance in comparison with BP. The performance improvement of our method mainly derives from the pseudo-error generation strategy, which has been discussed in the response to W2.

$**\large Response to Q4:**$

Yes, DFA can directly calculate the parameter update for every layer from the loss, and it thus can improve training efficiency by parallelization. However, to generalize DFA to graph data we introduce the pseudo-error generator as elaborated in Sec.4.2, and the main time cost is from the pseudo-error generation (Eqs.7, 8) and node filtering (Eq.9). According to Eqs.7 and 8, the time complexity of the two parts is $\mathcal{O}(tcn^{2})$ and $\mathcal{O}(cn)$ respectively, where $t, c, n$ denote the iteration epochs for error spreading, the number of categories and the number of nodes, respectively.

Thank you for your insightful feedback and for recognizing our efforts. We appreciate your suggestion to further discuss the method's limitations, particularly regarding its suitable scenarios and training efficiency.

During the rebuttal period, we conducted additional experiments to address these concerns, focusing on the method's suitability for various activation functions, its performance on large-scale graphs, training time, and convergence behavior. These insights have provided a more comprehensive understanding of the method's capabilities and constraints. In the final version of the paper, we will include a dedicated section discussing these aspects, offering a balanced view of the method's strengths and areas for future improvement.

We respect your decision and are grateful for your constructive critique. Your feedback has been instrumental in refining our work, and we thank you once again for your thorough and thoughtful review.