Graph Scattering Networks with Adaptive Diffusion Kernels

Authors: Toan Van Tran, Hung Son Nguyen
Primary area: learning on graphs and other geometries & topologies
Keywords: graph neural networks, graph scattering transform, deep learning, stability

Abstract:
Scattering networks are deep convolutional architectures that use predefined wavelets for feature extraction and representation. They have proven effective for classification tasks, especially when training data is scarce, where traditional deep learning methods struggle. In this work, we introduce and develop a mathematically sound framework for applying adaptive kernels to diffusion wavelets in graph scattering networks. Stability guarantees with respect to input perturbations are provided. A specific construction of adaptive kernels is presented and applied with continuous diffusion to perform graph classification tasks on benchmark datasets. Our model consistently outperforms traditional graph scattering networks with predefined wavelets, both in scenarios with limited and abundant training data.

Decision: reject
Reviewer scores: 5, 5, 3, 6, 3

Reviews and discussion:
<thread>
creation date:
1730387835534

thread_type:
official_review

<thread_object>
creator: reviewer_pdcq

<content>
summary:
This paper studies graph scattering network, and develops an adaptive kernels in diffusion wavelets. The authors further analyze its stability. The experiments show the general improvements over fixed kernel based diffusion wavelets.

strengths:
1. As the authors mention, most of current scattering networks utilize fixed filter banks. Adaptability is a direction to improve them.
2. This paper is rigorous, giving strict definitions and theorems to support arguments.

weaknesses:
1. Motivation conflict. The authors firstly acknowledged scattering network are advantageous with limited data availability at Line 31-33 because of no required training. However, the main motivation of this paper is to make existing scattering learnable and adaptive, which scarifies the internal advantages mentioned above.
2. Complexity. For a scattering network with $L$ layer and $h$ children for each parent node, the total number of filters is $\sum_{l=1}^{L}h^l$, an exponential function. If we make all filters learnable, the computing is very high and unbearable.
3. Experiments. The baselines are too old. More graph scattering methods are suggested to compare.
4. Writing. Starting from section 4, all following equations do not have a mark.

questions:
The authors prove propositions 4.1 and 4.2, Lemma 4.1 and Theorem 4.1. However, only proportion 4.1 describes the proposed adaptive kernel, with language, while the other three prove something for general diffusion wavelet. Therefore, I am not sure their values for this paper, and if these general conclusions have been similarly proposed by previous papers.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730480261936

thread_type:
official_review

<thread_object>
creator: reviewer_5wjq

<content>
summary:
This paper seeks to develop a generalized graph scattering transform which learns the transition matrix $A$ through a kernel inspired by the attentional diffusion method from Chamberlain et al. (2021). 

They take the initial node features $g_u$, map them into an embedding space by a learnable function $W$ and then build a diffusion operator via a kernel derived from the \{W(g_u)\}_{u\in V} and further add in learning of the diffusion operator via a multiheaded attention mechanism. 

After the attention mechanism, they then use the diffusion matrix $A$ to define diffusion wavelets of the form $\psi_j=A^{t_{j-1}}-A^{t_j}$ and use these wavelets to define a graph scattering transform. (This part is ``standard” and similar to other works such as Gama et al. (2019a) and Gao et al. (2019).) Additionally, they prove that their generalized graph scattering transform has similar theoretical properties to other versions of the geometric scattering transform and show strong numerical performance.

Overall, I think this is a good paper which needs a bit of work before it is publication worthy as described below. If these concerns are sufficiently addressed, I will likely raise my score.

strengths:
The geometric scattering transform (GST) provides a theoretically solid framework for understanding multi-scale GNNs from a graph signal processing point of view. However, the original versions of it are limited in their numerical effectiveness because they are overly handcrafted. This paper shows viable ways of increasing the effectiveness of the (GST) while retaining its nice theoretical properties. This therefore helps bridge the gap between ``things that work well” and ``things which are well understood” which is important since GNNs etc are increasingly used in real-world tasks.

weaknesses:
Right before the start of Section 4, I think $v$ should be defined in terms of the square-root of the degree vector (since you are using the symmetrized diffusion operator).

The discussion of Forward Euler etc in the end of Section 4.1 seems out of place in this paper. While it is indeed a useful insight from GRAND etc., I don’t see its relevance on diffusion wavelets which are already in discrete time

It seems to me that you should be able to take $N(\beta_A)=1$ 1 in Proposition 4.2 by imitating the proof of Proposition 4.1 of Gama et al. (2019a). (It might also be useful to look at the proof of Proposition 2.2 of Perlmutter et al `` Understanding Graph Neural Networks with Generalized Geometric Scattering Transforms” (2023).) I believe this would then allow you to establish the stability your method to additive noise (as is common in most formulations of the scattering transform).

Related Works:

Important: The second paragraph omits `` Graph Convolutional Neural Networks via Scattering” (Zou and Lerman 2020). This omission is particularly noteworthy because it is the first paper on graph scattering, predating Gama et al. by a couple of months. (The final publication date is later, but this is an artifact of the journal review process.)

Less important: Additionally, the discussion of incorporating learning into geometric scattering (Section 5) should likely also include ``Overcoming Oversmoothness in Graph Convolutional Networks via Hybrid Scattering Networks” (Wenkel et al. 2022). This paper introduced learning into the scattering framework in a different way than the Tong et al. paper that the authors mention. (As noted in Tong, these two forms of learnable scattering, as well as this one, are compatible and can be combined.) It also should likely include `` Scattering Networks for Hybrid Representation Learning” (Oyallon et al. 2018) and `` Separation and Concentration in Deep Networks” (Zarka et al. 2020) which incorporate learning into Euclidean scattering.

Notational inconsistencies:

There is inconsistent use of ``x” vs ``u” in Section 4.1

$A^*$ is used without being defined. Also, why do you use both $^*$ and $^T$ in equation 2? If the matrices are real this should be the same, right? 

In line 221, it would be more natural to call $p_\epsilon$ instead $d_\epsilon to be consistent with the proceed paragraph (or instead call them both $p$)

Very Minor: (Do not affect my score but should be fixed)

Line 54: ``we pursue on alleviating” is awkward. Please rephrase.
Throughout: Things like ``Section 5” are proper nouns and should be capitalized.
Throughout: Some quotation marks point the wrong way (which is an unfortunate artifact of LaTeX sometimes being a pain)

Throughout, some of the equations with $e^{stuff}$ are hard to read and it would be better to write $\exp(stuff)$.

questions:
Why do we need a metric space, in addition to the measure space? Chew et al. `` Geometric scattering on measure spaces” (2024) should that the geometric scattering transform could be extended to measure spaces where there was not an obvious metric structure (e.g., digraphs). 

In Section 3.1, what norm is being used? This is relevant because $P$ is an asymmetric matrix (which is similar to \overline{P} used in Section 3.2). In Perlmutter et al `` Understanding Graph Neural Networks with Generalized Geometric Scattering Transforms” (2023) it was shown that the natural choice of norm differs depending on whether one uses a symmetric or asymmetric diffusion matrix (for asymmetric matrices you should use a norm weighted in terms of degrees).

In Section 3.1, could you provide examples of when there we be a strict inequality in line 140? It seems to me that in most cases, this will be equality. For the standard diffusion matrix, I believe that the bottom eigenspace will be zeroed out in the limit, but the other eigenspaces are never fully suppressed (which is why you need epsilon in the next paragraph). 

Could the authors please provide examples of setting where having dependence on the sampling density is preferable (as claimed in line 226, ``Naturally…”)? I thought this was typically a nuisance which one would attempt to normalize out (as in line 222).

The unnumbered equations in lines 246-251 are hard to understand. Could the authors please provide some intuition?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730617605050

thread_type:
official_review

<thread_object>
creator: reviewer_pjh1

<content>
summary:
This work introduces a method for incorporating adaptive kernels into graph scattering networks. The paper provides theoretical stability guarantees against input data perturbations, ensuring robustness. Experimental results demonstrate that adaptive kernels offer advantages over traditional scattering networks.

strengths:
1. The theoretical analysis to support the advantages of the adaptive wavelet diffusion.

weaknesses:
1. The authors highlight the limitations of traditional methods under low-data scenarios. However, the paper lacks theoretical analysis or specific experiments tailored to illustrate how the proposed adaptive kernel-based scattering networks (AGSN) address performance in data-scarce environments.

2. The experimental results reveal that AGSN does not outperform some well-known graph classification techniques.

3. The limitation of The Related Works. There are some works also related to adaptive kernels for graph neural networks, such as [1-2]. It is not clear the advantages of the proposed adaptive wavelet diffusion compared to others.

[1] Sun, C., Hu, J., Gu, H., Chen, J. and Yang, M., 2020. Adaptive graph diffusion networks. arXiv preprint arXiv:2012.15024.

[2] Zhao, J., Dong, Y., Ding, M., Kharlamov, E. and Tang, J., 2021. Adaptive diffusion in graph neural networks. Advances in neural information processing systems.

4. The paper lacks the complexity analysis.

questions:
What are the advantages of the proposed adaptive wavelet diffusion compared to other methods [1-2] ?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730639375628

thread_type:
official_review

<thread_object>
creator: reviewer_vrop

<content>
summary:
This paper proposes a mathematically sound framework for applying adaptive kernels to diffusion wavelets, thus overcoming the limitations of traditional graph scattering networks with predefined wavelets.

strengths:
* Considering the importance of selecting an appropriate kernel, it is promising to develop a framework for application of adaptive kernels in graph scattering networks.

* The proposed framework is bulit on mathematically sound foundation, and stability guarantees with respect to input perturbations are also provided, thus enhanceing its rationality and reliability.

* The experimental results also demonstrated that it consistently outperforms traditional graph scattering networks.

weaknesses:
The main problem with this paper is that its experiments are not convincing enough.

* Baselines:
    * Given that graph deep learning has developed rapidly in recent years, this paper lacks comparisons against the latest graph deep learning methods.
    * More importantly, some typical graph scattering transform methods are not employed and compared in the experiments, such as GS-SVM [1] and GGSN+EK [2].

* The experimental results can not support the clained superiority. 
Although the authors have given some explanations, why not further conduct some experiments to prove it? 
For example, it's necessary to report the performance of deep learning methods when low training-data availability to prove the meaning of this work.

[1] Gao F, Wolf G, Hirn M. Geometric scattering for graph data analysis[C]//International Conference on Machine Learning. PMLR, 2019: 2122-2131.

[2] Koke C, Kutyniok G. Graph scattering beyond wavelet shackles[J]. Advances in Neural Information Processing Systems, 2022, 35: 30219-30232.

questions:
Please see the **weaknesses** part.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730697095724

thread_type:
official_review

<thread_object>
creator: reviewer_zgfs

<content>
summary:
This paper introduces Graph Scattering Networks with Adaptive Diffusion Kernel, which enhances traditional graph scattering networks by incorporating learnable kernels while maintaining mathematical soundness. The novel part is that it bridges the gap between fixed wavelet transforms and learnable architectures while preserving mathematical guarantees.

strengths:
1. the authors propose a novel framework that  incorporate learnable kernels in graph scattering networks.
2. prove that the adaptive kernels maintain symmetry and self-adjointness
3. provide stability analysis for learnable kernels

weaknesses:
1. As far as I understand, the adaptive kernel is restricted to self-adjoint operators for mathematical convenience.
2. The weak performance raises questions about whether the theoretical advantages of the approach translate to practical benefits.
3. The fundamental question "Why adaptive scattering?" is not convincingly answered in the paper. The theoretical contribution might be interesting, but its practical necessity and benefits are not well established.

questions:
1. What's the running time compared with other GNN methods, Could you provide runtime comparisons with baselines?
2. In what scenarios does adaptivity help/hurt performance? why we need adaptivity?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732511105801

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response by Authors

comment:
Dear AC and Reviewers,

We would like to say thanks to all the reviewers for their time and effort to review our work. The thoughtful reviews and constructive feedback help us to improve the paper significantly. We are encouraged to see the recognitions that our work is novel (zGfS), promising (vroP), rigorous (PdCQ), demonstrates general improvements over traditional methods (pJh1, PdCQ), and helps bridge the gap between things that work well and things which are well understood (5wJQ). We have updated the manuscript based on the reviewers' feedback and suggestions. 

One of the common concerns is about the experiments and AGSN does not outperform other graph deep learning methods. We would like to address this by clarifying that our main focus of this paper is to improve on traditional graph scattering, which is usually used in low-data scenario as a feature extractor. In our additional experiments in such scenarios, AGSN+MLP shows considerable performance gain compared to both traditional graph scattering (GSN+MLP, GS-SVM) and graph deep learning methods (GIN-0 (MLP-sum), UGformer). We also would like to clarify that the results in Table 1 are provided to show how graph scattering methods are still outperformed by graph deep learning in abundant data scenarios (90\% used for training). These results are added to provide a broader view. 

Additionally, there might be some confusion about the restriction on the adaptive kernels, and our theoretical contributions. We would like to clarify that the kernels do not need to be self-adjoint in our theoretical analysis. This thus lays a foundation for scattering networks using important diffusion operator in such class, and also other more general adaptive designs. We have revised our manuscript to make this clearer. 

___

We have updated our manuscript to address the comments and questions of the reviewers:
+ Following the comments of reviewers vroP, pJh1, and PdCQ, Section 6 has been updated with additional experiments in low data scenarios with other graph deep learning and scattering methods. We have included other graph scattering methods (GS-SVM, GGSN+EK) to Table 1 for comparison in abundant training data scenarios (suggested by reviewer vroP and PdCQ).
+ Following reviewers zGfS and PdcQ comments, we have revised Sections 1, 4, and 7 to highlight and make clearer our motivations and main contributions in this work.
+ As reviewer 5wTQ pointed out, the discussion on discretization schemes may seem irrelevant. We have included additional experiments in Appendix A.6 to show the effect of schemes and time step choices on the training process and performance of the model, similar to adjusting the learning rate.
+ Following reviewers pJh1, PdCQ, and zGfS comments, we have added the complexity analysis in Section 4.5, and runtime experiments in Section 6.
+ Following reviewers 5wTQ comments, we have added more discussions on other ways of incorporating adaptivity to scattering network, both in graph and Euclidean domains.
+ To maintain the focus of the paper, and leave space to address reviewers' comments, we have moved the discussion on temporal discretization schemes to Appendix A.1, and Table 1 to Appendix A.6 for additional experiments, with a discussion and pointer in Section 6.
+ We have fixed all typos and notational inconsistencies.
___

We are glad to answer any additional question you have on our submission.

Thank you,

Authors
</content>
</thread_object>

</thread>
<thread>
creation date:
1733079101257

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response by Authors

comment:
We would like to thank all reviewers once again for their thoughtful feedback and constructive comments.

We would greatly appreciate it if you could let us know if there are additional questions or concerns before the end of the discussion period. 

We are happy to engage in any follow-up discussion or address any additional comments.
</content>
</thread_object>

</thread>


Metareview:
metareview:
In this submission, the authors proposed a new graph kernel-based learning method with some theoretical guarantees. However, the reviewers and AC have concerns about the inconsistency between the claimed theoretical superiority and the practical performance achieved by the proposed method. Although the proposed method outperforms representative graph kernel methods, it seems inferior to GNN-based competitors in terms of both runtime and accuracy. 

In the rebuttal phase, the authors claimed that the proposed method works well when over 90% of data are used for training. However, such a setting is often infeasible in practice. In addition, the datasets (e.g., MUTAG and IMDB-B) considered in this submission are over-simplified. To demonstrate the usefulness of a kernel-inspired graph learning method, it is necessary to test it on large-scale graph datasets. In summary, the authors should enhance the performance of the proposed method, and the submission requires a next-round review.