Large real-world graphs mix kinds of things, such as authors, papers and venues, or users, businesses and reviews. They also keep changing as new papers and new reviews arrive. A common way to train neural networks on them is coarsening: merging similar nodes into "supernodes" so a much smaller graph can stand in for the original. Current coarseners handle only one of these two complications. One line handles many node types but must be recomputed from scratch whenever the graph changes. The other updates incrementally as the graph grows but assumes every node and edge is of the same kind. Both decide what to merge with hand-set similarity rules and a user-chosen compression ratio.
We propose to make every merge, split and reassignment decision by counting bits. The approach follows minimum description length (MDL), the principle that the best summary of data is the one that lets you write down the summary plus the leftover corrections in the fewest bits. For a typed graph, the summary groups each node type into supernodes and records how densely each pair of groups is connected under each relation. Because this code length decomposes over relation-specific blocks, the change caused by one new edge or one node move can be computed from that node's neighbors alone. That makes it a cheap, principled rule for when to reassign an old node in a streaming graph, and it also chooses the coarsening ratio itself. The bet is that this single objective fixes three known failures at once. It replaces the "error lock-in" of freeze-and-append coarsening. It removes the blindness of per-type hashing to cross-type structure. And it avoids the need to re-run a static heterogeneous coarsener at every time step.
Core Claim
An incrementally maintained, relation-typed MDL block code can serve as the operating objective of a coarsener for evolving heterogeneous graphs. Its per-node "bit savings from moving" score, computable in time proportional to the node's degree, can decide which previously placed nodes to reassign under a fixed update budget. We claim this matches the downstream accuracy of recomputing a heterogeneous coarsening from scratch at each step. We also claim it beats both freeze-and-append updating and per-type similarity hashing whenever node groups are defined by who they connect to across types rather than by their own features. Finally, it costs a fraction of recomputation per event and works on asynchronous event streams rather than only on snapshots.
Concretely, let each node type $t$ be partitioned into groups, and for each relation $r$ and each pair of compatible groups $(a,b)$ let $n^r_{ab}$ be the number of possible typed node pairs and $m^r_{ab}$ the number of observed edges. The description length we minimize is
$$ \mathcal{L} = L(\text{partition}) + \sum_{r}\sum_{(a,b)} \Big[\log_2(n^r_{ab}+1) + n^r_{ab}\, H\!\big(m^r_{ab}/n^r_{ab}\big)\Big] + L(X \mid \text{groups}), $$
where $H$ is the binary entropy in bits, the bracketed term is the cost of encoding block $(a,b)$ under relation $r$ losslessly, and $L(X\mid\text{groups})$ is the cost of node features coded around their group means. Empty blocks cost zero bits, so only nonzero blocks need to be stored. Moving a node $v$ changes only the blocks touching $v$'s old and new group, so the change $\Delta\mathcal{L}(v)$ needs only $v$'s per-relation edge counts into each group. This locality makes the objective usable on graphs with millions of nodes and on streams.
Where This Sits in Prior Work
The method's ingredients come from classical MDL summarization. VoG describes a static homogeneous graph with a fixed vocabulary of cliques, stars and chains, chosen greedily by bit savings. TIMECRUNCH adds temporal signatures but still decomposes each snapshot statically. LM-Gsum extends lossless supernode coding to labeled multi-graphs using hashing. All three are static and produce summaries for human reading rather than graphs for training. We reuse their two-part code, but move from a vocabulary of shapes to typed block densities and from one-shot search to local incremental updates.
BSC motivates and constrains the design. It shows that an MDL code over a stochastic block model (a model in which edge probabilities depend only on group memberships) can balance compression against change detection with bounded false alarms. However, it assumes a single relation, discrete snapshots, and global inference that its authors describe as costly on large graphs. Our code is a typed, relation-indexed relative of that model, maintained by local moves rather than global re-inference.
MDL-Pool shows MDL can select cluster counts inside a neural network without a free parameter, reporting 77.2% on IMDB-BINARY. It works on small static whole-graph classification, which is why we do not adopt its differentiable route for million-node streams.
Two coarseners define the gap we target. AH-UGC hashes each node type separately onto a circle and rebuilds cross-type edges afterwards. Keeping supernodes type-pure gave 57.75% versus 37.33% for type-blind UGC on IMDB, and that result constrains us: our supernodes stay type-pure. But AH-UGC groups nodes by their own features and local structure, not by their joint connection profile to other types' groups, and it is static. DIGC and ACNR update a homogeneous coarsening incrementally, keeping 98–99% of recomputation accuracy at 10–20x speed. DIGC freezes old assignments and suffers error lock-in. ACNR's reassignment is heuristic, and neither handles multiple types. Our contribution is the objective that decides reassignment, plus its extension to typed relations.
Temporal heterogeneous networks such as SE-HTGNN and THGFM are consumers, not competitors: they lack any coarsening step and are what a coarsened graph would be fed to.
Research Program
The first component is the online coarsener. Each arriving typed edge or node event updates one or two block counts in constant time and marks the endpoints as "dirty." For dirty nodes, the system computes the best move $\Delta\mathcal{L}(v)$ and keeps it in a lazy priority queue. A per-batch reassignment budget then executes the most bit-saving moves, which is our bits-based replacement for ACNR's migration rule. Group splits and merges within a type are proposed when a group's internal block code or feature residual grows. They are accepted only if total code length drops, so the number of supernodes per type is set by MDL. A constrained mode fixes a target ratio for fair comparison with ratio-based baselines. Events are processed in arrival order, so the method works on continuous-time streams; snapshots appear only where downstream evaluation needs them.
The second component is analysis. We will bound the per-event cost by degree times touched blocks, and measure how the gap between our incremental code length and a from-scratch optimized code evolves over time. This gap is our analogue of ACNR's $\epsilon$-similarity guarantee and is directly observable in bits. As a secondary, cheap output, we track the per-event code-length increase as a change statistic in the spirit of BSC. We do not claim BSC's false-alarm bounds carry over.
The third component is downstream use. We train a heterogeneous network (HeteroGCN as in AH-UGC, and EHG for the larger graphs) on the coarsened graph and lift predictions back to original nodes through group membership.
Baselines
The naive reference points are full-graph training on the uncompressed graph where memory permits, which gives the accuracy ceiling, and a random type-pure coarsening at the same ratio, which gives the floor. Any method that does not clearly separate from random type-pure grouping has learned nothing.
The strongest static competitor is AH-UGC, recomputed from scratch at each time step. It is the best reported heterogeneous coarsener and is fast: on Yelp it built its suite of coarsened graphs in 1,374 seconds against 6,904 for UGC, and on IMDB at a 30% ratio with HeteroGCN it reached 57.75% accuracy. We run the released configuration on identical splits and ratios, with its heterophily weight tuned under the same search budget we give our method's single hyperparameter, the reassignment budget. Beating it means matching its accuracy within one standard deviation on static IMDB, DBLP and ACM, exceeding it on the cross-type planted benchmarks, and costing at least an order of magnitude less cumulative update time over a stream.
The strongest dynamic competitor is ACNR from Adapting to Evolving Graphs, run in two ways: on the flattened graph, and type-isolated with one ACNR instance per node type and cross-type edges rebuilt as in AH-UGC. DIGC, also from that work, serves as the freeze-and-append reference that exposes error lock-in. The reported reference is 98–99% of static accuracy at 10–20x speed, but only on homogeneous graphs; no reported result was found on Lacuna for any incremental coarsener on heterogeneous graphs, including OGBN-MAG. Beating ACNR means higher downstream accuracy at equal update time, or equal accuracy with fewer reassignments.
Two ablations isolate the key ingredient. The first keeps our incremental machinery but scores moves by AH-UGC-style feature-and-structure similarity instead of $\Delta\mathcal{L}$, which tests whether the bits objective matters beyond the queueing scheme. The second keeps $\Delta\mathcal{L}$ but codes all relations as one, which tests whether relation typing matters. A further ablation fixes the ratio rather than letting MDL choose it.
Why not just…?
Why not just re-run AH-UGC on every snapshot? This is the most serious threat, because AH-UGC is single-pass and fast. If the graph changes slowly and groups are defined by features, recomputation may be cheap enough and just as accurate. Our case rests on two things. First, cost scales with the stream rather than the change: recomputing on OGBN-MAG's roughly 21 million edges at every event or yearly batch is wasteful when only a few thousand edges change. Second, per-type hashing cannot group authors by which venue and paper groups they connect to. The planted cross-type benchmark and the cumulative-time curves settle both points. If AH-UGC-recompute matches us on real data, we will report that the real-data benefit is purely speed.
Why not just run ACNR separately on each node type? Type-isolated ACNR inherits type purity and incremental speed for free. But ACNR's reassignment still uses within-type similarity, so it shares AH-UGC's blindness to cross-type profiles. It also has no principled signal for how many reassignments to make. It is included as a baseline, and the "similarity-scored moves" ablation tells us whether any gain comes from the objective or merely from the bookkeeping.
Why not skip coarsening and use mini-batch sampling or a heterogeneous temporal model directly? Sampling trains on the full graph without compressing it. OGB reports that GraphSAINT reaches 79.08% on ogbn-products, but that samplers like GraphSAGE show a roughly 15% train–test gap. Models like SE-HTGNN report speedups (2.7x on OGBN-MAG) but no compression. Coarsening is complementary: it shrinks what any of these models must touch. We therefore report EHG on full OGBN-MAG next to EHG on our coarsened graph, measuring memory, time and accuracy. If full-graph training fits and is cheap, the honest conclusion is that coarsening is needed only past that memory limit, and we will state it.
Proposed Experiments
The first experiment is controlled. Synthetic typed graphs with three node types are planted so that one type's groups are visible only through its connections to another type's groups, with features as pure noise. The stream then merges, splits and deletes groups over time. We measure group recovery (normalized mutual information) after each event for all methods. The decisive prediction is that DIGC degrades after merges, per-type hashing stays near chance on the hidden type, and our method tracks the planted structure.
The second experiment is static validation on DBLP, ACM, IMDB and Yelp at 10–50% ratios, using HeteroGCN node classification and coarsening wall time. The target is matching AH-UGC's 57.75% IMDB figure and its Yelp timing class.
The third experiment is the main dynamic test. DBLP, OGBN-MAG and Aminer are replayed in timestamp order, where a node's year defines its arrival. We report downstream accuracy at each checkpoint, cumulative update time, peak memory, and the bit gap to a from-scratch MDL optimum. A tgbn-genre stream (users and genres, a two-type bipartite case from TGB) tests event-order processing at scale. Because TGB found a moving-average heuristic beating TGN on node affinity (NDCG@10 0.559 vs 0.315 on tgbn-reddit), we include that heuristic as a reference so that coarsening gains are not judged against a weak neural floor.
The decisive check combines the three experiments. If, on real heterogeneous streams, the relation-typed $\Delta\mathcal{L}$ rule is not better than similarity-scored moves at equal budget, the core claim fails. We would then report the method as an accounting device for bits rather than a better coarsener.
References
- Summarizing and understanding large graphs
- On Summarizing Large-Scale Dynamic Graphs
- Summarizing Labeled Multi-graphs
- Balancing Summarization and Change Detection in Graph Streams
- MDL-Pool: Adaptive Multilevel Graph Pooling Based on Minimum Description Length
- AH-UGC: Adaptive and Heterogeneous-Universal Graph Coarsening
- Adapting to Evolving Graphs: A Scalable Framework for Dynamic Coarsening
- Simple and Efficient Heterogeneous Temporal Graph Neural Network
- THGFM: Dual-Branch Temporal Heterogeneous Graph Fusion Model
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- Temporal Graph Benchmark for Machine Learning on Temporal Graphs