betaFeedback

WorksComputer Science

Statistical Detectability of Coordination

Abstract

Information operations exploit coordinated activity on social media to amplify messages and manipulate public discourse. A common approach to coordination detection is to project account-entity interactions into account similarity networks based on temporal proximity, action counts, or behavioural similarity, and identify dense subgraphs or behavioural clusters. However, the current methodology finds groups of co-activated accounts or partitions all users into most similarly acting clusters, even when the accounts are acting independently of each other or the co-activity is due to some expected source. We formulate coordination detection based on hypothesis testing of account pairs and compare different null models. We connect the resulting pairwise scores to the planted-submatrix detection problem and derive statistical and computational limits as functions of group size, population size, and signal strength. We estimate the signal for 7 modalities of coordination over 26 labelled information-operation datasets, and compare the predicted regime with the performance of recovery heuristics. Our method achieves higher agreement with the labelled ground truth than previously reported, but the choice of null model is important and it changes the regime of most modalities. While it is always possible to extract a set of significantly densely co-acting accounts across nearly all modalities regardless of regime, density alone is uninformative of detection performance, rendering anomalous cluster discovery a poor proxy for recovering an information operation. Detectability boundaries establish whether an operation of a given size and signal can be recovered at all, and how much confidence a flagged group warrants.

Introduction

Information operations exploit coordinated activity on social media to manipulate conversations and spread disinformation through synchronised actions, such as simultaneous hashtag usage, coordinated replying, or orchestrated content amplification [1, 2, 3, 4]. Detecting such orchestrated campaigns from their online traces is critical to preserve the integrity of online spaces.

To isolate coordinated groups, detection pipelines typically build a coordination network, linking accounts whose actions resemble one another or co-occur close in time, such as accounts posting the same URL, reusing the same hashtag, reposting the same post, or replying in near-synchrony [3, 5, 6, 7, 8, 9]. Clustering of account behaviour or community detection methods then recover groups whose internal connections are denser than their connections to the rest of the network or whose activity patterns are similar [10, 11, 12]. Parameters are typically tuned empirically or set from prior domain knowledge, treating “similar enough,” “close enough,” or “dense enough” as a design choice. However, the choice of time window and what kind of clusters count as synchronised determine which coordination is detectable [13, 9].

A central challenge is to separate coordination from co-activity that arises by chance or from patterns expected among organic users. For example, users can act close in time by reacting to the same trending topic or hashtag, by following their own daily rhythms, or simply because they are very active. Accounting for such activity can change conclusions: Pantè et al. [ [14] show that, once organic control accounts are included, there is no statistical evidence of the inter-state coordination that earlier studies had suggested. We argue that a detected group is evidence of coordination only if expected patterns and resulting chance co-activity cannot explain its total signal. Benchmarks on labelled data show whether a detector recovers known operations, but do not quantify how surprising the observed structure is under the assumption of independent behaviour.

We treat coordination as a hypothesis-testing problem with two levels. At the level of pairs, we test each pair of accounts against a null model with prescribed patterns but otherwise independent activity, and turn its pp-value into a score, so that a coordinating group of kk accounts among nn becomes a k×kk \times k block of elevated scores in an n×nn \times n matrix. At the level of groups, we reduce coordination detection to the planted submatrix problem, for which the conditions under which such a block can be detected are known [15, 16, 17, 18, 19]. In contrast to the typical approach of graph clustering without a statistical model, which always returns a partition of the graph and where quality functions such as modularity are well-known to be prone to overfitting Guimera et al. [ [20], Peixoto [ [21], this formulation allows us to answer under what conditions coordinated behaviour can be detected. We derive a phase diagram with three detection regimes (impossible, hard, and easy), whose boundaries are functions of group size, population size, and signal strength. We also provide a theoretical basis for the recent empirical observations that multi-modality improves coordination detection [9, 22], showing that combining MM independent modalities of equal signal lowers every detection threshold by a factor of 1/M1/\sqrt{M}, so an operation that cannot be detected in any single layer can become detectable.

We measure the signal strength of 26 labelled information operations [23] and compare the predicted regime with the recovery of two greedy heuristics and a spectral method on 7 modalities and an aggregated view of each operation. Since chance synchrony has several sources, we implement four null models, and measure how much the conclusions depend on the definition of chance. The measured signal depends on the null model, because each null model attributes different parts of the observed synchrony to chance. Our approach has several assumptions that are common in the literature, but are often implicit, and made explicit by our principled statistical framework. This allows us to test the effect of these various assumptions to the peformance of the coordination detection.

This paper makes several contributions by formulating coordination detection as hypothesis testing within the planted-submatrix problem. First, we derive information-theoretic and computational boundaries for the detection of a coordinated campaign. Second, we introduce a new methodology for coordination detection, which achieves higher agreement with the labelled ground truth than previously reported [22], although the evaluation protocols cannot be made exactly equivalent. Third, we evaluate four null models on 26 information operations and show how and why the predicted regimes depend on the choice of the null model. Fourth, we show that multi-modal analysis lowers detection thresholds by 1/M1/\sqrt{M}. Finally, we show that a permutation test on the density of a returned set does not indicate recovery: the heuristics return significantly dense sets even when they do not recover the operation. Thus, structural properties of the coordination networks alone are an insufficient proxy for coordination detection.

Related Work

Coordination detection. Most methods for coordination detection build a network in which an edge links two accounts that act alike, and extract groups from the resulting network by connected components, community detection, or clustering [3, 5, 10, 8]. Such pipelines have been applied to elections [5, 24], to information operations [8, 11], and across platforms [25]. The modality, the size of the time window, and the threshold to retain significant edges are usually design choices [12]. The clustering and community detection methods used in this step return a partition or a group for any input network, including random graphs. Commonly used quality metrics such as modularity are known to overfit: modularity can take high values even on random graphs [20], so a high modularity is not evidence of communities [21]. The question is therefore not only whether a coordinating cluster exists, but whether its members co-act more than independent accounts would. A few studies test suspicious accounts against control accounts [14] (Mungari et al. 2026), or compare the coordination of accounts in an information operation with samples of regular users [Keller et al., 2020]. Still, the field lacks a formal and statistically grounded definition of coordination, including well-defined null models [12], and there is limited knowledge of when coordination is even detectable.

Detecting a planted submatrix. Like other methods that extract groups of nodes, dense-subgraph extraction returns a dense set for every input, including pure noise [Charikar, 2000, Hooı et al., 2016, Shabalin et al., 2009]. Statistical work asks when a planted block can be detected. Scan statistics detect it above the information-theoretic boundary [Kulldorff, 1997, Arias-Castro et al., 2011, Addario-Berry et al., 2010], while polynomial-time methods need a larger block or a stronger signal [17]. Locating the block, i.e. recovery, is at least as hard as detecting it [17]. Polynomial-time recovery is known above a signal of the order of the spectral boundary [Hajek et al., 2018], and the statistical and computational limits of recovery are also known for several planted submatrices [Chen and Xu, 2016]. The computational lower bound holds for broad classes of distributions of the entries of the matrix [18]. To our knowledge, these results have not yet been applied to coordination detection.

Methods

Co-action layers and null models

Figure 1. The pp-value of a pair under the account-activity null model. (a) Daily activity profiles of two accounts. (b) Two users co-act. (c, e) Two patterns of co-action times. (d, f) Distribution of the time intervals Δt\Delta t between co-actions, observed and under the null model, with the pp-value; the dotted line at 3 minutes shows that counts over a fixed time window might not distinguish the two co-action patterns.

We model the activity of nn accounts. An item is the object of an action, and a modality is a type of action on an item. The available modalities depend on the social media platform. In Section 4 we use seven modalities: using a hashtag, sharing a URL, mentioning an account, replying to a post, replying to an account, reposting a post, and reposting an account. Two accounts co-act in a modality if both act on the same item. Each modality defines a layer, a graph whose edges connect accounts that co-act at least once. Such pairs of accounts are tested for temporal synchronisation, and each edge carries a pp-value pij(l)p_{ij}^{(l)} that measures how unusually the pair acts on their shared items, under a null model.

Accounts that coordinate have been observed repeatedly performing similar or identical actions within a short span of each other, more often than other accounts [3, 5, 8]. Making this precise requires a choice of how short “short” is, yet different modalities operate on different natural time scales [22], and there is no consensus on a single window value that works across modalities or across documented coordinated campaigns [13, 12].

For a tested pair (i,j)(i,j) and a shared item oo, let Ti(o)T_i(o) and Tj(o)T_j(o) denote their respective action timestamps on oo. For each t∈Ti(o)t \in T_i(o), the interval to the next action of jj is

Δi→j(t;o)=min⁡s∈Tj(o), s≥t(s−t),\Delta_{i\to j}(t;o)=\min_{s\in T_j(o),\,s\ge t}(s-t),

provided such an action exists. We define Δ‾ij(o)\overline{\Delta}_{ij}(o) as the mean of the existing intervals in both directions. This statistic requires no fixed time window.

A null model generates randomised replicates of the actions on oo. With B=100B=100 item-level Monte Carlo replicates, pij(o)=(r+1)/(B+1)p_{ij}(o)=(r+1)/(B+1), where rr counts replicates whose mean interval does not exceed the observed Δ‾ij(o)\overline{\Delta}_{ij}(o). We use Fisher’s method to combine the pp-values of all items shared by the pair in modality ll into pij(l)p_{ij}^{(l)}.

We consider four null models that preserve each account’s actions on each item but randomize their timestamps to test for synchrony. We can approximately order the null models by the amount of observed temporal structure that they preserve [Gavin et al., 2022]. The uniform-modality null model draws the time of each action uniformly from an evenly spaced grid with one point per action, between the first and the last action in the modality. The uniform-account null model instead uses a separate grid per account, spanning its first and last actions across all modalities, thus preserving each account’s active period. Both null models attribute every other timing pattern, including daily rhythms and reactions to the same item, to synchrony. The account-activity null model preserves the date of each action and redraws its hour from the hourly profile of the account for that day of the week. Two accounts being active at the same hours is then not by itself evidence of coordination, if it is compatible with their baseline activity profiles. This null model does not model reactions to an item, so it overstates the synchrony of accounts that respond to the same post or URL soon after it appears (Section 4). The item-virality null model redraws the action times of an account on item xx uniformly, with replacement, from the action times of all accounts on xx. This keeps the adoption curve of each item in expectation, so accounts that react to a viral item at the same time are not by themselves evidence of coordination.

Coordination as planted submatrix

We model coordination as a single group of accounts whose activity produces pairwise independent pp-values from a coordination distribution PP, while all other pairs produce pp-values from a uniform distribution QQ on (0,1)(0,1). This model defines a hypothesis, H1H_1, which is tested against the null H0H_0 (absence of coordination). Our modeling makes the following two assumptions. First, the pp-values are independent, treating all the dependencies in the activity signals of nodes as encoded in the null model. Second, we assume that there is no internal structure among the coordinated or uncoordinated nodes. The latter is analogous to the typical, but often implicit, assumption in community detection methods that the clusters are internally homogeneous Fortunato et al. [2010].

For a coordinating pair of accounts (i,j)(i,j) we assume pij(l)∼P=Beta⁡(λ,1)p_{ij}^{(l)} \sim P=\operatorname{Beta}(\lambda,1) with 0<λ<10<\lambda<1. This is a common family of generating pp-values under an alternative hypothesis because its non-increasing density assigns greater probability to small pp-values [Sellke et al., 2001]. Moreover, Fisher’s method is optimal for combining independent pp-values following this family [Heard and Rubin-Delanchy, 2018]. However, our analysis can be carried out for any other continuous distribution PP supported on (0,1)(0,1). The log-likelihood ratio of Beta⁡(λ,1)\operatorname{Beta}(\lambda,1) against the uniform distribution, evaluated at the observed pij(l)p_{ij}^{(l)}, is log⁡λ+(1−λ)(−log⁡pij(l))\log\lambda+ (1-\lambda)(-\log p_{ij}^{(l)}), which is increasing in −log⁡pij(l)-\log p_{ij}^{(l)}. For a fixed set of independent pairs sharing the same λ\lambda, rejecting when the sum of −log⁡pij(l)-\log p_{ij}^{(l)} exceeds a critical value is uniformly most powerful: among tests with the same significance level, it has the highest probability of detecting coordination for every 0<λ<10<\lambda<1 [Lehmann and Romano, 2005].

This motivates the centred score

Yij(l)=−log⁡pij(l)−1,(1)Y_{ij}^{(l)}=-\log p_{ij}^{(l)}-1, \tag*{(1)}

which has mean 0 and variance 1 under H0H_0. Under the Beta alternative, Yij(l)∼Exp⁡(λ)−1Y_{ij}^{(l)}\sim\operatorname{Exp}(\lambda)-1, with mean μ:=1/λ−1>0\mu:=1/\lambda-1>0, which we call the signal strength. The Yij(l)Y_{ij}^{(l)} scores depend on the choice of null model (Section 4) and define, for each layer ll, a symmetric n×nn\times n matrix where the diagonal is left unspecified.

Let SkS_k be the family of all subsets of kk accounts. Under H1H_1, the coordinating group S⋆S^\star is drawn uniformly from Sk\mathcal{S}_k. Assuming independence across pairs under H0H_0 and conditional independence given S⋆S^\star under H1H_1, the off-diagonal entries follow for i<ji<j:

H0:Yij(l)∼Exp⁡(1)−1,H1:Yij(l)∼{Exp⁡(λ)−1,i,j∈S⋆,Exp⁡(1)−1,otherwise.\begin{aligned} H_0 &: \quad Y_{ij}^{(l)}\sim\operatorname{Exp}(1)-1,\\ H_1 &: \quad Y_{ij}^{(l)}\sim \begin{cases} \operatorname{Exp}(\lambda)-1, & i,j\in S^\star,\\ \operatorname{Exp}(1)-1, & \text{otherwise}. \end{cases} \end{aligned}

Our formulation is a variant of the well-studied planted-submatrix problem, for which regimes of statistical impossibility, computational hardness, and polynomial-time detection have been characterised asymptotically. To derive the corresponding detection boundaries for our setting, we must account for two differences from existing formulations. First, our matrix is symmetric, with (n2)\binom{n}{2} independent entries and (k2)\binom{k}{2} independent entries in the planted block. The formulations of Butucea and Ingster [2013] and Ma and Wu [2015] allow different sets of planted rows and columns, while Brennan et al. [2019] consider a single set, as we do, but treat all k2k^2 entries as independent. In contrast, our score matrix is symmetric, with an unspecified diagonal, and therefore has only (n2)\binom{n}{2} independent entries, of which (k2)\binom{k}{2} belong to the planted block.

The computational lower bound of Brennan et al. [2019] transfers to our problem by a reduction. Given an instance WW of their problem, we construct YY by setting Yij(l)=Yji(l)=WijY_{ij}^{(l)}=Y_{ji}^{(l)}=W_{ij} for i<ji<j. This polynomial-time reduction preserves the distribution under both hypotheses. Thus, a polynomial-time test for our problem would

also solve theirs, contradicting the lower bound under the planted clique hypothesis. The reduction transfers the lower bound to our problem, but it does not establish its tightness: the reduction discards k(k+1)/2k(k+1)/2 entries of their block on and below the diagonal. We obtain computational achievability thresholds from the sum and spectral tests, and derive the information-theoretic boundary for our symmetric model in Section 3.3. Second, unlike the classical Gaussian formulations, our entries follow shifted exponential distributions. We derive the upper bounds from the moment generating function of YY and the information-theoretic lower bound from the second moment of the likelihood ratio (Appendix A).

Detection boundaries

Next we derive sufficient conditions for detecting the presence of a planted block, using exhaustive search and polynomial-time methods, as functions of the signal strength μ\mu, the total number of accounts nn, and the block size kk.

Exhaustive search. The test searches over all possible blocks of size kk and rejects H0H_0 when

Tscan(l)=max⁡S∈Sk∑i<j∈SYij(l)T_{\mathrm{scan}}^{(l)}=\max_{S\in\mathcal{S}_k}\sum_{i<j\in S}Y_{ij}^{(l)}

exceeds a critical value cc, chosen so that the probability of a false detection P0(Tscan>c)→0\mathbb{P}_0(T_{\mathrm{scan}}>c)\to0 as n→∞n\to\infty. We obtain the critical value from a Chernoff bound and a union bound over Sk\mathcal{S}_k as c=(1+ε)k(k2)log⁡(n/k)c=(1+\varepsilon)k\sqrt{\binom{k}{2}}\log(n/k) for any fixed ε>0\varepsilon>0 (Appendix A.2). Under H1H_1, the true coordinating group has expected total score (k2)μ\binom{k}{2}\mu, so the scan detects the block for n→∞n\to\infty when μ>μscan=2log⁡(n/k)/(k−1)\mu>\mu_{\mathrm{scan}}=2\sqrt{\log(n/k)/(k-1)}, as for Gaussian entries [15].

Information-theoretic boundary. The total error probability of a test is the sum of the probabilities of a false positive under H0H_0 and of a missed detection under H1H_1. Below the information-theoretic boundary, no test can tell H1H_1 from H0H_0 with total error probability below a fixed positive level, regardless of the computational cost [15, 16, 18]. Following the second-moment method [15] (Ingster and Suslina 2012; Addario-Berry et al. 2010; Arias-Castro et al. 2011; Arias-Castro and Verzelen 2014), we bound the total error probability from below through the second moment E0[L2]\mathbb{E}_0[L^2] of the likelihood ratio LL of H1H_1 against H0H_0: if E0[L2]≤γ\mathbb{E}_0[L^2]\le\gamma for a constant γ>1\gamma>1, every test has a total error probability of at least 1−12γ−11-\frac{1}{2}\sqrt{\gamma-1} [Tsybakov and Zaiats, 2009]. The boundary therefore depends on the error level that one requires, through γ\gamma. We take γ=e\gamma=e because with this value the information-theoretic boundary for large groups equals the sum boundary μsum\mu_{\mathrm{sum}} derived below. With this choice, every test has a total error probability of at least 0.340.34 below the signal μIT\mu_{\mathrm{IT}} at which E0[L2]=e\mathbb{E}_0[L^2]=e, which is, to leading order (Appendix A.4),

μIT=min⁡{2log⁡(n/k)k−1,2nk2}.(2)\mu_{\mathrm{IT}}=\min\left\{\sqrt{\frac{2\log(n/k)}{k-1}},\frac{\sqrt{2}n}{k^2}\right\}. \tag*{(2)}

Another γ\gamma changes the large-group term 2n/k2\sqrt{2}n/k^2 of Equation (2) to 2log⁡γ n/k2\sqrt{2\log\gamma}\,n/k^2, while the small-group term 2log⁡(n/k)/(k−1)\sqrt{2\log(n/k)/(k-1)} does not depend on γ\gamma (Appendix A.4). For small groups, μIT\mu_{\mathrm{IT}} is a factor 2\sqrt{2} below the scan boundary μscan\mu_{\mathrm{scan}}; for μ\mu between the two, it is not known whether any test detects the block (Appendix A.4).

Computational boundary. The computational boundary is the signal strength above which a polynomial-time test detects the block and below which no polynomial-time test does [16, 18] (Hajek et al. 2015). As in [16] and [18], we bound it from above with polynomial-time tests. The sum test Tsum(l)=∑i<jYij(l)T_{\mathrm{sum}}^{(l)}=\sum_{i<j}Y_{ij}^{(l)} rejects H0H_0 when the sum of all scores is large [15] (Arias-Castro and Verzelen 2014). Under H0H_0, Tsum(l)T_{\mathrm{sum}}^{(l)} has mean 00 and standard deviation (n2)\sqrt{\binom{n}{2}}; under H1H_1, its mean is (k2)μ\binom{k}{2}\mu, and near the boundary its standard deviation remains close to (n2)\sqrt{\binom{n}{2}} (Appendix A.5). As in [15], we divide Tsum(l)T_{\mathrm{sum}}^{(l)} by its standard deviation under H0H_0. The normalised sum has expected value 00 under H0H_0 and δ=(k2)μ/(n2)\delta=\binom{k}{2}\mu/\sqrt{\binom{n}{2}} under H1H_1. For Gaussian entries, the total error of the sum test tends to 00 when δ→∞\delta\to\infty, and the boundary lies where δ\delta is approximately one [15]. Following [15], the sum boundary is the signal strength at which δ=1\delta=1 (Appendix A.5):

μsum=2n(n−1)k(k−1).\mu_{\mathrm{sum}}=\frac{\sqrt{2n(n-1)}}{k(k-1)}.

The spectral test uses the largest eigenvalue of the score matrix. Under H1H_1, the block adds to YY a matrix with entry μ\mu on the pairs of the block, whose largest eigenvalue is μ(k−1)\mu(k-1); if this eigenvalue is large enough, it raises the largest eigenvalue of YY above its value under H0H_0. As in [Montanari et al., 2015], the test rejects H0H_0 when the largest eigenvalue of Y/nY/\sqrt{n} exceeds 2+ϵ2+\epsilon with ϵ>0\epsilon>0, and it detects the block if and only if μ>μspec=n/(k−1)\mu>\mu_{\mathrm{spec}}=\sqrt{n}/(k-1) [Montanari et al., 2015, Knowles and Yin, 2013] (Appendix A.6).

Since each test detects the block above its own boundary, a polynomial-time test boundary is

μ>μcomp=min⁡(μspec,μsum).\mu>\mu_{\mathrm{comp}}=\min(\mu_{\mathrm{spec}},\mu_{\mathrm{sum}}).

The sum test gives the minimum when k>2(n−1)k>\sqrt{2(n-1)}, and the spectral test otherwise. For k≥nk\ge\sqrt{n}, no polynomial-time test detects the block under the planted clique hypothesis when k4KL⁡(P∥Q)/n2→0k^4\operatorname{KL}(P\|Q)/n^2\to0 [18], where KL⁡(P∥Q)\operatorname{KL}(P\|Q) is the Kullback–Leibler divergence of the distribution PP of a block entry from the distribution QQ of a null entry. For our scores, KL⁡(P∥Q)=μ2/2(1+O(μ))\operatorname{KL}(P\|Q)=\mu^2/2(1+O(\mu)), so the condition is μ=O(μsum)\mu=O(\mu_{\mathrm{sum}}) (Appendix A.7). For k<nk<\sqrt{n}, the lower bound of [18] applies to our scores only for μ\mu of order at most 1/log⁡n1/\log n, far below μcomp\mu_{\mathrm{comp}} (Appendix A.7). For μ\mu between these two values, the bounds do not determine whether a polynomial-time test detects the block.

Regimes. Detection is impossible if μ<μIT\mu<\mu_{\mathrm{IT}}, hard if μIT≤μ<μcomp\mu_{\mathrm{IT}}\le\mu<\mu_{\mathrm{comp}}, and easy if μ≥μcomp\mu\ge\mu_{\mathrm{comp}}. For k<nk<\sqrt{n}, hard thus means that neither the sum test nor the spectral test detects the block. With k=nβk=n^\beta and μ2=n−α\mu^2=n^{-\alpha}, the three boundaries are, to leading order, the lines α=β\alpha=\beta (scan and small-group information-theoretic boundary), α=2β−1\alpha=2\beta-1 (spectral), and α=4β−2\alpha=4\beta-2 (sum and large-group information-theoretic boundary). Up to terms that vanish for n→∞n\to\infty, these are the coordinates of Brennan et al. [2019]. The lines α=β\alpha=\beta and α=4β−2\alpha=4\beta-2 meet at β=2/3\beta=2/3: for larger groups the information-theoretic boundary equals the sum boundary, so detection is easy.

Untested pairs. When two accounts do not co-act, their pair has no pp-value. We give such pairs the score 00 under both hypotheses, so the signal strength can still be computed as the mean score over all pairs of the group, tested or not. The boundaries above assume that every pair is tested. With untested entries, the sum of all scores keeps its mean (k2)μ\binom{k}{2}\mu under H1H_1 and has a smaller variance under both hypotheses, so the sum test detects the block at a smaller μ\mu than μsum\mu_{\mathrm{sum}}; the same holds for the spectral test when the untested pairs are spread uniformly. The sum and spectral boundaries of a matrix with untested entries are therefore at most the values for a complete matrix. A layer in which μ^≥μcomp\hat{\mu}\ge\mu_{\mathrm{comp}} is easy, but a layer in which μ^\hat{\mu} is below μIT\mu_{\mathrm{IT}} or μcomp\mu_{\mathrm{comp}} may still lie above the corresponding boundary of its matrix with untested entries, so its regime, impossible or hard, is an approximation.

Other distributions for the alternative hypothesis H1H_1. The assumption P=Beta⁡(λ,1)P=\operatorname{Beta}(\lambda,1) can be relaxed to any continuous distribution PP on (0,1)(0,1). The scan, sum, and spectral tests detect the block when μ=EP[Yij(l)]\mu=\mathbb{E}_P[Y_{ij}^{(l)}] exceeds their boundaries, for any continuous PP under which the variance of Yij(l)Y_{ij}^{(l)} stays bounded. The scan rejects H0H_0 when the largest sum of scores over a set of kk accounts exceeds its critical value, and the sum test when the sum of all scores exceeds its critical value. Both critical values are computed from the null distribution Exp⁡(1)−1\operatorname{Exp}(1)-1 of the scores, so they do not depend on PP. Under H1H_1, the sum over the block has mean (k2)μ\binom{k}{2}\mu and variance (k2)Var⁡P(Yij(l))\binom{k}{2}\operatorname{Var}_P(Y_{ij}^{(l)}), and the central limit theorem these two numbers determine its distribution when kk is large. The spectral test uses the largest eigenvalue of the n×nn\times n score matrix YY, which we can write as Y=E[Y]+(Y−E[Y])Y=\mathbb{E}[Y]+(Y-\mathbb{E}[Y]). The expected matrix E[Y]\mathbb{E}[Y] has μ\mu for every pair in the block and 00 elsewhere, and its largest eigenvalue is μ(k−1)\mu(k-1). The entries of Y−E[Y]Y-\mathbb{E}[Y] outside the block have mean 00 and variance 11, and the largest eigenvalue of such a matrix is close to 2n2\sqrt{n} [Bai and Yin, 1988]. When μ(k−1)>n\mu(k-1)>\sqrt{n}, the largest eigenvalue of Y\mathbf{Y} is close to μ(k−1)+n/(μ(k−1))\mu(k-1)+n/(\mu(k-1)), which exceeds the edge of the spectrum [Féral and Péché, 2007]. The distribution PP only affects the (k2)\binom{k}{2} block entries of Y−E[Y]\mathbf{Y}-\mathbb{E}[\mathbf{Y}]. If PP has a finite fourth moment, the derivation is similar to Appendix § 6.6, and, when k/n→0k/n\to0, the largest eigenvalue of Y/n\mathbf{Y}/\sqrt{n} has the same limits as in Appendix § 6.6.

The information-theoretic boundary follows from the second moment of the likelihood ratio under independence of pp-values, and depends on PP through χ2(P∥Q)=∫01fP2−1\chi^2(P\mathbin\Vert Q)=\int_0^1 f_P^2-1, where fPf_P is the density of PP. The computational boundary assumes the planted clique hypothesis and requires conditions on PP, so it depends on PP through the Kullback–Leibler divergence. Two distributions with the same μ\mu can have different χ2(P∥Q)\chi^2(P\mathbin\Vert Q), and μ\mu gives only the bound χ2(P∥Q)≥μ\sqrt{\chi^2(P\mathbin\Vert Q)}\geq\mu. Hence a layer with μ^≥μcomp\hat{\mu}\geq\mu_{\mathrm{comp}} is easy for any PP. A layer with μ^\hat{\mu} below the information-theoretic boundary or below μcomp\mu_{\mathrm{comp}} is impossible or hard only if χ2(P∥Q)\sqrt{\chi^2(P\mathbin\Vert Q)} and dSKL\sqrt{d_{\mathrm{SKL}}} are close to μ\mu; otherwise a test that uses PP can detect the block.

Several modalities. A group that coordinates in MM modalities forms a block in each of MM layers. Assume the simplest case where the MM layers carry the same signal μ\mu, their scores are independent, and every pair is tested in all MM layers. Then, the summed score ∑l=1MYij(l)\sum_{l=1}^{M}Y_{ij}^{(l)} has null mean 00 and null variance MM, and its block entries have mean MμM\mu. By dividing by M\sqrt{M}, the summed score has null variance 11 and the mean of the block becomes Mμ\sqrt{M}\mu. This division does not change the decision of any test. The summed matrix therefore behaves as one layer with signal Mμ\sqrt{M}\mu, and every boundary is multiplied by 1/M1/\sqrt{M}: a coordinating group whose signal is below the information-theoretic boundary in each modality can be detectable when the signal is aggregated over many modalities. The null distribution of the summed score is a shifted Gamma distribution with shape parameter MM, so the factor M\sqrt{M} is exact for the sum and spectral boundaries and holds to leading order for the scan boundary and the information-theoretic boundary. A simulation of the scan with n=30n=30, k∈{3,4,5}k\in\{3,4,5\}, and M≤256M\leq256 is consistent with this result: the signal at which the scan has power 0.50.5 at level 0.050.05 has a fitted slope against MM on a log–log scale between −0.54-0.54 and −0.52-0.52 for M≥16M\geq16, closest to the limit −1/2-1/2 for the largest kk.

Signal Estimation and Group Detection

The layer graph of an operation and modality under one null model has as nodes the nln_l accounts that co-act with at least one other account. Let kk be the number of labelled accounts of the operation, and SlS_l be the set of klk_l labelled accounts in the layer; kl≤kk_l\leq k, since a member that does not co-act in the modality is not in the layer. We estimate the signal strength μ\mu of the block by the mean score of the labelled pairs of the layer, treating SlS_l as the planted set S∗S^*,

μ^=(kl2)−1∑i<j∈SlYij(l),(3)\hat{\mu}=\binom{k_l}{2}^{-1}\sum_{i<j\in S_l}Y_{ij}^{(l)}, \tag*{(3)}

where an untested pair contributes 00. A layer with μ^≤0\hat{\mu}\leq0 has no measurable signal, because its labelled pairs score no higher on average than independent pairs; we report it as no signal. The control mean of a layer is computed like μ^\hat{\mu} over the pairs of control accounts, and is 00 under a correctly specified null model.

We cap the Yij(l)Y_{ij}^{(l)} scores at 2020, because the far tail of an estimated null model is not validated and a few extreme pairs would otherwise determine μ^\hat{\mu}. The cap is above the largest score among null pairs: the largest layer has 9.0×1079.0\times10^7 tested pairs, and the expected number of null pairs above the cap is 9.0×107e−21<0.079.0\times10^7e^{-21}<0.07. One shared item gives a score of at most log⁡(B+1)−1=3.62\log(B+1)-1=3.62, so a pair reaches the cap only if it shares at least nine items. The cap affects between 0.004%0.004\% to 1.6%1.6\% of the tested pairs of a layer.

Recovery heuristics. The scan over all (nk)\binom{n}{k} sets is computationally infeasible for most data sets, so we define two greedy heuristics. Size-agnostic peeling repeatedly removes the node whose removal most increases the mean score of the remaining set, and returns the set of at least 55 accounts that maximises the density ρ(S)=∑i<j∈SYij(l)/∣S∣\rho(S)=\sum_{i<j\in S}Y_{ij}^{(l)}/|S|. The fixed-size heuristic is given the size kl≤kk_l\leq k of the block in the layer, seeds a set of klk_l nodes from the peeling order, and improves ρ(S)\rho(S) by single swaps (at most 200 iterations), keeping the best of 3 restarts. A permutation test compares the density ρ\rho of the returned set with the densities of the sets that the same heuristic returns after the edge weights are shuffled (100 replicates). The returned set SS beats chance if a random set of ∣S∣|S| nodes contains at least as many labelled nodes with probability below 0.050.05 (hypergeometric test). We also report the F1F_1 score of SS against the labelled nodes, and the signal μ^(S)\hat{\mu}(S) of the returned set, computed as in Equation (3) with SS in place of SlS_l. For the spectral method, we compute the eigenvector of the largest eigenvalue ν1\nu_1 of the score matrix of the layer, choose its sign as the sign whose klk_l largest entries have the larger total score, and return the klk_l accounts with the largest entries. A permutation test compares ν1\nu_1 with its values after the edge weights are shuffled (100 replicates).

Results

The predicted regime of the 26 labelled information operations depends strongly on the chosen null model (Figure 2, Table 2). The item-virality null model places the fewest layers in the easy regime (36%), followed by the account-activity null model (54%), the uniform-account null model (81%) and the uniform-modality null model (84%; Table 1). These differences stem from the fact that the null models differ in which timing patterns they attribute to chance. The item-virality null model redraws the action times from the adoption curve of the item. Because the data contain only a sample of control accounts, many of the post and URL items have exactly two adopters, and on such an item the item-virality null model gives p=1p=1 when each account acts once. As a result, this null model measures no signal in 50% of layers, and the pp-values of the labelled pairs follow Beta(λ\lambda, 1) with a median λ\lambda of 0.98, close to the uniform distribution. The account-activity null model keeps the hourly profile of each account, but it does not reproduce the independent reactions of different accounts to a new popular item, so the control mean is slightly positive in all 71 reply (post), repost (post), and URL layers. The uniform null models keep only the period in which a modality or an account is active. They measure the strongest signal for the information operations (see Table 2 and Figure 2b). However, their control mean is positive in almost all layers, and the pp-values of the control pairs are further from uniform than under the account-activity null model (see Figure 2c, median λ\lambda of 0.37 and 0.36, against 0.74). That is, the choice of a null model is a compromise between distinguishing the coordinated group and the control group: a null model that attributes more timing patterns to chance follows better the uniform pp-value distribution for control accounts, but also absorbs the coordination itself, while one that attributes fewer patterns leaves organic synchrony in the scores but separates the coordinated pairs more strongly.

Figure 2. (a) Phase diagrams under the four null models (uniform-modality, uniform-account, account-activity, item-virality). Each point is a graph layer, coloured by the F1F_1 of the set returned by the spectral method. (b, c) Beta distributions fitted by maximum likelihood to the pp-values under each null model. (b) Density of λ\lambda estimates for Beta(λ\lambda, 1) fitted to the pairs labelled as coordinated. (c) Density of (λ,b)(\lambda,b) estimates of Beta(λ,b\lambda,b) fitted to pp-values between control pairs or mixed pairs, as contours at 5%, 35%, and 70% of its maximum; the + marker shows the uniform distribution, expected under a calibrated null model.

regimelayersbeats chance agn.beats chance fix.beats chance spec.median F1F_1 agn.median F1F_1 fix.median F1F_1 spec.test rejects agn.test rejects spec.
uniform-modality null model
impossible60000.000.000.0066
hard2546100.000.000.032224
easy1681231261230.340.590.62153156
no signal0––––––––
uniform-account null model
impossible101300.000.000.001010
hard261011120.010.030.022425
easy1621321391340.350.670.66157156
no signal10000.010.010.0011
account-activity null model
impossible511515180.000.000.004746
hard248770.010.000.002121
easy1078289760.260.590.56105105
no signal17710100.080.220.171716
item-virality null model
impossible143240.000.000.001414
hard136480.010.000.041313
easy724238390.170.280.357272
no signal1003327400.030.120.238587

Table 1. Recovery by predicted regime: layers in which the returned set beats chance, median F1F_1 against the klk_l labelled accounts in the layer, and layers in which the permutation test rejects (p≤0.05p \le0.05; for the spectral method, the test on ν1\nu_1). agn.: size-agnostic; fix.: fixed-size; spec.: spectral.

layercontrol mean μ^\hat{\mu}, median [range] accountcontrol mean μ^\hat{\mu}, median [range] itemcontrol mean μ^\hat{\mu}, median [range] unif.control mean μ^\hat{\mu}, median [range] modalitycoordination μ^\hat{\mu}, mean [range] accountcoordination μ^\hat{\mu}, mean [range] itemcoordination μ^\hat{\mu}, mean [range] unif.coordination μ^\hat{\mu}, mean [range] account
pooled0.012 [0.005, 0.076]0.006 [−0.031-0.031, 0.16]0.215 [0.061, 1.48]0.114 [0.040, 0.56]1.13 [0.046, 3.56]1.10 [−0.41-0.41, 5.67]5.78 [0.93, 15.09]4.04 [0.48, 11.78]
mentions0.001 [−0.003-0.003, 0.014]−0.001-0.001 [−0.022-0.022, 0.12]0.098 [0.010, 1.27]0.032 [0.003, 0.44]0.56 [−0.047-0.047, 7.34]0.54 [−0.53-0.53, 4.09]4.04 [0.53, 15.03]2.71 [0.25, 14.75]
hashtags0.011 [0.004, 0.037]0.001 [−0.029-0.029, 0.17]0.167 [0.041, 0.50]0.075 [0.018, 0.27]0.65 [−0.012-0.012, 3.08]1.23 [−0.55-0.55, 7.57]4.79 [0.52, 14.38]3.34 [−0.15-0.15, 11.10]
reply (acct)0.000 [−0.005-0.005, 0.004]−0.002-0.002 [−0.027-0.027, −0.0001-0.0001]0.008 [0.003, 0.089]0.002 [−0.018-0.018, 0.025]0.062 [−0.075-0.075, 0.55]−0.012-0.012 [−0.56-0.56, 0.56]1.64 [0.22, 6.02]0.99 [0.091, 2.95]
reply (post)0.016 [0.004, 0.28]−0.009-0.009 [−0.14-0.14, −0.001-0.001]0.058 [0.012, 0.52]0.024 [0.006, 0.41]0.44 [0.009, 2.30]−0.095-0.095 [−0.24-0.24, −0.004-0.004]1.17 [0.019, 3.80]1.07 [0.019, 3.72]
repost (acct)0.001 [−0.006-0.006, 0.014]−0.001-0.001 [−0.029-0.029, 0.046]0.052 [0.006, 0.76]0.018 [0.002, 0.25]0.48 [−0.098-0.098, 6.56]0.29 [−0.42-0.42, 2.95]3.43 [0.17, 13.83]2.41 [0.091, 12.43]
repost (post)0.005 [0.0005, 0.062]−0.002-0.002 [−0.052-0.052, −0.0002-0.0002]0.015 [0.002, 0.18]0.009 [0.0009, 0.12]1.61 [0.043, 7.38]−0.15-0.15 [−0.91-0.91, 0.19]3.55 [0.16, 14.61]3.43 [0.15, 14.60]
URLs0.005 [0.0004, 0.13]−0.002-0.002 [−0.14-0.14, −0.0003-0.0003]0.021 [0.002, 0.52]0.010 [0.0009, 0.23]0.85 [0.032, 3.63]−0.072-0.072 [−0.63-0.63, 0.47]2.43 [0.18, 9.77]2.17 [0.16, 9.49]
all layers0.005 [−0.006-0.006, 0.28]−0.002-0.002 [−0.14-0.14, 0.17]0.055 [0.002, 1.48]0.021 [−0.018-0.018, 0.56]0.73 [−0.098-0.098, 7.38]0.37 [−0.91-0.91, 7.57]3.43 [0.019, 15.09]2.57 [−0.15-0.15, 14.75]

Table 2. Control mean μ^\hat{\mu} (median and range over the operations) and coordination μ^\hat{\mu} of the labelled pairs (mean and range over the operations) by modality under each null model. The control mean is 0 under a correctly specified null model.

Recovery of the ground-truth groups using the spectral method exceeds that of all 20 methods that Iannucci et al. [ [22] evaluate on the same 26 operations (Figure 3). As in their evaluation, we compute F1F_1 against all labelled accounts of the operation. Both evaluations use the ground truth beyond the final score: the spectral method is given the size klk_l of the labelled group in the layer, and F1∗F_1^* [22] is the F1F_1 of the cluster that best matches the labelled accounts. When each layer and null model is considered separately, the spectral method exceeds all 20 methods in 10 of the 28 single-modality combinations. The highest median F1F_1 is 0.62 for reposts of a post under the uniform-account null model, compared to 0.39 for synchronised hashtags [10] and 0.34 for time-aware (RT) [22], which uses the same modality. Some of the layers carry poor signal over the operations, but even when evaluated over all operations and single-modality layers, the spectral method reaches a median F1F_1 of 0.40 under the uniform-account null model, against 0.36, 0.24, and 0.18 under the uniform-modality, account-activity, and item-virality null models, and against 0.39, the highest reported median F1F_1 [Iannucci et al., 2022], achieved by synchronised hashtags. On the layers that the theory places in the easy regime, the spectral method exceeds all of the previous methods [22] under every null model, with a median F1F_1 of 0.45, 0.48, 0.46, and 0.39 under the uniform-modality, uniform-account, account-activity, and item-virality null models, and a median recall of 0.34 to 0.38; on the hard and impossible layers, the median F1F_1 is at most 0.04.

Figure 3. F1F_1 of the spectral method for each null model and layer that scores higher than the top 3 methods [22].

Under all four null models, combining modalities moves operations toward the easy regime, but with less than the factor 1/M1/\sqrt{M} derived in § 3.3. We combine the modalities in two ways. The summed layer adds the scores of a pair over the M=7M = 7 modalities, and is placed on the phase diagram at μ^Σ/M\hat{\mu}_{\Sigma}/\sqrt{M}. The pooled layer combines the pp-values of a pair across all modalities by Fisher’s method, so, under our assumptions, every tested pair has expectation 0 and variance 1 under H0H_0, independently of the number of layers. Since Fisher’s statistic −2∑log⁡p-2\sum\log p equals, up to a constant, the sum of the scores, the two layers differ only in how the sum is standardised. Under the account-activity, item-virality, uniform-modality, and uniform-account null models, the pooled layer is easy in 18, 18, 23, and 22 of the 26 operations, and the summed layer in 17, 14, 22, and 22, in both cases more often than the single-modality layers. The regime of the pooled layer also depends less on the null model: the four null models agree on 65% of operations, against 22% of the single-modality layers. However, the boundaries move less than the factor 1/M1/\sqrt{M} for two reasons. First, our derivation requires every pair to be tested in all MM layers, while a pair is tested in a mean of 1.34 layers (median over the

operations; range 1.04 to 2.0). Second, our derivation assumes one block with the same signal in every layer, while, in practice, we observe that each modality involves a different subset of the operation. Thus, a combined layer averages the signal of the strongest modality with that of the others. Under no null model is an operation easy on the pooled layer without being easy in some single modality. Recovery is lower on the combined layers: the median F1F_1 of the fixed-size heuristic is 0.03, 0.19, 0.12, and 0.02 on the pooled layer and 0.18, 0.39, 0.29, and 0.02 on the summed layer, against 0.60, 0.69, 0.64, and 0.37 on the easy single-modality layers (uniform-modality, uniform-account, account-activity, and item-virality null models), although a combined layer is scored against nearly the whole operation in a larger population.

Under all four null models, the heuristics find a set denser than chance in almost every layer, whether or not this set is the operation (Table 1). Even on layers where the found set does not beat chance recovery, the found set is still denser than chance in the vast majority of cases. The sets found by the size-agnostic heuristic, fixed-size heuristic, and spectral method are also denser than the operation in most layers. The pooled layer falls under the easy regime in most operations under every null model, but the spectral set has a median precision of 0.06, 0.22, 0.10, and 0.04, and a signal 1.9, 1.5, 1.5, and 3.8 times that of the labelled pairs. The scores therefore contain dense groups of mostly control accounts, which the model of one block in independent scores excludes. A significant permutation test only shows that a layer contains a dense set, but does not guarantee that the dense set represents the information operation.

Conclusion

We treat coordination detection as hypothesis testing across all accounts, reducing the task to detecting a planted block within a matrix of scores. Our derived boundaries establish the signal thresholds below which detection, and therefore recovery, is impossible, and above which polynomial-time tests detect the block. Our derivation shows how combining scores across multiple modalities lowers the statistical and computational boundaries. We demonstrate that algorithmic recovery is bounded by the chosen null model, through the timing patterns that it attributes to chance and the signal that it can measure. Across 26 labelled information operations, null models that attribute fewer patterns to chance are less calibrated, but they separate coordinated from organic pairs more strongly. Consequently, under these models, a spectral method recovers the operations better, by median F1F_1, than previously proposed coordination detection methods (Figure 3).

The dependence on the null model reveals two criticalities that affect the current study on coordination detection. First, permutation tests find a significantly dense set across nearly all layers, so the existence of a dense cluster in a coordination network is not evidence of coordination. Second, the simplest null models, that keep only the active period and attribute every timing pattern to synchrony, recover the coordinated groups best. Such null models separate the labelled accounts from the control accounts only based on their timing, which points to a sampling artefact in benchmark datasets: the accounts of these operations are not hiding in the timing patterns of organic accounts. This can reflect detection bias of the platform itself, so that information operations accounts that hide better are absent from the ground truth, or the collection of the data. The control accounts were sampled by the hashtags and dates of each operation, with at most 100 posts on those dates [23], and the uniform-account null model spreads the actions of an account over its own active period, so the same co-action is far more extreme for two accounts of the operation than for two control accounts. This calls for additional benchmark datasets, so that coordination detection frameworks can be evaluated against realistic conditions and more varied strategies and patterns of coordination.

Limitations. Our approach focuses on temporal synchronisation conditional on accounts interacting with the same items, rather than coordination expressed through unusual co-adoption. The null models account separately for individual activity patterns, item virality, or only the active period, but none controls for both activity patterns and item virality simultaneously. A joint null model could address this limitation, although it would require additional modelling assumptions and risk absorbing genuine coordination into the estimated baseline. Conversely, considering each null model separately allows us to examine how different sources of chance synchronisation affect the conclusions. Exploring joint null models through stratified or weighted randomisation is a direction for future work.

Our theoretical formulation and empirical evaluation rely on simplifying assumptions. First, on a statistical level, we assume independent pp-values, whereas pairs that share an account are correlated. Furthermore, because Monte Carlo pp-values are discrete and only approximately uniform under the null model, they yield slight biases and cause score means and variances to be 0 and 1 only approximately. However, because real-world detection lacks labels, the deviation from calibration cannot simply be solved by empirical null distributions. Instead, this calls for further research on null models that accurately capture organic timing without absorbing the coordination signal itself. Second, our derivation relies on the planted submatrix problem, assuming a single, homogenous block of coordinated accounts within a fully tested matrix. Because real-world information operations may be complex and consist of multiple sub-groups, future research could extend the derivation of phase boundaries to nested block structures. Similarly, the multi-modal gain assumes a uniform group producing equal signal in all modalities. Deriving the signal gain for coordination that alternates across modalities, or modalities with unequal signal, is left for future work. Finally, since the greedy heuristics and the spectral method are empirical approximations of the exhaustive scan and polynomial-time tests used in the theoretical derivation, their failure in the easy regime reflects either algorithmic limitations or, where μsum≤μ^<μspec\mu_{\mathrm{sum}} \le\hat{\mu} < \mu_{\mathrm{spec}}, the gap between detection and recovery (§ 3.3). Since the densest subgraph problem with negative edge weights is NP-hard [Tsourakakis et al., 2019], and our scores take negative values, good heuristics for weighted signed multiplex networks are essential to bridge theoretical detectability and empirical detection.

Derivation of the boundaries

Assumptions

The derivations use the model of § 3.2 for one layer, under these assumptions:

(A1) the scores YijY_{ij}, i<ji<j, are independent;

(A2) under H0H_0, every pijp_{ij} has the uniform distribution QQ;

(A3) under H1H_1, S∗S^* is uniform on Sk\mathcal{S}_k with pij∼P=Beta⁡(λ,1)p_{ij}\sim P=\operatorname{Beta}(\lambda,1) for i,j∈S∗i,j\in S^*, and pij∼Qp_{ij}\sim Q otherwise;

(A4) kk is known; (A5) every pair is tested. In the data, a pair that does not co-act has score 0 under both hypotheses. The diagonal of YY is 0 for the spectral test.

P0\mathbb{P}_0, P1\mathbb{P}_1 and E0\mathbb{E}_0, E1\mathbb{E}_1 denote the distributions of YY and the expectations under H0H_0, H1H_1. Asymptotic statements refer to n→∞n \to\infty with k=nβk=n^\beta and μ2=n−α\mu^2=n^{-\alpha} for fixed 0<β<10<\beta<1 and α\alpha; a formula holds to leading order if the ratio of its two sides tends to 1.

Distribution of the scores

The log-likelihood ratio of Beta⁡(λ,1)\operatorname{Beta}(\lambda,1) against the uniform distribution, evaluated at the observed pij(l)p_{ij}^{(l)}, is

log⁡(ℓ(pij(l)))=log⁡λ+(1−λ)(−log⁡pij(l)).(4)\log\bigl(\ell(p_{ij}^{(l)})\bigr)=\log\lambda+(1-\lambda)(-\log p_{ij}^{(l)}). \tag*{(4)}

The likelihood ratio of a block entry against a null entry is ℓ=dP/dQ\ell=dP/dQ. As a function of the score, ℓ(Yij)=λe(1−λ)(Yij+1)\ell(Y_{ij})=\lambda e^{(1-\lambda)(Y_{ij}+1)}, the exponential of (4).

Since the score is a one-to-one function of the pp-value, ℓ\ell takes the same value whether it is computed from pijp_{ij} or from YijY_{ij}. Every divergence between PP and QQ and every condition in [18] depends on the two distributions only through ℓ\ell, and therefore has the same value for the pp-values and for the scores.

For a set SS with m=(k2)m=\binom{k}{2} pairs and Σ(S)=∑i<j∈SYij\Sigma(S)=\sum_{i<j\in S}Y_{ij}:

H0:Σ(S)+m∼Gamma⁡(m,1),H1:Σ(S⋆)+m∼Gamma⁡(m,λ),(5)\begin{aligned} H_0 &: \Sigma(S)+m\sim\operatorname{Gamma}(m,1),\\ H_1 &: \Sigma(S^\star)+m\sim\operatorname{Gamma}(m,\lambda), \tag*{(5)} \end{aligned}

with mean 0 and variance mm under H0H_0, and mean mμm\mu and variance m(1+μ)2m(1+\mu)^2 under H1H_1.

Scan boundary

Following the scan-statistic analysis of Arias-Castro et al. [2011], Butucea and Ingster [ [15], we use a Chernoff bound and a union bound to derive the sufficient detection condition for the exhaustive scan stated in Section 3.3, adapting the calculation to symmetric matrices with shifted-exponential entries.

A set S∈SkS\in S_k contains m=(k2)m=\binom{k}{2} pairs, and there are ∣Sk∣=(nk)|S_k|=\binom{n}{k} such sets. For a set SS, let Σ(S)=∑i<j∈SYij\Sigma(S)=\sum_{i<j\in S}Y_{ij}, so that Tscan=max⁡S∈SkΣ(S)T_{\mathrm{scan}}=\max_{S\in S_k}\Sigma(S), and let L=log⁡(n/k)L=\log(n/k). As n→∞n\to\infty with k=nβk=n^\beta, 0<β<10<\beta<1, and bounded μ\mu, we have L→∞L\to\infty and L/k→0L/k\to0.

Under H0H_0, Yij+1∼Exp⁡(1)Y_{ij}+1\sim\operatorname{Exp}(1), so for 0≤t<10\le t<1 the logarithm of the moment generating function of a score is

ψ0(t)=log⁡E0[etYij]=−t−log⁡(1−t)=∑r≥2trr.\psi_0(t)=\log\mathbb{E}_0[e^{tY_{ij}}]=-t-\log(1-t)=\sum_{r\ge2}\frac{t^r}{r}.

Since tr/r≤tr/2t^r/r\le t^r/2 for r≥2r\ge2,

ψ0(t)≤t22(1−t),0≤t<1.(6)\psi_0(t)\le\frac{t^2}{2(1-t)},\qquad0\le t<1. \tag*{(6)}

For a fixed set SS, c>0c>0 and 0<t<10<t<1, Markov’s inequality applied to etΣ(S)e^{t\Sigma(S)} and the independence of the mm scores of SS give P0(Σ(S)>c)≤exp⁡(−tc+mψ0(t))\mathbb{P}_0(\Sigma(S)>c)\le\exp(-tc+m\psi_0(t)). The scan exceeds cc only if at least one set does, so a union bound over SkS_k and log⁡(nk)≤kL+k\log\binom{n}{k}\le kL+k give

P0(Tscan>c)≤(nk)exp⁡(−tc+mψ0(t))≤exp⁡(kL+k−tc+mψ0(t)),\begin{aligned} \mathbb{P}_0(T_{\mathrm{scan}}>c)\le\binom{n}{k}\exp\bigl(-tc+m\psi_0(t)\bigr) \\ &\le\exp\bigl(kL+k-tc+m\psi_0(t)\bigr), \end{aligned}

with ψ0(t)=log⁡E0[etYij]=−t−log⁡(1−t)=t2/2+O(t3)\psi_0(t)=\log\mathbb{E}_0[e^{tY_{ij}}]=-t-\log(1-t)=t^2/2+O(t^3).

Let

c⋆=2mkL=k(k−1)L.(7)c^\star=\sqrt{2mkL}=k\sqrt{(k-1)L}. \tag*{(7)}

and take c=(1+ε)c⋆c=(1+\varepsilon)c^\star for a fixed ε>0\varepsilon>0, and t=c/m=2(1+ε)L/(k−1)t=c/m=2(1+\varepsilon)\sqrt{L/(k-1)}, which tends to 0 because L/k→0L/k\to0. By (6), mψ0(t)≤c2/(2m(1−t))m\psi_0(t)\le c^2/(2m(1-t)), and with tc=c2/mtc=c^2/m and c2/(2m)=(1+ε)2kLc^2/(2m)=(1+\varepsilon)^2kL,

−tc+mψ0(t)≤−c22m1−2t1−t=−(1+ε)2kL1−2t1−t.-tc+m\psi_0(t)\le-\frac{c^2}{2m}\frac{1-2t}{1-t}=-(1+\varepsilon)^2kL\frac{1-2t}{1-t}.

Inserted into eq:7, this gives

log⁡P0(Tscan>c)≤−kL[(1+ε)21−2t1−t−1−1L].\log\mathbb{P}_0(T_{\mathrm{scan}}>c)\le-kL\left[(1+\varepsilon)^2\frac{1-2t}{1-t}-1-\frac{1}{L}\right].

As n→∞n\to\infty, the bracket tends to (1+ε)2−1>0(1+\varepsilon)^2-1>0 and kL→∞kL\to\infty, so P0(Tscan>c)→0\mathbb{P}_0(T_{\mathrm{scan}}>c)\to0.

Under H1H_1, the mm scores of S⋆S^\star are independent with Yij+1∼Exp⁡(λ)Y_{ij}+1\sim\operatorname{Exp}(\lambda), λ=1/(1+μ)\lambda=1/(1+\mu), so E1[Σ(S⋆)]=mμ\mathbb{E}_1[\Sigma(S^\star)]=m\mu and Var⁡1(Σ(S⋆))=m(1+μ)2\operatorname{Var}_1(\Sigma(S^\star))=m(1+\mu)^2. The maximum over all sets is at least the sum over the block, Tscan≥Σ(S⋆)T_{\mathrm{scan}}\ge\Sigma(S^\star). If mμ≥(1+2ε)c⋆m\mu\ge(1+2\varepsilon)c^\star, the event {Tscan≤c}\{T_{\mathrm{scan}}\le c\} implies Σ(S⋆)−mμ≤−εc⋆\Sigma(S^\star)-m\mu\le-\varepsilon c^\star, and Chebyshev’s inequality gives

P1(Tscan≤c)≤m(1+μ)2(εc⋆)2=(1+μ)22ε2kL⟶0.\mathbb{P}_1(T_{\mathrm{scan}}\le c)\le\frac{m(1+\mu)^2}{(\varepsilon c^\star)^2}=\frac{(1+\mu)^2}{2\varepsilon^2kL}\longrightarrow0.

The condition mμ≥(1+2ε)c⋆m\mu\ge(1+2\varepsilon)c^\star reads μ≥(1+2ε)μscan\mu\ge(1+2\varepsilon)\mu_{\mathrm{scan}}, with

μscan=c⋆m=2Lk−1=2log⁡(n/k)k−1.(8)\mu_{\mathrm{scan}}=\frac{c^\star}{m}=2\sqrt{\frac{L}{k-1}}=2\sqrt{\frac{\log(n/k)}{k-1}}. \tag*{(8)}

Since ε>0\varepsilon>0 is arbitrary, for every fixed δ>0\delta>0 the scan with critical value (1+δ/2)c⋆(1+\delta/2)c^\star has both error probabilities tending to 0 when μ≥(1+δ)μscan\mu\ge(1+\delta)\mu_{\mathrm{scan}}. This is a sufficient condition: the union bound treats overlapping sets as disjoint, so the exact boundary of the scan may be lower.

Information-theoretic boundary

Following the second-moment approach of [15] (Arias-Castro and Verzelen 2014) and the testing inequalities of [Tsybakov and Zaiats, 2009], we derive the lower bound on total testing error underlying the information-theoretic bound in § 3.3 and examine its dependence on group size and signal strength.

Error bound. A test decides from the score matrix Y\mathbf{Y} whether to reject H0H_0. Let AA be the set of score matrices for which it rejects. The test makes a false positive with probability P0(Y∈A)\mathbb{P}_0(\mathbf{Y} \in A) and misses the block with probability P1(Y∉A)=1−P1(Y∈A)\mathbb{P}_1(\mathbf{Y} \notin A)=1-\mathbb{P}_1(\mathbf{Y} \in A).

Under H1H_1, the coordinating group S⋆S^\star is drawn uniformly from Sk\mathcal{S}_k, so P1\mathbb{P}_1 is the average, over all S∈SkS \in\mathcal{S}_k, of the distribution of Y\mathbf{Y} when S⋆=SS^\star=S. The likelihood ratio L=dP1/dP0L=d\mathbb{P}_1/d\mathbb{P}_0 of H1H_1 against H0H_0 satisfies E0[L]=1\mathbb{E}_0[L]=1. For every test, that is, for every set AA,

P0(Y∈A)+P1(Y∉A)=P0(Y∈A)+1−P1(Y∈A)≥1−∥P1−P0∥TV≥1−12E0[L2]−1.\mathbb{P}_0(\mathbf{Y} \in A)+\mathbb{P}_1(\mathbf{Y} \notin A) =\mathbb{P}_0(\mathbf{Y} \in A)+1-\mathbb{P}_1(\mathbf{Y} \in A) \ge1-\lVert\mathbb{P}_1-\mathbb{P}_0\rVert_{\mathrm{TV}} \ge1-\frac{1}{2}\sqrt{\mathbb{E}_0[L^2]-1}.

The first inequality holds because P1(Y∈A)−P0(Y∈A)≤∥P1−P0∥TV\mathbb{P}_1(\mathbf{Y} \in A)-\mathbb{P}_0(\mathbf{Y} \in A)\le\lVert\mathbb{P}_1-\mathbb{P}_0\rVert_{\mathrm{TV}} for every set AA. The second holds because ∥P1−P0∥TV=12E0∣L−1∣≤12E0[(L−1)2]\lVert\mathbb{P}_1-\mathbb{P}_0\rVert_{\mathrm{TV}}=\frac{1}{2}\mathbb{E}_0|L-1|\le\frac{1}{2}\sqrt{\mathbb{E}_0[(L-1)^2]} by the Cauchy–Schwarz inequality, and E0[(L−1)2]=E0[L2]−1\mathbb{E}_0[(L-1)^2]=\mathbb{E}_0[L^2]-1 [Tsybakov and Zaiats, 2009]. Since P1\mathbb{P}_1 averages over S⋆S^\star, the bound holds for the error averaged over the possible groups, and therefore also for the largest error over all groups, which is at least the average.

Let ℓ=dP/dQ\ell=dP/dQ be the likelihood ratio of a single score of the block against a null score; its logarithm is Equation (4) (Appendix § 6.§ 2). If the group S⋆=SS^\star=S were known, the likelihood ratio of the whole matrix would be ∏i<j∈Sℓ(Yij)\prod_{i<j\in S}\ell(Y_{ij}), since the entries outside SS have the same distribution QQ under both hypotheses. Under H1H_1 the group is uniform on Sk\mathcal{S}_k, so LL is the average of these products:

L=(nk)−1∑S∈Sk∏i<j∈Sℓ(Yij).L=\binom{n}{k}^{-1}\sum_{S\in\mathcal{S}_k}\prod_{i<j\in S}\ell(Y_{ij}).

Second moment. Squaring LL gives a double sum over two groups SS and S′S', which we can read as two independent groups drawn uniformly from Sk\mathcal{S}_k:

E0[L2]=(nk)−2∑S,S′∈SkE0[∏i<j∈Sℓ(Yij)∏i<j∈S′ℓ(Yij)].\mathbb{E}_0[L^2]=\binom{n}{k}^{-2}\sum_{S,S'\in\mathcal{S}_k}\mathbb{E}_0\left[\prod_{i<j\in S}\ell(Y_{ij})\prod_{i<j\in S'}\ell(Y_{ij})\right].

Under H0H_0 the scores are independent, so the expectation is a product over pairs. A pair in neither group contributes 11, and a pair in exactly one group contributes E0[ℓ]=1\mathbb{E}_0[\ell]=1. A pair in both groups has both accounts in S∩S′S\cap S' and contributes

E0[ℓ2]=∫01(λxλ−1)2 dx=λ22λ−1=11−μ2=1+χ2(P∥Q),(9)\mathbb{E}_0[\ell^2]=\int_0^1(\lambda x^{\lambda-1})^2\,dx =\frac{\lambda^2}{2\lambda-1} =\frac{1}{1-\mu^2} =1+\chi^2(P\mathbin\Vert Q), \tag*{(9)}

with λ=1/(1+μ)\lambda=1/(1+\mu). The integral is over the pp-value xx, which is uniform on (0,1)(0,1) under H0H_0. This gives E0[ℓ2]\mathbb{E}_0[\ell^2] because the score is a one-to-one function of the pp-value, so ℓ\ell has the same value whether it is computed from YijY_{ij} or from pijp_{ij} (Appendix § 6.§ 2). The integral is finite only for λ>1/2\lambda>1/2, that is, for μ<1\mu<1. If the two groups share K=∣S∩S′∣K=|S\cap S'| accounts, exactly (K2)\binom{K}{2} pairs are in both groups. For two independent uniform groups, KK has the hypergeometric distribution P(K=j)=(kj)(n−kk−j)/(nk)\mathbb{P}(K=j)=\binom{k}{j}\binom{n-k}{k-j}/\binom{n}{k}. Hence

E0[L2]=E[(1−μ2)−(K2)]=∑j=0k(kj)(n−kk−j)(nk)(1−μ2)−(j2).(10)\mathbb{E}_0[L^2]=\mathbb{E}\left[(1-\mu^2)^{-\binom{K}{2}}\right] =\sum_{j=0}^{k}\frac{\binom{k}{j}\binom{n-k}{k-j}}{\binom{n}{k}}(1-\mu^2)^{-\binom{j}{2}}. \tag*{(10)}

Every term increases with μ\mu. At μ=0\mu=0 the sum equals 11, and as μ→1\mu\to1 it tends to infinity, because of the terms with j≥2j\ge2. So, for every γ>1\gamma>1, there is exactly one μ\mu at which E0[L2]=γ\mathbb{E}_0[L^2]=\gamma. We define μIT\mu_{\mathrm{IT}} by E0[L2]=e\mathbb{E}_0[L^2]=e. For μ<μIT\mu<\mu_{\mathrm{IT}}, the bound above gives a total error probability of at least 1−12e−1=0.341-\frac{1}{2}\sqrt{e-1}=0.34 for every test; this holds at finite (n,k)(n,k) when μIT\mu_{\mathrm{IT}} is computed from Equation (10).

Closed forms. For small groups (k≪nk\ll\sqrt{n}) the overlap KK has mean E[K]=k2/n→0\mathbb{E}[K]=k^2/n\to0. The terms j=0j=0 and j=1j=1 of Equation (10) have the factor (1−μ2)0=1(1-\mu^2)^0=1 and sum to 1+o(1)1+o(1); the terms with small j≥2j\ge2 vanish, and the term that remains is j=kj=k. This term equals (1−μ2)−m/(nk)(1-\mu^2)^{-m}/\binom{n}{k}, with m=(k2)m=\binom{k}{2}, because the two groups coincide (K=kK=k) with probability 1/(nk)1/\binom{n}{k} and then share all mm pairs. It is of order 11 when m(−log⁡(1−μ2))=log⁡(nk)+O(1)m(-\log(1-\mu^2))=\log\binom{n}{k}+O(1). As μ→0\mu\to0, −log⁡(1−μ2)=μ2(1+o(1))-\log(1-\mu^2)=\mu^2(1+o(1)), and log⁡(nk)=klog⁡(n/k)(1+o(1))\log\binom{n}{k}=k\log(n/k)(1+o(1)) because klog⁡(n/k)≤log⁡(nk)≤klog⁡(n/k)+kk\log(n/k)\le\log\binom{n}{k}\le k\log(n/k)+k. The condition becomes mμ2=klog⁡(n/k)(1+o(1))m\mu^2=k\log(n/k)(1+o(1)), and with m=k(k−1)/2m=k(k-1)/2,

μ=2log⁡(n/k)k−1 (1+o(1)).\mu=\sqrt{\frac{2\log(n/k)}{k-1}}\,(1+o(1)).

The value of γ\gamma changes log⁡(nk)\log\binom{n}{k} only by O(1)O(1), so it does not affect the leading term of μ\mu.

For large groups (k≫nk\gg\sqrt{n}) the overlap KK has mean κ=k2/n→∞\kappa=k^2/n\to\infty and standard deviation at most κ\sqrt{\kappa}, so K/κ→1K/\kappa\to1 and we can replace KK by κ\kappa. The expectation in Equation (10) is E[exp⁡(g(K))]\mathbb{E}[\exp(g(K))], with g(K)=−(K2)log⁡(1−μ2)g(K)=-\binom{K}{2}\log(1-\mu^2). As μ→0\mu\to0, −log⁡(1−μ2)/μ2→1-\log(1-\mu^2)/\mu^2\to1, and as K→∞K\to\infty, (K2)/(K2/2)→1\binom{K}{2}/(K^2/2)\to1; together with K/κ→1K/\kappa\to1, this gives g(K)/(μ2κ2/2)→1g(K)/(\mu^2\kappa^2/2)\to1. So E0[L2]\mathbb{E}_0[L^2] is approximately exp⁡(μ2κ2/2)\exp(\mu^2\kappa^2/2), which equals γ\gamma at μ=2log⁡γ/κ=2log⁡γ n/k2\mu=\sqrt{2\log\gamma}/\kappa=\sqrt{2\log\gamma}\,n/k^2. The approximation holds at this μ\mu since KK differs from κ\kappa by about κ\sqrt{\kappa}, replacing KK by κ\kappa changes gg by about μ2κκ≈1/κ\mu^2\kappa\sqrt{\kappa}\approx1/\sqrt{\kappa}, which tends to 00. For γ=e\gamma=e the value is 2 n/k2\sqrt{2}\,n/k^2, whose ratio to μsum=2n(n−1)/(k(k−1))\mu_{\mathrm{sum}}=\sqrt{2n(n-1)/(k(k-1))} tends to 11.

E0[L2]\mathbb{E}_0[L^2] exceeds ee as soon as either the term j=kj=k or the bulk of the overlap distribution does, so to leading order

μIT=min⁡{2log⁡(n/k)/(k−1),2n/k2}.\mu_{\mathrm{IT}}=\min\left\{\sqrt{2\log(n/k)/(k-1)},\sqrt{2n/k^2}\right\}.

This minimum is an approximation of the exact value of μIT\mu_{\mathrm{IT}}, the numerical solution of E0[L2]=e\mathbb{E}_0[L^2]=e with (10), and the ratio of the two tends to 1 as n→∞n\to\infty. On the 199 layers of Section 4, the exact value is between 0.54 and 1.10 times the closed form (median 0.99); the largest differences occur for groups with fewer than 10 accounts.

Gap to the scan. Where μIT\mu_{\mathrm{IT}} equals its first term, that is, for kk below about n2/3n^{2/3}, μIT\mu_{\mathrm{IT}} is a factor 2\sqrt{2} below μscan\mu_{\mathrm{scan}} (Appendix A.3). The smallest signal at which some test detects the block may lie above μIT\mu_{\mathrm{IT}}, because rare large overlaps KK can inflate E0[L2]\mathbb{E}_0[L^2]. For Gaussian entries, a truncated second moment that removes these overlaps closes the gap to the scan [15]; this has not been done for exponential entries. For μIT≤μ<μscan\mu_{\mathrm{IT}}\leq\mu<\mu_{\mathrm{scan}} it is therefore not proved that any test detects the block, nor that none does.

Sum boundary

Our sum test Tsum(l)T_{\mathrm{sum}}^{(l)} is the linear test of [15], applied to the N=(n2)N=\binom{n}{2} scores above the diagonal. As in [15], we divide Tsum(l)T_{\mathrm{sum}}^{(l)} by its standard deviation under H0H_0. The scores are independent by assumption, so with m=(k2)m=\binom{k}{2}, Equation (5) applied to the block and to the remaining N−mN-m pairs gives

E0[Tsum(l)]=0,Var⁡0(Tsum(l))=N,\mathbb{E}_0[T_{\mathrm{sum}}^{(l)}]=0,\quad\operatorname{Var}_0(T_{\mathrm{sum}}^{(l)})=N,
E1[Tsum(l)]=mμ,Var⁡1(Tsum(l))=N+mμ(2+μ).\mathbb{E}_1[T_{\mathrm{sum}}^{(l)}]=m\mu,\quad\operatorname{Var}_1(T_{\mathrm{sum}}^{(l)})=N+m\mu(2+\mu).

The normalised sum Tsum(l)/NT_{\mathrm{sum}}^{(l)}/\sqrt{N} has mean 0 and variance 1 under H0H_0, and mean δ=mμ/N\delta=m\mu/\sqrt{N} and variance 1+2δ/N+δ2/m1+2\delta/\sqrt{N}+\delta^2/m under H1H_1.

By Chebyshev’s inequality, the test Tsum(l)>zNT_{\mathrm{sum}}^{(l)}>z\sqrt{N} has type I error at most 1/z21/z^2 and, for z<δz<\delta, type II error at most (1+2δ/N+δ2/m)/(δ−z)2(1+2\delta/\sqrt{N}+\delta^2/m)/(\delta-z)^2. For z=δz=\sqrt{\delta}, both bounds tend to 0 when δ→∞\delta\to\infty, as for Gaussian entries [15].

In [15], the boundary of the linear test is where the normalised mean shift is approximately one. Following this, μsum\mu_{\mathrm{sum}} is the signal strength at which δ=1\delta=1:

μsum=Nm=2n(n−1)k(k−1).\mu_{\mathrm{sum}}=\frac{\sqrt{N}}{m}=\frac{\sqrt{2n(n-1)}}{k(k-1)}.

This value also equals the large-group term of μIT\mu_{\mathrm{IT}} with γ=e\gamma=e (Appendix A.4).

For k≥nk\geq\sqrt{n}, the order of μsum\mu_{\mathrm{sum}} is also the computational boundary of [18], which is dSKL≍n2/k4d_{\mathrm{SKL}}\asymp n^2/k^4, up to factors that grow slower than any power of nn. With dSKL=μ2/(1+μ)d_{\mathrm{SKL}}=\mu^2/(1+\mu) (Equation (12)), this is μ≍n/k2\mu\asymp n/k^2 as μ→0\mu\to0. Below this order no polynomial-time test detects the block under the planted clique hypothesis, and above it a polynomial-time test does (Appendix A.7).

Spectral boundary

Following the spectral-edge and matrix-deformation results of Bai and Yin [1988], Knowles and Yin [2013], we derive the spectral detection threshold stated in Section 3.3 and examine the effect of the larger variance of entries within the planted block.

The spectral boundary follows from the largest eigenvalue of a random matrix with a low-rank perturbation [Bai and Yin, 1988, Knowles and Yin, 2013]. Write Y=E[Y]+(Y−E[Y])\mathbf{Y}=\mathbb{E}[\mathbf{Y}]+(\mathbf{Y}-\mathbb{E}[\mathbf{Y}]). Under H1H_1, E[Y]\mathbb{E}[\mathbf{Y}] has the entry μ\mu on the pairs of S⋆S^\star and 0 elsewhere, so its largest eigenvalue is μ(k−1)\mu(k-1). Let θ=μ(k−1)/n\theta=\mu(k-1)/\sqrt{n}. Outside the block, the entries of Y−E[Y]\mathbf{Y}-\mathbb{E}[\mathbf{Y}] are independent, with distribution Exp⁡(1)−1\operatorname{Exp}(1)-1, mean 0 and variance 1 (Appendix A.2). Under H0H_0, the largest eigenvalue of Y/n\mathbf{Y}/\sqrt{n} tends to 2 [Bai and Yin, 1988]. Under H1H_1, it tends to θ+1/θ\theta+1/\theta if θ>1\theta>1 and to 2 if θ≤1\theta\leq1 [Knowles and Yin, 2013]. The test that rejects H0H_0 when the largest eigenvalue of Y/n\mathbf{Y}/\sqrt{n} exceeds 2+ϵ2+\epsilon therefore detects the block if θ+1/θ>2+ϵ\theta+1/\theta>2+\epsilon, and for no ϵ>0\epsilon>0 if θ≤1\theta\leq1, which gives μspec=n/(k−1)\mu_{\mathrm{spec}}=\sqrt{n}/(k-1).

The block entries of Y−E[Y]\mathbf{Y}-\mathbb{E}[\mathbf{Y}] have variance (1+μ)2(1+\mu)^2 instead of 1, because a centred block score has the distribution of 1+μ1+\mu times a centred score under H0H_0 (Appendix A.2). So Y−E[Y]\mathbf{Y}-\mathbb{E}[\mathbf{Y}] has the distribution of a matrix of centred scores under H0H_0 plus μ\mu times the same matrix with all entries outside the pairs of S⋆S^\star set to 0. The nonzero part of this second matrix is a k×kk\times k matrix of centred scores under H0H_0, so its eigenvalues lie between about −2k-2\sqrt{k} and 2k2\sqrt{k} [Bai and Yin, 1988]. By Weyl’s inequality, adding a matrix changes each eigenvalue by at most the largest absolute eigenvalue of the added matrix [Fulton et al., 2000]. The largest eigenvalue of Y/n\mathbf{Y}/\sqrt{n} therefore changes by at most about 2μk/n=2θ/k2\mu\sqrt{k}/\sqrt{n}=2\theta/\sqrt{k}, which tends to 0 as k→∞k\to\infty, and the limits above also hold with the larger variance of the block entries.

Computational boundary

We verify the conditions under which the reduction from the planted clique problem of Brennan et al. [2019] applies to our scores. Under PP, log⁡ℓ=μE−log⁡(1+μ)\log\ell=\mu E-\log(1+\mu) with E∼Exp⁡(1)E\sim\operatorname{Exp}(1) (Appendix A.2), so

KL⁡(P∥Q)=μ−log⁡(1+μ)=μ22(1+O(μ)),\operatorname{KL}(P\mathbin\Vert Q)=\mu-\log(1+\mu)=\frac{\mu^2}{2}(1+O(\mu)),
dSKL=μ21+μ,(11)d_{\mathrm{SKL}}=\frac{\mu^2}{1+\mu}, \tag*{(11)}

and Pr⁡P(log⁡ℓ≥τ)\Pr_P(\log\ell\geq\tau) decays with the exponent IP(τ)=u−1−log⁡uI_P(\tau)=u-1-\log u, where u=(τ+log⁡(1+μ))/μu=(\tau+\log(1+\mu))/\mu.

Besides the condition on KL⁡(P∥Q)\operatorname{KL}(P\mathbin\Vert Q), the lower bound of [18] needs two more. First, (P,Q)(P,Q) must be a computable pair: QQ can be sampled and ℓ\ell evaluated in polynomial time, EQ[ℓ]=EP[ℓ−1]=1\mathbb{E}_Q[\ell] = \mathbb{E}_P[\ell^{-1}] = 1, and both KL divergences are finite. This holds because PP and QQ are exponential with the same support. Second, large values of log⁡ℓ\log\ell must be rare under PP, because the reduction from the planted clique problem in [18] is accurate only on entries whose log⁡ℓ\log\ell stays below a threshold τ\tau. This is measured with the Chernoff exponent IP(τ)=sup⁡t{tτ−log⁡EP[ℓt]}I_P(\tau) = \sup_t\{t\tau- \log\mathbb{E}_P[\ell^t]\}, which gives Pr⁡P(log⁡ℓ≥τ)≤e−IP(τ)\Pr_P(\log\ell\ge\tau) \le e^{-I_P(\tau)} for τ≥KL⁡(P∥Q)\tau\ge\operatorname{KL}(P\|Q) [18]. For our scores, IP(τ)=u−1−log⁡uI_P(\tau) = u - 1 - \log u with u=(τ+log⁡(1+μ))/μu = (\tau+ \log(1+\mu))/\mu.

For k≥nk \ge\sqrt{n}, the second condition is that some threshold τ\tau satisfies τ≥KL⁡(P∥Q)\tau\ge\operatorname{KL}(P\|Q), τk4/n2→0\tau k^4/n^2 \to0, and IP(τ)/(τlog⁡n)→∞I_P(\tau)/(\tau\log n) \to\infty. If μ=o(μsum)\mu= o(\mu_{\mathrm{sum}}), that is, α>4β−2\alpha> 4\beta- 2, the threshold τ=μa\tau= \mu^a with 1<a<21 < a < 2 and aα/2>4β−2a\alpha/2 > 4\beta- 2 satisfies all three: KL⁡(P∥Q)≈μ2/2≤μa\operatorname{KL}(P\|Q) \approx\mu^2/2 \le\mu^a; τk4/n2=n4β−2−aα/2→0\tau k^4/n^2 = n^{4\beta-2-a\alpha/2} \to0; and IP(τ)≈μ2a−2/2I_P(\tau) \approx\mu^{2a-2}/2, so IP(τ)/(τlog⁡n)≈μa−2/(2log⁡n)→∞I_P(\tau)/(\tau\log n) \approx\mu^{a-2}/(2\log n) \to\infty. For k<nk < \sqrt{n}, the second condition is IP(log⁡ρ−1)≥2log⁡nI_P(\log\rho^{-1}) \ge2\log n, with ρ\rho the edge density of the planted clique hypothesis. This needs u≳2log⁡nu \gtrsim2\log n, that is, μ=O(1/log⁡n)\mu= O(1/\log n).

Coordinates of the phase diagram

The phase diagram for submatrix detection in Brennan et al. [ [18] has two coordinates: the size of the block, k=nβk = n^\beta, and the signal, dSKL=n−αd_{\mathrm{SKL}} = n^{-\alpha}, both up to factors that grow slower than any power of nn. In these coordinates, detection is impossible for α>max⁡(β,4β−2)\alpha> \max(\beta, 4\beta- 2), possible in polynomial time for α<max⁡(0,4β−2)\alpha< \max(0, 4\beta- 2), and, under the planted clique hypothesis, hard in between.

We use the same coordinates, with the signal μ2\mu^2 in place of dSKLd_{\mathrm{SKL}}, since dSKL=μ2/(1+μ)d_{\mathrm{SKL}} = \mu^2/(1+\mu) (11). The exponent of dSKLd_{\mathrm{SKL}} differs from α\alpha by log⁡(1+μ)/log⁡n≤log⁡2/log⁡n\log(1+\mu)/\log n \le\log2/\log n for μ≤1\mu\le1, which tends to 00 for n→∞n \to\infty. Each boundary has the form μ2=cLnak−b\mu^2 = cL n^{a}k^{-b}, with k−1≈kk - 1 \approx k, a constant cc, a factor LL equal to 11 or log⁡(n/k)\log(n/k), and exponents aa and bb. With k=nβk = n^\beta and μ2=n−α\mu^2 = n^{-\alpha}, the boundary is α=bβ−a−log⁡(cL)/log⁡n\alpha= b\beta- a - \log(cL)/\log n. The last term is O(log⁡log⁡n/log⁡n)O(\log\log n/\log n) and tends to 00, so as n→∞n \to\infty the boundary becomes the line α=bβ−a\alpha= b\beta-a. The scan boundary and the small-group term of μIT\mu_{\mathrm{IT}} have μ2∝log⁡(n/k)/k\mu^2 \propto\log(n/k)/k, which gives α=β\alpha= \beta; the sum boundary and the large-group term of μIT\mu_{\mathrm{IT}} have μ2≈2n2/k4\mu^2 \approx2n^2/k^4, which gives α=4β−2\alpha= 4\beta- 2, as in [18]. The spectral boundary has μ2≈n/k2\mu^2 \approx n/k^2, which gives α=2β−1\alpha= 2\beta- 1. This line is not in [18], where, for k<nk < \sqrt{n}, detection is possible in polynomial time already for α<0\alpha< 0. Layers with k<nk < \sqrt{n} and 2β−1<α<02\beta- 1 < \alpha< 0 are therefore hard for the sum and spectral tests.

References

  1. [1]Kate Starbird, Ahmer Arif, and Tom Wilson. Disinformation as collaborative work: Surfacing the participatory nature of strategic information operations. Proceedings of the ACM on Human-Computer Interaction, 3(CSCW): 1–26, 2019.DOI
  2. [2]Lynnette Hui Xian Ng and Kathleen M Carley. A combined synchronization index for grassroots activism on social media. arXiv:2212.13221, 2022.arxiv.org/abs/2212.13221
  3. [3]Diogo Pacheco, Pik-Mai Hui, Christopher Torres-Lugo, Bao Tran Truong, Alessandro Flammini, and Filippo Menczer. Uncovering coordinated networks on social media: methods and case studies. In Proceedings of the international AAAI conference on web and social media, volume 15, pages 455–466, 2021.arxiv.org/abs/2001.05658
  4. [4]Emilio Ferrara, Onur Varol, Clayton Davis, Filippo Menczer, and Alessandro Flammini. The rise of social bots. Communications of the ACM, 59(7):96–104, 2016.
  5. [5]Leonardo Nizzoli, Serena Tardelli, Marco Avvenuti, Stefano Cresci, and Maurizio Tesconi. Coordinated behavior on social media in 2019 uk general election. In Proceedings of the international AAAI conference on web and social media, volume 15, pages 443–454, 2021.arxiv.org/abs/2008.08370
  6. [6]Derek Weber and Frank Neumann. Amplifying influence through coordinated behaviour in social networks. Social Network Analysis and Mining, 11(1):111, 2021.DOI
  7. [7]Karishma Sharma, Yizhou Zhang, Emilio Ferrara, and Yan Liu. Identifying coordinated accounts on social media through hidden influence and group behaviours. In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pages 1441–1451, 2021.arxiv.org/abs/2008.11308
  8. [8]Lorenzo Cima, Lorenzo Mannocci, Marco Avvenuti, Maurizio Tesconi, and Stefano Cresci. Coordinated behavior in information operations on twitter. IEEE Access, 12: 61568–61585, 2024.DOI
  9. [9]Lorenzo Mannocci, Stefano Cresci, Matteo Magnani, Anna Monreale, and Maurizio Tesconi. Multimodal coordinated online behavior: Trade-offs and strategies. arXiv:2507.12108, 2025.arxiv.org/abs/2507.12108
  10. [10]Thomas Magelinski, Lynnette Ng, and Kathleen Carley. A synchronized action framework for detection of coordination on social media. Journal of Online Trust and Safety, 1(2), 2022.
  11. [11]Luca Luceri, Valeria Pantè, Keith Burghardt, and Emilio Ferrara. Unmasking the web of deceit: Uncovering coordinated activity to expose information operations on twitter. In Proceedings of the ACM Web Conference 2024, pages 2530–2541, 2024.
  12. [12]Lorenzo Mannocci, Michele Mazza, Anna Monreale, Maurizio Tesconi, and Stefano Cresci. Detection and characterization of coordinated online behavior: A survey. ACM Computing Surveys, 58(16):1–38, 2026.arxiv.org/abs/2408.01257
  13. [13]Georgios Panayiotou, Lorenzo Mannocci, and Maurizio Tesconi. Setting the clock: Evaluating temporal window parameters for coordinated behavior detection. arXiv preprint arXiv:2609.21959, 2026.arxiv.org/abs/2609.21959
  14. [14]Valeria Pantè, David Axelrod, Alessandro Flammini, Filippo Menczer, Emilio Ferrara, and Luca Luceri. Beyond interaction patterns: Assessing claims of coordinated inter-state information operations on twitter/x. In Companion Proceedings of the ACM on Web Conference 2025, pages 1234–1238, 2025.arxiv.org/abs/2502.17344
  15. [15]Cristina Butucea and Yuri Ingster. Detection of a sparse submatrix of a high-dimensional noisy matrix. Bernoulli, pages 2652–2688, 2013.DOI
  16. [16]Zongming Ma and Yihong Wu. Computational barriers in minmax submatrix detection. The Annals of Statistics, pages 1089–1116, 2015.DOI
  17. [17]Tony Cai, Tengyuan Liang, and Alexander Rakhlin. Computational and statistical boundaries for submatrix localization in a large noisy matrix. 2017.DOI
  18. [18]Matthew Brennan, Guy Bresler, and Wasim Huleihel. Universality of computational lower bounds for submatrix detection. In Conference on Learning Theory, pages 417–468. PMLR, 2019.arxiv.org/abs/1902.06916
  19. [19]Matthew Brennan and Guy Bresler. Reducibility and statistical-computational gaps from secret leakage. In Conference on Learning Theory, pages 648–847. PMLR, 2020.arxiv.org/abs/2005.08099
  20. [20]Roger Guimera, Marta Sales-Pardo, and Luís A Nunes Amaral. Modularity from fluctuations in random graphs and complex networks. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 70(2):025101, 2004.DOI
  21. [21]Tiago P Peixoto. Descriptive vs. inferential community detection in networks: Pitfalls, myths and half-truths. Cambridge University Press, 2023.
  22. [22]Letizia Iannucci, Elisa Muratore, Antonis Matakos, and Mikko Kivelä. Detecting coordinated activities through temporal, multiplex, and collaborative analysis. In Proceedings of the International AAAI Conference on Web and Social Media, volume 20, pages 1063–1082, 2026.
  23. [23]Ozgur Can Seckin, Manita Pote, Alexander C Nwala, Lake Yin, Luca Luceri, Alessandro Flammini, and Filippo Menczer. Labeled datasets for research on information operations. In Proceedings of the International AAAI Conference on Web and Social Media, volume 19, pages 2567–2574, 2025.arxiv.org/abs/2411.10609
  24. [24]Serena Tardelli, Leonardo Nizzoli, Marco Avvenuti, Stefano Cresci, and Maurizio Tesconi. Multifaceted online coordinated behavior in the 2020 us presidential election. EPJ Data Science, 13(1):33, 2024.DOI
  25. [25]Federico Cinus, Marco Minici, Luca Luceri, and Emilio Ferrara. Exposing cross-platform coordinated inauthentic activity in the run-up to the 2024 us election. In Proceedings of the ACM on Web Conference 2025, pages 541–559, 2025.DOI

Paper details

vlnc:W_cm3zfj4m
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents