Most graph neural networks that scale to millions or billions of edges work by running a diffusion ahead of time. A diffusion here means spreading each node's features to its neighbors through random walks, as in Personalized PageRank (PPR, the probability that a walk restarting at a given node ends up at another node). A plain neural network is then trained on the diffused features. This is fast, and it avoids the collapse that happens when many message-passing layers are stacked. It also bakes in a strong assumption. Walk probabilities are non-negative, so the diffusion can only average neighbors together. On heterophilous graphs, where linked nodes tend to belong to different classes (fraud rings, dating networks, citation-by-year tasks), averaging mixes classes and erases the distinctions a classifier needs.
We propose to precompute a signed PPR. Each edge carries a weight in $[-1,1]$, estimated once from a cheap first-stage model, so that a walk crossing an edge between dissimilar nodes subtracts mass instead of adding it. The key technical observation is that the approximation algorithms behind scalable PPR, namely forward push and push-plus-Monte-Carlo, keep their termination and error guarantees when the transition weights are signed, as long as each row's absolute weights sum to at most one. If this holds in practice, heterophily-aware diffusion costs the same as PPRGo- or FORA-style precomputation and runs on graphs where signed message passing has so far been confined to full-batch toy datasets.
Core Claim
Scalable decoupled models on heterophilous graphs lack one ingredient that fixed polynomial filters cannot supply: edge-specific signs. A learnable combination of hop features such as $X, AX, A^2X$, or high-pass variants like $(I-A)X$, can realize any polynomial filter of the adjacency matrix, including ones with negative coefficients. Every edge at the same hop is still treated identically. Signed messages as in GGCN, which derives edge signs from cosine feature similarity and shows that over-smoothing and heterophily share a root cause, assign signs per edge. No polynomial in $A$ can do this. We claim this per-edge sign information can be moved entirely into precomputation.
The operator we precompute is
$$\pi_s = \alpha\, e_s + (1-\alpha)\, \pi_s S, \qquad S_{uv} = \sigma_{uv}/d_u,$$
where $\pi_s$ is the signed PPR row for seed node $s$, $e_s$ is the indicator vector of $s$, $\alpha$ is the restart probability, $d_u$ is the degree of $u$, and $\sigma_{uv}\in[-1,1]$ is an edge sign-and-strength. We set $\sigma_{uv}$ to the centered cosine similarity between first-stage embeddings of $u$ and $v$.
Forward push keeps the invariant that the true answer equals the current estimate plus residual mass diffused onward. Pushing a residual $r_u$ removes $\alpha|r_u|$ from the total absolute residual, because of the triangle inequality and $\sum_v |S_{uv}|\le 1$. Push therefore still terminates after $O(1/(\alpha r_{\max}))$ operations, where $r_{\max}$ is the residual threshold, and the $\ell_1$ error stays bounded by the leftover absolute residual.
For the long tail of small residuals, Monte Carlo walks on $|S|$ that carry the product of signs are still unbiased. Their per-walk contribution stays bounded by one, so the concentration bounds used by FORA carry over.
A structural bonus follows from the signs. On bipartite-like heterophily, two negative steps multiply to a positive one. Signed diffusion therefore automatically recovers the 2-hop homophily that LD2 hard-codes through its $A^2$ channel. It does so adaptively and only where the edge signs support it.
Position Relative to Prior Work
Three lines of work supply the machinery we reuse.
- Approximate PPR algorithms. FORA combines forward push with random walks and answers top-500 queries in under a second on a 1.5-billion-edge Twitter crawl. HubPPR and TPA (Yoon et al.) accelerate PPR further through hub indexing and community decomposition.
- PPR-based neural models. PPRGo keeps the top-$k$ PPR neighbors of each node and trains on the 12.4M-node MAG-Scholar graph in under two minutes. GBP combines reverse push with walks and handles the 1.8-billion-edge Friendster graph in about 1,849 seconds.
- The shared limitation. All of these assume non-negative, topology-only transitions. The PPR-based neural models are therefore pure low-pass smoothers. This gap motivates our work; we keep their algorithms and change only the transition weights.
Two works are the closest competitors and define what must be beaten.
HAPPY already makes PPR heterophily-aware. It reweights walk transitions using feature similarity and pseudo-label dissimilarity, and it reports gains such as +4.28% over OGNN on squirrel-filtered. Its transition weights remain non-negative, however. It extracts and stores a context subgraph per node, and it has not been run above $10^7$ nodes. Our operator differs in two ways: its weights can be negative, and it keeps only a top-$k$ list of signed scores per node, the same storage footprint as PPRGo.
LD2 is the strongest scalable heterophily method. It precomputes a high-pass 1-hop channel and low-pass 2-hop channels in linear time, and it trains on wiki (243M edges) in under a minute with under 5 GB of GPU memory. Its filters are fixed and topology-only, which is exactly the class of operator we argue cannot express per-edge signs.
HPGNN extends push to simplicial complexes. Its clique lifting does not survive hub-heavy power-law graphs, so we treat it as evidence that push-style approximation adapts to non-standard operators, not as a scalable competitor.
Three results constrain the design.
- Platonov et al. show that older heterophily benchmarks leak through more than 50% duplicate nodes. On their cleaned suite, plain GNNs that keep the node's own features separate from the neighbor aggregate take 13 of the top 15 spots. Our method must therefore beat ego-separated baselines, not only specialized heterophily models.
- The same paper finds that a graph-agnostic ResNet is often competitive. Every experiment reports it.
- Are we measuring oversmoothing correctly? warns against relying on Dirichlet energy alone. We measure over-smoothing through accuracy and class-separation statistics as the diffusion is made longer.
Research Program
The pipeline has three stages.
- Edge signs. Train an MLP on training-set labels only. Compute its penultimate embeddings and set $\sigma_{uv}$ from their centered cosine similarity, shrunk toward zero for low-confidence node pairs. This is one pass of cost $O(|E|d)$, where $d$ is the embedding width.
- Signed PPR. Run signed forward push with Monte Carlo residual walks from every labeled node and every node to be predicted. Keep the top-$k$ entries of each signed row by absolute value.
- Classifier. Train a PPRGo-style classifier whose input for each node concatenates its own features with the signed aggregate $\sum_v \pi_s(v)\,x_v$. Keeping the node's own features separate mirrors the ego-separation that Platonov et al. found decisive.
Optionally, the signs can be recomputed once from the stage-three model and the pipeline repeated. We will report whether this second round helps, since it doubles precomputation cost.
The analysis work covers three questions:
- Proving the signed push and Monte Carlo error bounds, including how variance grows when signs cancel heavily.
- Characterizing how signed PPR behaves as $\alpha \to 0$, which corresponds to effectively infinite depth. For a structurally balanced sign pattern, the limit separates the two sign-consistent groups instead of converging to a single constant vector, which would be a direct over-smoothing counterexample. For unbalanced patterns, we will measure how quickly the separation decays.
- Engineering a streaming implementation on CPU, following the FORA and GBP design, for Friendster-scale graphs.
Baselines
Graph-agnostic ResNet/MLP (do-nothing reference). This model sees only node features. Following Platonov et al., it is run with the same hyperparameter search budget as every other model and the same splits. Any graph method that does not clearly exceed it has not shown that topology helps.
LD2. This is the strongest scalable heterophily competitor: linear-time precomputed high-pass and 2-hop channels feeding an MLP (LD2). It is the most direct threat because it already scales to pokec, snap-patents, and wiki, and needs no first-stage model. We run the released design on identical splits, with the same GPU, the same total preprocessing-plus-training wall-clock budget, and the same number of tuning trials. The file reports LD2's efficiency (training on wiki in under one minute, under 5 GB of GPU memory), but no reported result was found on Lacuna for LD2's accuracy on pokec, snap-patents, or wiki. We will therefore rerun it rather than quote it. Beating LD2 means higher mean accuracy across five or more seeds, outside the seed standard deviation, on at least two of the three large heterophilous graphs, at no more than twice its preprocessing time.
PPRGo and GBP. These are the unsigned versions of our pipeline (PPRGo, GBP), run with the same $\alpha$, $r_{\max}$, and $k$ grid. On the homophilous MAG-Scholar-C, PPRGo reports 69.3% accuracy. Our method should match this within a point, which shows the signs do no harm when neighbors are similar. On heterophilous graphs we expect a large gap in our favor. If that gap does not appear, the premise is wrong.
HAPPY. This is the non-negative heterophily-aware PPR (HAPPY). It is run on the Platonov suite and arxiv-year, where the paper reports results. The file gives only relative gains (for example +2.69% over P-PPR on amazon-ratings), so absolute numbers will come from our reruns. On the million-node graphs we record whether it completes within the shared budget, and if so its memory use.
Sign ablations. These isolate the key ingredient and are the most important controls. The first keeps the same pipeline but uses $|\sigma_{uv}|$, so the edges are feature-weighted but unsigned. The second uses randomly permuted signs, which keeps the same sign statistics but destroys the information. The third uses topology-only signed polynomial hops in the SIGN style. If the unsigned feature-weighted variant matches the full method, then the gain comes from reweighting and the sign itself adds nothing.
Why not just…?
Why not just concatenate $X, AX, A^2X, (I-A)X$ and let an MLP learn the signs, as in SIGN? This is the most serious threat. Such a model learns a signed polynomial filter cheaply, and SIGN scales to ogbn-papers100M. Its signs, however, are per hop, not per edge. When one node has both same-class and different-class neighbors, which is the typical mixed-heterophily case on pokec and snap-patents, a hop-level coefficient cannot tell them apart. The SIGN-with-high-pass ablation above tests this directly. We will also report accuracy separately for nodes grouped by how mixed their neighborhood is. If SIGN matches us on the high-mixing nodes, we drop the claim.
Why not just use an ego-separated GAT or GraphSAGE with neighbor sampling? On cleaned small benchmarks this is the model to beat, per Platonov et al., and we run it there under the same budget. Its limitation is scale and depth, not accuracy. Sampled receptive fields grow exponentially with the number of layers, so on wiki and Friendster it must stay shallow. Signed PPR reaches long-range, sign-corrected context in a single precomputed step. We will report accuracy against a matched wall-clock budget, so that a win for GAT on the small graphs and a loss at scale are both visible.
Why not just reuse HAPPY's heterophily-aware walks? HAPPY's reweighted walks already avoid dissimilar neighbors, but they can only down-weight such neighbors. They cannot use a different-class neighbor as evidence against its class. They also require per-node subgraph storage. The unsigned-weighted ablation is essentially HAPPY's transition rule inside our storage-light pipeline. That comparison separates two questions: whether negative mass helps, and whether our storage format is merely a cheaper HAPPY.
Why not just an MLP? On some cleaned benchmarks an MLP is competitive, and we expect our method to reduce to near-MLP accuracy wherever topology is uninformative. That behavior is acceptable. LD2 reports that topology channels help substantially on genius, pokec, and snap-patents, which is where the MLP should lose.
Decisive Experiments
Accuracy. Datasets are the Platonov cleaned suite (roman-empire, amazon-ratings, minesweeper, tolokers, questions, squirrel-filtered, chameleon-filtered) and the large heterophilous graphs (arxiv-year, genius, pokec, snap-patents, wiki). We report accuracy, or ROC-AUC where standard for the dataset, with at least five seeds.
Homophilous sanity checks. On MAG-Scholar-C, ogbn-products, and ogbn-papers100M, signed PPR must not fall below PPRGo and SIGN.
Scaling. Friendster follows GBP's setup. We report precomputation wall-clock time, peak memory, and the empirical $\ell_1$ error of signed push against exact power iteration on subsampled seeds. The bound predicts that error scales linearly with $r_{\max}$.
Over-smoothing. We sweep $\alpha$ from 0.5 down to 0.01 and track accuracy and between-class to within-class feature distance, following the measurement caution of Are we measuring oversmoothing correctly?. Unsigned PPR should degrade toward MLP-or-worse on heterophilous graphs as $\alpha$ shrinks, while signed PPR should hold.
Kill conditions. The project is judged a failure if either of the following occurs:
- The unsigned feature-weighted ablation, or the SIGN high-pass concatenation, comes within seed noise of the full method on the large heterophilous graphs.
- Sign cancellation inflates Monte Carlo variance enough that preprocessing exceeds twice LD2's cost at matched accuracy.
References
- Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks
- Efficient Algorithms for Approximate Single-Source Personalized PageRank Queries
- LD2: Scalable Heterophilous Graph Neural Network with Decoupled Embeddings
- HubPPR: Effective Indexing for Approximate Personalized PageRank
- TPA: Fast, Scalable, and Accurate Method for Approximate Random Walk with Restart on Billion Scale Graphs
- Scaling Graph Neural Networks with Approximate PageRank
- Scalable Graph Neural Networks via Bidirectional Propagation
- Heterophily-Aware Personalized PageRank for Node Classification
- Leveraging Personalized PageRank and Higher-Order Topological Structures for Heterophily Mitigation in Graph Neural Networks
- A critical look at the evaluation of GNNs under heterophily: are we really making progress?
- Are we measuring oversmoothing in graph neural networks correctly?
- SIGN: Scalable Inception Graph Neural Networks