Understanding and Tackling Over-Dilution in Graph Neural Networks

With sincerely thank you for recognizing our contributions, we've carefully addressed each point in the review to further elevate our work.

---

W1: The significance of the paper exhibiting over-dilution in deep layers without the presence of other phenomena, e.g., over-smoothing

Identifying over-dilution in deep layers without interference from other phenomena like over-smoothing is challenging due to the shared underlying cause, such as the size of the receptive field.

Therefore, our focus was on demonstrating the impact of over-dilution on performance in a single layer, where other phenomena are less prevalent.

For a more detailed explanation, please refer to our response to W2 & Q4.

---

W2 & Q4: Experimental evidence of NATR’s effectiveness in addressing the over-dilution issue

• intra-node dilution

We may not have emphasized this sufficiently in the text, but Table 5 clearly demonstrates the effectiveness through a comparison between (A)- $*MLP*$ and (D)- $*NATR*_{\text{MLP}}$.

In both models, message passing is not utilized, ruling out the issue of over-smoothing.

In this context, the performance improvement observed with NATR can be attributed to its ability to resolve over-dilution at the intra-node level, regardless of the over-smoothing issue.

It's important to note that even with an increased number of parameters in the MLP model, there was no observed improvement, further emphasizing NATR's unique capability in addressing over-dilution.

• inter-node dilution

We demonstrated single-layer over-dilution using the Computers dataset as an example. Here, a typical node has 204 attributes (median value) and 19 neighbors (median degree). In this case, each attribute's representation dilutes to approximately 0.025% per layer with either the mean or sum aggregation operator.

Table 9 in the Appendix reveals that NATR significantly outperforms MPNNs even with a single layer, as evident in examples (q) and (r).

Typically, issues like over-smoothing, over-squashing, and over-correlation occur after multiple layers of message passing.

Hence, this demonstrates NATR's effectiveness in mitigating mainly over-dilution, both at the intra-node and inter-node levels.

---

W3: Difference with over-correlation

According to Jin et al., the over-correlation refers to the phenomenon where the feature representations learned by the stacked network become highly correlated across different dimensions.

In the node-level representation of MPNNs, each dimension does NOT mean each attribute representation (for initial node representation, it is a summed value of the corresponding dimension from attribute-level representations).

Therefore, the concept of over-dilution is distinct from overcorrelation.

Also, the intra-node dilution can occur even at the single-layer while overcorrelation is observed when stacking layers.

However, we agree that it would be good to discuss its connection to overcorrelation because both of them are unique perspectives to construct more informative node representations.

---

Q1, Q2, Q3: the criteria for selecting the datasets

We selected benchmark datasets that contain attribute information.

OGB offers dense node features (or one-hot vector) rather than explicit attribute indicators.

For the ogbl-ddi dataset, we were able to extract attributes in a fingerprint format (binary vector) using RDKit, which is why it has been included in our benchmark dataset selection.

If there is a larger dataset that contains attribute information, we will include it as our benchmark dataset.

---

We appreciate your feedback and would like to clarify any contributions that we may not have sufficiently emphasized in the current version.

---

W1: Experiments on other datasets such as ogbn-arxiv or ogbn-product

Since Reviewer HxeZ also pointed this out, it seems we missed adding more explanation about this point.

We chose benchmark datasets containing attribute information, as our primary focus is on attribute-level representation.

However, OGB offers dense node features rather than explicit attribute indicators.

• ogbn-arxiv : 128-dimensional feature vector obtained by averaging the embeddings of words
• ogbn-product : 100-dimensional feature vector obtained by PCA of bag-of-words features

In the case of the ogbl-ddi dataset, we successfully extracted attributes in a fingerprint format (binary vector) using RDKit and DrugBank DB.

If larger datasets become available that include explicit attribute information, we are certainly prepared to include them in our benchmark datasets.

---

W2: The implication of the analysis in Section 6.2

You are correct. Indeed, the subsets of the bottom 25% and the top 25% were separated following Eq (7) (as two-hops version) and we used the fixed subsets for a fair comparison between MPNNs and NATR.

As presented in Table 4, we delve deeper into how the NATR model exhibits performance improvements when combined with MPNNs.

GCN, GAT, and SGC demonstrate notably lower performance on over-diluted nodes (bottom 25%).

For the same subsets, NATR shows a more significant improvement in performance on over-diluted nodes than less-diluted nodes.

This distinction highlights the effectiveness of NATR in mitigating over-dilution issue and illustrates the benefits of our proposed approach in enhancing model performance where MPNNs may struggle.

---

W3: How the method addresses the inter-node dilution

To address inter-node dilution, NATR's attribute decoder integrates attribute representations across all layers.

This integration helps prevent the dilution of a node's own information in the context of its neighboring nodes.

The final node-level representation of node $v$, $\tilde{H}_v^{(M)}$ is calculated by combining two representations: $H_v^{(M)}$ for graph context information and $O_v^{(M)}$ for node $v$’s specific information, exclusively.

This approach effectively mitigates inter-node dilution, maintaining distinct node information within the graph context, as described in Eq (11) and Figure 2 (b).

---

Q1: The number of parameters of each model and the effect of additional parameters

It is an acknowledged fact that the use of a transformer architecture in NATR leads to additional parameters and increased computational complexity.

However, it is important to note that simply increasing the number of parameters in existing MPNNs does not yield performance improvements comparable to those achieved by NATR.

You can see the degradation of performance in MPNNs when the number of parameters (layers) increases in Table 3.

Significantly, NATR leverages the transformer architecture to effectively address the issue of over-dilution.

This not only enhances performance but also facilitates the use of deeper layers (please see Table 9 as well), demonstrating the utility and efficacy of our approach.

---

Q2: the performance would change with different numbers of attributes in a graph

The performance can be affected not only by the number of attributes but also by the complicated property of each attribute.

Therefore, it is hard to figure out the trend of the correlation between performance and the number of attributes.

---

Q3: feature selection methods can help to alleviate this problem

We agree that feature selection methods can be beneficial in mitigating the issue of combining attributes with varying levels of importance. However, these methods typically apply uniform weighting across all nodes.

Nevertheless, it's crucial to recognize that the significance of attributes can vary from node to node.

For instance, while attribute 't' may be important for node A, it might not hold the same level of significance for node B.

Our NATR model addresses this by employing a graph context-aware attribute decoder.

This decoder utilizes node-level representations as queries, which enables the assignment of greater weight to the more significant attribute representations for each individual node.

This approach ensures that the importance of attributes is determined in the context of each node's specific role and relationship within the graph.

---

Thank you again for your valuable comments. We have attempted to address each of your questions thoroughly, enhancing the clarity of our paper's contributions. Please let us know if there are points that require further explanation!

Thank you for the very detailed feedback, it has been instrumental in refining our work and highlighting its strengths.

---

W2 & Q5: Clarification on Over-Smoothing, Over-Squashing, and Over-Dilution

We realize we may not have delved into the details as thoroughly as needed, although we have compared these concepts in Figure 1, we'll expand the discussion in the main text.

Appendix Section A and Figure 4 provide further details both conceptually and theoretically.

Over-dilution presents a novel and comprehensive concept, while being related to over-smoothing and over-squashing in terms of information distortion in graph structures.

• Unique perspective on intra-node dilution

We acknowledge that our initial presentation may have overlooked the unique aspects of intro-node dilution. Unlike over-smoothing and over-squashing, which are primarily concerned with node-level representation, over-dilution encompasses both node-level and attribute-level representations, crucial for forming informative representations on graphs. This phenomenon can arise at the intra-node level due to an excess of attributes within nodes, independent of the triggers for over-smoothing and over-squashing.

• Comparison with over-smoothing

In contrast to over-smoothing, where node representations become increasingly similar due to the exchange of information across multiple hops, over-dilution can arise even in single-layer aggregations, as demonstrated in our primary discussion. Take, for example, a star graph structure, which is essentially a tree with a central node and several leaf nodes, each linked to the central node by a single edge. Following a single message-passing step, the central node may experience over-dilution, but over-smoothing among nodes is less likely to occur since the leaf nodes do not share features with one another.

• Comparison with over-squashing

Regarding over-squashing, we now understand that our initial explanation may have been too concise. Unlike over-squashing, which deals with long-range information propagation between nodes, over-dilution focuses on the attenuation of information at individual nodes, observable even in the first layer based on aggregation coefficients. This distinction is evident in our analysis, where over-dilution is shown to be a prevalent issue even in short-range interactions, challenging the traditional understanding of information propagation in graph neural networks. Conceptually, over-dilution focus on the preservation of information (formally $\partial h_x^{(l)}/\partial h_{\color{Red}x}^{(0)}$), while over-squashing focus on the propagation ( $\partial h_x^{(l)}/\partial h_{\color{Red}y}^{(0)}$).

---

Q1 & Q2: Comparison with GCNII

First and foremost, it's essential to clarify that NATR works as a complementary model to any node embedding module, not as a competitor to a specific standalone model.

Although GCNII is effective in mitigating over-smoothing, this does not necessarily make it superior to NATR, as NATR is specifically tailored to address the issue of over-dilution.

When equipped with GCNII as its node embedding module, $*NATR*_{\text{GCNII}}$ could potentially yield a more informative node-level query in the attribute decoder.

In Table 8 and Section F of the Appendix, we present the performance of NATR using different node embedding modules, demonstrating its compatibility rather than positioning it as a competitor.

This experiment involved a hyperparameter search, the details of which are outlined in Section E of the Appendix.

---

Q3: Experiments on larger datasets such as ogb-arxiv, ogb-citation2, or ogb-ppa

Your point regarding dataset selection is well-taken.

Our choice to use benchmark datasets with explicit attribute information was intentional, as we aimed to highlight NATR's capabilities in handling such data.

For OGB, we encountered datasets offering dense node features or one-hot vectors rather than explicit attribute indicators:

• ogbn-arxiv : 128-dimensional feature vector of word embeddings
• ogbl-ppa : one-hot vector
• ogbl-citation2 : 128-dimensional word2vec features

In the case of the ogbl-ddi dataset, we successfully extracted attributes in a fingerprint format (binary vector) using RDKit and DrugBank DB.

If larger datasets that include explicit attribute information become available, or if you are aware of any, we would definitely be happy to consider them!

---

We want to express our gratitude for the thorough review and have addressed each concern in detail.

---

Q1: Clarification on notations.

In MPNNs, the initial node-level representation $h_v^{(0)} \in \mathbb{R}^d$ is a summation (or averaging) of attribute representations $z_t \in \mathbb{R}^d$, such that $h_v^{(0)} = \sum_{t \in \mathcal{T}_v} z_t$.

Therefore, the $t$-th value of $h_v^{(0)}$ is NOT the same as $z_t$; instead, each dimension of $h_v^{(0)}$ is a summed value of the corresponding dimension from attribute-level representations.

We define the dilution phenomenon as two cascaded sub-phenomena as intra-node dilution→ inter-node dilution.

The intra-node dilution occurs when constructing the initial node-level representation $h^{(0)}_v$ while the inter-node dilution occurs when aggregating node-level representations (for $h^{(k)}_v$).

Therefore, we use the initial node-level representation $h^{(0)}_v$ (NOT $h^{(k)}_v$) in Eq. (3) to describe the intra-node dilution.

---

Q2 & Q7: Connection to overcorrelation (Jin et al.).

According to Jin et al., the over-correlation refers to the phenomenon where the feature representations learned by the stacked network become highly correlated across different dimensions.

As we answered in Q1, each dimension of node-level representation does NOT mean each attribute representation (it is a summed value of the corresponding dimension from attribute-level representations.).

Therefore, the concept of over-dilution (specifically, the intra-node dilution) is distinct from overcorrelation.

Also, the intra-node dilution can occur even at the single-layer while overcorrelation is observed when stacking layers.

However, we agree that it would be good to discuss its connection to overcorrelation because both of them are unique perspectives to construct more informative node representations.

We will incorporate this discussion into the revised version of our paper.

---

Q3, Q5, Q7: Difference with the influence distribution (Xu et al.) and over-squashing

While the influence distribution with Jacobian (Xu et al.) serves as a clear framework to analyze limitations of MPNNs, as utilized in the over-squashing paper (Topping et al.), our Definition 3.2 is NOT the same.

The numerator in our Definition 3.2 differs to reflect our unique perspective on how information is preserved within nodes (i.e. $\partial h_x^{(l)}/\partial h_{\color{Red}x}^{(0)}$), in contrast to the approach of Xu et al. and Topping et al., which focus on information propagation between nodes (i.e. $\partial h_x^{(l)}/\partial h_{\color{Red}y}^{(0)}$) .

(we have appropriately mentioned and cited the use of the influence distribution with Jacobian in our work.)

For a detailed comparison with over-squashing, please refer to Figure 1 in the main text and Section A with Figure 4 in Appendix.

---

Q4: Relationship between degree fairness (normalization) papers.

Thanks for the suggestion of the discussion about potential link between our Hypothesis 2 and the concept of degree fairness!

Our Hypothesis 2 indeed provides a comprehensive framework to examine the interplay between over-dilution and aggregation weight $\alpha$ that can be defined not only by degree but also by factors like the attention coefficient, as seen in GAT models.

Recognizing this, we agree that it is valuable to delve into a more detailed discussion of the connections with these specific works, thereby enriching our analysis of the over-dilution phenomenon and its broader implications.

---

Q6: The performance of NATR when the number of layers increases.

As you correctly noted, NATR indeed retains its advantages even as the number of layers increases.

It's important to emphasize that our primary goal is to demonstrate the effectiveness of NATR in solving the over-dilution phenomenon, rather than specifically focusing on building deep GNNs.

In our main experiments, we found that just 5 layers were sufficient to saturate the size of receptive field (please refer to Figure 2 (b)) and to significantly degrade the performance of MPNN models, effectively demonstrating the efficacy of NATR in such a context.

However, to further illustrate NATR's robustness with an increased number of layers, we’ve extended our experiments up to 12 layers, as shown in Table 9 of the Appendix.

These additional experiments have confirmed that NATR not only maintains its performance but also improves upon it compared to the results observed with 5 layers in the main text.

---

Your feedback has been invaluable in enhancing our paper. We believe we have addressed each point and hope our revisions have made our contributions more evident. Please let us know if any question still needs clarification.