Centrality Graph Shift Operators for Graph Neural Networks

1. The novelty of this paper is limited. The proposed CGSOs incorporate some established metrics, but their performance is comparable with that of some basic methods, such as GCN.
2. The cost of CGSOs is excessively high for large graphs due to their quadratic complexity in computing the PageRank score.
3. The CGSOs contain numerous scalar parameters that require training, which presents a significant challenge in achieving optimal results.
4. Notably, another category of polynomial-based GNNs, such as GPRGNN[1] and BernNet[2], can learn the GSO directly and demonstrate superior performance in real-world tasks.
5. The baselines used in the experiments are outdated. For the spectral clustering task, recent methods should be included for comparison. Similarly, for the classification task, newer methods like GCNII[3], GPRGNN[1], and UniFilter[4] should also be considered.

[1] Chien, Eli, et al. "Adaptive universal generalized pagerank graph neural network." In ICLR, 2021.
[2] He, Mingguo, Zhewei Wei, and Hongteng Xu. "Bernnet: Learning arbitrary graph spectral filters via bernstein approximation." In NeurIPS, 2021.
[3] Chen, Ming, et al. "Simple and deep graph convolutional networks." In ICML, 2020.
[4] Huang, Keke, Yu Guang Wang, and Ming Li. "How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing." In ICML, 2024.

The benefits of CGSOs have not been sufficiently verified by experiments.

1. This work "considers a learnable parameterized CGSO framework which is a generalization of the work of Dasoulas et al. (2021)". However, there is no comparison to PGSO (Dasoulas et al., 2021).
2. Besides, there is no comparison to other "parameterized GSO" works. There are several works that do not identify themselves as parameterized GSO but actually match the Definition 2.1, such as Directional Graph Networks (Beani et al., 2021), ACM (Luan et al., 2022), PEGN (Wang et al., 2022) and the 1-hop variant of CKGConv (Ma et al., 2024).
3. No demonstration of retaining the original connectivity is crucial, which is the main advantage of GSOs. A simple study on memory or runtime is expected for CGSOs compared to PPNP and APPNP (Gasteiger et al., 2019). What is the computation and performance trade-off?

Based on the aforementioned, I am not fully convinced that introducing global centrality is the key point of the improved performance. Alternatively, it is natural to suspect that the improvement is from parameterized GSO, allowing high-pass filtering, rather than the global centrality, since

• 5/8 datasets are heterophily graph datasets;
• no significant outperformance on the homophily graphs, CiteSeer and PubMed, compared to GCN w/ $\hat{\mathbf{A}}$.

• Beani, D., Passaro, S., Létourneau, V., Hamilton, W., Corso, G., & Lió, P. (2021). Directional Graph Networks. Proc. Int. Conf. Mach. Learn., 748–758.
• Luan, S., Hua, C., Lu, Q., Zhu, J., Zhao, M., Zhang, S., Chang, X.-W., & Precup, D. (2022). Revisiting Heterophily For Graph Neural Networks. Adv. Neural Inf. Process. Syst., 35, 1362–1375.
• Wang, H., Yin, H., Zhang, M., & Li, P. (2022). Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks. Proc. Int. Conf. Learn. Represent. International Conference on Learning Representations.
• Ma, L., Pal, S., Zhang, Y., Zhou, J., Zhang, Y., & Coates, M. (2024). CKGConv: General Graph Convolution with Continuous Kernels. Proc. Int. Conf. Mach. Learn.

1. Limited Comparisons with Strong Baselines: While the paper demonstrates the effectiveness of CGSOs within traditional GNN models (such as GCN and GATv2), it lacks comparison with more recent and competitive methods, like Graph Transformers and other strong GNN baselines. Including such comparisons could have provided a clearer perspective on the advantages and limitations of CGSOs relative to state-of-the-art models, particularly those that also incorporate global graph structure.

2. Inconsistent Performance Across CGSOs: The performance of the models varies significantly depending on the CGSO used, with no single centrality metric consistently outperforming the others across datasets. This inconsistency suggests that the choice of CGSO might be heavily dataset-dependent, potentially complicating its practical application, as users would need to test different CGSOs to identify the most suitable one for their specific data. Many times also a simple degree Graph Shift Operation outperforms many of the more complicated CGSOs proposed in this work. This could limit the overall generalizability and efficiency of the proposed approach.

3. Many Hyperparameters: The proposed method introduces many hyperparameters, specifically those introduced in Equation 4, making hyperparameter optimization challenging.

4. Potential Bias in Evaluation: The authors have used two-layer GNNs for all comparisons. This limits the GNNs' power to local information, while CGSOs provide more global information even for shallow GNNs.

Minor point: Line 471: Singless should be corrected to Signless.

Unfortunately I see several weaknesses in the paper as it currently is:

To me the most important point is the disconnect between the theoretically studied Markov averaging operator (line 192) and the experimentally investigated CGSO (eq. (4) / line 285). As far as I can tell, the theoretical results only apply to the CGSOs for which $m_1, e_3, m_3 = 0$. This severely limits the applicability of the theoretical results.

It also seems that a more inclusive theoretical characterisation of such CGSOs is not out of reach: For the degree-normalization, this was e.g. achieved in https://arxiv.org/abs/2101.10050 (c.f. ibid. Section 4).

It should also be stated clearly in the present paper, that parametrising the graph shift operator as in eq. 4 is not novel: It arises from Ideas in https://arxiv.org/abs/2101.10050 by replacing the degree normalization with a more general centrality normalization (otherwise both papers use a similar labelling of parameters, leading me to believe that the authors are aware of the earlier work).

The claim that the layer update rule specified in eq.s (1) and (2) encompasses the entirety of message passing models is not correct, as the message function considered here e.g. does not depend on the respective node features. While it is of course valid to restrict an analysis to a certain model subclass, this needs to be clearly stated. Also, I am unsure how (2) refers to the update step; to me this equation describes channel mixing. Could the authors clarify?

As for the theoretical analysis, I am unfortunately unsure about both validity and significance of claims: In Proposition 3.1, all results except the upper bound on the spectral radius are straight forward results from linear algebra. In Proposition 3.2, I am unsure whether the given expression of the mean of the eigenvalues is correct: The given Markov averaging operator has all diagonal entries zero. Hence the trace (computed in the weighted $L^2$ space of Section 3.1) is zero. Hence the sum and thus also the mean of the eigenvalues is zero. Are self loops considered here? Also the subscript $\phi$ in this theorem is undefined as far as I can tell.

In the experimental section, it would be good to highlight the performance gain that choosing a different normalization (i.e. centrality metric) and parametrisation of the GCSO can bring over the base model.

Also, in the paragraph on baselines, the GSO for GCN is included without self-loops. This is not the standard matrix used in GCN. Is this merely a typo?

While it is interesting to see the performance gain for GCN and GAT(v2) these methods, while standard) are fairly old by now (three to eight years). It would be good to compare with at least some more recent or SOTA methods.

Additionally, it seems straightforward to combine the GCSO with at least one spectral method, such as e.g. ChebNet or BernNet, as these methods rely heavily on graph shift operators.

In the introduction section, I believe the historical remarks on matrix representations of graphs are superfluous. To me, this would be interesting trivia in a textbook setting. In a paper setting, I believe these column inches are better spent elsewhere.

While I like the premise of the paper, the weaknesses of the paper currently overweigh in my estimation