Hyperbolic-PDE GNN: Spectral Graph Neural Networks in the Perspective of A System of Hyperbolic Partial Differential Equations

[Cons 1/Q1]: Computational costs under different modules.

[Answer]: The efficiency of the proposed method primarily depends on the choice of the spectral GNN filter. A more efficient filter leads to higher efficiency. Additionally, hyperparameters ($i.e.$, termination time $T$ and time step $\tau$) also affect the efficiency of the model. A smaller $T/\tau$ results in fewer iteration steps and higher efficiency.

[Cons 2]: The impact of different hyperbolic equations.

[Answer]: In essence, this work proposes a spectral GNN framework applicable to a broad class of hyperbolic PDEs. The specific GNN architecture for particular equations can be derived following this framework. In dynamical system modeling, second-order hyperbolic equations are most commonly encountered, characterized by real-valued eigenvalues and wave-like solution behavior.

The computational performance of the constructed GNN primarily depends on the numerical methods employed. The explicit scheme induced by the forward Euler method, when combined with initial conditions, enables rapid iterative solving, whereas implicit backward schemes may result in slower computation speeds. Different hyperbolic equations may exhibit variations in numerical stability. We will further investigate potential subtle distinctions arising from varying forms of hyperbolic equations in future works.

[Cons 3]: The implicit method may work better.

[Answer]: The advantage of the forward Euler method lies in its simplicity and efficiency. The implicit method offers better performance but involves solving linear equation systems, incurring higher costs. Literature [1] demonstrates that the performance improvement brought by the implicit method is small, yet it triggers significant performance costs.

[1] Ben Chamberlain, James Rowbottom, Maria I. Gorinova, Michael M. Bronstein, Stefan Webb, Emanuele Rossi: GRAND: Graph Neural Diffusion. ICML 2021: 1407-1418.

[Q2]: The effect of different polynomials.

[Answer]: As shown in Tables 4 and 5, polynomials such as Bernstein and Jacobi can fit arbitrary filters, making them superior GNNs. Chebyshev polynomials exhibit the Runge phenomenon, leading to the fitting of suboptimal filters. Since our method enhances the capability of polynomial fitting for filters, it results in significant performance improvements for Chebyshev polynomials.

[Sug]: Improvement of writing.

[Answer]: We will consider and incorporate your suggestions into the revised version. Thanks for your comments.

[Cons]: The question about the concept of hyperbolic PDE.

[Answer]: We appreciate your theoretical endorsement for our approach. As you pointed out, the hyperbolic PDE in this paper differs fundamentally from the hyperbolic geometry mentioned in the literature [1,2].

The focus of hyperbolic PDEs lies in constructing the message passing process of GNNs ($i.e.$, $\frac{\partial^2 \mathbf{X}}{\partial t^2} = a^2 \widehat{\mathbf{L}} \mathbf{X}$) based on the theory of partial differential equations. This design can naturally map nodes into a solution space spanned by a set of eigenvectors of the graph, which improves the capability of learning complex graph filters, such as handling the challenging heterophilic graphs.

On the other hand, hyperbolic geometry focuses more on the hierarchical structure of graphs. It typically involves mapping nodes to hyperbolic space using models such as the Poincaré Ball Model ($i.e.$, $d(\mathbf{x}, \mathbf{y})=\mathrm{arcosh}(1+2\frac{||\mathbf{x}-\mathbf{y}||^2}{(1-||\mathbf{x}||^2)(1-||\mathbf{y}||^2)})$) or the Lorentz Model ($i.e.$, $<\mathbf{x}, \mathbf{y}>=-x_0y_0+\sum^n_{i=1}x_ny_n$) to extract hierarchical relationships between nodes.

The essence of the two concepts mentioned above is fundamentally different, with their focus being distinct. To avoid ambiguity for the readers, we will incorporate your valuable suggestions and modify the title as well as the method names in the next version. We will also discuss the distinctions from hyperbolic geometry in related works to avoiding misunderstanding.

Below are our new title and method name for modification: "Hyperbolic-PDE GNN: Spectral Graph Neural Networks in the Perspective of A System of Hyperbolic Partial Differential Equations"

[1] Qi Liu, Maximilian Nickel, Douwe Kiela: Hyperbolic Graph Neural Networks. NeurIPS 2019. [2] Ines Chami, Zhitao Ying, Christopher Ré, Jure Leskovec: Hyperbolic Graph Convolutional Neural Networks. NeurIPS 2019.

[Cons 1]: Slightly lower performance on some datasets.

[Answer]: In this paper, we aim to propose a general framework for GNNs, with the advantage of being applicable to spectral GNNs. The hyperbolic PDE-based paradigm allows the model to learn complex graph filters, generating better results on heterophilic graphs. Extensive results demonstrate the superiority, and reflect a new research direction of GNNs. We leave further improvements in future works.

[Cons 2/Q3]: Complexity and parameter efficiency.

[Answer]: Converting spectral GNNs into a dynamical system may increase the the computational costs, but can also be controlled by hyperparameters (termination time $T$ and time step $\tau$). For instance, when $T=1$ and $\tau=1$, the efficiency is comparable to the original method while performing better. Furthermore, this method introduces no additional parameters apart from the MLP parameters for initializing $\varphi(\cdot)$. Therefore, the cost and efficiency is acceptable and worthwhile.

[Q1]: The theoretical distinctions between different polynomial families.

[Answer]: Different polynomials, such as Chebyshev and Bernstein polynomials, would fit filters based on their mathematical properties. For example, Chebyshev polynomials exhibit Runge's phenomenon, while Bernstein polynomials can fit any function. Experimental results indicate that in graph tasks, learnable GPR performs the best, whereas ChebNetII may excel in image tasks.

[Q2]: Applicability of hyperbolic framework on non-spectral GNNs.

[Answer]: Our method is applicable to non-spectral GNNs. We can simply replace the function $P(\cdot)$ in Equation 17 with any feasible convolution operation such as attention mechanisms, as demonstrated in our enhancement of GAT on image tasks. The effectiveness of this framework depends on whether the base model can effectively adapt to the task. Attention mechanisms can effectively capture the importance levels between pixels, thus Hyperbolic-GAT further improves the performance of GAT.

[Cons 1/2]: Somewhat limited experimental evaluation, and some marginal improvements on a few datasets.

[Answer]: The proposed method is essentially a general framework that enhances the capability of spectral GNNs, as shown in Tables 4 and 5. The results on both homophilic and heterophilic graphs, and the extensive experimets on the low-pass filter and arbitrary filter methods, consistently achieve competitive results. All the analyses comprehensively demonstrate the effectiveness of our method.

On the other hand, our method also demonstrates high interpretability to connect spectral GNNs. It provide high flexibility to implement different spectral graph filters for further improvements, and reflect a new direction of GNN studies.

Thanks for the comments. We will conduct further exploration in our future works.

[Cons 3/Q1]: The lack of the proof of Theorem 3.5.

[Answer]: Theorem 3.5 is a well-known mathematical theory as Weierstrass approximation theorem [1,2], and we will introduce more details and references in the next version.

[1] Stone, M. H. (1937), "Applications of the Theory of Boolean Rings to General Topology", Transactions of the American Mathematical Society, 41 (3): 375–481, doi:10.2307/1989788, JSTOR 1989788.

[2] https://en.wikipedia.org/wiki/Stone%E2%80%93Weierstrass_theorem

[Q2]: Evaluation without graph classification or link prediction.

[Answer]: Actually, our method is a foundational and general framework, which is a task-agnostic graph learning method. The node classification task is a widely-adopted evaluation setting for evaluating the effectivness of GNNs [1,2,3], and thus we follow this setting. The extensive results also reflect the superiority. Thanks for the suggestion, we would like conduct more explorations on link prediction and graph classification in our future works.

[1] Wang, X. and Zhang, M. How powerful are spectral graph neural networks. ICML 2022. [2] Geng, H., Chen, C., He, Y., Zeng, G., Han, Z., Chai, H., and Yan, J. Pyramid graph neural network: A graph sampling and filtering approach for multi-scale disentangled representations. KDD 2023. [3] Zheng, S., Zhu, Z., Liu, Z., Li, Y., and Zhao, Y. Node-oriented spectral filtering for graph neural networks. IEEE Trans. Pattern Anal. Mach. Intell., 46(1):388–402.

[Q3]: Comparison with methods for hierarchical structures.

[Answer]: Actually, our hyperbolic PDE-based GNNs and traditional hyperbolic GNNs are quite different paradigms.

• Traditional hyperbolic GNNs map nodes to hyperbolic embedding space, which can be capable to capture hierarchical structures.
• This paper proposes a new paradigm (Equation 9 and 24) of message passing through a system of hyperbolic PDEs. This paradigm can naturally map nodes into a solution space spanned by a set of eigenvectors of the graph, which improves the capability of learning complex graph filters, such as handling the challenging heterophilic graphs.

Therefore, the motivations, modeling paradigms and properties are different. Please refer to #R3 for more details. Thanks for your suggestions. We will make more discussion in the next version.