Large real graphs such as co-purchase networks contain dense bipartite blocks: hundreds of items all bought by the same hundreds of customers. Visualization researchers know these blocks as the source of the "hairball effect," the unreadable tangle of crossing lines in a drawing of a big network. Their fix is edge bundling. A complete block of $a \times b$ edges is drawn as $a + b$ strands meeting at a single shared junction. Graph neural networks (GNNs), models that compute each node's representation by repeatedly averaging its neighbors' representations, suffer from the same blocks in two ways. The blocks inflate memory, because every edge carries a message. They also speed up over-smoothing, the collapse of all node representations toward a common value as averaging is repeated. The standard scalability fix, graph coarsening, borrows the other hairball remedy, merging nodes into super-nodes. This destroys node identity and pollutes labels whenever a super-node mixes classes.
We propose the opposite borrowing: compress edges into junctions and keep every node. We then give each junction a learned gate, so the model can switch off a whole bundle of homogenizing messages at the cost of one scalar. With gates open, the junction graph computes exactly what the original GNN computes, using fewer messages. With gates learned, it becomes a structured, supervised rewiring that acts on bundles rather than individual edges. The two-sentence version is this: replace dense bipartite blocks of edges with shared junction nodes, which shrinks the graph without merging any nodes. Then learn one gate per junction, which lets the network block whole floods of cross-community averaging that cause over-smoothing.
Core Claim
Two claims are testable. The first is a compression claim. On graphs with dense neighborhood overlap, replacing (near-)bicliques with junctions reduces message-passing memory substantially, and with all gates fixed at 1 it changes the model's outputs not at all. The second is an over-smoothing claim. Learned junction gates slow the decay of representation diversity with depth and improve accuracy on heterophilic graphs, where neighbors tend to have different labels. They should do better than per-edge pruning at initialization, node coarsening, and per-edge attention, compared at equal memory.
Concretely, let a mined biclique pair a source set $S$ with a target set $T$, with a junction node $j$ standing in for all $|S||T|$ edges. The message $j$ delivers to every $t \in T$ is
$$m_j = g_j \cdot \sum_{u \in S} \frac{h_u}{\sqrt{d_u}}, \qquad g_j = \sigma\big(w^\top [\mu_S, \mu_T, |\mu_S - \mu_T|]\big).$$
Here $h_u$ is node $u$'s current representation, $d_u$ its original degree, $\mu_S$ and $\mu_T$ the mean representations of the two sides, $w$ a learned vector shared across junctions, and $\sigma$ the logistic function. Node $t$ divides the received message by $\sqrt{d_t}$. With $g_j = 1$ this reproduces symmetric-normalized graph convolution on those edges exactly. Edges not covered by any junction stay as ordinary edges. The gate can only see summaries of the two sides, which is what makes it cheap. It is also what makes it a bundle-level decision: it suppresses a whole corridor of averaging between two communities. This is the learned analogue of the topology-constrained bundling in TGI-EB, which refuses to merge edges across functionally distinct communities because such "illegal bundles" distort meaning.
Relation to Prior Work
Several papers motivate the proposal by exposing the gap. Scaling Up Graph Neural Networks Via Graph Coarsening trains on a graph of super-nodes and transfers the weights back. It reports memory savings and even accuracy gains, for example 76.0% versus 72.6% on DBLP. The same paper names "mixed super-nodes" as its failure mode and frames coarsening as a low-pass filter. That framing is exactly the operation the over-smoothing literature warns about (Complete the Missing Half; Nonlocal Message Passing). We sidestep the tension by never averaging node features together. Junctions merge edges, every node keeps its own representation, and any compression loss sits in an explicit, inspectable gate.
Other papers constrain the design. Spectral Graph Pruning Against Over-Squashing and Over-Smoothing shows that deleting the right edges can slow representation collapse and help heterophilic graphs (Roman-Empire GCN from about 70% to about 78%). This tells us that structure modification is a real lever. PROXYDELETE, however, works per edge, without supervision, at initialization, and by deletion. Its own limitations include severing multi-hop paths and a memory footprint tied to the full edge set. We act per bundle, with supervision, by reweighting, and we shrink the edge set as a side effect. CFGNN also routes messages through intermediate hub nodes. Its hubs come from shortest-path hub labeling, ignore features, and risk squashing conflicting classes into one transit vector. Our junctions are virtual, numerous, aligned with dense overlap rather than shortest paths, and gated by feature summaries.
On the hairball side, On Strict (Outer-)Confluent Graphs formalizes drawings in which adjacency is carried by smooth paths through shared junctions. Angelini et al. show that optimal clique-to-path transformations are hard. We take only the representational idea from these papers and accept a greedy, approximate mining step, since exact optimality is out of reach. We should also be candid about a limit of the file: biclique-based compression of graphs exists in the broader graph-compression literature, but nothing in the file applies it to GNNs. Our claim of novelty rests on the gated junction as an over-smoothing control and on the head-to-head with node coarsening, not on compression alone.
Research Program
The first component is a linear-time junction miner. Nodes are hashed by min-hash signatures of their neighbor sets, candidate groups with high neighborhood overlap are collected, and each group is greedily grown into a biclique $(S, T)$. A biclique is accepted when replacing it saves at least a set number of messages. For near-bicliques, the few missing edges are recorded as signed correction edges, so exactness at $g_j = 1$ is preserved. The miner runs once, streams over adjacency lists, and must finish within the same order of time as one training epoch on ogbn-products. Otherwise its preprocessing cost counts against it, the same objection the file raises against hub labeling and spectral coarsening.
The second component is the gated junction layer and its integration with mini-batch sampling. A sampled target node pulls in its junctions rather than its raw neighbors. When $S$ is large, a junction's source side is subsampled with an unbiased rescaling.
The third component is analysis. We will prove the exactness statement for open gates. We will also characterize the gated operator as a structured reweighting of the normalized adjacency, so its effect on smoothing can be read through the same spectral-gap and energy lens that Spectral Graph Pruning uses.
As a secondary product, the learned gates define a bundled drawing of the graph in which closed junctions mark corridors the model refused to average across. This lets us check against labels whether the network learned the "no illegal bundles" rule that visualization designers impose by hand.
Baselines
The naive reference point is a standard GCN and GraphSAGE trained on the raw graph with neighbor sampling. On ogbn-products, Open Graph Benchmark reports 78.50% test accuracy for GraphSAGE and 79.08% for GraphSAINT. GraphSAINT is the strongest sampling competitor named in the file. We will rerun both with the official splits under our own tuning budget, so all methods are compared on reproduced rather than quoted numbers.
The strongest structural competitor on heterophilic graphs is PROXYDELETE from Spectral Graph Pruning, which reports about 78% on Roman-Empire against about 70% for plain GCN. We will run it with the same backbone GCN, the same number of layers, and an edge-modification budget chosen so that its edge count matches ours. Beating it means higher Roman-Empire accuracy at equal or lower memory.
The strongest scalability competitor is variation-neighborhood coarsening from Scaling Up Graph Neural Networks Via Graph Coarsening. It reports 76.0% on DBLP at $c = 0.1$ and 70–80% memory reduction on Coauthor Physics at $c = 0.3$. We will compare at matched peak GPU memory, sweeping its coarsening ratio so that one curve of accuracy against memory covers both methods. Winning means dominating that curve, especially on heterophilic data where mixed super-nodes should hurt it.
For depth, the reference is Nonlocal SAN from Nonlocal Message Passing, which reports about 87% on Cora at 256 layers against about 30% for Post-LN. We will run it on the same graphs where it fits in memory and report where it runs out of memory.
Three ablations isolate the key ingredient. The first fixes all gates at 1 (pure compression), which must match the raw-graph baseline within noise. The second uses gates over random edge groups of the same sizes as the mined bicliques, which tests whether the biclique structure matters. The third is a GAT-style per-edge attention model given the same memory, which tests whether bundle-level gating beats finer-grained gating once cost is equalized. All methods get the same hyperparameter search budget, the same seeds, and the same hardware.
Why not just…?
Why not just sample neighbors, as GraphSAGE and GraphSAINT do? Sampling controls memory but does nothing about which messages homogenize representations. On ogbn-products GraphSAGE shows a train–test gap of 94.09% versus 78.50% (Open Graph Benchmark). Junctions are orthogonal to sampling, so the right test is sampling with and without junctions under equal memory. If junctions add nothing on top of GraphSAINT, the scalability half of the claim fails on that graph.
Why not just coarsen the graph? Coarsening is the closest scalability competitor and does work on homophilic citation graphs. It does so by averaging nodes, and the coarsening paper itself names mixed super-nodes as the failure mode. The matched-memory accuracy curves on Roman-Empire, Amazon-Ratings, and Squirrel against DBLP and Coauthor Physics will show whether keeping node identity matters. We predict a gap on the heterophilic graphs and parity on the homophilic ones. Parity everywhere would mean the edge-versus-node distinction is not worth the added machinery.
Why not just prune edges with PROXYDELETE or a weight threshold? Thresholding is ruled out by GLANB, which shows that weight cuts delete weak bridges that hold the network together. PROXYDELETE is a genuine threat on mid-sized heterophilic graphs, because it already removes cross-class edges. Its decisions are unsupervised and made at initialization, and they leave memory tied to the full edge set. The decisive comparison is Roman-Empire and Squirrel at matched edge budgets. A further check is whether PROXYDELETE combined with junctions beats either one alone, which would suggest the two levers are complementary rather than redundant.
Why not just use per-edge attention or Nonlocal SAN's energy gating? Per-edge attention can in principle learn anything a bundle gate can, but it pays per-edge memory. That is exactly the cost we are trying to remove on ogbn-products. Nonlocal SAN gates with a single global energy scalar computed over the full graph, a bottleneck the file notes for graphs beyond one GPU. The equal-memory GAT ablation settles the first question. Running Nonlocal SAN until it runs out of memory, then adding its global gate on top of junctions, settles the second.
Proposed Experiments and Decisive Checks
The first check is a go/no-go on compression. Before any training, we mine junctions on ogbn-products, ogbn-arxiv, Squirrel, Amazon-Ratings, Roman-Empire, DBLP, and Coauthor Physics, and report the fraction of messages eliminated and the miner's wall-clock time. The file contains no compression figures, so this is unknown and must be measured. If co-purchase graphs compress little, the scalability claim is dead and the work reduces to a gating study. Long Range Graph Benchmark peptides, which are sparse chains, serve as a negative control: compression there should be near zero, and the method should neither help nor hurt.
The second check is exactness. With gates fixed at 1, predictions on every dataset must match the raw-graph GCN up to floating-point error.
The third check is over-smoothing. We sweep depth from 2 to 64 layers on Roman-Empire, Squirrel, Amazon-Ratings, and Cora. Because Are we measuring oversmoothing in graph neural networks correctly? questions the fidelity of single similarity and energy metrics, we report Dirichlet energy, mean pairwise cosine similarity, and accuracy together. The claim holds only if gated junctions keep energy and accuracy higher with depth than the open-gate ablation and the random-bundle ablation.
The fourth check is mechanism. Using held-out labels, we measure whether closed gates concentrate on junctions whose two sides have different majority classes. This is the learned counterpart of the topology-constrained bundling rule in TGI-EB, and the resulting gated bundled drawings will be shown as qualitative evidence.
The fifth check is scale. We train on ogbn-products with GraphSAINT-style sampling with and without junctions, against the reported 79.08%. We then attempt ogbn-papers100M, reporting peak memory, epoch time, and accuracy, and noting which baselines cannot run at all.
The proposal succeeds if three things hold together: open gates are exact, there is a clear memory reduction on dense graphs, and learned gates beat PROXYDELETE and coarsening on heterophilic graphs at matched memory. It fails cleanly if compression is negligible on real graphs or if equal-memory per-edge attention matches the gated junctions.
References
- TGI-EB: A New Framework for Edge Bundling Integrating Topology, Geometry and Importance
- Scaling Up Graph Neural Networks Via Graph Coarsening
- Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks
- Solving Oversmoothing in GNNs via Nonlocal Message Passing: Algebraic Smoothing and Depth Scalability
- Spectral Graph Pruning Against Over-Squashing and Over-Smoothing
- Bridging Indexing Structure and Graph Learning: Expressive and Scalable Graph Neural Network via Core-Fringe
- On Strict (Outer-)Confluent Graphs
- Turning Cliques into Paths to Achieve Planarity
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- Extracting the Globally and Locally Adaptive Backbone of Complex Networks
- Are we measuring oversmoothing in graph neural networks correctly?