| paper | The Grapevine Web: Analysing the Spread of False Information in Social Networks with Corrupted Sources |
| authors | — |
| venue | AAMAS 2023 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given a learner, source-distance types \(D\), distribution \(\mu\), intensity \(\rho\), Markov parameters \(M\), prior \(\theta\), and budget \(\kappa\), choose \(x_d\) with \(0\le x_d\le\mu_d\) and \(\sum_d x_d\le\kappa\) to maximize \(B_\rho(0)-B_\rho(x)\), where source messages are Poisson counts of intensity \(\rho\mu_d\) and corruption changes \(q_{d,1}\) to \(q_{d,0}\).
A one-learner Poissonized high-multiplicity population with distance types \(d\), source mass \(\rho\mu_d\), fractional corruption variables \(x_d\), and objective equal to the expected drop in Bayesian posterior belief.
The fixed-\(\rho\) Poissonization does not by itself establish convergence from deterministic \(N\)-clone populations as \(N\to\infty\), so the precise high-multiplicity dictionary remains to be proved.
fatal: False
The mirror covers only the single-learner optimal corruption result in Theorem 2; it leaves the learning threshold, multi-learner non-submodularity, empirical heuristics, and influence-evaluation issues untouched.
The strongest case is a narrow one: the paper gives one genuinely mirrorable computational result, and it is enough. I would anchor on Theorem 2, “Choosing closest sources is always optimal in the single learner case.” This theorem is proved in the paper; it is not imported from [15]. The paper does not prove an NP-hardness or formal polynomial-time classification for its multi-learner attack. Its statement that subset selection is NP-hard is only a generic citation, so I would not use it as an anchor.
My lead problem is Continuous Grapevine Source-Mass Attack.
There is one Bayesian learner and a finite set of source types \(D\). A source type \(d\) consists of a common distance \(d\) from the learner and the common propagation parameters relevant to the paper’s Markov matrix \(M^d\). This is a complete type under the paper’s own simplifying assumption: message propagation depends on the path only through its length. Let \(\mu_d\) be the fraction of source mass of type \(d\), with \(\sum_d\mu_d=1\). The regime is a large population of source accounts—syndicated news accounts, local media outlets, or coordinated bot accounts—falling into a small number of distance or network-role cohorts. Thus the total number of accounts is very large while \(|D|=\tau\) is moderate.
The attacker chooses \(x_d\), the fraction of type-\(d\) source mass to corrupt. The feasible region is
\[ 0\le x_d\le \mu_d \qquad\text{and}\qquad \sum_d x_d\le \kappa, \]
where \(\kappa\) is the attacker's fractional budget. Corruption changes the source message from \(1\) to \(0\), exactly as in the paper.
To make the Bayesian objective well-defined for divisible mass, use a Poissonized high-multiplicity representation with source intensity \(\rho\). For \(i\in\{0,1,\varnothing\}\), write
\[ q_{d,j}(i)=(M^d)_{ij}. \]
Under the learner’s no-attack hypothesis \(\omega=j\), the number \(Y_{d,i}\) of type-\(d\) messages arriving in state \(i\) is Poisson with mean \(\rho\mu_dq_{d,j}(i)\). The learner uses the posterior
\[ \beta(Y)= \frac{\theta L_1(Y)} {\theta L_1(Y)+(1-\theta)L_0(Y)}, \]
where \(L_j\) is the corresponding product of Poisson likelihoods. Under the actual state \(\omega=1\) and attack vector \(x\), the observed count has mean
\[ \rho\bigl((\mu_d-x_d)q_{d,1}(i)+x_dq_{d,0}(i)\bigr). \]
Let \(B_\rho(x)\) be the expectation of \(\beta(Y)\) under this attacked distribution. The continuous problem is
\[ \max_{x} \ \sigma_\rho(x) := B_\rho(0)-B_\rho(x) \]
subject to the mass constraints above. A solution is an optimal mass vector \(x\), or an \(\varepsilon\)-optimal vector if approximation is requested.
This is recognisably the authors’ problem: the source corruption action, Markovian mutation, Bayesian posterior, and expected loss of belief are unchanged. Only named source identities and the cardinality budget have been replaced by source-type mass and a fractional budget. The Poissonization is a clean way to represent arbitrary masses; a deterministic clone population gives the corresponding rational high-multiplicity formulation.
I expect this problem to be Class A, tractable. The exchange argument in Theorem 2 says that, regardless of the already corrupted set, replacing a farther source by a nearer one never decreases influence. In the mass formulation, the same argument exchanges an infinitesimal amount of corrupted mass. Therefore an optimal solution fills source types in increasing order of distance:
\[ x_d=\mu_d \]
for every type strictly closer than a cutoff, takes the necessary residual mass from the cutoff type, and sets all farther types to zero. Once the types are sorted, the solution is computable in \(O(\tau\log\tau)\) time, without evaluating the exponentially large posterior state space. This is exactly the kind of structural simplification that makes a continuous formulation computationally valuable.
The scenario is plausible rather than artificial. A single platform trust engine, public-health dashboard, or fact-checking institution may receive messages from millions of accounts, while accounts are effectively interchangeable within a modest number of propagation-distance or platform-role classes. The attacker may control a percentage of a syndication cohort rather than select one special individual. This is a genuine population continuization: mass is attached to source agents, not to outcomes, probabilities added after the fact, or time dynamics.
The main weakness is that this mirrors only the paper’s single-learner theorem, while the paper’s more interesting setting has multiple learners on an arbitrary network. There is also a technical issue if one takes a literal atomless limit while allowing the learner to observe infinitely many independent messages: the posterior may concentrate and the Bayesian problem can become degenerate. That is why the problem keeps an explicit source-intensity parameter \(\rho\). The normalized society is still \(\mu\); \(\rho\) records the high-multiplicity observation scale. If one insists on a \(\mu\)-only, infinite-data limit, this mirror becomes much weaker.
The natural next question is the multi-learner version: source types would carry their full distance profile to a finite set of learner types, and the attacker would choose a mass vector \(x\) to maximize the learner-mass-weighted drop in expected posterior. Lemma 4 supports coordinatewise monotonicity of this objective, while Lemma 6 warns that the finite influence function is neither submodular nor supermodular. That extension is plausibly open, and may be continuum-specifically hard. I would present it as a follow-up generated by the lead mirror, not as a second established anchor.
Theorem 2 is a genuine, if minimal, computational anchor, so the negative case should not pretend otherwise. The problem is that its proposed mass mirror has no nondegenerate population limit.
Take \(N\mu_d\) cloned sources of type \(d\), and corrupt \(Nx_d\) of them. Let \(q_{d,j}(i)=(M^d)_{ij}\). Conditional on the true state \(1\), the empirical signal distribution for type \(d\) is
\[ \bar q_{d,x}(i) = \left(1-\frac{x_d}{\mu_d}\right)q_{d,1}(i) + \frac{x_d}{\mu_d}q_{d,0}(i). \]
The learner’s log posterior odds are, up to the prior term,
\[ \sum_{d,i}Y_{d,i} \log\frac{q_{d,1}(i)}{q_{d,0}(i)}. \]
After division by \(N\), this converges to
\[ \Lambda(x) = \sum_d \mu_d\sum_i \bar q_{d,x}(i) \log\frac{q_{d,1}(i)}{q_{d,0}(i)}. \]
Thus, for informative sources, the posterior converges to \(1\) when \(\Lambda(x)>0\) and to \(0\) when \(\Lambda(x)<0\). In particular, \(B_N(0)\to1\), while \(B_N(x)\) also tends to \(1\) for every attack that leaves positive aggregate evidence, and tends to \(0\) only after a threshold is crossed. Hence the paper’s expected-posterior influence has no useful \(\mu\)-only limit: it becomes essentially \(0\)-or-\(1\), with a knife-edge boundary. The finite-\(N\) Bayesian effect that Theorem 2 orders is precisely what disappears under high multiplicity.
The proposed Poissonization does not repair this. Holding \(\rho\) fixed retains only a finite effective number of observations, so \(\mu\) describes composition while \(\rho\) carries all the information-scale content. That is a finite-intensity statistical experiment, not the atomless high-multiplicity society in the programme. Sending \(\rho\) to infinity restores the concentration above. A deterministic clone population does not converge to the fixed-\(\rho\) Poisson model without adding a new rare-activation or sampling assumption.
The nearest-source cutoff is therefore a valid finite-clone restatement of Theorem 2, but not a well-defined continuous version of its objective. Avoiding the collapse requires sampling only finitely many messages, scaling transmission or mutation probabilities with \(N\), or replacing expected posterior by normalized log evidence. Each option changes the paper’s observation model or objective; it is a new mean-field statistical problem rather than a mirror.
The richer multi-learner rescue is weaker still as a paper anchor. The paper proves no complexity result there: Lemma 4 is monotonicity, Lemma 6 is a counterexample to submodularity, Example 5 is a finite instance, and the NP-hardness remark is only a generic citation. To preserve the network, a source type must encode its distance profile to every learner, while a learner type must encode its source-distance histogram. In arbitrary graphs these profiles are identity-specific and proliferate with the network. Replacing them by finitely many block types or a distance kernel produces a new quotient-network model, and its concentrated \(0\)-\(1\) posterior objective is a new threshold-coverage problem.
Lemma 1 is analytic and imported from prior work; Lemma 3 is a trivial no-learning case. Nothing else supplies a second computational anchor. I would therefore reject this paper as a worthwhile ChoCo mirror under the strict population-continuization standard. The negative case is not a proof that a block-network Bayesian model could never be valuable; if finite-intensity or new sampling semantics are admitted, the proponent’s construction survives as an extension. But that concession is exactly why the paper does not support the claimed continuous mirror as stated.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.