Certified Coordination: A Contrario Bicluster Detection in Social Media

Coordinated campaigns on social media, such as botnets, astroturfing and copy-paste brigades, leave a characteristic trace. A group of accounts uses the same small set of hashtags, links and emoji far more often than chance would allow. Written as a matrix with accounts as rows, informal tokens as columns and a one wherever an account used a token, a campaign is a small, unusually dense rectangle. Finding the densest rectangles is computationally hard. Deciding whether a rectangle you found is real or a fluke of chance is a separate problem, and current methods mostly skip it. This proposal adapts a contrario detection to that second problem. A contrario detection is a technique from image analysis that declares a pattern meaningful only when its expected number of chance occurrences, summed over every pattern one could have tested, is below one. The result is an unsupervised detector of coordinated account groups that has a provable bound on false alarms and needs no threshold tuning.

The central observation is that the guarantee does not depend on how the rectangle was found. The search can be any fast heuristic, because exact search is NP-hard. The validation step counts all possible rectangles of each size and therefore holds for whatever the heuristic returns. Proving the guarantee in principle is the easy part. The real work is finding a null model of "no coordination" that is honest about informal text, where a handful of hashtags and hyperactive accounts dominate. A naive uniform null would flag every trending tag. The proposal therefore centres on a margin-conditioned null, an empirical calibration of it, and a test of whether the certified rectangles actually concentrate on bots in TwiBot-20 and TwiBot-22.

Core Claim

Let $X$ be an $M \times N$ binary matrix of $M$ accounts by $N$ informal tokens, with $X_{ij}=1$ if account $i$ used token $j$. Tokens can optionally be paired with a time bin. Under the null hypothesis of no coordination, entries are independent with $P(X_{ij}=1)=p_{ij}$. Here $p_{ij}$ is set from the account's activity $d_i$ and the token's popularity $d_j$, for example $p_{ij}=\min(1, d_i d_j / E)$, where $E$ is the total number of ones. For a candidate rectangle $B$ with $m$ rows, $n$ columns and $s$ ones, define

$$\text{NFA}(B) = M N \binom{M}{m}\binom{N}{n}\, \overline{P}_{H_0}(S_B \ge s),$$

where $S_B$ is the number of ones in $B$ under the null and $\overline{P}$ is a Chernoff/Bennett upper bound on its Poisson-binomial tail. The factor $MN$ pays for choosing the size, and the binomial coefficients pay for choosing which rows and columns. The standard a contrario argument then gives the guarantee: if the null holds, the expected number of rectangles anywhere in the matrix with $\text{NFA}<\epsilon$ is at most $\epsilon$. This is the same guarantee On Straight Line Segment Detection establishes for line segments.

The test count is astronomically large, and it is still affordable because the data are sparse. With a million accounts, choosing 50 of them costs roughly $10^{235}$ in the test count. A 50-account by 5-token block filled to 90% when the typical $p_{ij}$ is near $10^{-4}$ has a null probability of order $10^{-900}$. Such a block clears the bar easily. A block made of trending tags and heavy posters has large $p_{ij}$ and does not clear it. The claim to be tested is that this one number gives calibrated, tuning-free detection on real informal data, and that the detections are enriched for coordinated or automated accounts.

Relation to Prior Work

The method comes from the vision line of a contrario detection. LSD: a Line Segment Detector uses a binomial null on gradient orientations to detect segments without parameters. Robust and Accurate Line- and/or Point-Based Pose Estimation without Manhattan Assumptions shows that the same logic can set inlier thresholds inside a randomized search. That second result is the closest precedent for our split between heuristic search and exact validation. These works use simple uniform nulls over geometric families of polynomial size. We need a heterogeneous null over a family of rectangles that is exponential in size.

On the biclustering side, three results constrain the design. Monochromatic Bi-Clustering and A Constant-Factor Approximation Algorithm for Co-clustering. establish NP-hardness, which is why we give up on exact search. The second paper also shows that clustering rows and columns separately is a good approximation for global partitions, but that is the wrong objective for a few small, local blocks. Efficient and Effective Optimal Transport-Based Biclustering supplies a scalable method whose cost grows with the number of nonzeros. However, it requires the cluster count and regularisation to be set by hand, and it offers no significance test.

The closest statistical work is A Multiscale Scan Statistic for Adaptive Submatrix Localization. It localizes one elevated block of unknown size using size-dependent penalties and a hill-climbing search, and it is proven only under homogeneous synthetic noise. We reuse its alternating hill-climbing search. We differ in four ways: we replace its penalty with an explicit false-alarm count, we allow a heterogeneous null, we extract many blocks with a stopping rule, and we apply it to text. Liew et al. imported the Hough transform into biclustering but used raw accumulator thresholds. That is exactly the step an a contrario count replaces.

On the language side, two papers motivate the choice of informal tokens as columns. Multi-Channel Convolutional Neural Network for Twitter Emotion and Sentiment Recognition reports that a separate channel for hashtags and emoji adds 2.3–3.5% accuracy. Learning Cross-Lingual Word Embeddings from Twitter via Distant Supervision finds that non-standard tokens behave as stable anchors. Twitter Topic Summarization by Ranking Tweets using Social Influence and Content Quality builds user–tweet–word graphs but ranks them with heuristic propagation and attaches no significance. BotRGCN and TwiBot-22 treat coordination as supervised node classification, and they report memory walls and poor transfer across sub-communities. Those reported weaknesses are what makes an unsupervised detector that scales with the number of nonzeros worth testing. Finally, Local Compositional Complexity also separates structure from noise in the spirit of the Helmholtz principle, the idea that we perceive structure only when chance cannot explain it. It works on clean text, uses a description-length criterion, and gives no false-alarm count.

Research Program

The first component is the null model and its calibration. The margin-conditioned null uses estimated margins, so the guarantee is approximate. We will measure how approximate by randomising real matrices while preserving every account's and every token's counts, using degree-preserving swap randomisation. On each randomised matrix we run the full pipeline and count detections at $\epsilon=1$. Calibration means the average count is at most one. We will also report where it breaks: tiny tokens, extreme accounts, and the bursty token-time columns. If the count is miscalibrated, we will replace the margin product with a fitted logistic margin model and re-test.

The second component is search and peeling. Seeds come from token pairs that co-occur unusually often. Each seed grows by alternately adding or removing the rows and then the columns that most reduce the NFA, in the style of the Liu and Arias-Castro hill climb. Each pass is linear in the nonzeros it touches. A rectangle with $\text{NFA}<1$ is reported, its entries are masked, and the process repeats until no seed passes. This stopping rule replaces the hand-set cluster count of BCOT. Because masking changes later nulls, we will either recompute the NFA against the original margins or report detections only in non-overlapping order.

The third component is the choice of informal columns. We compare three column sets: hashtags, URL domains, mentions and emoji alone; content words alone; and all tokens together. We also compare each of these with and without hour bins. Binning separates genuine simultaneity from slow-moving interest communities.

Baselines

The naive reference point is the base bot rate among accounts flagged by a frequency rule: an account is flagged if it shares at least $k$ tokens with at least $u$ other accounts. Results are reported for every $(k,u)$ on a grid, so that the threshold-tuning cost the a contrario method avoids is visible. Random selection of accounts gives the overall bot prevalence. Detections must beat both at matched numbers of flagged accounts.

The strongest supervised competitor is BotRGCN, run with its released configuration. The most relevant reported number is accuracy 0.8462, F1 0.8707 and MCC 0.7021 on TwiBot-20, from BotRGCN. For TwiBot-22, the file reports only that graph models beat feature models by 8.2%, from TwiBot-22. These figures classify all accounts, while our method flags a subset, so the fair comparison is precision at matched coverage. We rank BotRGCN's scores and compare the precision of its top-$K$ accounts with the precision of our $K$ flagged accounts. We also compare under a cross-community split, training BotRGCN on one TwiBot-22 sub-community and testing on another. Beating BotRGCN means matched-coverage precision that is equal in-domain and higher cross-domain, with no labels used.

The strongest unsupervised competitors are BCOT and the multiscale scan statistic, both run on the identical matrix. Each method gets the same number of hyperparameter or cluster-count settings, and each block it returns is calibrated by a permutation test that reruns the method on 100 swap-randomised matrices. The two ablations that isolate our key ingredient are, first, an NFA with a uniform null where every $p_{ij}$ equals the global density, and second, a "local" score that drops the binomial test-count terms. The first ablation should flood the output with trending-tag blocks, and the second should overfire on the randomised matrices.

Why not just…?

Why not just train a relational graph network? BotRGCN works well when labels match the deployment community. TwiBot-22 itself documents out-of-memory failures and poor transfer between communities, and a supervised score has no interpretable false-alarm meaning. The cross-community comparison above tests directly whether our label-free detector holds up where BotRGCN degrades. If BotRGCN wins even cross-domain, our method's value narrows to interpretability and calibration, and we will report that plainly.

Why not just run BCOT or the scan statistic and calibrate with permutations? This is the real threat. Permutation calibration is valid. It costs one full search per permutation and controls only the maximum statistic, not each detection in sequence. Our experiment compares precision and calibration at equal wall-clock time. If permutation-calibrated BCOT matches our numbers, the contribution reduces to a closed-form substitute that is about 100 times cheaper, and the paper will be framed that way.

Why not just cluster rows and columns separately and intersect? The constant-factor guarantee of Anagnostopoulos et al. concerns global partitions. Blocks of 50 accounts out of a million are averaged away, which matches the experience in Liu and Arias-Castro that SVD-based clustering loses to local scanning. Planted-block recovery on real randomised matrices will show this directly.

Why not just detect near-duplicate tweets? Copy-paste campaigns would be caught by exact or near-duplicate matching. Coordination through shared links and tags with varied wording would not. We will report the fraction of certified blocks whose members share no near-duplicate text. If that fraction is negligible, the simpler detector suffices.

Proposed Experiments

The first decisive check is calibration. Across 100 swap-randomised versions each of the TwiBot-20 and TwiBot-22 account-by-token matrices, the mean number of detections at $\epsilon=1$ must be at most one under the margin null, and should be much larger under the uniform-null ablation. The second check is planted recovery. We plant blocks of varying size and density into the randomised real matrices and measure recovery rate against block strength for our method, the scan statistic and BCOT. This extends the synthetic benchmarks of the scan-statistic paper to heterogeneous informal data. The third check is substance: on the real matrices, measure bot precision and bot coverage of certified blocks against the baselines at matched coverage, both in-domain and cross-community. We will also manually inspect 50 blocks to estimate how many are organic communities, such as fandoms or breaking news, rather than coordination. That last number is the honest limit of the method. A contrario detection certifies non-randomness, not inauthenticity, and the hour-binned columns are our main lever for narrowing the gap between the two.