🤖 machine learning

DeltaGNN: Graph Neural Network with Information Flow Control

The paper introduces DeltaGNN, a scalable and generalizable Graph Neural Network architecture that utilizes a novel information flow control mechanism with linear computational overhead to effectively overcome over-smoothing and over-squashing challenges, thereby enabling the detection of both short-range and long-range node interactions across diverse graph structures.

Original authors: Kevin Mancini, Islem Rekik

Published 2026-08-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kevin Mancini, Islem Rekik

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the digital world, data often arrives not as neat rows in a spreadsheet, but as complex webs of connections. Think of a social network where people are linked by friendships, or a medical scan where different parts of an organ are connected by tissue. To make sense of these webs, scientists use a type of artificial intelligence called a Graph Neural Network. These models work by having each point in the network look at its immediate neighbors, gather information from them, and update its own understanding. By repeating this process, the model builds a picture of the whole system, allowing it to solve problems like identifying a disease in a tissue sample or predicting how a chemical molecule will behave.

However, these networks face a fundamental problem when they try to look too far ahead. If the model looks at too many neighbors in a row, the distinct details of each point get washed out, and everything starts to look the same. This is known as over-smoothing. At the same time, if the network has a narrow bottleneck—a single path connecting two large groups—the information trying to pass through gets crushed and lost, a problem called over-squashing. These issues prevent the AI from understanding long-distance relationships within the data, which are often the most critical for making accurate predictions. For years, researchers have tried to fix this by building more complex models, but these solutions are often too slow to run on large, real-world datasets.

A team of researchers at Imperial College London has now proposed a different way forward. Instead of making the model more complex, they introduced a mechanism to control how information flows through the network, effectively cleaning up the connections as the model learns. They call their new system DeltaGNN. The core of their approach is a simple but powerful idea: they measure how fast and how much a point in the network changes its understanding as it gathers information from its neighbors. By tracking these changes, the system can identify which connections are helpful and which are causing confusion or bottlenecks.

The researchers developed a scoring system to evaluate every connection in the network. If a connection causes a point to change its understanding too drastically or too slowly, the system flags it as problematic. Connections that link points with very different characteristics, or those that act as narrow choke points, receive low scores. The model then uses these scores to selectively remove the worst connections while keeping the rest of the network intact. This process happens step-by-step, layer by layer, allowing the network to gradually reshape itself into a more efficient structure. It is like a gardener pruning a bush: by cutting away the tangled, unhelpful branches, the plant can grow stronger and healthier without needing to be replanted.

What makes this approach unique is that it does not require expensive pre-calculations or massive amounts of extra computing power. The scoring happens naturally as the model learns, adding almost no time to the process. The researchers tested their system on ten different real-world datasets, ranging from scientific citation networks to medical images of liver tumors. These datasets varied widely in size, density, and how similar the connected points were to one another. In every case, DeltaGNN performed better than existing state-of-the-art methods, often by a significant margin. It was particularly effective on large, dense graphs where other models failed completely, running out of memory or taking too long to finish.

The study also revealed that the new method works well regardless of the specific shape of the data. Whether the network was made of highly similar points or very different ones, the system adapted and found the best connections. The researchers found that by removing the problematic links, the model could learn both short-range details and long-range patterns simultaneously. This dual ability allowed it to distinguish between different classes of data with greater accuracy than previous models. For instance, in the medical imaging tests, the system successfully identified different types of liver tumors by recognizing subtle patterns that other models missed.

The team's work suggests that the key to solving these long-standing problems in artificial intelligence is not necessarily to build bigger, more complex brains, but to manage the flow of information more carefully. By introducing a way to measure and control how information travels through a network, they have created a tool that is both powerful and efficient. This approach offers a scalable solution for analyzing massive datasets, from mapping the human brain to understanding global social trends. The researchers have made their code available to the public, inviting others to test and build upon this new method. Their findings indicate that with the right way to filter connections, artificial intelligence can finally see the long-range relationships that have been hidden in plain sight.

Technical Summary: DeltaGNN: Graph Neural Network with Information Flow Control

Problem Statement
Graph Neural Networks (GNNs) are effective for processing graph-structured data but face significant limitations in semi-supervised node classification, specifically regarding over-smoothing and over-squashing.

Over-smoothing: As the number of layers increases, node representations become indistinguishable, particularly in graphs with heterophilic edges (edges connecting nodes of different classes).
Over-squashing: Graph bottlenecks cause the exponential growth of a node's receptive field, forcing substantial information into fixed-sized feature vectors, thereby inhibiting the capture of long-range interactions (LRIs).

Existing solutions, such as graph transformers (global attention) and topological rewiring (curvature-based), suffer from high computational complexity (often quadratic or requiring expensive pre-processing) or fail to generalize across diverse graph topologies, densities, and homophily ratios. There is a need for a scalable, generalizable method that addresses both phenomena with linear computational overhead.

Methodology
The authors propose DeltaGNN, a novel architecture built upon two core concepts: Information Flow Score (IFS) and Information Flow Control (IFC).

Information Flow Score (IFS):
- The authors define Graph Information Flow (GIF) as the rate of node embedding aggregation during message passing.
- They introduce First Delta Embeddings ( $\Delta^t_u$ ), representing the "velocity" of embedding updates, and Second Delta Embeddings ( $( \Delta^2 )^t_u$ ), representing the "acceleration" (rate of change of velocity).
- The IFS ( $S_u$ ) is a connectivity measure calculated as:
  $S_u = V_t[\Delta^2_u] + \frac{1}{\Delta_u + 1}$
  where $V_t[\Delta^2_u]$ is the time variance of the second delta embeddings.
- Theoretical Basis:
  - High $\Delta$ values correlate with low homophily (heterophilic interactions).
  - Low variance in $\Delta^2$ correlates with proximity to graph bottlenecks (over-squashing).
- The score is designed to be low for nodes near bottlenecks or with low homophily, identifying regions prone to over-smoothing and over-squashing.
Information Flow Control (IFC):
- Unlike static rewiring, IFC is a sequential, in-training edge-filtering mechanism.
- It integrates with standard GNN layers, iteratively removing edges with low IFS values.
- The process uses a parameter $\theta$ optimized via hill ascent to maximize the mean node score, ensuring sparsity is preserved while removing detrimental edges.
- This mechanism operates with linear computational overhead ( $O(|V|)$ ) and memory complexity.
DeltaGNN Architecture:
- Sequential Transformation Stage:
  - Homophilic Path: Processes the graph through a standard GNN with IFC. This removes heterophilic edges and bottlenecks, creating a highly homophilic subgraph ( $G_{ho}$ ) to capture short-range dependencies.
  - Heterophilic Path: Performs heterophilic graph condensation. Nodes with the highest IFS (reliable representations) are selected to form a smaller, fully connected, highly heterophilic subgraph ( $G_{he}$ ). A separate GNN aggregates long-range dependencies on this condensed graph.
- Prediction Stage: Concatenates the outputs of both the homophilic and heterophilic paths, followed by a linear readout layer to perform classification.

Key Contributions

Novel Connectivity Measure: Introduction of the Information Flow Score (IFS), which identifies graph bottlenecks and heterophilic interactions based on the dynamics of embedding updates, supported by theoretical lemmas.
Information Flow Control (IFC): A mechanism for sequential edge filtering that mitigates over-smoothing and over-squashing with linear time and memory complexity, integrable into any GNN architecture.
DeltaGNN Architecture: A scalable and generalizable framework that decouples homophilic and heterophilic interactions to effectively detect both short-range and long-range interactions. It is claimed to be the first architecture to achieve this with linear overhead and consistent performance across varying graph properties.

Experimental Results
The model was benchmarked on 10 real-world datasets (including Cora, CiteSeer, PubMed, Cornell, Texas, Wisconsin, and MedMNIST) with varying sizes, topologies, densities, and homophily ratios.

Accuracy: DeltaGNN outperformed state-of-the-art methods (including GCN, GIN, GAT, Graph Transformers, and various rewiring algorithms) on 4 out of 6 homophily-varied datasets, with an average accuracy increase of 1.23%. It showed particular effectiveness on low-homophily datasets (e.g., Texas, Wisconsin).
Scalability:
- Time: DeltaGNN achieved the lowest epoch time in 3 out of 5 datasets tested, reducing average epoch time by 30.61% compared to the worst-performing model. It successfully processed dense graphs where other methods (like GAT and graph transformers) failed due to Out-of-Memory (OOM) or Out-of-Time (OOT) errors.
- Memory: While using approximately twice the memory of standard GCNs due to dual-path aggregation, it remained significantly more efficient than GAT and graph transformers, which failed on dense datasets entirely.
Connectivity Measures: The IFS demonstrated superior performance in increasing graph homophily during edge filtering (8.65% increase) compared to topological measures (e.g., Ollivier-Ricci curvature, Betweenness Centrality), which often failed to scale or generalize.

Significance and Claims
The paper claims that DeltaGNN addresses the fundamental trade-off between capturing long-range interactions and maintaining computational efficiency. By leveraging the dynamics of message passing (velocity and acceleration of embeddings) rather than static topological properties, the proposed method offers a generalizable solution that works across diverse graph structures without the quadratic complexity of attention mechanisms or the expensive pre-processing of curvature-based rewiring. The authors position DeltaGNN as a scalable framework that expands the applicability of GNNs in semi-supervised node classification tasks, particularly for large and complex graphs where long-range dependencies are crucial.

Technical Summary: DeltaGNN: Graph Neural Network with Information Flow Control

More like this