ResTran: A GNN Alternative To Learn Graph With Features

• Insufficient literature survey on the related work.
• The novelty is extremely limited. See comments below.
• The claim that existing GNNs can only work well on heterophilic graphs with complicated architecture is false. The authors not only ignore the complete literature of spectral GNNs but also LINKX method.

My first concern with the work is that its literature survey on prior related works is insufficient. Note that one major claim of this paper is that current GNNs can not handle heterophilic graphs if not using complex architecture. However, this is apparent wrong as the line of spectral GNNs research tackles this problem with a very simple design [1,2,3]. Also, LINKX [4] is another simple architecture that has been shown superior performance on heterophilic graphs. Notably, spectral GNNs are shown to be capable of learning ``any’’ graph spectral filtering that is beyond just low-pass (homophily) and high-pass (heterophily) cases. It is surprising that the authors completely ignore this literature.

On the other hand, the idea of obtaining node embedding from node features and graph topology in an unsupervised fashion has also been proposed previously. One of the early model SIGN [5] propose to compute propagated features $X, AX, A^2X,\cdots,A^KX$ first (with $A$ being potentially normalized or use $L$ instead) and concatenate them as the node embedding for applying MLP in downstream tasks. This work has also led to a series of works focusing on scalable graph learning methods such as SAGN [6] and GAMLP [7] with similar ideas. The ResTrans method is just using the embedding $L^{-1/2}X$. Note that one potential drawback of ResTrans is its computational complexity. Indeed, as the authors mentioned, naively compute $L^{-1/2}$ is computationally infeasible. They propose to apply the Krylov subspace method, which essentially computes $X,LX,L^2X,\cdots,L^rX$ and is very similar to SIGN design. It is a surprise to me that the authors completely miss this line of work as well. Compared to these prior works, I think the novelty of the proposed method is relatively limited.

I would suggest the authors explain the difference of their method to at least SIGN and compare them carefully in the experiments. Also, I think the authors should also compare to some spectral GNN baselines such as those in [1,2,3]. Otherwise, it is hard to convince me that ResTrans is a good method for heterophilic graphs.

References

[1] Adaptive Universal Generalized PageRank Graph Neural Network, Chien et al. ICLR 2021.

[2] Bernnet: Learning arbitrary graph spectral filters via bernstein approximation, He et al., NeurIPS 2021.

[3] How powerful are spectral graph neural networks, Wang et al. ICML 2022.

[4] Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods, Lim et al., NeurIPS 2021.

[5] Sign: Scalable inception graph neural networks, Frasca et al. ICML GRL+ workshop 2020.

[6] Scalable and adaptive graph neural networks with self-label-enhanced training, Sun et al. 2021.

[7] Graph attention multi-layer perceptron, Zhang et al. KDD 2022.

I am not sure about the computational complexity of these methods: The authors should have included some experimental results on time complexity to indicate whether the usually expensive eigenvector computations can be justified instead of simple combinatorial message passing.

Spectral embeddings/methods have inherent limitations in the kind of data they can capture from a graph: They fail to capture relational aspects of data (such as node/edge-colors) and so on, unlike combinatorial message-passing algorithms. If the authors propose such a radical departure from standard GNN methods, they should investigate their method on a variety of datasets, such as molecular graphs or synthetic graphs arising from relational sources.

Overall, I found the paper raise more concerns than it claimed to solve. Here are some of my major concerns:

• Not much novelty from traditional spectral clustering methods, most part of the papers are well-known results or naive extension of existing methods.
• Most of the background or preliminaries can be distilled into shorter context or put in appendix such as propositions from previous papers, it’s currently taking more than 2 pages of the main paper.
• No complexity analysis to support the claim that it’s less complicated than GNN.
• Using the shifted graph Laplacian term b to control the heterphilous information in feature map seems to require a lot of fine tuning. How to choose the hyperparameters (b, r, etc) in experiment section is not clear to me, based on the appendix the authors used a fixed value, some ablation study would be nice to see.
• There are multiple works in GNN that already support heterophilous dataset without over-smoothing. The authors’ claim about the lack of GNN is not valid. I would suggest the authors to at least do some comparison with the recent ones.
• Experiment section lack of comparison to more recent GNN works that also targeting at heterophilous datasets.

1. It seems to me ResTran is closely related to 1-layer message-passing neural networks (MPNNs), since it utilizes $L^+$ to transform node features $X$ and it is known that $L^+_{ij}$ represents the effective resistance between two end nodes in the graph interpreted as an electrical network. While traditional MPNNs utilize adjacent matrix $A$ to transform $X$ and have weight 0 when there is no edge between two nodes, I find the key idea is similar, which sounds like ResTran is still in some sense a GNN.

2. I do not really see that ResTran is simpler than existing GNNs. Depending on the definition of complexity, I find the feature transformation is already non-trivial as it includes utilizing Krylov subspace method to approximate the transformed features. After that, from the experiments, it seems it still needs complex neural networks to get decent results, i.e., AVAE, and using simple methods such as SVM does not seem to work.

3. The authors claim that ResTran may not suffer from over-smoothing and can overcome homophilous bias, and I think these need to be further discussed. It appears it is because ResTran only utilizes $L^+$ transforms features once (somewhat like a 1-layer MPNN) that it does not suffer from those issues, but it may come at the cost of the capability of capturing topological information in graphs. More experiments need to be done to demonstrate its capability, for example, comparing ResTran with [1], where some simple tricks were proposed to improve GCNs and, even with different splits, it seems it significantly outperforms ResTran, especially on heterophilous datasets.

4. I am unsure if the comparison is fair. Different from traditional GNNs, which propagate features with $A$, use MLPs to make predictions, and train the network with a classification loss, it seems critical for ResTran to use some semi-supervised models such as VAT and AVAE to get good results. However, the node representations yielded by those GNNs are not trained in the same way, e.g., VAT involves adversarial training--it is known that adversarial training can also further improve GNNs' performance [2].

[1] Chen, Ming, et al. "Simple and deep graph convolutional networks." International conference on machine learning. PMLR, 2020.

[2] Kong, Kezhi, et al. "Robust optimization as data augmentation for large-scale graphs." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.