Label Propagation Along Edges Fakers Cannot Cheaply Forge

Fake popularity on social platforms is manufactured by accounts that must look like they belong. Modern bots and paid followers deliberately follow many ordinary humans, so in the follow graph they sit among real people. This camouflage breaks the most scalable graph method we have, label propagation: the idea of spreading a few known "bot" and "human" labels to unlabeled accounts along the graph's edges, on the assumption that connected accounts tend to share a label. Our proposal starts from one asymmetry. A bot can create outgoing edges (whom it follows, likes, or mentions) at almost no cost. It cannot cheaply make real humans follow it back. We therefore propagate labels separately along each edge direction and relation, computed once as sparse matrix products before any training. A small classifier then learns how much to trust each direction at each distance. Because the propagation is precomputed, the method should run on the full million-user TwiBot-22 graph, where most camouflage-aware graph neural networks run out of memory.

The opportunity matters because the field faces a trade-off. The detector built for camouflage, HOFA, uses end-to-end message passing with negative attention weights and has not been shown to run at TwiBot-22 scale. The methods that do scale, such as GAMLP and PTA, treat every edge as evidence of shared labels. We claim that the useful part of camouflage resistance can be captured before training, in which edges labels travel along, and does not require a learned high-pass filter. If that holds, robust detection and scalability stop being in conflict.

Core Claim

We claim that direction-split, relation-split label propagation, computed once and then combined by a learned attention over hops and channels, matches or beats coupled camouflage-aware graph neural networks on bot and collusion detection. It should also fit on one GPU for the full TwiBot-22 graph, and it should be harder to fool with injected accounts, because an attacker's cheapest edges end up in the channels the model learns to discount.

Let $A_r$ be the directed adjacency matrix for relation $r$ (follow, like, mention), with $(A_r)_{ij}=1$ if account $i$ acts on account $j$. We form three operators per relation: incoming edges $A_r^\top$ (who acts on me), outgoing edges $A_r$ (whom I act on), and reciprocated edges $A_r \circ A_r^\top$. Each operator is row-normalized, giving a channel $P_c$. Let $\tilde Y$ be the matrix of seed labels with the current training fold masked out. We precompute

$$Z_c^{(k)} = P_c^{\,k}\,\tilde Y, \qquad k = 1,\dots,K,$$

together with the high-pass residual $s - Z_c^{(k)}$. Here $s$ is the prediction of a metadata-only classifier, meaning a model that sees only profile fields such as account age and posting rate and never sees the graph. The residual measures how much an account's neighbourhood disagrees with its own profile. A small network with attention over the pairs $(c,k)$, in the style of GAMLP's attention over hops, produces the final score. The cost of precomputation is $O(|E| \cdot K \cdot C)$, where $|E|$ is the edge count and $C$ the number of channels, because each hop is one sparse matrix product per channel.

Positioning Against Prior Work

Several papers motivate the gap. HOFA documents "heterophilous disguise": bots following humans so that averaging over neighbours dilutes their suspicious signal. It counters this with a metadata-based nearest-neighbour graph and tanh attention that can assign negative weights, all trained end to end. TwiBot-22 shows that graph structure matters, since removing it costs up to 25% F1. It also reports that many strong detectors hit out-of-memory errors at one million users. My Brother Helps Me had to shrink TwiBot-22 to subgraphs of about 50,000 nodes just to run its attack. The asymmetry itself has earlier support. The marionette study found that genuine users rarely follow fake accounts back. Its expectation-maximization model on a 12,000-user graph improved F-measure from 0.872 to 0.892 by weighting social relations. We turn that observation into an explicit channel design and run it at a scale the marionette study never reached.

Other papers supply the method. Dong et al. prove that decoupled graph convolution networks are equivalent to "propagate labels, then train." That result justifies using propagated labels as supervision or as input features. GAMLP provides attention over hops and a last-residual connection that stops the model from reading its own training labels. GLPN-LLM shows that random label masking prevents this leakage during propagation. We depart from all three in two ways. They propagate over a single undirected, homophily-assumed operator. They were evaluated on citation graphs or small misinformation graphs, not adversarial ones.

A third group constrains the design. CMLP propagates fraud labels over a user–item graph with 877M edges and implicitly down-weights popular items. That makes clear that scale alone is not new, and that popular hubs need handling. Sarkar et al. show that turning high-degree hubs into sinks, nodes where random walks stop, has bounded error and can improve accuracy. We adopt it as an option for celebrity accounts and viral hashtags, not as a core ingredient. Fixed Aggregation Features Can Rival GNNs is the strongest threat to the proposal and is handled directly below.

Research Program

The build has three parts. The first is a sparse precomputation pipeline over TwiBot-22's multi-relational graph. It produces label channels split by direction and relation and runs out of core by streaming the edge list. Leakage is prevented by k-fold seed masking: each training node's propagated features come only from seeds in the other folds.

The second part is the attention classifier over (channel, hop) pairs. Its learned attention weights are themselves a result, because we expect them to be low on outgoing follow edges and high on incoming and reciprocated edges.

The third part is analysis. We will measure how much each channel is homophilous on labeled nodes, that is, how often its edges join accounts with the same label. We will also compute an "attacker cost" profile: the fraction of each channel's mass that an adversary controlling only bot accounts could fabricate. We will test whether that fraction predicts the attention weights.

The adversarial study reruns the brother-injection attack from My Brother Helps Me, on its 50,000-node subgraphs and on the full graph. We will then run an adaptive variant in which the attacker also buys incoming edges from compromised low-activity accounts. That variant tells us how the defense degrades as fabricating edges gets cheaper.

Baselines

The naive reference point is the metadata-only classifier: gradient-boosted trees and a multilayer perceptron trained on account profile features, with no graph. It is immune to disguise by construction, as HOFA's use of it as an anchor shows. Any graph method must clearly beat it on MCC to justify the graph. The second reference is classical training-free label propagation, Personalized PageRank over the undirected union of relations, run with the same seeds. It tests whether anything beyond plain diffusion is needed.

The strongest reported competitor on the full TwiBot-22 graph in the file is CACL. Its HGT+CACL model reports 75.07% accuracy and 32.39 MCC, against 29.18 MCC for plain HGT. BotRGCN and RGT are the graph baselines cited by TwiBot-22, but no reported result found on Lacuna for their individual TwiBot-22 scores. We will rerun them on the official splits. The strongest camouflage-specific competitor is HOFA, which reports 82.29% accuracy on TwiBot-20 and 88.68% on MGTAB-22. We compare against it on those two datasets using their published splits. On TwiBot-22 we give HOFA the neighbourhood sampling it needs to fit in memory and report both its score and its cost.

The scalable decoupled competitors are GAMLP and PTA, run on the same features and seeds with a single undirected operator. This contrast isolates the value of splitting by direction.

All methods share the same user features, the same train, validation and test splits, one 24-hour hyperparameter search budget, and one GPU with fixed memory. We report MCC, F1, accuracy, AUC-PR, peak memory, and wall-clock time. Beating the baseline means exceeding 32.39 MCC on full TwiBot-22 within single-GPU memory, and matching HOFA within one point of accuracy on TwiBot-20 and MGTAB-22 at a fraction of its training time.

Three ablations isolate the key ingredient. The first collapses all channels into one undirected operator. The second keeps the channels but propagates features instead of labels. The third removes the high-pass residual.

Why not just…?

Why not just train a tabular classifier on account metadata? TwiBot-22 reports that graph models beat feature-based models by 8.2% on average on that benchmark, and that removing the network component costs up to 25% F1. Paid followers and marionettes are specifically built to have realistic profiles. The counter-evidence is real, though. TROLLMAGNIFIER reaches 97.8% F1 with a random forest over hand-built interaction features. The metadata-only baseline is therefore included, and we will also feed it simple counts of in-edges versus out-edges, to check whether counting degree in each direction already captures the asymmetry.

Why not just run Personalized PageRank? It is fast, but Dong et al. show that plain propagation degrades under structural noise. Camouflage edges are structural noise placed deliberately to cross the human/bot boundary. The undirected PageRank baseline measures this directly, and the channel-collapse ablation shows whether any failure comes from mixing directions.

Why not just precompute fixed aggregation features in each direction and train gradient-boosted trees? This is the most serious threat. Fixed Aggregation Features Can Rival GNNs suggests that a tabular model over precomputed neighbourhood averages may be enough. If those averages are also split by direction, it could capture most of our gain. We therefore run exactly this baseline with our channel split. The features-versus-labels ablation settles the question. If it ties with us, we will report that the contribution is the direction and cost-aware channel design rather than label propagation itself, and we will recommend the simpler model. We expect propagated labels to help most where seeds are scarce and features are forged, and we will test this by cutting seeds to 1% of labels.

Why not just subsample the graph and run HOFA or CACL? Subsampling is how the adversarial study coped with scale, and it breaks up coordinated clusters that span communities. We will report HOFA under sampling on TwiBot-22. If it matches us at equal compute, our claim reduces to an efficiency result, and we will say so.

Decisive Checks

Four results decide the proposal. First, the method must exceed 32.39 MCC on the full TwiBot-22 graph on one GPU. Second, on labeled nodes, incoming and reciprocated channels must be measurably more homophilous than outgoing ones, and the learned attention must follow that ordering. If both directions are equally homophilous, the premise fails. Third, under the brother-injection protocol, the attack success rate should fall well below the more than 73% reported against GCN and R-GCN detectors. Under the adaptive attacker who buys incoming edges, robustness should degrade in proportion to that added cost. Fourth, the method must beat fixed aggregation features with the same direction split once seeds are scarce.

One caveat applies throughout. TwiBot-22 labels come from weak supervision that is 90.5% accurate against expert labels. We will therefore also report results on the expert-labeled subset, so that label propagation is not rewarded for reproducing artifacts of how the labels were generated.