Catching Coarsening Mistakes with Random Walks

Many graph models summarize a large graph by grouping nodes into "super-nodes", then grouping those again, building a hierarchy of coarser and coarser views. The current best way to give a graph transformer this multi-scale view, Hierarchical Distance Structural Encoding (HDSE), stops improving after a single coarsening level. Its authors suspect the reason is that off-the-shelf partitioning algorithms make bad groupings, and once made, those groupings are frozen into every level built on top of them. This is the classic failure of hierarchical systems: a mistake made early becomes the fixed foundation for everything after it.

This note proposes a cheap, local test for when a grouping is wrong, and a way to make the model distrust those parts of the hierarchy. The test uses random walks. A good coarsening should commute with walking. Taking $k$ steps on the fine graph and then summarizing should give about the same result as summarizing first and then taking $k$ steps on the coarse graph. Wherever the two disagree, the super-node has merged things that do not behave alike under diffusion. We compute this disagreement for each super-node and each level, and use it to down-weight unreliable hierarchical channels and to split the worst super-nodes. The claim to test is that this lets hierarchical encodings keep improving past one level, where HDSE currently stalls.

Core Claim

Structural encodings based on random walks summarize a node's surroundings using the probabilities that a randomly moving particle lands at, or returns to, particular nodes after $k$ steps. Return probabilities after 3 steps flag triangles, for example, as in Substructure Aware Graph Neural Networks. Prior work uses these probabilities only as input features. We use them as a measure of coarsening error.

Let $P$ be the fine-graph random-walk transition matrix. Let $Q$ be the assignment matrix mapping nodes to super-nodes, and $Q^+$ its pseudo-inverse, which lifts super-node signals back to nodes. Graph Coarsening with Message-Passing Guarantees shows that the right coarse propagation operator is the oriented, asymmetric $P_c = QPQ^+$, and it bounds the error for one-hop linear propagation. We define the $k$-step walk-commutation residual

$$R^{(k)} = Q P^{k} Q^{+} - (Q P Q^{+})^{k},$$

which is zero exactly when $k$ walk steps survive coarsening intact. For super-node $c$, the score $e_c = \sum_{k \le K_w} \lVert R^{(k)}_{c,:} \rVert_1$ summarizes its error over walk lengths up to $K_w$.

At level two and above, the same quantity is computed with the composed assignment $Q_2 Q_1$. This makes the compounding of errors across levels directly measurable rather than hypothesized. The specific bet is that the residual at higher levels predicts where HDSE-style models fail, and that gating hierarchical attention by it restores the gains from depth.

Research Program

The work has three parts.

Diagnostic. On LRGB and ZINC molecules, we compute $e_c$ for METIS and Louvain hierarchies at depths one to three. We then test whether per-graph residual mass predicts per-graph error of an HDSE model, and whether residual mass grows superlinearly with depth. Superlinear growth is what compounding implies, since each level's error is pushed through every later assignment. The theory extends the one-hop bound of the coarsening paper. Their restricted spectral approximation controls $\lVert QPQ^+ - \text{ideal}\rVert$, and a telescoping argument bounds $R^{(k)}$ by roughly $k$ times that one-step defect for linear walks. We would state this bound and check empirically how loose it is.

Model. We build an error-aware hierarchical random-walk encoding. Each super-node at each level receives coarse random-walk features: return probabilities and relative landing probabilities under $P_c$, computed on graphs of only $c$ super-nodes. This is what HDSE lacks, since its shortest-path distances cannot tell a single bridge from many parallel paths, as argued in Self-Attention in Colors. Each super-node also receives its residual $e_c$. The residual enters the attention bias as a learned, monotone down-weighting of the hierarchical channel, so a node attending to a suspect super-node falls back on its flat, fine-level encoding.

Refinement. The second mechanism is a non-learned step: super-nodes whose residual is in the top few percent are split by re-running the partitioner inside them. This is repeated once before training. Because the residual is computed from sparse matrix–vector products, costing about $K_w$ times the number of edges times the number of super-nodes, the whole pipeline remains a preprocessing step. It avoids the all-pairs memory blowup that Benchmarking Positional Encodings for GNNs and Graph Transformers reports for relative random-walk encodings on large graphs.

Role of each direction. Random-walk structural encoding supplies the mechanism. Hierarchical error propagation supplies the question and the evaluation lens. From ReCAPA we borrow the idea of measuring how much an early mistake raises the chance of later ones, its Error Propagation Rate. That paper studies action sequences of embodied agents, not graphs, so we adapt the notion to levels of a coarsening hierarchy.

Baselines

Flat model with no hierarchy. This is the naive reference point: GCN+ or GatedGCN+ from Can Classic GNNs Be Strong Baselines for Graph-level Tasks?, a classic message-passing network with node-level random-walk encodings, residual connections, normalization and dropout. It is the strongest simple competitor, since it ranks in the top three on all 14 of that paper's benchmarks and runs three to eight times faster than GraphGPS. That paper reports a 79.3% error reduction on ZINC relative to plain GCN. No raw ZINC MAE for GCN+ was found on Lacuna.

Strongest existing hierarchical method. This is GraphGPS with HDSE from Enhancing Graph Transformers with Hierarchical Distance Structural Encoding, which reports a 6.21% Average Precision gain over GraphGPS on Peptides-func. No raw AP value for GraphGPS+HDSE was found on Lacuna.

Reported reference points on LRGB. Long Range Graph Benchmark reports test AP of 0.6439 for SAN and 0.5930 for GCN on Peptides-func. We would rerun all baselines ourselves rather than rely on these numbers.

Fair comparison. All baselines run in the GraphGPS codebase from Recipe for a General, Powerful, Scalable Graph Transformer. They use the same splits, the 500k-parameter budget of Benchmarking Graph Neural Networks, the same number of hyperparameter trials per method, and at least four seeds. Preprocessing time is reported separately.

What counts as beating them. Beating HDSE means two things. First, a statistically significant improvement at the best depth on Peptides-func, Peptides-struct and ZINC. Second, and more decisively, performance that increases from depth one to depth two or three, where HDSE is flat.

Ablations isolating the key ingredient. Two ablations matter most. The first adds coarse random-walk features but no residual gating and no refinement; this is the "obvious" hierarchical random-walk encoding. The second keeps gating but replaces the residual with a random score of matched distribution. If the first ablation matches the full model, the error-awareness contributes nothing and the paper reduces to "random walks instead of shortest paths at coarse levels".

Why not just…?

Why not just use a flat GNN+ with node-level random-walk encodings? This is a real threat on ZINC, where local motifs dominate and the GNN+ results are very strong. Hierarchy should matter where long-range structure matters, and on Peptides-func the LRGB paper shows a gap of about five AP points between GCN and global attention. We would therefore report the hierarchy's contribution separately on local and long-range tasks. We would accept a null result on ZINC as informative rather than hide it.

Why not just use a better coarsening algorithm, such as the spectrally guaranteed one or learned pooling like MeGraph? The guaranteed coarsening controls one-hop linear propagation only, and its accuracy on Cora (78.5% versus 81.6% for the full graph) shows that coarsening error remains even with guarantees. MeGraph lets coarse and fine levels correct each other through bidirectional fusion. However, its pooling uses learned feature scores with no structural check and no error bound. We would run both as alternative partitioners under our residual. If the residual still predicts failure under the better partitioners, it is measuring something they do not fix. If the residual becomes uniformly small, better coarsening is the simpler answer, and we would say so.

Why not just average over several random partitions, like beam search over hierarchies? Averaging over partitions resembles the beam aggregation in BeamAggR and could wash out bad groupings without any diagnostic. It is plausible that this works. We would include an ensemble of four Louvain or METIS seeds with the same total compute as the full model. Our method wins only if it matches or beats this ensemble at a quarter of the inference cost, or if the ensemble also fails to gain from depth.

Proposed Experiments

Synthetic propagation test. On CLUSTER and PATTERN, whose planted block structure makes a correct partition known, we inject controlled errors at level one by merging non-adjacent blocks into one super-node. We then measure, for HDSE and for our model, how much accuracy drops per corrupted super-node at depths one, two and three. This is our graph analogue of ReCAPA's propagation rate. Under the compounding hypothesis, HDSE's drop should grow with depth while ours stays flat. We also check whether the residual detects the injected merges, scored by area under the ROC curve.

Main benchmarks. We run Peptides-func (AP), Peptides-struct (MAE), PCQM-Contact (MRR) and ZINC (MAE) at depths one to three against every baseline above.

Negative control. We run PascalVOC-SP and COCO-SP, where the PE benchmark finds random-walk encodings redundant. The prediction is that residuals there are small and the method gives no gain. A method that helped everywhere would be suspicious.

Scale. We run ogbn-arxiv to test whether residual computation stays a minor fraction of training time.

Decisive outcomes. The project succeeds if three things hold. First, per-graph residual mass correlates with HDSE error. Second, gating plus refinement turns HDSE's flat depth curve into an increasing one. Third, the full model beats both the ungated ablation and the compute-matched partition ensemble on the long-range tasks. If the second outcome fails, the claim that stalling with depth is caused by compounding coarsening errors is wrong, and that negative result is itself worth reporting.