| paper | Learning a Social Network by Influencing Opinions |
| authors | — |
| venue | AAMAS 2024 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational population masses \(\mu\), initial type-opinion masses \(\lambda^0_{t,\ell}\), a known hypothesis class \(\mathcal H\subseteq\{0,1\}^{T\times T}\), and budgets \(q,B\), an unknown \(h\in\mathcal H\) drives synchronous majority updates: \(h_{st}=1\) means source type \(s\) influences target type \(t\), and a query chooses rational \(\eta\) with \(\sum_{\ell}\eta_{t,\ell}=\mu_t\). The intervention cost is \(c(\lambda,\eta)=\frac12\sum_{t,\ell}|\eta_{t,\ell}-\lambda_{t,\ell}|\), and the campaigner observes the complete successor mass vector after each update. Does there exist an adaptive policy that identifies \(h\) exactly for every \(h\in\mathcal H\) using at most \(q\) observations and total cost at most \(B\)?
A finite-type block network over population mass \(\mu\): hidden \(h\in\{0,1\}^{T\times T}\), state \(\lambda\) records type-opinion mass, interventions move mass at \(L^1/2\) cost, majority updates produce aggregate successor masses, and the objective is exact network identification.
The mirror identifies only the quotient relation \(h\), not an arbitrary individual graph \(G\), so the original universal exact-recovery guarantee does not transfer literally and exact single-edge defects become unobservable.
fatal: False
Theorem 1 is mirrored as exact learning of a finite type-block influence network; Proposition 1 as block-level clique recognition with mass margins; and Theorem 2 as entropy-optimal mass-query design. The individual-edge lemmas, arbitrary-graph guarantee, and unrestricted graphon variants are not covered.
The strongest positive case is an author-recognisable extension of the paper, not a literal replacement of every named agent by an atomless point. The paper contains no named NP-hardness, P, FPT, or W[1]-hardness theorem of its own. Its relevant named computational anchors are resource and information results: Theorem 1, Proposition 1, and Theorem 2, all proved in this paper.
The natural regime is a large online platform or public-information network. There may be millions of users, but they fall into \(\tau\) repeated cohort types: for example, location–demographic–interest classes. Members of one type have the same intervention price, initial opinion role, observability, and type-level influence environment. The platform can campaign on a fraction of a cohort and reports the resulting opinion mass in each cohort. Thus \(N\) is large while \(\tau\ll N\), and \(\mu_t\) is the fraction of users of type \(t\).
The hidden network is a type-level directed influence relation \(h\in\{0,1\}^{T\times T}\): \(h_{st}=1\) means that every member of target type \(t\) receives influence from the mass of source type \(s\). The campaigner knows \(T\), \(\mu\), and the admissible class \(\mathcal H\), but not \(h\). This is not the objectionable move of assigning arbitrary users the same type: the scenario assumes genuine repeated cohorts with common network roles.
A continuous state is \(\lambda=(\lambda_{t,b},\lambda_{t,w})_{t\in T}\), where \(\lambda_{t,b}+\lambda_{t,w}=\mu_t\). A campaign query chooses a new labelling mass \(\eta\) satisfying the same constraints. Its intervention cost is
\[ c(\lambda,\eta)=\frac12\sum_{t\in T}\sum_{\ell\in\{b,w\}} \left|\eta_{t,\ell}-\lambda_{t,\ell}\right|. \]
For \(h\), define the majority margin for a mass of type \(t\) currently holding opinion \(\ell\) by
\[ \Delta_{h,t,\ell}(\eta) = \sum_{s\in T}h_{st} \bigl(\eta_{s,\ell^c}-\eta_{s,\ell}\bigr). \]
That mass switches if \(\Delta_{h,t,\ell}(\eta)>0\), and otherwise retains its opinion. The campaigner observes the complete post-update type-mass vector \(U_h(\eta)\), chooses subsequent queries adaptively, and must identify \(h\), or a stated property of \(h\), within observation budget \(q\) and intervention-mass budget \(B\).
When all \(\mu_t\) and intervention masses are rational, clearing denominators produces a finite high-multiplicity block network. Strict majority inequalities are preserved exactly. Ties require care: the original proof sometimes relies on the missing self-loop changing a margin by one voter, whereas an atomless model removes that correction. I therefore regard the following as an extension mirror with an explicit tie-margin treatment, not as a cost-free direct restatement.
The lead anchor is Theorem 1: “The campaigner can learn the underlying graph \(G\) of any social network \((N,G)\) by spending \(O(n^2)\) on observation and \(O(n^3)\) on intervention.” This is proved in the paper.
The corresponding problem is HM-Exact Type-Network Learning under Majority Diffusion. An instance consists of rational \(\mu\), a finite type set \(T\), a known hypothesis class \(\mathcal H\subseteq\{0,1\}^{T\times T}\), an initial state \(\lambda^0\), and budgets \(q,B\). A solution is an adaptive policy that, after at most \(q\) observed updates and total intervention cost at most \(B\), outputs the hidden \(h\in\mathcal H\) correctly for every \(h\).
This is recognisably the paper’s problem: the hidden object is still an influence network; the dynamics are still binary synchronous majority; the campaigner still intervenes, observes transitions, refines a hypothesis space, and must learn exactly. The only change is that the graph is a repeated type-block graph and interventions are measured by mass.
I would expect the finite-type, rational, separated-margin version to be Class A. The proof idea behind the paper’s Lemma 1 and Theorem 1 survives at type level: progressively vary source-type mass until a target type crosses a majority threshold, then use adjacent mass labellings to determine whether a particular type relation is present. The natural target is a polynomial bound such as \(O(\tau^2)\) observations, with polynomially encoded rational interventions. Further questions include the minimum observation–mass trade-off, learning when \(\mu\) is unknown, and whether arbitrary step-function graphons rather than binary type relations remain tractable.
The second anchor is Proposition 1: “The campaigner can determine if \(G\) is a clique by using \(2n+1\) observations and making \(n^2\) interventions.” This is also proved here.
Its continuous counterpart is HM-Odd-Margin Clique Recognition. The instance contains a rational type distribution \(\mu\), an initial all-black state, and a positive rational anchor mass \(\delta\). The campaigner may choose a mass \(S\) of size \(1/2-\delta/2\), flip it to white, observe one update, then flip \(S\) together with a disjoint anchor cohort of mass \(\delta\), and observe again. The goal is to decide whether the hidden type-level network is complete.
The anchor mass is the correct continuous replacement for odd cardinality. In the finite proof, the first manipulated set has size \(1/2-1/(2n)\), while the second has size \(1/2+1/(2n)\); one voter supplies the strict margin. In the continuum, \(\delta\) supplies that margin explicitly. For a complete network, the first query returns to all black and the second reaches all white. Repeating the construction with type-level anchor cohorts should certify completeness.
I expect this problem also to be Class A under the separated-margin and block-network assumptions. It remains a recognition problem about hidden influence structure, not merely a test of whether a known population reaches consensus. Further questions are how the budget depends on \(\delta\), whether the anchor can itself be learned, and what happens with noisy aggregate observations.
The third anchor is Theorem 2, which gives the expected information gained from an additional query. It is proved in the paper, although it is an information-value result rather than a named complexity classification.
The corresponding problem is HM-Optimal Information-Gain Campaigning. An instance consists of the type masses, current history \(\mathcal D\), current state \(\lambda\), a rational prior \(\pi\) over hidden type-level networks \(h\), and a remaining intervention budget \(B\). The decision variable is a rational mass labelling \(\eta\) with \(c(\lambda,\eta)\le B\). The objective is to maximise the expected posterior entropy reduction about \(h\).
For a possible observed successor state \(s\), let \(\mathcal H_{\mathcal D}(s;\eta)\) be the networks consistent with the old history and the new observation. Under a uniform posterior, the objective is
\[ \operatorname{IG}(\eta\mid\mathcal D) = \sum_s \frac{|\mathcal H_{\mathcal D}(s;\eta)|}{|\mathcal H_{\mathcal D}|} \log_2 \left( \frac{|\mathcal H_{\mathcal D}|} {|\mathcal H_{\mathcal D}(s;\eta)|} \right). \]
With a general prior, the corresponding terms use posterior probabilities instead of cardinalities. This is the mass-action analogue of Theorem 2; the probability distribution over hidden graphs is not itself being misrepresented as the continuous population.
I would classify fixed-query evaluation as plausibly Class A under a factored prior over type-target relations. Optimising over all rational mass queries is more likely a Class C boundary problem: the action space is continuous, the majority response is thresholded, and the number of possible posterior regions can be exponential in \(\tau\). This directly develops the paper’s own open question about efficiently exploring the exponentially many possible queries.
The weakest point is that the paper’s exact-learning proof is identity-sensitive. Its pivot argument exploits individual interventions and one-voter tie changes. An atomless population erases those effects. My mirror therefore replaces arbitrary graphs by repeated type-block networks, named interventions by cohort-mass interventions, and parity by an explicit strict-margin parameter. A referee could reasonably call that an extension rather than a direct mirror.
That weakness does not eliminate the positive case. The paper’s central object remains intact: a campaigner learns a hidden influence network by designing opinion interventions and observing deterministic diffusion. The network is now a high-multiplicity object, the resource is honestly measured in mass, and the resulting questions have a clear algorithmic landscape: exact type-network learning likely tractable, clique recognition likely tractable, and entropy-optimal continuous campaigning a plausible continuum-specific frontier.
The paper is a poor candidate for continuization because its agents are not merely population mass. They are addresses in the hidden object and in the query interface. The campaigner’s task is to recover whether the named edge \((j,i)\) exists, by changing the opinion of named agent \(j\) and observing named agent \(i\). The pivot in Lemma 1 is useful precisely because it is one identifiable individual.
This creates a fundamental dichotomy. Suppose we represent a continuum network by a graphon \(W(x,y)\). Aggregate opinion dynamics depend on quantities such as
\[ M_W(y,z)=\int W(x,y)z(x)\,d\mu(x), \]
where \(z(x)\) is signed opinion mass. Changing \(W\) on a null set does not change any aggregate observation. Thus a complete network and one with a single missing edge are observationally identical in the continuum, although one is a clique and the other is not. Exact individual edges disappear. Retaining positive mass for every individual simply retains an atomic population and abandons the high-multiplicity limit.
The proposed finite-type repair does not preserve the paper’s problem. If \(h_{st}=1\) means that every member of type \(s\) influences every member of type \(t\), then the model is restricted to blow-ups of a finite type graph. The hidden object is now \(h\), not \(G\). All individual graph structure inside a type block has been assumed away before learning begins. This may define a new active-learning problem, but it is not a high-multiplicity version of exact learning of an arbitrary network.
That defeats Theorem 1. The theorem promises recovery of \(G\) for every directed graph, whereas aggregate type observations can recover at most the quotient relation \(h\). If arbitrary within-type edges are restored, they are invisible to mass observations; if they are prohibited, the theorem’s identity-sensitive combinatorics have been removed. The suggested \(O(\tau^2)\) type-learning problem is therefore a new block-network result, not a continuous mirror of the paper’s exact-learning result.
Proposition 1 has the same problem in a less obvious form. Clique recognition is a graph property rather than an edge-by-edge output, but exact cliquehood is not invariant under the continuum representation: a null set of missing edges is invisible. The proposed anchor mass \(\delta\) repairs the strict-majority tie, but it does not repair this loss of information. It can detect a missing relation only when that defect occupies a positive-measure type block. The resulting property is “complete almost everywhere” or “complete at the block level,” not the paper’s \(G\)-is-a-clique property. Repeating the experiment over type blocks merely tests the assumed finite type graph.
Theorem 2 is even less stable under the limit. Its information gain is defined over a finite labelled hypothesis space and relies on observations of the full labelled successor vector. For arbitrary continuum networks, the analogue would require a prior over graphons or infinite edge configurations; cardinality ratios such as
\[ \log_2\!\left(\frac{|\mathcal H_t|}{|\mathcal H_{t+1}|}\right) \]
no longer define the relevant information quantity. Aggregate observations leave enormous families of individual graphs observationally equivalent. If one instead puts a finite prior on \(h\), then the problem becomes ordinary Bayesian experimental design over a finite hidden matrix; the continuous population contributes only weights to the query cost and threshold calculation. The proposed entropy-maximisation problem is coherent, but it is not the information-gain theorem’s high-multiplicity counterpart.
The proponent’s block-network model is not nonsensical, and it could support a separate paper. But it obtains coherence by replacing the paper’s hidden named network with a finite quotient network. Preserving the original target makes exact edges and exact cliquehood measure-zero phenomena; preserving a meaningful continuum makes the target a different object. On the programme’s criterion, none of the three anchors survives that dichotomy as a worthwhile continuous mirror.
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.