Regular equivalence vs. Weisfeiler–Lehman for coordinated accounts

Links: CS224W L06 (theory of GNNs, Classic SNA bridge and proof workshop), L07 (structural features), notebooks/project/retweet_thread.py (the running project this extends). Atlas: expressivity theory; social networks and information ecosystems.

Question

Sociology's regular equivalence (White & Reitz 1983; CATREGE, Borgatti & Everett 1993) and graph ML's colour refinement (1-WL, the ceiling of message-passing GNNs) are the same iterative procedure with one difference: regular equivalence refines by the set of neighbour classes, WL by the multiset. In GNN terms: max aggregation versus sum. Which of the information each one keeps (direction, counts, roles) matters for finding coordinated accounts on an X-like retweet graph, when per-account behaviour is camouflaged?

Hypotheses (written before running)

1. Lattice. From the same initial colouring, directed WL refines undirected WL and directed RE, and both refine undirected RE, at every round. (A theorem, proved in the notebook; the run checks it numerically.)

2. Exact equivalence is degenerate at scale. On a ~1,200-node graph WL individualises almost every node within 2–3 rounds, and undirected regular equivalence collapses to one class.

3. Counting matters for coordination. In a continuous relaxation (random-weight message passing), sum aggregation detects rings better than max or mean from structure alone; direction helps max the most.

Setup

• Data: gl.retweet.make_world(seed, stealthy()): 1,200 humans in 4 communities, 3 rings of 10 coordinated accounts with human-like timing and camouflage retweets; worlds 0, 1, 2 (config.yaml).

• Exact study: refinement with set/multiset aggregation, directed/undirected, up to 6 rounds.

• Continuous study: 3 rounds of tanh(W [h ‖ AGG_out ‖ AGG_in]) with random W (never trained), AGG ∈ {max, mean, sum}, from a constant start (structure only) or from 7 account features; logistic regression on all rounds; per-fold ROC AUC for ring membership, 5-fold CV × 2 repetitions × 3 weight draws.

• Baselines: log in/out degree; account features alone.

Run: uv run marimo edit experiments/rege-vs-wl/rege_vs_wl.py and press the three run buttons (experiment 1: about a minute; experiment 2: a few minutes). The notebook writes results.md, results.json, ring_results.json and coamp_results.json.

Results (summary; full table in results.md)

• Hypothesis 1 holds at every round (checked on world 0).

• Hypothesis 2 holds: WL is discrete by round 2; undirected RE has 1 class from round 1; directed RE starts at 3 classes and is also discrete by round 4. Exact equivalence says nothing useful at this scale, which is why SNA moved to approximate roles and why GIN's continuous similarity matters.

• Hypothesis 3 holds. From structure alone: undirected max and mean 0.502 (chance, as Proposition 2 predicts; the 0.002 is one world's three isolated accounts), sum 0.998; directed max 0.895, mean 0.956, sum 1.000. The degree-only baseline is 0.595, so the advantage of sum is counting over several hops, not degree.

• Experiment 2 (random ring sizes and a size shift). Hypothesis, written before running: with a fixed ring size counts are a fingerprint, so when sizes vary, and above all when a readout trained on small rings (4–7) is tested on large ones (14–20) or the reverse, sum should lose and sets should transfer. Refuted. Directed sum stays at 0.997 in distribution and 1.000 / 0.999 under both shifts; directed max drops to 0.832 / 0.651 and directed mean to 0.948 / 0.615; degree alone 0.640 → 0.559 / 0.536. Counting carried the signal; the normalised aggregators were the brittle ones. (Why is not yet tested; see the notebook for a reading and the ablation it needs.)

• A numerical trap found on the way: from a constant start, mean aggregation is constant in exact arithmetic, but in floating point "d identical values summed and divided by d" leaves ~1e-16 differences that depend on d. With one isolated account giving a column some spread, the classifier ranked by that noise and learned degree from rounding error (per-fold AUC 0.05). Inputs are now rounded to 10 decimals at each layer; mean is exactly 0.500 again.

• Experiment 3 (pure co-amplification rings). No ties among members; they only amplify their targets' posts and are followed and post like humans (co_amplify=True), so reciprocity and in-degree give nothing away. Hypothesis: without reciprocity, sets should match or beat counts. Refuted. Directed sum 0.914 (0.890 / 0.917 under the size shifts), directed max 0.709, directed mean 0.717, degree 0.655. The standard coordination heuristic, co-retweet (Jaccard) overlap, is the weakest structural signal at 0.611. Across all three experiments the multiset beats the set and direction-aware beats undirected.

Caveat: the world is synthetic; these results say what the method can detect when the mechanism is known. These results say what the method can detect when the mechanism is known; they do not say what real coordinated accounts look like.

Next steps

1. ~~Rings of random size~~ (done, experiment 2: counting transfers, sets do not).

2. ~~Pure co-amplification rings~~ (done, experiment 3: counting still wins; co-retweet overlap is weak). Next for the role notion: rings whose members differ in volume by orders of magnitude, so counts are noise.

3. Ablate the sum's robustness: sum without per-graph standardisation, and reciprocated-tie counts alone.

4. Weighted and temporal refinement: multisets of (colour, weight bucket) and of (colour, time-gap bucket).

5. Real data: gl.retweet.load_retweets_csv on a labelled coordination dataset; compare with RolX-style role discovery and with a trained direction-aware GIN.

6. Theory: characterise the logic of max-aggregation GNNs on directed graphs (a graded-modal-logic fragment without counting; cf. Barceló et al. 2020, Grohe 2021).

References

White & Reitz (1983) Graph and semigroup homomorphisms on networks of relations, Social Networks 5 · Borgatti & Everett (1993) Two algorithms for computing regular equivalence, Social Networks 15 · Weisfeiler & Leman (1968) · Xu, Hu, Leskovec & Jegelka (2019) How powerful are GNNs? (ICLR) · Morris et al. (2019) Weisfeiler and Leman go neural (AAAI) · Barceló et al. (2020) The logical expressiveness of GNNs (ICLR) · Grohe (2021) The logic of graph neural networks (LICS) · Hooi et al. (2016) FRAUDAR (KDD).

In the repository: experiments/rege-vs-wl/ · README.md coamp_results.json config.yaml rege_vs_wl.py results.json results.md ring_results.json