Towards Dynamic Message Passing on Graphs

Thank you for your kind suggestions and insightful questions about our work. We hope the following response can address your concerns. We also kindly refer you to the PDF in the global response for the new figures/tables during the rebuttal due to the limited number of characters.

W1: Theoretical explanations on why $N^2$ works for over-squashing/smoothing.

Response: We provide some intuitive and sketchy theoretical analysis. We will keep working on this in the future.

• Over-smoothing: $N^2$ learns the displacements of nodes and gives rise to the linear combination of the layer input, the local message passing output, and the global message passing output. Specifically, the layer input represents the output of an all-pass filter, the local output is from a low-pass filter, and the global output is from a filter that aggregates messages from nodes of learnable similarity, and thus possesses learnable frequency characteristics. The messages from the all-pass filter and the learnable filter prevent the output from over-smoothing.

  • We must note that global message passing with the uniform connection provides the SAME global output for all the graph nodes. This output can be regarded as a shared bias term and cannot alleviate over-smoothing. Please refer to Fig R1b in the PDF response for empirical results.

• Over-squashing: $N^2$ tackles over-squashing by detouring from the original graph bottlenecks and avoiding forming new pseudo-node bottlenecks.

  • First, pseudo nodes provide two-hop message highways for graph nodes. Therefore, graph nodes do not have to pass messages through the original bottlenecks.
  • Second, the pseudo-node bottlenecks stem from the overwhelming number of graph nodes in the receptive field of each pseudo node. However, by multiplying edge weights with the messages from these nodes, certain messages can be eliminated and thus exclude the nodes from the receptive field. We can define the effective receptive field size based on the value of the edge weights, where nodes with smaller edge weights are eliminated from the effective field. This elimination reduces the size of the effective receptive field and avoids forming bottlenecks.
    • Uniform connection shares the same edge weights for the messages from all nodes. Therefore, these messages are either completely eliminated or preserved, which cannot reduce the size of the effective receptive field. In Fig R1a in the PDF response, we show that $N^2$ with uniform connection is less effective in tackling over-squashing.
    • Our dynamic connection measures the specific edge weights for each node, learning to eliminate messages from certain nodes, and thus reduce the size of the effective receptive field.

W2: Comparison with graph structure learning or graph rewiring methods.

Response: Thank you for your suggestion. There are some graph transformer or GNN methods in our manuscript that also employ graph structure learning or rewiring strategies, such as Exphormer with the expander graph and DRew, GPRGNN, and H$_2$GCN with edge shortcuts. Except for these methods, we also compared $N^2$ with DGM (L79-80), a graph structure learning method, and the results are presented in Tab. R3. $N^2$ shows better performance compared to DGM.

Q1: Why use the recurrent layer?

Response:

• Why recurrent layer: The recurrent layer is the core of $N^2$. It is an implementation of the message passing in the common space from Sec 3. The recurrent layer, including pseudo-node adaptation and dynamic message passing, empowers dynamic interactions between nodes. $N^2$ employs the layer to move nodes recursively to their optimal positions.

• Why recurrence: The main reason $N^2$ uses the parameters recurrently for the layer is to largely reduce the number of parameters. According to the ablation study in Fig. 8, nodes require multiple steps to move to their optimal position. Each step corresponds to a new layer with a set of parameters. To reduce the number of parameters, we conducted an ablation study and found that the layers can learn to move nodes based on their current positions. Therefore, a single set of parameters will be sufficient and thus give rise to the recurrent layer.

Q2: Why propose proximity measurement instead of distance metrics?

Response: Compared to distance metrics, such as Manhattan and Euclidean distance, proximity measurement has lower spatial complexity. We tested distance and proximity with torch.cdist and torch.matmul during model design. Results show that distance-based $N^2$ is on par with proximity-based $N^2$, but the distance version encounters out-of-memory problems under many hyperparameter settings. Therefore, we choose proximity (inner product) for $N^2$.

Thank you very much for the valuable suggestions for our paper. Under your guidance, we have discovered new advantages of $N^2$ compared to uniform connections and rewiring. We also kindly refer you to the PDF in the global response for the new figures/tables during the rebuttal due to the limited character number.

W1&W2: More explanation of the pseudo-node bottleneck and why $N^2$ can reduce the bottlenecks in both pseudo nodes and input graphs.

Response:

1. Uniform connection leads to pseudo-node bottlenecks has been explained in L42-45 and Fig 1, before citing [1]. More rigorously, [1,R1] refer to bottlenecks as nodes with large effective receptive fields. The uniform connection forms pseudo-node bottlenecks by taking all the graph nodes into the receptive field equally. This results in large effective receptive fields on large-scale graphs and thus forms bottlenecks. We also evaluate $N^2$ with the uniform connection in Fig R1 in the PDF response, which shows inferior performance in tackling over-squashing.

2. Adding pseudo nodes with uniform connection provides more pseudo-node bottlenecks, where each pseudo node still incorporates all graph nodes into its receptive field.

3. Subsampling edges can remove some informative interaction between nodes, leading to sub-optimal message passing.

4. $N^2$ for pseudo-node bottlenecks: we have provided both intuitive and empirical analysis in L48-49 and Sec 5.3.3 to show that $N^2$ DOES NOT form pseudo-node bottlenecks. $N^2$ learns the edge weights between graph and pseudo nodes through spatial relations. Therefore, it can eliminate messages from certain nodes while preserving the others, reducing the size of the effective receptive fields.

   • Note that L297 refers to the pseudo-node bottlenecks specifically. We will fix this in the revision.

5. $N^2$ for input-graph bottlenecks: we have provided empirical results in Sec 5.3.2 that $N^2$ can tackle over-squashing. This is because $N^2$ optimizes the global two-hop message highways based on specific tasks and avoids forming new pseudo-node bottlenecks. The global highways detour messages from the input-graph bottlenecks. Therefore, the original bottlenecks may still exist but are well circumvented.

W3: Comparison with rewiring methods (DRew).

Response: Thank you for bringing up this insightful question to us. The rewiring methods and pseudo-node methods actually represent the local-to-global and the global thread, respectively. Both threads are effective in improving message passing. We choose DRew[2] to represent rewiring methods, which has been referred to by many reviewers. The main reasons we need globality in one layer are:

• Less layers: Pseudo-node methods require less layers than rewiring methods. For example, 6-layer $N^2$ surpasses 13-layer DRew in Tab S7 in the paper. We note that DRew with positional encodings will not be taken into comparison, because of the injected globality into node features.
• Less memory usage: Rewiring methods either directly add edges to the input graphs or gather messages from multi-step neighbors in one layer. Both require more memory usage. We evaluate DRew on the same dataset in Sec 5.3.1. DRew is out-of-memory when the number of graph nodes surpasses 200,000 with 2 convolution layers and 8,000 with 3 layers.
• Better efficiency: Rewiring edges is also time-consuming. We compare the computational complexity between $N^2$ and DRew with the same number of convolution layers/recursive steps. Fig R2 in the PDF response shows that DRew requires more time when scaling to large graphs.
• Simpler preprocess: $N^2$ only requires the pre-construction of the adjacency matrix while DRew sample or select multi-step neighbors. We even encountered the timeout problem when trying a larger number of layers (5,6) on DRew on large graphs such as ogbn-arxiv.

Besides DRew, we have also compared with other rewiring methods, such as GPRGNN and H$_2$GCN in Tab 3 and 4.

Q1: Positional/structural encodings usage.

Response: No positional or structural encodings are used for $N^2$. Except for being specifically noted, all the baseline results are from the original papers. Among X+pseudo node methods, only MPNN+pseudo node uses the positional encoding.

Q2: Hyperparameter settings.

Response: We perform grid search for the hyperparameters based on the loss of the validation split, including the recursive steps $\in$[1,10], the hidden and the state space dimension $\in${64,128}, the number of pseudo nodes $\in${8,16,32,64,128,256,300,320}, and dropout $\in$[0,0.8] with step equals 0.1. The rest of the hyperparameters are fixed as reported in the Appendix and have not been specially tuned on individual datasets.

All the learnable parameters in $N^2$ are optimized during training, including the weights in the linear transformation, $\lambda$ in the proximity measurement, and the pseudo/class-node states. The cross-entropy loss is adopted for classification and the L1 loss for regression.

Q3: Why $N^2$ outperforms graph transformers.

Response: We attribute this to the flexible pseudo nodes:

• Simpler objective. Instead of optimizing relations with all the other nodes, $N^2$ empowers the graph nodes to focus on relations with pseudo nodes, which are of a much smaller amount.
• Information filter. The pseudo nodes can also be regarded as the information bottleneck [R2] in the graph space which filters out redundant information. This can be supported by the pseudo-node ablation in Fig. 7, where node amounts are upper-bounded to serve as an effective information filter.

[R1] On the Bottleneck of Graph Neural Networks and its Practical Implications, ICLR21

[R2] Deep Variational Information Bottleneck, ICLR17

Dear reviewer,

Take note that, as per the conference instructions, the authors forwarded me a link to an external anonymized page that shows the scripts they used & the associated hyperparameters.

Let me know if you would like to see something specific and I will forward you the information.

kind regards AC

Thank you very much for your valuable suggestions that help us improve our paper. We respectfully refer you to the PDF in the global response for the new figures/tables during the rebuttal due to the limited character number.

W1&Q1(a): Why $N^2$ mitigates over-smoothing/squashing.

Response:

1. Over-smoothing
   • Unlike the uniform connection that shares edge weights for all the graph nodes, our dynamic connection measures specific relations for each graph node. Therefore, although two nodes are connected on the input graphs, they receive different outputs from global message passing (MP) and avoid becoming too similar to each other.
   • Learning node displacements allows the addition of layer input, local and global output. Thus, even with local MP, the other two features maintain high-frequency signals.
2. Over-squashing
   • Pseudo nodes produce two-hop message highways, detouring messages from the graph bottlenecks.
   • Dynamic connections avoid forming new pseudo-node bottlenecks that hinder global MP.
3. Why local MP: previous studies show the importance of encoding graph structures[R1]. Therefore, we adopt local MP to implicitly encode graph structures.

To further evaluate our dynamic connection, we apply the uniform connection to $N^2$, which shows performance degradation in tackling over-smoothing/squashing problems in Fig R1 in the PDF response.

W2&Q1(b): Motivation and ablation on the recurrent layer.

Response:

• Motivation for the layer: We propose the recurrent layer, including BOTH pseudo-node adaptation and dynamic MP, to move nodes from current positions towards the optimal positions (L147-148).
  • To move towards optimal position: Given the current node positions, a recurrent layer learns the displacements the nodes should take, changing their distribution in the space.
  • To base on current positions: The recurrent layer employs pseudo-node adaptation and bases the edge weights for MP on the spatial relations between nodes, to adapt to nodes in various positions. The changes in position also reshape the spatial relations and thus reshape the message pathways.
• Motivation for the recurrence: We adopt a single recurrent layer used recurrently to reduce the number of parameters, instead of modeling node displacement by different layers for each step.
• Ablation. We have already evaluated layers without recurrence in Sec 5.3.4. Multiple recurrent layers do not share parameters and thus are not recurrent. We further remove the layer completely. With only input and output modules employed, Tab R1(b) in the PDF response shows performance degradation.

W3&Q2(a): Contribution compared to Exphormer.

Response:

1. Compared to Exphormer, we highlight our $N^2$ as follows

   • A new perspective to model MP, where nodes are distributed in a common space; they communicate based on their spatial relations and learn to optimize their positions.
   • Fewer parameters by a single shared recurrent layer.
   • Better scales up to large graphs (Tab 4).

2. Technically speaking, our $N^2$:

   • decouples global MP into g(raph)-nodes to p(seudo)-nodes, p to p, and p to g. Instead, Exphormer performs MP between all nodes, which cannot differentiate between messages from pseudo or graph nodes.
   • multiplies proximity with messages. Instead, Exphormer employs normalized attention, which can yield equally small weights and attenuate the messages, especially when the optimal assignment involves a large number of graph nodes to the same pseudo node.

We also evaluate the mixed messages or attention from Exphormer on $N^2$, where both show performance degradation in Tab R1(c) in the PDF response.

W4&Q3: Hyperparameters.

Response: We have performed grid search for the hyperparameters of $N^2$ (Tab S6) and the reproduced models based on validation loss. We emphasize that the superiority of our results is valid and the baseline results can be fully reproduced. Please refer to our AC for the URL of detailed hyperparameter config files.

W5&Q2(b): Design comparison with graph pooling.

Response: First, we clarify that we have provided a discussion on graph pooling in L86-91, not just in L76. Second, the differences between pseudo nodes and graph pooling can be summarized as:

• Different objectives. Pseudo nodes optimize communication efficiency while pooling nodes capture the hierarchy in the graph structures, ensuring better structure compression.
• Physical connection. Pseudo nodes are physically connected to graph nodes as part of the graphs and participate in the MP. In contrast, pooling nodes are higher-level abstractions of graph nodes and are not physically connected with them.
• Intercommunication. Pooling nodes use the coarse adjacency matrix for the MP. Pseudo nodes are free from structure-preserving constraints and learn fully connected pathways.

W6: Comparison with hierarchical GNNs.

Response: We have performed comparisons in Sec 5.1 with some representative hierarchical GNNs from L86-91. Please let us know if you are referring to other types of GNNs.

Q4: Details for Tab 5.

Response: Tab 5 follows the settings from Sec 5.1/5.2. and the hyperparameter setups in Tab S6. Tab R1(a) in the PDF response shows the standard deviation results for three runs.

Q5: Font size, typo.

Response: Thank you for your suggestions. We will fix them in our revision to ensure readability.

Q6 (Limitation): More limitation discussion based on the reviewer's open questions.

Response: We will revise our paper based on your reviews. For Q1(i), we can only provide intuitive/empirical analysis, not rigorous proof due to limited rebuttal time. We will add this to our limitation part and keep working on it.

[R1] Do Transformers Really Perform Bad for Graph Representation? NeurIPS21

Thank you very much for your positive feedback. We will refine our manuscript based on the rebuttal, including clarifying our motivations and contributions, delineating hyperparameter setups (based on our provided config files), and increasing the font size of tables and figures. We sincerely appreciate your suggestions, which have significantly helped us improve our work.

Thank you very much for your support and valuable suggestions that further broaden the potential application of our method to graph interpretations and other neural networks. We will keep studying these problems in the future.

Q1: Can we learn an additional pseudo node to provide global guidance?

Response: If we understand your question correctly, the additional pseudo node refers to the pseudo node of the current pseudo nodes. Please let us know if we make a mistake.

• Global guidance in $N^2$. Given the number of pseudo nodes is relatively small, we directly apply dense pairwise message passing between pseudo nodes in the original $N^2$, which empowers the pseudo nodes to capture global information. The captured global information can be further fed back to graph nodes and serve as global guidance. The learning of global information can be supported by $N^2$ for graph classification where we employ pseudo-node states as the graph-level outputs.

• Additional pseudo nodes. Following your suggestion, we further add an additional pseudo node that aggregates messages from the current pseudo nodes. The results are presented in Tab. R2. We can see that the additional pseudo node cannot further benefit $N^2$. However, regarding the pseudo nodes as cluster centers is interesting, and may help us to extend $N^2$ to graph interpretations. We will keep studying it in the future.

Q2: Discussion between dynamic and adaptive message passing.

Response: We kindly refer you to the introduction and related works in our manuscript where we have discussed dynamic message passing with adaptive message passing. To summarize, dynamic message passing achieves global message passing without forming new bottlenecks and requires linear computational complexity. Dynamic message passing also empowers shared parameters thus reducing the number of parameters required.

Q3: Broader application of the dynamic message passing.

Response: Thank you for bringing up this interesting and inspiring question to us. First, in the context of graph representation learning, dynamic message passing currently only employs neighbor smoothing for local message passing to keep our method as simple as possible. However, it can be further combined with other graph models to improve the effectiveness of our local message passing.

Second, our dynamic pseudo-node strategy can also be applied to networks such as Transformer to reduce their computational complexity. This is a very interesting question and we will dig it up in the future.