Graph Rewiring: Modifying Graph Topology to Improve Information Flow

Graph rewiring is a preprocessing technique that modifies the graph's edge structure to improve information flow during GNN message passing, primarily by adding shortcut edges that bypass bottleneck structures causing over-squashing. The rewired graph determines which nodes exchange messages during GNN computation. The original graph structure can be preserved as edge features or structural encodings. This separation of “computation graph” from “data graph” lets the GNN optimize information flow without losing structural semantics.

Why it matters for enterprise data

Enterprise relational graphs frequently contain topological bottlenecks:

• Rare merchants: A merchant visited by only 2 customers from different communities. All information between those communities flows through one merchant node.
• Single warehouses: A supply chain where one warehouse connects all suppliers to all retailers. All supply-demand signals flow through that bottleneck.
• Bridge accounts: In fraud detection, a legitimate account that transacts with both a fraud ring and normal accounts. Fraud signals must pass through this narrow bridge.

Rewiring adds alternative paths for these signals, letting the GNN detect patterns that would be squashed in the original topology.

Three rewiring approaches

Spectral rewiring

Add edges that maximize the spectral gap (second-smallest eigenvalue of the graph Laplacian). A larger spectral gap means better connectivity and faster information propagation. The spectral gap is the algebraic measure of how well-connected the graph is.

Curvature-based rewiring (SDRF)

Compute the Ricci curvature of each edge. Edges with negative curvature are bottlenecks. Add shortcut edges near the most negative-curvature edges to provide alternative paths. This directly targets the topological source of over-squashing.

Random shortcuts

Add random edges between nodes that are far apart in the graph. Simple but effective: even random shortcuts reduce effective diameter and mitigate over-squashing. The GNN learns to use or ignore these edges as needed.

import torch
from torch_geometric.utils import to_dense_adj, dense_to_sparse

def add_random_shortcuts(edge_index, num_nodes, num_shortcuts=1000):
    """Add random long-range edges to reduce graph diameter."""
    # Sample random node pairs
    src = torch.randint(0, num_nodes, (num_shortcuts,))
    dst = torch.randint(0, num_nodes, (num_shortcuts,))
    # Remove self-loops
    mask = src != dst
    new_edges = torch.stack([src[mask], dst[mask]])
    # Add to existing edges
    return torch.cat([edge_index, new_edges], dim=1)

# Usage
data.edge_index_rewired = add_random_shortcuts(
    data.edge_index, data.num_nodes, num_shortcuts=data.num_edges // 10
)

# Train GNN on rewired graph
# Use original edge_index for edge features/structure
# Use edge_index_rewired for message passing
out = model(data.x, data.edge_index_rewired)

Concrete example: cross-community fraud detection

A payment network has two customer communities connected by a single merchant:

• Community A: 10,000 accounts, dense internal transactions
• Community B: 8,000 accounts, dense internal transactions
• Bridge: Merchant M, connected to 5 accounts in A and 3 accounts in B

A fraud ring spans both communities. Without rewiring, the fraud signal from Community A must flow through the 8 edges to Merchant M to reach Community B. The signal is squashed at this bottleneck.

After adding 50 random shortcut edges between Communities A and B, the fraud signal has multiple paths to flow. The GNN can now detect the cross-community ring pattern. Fraud detection AUROC improves from 71.2 to 76.8 on this graph.

Limitations and what comes next

1. Memory and computation: Each added edge increases memory and computation for message passing. Adding too many edges (dense rewiring) approaches the cost of a full graph transformer without the benefits of learned attention.
2. Which edges to add: Random shortcuts are simple but imprecise. Spectral and curvature-based methods are targeted but expensive to compute. Finding the right balance is task-dependent.
3. Semantic mismatch: Rewired edges have no semantic meaning. The GNN must learn to distinguish real edges (with semantic content) from shortcut edges (for computation only). Using edge type features helps.