Understanding and Tackling Over-Dilution in Graph Neural Networks

Junhyun Lee, Veronika Thost, Bumsoo Kim, Jaewoo Kang, Tengfei Ma

TL;DR

Graph Neural Networks often lose critical node attribute details due to naive feature aggregation mechanisms. This paper introduces "over-dilution"—a phenomenon where important local signals are drowned out within a single layer—and proposes the Node Attribute Transformer (NATR) to dynamically weight and preserve these essential attribute-level details.

What Problem Does This Paper Address?

While Graph Neural Networks (GNNs), particularly Message Passing Neural Networks (MPNNs), excel at learning from graph-structured data, they suffer from well-documented structural pathologies like over-smoothing (nodes becoming indistinguishable over deep layers) and over-squashing (information bottlenecks from distant nodes).

However, the authors identify a distinct, overlooked limitation: over-dilution. This happens when a node's specific, high-value attribute information gets drowned out during feature aggregation, even within a single layer. The authors break this down into two cascading sub-phenomena:

  1. Intra-node dilution: A node's unique attributes are uniformly averaged or summed, burying a small subset of highly critical features under a mountain of less relevant ones.
  2. Inter-node dilution: A node's distinct local signal is overwhelmed by the sheer volume of feature information aggregated from its neighbors.
Figure 1: (a) illustrates an attributed graph, where each node is initially characterized by a set of attributes with corresponding embedding vectors. (b) demonstrates the two-step dilution process in the first layer of MPNNs. The first step, intra-node dilution, involves forming the node-level representation by summing its attribute representations, leading to reduced influence of each attribute, especially with an increasing number of attributes. The second step, inter-node dilution, occurs during message propagation, where a node’s representation is integrated with those of its neighboring nodes. (c) and (d) illustrate the phenomena of over-smoothing and over-squashing, respectively.

Methods

To combat over-dilution, the authors introduce the Node Attribute Transformer (NATR). Instead of treating node attributes as a static vector to be uniformly combined, NATR treats attribute representations as individual tokens (akin to words in natural language processing).

The architecture consists of two primary components:

  • Attribute Encoder: Employs Multi-Head Self-Attention (MHSA) to learn and model the underlying correlations between different attributes.
  • Attribute Decoder: Uses cross-attention to dynamically adjust attribute weights based on the local structural context. It integrates a base node embedding module (such as a GCN or GAT) to generate queries, ensuring that attribute importance is evaluated relative to both the node's characteristics and its neighborhood.

NATR is highly flexible: it can serve as a standalone architecture or be deployed as a modular plug-in to enhance pre-trained, industry-established MPNN models without requiring a full retrain from scratch.

The overall architecture of the Node Attribute Transformer (NATR).

Datasets

The authors evaluated NATR across four benchmark datasets using the Open Graph Benchmark (OGB) pipeline:

  • Amazon Computers & Amazon Photo: Segments of the Amazon co-purchase graph where nodes are products, edges represent frequent co-purchases, and attributes are bag-of-words derived from product reviews.
  • Cora ML: A standard citation network where nodes are documents and attributes are bag-of-words text features.
  • OGB-DDI (Subset & Full): Drug-drug interaction graphs where node attributes consist of molecular substructures (Morgan Fingerprints) extracted from the DrugBank database.

Key Insights and Ideas

  • Over-dilution is an immediate, single-layer threat: Unlike over-smoothing, which manifests across deep networks, over-dilution strikes in the very first layer if a node possesses a high number of attributes or neighbors.
  • Local context dictates attribute value: A specific attribute (e.g., geographic location vs. academic interest in a social network) might be highly informative for one community but pure noise for another. NATR's dynamic weighting allows the network to adapt locally rather than enforcing a global, uniform treatment.
  • Preserving uniqueness naturally halts over-smoothing: By protecting attribute-level details, NATR keeps node representations distinct. Consequently, it inherently mitigates over-smoothing, maintaining high node distinctiveness even as network depth increases.

Key Results

The authors evaluated NATR on link prediction (measured by Hits@20) and node classification tasks:

  • Link Prediction Performance: NATR consistently yielded massive performance boosts over standard baselines. On the Computers dataset, NATR-GCN achieved 42.38% Hits@20 compared to standard GCN's 31.01%. When paired with GAT, it boosted performance from 24.73% to 40.63%.
  • Resilience to Depth: Standard MPNNs degrade rapidly when stacked. For example, standard GAT performance on Computers plummeted from 24.73% (2 layers) to 4.15% (5 layers). In contrast, NATR-GAT maintained a stable 40.21% at 5 layers.
  • Node Classification & Distinctiveness: NATR improved classification accuracy across the board while maintaining significantly higher Mean Average Distance (MAD) scores, proving mathematically that node representations remained distinct and informative.

Limitations and Future Work

  • Computational Complexity: The attribute encoder relies on self-attention, introducing a quadratic computational complexity relative to the total number of attributes ($O(|T|^2)$). While the authors note that the number of unique attributes is typically smaller than the number of nodes and scales reasonably well, it could still pose a bottleneck for graphs with massive feature vocabularies.
  • Future Directions: Promising future work includes optimizing the transformer architecture to scale efficiently to extremely large attribute spaces and adapting the framework to handle continuous, high-dimensional node features more natively.

Summary updated

Abstract

Message Passing Neural Networks (MPNNs) hold a key position in machine learning on graphs, but they struggle with unintended behaviors, such as over-smoothing and over-squashing, due to irregular data structures. The observation and formulation of these limitations have become foundational in constructing more informative graph representations. In this paper, we delve into the limitations of MPNNs, focusing on aspects that have previously been overlooked. Our observations reveal that even within a single layer, the information specific to an individual node can become significantly diluted. To delve into this phenomenon in depth, we present the concept of Over-dilution and formulate it with two dilution factors: intra-node dilution for attribute-level and inter-node dilution for node-level representations. We also introduce a transformer-based solution that alleviates over-dilution and complements existing node embedding methods like MPNNs. Our findings provide new insights and contribute to the development of informative representations. The implementation and supplementary materials are publicly available at https://github.com/LeeJunHyun/NATR.
BibTeX
@inproceedings{lee2025understanding,
  author = {Junhyun Lee and Veronika Thost and Bumsoo Kim and Jaewoo Kang and Tengfei Ma},
  title = {{Understanding and Tackling Over-Dilution in Graph Neural Networks}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2025},
}
Figure