Thank you for engaging in the discussion.
**W2**. While it's true the right plot of Fig. 3 is not tight enough, we should emphasize this is an open research question. Our findings align with previous work in over-smoothing, please refer to Fig. 2 in [1] for example, where a similar loose bound was found.
We now provide insights for possible future directions to find a tighter bound:
- The RHS in Theorem 3.9 also depends on the maximum singular value of the learnable weights matrices $W\_{l1},...,W\_{ll}$, *i.e.*, $s$, which solely depends on the training process. We can use techniques like weight normalization [1] to bound $s$.
- When there's a big gap between the arguments of the Lipschitz functions, we might use integral Lipschitz functions [2] since in that case $|f(x\_2)-f(x\_1)|\le C\frac{|x\_2-x\_1|}{|x\_2+x\_1|/2}$. This is tighter than an absolute Lipschitz function, but its effect on the factor graph spectrums needs further theoretical exploration.
- Previous works have found that the Frobenius norm might not be very tight as an upper bound for the spectral norm [3]. Precisely, $\\|T\\|\le\\|T^K\\|^{\frac{1}{K}}=\sup\_{x\ne 0}{\left(\frac{\\|T^Kx\\|}{\\|x\\|}\right)^{\frac{1}{K}}}=\sup\_{x:\\|x\\|=1}{(\\|T^Kx\\|)^{\frac{1}{K}}}$, for some finite $K$ [3]. Since $E(x)=x^\top L x=\\|L^{1/2}x\\|\_F^2=\sum_{i=1}^{N}{\lambda\_i\tilde{x}^2\_i}$ with $\tilde{x}$ being the GFT of $x$ (which is a weighted nuclear norm with direct relationship with the spectral norm), we might use other norms like Sobolev [4], gradient-adapted [5], or other $p-$norms [4,6].
- Recently, some works have explored alternatives to the regular triangular inequalities [7], which might not be tight for the over-smoothing analysis.
In summary, there are some future directions to make our bounds tighter, but they need to be carefully studied in the case of continuous filters in product graphs.
**Q4**. By robustness, we mean smaller standard deviations in prediction performance as shown in Tab. R1 in the **uploaded PDF file of the main rebuttal**.
Regarding the longer horizons, the authors from the GTCNN model [8] (which can be considered as a particular case of CITRUS for discrete, two-factor graphs) said: "The GTCNN outperforms the other models in a short horizon while Graph WaveNet and GMAN work better for longer horizons. The benefits in the short term are due to high-order spatiotemporal aggregation in the GTCNN which allows capturing efficiently the spatiotemporal patterns in the data". Therefore, we state the GTCNN model doesn't perform well in longer horizons due to the non-optimal receptive field of the discrete case. More formally, consider a one-layer CITRUS network without non-linearity for predicting one horizon as $\tilde{y}=e^{-tL\_{\diamond}}Xw$. The loss function is therefore given by $\min\_{w}{\\|y-e^{-tL\_{\diamond}}Xw\\|\_2^2}=\min\_{w}{w^\top X^\top e^{-2tL\_{\diamond}}Xw-2y^\top e^{-tL\_{\diamond}}Xw}$. Here, the second term tries to maximize the inner product (the similarity) between the target $y$ and predicted output $\tilde{y}=e^{-tL\_{\diamond}}Xw$. The first term $f_{CITRUS}=w^\top X^\top e^{-2tL\_{\diamond}}Xw$ enforces the output to be as smooth as possible on the heat diffusion filters $e^{-tL\_{\diamond}}$. For a simple GTCNN [8], this smoothness term takes the form of $f\_{GTCNN}=w^\top X^\top L\_{\diamond}^2Xw$. If we consider longer horizons, these terms will accumulate leading to bigger smoothness terms in the loss function, likely leading to over-smoothing. The key difference between $f\_{CITRUS}$ and $f\_{GTCNN}$ is that our model learns $t$ to alleviate this accumulation issue as observed in Fig. R3 in the **uploaded PDF file of the main rebuttal**. Please also note that we can also have better control of the spectrum of $f\_{CITRUS}$ because of the learnable heat kernel.
Apart from the role of $t$ in $f_{CITRUS}$, other aspects besides over-smoothing could also play an important role, like over-squashing and over-fitting, which we leave for future work.
References
----
[1] “Graph neural networks exponentially lose expressive power for node classification”, ICLR, 2020
[2] “Stability properties of graph neural networks”, IEEE TSP, 2020
[3] “Learning interface conditions in domain decomposition solvers”, NeurIPS, 2022
[4] “Reconstruction of time-varying graph signals via sobolev smoothness”, IEEE TSIPN, 2022
[5] “Time-varying graph signal reconstruction”, IEEE JSTSP, 2017
[6] “Flow smoothing and denoising: Graph signal processing in the edge-space”, IEEE GlobalSIP, 2018
[7] “Studying the effect of gnn spatial convolutions on the embedding space’s geometry”, UAI, 2023
[8] "Graph-time convolutional neural networks: Architecture and theoretical analysis", IEEE TPAMI, 2023.