Towards Generalization under Topological Shifts: A Diffusion PDE Perspective

1. The theory part contains several flaws. First, the current proof of theorem 3.1 appears incorrect, as U should be unknown. Without conditioning on U, X, A and Y are all dependent, causing the whole proof to fail. Moreover, corollary 3.3 and proposition 3.4 show upper bounds for D_{ood}, while theorem 4.1 considers the lower bound (through explicit constructions). Therefore, these theoretical results are not comparable. Finally, a smaller but still important issue is that the assumption regarding the bijectivity of g is actually very strong. While there may be other potential issues, these are already crucial ones.

2. Even if the theory is correct, it only provides (loose) bounds on the generalization error. It is difficult to determine whether any of these results will hold in practice. The tightness of these bounds could be evaluated using synthetic datasets, if possible.

3. There exists a whole line of work exploring when GNNs perform better than MLPs (answer: not always) [1-4]. These works essentially suggest that concatenating the latent space returned by GNNs and MLPs may lead to better overall performance. As this work also directly considers a hybrid architecture (by combining GNNs and global attentions), one may speculate that the performance gain comes from this combination, rather than the explanation provided in this paper. Additional discussions and experiments should be provided to address this point. The difference between ADIT and GNN + attention should also be highlighted.

4. The experimental results do not convincingly demonstrate ADIT's superiority or support the arguments regarding generalization. For example, I expect that several methods (GCN, GAT, SGC...) would perform well on various synthetic data tasks, and the Diff-nonlocal baseline would achieve optimal performance in DPPIN node regression. Overall, since generalization itself is difficult to define, the authors should consider potential improvements in their real data experiments.

[1] Ma, Yao, et al. "Is Homophily a Necessity for Graph Neural Networks?." International Conference on Learning Representations.

[2] Gomes, Diana, et al. "When Are Graph Neural Networks Better Than Structure-Agnostic Methods?." I Can't Believe It's Not Better Workshop: Understanding Deep Learning Through Empirical Falsification. 2022.

[3] Dong, Mingze, and Yuval Kluger. "Towards understanding and reducing graph structural noise for GNNs." International Conference on Machine Learning. PMLR, 2023.

[4] Luan, Sitao, et al. "Revisiting heterophily for graph neural networks." Advances in neural information processing systems35 (2022): 1362-1375.

1. While the authors show that the error bond can be reduced by the proposed model (which is a relatively new aspect), the model architecture, e.g., attention and diffusion, is not novel.

2. The newly proposed model has a closed-form solution (e.g., mentioned in section 4.1), and it is believed that similar results can be achieved by those spectral GNNs since essentially the model is equivalent to the spectral filtering on a fully connected weighted graph plus a sparse graph that originally given, e.g., equation 9 and its closed form solution. However, lack of comparisons can be found via the empirical studies.

3. It is found that the theoretical assumption/claims may be hard to be verified via the practical experiments.

The data generation model (Sec 3.1) is based on the implicit assumption that the graph is a finite realization of a graphon. However, the theoretical motivation is based on the assumption that GNNs are effectively PDE on Riemannian manifolds. The paper would be much stronger without this inconsistency, e.g., if the data generation model also assumed the graphs were generated from manifolds. (One could probably replace W with the heat semi-group P=e^{-tL} or something.)

It's unclear what the implied constants (from the big-O) notation depend on in Theorem 3.1. In particular, if they depend on the Lipschitz constant of the classifier $\phi$ that would significantly weaken the result since this quantity is hard to control.

In, e.g., Proposition 3.2, it is unclear what $\|A\|_2$ means. Is it the Frobenius norm or the $\ell^2$ operator norm?

The assumption of conditional independence in Prop 3.4 is very strong to the point where it likely renders the result uninteresting. (To be fair, the authors acknowledge this as a potential weakness.)

Equation 8 does not seem to be the natural generalization of (7) to the graph setting. Instead V should be some sort of ``graph vector field” defined on the edges of the graph (where you would likely need to involve the incidence matrix as well).

I don’t think the theory implies, from a qualitative point of view, what the authors believe it implies. Yes, the upper bounds in Corollary 3.3 are somewhat weak. However, corresponding lower bounds are needed in order to ensure that this is a real limitation of GRAND-style networks rather than an artifact of the analysis. Indeed, the experiments in Table 3 actually show sublinear deterioration, which seems not so bad.

Additionally, I don’t think that Theorem 4.1 shows that the proposed model addresses these concerns. It’s a Universal-Approximation-based” argument which shows that a good model exists. However, I am unconvinced that if a model is trained on distribution 1, it will learn a model that actually works well on distribution 2. Instead, I think it will likely learn the model which is best for distribution 1, which may or may not be the good model” guaranteed via universal approximation.

This isn't a significant weakness, but the conclusion that extending the diffusion operator to a non-local counterpart improves generalization feels somewhat intuitive. It would be valuable to explore whether the analysis can yield additional, deeper insights beyond this.