Streaming Role Coarsening for Heterophilous Dynamic Graphs

Large graphs are often shrunk before learning. Many nodes are merged into a few "super-nodes", and a neural network runs on the smaller graph. The methods that do this assume that connected nodes are similar, a property called homophily, and they assume the graph does not change. Many graphs of practical interest break both assumptions. In fraud, trading, and traffic graphs, fraudsters link to victims and sensors link to sensors in the opposite state, a property called heterophily. These graphs also arrive as a continuous stream of timestamped edges, not as a sequence of snapshots. Two recent lines of work each fix one assumption. UGC: Universal Graph Coarsening hashes a mix of node features and adjacency rows so it can coarsen heterophilous graphs, but it is static. Adapting to Evolving Graphs: A Scalable Framework for Dynamic Coarsening updates a coarsening incrementally, but its objective assumes smoothness across edges, it works only on discrete snapshots, and its authors name continuous-time streams as unsupported.

We propose to group nodes by their role, meaning what their recent neighbors look like, rather than by who they are connected to. Each node keeps a small time-decayed summary of its neighbors' features, and its super-node is simply the hash bucket of that summary. When an edge event arrives, only its two endpoints' summaries change, so only those two nodes can move between super-nodes. The coarse graph can therefore be kept exactly current at constant cost per event. Under heterophily, nodes of the same class tend to share neighbor distributions even when they are not adjacent; this is the observation behind MixHop's 2-hop "return" to the original class. For that reason, role buckets should stay class-pure exactly where adjacency-based clusters mix classes.

Core Claim

For streaming graphs whose heterophily pattern drifts over time, a coarsening defined as a stateless function of each node's current role signature has three properties. It can be maintained per event rather than per snapshot. It avoids the "error lock-in" that forces Adapting to Evolving Graphs to add a separate reassignment procedure. Its quality can be certified by a bound on neighbor-aggregation error instead of Dirichlet energy. Dirichlet energy is the sum of squared feature differences across edges, and it rewards the smoothing that heterophily research shows to be harmful (The Heterophilic Graph Learning Handbook).

The signature of node $v$ at time $t$ is

$$s_v(t) = \Big[\, x_v \;,\; \frac{\sum_{(v,u,\tau),\,\tau\le t} e^{-\lambda (t-\tau)}\, x_u}{\sum_{(v,u,\tau),\,\tau\le t} e^{-\lambda (t-\tau)}} \,\Big].$$

Here $x_v$ is the node's own feature vector, the sum runs over edge events touching $v$ up to time $t$, and $\lambda$ is a forgetting rate. Keeping the ego part and the neighbor part in separate halves is deliberate. Complete the Missing Half shows that under heterophily the difference between a node and its neighbors carries the signal. Mixing the two halves before hashing would erase that difference.

A locality-sensitive hash puts nodes with nearby signatures in the same bucket with high probability; we use several independent tables. It gives a certificate of the following form. With high probability over the tables, every node $v$ in super-node $S$ satisfies

$$\big\| m_v(t) - \bar m_S(t) \big\| \le c\, r .$$

In this bound, $m_v$ is the neighbor half of $s_v$, $\bar m_S$ is its bucket average, $r$ is the hash radius, and $c$ is the hash's approximation factor. So the coarse graph's lifted neighbor aggregates are accurate to within $cr$ whether or not the graph is homophilous. The form of the bound comes directly from standard LSH collision guarantees. The work is to make it tight enough to matter and to relate it to downstream error.

Research Program

The first component is the streaming coarsener. Each edge event $(u,v,t)$ updates the decayed numerator and denominator of $u$ and $v$ in $O(d)$ time, where $d$ is the feature dimension. The event then rehashes both nodes. If a bucket changes, the coarsener moves the node and adjusts the counts on the edges between super-nodes. Decay is applied lazily, from a last-touched timestamp, so idle nodes cost nothing. Super-edges store two quantities: a decayed count, and a compatibility summary, which is the average product of endpoint ego features. The coarse graph therefore records which roles talk to which. It does not treat every super-edge as a "be similar" constraint.

The second component is the learner. It borrows the two-branch design of CoRe-GNN, which runs fine-grained message passing inside clusters in parallel with message passing over super-nodes, then lifts the result back. CoRe-GNN's authors state that it assumes a fixed propagation matrix and does not handle dynamic graphs. We keep its lift-back idea and replace the rest in two ways. The coarse branch runs over the streaming role graph, with separate ego and neighbor channels in the style of adaptive channel mixing from Exploring Heterophily in Graph-level Tasks. The fine branch is only a node's own features plus its decayed signature, so inference costs one lookup instead of a neighborhood expansion.

The third component is analysis. We will turn the aggregation bound into a bound on prediction change for a Lipschitz coarse-branch model; a Lipschitz model is one whose output changes by at most a constant times the change in its input. We will also measure empirically how bucket purity tracks class purity as the homophily level moves from high to low. The "mid-homophily pitfall" catalogued in the Handbook predicts that purity is worst at intermediate homophily. We want to know whether role signatures escape that pitfall or inherit it.

Baselines

The naive reference points are a feature-only MLP (a multi-layer perceptron that ignores the graph) and, on node-affinity tasks, the Moving Average heuristic. The Handbook reports that MLPs beat standard GNNs on malignant-heterophily datasets such as Texas, Cornell, Film, and roman-empire. Temporal Graph Benchmark reports Moving Average at NDCG@10 of 0.559 on tgbn-reddit, against 0.315 for TGN (a temporal graph network that keeps a learned memory per node). NDCG@10 is a ranking score over the top ten predictions. Any method that does not beat these points has not justified using the graph, and they will be run on identical splits and features.

The strongest static-coarsening competitor is UGC recomputed from scratch at intervals. UGC runs in linear time, handles heterophily through its mixing factor, and is reported at 86.3% on Cora at a 50% coarsening ratio versus 79.9% for heavy-edge matching. We will run it with the same hash family and the same downstream model. Its recompute interval will be tuned so that its total wall-clock time equals our streaming cost. The fair comparison is therefore accuracy over time at equal compute, not per-event latency. Beating it means higher time-averaged accuracy or NDCG on the heterophilous streams at that matched budget.

The strongest dynamic-coarsening competitor is ACNR from Adapting to Evolving Graphs. It retains 98 to 99% of full static recomputation accuracy and runs 10 to 20 times faster on citation graphs. It will be run on snapshots formed from our streams at the granularity its authors use. We expect it to match us on homophilous controls and to fall behind on heterophilous streams. If it does not fall behind there, the heterophily argument fails.

The strongest fine-grained temporal heterophily model is THeGCN. It reports 55.82% accuracy on PEMSLA against 48.27% for the best temporal baseline, APAN. On PEMS we aim to come within a few points of THeGCN at a large reduction in inference cost. We do not claim we will surpass it. Surpassing it would be a bonus, and landing far below it would mean coarsening discards too much.

For scale, the reference is the OGB report of GraphSAINT at 79.08% test accuracy on ogbn-products (Open Graph Benchmark), together with CoRe-GNN's reported gain of over 7 points against Cluster-GCN there.

Three ablations isolate the key ingredient. The first hashes ego features only, dropping the neighbor half. The second removes the decay, so all history is kept equally. The third replaces role hashing with a smoothness-based assignment in the style of Featured Graph Coarsening with Similarity Guarantees while keeping everything else fixed. All tuning budgets are equal across methods, measured in trials per method.

Why not just…?

Why not just rerun UGC periodically, since it is already linear time? This is the most serious threat, and we treat it as the main comparison rather than argue it away. Recomputation cost grows with the total graph size, while our cost grows with the number of new events. On streams such as tgbn-token (over 72 million edges) or tgbl-comment (over 30 million timestamps), periodic recomputation must either lag or spend far more compute. The incremental paper also reports that recomputation overfits transient snapshot noise, whereas incremental updates act as temporal regularization. The matched-compute experiment settles the question. If periodic UGC ties us at equal wall-clock, the streaming machinery is not worth it, and we will report the role signature as the contribution on its own.

Why not just feed UGC-style features into ACNR? That would keep ACNR's optimization-based reassignment and its smoothness objective. ACNR's own authors add reassignment precisely because frozen assignments lock in errors. Under drifting heterophily, the objective itself pulls adjacent dissimilar nodes together. The smoothness-assignment ablation tests this directly with everything else held fixed.

Why not just drop the graph and use an MLP, or a moving average? On malignant heterophily, the MLP may genuinely win, and the Handbook says so. We include those datasets so that we can report this honestly. On benign heterophily (Chameleon, Squirrel), on motif-driven tasks, and on traffic streams where THeGCN beats temporal baselines by over 7 points, structure carries signal an MLP cannot see. Moving Average is strong on tgbn-reddit but, per TGB, weak under high surprise, meaning many test edges never seen in training. We will stratify results by TGB's surprise index.

Why not just sample neighborhoods or partition, as THeGCN or Cluster-GCN do? Sampling keeps the per-query cost of computing weights over historical windows. Partitioning cuts inter-cluster edges, and CoRe-GNN shows the cost of that cut: about 33% versus about 44% on the Paris road network. Our coarse branch keeps long-range role-to-role context at constant cost per event.

Proposed Experiments

The heterophilous dynamic setting uses PEMSBA, PEMSLA, and PEMSSD for node classification, and tgbn-reddit, tgbn-trade, tgbn-genre, and tgbn-token for node-affinity ranking under TGB's streaming protocol. Lacuna has no reported results for trade, genre, or token, so we will run every baseline ourselves on those.

Static heterophily sanity checks use Squirrel, Chameleon, roman-empire, Texas, Cornell, and Film, where we compare against UGC at matched coarsening ratios. Lacuna reports no UGC accuracy on these, only a 9x speed advantage on Squirrel. Homophilous controls are ogbn-arxiv streamed by publication year and D-PUBMED, where ACNR should be competitive.

A controlled synthetic stream plants role-structured graphs whose compatibility matrix, the probability table of which roles connect to which, rotates partway through the stream. Its purpose is to measure how quickly bucket purity recovers after drift, as a function of $\lambda$.

Scale tests stream ogbn-products and ogbn-papers100M edges in insertion order, measuring throughput and memory only. Lacuna has no reported result for papers100M.

Metrics are accuracy and NDCG@10 averaged over time, events processed per second, peak memory, and bucket class-purity against edge homophily.

The decisive checks are three. First, at matched compute, the method beats periodically recomputed UGC on the heterophilous streams. Second, removing the neighbor half of the signature costs substantially more on heterophilous data than on the homophilous controls. Third, after the synthetic drift, purity recovers within a number of events proportional to $1/\lambda$, which is the time scale over which the decayed neighbor average forgets pre-drift edges. If the first check fails, we report the signature result without the streaming claim. If the second fails, the role hypothesis is wrong.