Laplace-Transform-Filters render spectral Graph Neural Networks transferable

In Section 4, it is briefly discussed that typical polynomial filters would diverge due to that the norm of  on the graph  tends to infinity (since ). Could authors elaborate on this? The spectral norm of a graph Laplacian should be bounded, so I do not directly see this.

We are very glad to oblige and elaborate on this! While each fixed (finite dimensional) Laplacian of course has bounded spectral norm, the spectral norm of the un-normalized Laplacian (sometimes also referred to as the combinatorial Laplacian) is not uniformly bounded: Considering the graph of two nodes connected by an edge with weight $\omega$.  It is not hard to see that the spectral norm of the corresponding Laplacian is given as $||L|| = \lambda_{\max} = 2 \cdot \omega$. Let $v$ be the normalized eigenvector associated to this eigenvalue  $\lambda_{\max}$. Then we have

for any (non-trivial) polynomial, as $w$ tends to infinifty.

It should also be noted that the lack of uniform boundedness of the graph Laplacian is not an issue if the correct class of filters is being employed: One way of achieving stability in a spectral convolutional network is certainly to demand the Laplacian be sufficiently bounded. However, ultimately what needs to be bounded to achieve stable networks, is the norm of the filters $||g(L)||$. If polynomial filters are employed this indeed directly translates to the requirement that the norm of $L$ needs to be sufficiently bounded. For non-polynomial filters such as resolvents or exponentials, this however is not necessary. We e.g. have

irrespective of the norm of $L$; which might be arbitrarily large.

Moreover, this seems to contradict the claim by Transferability of Spectral Graph Convolutional Neural Networks, JMLR 2019.

We understand how initially this might indeed seem to be the case. However our results coexist in perfect harmony with those of Levie:

In Levie's work, filter functions are assumed to be  bounded ($\sup_x|g(x)| = 1$) and Lipschitz continuous with Lipschitz constant $D<1$ on the spectrally relevant part of $\mathbb{R}$ (c.f. e.g. Theorem 17; page 17; ibid.). For e.g. the unnormalized graph Laplacian approximating an (unbounded) Laplace-Beltrami operator on a manifold, this spectrally relevant part is the non-negative real line. Polynomials are neither globally Lipschitz nor bounded on $\mathbb{R}_{\geq 0}$.
Thus Levie's (nonetheless very fundamental) work does not make statements about networks based on polynomial filters in the setting of unbounded graph shift operators (such as e.g. a sequence of Laplacians approximating the (necessarily unbounded) Laplace-Beltrami operator in the setting of Levie's paper).
Hence, as Levie does not make statements about polynomial filters in the setting of unbounded sequences of graph shift operators, our claim that polynomial filters are not transferable in this setting  does not contradict any of Levie's results.

We thank the reviewer for raising this important question. Following this feedback, we have included a more detailed discussion of Levie's work in Appendix B of our submission. The reviewer might also be interested on our response to Reviewer DCXz where we further discuss the relation of our results to those of other existing works.

Thank you very much for your thorough review of our paper!

We were very happy to read that

The paper is well-written

and that

the experiments are well-conducted.

Let us discuss the raised points individually:

An obvious limit is that the class of filtering functions is limited to the class of low-pass filters, [...] the transferability may not hold in general setting, as spectral GNNs may learn also high-pass filters.

The review is spot on in recognizing that transferability is not established for all filter functions! This is in fact a main finding of our paper:

 Not all filter functions will lead to architectures that are able to transfer in all settings.

As remarked by the reviewer, on undirected graphs a frequency interpretation is available. Here one might interpret our findings as only (certain) low pass filters facilitating bi-directional transferability. Additionally (certain) all-pass filters (or more precisely filters that are constant on large frequency components) will lead to mono-directional transferability (c.f. the discussion in Section 4.2; esp. Line 289ff.).

Heuristically we might understand this result from a spectral graph theory perspective: It is well known (Chung 1997) that the low lying spectral information of the graph Laplacian corresponds to coarse structures within a graph. Large eigenvalues instead correspond to fine structure details. We want networks to be transferable between graphs that are approximately the same. Such graphs may differ greatly in their fine structure details, but generically will have similar rough structures within them. That is to say, the low lying spectral information within these graphs will be similar, while the high lying spectral information may be very different. Low pass filters will suppress the variations in the large eigenvalues while letting the approximately similar low lying spectral components of the respective Laplacians pass. This heuristically motivates while it is these filters that can be shown to be transferable. A similar line of argument motivates why also all-pass filters but not high pass filters can be transferable in this undirected setting.

For directed graphs, a frequency perspective is no longer straightforwardly available. Nevertheless, also here we may characterize the class of filters yielding transferable networks.

In both settings, it is the class of Laplace transform filters that renders spectral graph convolutional networks transferable. This fact informed the choice of title of our paper: Laplace transform filters render spectral graph neural networks transferable.

    Two important works on transferability of GNNs are not well-discussed:

1.               Convergence and Stability of Graph Convolutional Networks on Large Random Graphs

2.               Graphon Neural Networks and the Transferability of Graph Neural Networks

This is an important point; thank you for this valuable feedback. Following this advice, we have now created a dedicated Appendix (c.f. Appendix B in our updated manuscript), where we discuss in detail other approaches to transferability as well as the relation of our results to them.

For the second work, the author only mentioned it is limited to the (very) large graph setting. This is not true. The work in fact discussed a general setting that goes beyond the graph coarsening.

Analyzing GNN transferability with the help of auxiliary graphons is of course a fundamental and well established approach to transferability. Nevertheless, the convergence rate in Theorem 1 of the paper mentioned by the reviewer is given as $\sim C/N^\frac12$ with a potentially large constant $C$ (e.g. dependent on spectral separation properties of the graph at hand). This result – while fundamental-- e.g. does not make meaningful predictions in the setting of smaller graphs such as the molecular graphs of QM$7$. Our approach instead is not dependent on any type of limit object being approximated sufficiently well. Hence it also applies here – as well as other settings outside the coarse graining setting -- without restrictions.

<!-- 1. The similarity of graphs from the diffusion perspective. Is this really a novel perspective? -->

The notion of diffusion similarity was indeed established already in 2013 by Hammond et. al., as we discuss in our paper.

To the best of our knowledge, however, our work is indeed the first one to investigate the transferability of graph neural networks between graphs that are similar from the perspective of information diffusion. Hence, we do indeed provide a novel perspective on transferability.

To incorporate this feedback and avoid any potential ambiguity, we have changed the sentence

"Transferability of graph neural networks is then considered between graphs that are similar from this novel perspective of information diffusion."

in the abstract (to which we assume you are referring) to read

'Transferability of graph neural networks is then considered between graphs that are similar from this novel perspective on transferability.'.

The fundamental reason why  has pitfalls in measuring the similarity between two Laplacians comes from that the spectral norm is a poor measure. Sometimes, Frobenius norm, as the sum of the eigenvalues, might be a better measure, but still limited. Fundamentally, one could really compare how similar two graphs are by checking the full difference matrix .

We fully agree with the reviewer that certain distance measures are more adapted to certain task-settings than others.

However, as we argue below, neither spectral or Frobenius norm, nor the full difference matrix are well adapted to capture the type of similarity captured by the notion of diffusion similarity. To exemplify this, let us revisit the rewiring setting of clique vs. dumbbell graphs in Fig.s 1 & 2. Irrespective of where an edge is deleted, the difference matrix (w.l.o.g. after relabelling nodes) reads:

What would be interesting here is to show what theoretical insights and advantages this particular case analysis provides over the more general case. Unfortunately, insights in this regard are limited or inexistent in the paper.

We are happy to list some examples of the insights and advantages of our transferability analysis:

1. Our work applies to transferability settings not covered by existing approaches (c.f. also the discussion above)
2. We provide a quantitative similarity notion (i.e. diffusion similarity) adapted to the setting of graphs that are approximately similar, but different in fine structure articulation. We also discuss how existing approaches fail in this setting and discuss implications for transferability.
3. We discuss that polynomial filters will not be able to transfer in the considered settings; a fact sometimes not appreciated in the community. Indeeed, we believe that also the reviewer was curious about this in their initial review and asked whether this finding does not contradict results of Levie et al. (2019) (c.f. also the discussion above).
4. We characterize the class of filters that is able to transfer between graphs that are approximately similar, but different in fine structure articulation. Such a characterization had not been done before in the literature.
5. We provide (non asymptotic) quantitative bounds for these novel transferability settings and more generally for the setting of graphs that are approximately similar, but different in fine structure articulation.
6. We distinguish between mono- and biderictional similarity and classify the class of fillters that will facilitate transferability in the respective senses. We find that not all filters are bidirectionally transferable, which had not been appreciated in the community before.
7. We consider transferability of undirected and directed graphs on an equal footing, while the vast majority of existing approaches focuses solely on the undirected setting.
8. We relate transferablity to continuity of models: Models conforming to our developed theory are continuous from the space of graphs to Euclidean latent spaces; models not conforming to our theory are shown to be not conitnuous: If for esxample a sequence of graphs converges to a coarse grained graph defined on fewer nodes in the diffusion sense, latent embeddings generated by models conforming to our developed theory will converge to the latent embedding of the coarser graph. This is not true for other models (c.f. also Figure 10).
9. Our analysis is not contingent on an underlying limit object that is sufficiently well discretized. Hence it also applies to small to medium sized graphs. This is e.g. exemplified in Section 5.1 (c.f. also line 404ff).
10. Our analysis allows in practice to build models that experimentaly are able to transfer where existing models are unable to transfer: In Table 1, only models conforming to our theory are showcasing transferability. Thus our results have tangible practical relevance when designing new architectures.

And how the latter analysis ties to the more general ones as well as to the ideas of graph coarsening [...]

In addition to discussions in the main body of our paper (c.f. e.g. line 38ff., line 122 ff., line 187 ff., line 231 ff., line 404 ff.), we discuss in Appendix D how our work relates to the notion of restricted spectral similiarity that is used in graph coarsening and discuss how this notion -- while valid -- is not quite strong enough to guarantee transferability.

In Appendices B and C we further discuss existing approaches to transferability and how our approach differs from and relates to them.

Can we improve our discussion of these points in any form? We would be glad to act on any further feedback!

Moreover, the tools used for such an analysis have also been thoroughly discussed in graph coarsening and here they are adapted to GNNs.

Might we kindly ask which tools the reviewer is referring to? We are unaware of any tools from the coarse graining literature that are being used in our work, aside of course from providing an example setting to which our theory applies.

As we discuss above and in great detail in Appendix D the notion of restricted spectral similarity mentioned by the reviewer in an earlier comment (while definitely providing valuable information) is not sufficient to guarantee GNN transferability in the example setting of transferability between a graph and its coarsified version.

Additionally, our work considers transferability between a graph and its coarsified version as one example, but extends fundamentally beyond it.

Instead, our work and analysis is based on the fundamental notion of heat diffusion and the related notion of the Laplace transform. Mathematically, our tools thus originate in the well established field of analysis of semi-groups.

Related to the frequency analysis for directed graphs, do consider that it is quite investigated in the graph signal processing literature. But this is less relevant for the judgement of this paper and more fyi.

We are very happy to have a tangential discussion on this! We are well aware of the GSP literature (papers of which we of course refer to within our own paper) and the various approaches to constructing a Fourier-like transform with associated frequency interpetation for directed graphs.

Here we discuss related complications in the setting of transferability, as considered in our paper:

In the (for simplicity one dimensional) Euclidean setting, we have:

where the operator $g(-i \partial_x)$ is defined via the Borel functional calculus.

We may write this as

with the projection valued measure $P$ associated to the self-adjoint operator $A = -i \partial_x$ and the integration being performed over the spectrum $\mathbb{R} = \sigma(-i \partial_x)$ of the operator $A$.

If $A$ is instead a finite dimensional self-adjoint operator, the projection valued measure $P$ associated to $A$ is a discrete measure, so that for $A$ (instead of the derivative operator) being a matrix (such as a graph Laplacian) we may write

Here {$P_\lambda$}$_\lambda$ is the family of spectral projections associated to the self adjoint matrix $A$ and we have

As is well known, the spectrum $\sigma(A)$ thus plays the role analogous to the frequency domain in the continuous setting. In the graph frequency domain, a graph filter $\hat{g}$ then simply acts by multiplication with $\hat{g}(\lambda)$ in the eigenspace corresponding to the eigenvalue $\lambda$.

However, if $A$ is a (non-symmetric) matrix associated to a directed graph (such as the corresponding adjacency matrix or graph Laplacian), the above equation no longer holds: In the Jordan Chevallier decomposition above -- in addition to the spectral projections $P_\lambda$ -- there now also appear nilpotent radicals $D_\lambda$ (which are identically zero if $A$ is diagonalizable). Instead, this equation now reads

with the radicals $D_\lambda$ satisfying $D_\lambda^{n_\lambda} = 0$ for the algebraic multiplicity $n_\lambda$ of the eigenvalue $\lambda$.

For a filter $\hat{g}(A)$ (defined via the Dunford-Taylor integral; i.e. the holomorphic functional caclulus), we then have (as e.g. proved in Kato)

Here $\hat{g}^{(n)}(\lambda)$ is the $n^{\text{th}}$ derivative of $\hat{g}$ evaluated at the eigenvalue $\lambda$.

The appearance of these derivative terms complicates the interpretation of the spectrum $\sigma(A)$ as playing the role of a frequency domain. Additionally, the appearance of the radicals $D_\lambda$ complicates the study of transferability between graphs, as now not only variations in spectral projections $P_\lambda$ but also variations in radicals $D_\lambda$ need to be considered and bounded.

We would be happy to discuss this more, should you be interested!

Thank you for your engagement! We happily address the raised points and elucidate significance and novelty of our work!

[...] this work [...] ignores the high spectral variations which are the most sensitive part.

Our work considers transferability of GNNs between graphs that are approximately the same, but differ in their fine-print articulations. This is exactly the setting relevant for transferability, as transferability is concerned with ensuring that GNNs generate similar latent embeddings for similar graphs.

Spectrally expressed (c.f. Chung 1997), graphs that are approximately the same, but differ in fine structure articulations have associated Laplacians where the low lying spectral structure is similar, but the high lying spectral structure may differ greatly.

Example settings of graphs having the same low lying spectral structure, but different high lying spectral structure are:

1. Graphs that differ by an edge deletion in a high connectivity area
2. Graphs that describe the same object at different resolutions (coarse vs. fine)
3. Graphs discretising a manifold

Our work then considers transferability between such graphs that are approximately the same, but that vary in fineprint articulations, which exactly means that the high lying spectral information may vary significantly.

We then classify the class of filters that is able to transfer in this setting.

[The] diffusion distant is hiding this problem.

The notion of diffusion distance introduced by Hammond et. al. (2013) is not meant to hide any problem, as there fundamentally is no problem to be hidden!

Our work studies transferability between graphs that are approximately the same, but vary in fine print articulation. That means, that associated Laplacians are similar in their low lying spectral structure, but are allowed to vary in their high lying structure (as is e.g. the case for edge deletions, coarse graining, and discretisation of a manifold).

The distance notion $||L - \tilde{L} ||$ is not able to pick up on the similarity in the such settings, as it weighs all spectral components simlarlly (c.f. also the discussion In Section 3 line 125 ff.). In contrast the diffusion distance is able to pick up on this similarity; it is better adapted to this setting.

For the setting of coarse graining, the reviewer suggested to compare with the the notion of restricted spectral similarity. As the name suggests, restricted spectral similarity only considers similarity between the spectral components below a cutoff. Similarity of higher lying spectral components is not considered. This is approach of focusing on the low lying spectral components is clearly necessary, as coarse-grained and original graphs differ in their fine-structure articulation (as well as the number of nodes).

Unfortunately, as we discuss in detail in Appendix D, the notion of restricted spectral similarity while valid is not quite enough to ensure transferability between a graph and its coarse grained version. The diffusion distance is able to guarantee transferability in this setting.

Additionally, it should be noted that our work considers transferability between graphs that are approximately the same, but differ in their fine-print articulations in general. The setting of coarse graining graphs -- while a motivating one -- is just one example.

Establishing transference between graphs that are close in a diffusion sense remains a particular case of the more general GNN stability.

Since the general stability of GNNs without a low pass filtration is discussed thoroughly, I struggle to see significance in this work to merit publication.

Established approaches to GNN stability do not cover settings that are covered under our transferability theory!

The underlying reason is, that existing approaches to stability measure the distance between graphs in spectral norm as $||L - \tilde{L} ||$. This distance-measure weighs all parts of the spectrum with similar strength. Thus graphs that are similar in the low lying parts of the spectrum but differ potentially strongly for the high lying part of the spectrum will not be considered similar ($\epsilon \ll ||L - \tilde{L} ||$). As transferability is however only established for $||L - \tilde{L} || \leq \epsilon$ This setting is thus not covered by existing stability approaches while our theory applies to it.

A straightforward example is the setting of edge deletions discussed at the beginning of Section 3. Here we always have $||\tilde{L} - L ||= 2$. In contrast, the diffusion metric is more sensitive, and depending on where the edge is deleted may be vanishingly small. Thus existing approaches for transferability will never allow for statements on transferability here, while using the diffusion distance will allow for such statements.

A different example of such a setting where our transferability analysis applies is the example setting of coarse graining graphs.

Also in the setting of coarse and fine structure, the suppression of large frequency components is of crucial importance! Let us consider a graph for which we choose two nodes and modify the edge weight $w$ between them.

As we increase the edge weight $w$ between them, it is more and more justified to treat these two nodes as a single entity, as they are so strongly connected. However, since we have for the associated ($w$-dependent) graph Laplacian $L_w$ that $|| L_w|| \rightarrow \infty$, a triangle inequality argument then proves that for any matrix $M$, we will have $||L_w - M || \rightarrow \infty$.

Hence the Laplacian of this graph will eventually be infinitely far away from any other graph Laplacian. In particular, $L_w$ will never converge to the Laplacian of any other graph, when distance is measured with linear norm difference $||L_w - \tilde{L} ||$.

However, we can show that if we use the diffusion distance instead, we will have convergence! The sequence of Laplacians $L_w$ *converge in the diffusion sense to the Laplacian $\tilde{L}$ of the graph where the two nodes connected by the edge of weight $w$ are fused together into a single node:

We have

as $w \rightarrow \infty$ (suppressing embedding operators in notation).

Our results then show that this convergence also holds for networks that employ Laplace transform filters: For such networks the graph-level embeddings generated for the graphs $G_w$ will converge to the embedding of the graph $\tilde{G}$. For other models, the embeddings generated for the graphs $G_w$ will not be more and more similar for the embeddings of the graph $\tilde{G}$ (c.f. also Figure 10 on page 9).

In the example of coarse and fine structure graphs, a well established and well cited notion of similarity is the notion of restricted spectral similarity. This is a very valid and useful one when coarsifying graphs, as it guarantees spectral similarity up to a frequency cutoff and allows to derive conclusions on alignment of eigenspaces of the respective Laplacians.

As we detail in Appendix D we however need slightly stronger results on alignment of eigenspaces than the ones that restricted spectral similarity is able to provide. We discuss this in detail in our response above.

Hence the notion of restricted spectral similarity from coarse graining -- while very valid -- is almost but not quite able to guarantee transferability in this context of GNN transferability between graphs and their coarsified versions.

Hence we unfortunately have to use a different measure of similarity when investigating transferability. The notion of restricted spectral similarity nonetheless remains a very valid, well established, useful and fundamental notion. We make this point very clear in our manuscript (c.f. e.g. Line 1043 ff.).

Dear Reviewer Dvw3,

Thank you again for your valued participation in the discussion phase!

We had a friendly discussion with the other reviewers above (https://openreview.net/forum?id=cTDooc2J9S&noteId=ujeYLl2Uj7) on the role of high frequency components in our analysis.

In two sentences, we would summarize the consensus achieved above as:

Our paper provides novel and valuable insights for transferability in settings where the overall rough structure of graphs is paramount. To be ready for publication, it also also needs to be clearly stated that this is our scope and we do not consider settings where the exact articulations of graphs is fundamental.

We have now updated our paper to reflect this. Following this discussion, we believe that we now also better understand your concern and -- as we hope -- are able to alleviate it!

Settings where the overall structure of a graph is more fundamental than the (high frequency) fine print structure occur, whenever not the exact articulation of the graph at hand is fundamental, but rather many graphs may be used to describe the same situation.

Some examples are:

1. Graphs discretizing the same manifold (e.g. sensor networks measuring temperature in a geographical region)
2. Graphs that describe the same object at different resolutions (e.g. social networks expressed at the level of individual users vs. communities)
3. Graphs with edge presence determined by cutoffs (c.f. also the discussion in Gasteiger et. al. (2019) 'Diffusion Improves Graph Learning' (e.g. first paragraph of the introduction))

In these situations, we do not want models to overfit on the exact articulation of a graph, because the graph at hand is just one of many ways to describe an underlying system. The model should thus be insensitive to variations in fine structure (i.e. high frequency variations). That is to say, models should be insensitive to high frequency variations.

Existing approaches to stability measured distances in graphs using the linear distance $d_{\text{lin}}(d, \tilde{L}) = ||L - \tilde{L} ||$. They then established transferability between graphs for which $|| L - \tilde{L}|| \leq \epsilon$. Thus they do not apply to the setting considered above: Graphs whose overall structures align but which differ in fine print articulation will generically differ greatly in the high-lying spectral components. In this setting we will have $\epsilon \ll ||L - \tilde{L} ||$, so that existing stability theories will not apply.

As the linear distance $||L - \tilde{L} ||$ is unsuitable for this setting, we now want to find a distance metric $d(L, \tilde{L})$ that is adapted to this setting. When we have such a distance metric that is small whenever the overall structures within graphs are similar, we can built a transferability theory which provides guarantees for model transferability whenever $d(L, \tilde{L}) \leq \epsilon$; i.e. when graphs are similar in overall structure but may vary in fine-print articulation.

We then contribute this within our paper:

1. We establish and discuss a distance notion adept at capturing the setting of graphs that possess similar overall structure but vary in fine print articulation.
2. We built a transferability theory for this setting where existing transferability theories do not apply.
3. We establish that not all models will be able to transfer between graphs that are similar and characterize the class of models that are able to transfer.
4. We validate these findings numerically.

To make this point clearer, we now have made significant modifications to our paper. In particularly we make clear the following points:

1. Diffusion distance as relaxation: The diffusion distance can be viewed as a relaxation of the typical linear distance $\|L - \tilde{L}\|$, which allows us to consider graphs to be similar if rough overall structures align, while fine-print articulations may vary. This setting captures fundamental examples such as graphs discretizing the same manifold, graphs describing the same object at different resolutions or graphs differing by edge deletions. We now present this exact characterization in the Introduction (c.f. line 49ff) of our updated manuscript.

2. Weaker similarity implies weaker assumptions: Since the diffusion distance is a relaxed notion of similarity compared to the linear distance $||L - \tilde{L}||$, also only weaker (spectral) conditions on filters are needed in order to guarantee transferability in this setting (c.f. line 67ff. of our Introduction). 

3. Not applicable when fine-structure details are critical: While the notion of diffusion similarity is well adapted to situations where the overall structure of graphs is more important than their exact fine-print articulations, there also exist settings where precisely the fine-structure of graphs is important to consider. For this setting, we do not provide results; it is outside the scope of our work.

so why is the convergence of the suggested LTF models a good thing?

This is because the convergence here is to a different graph than the graph representing the original equilibrium molecule! As the limit graph is different from the original equilibrium graph, there is no contradiction to unstable intermediate molecules behaving differently from the original equilibrium graph.

More precisely: When deflecting hydrogen atoms out of their equilibrium positions towards the nearest heavy atoms, the final state is that where these hydrogen atoms have arrived exactly at the position of the respective nearest heavy atom. It is thus a graph where instead of the original charge $Z_{\text{heavy}}$ at the position of a heavy atom and the charge $Z_{\text{hydrogen}} = 1$ at the original positions of hydrogen atoms, there now is the charge $Z_{\text{limit}} = Z_{\text{heavy}} + N\cdot Z_{\text{hydrogen}}$ is to be found at the original position of the heavy atom in question. Here $N$ is the number of hydrogen atoms being collapsed onto said heavy atom.

The resulting limit graph is thus a coarse grained version of the original graph. These heuristic arguments are made precise using the notion of diffusion similarity: a modified molecular graph, with hydrogen moved out of equilibrium towards the nearest heavy atom converges in the diffusion sense to this coarser limit graph.

This convergence is respected by LTF based models: Whenever a graph converges to another graph in the diffusion sense, also the latent embeddings generated by LTF-based models will converge to those of the limit model.

Thus LTF based models are continuous from the space of graphs to the Euclidean latent space. The same is not true for other models, as Fig. 10 shows.

448: Does this mean that the distances are simply ignored in this experiment? And if yes, why would htat be a good idea?

Ignoring distances would indeed not be reasonable. In this experiment, positions of hydrogen atoms are varied (individual (original equilibrium) positions are available within QM$7$). Modified edge weights are then calculated using the same formula as before (c.f. line 443) as

with updates positions $\{ x_i\}$ for hydrogen atoms.

How was the QM7 target chosen and why only this single target?

One of the contributions of our paper is to provide transferability guarantees in the setting of small to medium sized graphs. Here existing approaches (which rely on auxiliary ambient objects to establish transferability) are not applicable. To showcase the applicability of our theory to this realm of smaller graphs in practice, we need to make use of a dataset such consisting of smaller graphs. This is true for QM$7$.

Additionally, QM$7$ is a molecular dataset. As argued above (c.f. also the discussion from line 378 onwards) the notion of (chosen or varying) resolution scales is natural to the description of physical systems (cf. The discussion in lines 378 - 387).

Finally, QM$7$ (as opposed to e.g. QM$7$b or QM$9$) directly provides adjacency matrices (in the form of Coulomb matrices). Hence spectral methods – as investigated in our paper – are directly applicable here without further design choices or pre-computations.

QM$7$ is a single-target dataset; with the sole target being atomization energy. This sole target is thus the target for which we report results in Table 1.

Thank you for your thorough review as well as your insightful questions! We were very glad to read that

The paper is well-written and easy to read, especially for a theory-heavy paper.

And that

[...] the suggested diffusion-based distance and its use for graph learning seem novel and interesting

Let us address the raised points individually:

35ff: small changes may have a big effect on the desired label, e.g. when computing the parity function (but also in chemistry applications). It is (to me) not clear how this transferability should be happening. 

There certainly exist situations where transferability between different graphs is not a desirable quality. This is especially the case when the exact articulation of a graph is important; e.g. when the label is given as the parity of the set of edges or nodes as the reviewer observed.

However, there also exist situations where the exact articulation of a graph is not important. This is for example the case when graphs are used as a means to describe a given more fundamental object. Examples include different graphs discretizing the same manifold, graphs describing the same entity at different resolutions (e.g. a social network expressed at the level of individual users vs. the level of interacting communities) or when graphs are drawn from a common statistical distribution. In these settings, a model should not overfit on the exact graph articulation at hand, but rather learn to represent information about the more fundamental underlying entity. In other works the model should be transferable between the graphs that describe this same underlying entity.

166: it would be nice to have a formal definition of J here. 

We are glad to follow this advice. We have added a formal definition and a surrounding discussion of $J$ in our updated manuscript.

202: how to find this mapping? It would be nice to elaborate a little here. 

We checked and are unfortunately uncertain which mapping you are referring to, as line 202 does not contain (the description of) any mapping. Could you maybe clarify? We would be happy to provide further details. The closest linear mappings to line 202 in our manuscript are the projection and interpolation operators $J^\downarrow, J^\uparrow$. These are rigorously introduced from line 192 onwards. Heuristically, $J^\downarrow$ acts as an averaging operator. Its natural emergence in this setting may be understood from the perspective of heatflow: In the physical setting of heat conductance over a graph, the temperature in a strongly connected subgraph will equalize very fast. This subgraph will behave as a single entity, and the temperature of this single entity (i.e. super-node) will be given as the average temperature of the original nodes. This assingment of the respective average value to the supernodes in question is facilitated by $J^\downarrow$. The interpolation $J^\uparrow$ is simply the adjoint mapping to $J^\downarrow$.

286: why 10^0 instead of 1?

We used this notation to foster notational consistency with the discussion in the experimental section. There we use the notation '$\sim 10^n$' when discussion transferability errors (c.f. lines 413, 416, 417). However we are of course very happy to write '$1$' in place of '$10^0$' in line 286 and have now done so in the updated version of our manuscript.

307f: this sentence is hard to parse, especially the end after "importantly"

Thank you for this feedback! Following this comment, we have now broken up this sentence into smaller ones, in order to foster readability.

344: J^up J^down (not down, down)

Thank you for spotting this typo! We have now corrected it in the updated version of our pdf.

376: QM7 contains small molecules only, this may have an effect on how much diversity is in there.

There certainly exist much larger and more diverse molecular datasets (such as GDB-13 of which QM$7$ is a subset). QM$7$ as a dataset contains all organic molecules of up to 23 atoms (c.f. http://quantum-machine.org/datasets/). Since our objective in using this dataset is not to contribute to the state of the art in molecular property prediction, but rather to showcase our theoretical transferability results in an example setting, we believe that the scope of the QM$7$ is already perfectly adequate for our purposes here. Additionally, one of the contributions of our work is to provide an approach to transferability in the setting of small to medium sized graphs, where existing approaches (reliant on auxiliary ambient objects to establish transferability) are not applicable. To showcase the applicability of our theory to this realm in practice, we actually need to make use of a dataset such as QM$7$ consisting of smaller graphs.

Do the results generalize to QM9 too? (e.g. between the two datasets) And how about other targets?

Following this feedback, we have now additionally also conducted Experiments on QM9. We currently provide preliminary results in Appendix J.3 of our updated manuscript and will include full results (on all targets and for all architectures) in the camera ready version of our paper.

We find that here too, Laplace transform filters minimize the transferability error; most often by a substantial margin.

Regarding the question of generalization between QM$7$ and QM$9$ we note: As QM$7$ might be considered a subset of QM$9$; hence we would expect a certain amount of generalization from the former to the latter. While this is indeed an interesting research question, generalization in this sense is however not the focus of our present work as it does not fall into the realm of transferability. As such we did not consider this setup in our experimental section.

How is "transferability" between dissimilar graphs avoided? And is this shown somewhere? (as its part of the conclusion)

In Section 5.2, we conduct an experiment where we replace individual nodes in a graph with fully connected cliques. As we see in Fig. 12, this severely negatively affects the performance of typical models: Their corresponding node classification accuracy deteriorates as clique size is inreased. As we argue (c.f. line 481 ff. and in more detail in Appendix H), this occurs because these standard models are more and more transferable (as the clique size increases) between the given graph and a version of this graph where the connections between individual cliques are severed. Information propagation within these models thus occurs as if the underlying graph were disconnected. This precludes an information exchange between the respective cliques and explains the deterioration in classification accuracy.

In contrast LTF-based networks retain a high classification accuracy. These networks retain the ability to transfer information also between individual communities. In other words, they are not transferable between the given graph and a disconnected version of it. This is the case because from a diffusion perspective, these different graph structures are not considered similar, as we discuss in Section 3.1 (c.f. especially Fig. 4).

400ff: what are the features of the "coarse" nodes? What kind of information is still there?

The features associated to the coarse grained nodes are the average features of the original nodes that are being collapsed to the respective super node. We have included a detailed discussion of this in Appendix G.1 (c.f. line 1948 ff.).

412: is this result surprising in any way?

As we are conducting experiments considering graphs expressed at different resolutions, we wanted to check whether models that naturally already employ an information propagation scheme that utilizes different resolution scales are able to transfer between such graphs on different resolutions. As such models do not only utilize the graph at its original scale but also at a coarser scale when generating latent embeddings, one might initially be tempted that such models might be able to better handle transferability between different resolutions. As our experiment shows (c.f. Table 1) this is however not the case.

Questions: Why would you expect a network trained on molecules without H to generalize to graphs containing H atoms? Which directly leads to the question: why would such a behavior be desirable? (its different for the torus, there the setting is clear)

The same physical system may be expressed and described at different resolution scales. In theoretical physics, this is famously formalized into the celebrated notion of the renormalization group.

In the (molecular) setting at hand, there are various levels of resolutions at which a molecule as a physical system may be expressed.

We may express it at the level of interacting atomic nuclei, as is done in the QM$7$ dataset. Fundamentally, it may however also be described at a finer scale at the level of interacting protons and neutrons (making up the individual nuclei).

At an even more fundamental level, we may vary the resolution scale of our physical description even more and split up protons and neutrons even further into individual quarks.

All of these descriptions encode the same underlying physical system. As such, each description should yield (approximately) the same result when computing aggregate quantities such as e.g. the molecular atomization energy.

In our experiment in Section 5.1, we now do not train on graphs without hydrogen atoms.

Instead, we train on a coarsified version of QM$7$, where in comparison to the articulation in the original QM$7$ data we have lowered the resolution scale in the description of the individual molecules (c.f. also line 381 ff.): Instead of only aggregating individual protons and neutrons inside each atom into a single node (as is done in QM$7$), we now also additionally aggregate together each heavy atom with all its surrounding (single proton) hydrogen atoms into single nodes.

The resulting graph still describes the same underlying molecule, just at a different resolution scale. Since fundamentally, the same molecule is still being described, we would want a model (that is transferable between resolutions) to provide the same (or very similar) predictions for this very same molecule.

More generally, a model that is transferable from a coarse- to a fine-resolution scale may be trained on a lower resolution scale while still performing very well when confronted with high resolution data during inference. This might find applications in settings where only noisy or low quality training data is available for training. Additionally it may open up avenues to train models much more economically and less resource intensive on smaller graphs while then successfully being able to deploy them on larger graphs.

In the opposite direction, transferability from fine to coarse would allow models to be trained on high quality training data (such as e.g. synthetic data obtained from DFT calculations in the chemistry setting) and benefiting from all the high-resolution information available in this data, while not losing performance when eventually being deployed on experimentally obtained lower quality test data.

The experiment where hydrogens are deflected out of their equilibrium position is also interesting: I would expect unstable atoms (i.e. the ones with deflected hydrogen) to behave quite differently from their "normal" counterparts,

We are very glad that you found our experiment to be interesting! We might think of molecules where hydrogen atoms have been deflected out of their equilibrium position to be energetically excited. Hence they would indeed have (at least slightly) different properties than their equilibrium counterparts.

Thank you for your appreciation of our efforts! We are glad to read that we were able to further improve our work by incorporating your feedback!

With the modifications provided:

Do you feel like our work is a good paper that should be accepted at the conference?

We understand that modifying scores is completely at the discretion of reviewers and we have no right to any other score than the one you assign!

If you should however feel like our work is good and should be accepted, ICLR reserves a particular score for that sentiment. If it were the case that you consider our work to be good, we would be extremely grateful if you could reflect that sentiment in that very numerical quantity of 'score', that the fate of a paper so often comes down to.

Should you choose to do so, that would of course be absolutely voluntary on your part; we completely understand that!

Thank you very kindly for your review! We were vey glad to read that

The paper is very well written and easy to follow.

and that

The paper is relevant and the topic is important.

We also would like to thank you sincerely for candidly expressing your honest concerns so that we may directly address them here. We fundamentally believe that these concerns expressed may easily be resolved and aim to do so below.

Let us address each the the three raised points in detail:

Regarding the asymptotic model, the authors consider a graph that grows in the number of nodes (L) with no particular structure. This immediately removes any form of intuition or interpretation from the graph limit.

We first provide clarifications about the asymptotic model to elaborate on the interpretation of our approach. First, note that letter $L$ referenced above does not denote the number of nodes but rather the graph Laplacian throughout our paper. We introduce this notation at the beginning of our paper (i.e., in the background section (Section 2.1), line 85) and also reiterate it in our table on notational conventions (Appendix A, line 777). We instead utilize the variable $N$ to denote the number of nodes (as introduced in line 75 of our background section).

Second, we would like to clarify the structural implications of our notion of transferability in this setting. We point the reviewer to line 488ff in Section 5.3, which states that

"The concept of operators capturing the geometry of underlying spaces also applies to manifolds. [...] This is hence is a prime setting for studying transferability."

, that is, we consider transferability of graphs approximating the same underlying manifold. Thus, a convergent sequence of graphs will possess increasing structural similarity with the underlying manifold. This provides the intuitive notion of structure, as was your concern. Indeed, not only is this an intuitive notion of a graph limit, but we also provide a mathematically completely rigorous discussion of how graphs are taken to approximate manifolds in Appendix F.2. We refer the reader to this detailed mathematical discussion in line 500f of Section 5.1. For further conceptual clarity, we also provide in Fig. 13 a visualization of the (regular grid) graph discretizations considered in our experiments.

We thank the reviewer for this comment as the setting of graphs discretizing the same manifold is an important example setting for our theoretical analysis of transferability between structurally similar graphs. We emphasize this meaning further in the updated manuscript, where we replace occurrences of the wording "ambient space" with "manifold" to avoid any ambiguity.

Minor issue: Theorem 4.4 should have a statement, it currently reads "As proved in ...".

Following the reviewer's comment, we have now changed the formulation of Theorem 4.4 in our updated manuscript

from

'As proved in Appendix E.3, we have:  [statement that was proved]' .

to:

'As we prove in Appendix F.3, we find for the transferability of a single filter $\psi$ that: [statement that was proved]'.

The plots are divided into high and low resolutions, but this is not a mathematical quantity. The authors should modify a continuous quantity such as the number of nodes.

We gladly provide further discussion of the meaning of the terms 'high and low resolution' in the experimental section: Regarding the the results of Table 1: Here we collect results for models trained on the original high-resolution QM$7$ dataset and evaluated on a (coarsified) low resolution version of this dataset. We also report results for the opposite pairing of models trained on low resolution QM$7$ and evaluated on the original high resolutionQM$7$ dataset. We rigorously discuss how the coarsified low resolution QM$7$ dataset is obtained (c.f line 381ff. of the relevant Section 5.1 as well as Appendix G.1 (referenced in Section 5.1)). We also included both datasets (the original high resolution QM$7$ dataset as well as the coarsified low resolution QM$7$ dataset) in our submitted supplementary material.

We agree with the reviewer that varying a numerical quantity (like the number of nodes, as suggested) can indeed provide valuable insights into transferability properties of networks. For this reason our original manuscript provides the following three experiments which vary various numerical quantities (e.g. the number of nodes):

In Fig. 14 we vary the number of node} in graphs approximating the same manifold and discuss corresponding effects on transferability

In Fig. 12 we vary the number of nodes inside cliques. Here we show that standard architectures can not deal with such a situation, while our theory allows to design models that can handle this setting well.

In Fig. 10 we continuously vary edge-weights inside subgraphs. We use this to show that standard models are not continuous as maps from the space of graphs to Euclidean latent spaces, while models conforming to our theory (i.e. LTF-based models) are continuous.

In our updated manuscript, we have now also included the axis labelling of Fig. 14, which was previously still missing.

We sincerely hope that we were able to clear up any misunderstandings or doubts. Should this not be the case, please do not hesitate to get back to us; we would be more than happy to provide additional details or incorporate any feedback further feedback!

With respect to the bound, the authors do not provide a rate and simply show that it converges]. [...] I believe this paper is too general and therefore there are no implications for the practitioner.

The reviewer expressed concerns regarding rates of convergence for transferability. We agree with the reviewer that quantitative bounds can be critical for practical relevance. However, we wish to direct the reviewer to our results in Theorems 4.4, 4.6, and 4.7. Indeed, as a main contribution of our work, we do in fact provide explicit quantitative bounds on transferability. Theorems 4.6 & 4.7 reduce network transferability to single filter transferability. Theorem 4.4 then provides explicit quantitative (even non-asymptotic) bounds on this single filter transferability.

Additionally, as the reviewer observed, we also provide results on convergence of latent embeddings: We show that if a sequence of graphs converges to a limit graph in the sense of diffusion similarity, embeddings generated by networks conforming to our theory will converge to the latent embedding of the limit graph. This is in fact predicted by our quantitative results in Theorems 4,4, 4.6 & 4.7.

We might interpret this result as  LTF-based models constituting continuous  maps from the space of graphs to Euclidean latent spaces. In contrast, as we show in Section 5.1, latent embeddings generated by other models will not converge. Such models are not continuous.

In our work, we indeed introduce a general and widely applicable framework for the study of transferability properties of graph neural networks. This framework is distinct from previously introduced frameworks and also applies to situations where previous works are not applicable. We fundamentally believe this to be an important and valuable contribution in its own right.

At the same time, our work is also of great practical relevance:

First and foremost, we establish (for the first time) that not all types of filter-functions will lead to transferable networks. We then completely characterize the class of filters that allow for transferability. This enables the practitioner to actually design networks that will be able to transfer in practice.

We also provide a discussion of the reasons why architectures not conforming to the developed theory are unable to transfer in the considered settings (c.f. Appendix H).

Counter to other approaches, the transferability framework we introduce is not dependent on any underlying limit object. This hence allows to provide transferability guarantees also for the settings of small to medium size graphs.

Our transferability framework is applicable in important settings not covered by previous approaches, such as e.g. the inclusion of subgraphs (c.f. e.g. Fig. 5 or Appendix D) and the setting of graphs on different resolution scales (c.f. e.g. Section 5.1)

The developed transferability framework also  directly extends to directed graphs (c.f. e.g. Appendix F.3), a setting previously hardly acknowledged in  the literature, but of great practical relevance (c.f. e.g https://arxiv.org/abs/2305.10498).

Following this feedback, we now reference practical implications in the 'Contributions' section of our updated manuscript.

Thank you for your rigorous review of our paper. We were happy to read that our writing

is logically rigorous and we were able to convey one of our main messages, namely that polynomial filters do not satisfy transferability, whereas Laplace Transform Filters [...] do clearly.

As we understand it, only questions 'Regarding the experiments on different graphs sampled from the same manifold' remained open. We are very happy to answer these:

'Considering the definition of Bidirectional Transferability and the motivating example, it seems natural that the experiments on graphs of different resolutions would be successful. Therefore, I am more interested in the experiments on different graphs sampled from the same manifold. However, it seems that the authors only conducted experiments on a pair of graphs on the Torus manifold, is that correct? '

That is correct. We derived and presented a general theoretical framework for generic graphs discretising the same ambient space in Appendix F.2 Further discussion of graphs discretizing ambient spaces.

As an example we there then derived theoretical convergence guarantees for graphs discretizing the Torus manifold. To experimentally verify this convergence in this example, we then conducted the experiments provided in Section 5.

Additionally, I would like to ask why the final comparison in this experiment is made using transferability error, rather than demonstrating the difference between network outputs before and after transfer?

We are not exactly certain if we understand the question correctly, as the transferability error exactly measures the difference in outputs generated by networks deployed on the respective graphs.

What the experiment at hand experiment demonstrates is that deploying an LTF-based network on two graphs that discretize the same ambient space leads to similar outputs; with outputs becoming more similar, the closer the graphs approximate the common object.

The transferability error now measures the difference between deploying the networks on the respective graphs. As such it is the metric of choice when comparing the respective outputs.

Did this answer your question? If not, please do not hesitate to get back to us; we will be glad to provide further details!

Thank you very much for your careful review of our paper!

We were very happy to read that

the problem formulation and results are interesting

and were delighted to see that you

want to advocate in favor of this paper.

Let us answer your raised questions and explain how – in contrast to other approaches – our work is able to provide transferability guarantees without having to impose spectral restrictions on the studied graph filters.

At a very high level, the underlying reason for this is a difference in how we quantify the magnitude of graph perturbations:

Previous works unanimously used a linear spectral-norm based approach to quantify the size of graph perturbations as $d(L, \tilde{L}) = ||L - \tilde{L}||$. As we detail below, deriving results in terms of this measure of perturbation size is challenging and generically only possible when further restrictions on filter functions are imposed.

In contrast, we quantify differences between graphs using the notion of diffusion distance $d(L,\tilde{L}) = \sup_{t\geq 0} || e^{-tL }  -   e^{-t\tilde{L}} ||$ as originally introduced by Hammond (2013). Bounding variations in filter outputs in terms of this distance measure is much easier, as discussed in detail below.

For conceptual clarity, let us here discuss in detail the setting of a fixed number of nodes. The setting of varying numbers of nodes proceeds in complete conceptual analogy, but with added notational complexity due to the need of having to map between the different node sets.

 When studying single filter transferability, we are then interested in bounding the difference $||\psi(L) - \psi(\tilde{L}) ||$ corresponding to the maximal difference in outputs of a single fixed filter deployed on two different graphs $G,\tilde{G}$ with associated Laplacians $L,\tilde{L}$.

Both our work and existing approaches then aim to bound this difference in terms of a distance measure $d(L,\tilde{L})$ that measures how different the respective laplacians $L,\tilde{L}$ are:

$||\psi(L) - \psi(\tilde{L}) || \leq C_\psi \cdot d(L,\tilde{L}).$

Here $||\cdot||$ denotes spectral norm and the stability constant depends on $\psi$ (and for some existing approaches may also depend on the spectral properties of $L$ and $\tilde{L}$).

The fundamental difference between our approach and existing works is then, in which distance measure $d(L,\tilde{L})$  the difference between the two Laplacians $L, \tilde{L}$ is measured:

Existing approaches unanimously make use of the operator norm differences

$d(L,\tilde{L}) = ||L - \tilde{L}  ||$

between the two Laplacians to provide a measure of similarity.

The fundamental problem in deriving a bound of the form $||\psi(L) - \psi(\tilde{L}) || \leq C_\psi \cdot  ||L - \tilde{L}  ||$ for some constant now is that scalar Lipschitzness does not imply operator-Lipschitzness: In other words, even if for scalar $x,y \in \mathbb{R}$ we have $|\psi(x) - \psi(y) | \leq K \cdot  |x – y|$, this still does not imply that we would also have $||\psi(L) - \psi(\tilde{L}) || \leq K \cdot  ||L - \tilde{L}  ||$.

In order to find a constant $C_\psi$ so that  $||\psi(L) - \psi(\tilde{L}) || \leq C_\psi \cdot  ||L - \tilde{L}  ||$, it is thus not sufficient that $\psi$ simply be Lipschitz. Instead, further restrictions on $\psi$ (and potentially on the spectra of $L, \tilde{L}$) need to be made, and the constant $C_\psi$ will depend on these restrictions.

In contrast to previous works, we instead do not use the norm difference $||L - \tilde{L} ||$ to measure graph similarity. Instead,  the distance measure we are considering is the diffusion distance

$d(L,\tilde{L}) = \sup_{t\geq 0} || e^{-tL }  -   e^{-t\tilde{L}} ||,$

introduced by Hammond (2013).

The key idea here is that including the exponential into the distance metric leads to an (exponential) suppression of large eigenvalues of $L$ and $\tilde{L}$. Information encoded into these large eigenvalues (and corresponding eigenspaces) corresponds to fine structure details of the graphs $G$ and $\tilde{G}$ (c.f. e.g. Chung 1997).

Suppressing this fine-structure information before taking a distance measurement effectively leads to a comparison that is predominantly determined by the coarse structures within the graphs. If the rough structures within the two graphs are similar, the distance between the two graphs will then be relatively small. Thus this metric is adapted to considering graphs that are similar up to fine-structure variations to be close to each other. This is the setting we are interested in when considering transferability, so that this distance measure is adapted to this setting of transferring filters between approximately similar graphs (see also the discussion in Section 3).

Suppose now that we are given a Laplace transform filter $\psi(z) = \int_0^\infty \hat{\psi}(t) e^{-tz}dt$ and want to determine whether it is transferable between two graphs. That is, we want to determine whether the quantity $||  \psi(L) -  \psi(\tilde{L})   ||$ is small. To this end, we may note:

$||  \psi(L) -  \psi(\tilde{L}) ||  =   \left|| \int_0^\infty \hat{\psi}(t) e^{-Lz}dt  - \int_0^\infty \hat{\psi}(t) e^{-t\tilde{L}}dt   \right||$

$\leq \int_0^\infty   | \hat{\psi}(t)| || e^{-Lz} - e^{-t\tilde{L}}  || dt$

$\leq$ $\int_0^\infty   | \hat{\psi}(r)|  \cdot   \text{sup}_{t\geq 0}|| e^{-Lz} - e^{-t\tilde{L}}  || dr$

$=  || \hat{\psi}||_1 \cdot d(L,\tilde{L}) .$

Thus  in our approach, we may express the desired bound $||\psi(L) - \psi(\tilde{L}) || \leq C_\psi \cdot d(L,\tilde{L})$ on filter outputs simply as

$||  \psi(L) -  \psi(\tilde{L}) || \leq || \hat{\psi}||_1 \cdot d(L,\tilde{L})$.

As the calculation above showed, we do not need to introduce any further restrictions on $\psi$ or the spectral properties of $L$ or $\tilde{L}$.

Instead, we can straightforwardly guarantee that if $|| \hat{\psi}||_1$ is not too large and the diffusion distance $d(L,\tilde{L})$ is small, the quantity $||  \psi(L) -  \psi(\tilde{L})   ||$  is also small and the filter $\psi$ is thus transferable.

We believe that this is indeed an important quality of our work and hope that tools and approaches developed in the present submission may be picked up by other researchers in the community in order to be used for further research. In order to ease and facilitate this, we have now included an appendix highlighting further the properties of diffusion similarities over the standard spectral difference (Appendix C). We have also included an Appendix discussing in more detail existing works on transferability and -- where applicable -- also discuss the origin of the respective spectral assumptions made in these works (c.f. Appendix B).

Below we discuss the spectral assumptions in the papers mentioned by the reviewer individually:

Stability to Deformations of Manifold Filters and Manifold Neural Networks:

Here filters are bounded as $||\psi(L) - \psi(\tilde{L})|| \leq K ||L – \tilde{L}||$. In Theorem 2 absolute perturbations are considered ($\tilde{L} = L + A$), in  Theorem 3 relative perturbations are considered ($\tilde{L} = L + EL$). In both cases the conditions on spectrum and filter functions stem from the fact that Lipschitz-ness does not directly translate to operator Lipschitz-ness.

Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offs:

Here instead of measuring the linear norm difference $||LP -  \mathcal{L}P||$ between a graph Laplacian $L$ and a manifold Laplacian $\mathcal{L}$ (which generically would be infinite as $\mathcal{L}$ is an unbounded operator), the difference of the action of these operators on eigenfunctions ($|| LP\phi -  \mathcal{L}P\phi  ||$). After a triangle inequality argument, one term that has to be bounded in order to bound the difference in filter outputs is $||\phi_i^n - \phi_i||$ of the $i^{th}$ eigenfunction and eigenvector respectively. The fidelity of this approximation depends on spectral separation properties (c.f. Theorem 4 ibid.), which hence leads to the requirement that the spectrum be $\alpha$-separated. This requirement can thus be considered an artifact of considering the linear approximation $||\phi_i^n - \phi_i||$ for each eigenfunction. In contrast, in our approach (c.f. Appendix F.2) the notion of approximation of the Laplacian on the underlying manifold is different. We bound the quantity $|| J^\uparrow e^{-tL} J^\downarrow- e^{-t\Delta}  ||$ instead. Hence we do not need to bound differences between individual eigenfunctions and eigenvectors and hence avoid dependencies on spectral separations.

Transferability of Spectral Graph Convolutional Neural Networks 

Levie's work only requires filters to be bounded and Lipschitz continuous (c.f. Theorem 17 ibid.). This is also true for Laplace-Transform Filters as considered in our work. We avoid Levie's growth of the stability constant with the number of considered eigenvalues (c.f. the discussion towards the end of page 12 ibid.) by avoiding approximations of individual eigenfunctions and instead approximating the bounded operator $e^{-t\Delta}$ directly.

Graphon Neural Networks and the Transferability of Graph Neural Networks

Here the assumptions are that filter functions are bounded and Lipschitz continuous (c.f. AS2 on page 6; ibid.). These assumptions are satisfied true for Laplace Transform Filters as well.

Graph Convolutional Neural Networks via Scattering

Here the conditions on the spectrum also arise from a Lipschitz type approach to bounding differences. The difference $||\psi(L) – \psi(\tilde{L})||$ is then via a triangle inequality argument reduced to bounding each term
$||\psi(\lambda_k)u_k u_k^\intercal – \psi(\tilde{\lambda}_k)\tilde{u}_k \tilde{u}_k^\intercal||$ individually. This is done in eqs. (64) and (68) respectively, which are contingent the there stated spectral restrictions.

Diffusion Scattering Transforms on Graphs

Here the dependence in Theorem 5.3 on the 'spectral gap' as defined before Proposition 4.1 comes from the Lipschitz type argument used in eq. (48).

Stability Properties of Graph Neural Networks

Here as well, Lipschitz type arguments are being used (See e.g. the assumptions of Theorem 1), and hence additional restrictions on spectrum and filter functions need to be posed.

We sincerely thank you for your comments, which are really important questions to answer to put our work in context of existing literature. We greatly appreciate that you gave us the opportunity to demonstrate our novelty with respect to these past works.

Dear Reviewer DCXz,

We hope you are having a great weekend and -- should you celebrate it -- had a happy Thanksgiving!

As the end of the rebuttal period is drawing close and Monday will be our last day to receive comments, we wanted to make sure we have now understood and incorporated your feedback exactly as intended.

In your response above you were

asking for a remark that states that: (1) Your analysis produces a conclusion that is counter to the conclusions of other existing papers. (2) That this is because you are measuring Laplacian distances in a different way. (3) That your results do not apply to problems where we want to process high frequency components.

To incorporate this, we have introduced a Caveat paragraph in our Introduction section (in line 65 ff.) which reads:

Caveat: The notion of diffusion-similarity central to our analysis below is adapted to the setting where the rough overall structure within graphs is more important than fine structure details. Utilizing such a relaxation of the standard linear distance ||L - \tilde{L}|| allows to consider more relaxed conditions on filter functions than previous works (Gama et al., 2019; Wang et al., 2021) in this setting. It is however important to note that since our analysis is based on a distance notion that discounts fine-structure details within graphs, the results in our paper do not allow to draw conclusions about transferability and model performance in settings where the exact articulation of a graph is important.

When introducing the diffusion distance, we then also write (c.f. line 160 ff.)

The exponential suppression of high-lying spectral information renders this metric adept at capturing variations preserving coarse structures (but ill-suited for fine-structure variations; c.f. Appendix C).

We do believe we have thus incorporated your feedback. In the introduction, we talk about coarse vs. fine structures as opposed to low vs. high lying spectral information as either terminology encodes the same information and we want to avoid being too technical in the Introduction section. Should you however want us to change

the results in our paper do not allow to draw conclusions [...] in settings where the exact articulation of a graph is important.

to

the results in our paper do not allow to draw conclusions [... ] for filters that process high frequency information.

we would also happily do that!

Thank you again for your continued engagement and valuable feedback, which we believe has greatly enhanced the clarity of our paper.