Beyond Directed Acyclic Computation Graph with Cyclic Neural Network

We would like to express our sincere thanks for the reviewer’s constructive feedback. Based on your review, we have made corresponding changes within the paper and our rebuttals are provided below:

Rebuttal to Weakness 1 and Question 1:

Concern:

Clarity between RNN and Cyclic NN.

Response:

To highlight the distinctive characteristics of Cyclic NN, we have added a new Section A.4 in the appendix, along with Figure 5, which provides a clear illustration comparing Cyclic NN with RNNs. Comparison with RNNs: Recurrent structures like RNNs, LSTMs, and GRUs focus on the recurrence of the same computation block. In contrast, our Cyclic NN emphasizes cyclic communication between different computation blocks, as highlighted in red in Figure 5. The presence of cyclic structures enables us to build neural networks with any graph structure beyond directed acyclic graphs (DAGs). While recurrent structures can be seen as self-loops over a single computation neuron, Cyclic NN allows for more flexible network structures beyond self-loops. We propose the computational neuron to increase the capacity of each calculation block. As a more expressive neuron design, we can also use LSTM or gated neuron to be the computational neuron in Cyclic NN.

Rebuttal to Weakness 2:

To better contextualize our proposed Cyclic NN within current literature, we replace the related work of “Graph Generator” with “Artificial Neural Networks”. It can better contextualize the position of Cyclic NN. The newly added related work section is also given as follows:

“Artificial neural networks (ANNs) have evolved through various paradigms, each suited to specific tasks and data structures. Feedforward neural networks (MLPs, CNN, and Transformers, etc) form the foundational class of ANNs. These models are characterized by their layer-by-layer processing, making them effective for structured data tasks. Recurrent neural networks (RNNs) and their variants such as Long Short-Term Memory and Gated Recurrent Units introduced recurrent loops, enabling temporal modeling for sequential data. Graph Neural Networks (Graph Convolutional Networks, Graph Attention Networks, and Graph Isomorphism Networks, etc) extend neural computation to graph-structured data. While GNNs support message passing between nodes, they are typically constrained by acyclic computational graphs. Recently, there are also new ANN designs inspired by biology nerve systems. Liquid neural networks adapt dynamically to changing inputs, exhibiting flexible, real-time computation inspired by biological intelligence. Spiking Neural Networks mimics the communication pattern of biology neurons with discrete spike events instead of continuous activations.

Cyclic NN firstly focuses on the network topology similarity with biology neural network by introducing cyclic structures within ANNs. It represents a transformative departure from these existing paradigms by removing the Directed Acyclic Graph (DAG) constraint. Inspired by the flexible and dynamic nature of biological neural systems, Cyclic NN introduces cyclic connections between neurons, enabling richer information flow. This design achieves enhanced expressiveness, biological plausibility, and flexibility.”

We would like to firstly thank the reviewer for acknowledging our novelty, contribution and foreseeing the future impact of our proposed Cyclic NN. Our rebuttals towards your weaknesses and questions are listed as follows. Hope we are able to clear your concerns on this paper.

Rebuttal to Weakness:

Concern:

Differences between Cyclic NN and Graph Neural Network is not clear

Response:

To highlight the distinctive characteristics between Cyclic NN and graph neural networks. We specifically add a new Section A.4 in the appendix, along with Figure 5, which provides a clear illustration comparing Cyclic NN and GNN.

Comparison with GNNs: In GNNs (such as GCNs, recurrent GNNs, and GATs), the graph $\mathcal{G}$ is the input to the network, aiming to learn representations for each node. Typically, DAG-structured computations are used within the model, like the linear layers in GCNs. GNNs serve as encoders for nodes within graphs, with the graph structure acting as the model's input. However, in Cyclic NN, the input is not constrained to graphs; it can be an image, for example, and the Cyclic NN encodes this input into a representation. Here, the graph structure $\mathcal{G}$ refers to the encoder itself within the Cyclic NN. Thus, the Cyclic NN has fundamental differences with GNNs.

Rebuttal to Question:

We would like to provide the rebuttal based on the list of your questions.

Q1: In Eqn (4), the neuron input depends on the outputs of the adjacent neurons. When t=0, the outputs of the adjacent neurons have not been unknown yet. So how is line 6 of Algorithm 1 computed? Do the authors ignore the outputs of the adjacent neurons when t=0?

A1: We initialize all computational neuron’s output to 0 when t=0. Thus, we pass the tensor with 0s on line 6 of Algorithm when t=0, which ignores the outputs of adjacent neurons.

Q2: For a later $N$, if it is adjacent to an earlier neuron (call it $N_1$), would the input of the later neuron use the output of the earlier neuron in the last round (before the for loop) or in the current round (inside the for loop)?

A2: This is a very good question. We also face this problem when designing the training algorithm. We finally adopted the output of the earlier neuron in the last round (before the for loop) for propagation as we found the training would be more stable compared to the other choice. If we use the current round result, the computational neurons update will depend on the update order, which we also want to avoid as there is no reason to pre-define the update order especially on the cyclic graph structure.

Q3: The inner while loop of Algorithm 1 updates this parameter $T$ times. Is this understanding correct?

A3: Yes, this understanding is correct. We will update each computational neuron $T$ times.

Q4: If correct, then the $T$ steps of the inner while loop of Algorithm 1 do not propagate information across $T$ hops of the graph. Rather, information is propagated to at most one hop away, no matter how big is $T$. The inner while loop is more like running an optimization $T$ steps rather than propagating information in a $T$-layer GNN.

A4: Here we would like to argue the information will be propagated across $T$ hops of the graph similar to the message passing mechanism in GNNs. In each step, the computational neuron receives information from its neighbors and gets the new output for next step’s propagation. Here its parameter only updates by one training step, which makes it stay nearly the same. Its output will not change and still keeps its neighbors information. In the next round, its output (carrying current round neighbor’s information) will be propagated again to reach farther neighbors. Here, we optimize $T$ steps, and at the same time, the information is propagated to $T$ hops neighborhoods.

It also answers the following question that as the information is propagated further, the unrolling in Figure 3 is reasonable because the output is propagated further and splitted into more linear regions by Relu activation.

We would like to thank the reviewer for providing constructive feedback on our proposed cyclic neural network. To clarify our strength and make the contribution clearer. We conduct additional experiments to answer the reviewer's questions. Our rebuttals are provided as follows:

Rebuttal to Weakness 1 (W1) and Question 1 (Q1):

Concern:

The differences between our proposed Cyclic Neural Network (Cyclic NN) and recurrent neural networks (RNNs) or graph neural networks (GNNs) are unclear.

Response:

To highlight the distinctive characteristics of Cyclic NN, we have added a new Section A.4 in the appendix, along with Figure 5, which provides a clear illustration comparing Cyclic NN with RNNs and GNNs.

Comparison with RNNs:

Recurrent structures like RNNs, LSTMs, and GRUs focus on the recurrence of the same computation block. In contrast, our Cyclic NN emphasizes cyclic communication between different computation blocks, as highlighted in red in Figure 5. The presence of cyclic structures enables us to build neural networks with any graph structure beyond directed acyclic graphs (DAGs). While recurrent structures can be seen as self-loops over a single computation neuron, Cyclic NN allows for more flexible network structures beyond self-loops.

Comparison with GNNs:

In GNNs (such as GCNs, recurrent GNNs, and GATs), the graph $\mathcal{G}$ is the input to the network, aiming to learn representations for each node. Typically, DAG-structured computations are used within the model, like the linear layers in GCNs. GNNs serve as encoders for nodes within graphs, with the graph structure acting as the model's input. However, in Cyclic NN, the input is not constrained to graphs; it can be an image, for example, and the Cyclic NN encodes this input into a representation. Here, the graph structure $\mathcal{G}$ refers to the encoder itself within the Cyclic NN. Therefore, our Cyclic NN is distinct from both RNNs and GNNs (including recurrent GNNs). The newly added Figure 5 provides a clearer illustration of these differences.

Rebuttal to Weakness 2 (W2):

Concern:

The improvement of Cyclic NN might not be generalizable across different graph structures.

Response:

The improvements of Cyclic NN are also observed in WSGraph and BAGraph structures. As shown in Table1, the widely used DAG-structured BP-Chain* method achieves an error rate of 1.77 on the MNIST dataset. In comparison, Cyclic NN with WSGraph and BAGraph achieves error rates of 1.70 and 1.64, respectively, both surpassing the current DAG solution. This demonstrates that the improvement of our approach is consistent across different types of Cyclic NN graphs. Our core contribution lies in introducing cyclic structures among different computation blocks. To ensure a fair comparison among all training methods, we adopted the same structure as feed-forward networks. To further validate the effectiveness of Cyclic NN, we added an ensemble method that combines multiple linear layers as a baseline. The experimental results, shown in Table 1, indicate that Cyclic NN still performs the best among all methods. This underscores the advantages of incorporating cyclic structures within the model.

Rebuttal to Question 2 (Q2):

Concern:

Clarity on the stability and effectiveness of localized optimization in training.

Response:

To address this, we have added a new Section A.5 in the appendix, which presents the training curves for different graph structures. We plotted the feed-forward (FF) loss, classifier loss, and error rate changes over training epochs. Observations indicate that for all graph structures and datasets, the decrease in losses and error rates is stable and steady. Localized optimization focuses on optimizing parameters at a local level without propagating updates across layers, helping to mitigate gradient vanishing or exploding issues commonly encountered in global optimization.

Rebuttal to Question 3 (Q3):

Concern:

The need to provide the full asymptotic complexity of the model.

Response:

We appreciate this suggestion. In Section 3.5, we have added a paragraph to illustrate the full asymptotic complexity of the proposed GOMLP model: "Consider the example of GOMLP and examine the time complexity of each computation neuron. The maximum complexity for each computation neuron is $O((|\mathcal{V}| - 1)d^2) = O(|\mathcal{V}|d^2)$ when it receives information from all other computation neurons. Therefore, the total time complexity of GOMLP is $O(|\mathcal{E}||\mathcal{V}|d^2)$."

We hope that these clarifications address your concerns and highlight the contributions of our work more effectively. Let us know if you have any further questions. We would be very happy to improve our paper based on your suggestions :).

Thanks for addressing my questions. The rebuttal has clarified most of my concerns. I have adjusted the score.