Pay attention to cycle for spatio-temporal graph neural network

We thank the reviewer for suggesting various constructive comments. Please find our response to the weaknesses proposed by the reviewer.

• Weakness 1: Theorem 3.1 demonstrates that any cyclic subgraphs of the temporal traffic signal $\mathcal{G} \times I$ is comprised of nodes of form $(c_1, t_1), (c_2, t_2), \cdots, (c_n, t_n) \in \mathcal{G} \times I$, where the nodes $c_1, c_2, \cdots, c_n$ are on a common cyclic subgraph of the underlying traffic network $\mathcal{G}$. We added the above comment after Theorem 3.1 of the updated manuscript.
• Weakness 2: Using the notation mentioned in our response above, the temporal cycled clique in the spatiotemporal graph corresponds to a complete subgraph with nodes of form $(c_1, t_1), (c_2, t_2), \cdots, (c_n, t_n) \in \mathcal{G} \times I$, where the nodes $c_1, c_2, \cdots, c_n$ are on a common cyclic subgraph of the underlying traffic network $\mathcal{G}$. That is, all the nodes $(c_1, t_1), (c_2, t_2), \cdots, (c_n, t_n)$ are connected by edges by one another. For example, consider a cyclic traffic network consisting of 5 destinations A, B, C, D, and E where the edges correspond to roads connecting destinations A-B, B-C, C-D, D-E, and E-A. A temporal cycle would for example correspond to a graph with nodes $(A,t_1), (B,t_2), (C,t_3), (D,t_2), (E,t_3)$. By using a clique adjacency matrix, which corresponds to connecting all the destination with edges, one is able to understand traffic flow among destinations at different periods of time which do not directly share a road connection, such as understanding traffic flow from destination B at time $t = t_2$ to destination E at time $t = t_3$. More specific details on constructing clique adjacency matrices can be found in Choi et al. (2023).
• Weakness 3: As the reviewer suggested, we demonstrated the extendability of the proposed model to other spatio-temporal datasets by adding a new experimental result on predicting air quality using KnowAir Dataset. We used this dataset instead of the Airformer dataset as suggested by the reviewer, because the explicit adjacency matrix was not given in the latter dataset, which made us difficult to analyze Airformer dataset using Cy2Mixer given the limited time in writing the response for reviewers. Experimental results suggest that Cy2Mixer outperforms other baseline and state-of-the-art models, thereby suggesting that our proposed model can be used for effectively analyzing other types of spatio-temporal datasets.
• Weakness 4: As the reviewer rightfully pointed out, it is important to ask why utilizing cyclic structures are helpful to traffic forecasting problems. The significance lies in elucidating the restrictions or constraints associated to constructing a global traffic signal throughout any time period $X: \mathcal{G} \times I \to \mathbb{R}^{N x C}$ from glueing a collection of traffic signals $X_t \in \mathbb{R}^{N x C}$ obtained from a set of distinct time periods. This fact originates from a mathematical insight from algebraic topology and algebraic geometry that given a topological space Y and a collection of open neighborhoods $U_\alpha$ which satisfies $\cup_\alpha U_\alpha = Y$, the constraints associated to glueing continuous functions $f_\alpha: U_\alpha \to \mathbb{R}^k$ to a unique global function $f: Y \to \mathbb{R}^k$ can be understood from computing topological (or cohomological) invariants of a topological space $Y$. In the context of traffic network datasets, the topological space $Y$ corresponds to the temporal traffic network $\mathcal{G} \times I$, the open neighborhoods correspond to traffic network at a certain time frame $\mathcal{G} \times (t_e - 1, t_e + 1)$, the functions $f_\alpha$ correspond to a constant extension of traffic signals $X_{t_e}: \mathcal{G} \times \{t_e\} \to \mathbb{R}^{N \times C}$ to the space $\mathcal{G} \times (t_e - 1, t_e + 1)$, the function $f$ corresponds to the global traffic signal $X: \mathcal{G} \times I \to \mathbb{R}^{N \times C}$, and the obstructions correspond to cyclic subgraphs of $\mathcal{G} \times I$, namely the temporal interactions among nodes of a traffic network which lie on an identical cyclic subgraph. Theorem 3.1 allows us to reduce the problem of computing cyclic subgraphs of $\mathcal{G} \times I$ to computing cyclic subgraphs of $\mathcal{G}$, which implies that previous techniques which analyzes cyclic subgraphs of any graphs can be also utilized to analyze cyclic subgraphs of traffic datasets. We made clarifications addressing the comments above after Theorem 3.1 in the updated manuscript.
• Weakness 5: As the reviewer suggested, we edited the abstract of the manuscript.

We sincerely thank the reviewer for providing very detailed comments to our manuscript. Please find our responses to the weaknesses and questions provided by the reviewer.

• Weakness 1: One of the significant contributions of this manuscript lies in verifying that incorporating cyclic substructures of traffic networks (or graph datasets) is effective in forecasting traffic datasets. We note that previous studies which incorporate cyclic substructures of graphs to GNNs, as shown in Choi et al. (ICLR, 2022b), primarily focus on classifying isomorphism classes of collections of different graphs. This is a problem which is of a very different nature to traffic forecasts, which can be understood as a problem focusing on approximating and forecasting collections of functions $f: \mathcal{G} \to \mathbb{R}^{N \times C}$ defined over an underlying traffic network $\mathcal{G}$, or in other words a single underlying graph $\mathcal{G}$. The novelty of the paper hence lies in demonstrating that utilizing cyclic structures of traffic networks is indeed effective in forecasting traffic datasets.

  As the reviewer rightfully pointed out, it is hence a natural question to ask why utilizing cyclic structures are helpful to traffic forecasting problems. The significance of utilizing cyclic substructures of traffic networks lies in elucidating the restrictions or constraints associated to constructing a global traffic signal throughout any time period $X: \mathcal{G} \times I \to \mathbb{R}^{N \times C}$ from glueing a collection of traffic signals $X_t \in \mathbb{R}^{N \times C}$ obtained from a set of distinct time periods. This fact originates from a mathematical insight from algebraic topology and algebraic geometry that given a topological space Y and a collection of open neighborhoods $U_\alpha$ which satisfies $\cup_\alpha U_\alpha = Y$, the constraints associated to glueing continuous functions $f_\alpha: U_\alpha \to \mathbb{R}^k$ to a unique global function $f: Y \to \mathbb{R}^k$ can be understood from computing topological (or cohomological) invariants of a topological space $Y$. In the context of traffic network datasets, the topological space $Y$ corresponds to the temporal traffic network $\mathcal{G} \times I$, the open neighborhoods correspond to traffic network at a certain time frame $\mathcal{G} \times (t_e - 1, t_e + 1)$, the functions $f_\alpha$ correspond to a constant extension of traffic signals $X_{t_e}: \mathcal{G} \times \{t_e\} \to \mathbb{R}^{N \times C}$ to the space $\mathcal{G} \times (t_e - 1, t_e + 1)$, the function $f$ corresponds to the global traffic signal $X: \mathcal{G} \times I \to \mathbb{R}^{N \times C}$, and the obstructions correspond to cyclic subgraphs of $\mathcal{G} \times I$, namely the temporal interactions among nodes of a traffic network which lie on an identical cyclic subgraph. Theorem 3.1 allows us to reduce the problem of computing cyclic subgraphs of $\mathcal{G} \times I$ to computing cyclic subgraphs of $\mathcal{G}$, which implies that previous techniques which analyzes cyclic subgraphs of any graphs can be also utilized to analyze cyclic subgraphs of traffic datasets. We made clarifications addressing the comments above after Theorem 3.1 in the updated manuscript.

• Weakness 2: Unlike the rewiring approach proposed by the reviewer, the clique adjacency matrix can be thought as rewiring the nodes present in a common cyclic subgraph as cliques, as well as eliminating any edges in the underlying graph which do not lie in any of the cyclic subgraphs. By doing so, the proposed model encapsulates the topological non-trivial invariants by incorporating the features obtained from both the usual adjacency matrices and the clique adjacency matrices. In light of the observation that topological non-invariant invariants elucidates the conditions and obstructions associated to gluing traffic signal measurements $X_t$ to obtain a global traffic signal $X$, the proposed method thereby utilizes both types of adjacency matrices to effectively obtain global traffic signals $X$ from adequately gluing traffic signal measurements $X_t$.

• Weakness 3: As the reviewer kindly pointed out, we made all the relevant clarifications on the notations used in the manuscript.

• Question 1: If the underlying geometric structure of the traffic network changes, the corresponding adjacency matrix will also change. We believe it is possible to obtain a new clique adjacency matrix based on the newly obtained adjacency matrix, and Cy2Mixer is capable of incorporating the newly obtained clique adjacency matrix and forecast traffic signals. Nevertheless, to the best of our knowledge, the underlying traffic network associated to traffic datasets we used in the experiments are fixed, and no new edges or edges are added to the traffic network with respect to changes in time.

• Question 2:

We conducted an ablation study which compares the parameters and the computation time required for training respective models. In comparison to other state-of-the-art techniques, Cy2Mixer unfortunately requires using more parameters while exhibiting non-optimal computation time required for training. Nevertheless, as shown in ablation studies in the manuscript, the preprocessing time required to construct clique adjacency matrix is significantly less than the preprocessing time required to construct DTW matrix. For example, as indicated in Page 8 of the manuscript, generating the DTW matrix for a cyclic graph with 307 nodes takes more than 3 hours, whereas generating the clique adjacency matrix takes less than a minute. In fact, while the preprocessing computation cost for generating the DTW matrix depends on the number of nodes of the underlying traffic network and the complexity of time series data, constructing clique adjacency matrices requires less preprocessing time, in particular at most a minute for all the traffic datasets used for empirical results in this manuscript. We believe that because Cy2Mixer can make efficient use of time in preprocessing traffic datasets, our proposed model has potential to efficiently analyze and forecast traffic datasets in comparison to other baseline models.

We thank the reviewer for providing constructive feedback to our manuscript. Please find our response to the weaknesses and questions posed by the reviewer.

• Weakness 1: As the reviewer kindly pointed out, we made all the relevant clarifications on the notations used in the manuscript.
• Weakness 2: This is a great question. The significance of utilizing cyclic substructures of traffic networks lies in elucidating the restrictions or constraints associated to constructing a global traffic signal throughout any time period $X: \mathcal{G} \times I \to \mathbb{R}^{N \times C}$ from glueing a collection of traffic signals $X_t \in \mathbb{R}^{N \times C}$ obtained from a set of distinct time periods. This fact originates from a mathematical insight from algebraic topology and algebraic geometry that given a topological space Y and a collection of open neighborhoods $U_\alpha$ which satisfies $\cup_\alpha U_\alpha = Y$, the constraints associated to glueing continuous functions $f_\alpha: U_\alpha \to \mathbb{R}^k$ to a unique global function $f: Y \to \mathbb{R}^k$ can be understood from computing topological (or cohomological) invariants of a topological space $Y$. In the context of traffic network datasets, the topological space $Y$ corresponds to the temporal traffic network $\mathcal{G} \times I$, the open neighborhoods correspond to traffic network at a certain time frame $\mathcal{G} \times (t_e - 1, t_e + 1)$, the functions $f_\alpha$ correspond to a constant extension of traffic signals $X_{t_e}: \mathcal{G} \times \{t_e\} \to \mathbb{R}^{N \times C}$ to the space $\mathcal{G} \times (t_e - 1, t_e + 1)$, the function $f$ corresponds to the global traffic signal $X: \mathcal{G} \times I \to \mathbb{R}^{N \times C}$, and the obstructions correspond to cyclic subgraphs of $\mathcal{G} \times I$, namely the temporal interactions among nodes of a traffic network which lie on an identical cyclic subgraph. Theorem 3.1 allows us to reduce the problem of computing cyclic subgraphs of $\mathcal{G} \times I$ to computing cyclic subgraphs of $\mathcal{G}$, which implies that previous techniques which analyzes cyclic subgraphs of any graphs can be also utilized to analyze cyclic subgraphs of traffic datasets. As the author suggested, we made clarifications addressing the comments above after Theorem 3.1 in the updated manuscript.
• Weakness 3: To ensure a fair and unbiased comparison of Cy2Mixer with other baseline models, we applied the same preprocessing steps as indicated in previous baseline models. The empirical results suggest that under the identical preprocessing protocols, Cy2Mixer still exhibits comparable or outperformance in forecasting traffic dataset in comparison to previous baseline techniques.
• Question 2: In Table 5, we added a summary of the number of cycles and the average magnitude of cycles for each traffic datasets. As indicated in the original manuscript, PeMS07 do not possess any cyclic subgraphs unlike any other traffic datasets.

We thank the reviewer for providing constructive comments. We would like to address the weaknesses pointed out by the reviewer as follows.

• Weakness 1: One of the key insights utilized in previous studies, such as utilizing the DTW matrix or utilizing dynamically varying adjacency matrices, is that variations in geometric properties of graphs can clarify restraints or conditions that traffic signals at each time period have to satisfy. These geometric conditions are of great importance in deducing global traffic behaviors from conglomerating instances of traffic signals. In this manuscript, we focus on deducing these geometric constraints by extracting cyclic substructures of temporal traffic networks, the problem of which can be reduced to extracting cyclic substructures of pre-existing edges of traffic networks as shown in Theorem 3.1. These cyclic structures form the backbone of topological invariants of temporal traffic networks, the topological properties of which can be effectively used for traffic forecasting.

  As for real-world applications, consider a cyclic traffic network consisting of 5 destinations A, B, C, D, and E where the edges correspond to roads connecting destinations A-B, B-C, C-D, D-E, and E-A. By using a clique adjacency matrix, which corresponds to connecting all the destination with edges, one is able to understand traffic flow among destinations at different periods of time which do not directly share a road connection, such as understanding traffic flow from destination B to destination D.

• Weakness 2: In Table 5, we added a summary of the number of cycles and the average magnitude of cycles for each traffic datasets. As indicated in the table, we can conclude that our original experimental protocols conduct experiments on traffic graphs with varying proportions of cycles.

• Weakness 3: We utilized identical hyperparameter search processes as suggested in previous studied (in particular PDFormer and STAEFormer), and compared empirical results under identical experimental settings. As for the experimental results obtained from STAEFormer, we added new experimental results obtained from traffic datasets which were not tested in previous studies.