ResolvNet: A Graph Convolutional Network with multi-scale Consistency

• Why the reported results cannot beat SOTA baselines (like GCNII) in Table 1?

The results in Table 1 were obtained following the experimental setup of [1] (i.e. “Predict then Propagate”) which evaluates on class-balanced random splits. In contrast the GCNII-paper followed the experimental setup of [2], so that reported numerical values for accuracies can not simply be compared.

To allow for a comparison of GCNII with the other baselines of Table 1 as well as ResolvNet, we evaluated GCNII within the experimental Setup of Table 1 (i.e. following the setup of [1]). We used the best-performing hyperparameters whenever they were reported in the original GCNII paper [3] and otherwise performed a full hyperparameter sweep.

As is evident from Table 1 in our updated manuscript, our method actually performs better than GCNII on the vast majority of datasets.

Regarding the performance in the homophilic regime the reviewer inquired about

(As far as I know, GCNII (which is open source) can beat the proposed method on Cora and Pubmed)

we note the following result:

On Cora, there is a marginal difference between results for ResolvNet and GCNII (84.16% vs. 84.41 %). ResolvNet clearly performs better on the other datasets.

We would also like to thank the reviewer for bringing the recent and interesting GraphMAE2 paper to our attention. This paper focusses on the self-supervised setting, the training procedure of the GraphMAE2 model involves pre-training and the backbones for its encoder and decoder might be constituted by any GNN-architecture (including ResolvNet). In contrast, Table 1 focusses on benchmarking the performance of different convolutional - layers against each other; all under the same (semi-)supervised training procedure and using the same loss. Nevertheless, we found both GraphMAE2 and its precursor GraphMAE to be interesting works and are happy to now cite them in the introduction to our paper.

Finally, we would like to point out that – while ResolvNet generally performs better than baselines in the homophilic setting -- we are not concerned with designing another network that incrementally improves the state of the art on standard node-classification datasets.

Instead we are concerned with introducing the concept of multi-scale consistency. We explain its importance for the transferability of models between graphs describing the same object at different resolutions, as well as for the information-flow within multi-scale graphs. We then introduce ResovNet as a method to address the lack of multi-scale consistency of previous architectures.

• On three famous datasets Cora, Citeseer and Pubmed, there are only two baselines are considered (in Table 1).

We clearly compared against $10$ baselines on all datasets of Table 1 (including Cora, Citeseer and Pubmed) in our initial manuscript. We are unsure how to interpret this comment; could the reviewer clarify?

In our updated manuscript, we now additionally also compare against the recent ChebNetII (He et al. (2022)) as an additional baseline. Thus we now compare in total against $12$ (as opposed to the previous $10$) baselines in this table. Our conclusions remain the same.

• the proposed method cannot get the best performance in Table 3.

As stated in the header of Table 3, this Table lists Mean Absolute Errors (MAEs). Here, lower numbers thus correspond to better performance. Thus our method is clearly the best performing one in Table 3.

As already discussed in the corresponding section of the main-text, our method in fact not only performs best, but it does so by a large margin (MAEs are lower by factor of between 10 to 40 compared to baselines).

While we had provided the evaluation metric in the header of Table 3,and marked our method via “\textbf” as the best-performing method in this Table, we have -- following this comment by the reviewer -- now added a “($\downarrow$)” symbol to the header of Table 3 for additional clarity.

We would like to thank the reviewer for reviewing our paper and providing us with their feedback.

As we understand it, the main points of criticism expressed by the reviewer are that 1) our method supposedly does not perform best in Table 3, and 2) the reviewer hypothesized that our ResolvNet method would not perform better than GCNII in Table 1.

Both points however stem from misconceptions:

1. In Table 3 the metric is “mean-absolute-error”, so that lower numbers correspond to better performance. Our method actually performs best in Table 3 by a large margin (i.e. by an error that is lower by factor of $10$ to $40$ compared to baselines) as discussed in the main-text of our submission.
2. Accuracies reported in the GCNII-paper [2] and Table 1 of our submission can not simply be compared, as the experimental setups differ significantly: Our paper uses the experimental setup and (class-balanced) random splits of [1] (i.e. “predict then propagate”). Instead, [2] uses the experimental setup and splits of [3]. Evaluating ResolvNet and GCNII in a common evaluation setup clearly shows that ResolvNet performs better (details provided below).

Let us address these and all other points raised by the reviewer in detail individually below:

We would like to sincerely thank the reviewer for the careful review of our paper.

We were especially happy to read that we consider

indeed an important topic,

that

the paper provide a very clear definition on multi-scale consistency

and that our various explanations using different modalities (text, examples, figures)

help readers understand why [multi-scale consistency] is important.

Let us address the raised points individually:

• Experiment dataset is small. This is potentially because the proposed method has very high complexity due to matrix inverse (see feed-forward rule in paragraph The ResolvNet Layer. The authors need to conduct experiment on larger datasets (e.g., OGBN) and report complexity in terms of FLOP/Wall-clock time.

Following this important point by the reviewer, we have included an additional section (Appendix J: Scaling ResolvNet to large Graphs) that discusses in detail how ResolvNet is scaled to large graphs.

As detailed in Appendix J, the key ingredient here is a Neumann-Representation of the resolvent that avoids an explicit matrix-inversion.

This replaces the hypothetical $\mathcal{O}(N^3)$ complexity during preprocessing and $\mathcal{O}(N^2)$ complexity during training and inference that a naïve implementation of ResolvNet would constitute with a $\mathcal{O}(EFN)$ complexity (i.e. the complexity of sparse-dense matrix multiplication). Here $N$ is the number of nodes, $E$ is the number of edges and $F$ is the feature dimension.

Beyond these theoretical considerations and in addition to the empirical complexity analysis already provided in Appendix G, we also followed the recommendation of the reviewer and evaluated complexity experimentally (reporting (reliably measurable) MACS (i.e. multiply-accumulate operations) in-lieu of FLOPS):

We trained ResolvNet, ChebNet (both with $K = 1$) and GAT in a two-layer deep configuration with $64$ hidden units in each layer for $100$ epochs on the OGBN-Arxiv and OGBN-Products datasets, which are comprised of $169,343$ Nodes and more than 2M nodes respectively.

Results are collected in the tables below:

Results are collected in the tables below:

OGBN-Arxiv:

OGBN-Products:

As can be inferred from the tables above, ResolvNet takes significantly less time to train per epoch on OGBN-Arxiv, when compared to GAT. It also needs considerably less GPU memory and multiply-accumulate operations compared to GAT.

Compared to ChebNet, our method needs to compute an order of magnitude more sparse-dense matrix multiplication operations (as detailed in Appendix J). This is reflected in the number of performed MACs, which for ResolvNet is roughly an order of magnitude larger than that for ChebNet.

On OGBN-Products, our method remains more complex than ChebNet. In contrast to GAT however, ResolvNet remains trainable.

1) Enumerate all nodes. Translate node identifiers into one-hot-encodings. Combine the one-hot-identifiers of nodes (row-wise) into a node-feature matrix of dimension $N \times N$.
2) Fix $z < 0$. Compute the resolvent $R_z(\Delta)$.
3) Compute the matrix product $Y = R_z(\Delta)\cdot X$
4) Treat rows in $Y$ as updated node features

• How do learnable filters as polynomials in resolvents achieve similar effects of up-projection operator and down-projection operator. It may need more illustrations and explanations for this in Sec 3.2.

The key insight here is provided by Theorem 3.3. From this Theorem, we infer that for multi-scale graphs we have $R_z(\Delta) \approx J^{\uparrow}R_z(\Delta_{\text{collapsed}}) J^{\downarrow}.$ Additionally, we have $J^{\downarrow} \cdot J^{\uparrow} = Id_{G_{\text{collapsed}}}$, as detailed in Appendix B. Combining these two facts yields $(R_z(\Delta))^k \approx J^{\uparrow}(R_z(\Delta_{\text{collapsed}}))^k J^{\downarrow}.$

Thus also polynomials in resolvents effectively first project down to $G_{\text{collapsed}}$, then propagate there and subsequently interpolate pack up to the original graph $G$.

We provide a full discussion of this in Appendix B (c.f. especially Theorem B.4). Following this comment by the reviewer, we now highlight this even stronger in the main body of our submission.

We would like to sincerely thank the reviewer for the careful evaluation of our paper and appreciation of our results. We were especially happy to read that

[our paper] represents a significant and innovative contribution to the field,

this work stands out as a high-quality piece of research

and that

The paper is exceptionally well-organized

Let us address the raised points individually:

• The paper could benefit from more extensive ablation studies and parameter analyses.

Following this comment, we have conducted ablation studies on both $\omega$ and $K$. The results are collected in Appendix K in our updated manuscript.

As a rough summary, we see that increasing $K$ beyond $K = 1$ does not significantly improve performance. This is reminiscent of similar results for e.g. Chebnet, whose polynomial filtering operation generically does not perform better if the polynomial dimension is increased.

For $\omega$, we see that a too small value has negative implications as far as performance is concerned. For sufficiently large $\omega$ (small) variations of $\omega$ do not affect performance. I.e. ResolvNet is stable under (sufficiently small) variations in $\omega$.

• Complexity of Concepts: The concept of "resolvents" is not a commonly understood mathematical idea. Providing more explanations, along with practical application cases, would greatly aid readers in grasping this concept and its significance in the proposed framework.

We will be very glad to do so! For a camera ready version, we will include an additional section in the Appendix, detailing the significance of resolvents in other fields such as Mathematics and Physics, as well as a detailed mathematical introduction, (following the pedagogical structure of (Teschl (2014)).

• Minor issue: Notation Introduction: The paper occasionally lacks a comprehensive introduction to certain notations. For instance, the notation $T$ in section 3.2 is introduced without adequate context or explanation.

This is indeed a typo, which we thank the reviewer for spotting. We corrected it and now write the Laplacian as $\Delta$ instead of $T$ also in Section 3.2.

• The datasets utilized in this study are primarily small to medium-sized. How would ResolvNet perform in terms of accuracy and computational time when applied to larger datasets?

This is indeed an important question. Following this raised point, we now include a new and additional section (Appendix J: Scaling ResolvNet to large Graphs) in the Appendix that discusses in detail how ResolvNet is scaled to large graphs.

The key ingredient here is a Neumann-representation of the resolvent that avoids an explicit matrix-multiplication: $(T - zId)^{-1} \approx \frac{1}{z} \sum\limits_{k=1}^K (-T/z)^k$ This approximation becomes exact as $K$ is taken o infinity. A similar approximation was already used to scale the PPNP method of “PPNP Paper” to large graphs. This replaces the hypothetical $\mathcal{O}(N^3)$ complexity during preprocessing and $\mathcal{O}(N^2)$ complexity during training and inference that a naïve implementation of ResolvNet would constitute with a $\mathcal{O}(EFN)$ complexity (i.e. the complexity of sparse-dense matrix multiplication). Here $N$ is the number of nodes, $E$ is the number of edges and $F$ is the feature dimension.

Beyond these theoretical considerations and in addition to the empirical complexity analysis already provided in Appendix G, we also evaluated complexity on large graphs experimentally: We trained ResolvNet, ChebNet (both with $K = 1$) and GAT in a two-layer deep configuration with $64$ hidden units in each layer for $100$ epochs on the OGBN-Arxiv and OGBN-Products datasets, which are comprised of $169,343$ Nodes and more than 2M nodes respectively.

Results are collected in the tables below:

OGBN-Arxiv:

OGBN-Products:

As can be inferred from the tables above, ResolvNet takes significantly less time to train per epoch on OGBN-Arxiv, when compared to GAT. It also needs considerably less GPU memory and multiply-accumulate operations compared to GAT.

Compared to ChebNet, our method needs to compute an order of magnitude more sparse-dense matrix multiplication operations (as detailed in Appendix J). This is reflected in the number of performed MACs, which for ResolvNet is roughly an order of magnitude larger than that for ChebNet.

On OGBN-Products, our method remains more complex than ChebNet. In contrast to GAT however, ResolvNet remains trainable.

As for accuracy on large graphs, we again expect better performance on homophilic graphs as ResolvNet’s (necessary) inductive bias towards homophily is independent of graph-size. A full experimental investigation of this question is still ongoing and will be included in a camera ready version of this submission.

• There are some other obvious baselines with which the authors could compare their methods: a. Apply pooling to learn the clusters (say using diffpool, gpool, eigenpooling among others) and then use a generic GNN on the coarsened graph.

We had indeed not thought of this, as our main intention is to design a model that might be deployed at any scale, and does not need to coarse-grain given graphs to a predetermined scale, like pooling does.

Nevertheless, we agree with the reviewer that this is an interesting comparison. We thus followed the reviewers recommendation and combined GCN as a representative baseline with Self-Attention Graph Pooling (SAG-pooling) [1]. We chose SAG-pooling as the pooling method since its implementation does not need data to be loaded in a dense format and hence is compatible with experimental setup.

We considered two implementations:

“SAG” simply pools first and then runs GCN on the coarsened graph.

“SAG-Multi” instead generates graph representations first at the original scale via GCN, then pools, runs GCN on the coarsened graph and generates a second (coarser) Graph representation. This procedure is iterated again and all three representations are combined into a single representation.

We then reran all experiments on QM$7$ data described in Section 5 again also for these two additional baselines.

We here first provide an updated version of Table 2 (listing prediction errors for atomic energy prediction on original QM$7$) with these two baselines added:

As can be inferred from this Table , either way of combining GCN (as the prototypical message passing network) with pooling does not lead to a performance increase on the multi-scale data of the QM$7$-dataset.

We also investigated the graph-level multi-scale stability of these models, updating Table 3 (which evaluated the models trained for Table 2 on coarse-grained/collapsed versions of the molecular graphs in QM$7$):

From this table with the previous one, we may infer that including a learned pooling operations has a drastically negative effect when aiming to transfer models between graphs describing the same object (in this case a molecule) at different resolution-scales:

Additional discussions and an investigation of the behaviour of the (GNN + Pooling)-baselines in comparison with ResolvNet under continuously varying the scale-imbalance within graphs is discussed in Appendix G.1 (c.f. also Fig. 13).

• It is not clearly defined how the two kinds of filters are combined: does a node learn which filter to use?

In principle, any Type-0 filter can represent any fixed Type-I filter, so that the type of filter may indeed be learned. In practice, however it is beneficial to equip models with a stronger inductive bias towards the desired type of transferability (c.f. the discussion after Theorem 4.1). Thus in practice we treat the type-of-filter-choice as a binary hyperparameter. We have made this clearer in our updated manuscript now (c.f. the updated discussion after eq. (2)).

• The abstract is not clear, especially the sentence: At the graph level, multi-scale .." The last sentence also seems to make bolder claims than what the experiments show.

Following this comment, we have amended the last sentence of the abstract and changed the “At the graph level, multi-scale .."- sentence to “At the graph-level, a multi-scale consistent graph neural network assigns similar feature vectors to distinct graphs." describing the same object at different resolutions". We hope that the new formulation is clearer now; but would be happy to change the sentence again.

References:

[1]: Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 3734–3743. PMLR, 2019. URL http://proceedings.mlr.press/v97/lee19c.html

• b. Separate the two networks using Gaussian Mixture Models, have two different GNNs for the two scales, and combine the two representations for node/graph prediction.

We agree that this is an interesting point for comparison. To implement the corresponding experiment, we considered the QM$7$ dataset.

As described in Section 5, weights here essentially correspond to inverse distance between atoms. We hence separate the scales by fixing a cut-off distance: Nodes that are within the cut-off distance of each other are considered to be connected via an edge in $G_{\text{high}}$. Pairs of nodes that are further apart from each other provide an edge in $G_{\text{reg}}$.

The resulting prediction accuracies are provided below:

As can be inferred from this table, the idea of the reviewer significantly improves accuracy for most baselines. However, mean absolute errors of baselines, even after the two-scale-mixture modification, is still at least roughly twice as large as that of Resolvnet (16.52 $\pm$ 0.67 kcal/mol).

Additionally, in order to combine baselines with such a scale-separation procedure, we had to manually select graph decomposition into the respective scales, while ResolvNet automatically takes care of this.

Full details on the considerations above are provided in Appendix G.2.

We would like to sincerely thank the reviewer for the careful review of our paper and the insightful advice, which we have followed diligently. We were especially happy to read that our

Idea of separating a network into multiple scales is nice

and that our

experimental results show the usefulness of the method

Let us address each raised point individually:

• It would be good if the authors could demonstrate the performance of their methods on synthetically generated graphs, say using stochastic block models. That would allow all parameters to be controlled.

We think that this is a great idea as stochastic block models indeed allow to generate graphs with strongly connected communities.

Following this comment by the reviewer, we have thus conducted additional experiments and ablation studies on graphs drawn from stochastic block models. We provide precise descriptions of our experimental setup, as well as full experimental results in the newly created section “Appendix H: Additional Experiments on synthetic Data”.

Here we provide a brief summary of the main result:

We generate graphs using a custom stochastic block model: Apart from cluster-size and number-of-clusters, our model takes as input two probabilities:

The probability $p_{\text{inner}}$ determines the likelihood of two nodes within the same cluster being connected by an edge.

The probability $p_{\text{inter}}$ determines the likelihood for two nodes in different clusters to be connected by an edge.

To numerically verify Theorem 4.2 and showcase the intuition behind Figure 2, we first keep all parameters except for $p_{\text{inner}}$ constant. We then vary $p_{\text{inner}}$ from $p_{\text{inner}} = 0$ (no edges within the clusters) to $p_{\text{inner}} = 1$ (fully connected clusters).

In this setup, we compare the feature vectors that ResolvNet and baselines generate for such graphs with the feature vectors generated by these models for coarse-grained versions of the original graphs where clusters are collapsed to single nodes.

*Figure 14 (b-d) in Appendix H plots corresponding results: As the connectivity within the clusters increases towards full connectivity, the norm difference between features of the original graph and that of its collapsed version decreases for ResolvNet. This is what we desire, as discussed in Section 2 and Section 4: Very strongly connected sub-graphs are supposed to be treated in a similar way that single (collapsed) nodes are.

As is also evident from Figure 14 in Appendix H, baselines (in contrast to ResolvNet) do not exhibit this behaviour. This implies that these baselines are not able to consistently integrate multiple scales and hence are not transferable between different graphs describe the same underlying object at different resolution scales.

Beyond these results Appendix H contains additional investigations and experiments (c.f. e.g. Figure 15 and Figure 16 in Appendix H).

We thank the reviewer for the continued engagement and are very happy to extend our discussion of mixture models:

Performing a manual scale-separation and running simultaneous networks on the different graph-structures improved the relative performance of baselines. This is most pronounced for ARMA, where the performance gap between the standard- and mixture-implementations is roughly a factor of two, which is quite significant; as the reviewer points out.

However, ResolvNet performs better than this best performing micture-model (ARMA-mixture) by an additional factor of two; i.e. with a performance improvement of exactly the same significance.

Thus ResolvNet is still able to incorporate multi-scale data a lot better than mixture-models.

As an important additional point we note the following:

Considering mixture-models (as opposed to ResolvNet) does not lead to graph-level multi-scale consistency.

Mixture-models (as opposed to ResolvNet) are unable to consistently handle graphs describing the same object at different resolution scales:

To showcase this, we have now investigated the graph-level multi-scale stability of mixture-models, by rerunning the experiment corresponding to Table 3 (which evaluated the models trained for Table 2 on coarse-grained/collapsed versions of the molecular graphs in QM$7$) for mixture-models:

When confronted with such different resolution scales, the performance difference between ResolvNet and mixture-models becomes even larger:

While ResolvNet performed better than mixute models by a factor of at least two on same-resolution multi-scale data, the performance gap now varies between a factor of $12$ to $50$ if multiple graph-resolutions are considered.

Thus:

1. For single-resolution multi-scale data, ResolvNet performs better than mixture-models by a factor of two and more
2. In multi-resolution, multi-scale settings ResolvNet performs better than mixture-models by a factor of $12$ to $50$

We hope our extended discussion was able to clarify our earlier commentary. We of course stand by, should further questions arise.

We sincerely thank the reviewer for the continued engagement with our work.

• What was the effect of manual separation on the node classification datasets?

One of the inherent drawbacks of the suggested manually-scale-separated mixture-model baseline is that any given graph needs to be manually separated into distinct graph structures (corresponding to the different scales) before such a baseline may be run.

The node classification datasets (i.e. Citeseer, Cora, etc.) are not inherently multi-scale. It is thus not clear how such a manual separation into distinct scales as suggested should proceed on these datasets.

Should the reviewer have a separation method in mind, we would be happy to combine this separation-method with the already suggested mixture-models and conduct further experiments with this additional baseline in a camera ready version of our submission.

• If I understand the authors' response, the performance of the method should be judged more on the regression task than the node classification task. Why then there is so much emphasis being placed on node classification in the experimental results? Are there any other tasks where the method does well?

The focus of our paper is to introduce the concept of multi-scale consistency for graph neural networks. As we detail in the paper, this concept has two aspects:

1. For a fixed multi-scale graph, multi-scale consistency refers to an unrestricted flow of information over the entire graph, even if connectivity varies within said graph

2. When confronted with graphs describing the same object at different resolution scales, a multi-scale consistent network assigns similar feature vectors to graphs describing this same object at different resolution scales.

We showcase the lack of multiscale consistency of baselines and how the proposed ResolvNet is able – in contrast to baselines – to consistently incorporate varying scales in different experiments:

1. To showcase the first point 1) above, we e.g. conduct experiments on QM$7$ data. Here edge weights essentially correspond to inverse distances. Atoms that are far-away from each other are thus connected via edges with far lower weights. However, long-range communication (i.e. along the weight suppressed lower connectivity scale) within such molecular data is important for prediction tasks (c.f. the references provided in our paper). Since ResolvNet is able to better incorporate such varying connectivity scales than baselines (as established in extensive theoretical discussions, in our experiments and further cemented via additional experiments in the discussion phase), ResolvNet is able to better predict molecular properties than baselines.

2. To showcase the second point 2) above, we e.g. confronted ResolvNet and baselines with coarse-grained descriptions of molecules during inference. ResolvNet’s prediction capabilities remained the same, while those of baselines severely declined (c.f. Table 3, or the discussion in an earlier comment).

While these are the settings that our paper is concerned with and indeed the type of tasks ResolvNet was designed for, we find it important to also evaluate ResolvNet against other baselines on the standard banchmark of node classification. We make this clear by writing

To establish that the proposed ResolvNet architecture not only performs well in multi-scale settings, we conduct node classification experiments […]

when discussing the corresponding node-classification results of Table 1.

An inductive-bias towards homophily is necessary, to achieve multiscale consistency, as was discussed in the paper. We thus expect ResolvNet to perform well on homophilic graphs. This is indeed what our experiments show, with ResolvNet being by far the best performing method in this realm (c.f. Table 1).

In total we thus established ResovNet’s superior performance in three different real-world settings:

1. For node classification on homophilic graphs, ResolvNet was the best performing method (c.f. Table 1)

2. On muli-scale data ResolvNet performed significantly better than baselines (c.f. e.g. Table 2 for experiments on corresponding real world data)

3. In the multi-resolution-scale setting, ResolvNet also performed significantly better than baselines (c.f. e.g. Table 3 or Figure 7)

We hope this discussion has clarified the versatility aspect of ResolvNet.

We of course stand by should additional questions arise and would be happy to include even more experiments in a camera ready version of our paper.