| paper | d4-conf-aaai-2018-1092 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→other discrete result → its continuous mirror
Answer: The exact optimum is \(R_N(Q)=1-\frac{h_N-1}{h_N}(1-h_N/N)^Q\mathbb E[(N-h_N-D_Q)/(N-D_Q)]\), where \(D_Q\) counts distinct labels in \(Q\) independent uniform draws from \(N-h_N\) labels. For every fixed \(\epsilon>0\), budgets \(Q_N=O(N^{1-\epsilon})\) give \(R_N(Q_N)=(1+o(1))/h_N=o(1)\). If \(Q_Nh_N/N\to c\), the ratio tends to \(1-e^{-c}\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
For an \(N\)-indexed society with types \(H,I\), masses \(\mu_H=\lceil\log N\rceil/N\) and \(\mu_I=1-\mu_H\), and a hidden uniform assignment of identities to types, suppose \(H\) forms a clique and \(I\) consists of isolates. With \(q=1\), one seed, and Jump-Crawl queries costing mass \(1/N\) per queried identity, characterize the best approximation ratio for expected activated mass relative to the full-information optimum as a function of query budget \(Q_N\). In particular, must every policy with \(Q_N=O(N^{1-\epsilon})\), for fixed \(\epsilon>0\), have ratio \(o(1)\)?
Use a two-type population whose rational masses describe the rare clique group and the isolated group; identities are hidden, while the type relation rule determines links. Queries and the single seed remain attached to identifiable members, each of mass \(1/N\), and the objective is expected activated mass.
The lower bound is nondegenerate only along the \(N\)-indexed sequence where \(\mu_H\) shrinks; at fixed positive \(\mu_H\), a constant number of uniform queries can find the clique with constant probability. The proponent flags the shrinking mass but does not establish that this singular sequence is a continuous-population limit rather than a mass-normalized finite query problem.
fatal: False
The mirror covers Theorem 1's rare-clique query lower bound. It leaves Theorem 2's ARISEN guarantee aside because that result depends on realized SBM neighborhoods and individual seeds; the empirical comparisons are also not covered.
The strongest honest mirror is an unknown network over a mass-described population. For population scale \(N\), let the society have type distribution \(\mu_N\), with each of \(N\) agents carrying mass \(1/N\). Types describe agents’ shared network-generating role; the identity-to-type assignment is hidden, and realized links are the uncertain environment that queries reveal. A query costs \(1/N\) units of population mass and reveals one agent’s links. After querying, a policy outputs a seed set, represented by a measure of total mass \(K/N\). Its value is the expected mass activated under the independent cascade model, compared with the full-information optimum. This keeps the paper’s information problem intact while making population proportions, query budget, seed supply, and influence all expressible in mass terms.
My lead anchor is Theorem 1, proved in this paper. It says that there is a family of \(N\)-node graphs on which any algorithm with query cost \(O(N^{1-\epsilon})\), for some \(\epsilon>0\), has approximation ratio at most \(o(1)\). The construction is a clique of \(\lceil\log N\rceil\) nodes and \(N-\lceil\log N\rceil\) isolated nodes, with cascade probability \(q=1\) and one seed. The paper’s result is a lower bound for Jump-Crawl queries: without discovering the clique, the algorithm gets influence \(1\), while a clique seed gets influence \(\lceil\log N\rceil\).
The corresponding Rare-type exploratory influence problem has two types, \(H\) and \(I\), with masses \(\mu_H=\lceil\log N\rceil/N\) and \(\mu_I=1-\mu_H\). Agents of type \(H\) form a clique; agents of type \(I\) are isolated. The identities of the agents in each type are hidden. Given the type masses, the query budget \(Q_N\), and the graph-generation rule, can an adaptive Jump-Crawl policy return one seed whose expected activated mass is a constant fraction of the full-information optimum? A solution is such a policy; the theorem says that when \(Q_N=O(N^{1-\epsilon})\), its ratio is \(o(1)\). In mass units, the high-type seed activates \(\lceil\log N\rceil/N\), while a low-type seed activates \(1/N\). A query budget of mass \(Q_N/N=O(N^{-\epsilon})\) finds the rare type with vanishing probability. This is a clean hardness-transfers question: the discrete lower bound survives in a mass-described instance sequence. It also raises the natural boundary question of how query mass must scale with the rarest influential type’s mass to obtain a constant approximation.
A second, complementary anchor is Theorem 2, the paper’s “Simplified case” theorem, also proved here. For isolated communities (\(p_b=0\)), when the top \(K\) communities have equal size \(\mu\) and \(K\mu\ge .01N\), ARISEN can be implemented with \(O(\log^6 N)\) queries and approximation ratio
\[
\left(1-e^{-0.99}-0.01-\frac{1}{K}-o(1)\right)\beta(\mu).
\]
Here \(\beta(\mu)\) is the fraction in the giant component of \(G(\mu,p_wq)\), under the theorem’s conditions. The result says that a polylogarithmic number of local queries suffices for this guarantee against the optimum that knows the entire graph.
Its mass mirror, Community-mass exploratory influence, takes an unknown SBM population with community masses \(\mu_i=|C_i|/N\), \(p_b=0\), known within-community link probability \(p_w\), and cascade probability \(q\). The top \(K\) communities have equal mass \(\sigma=\mu/N\), with \(K\sigma\ge .01\); the within-community conditions ensure connectivity and a supercritical cascade. The policy has query mass \(O(\log^6 N/N)\) and returns seed mass \(K/N\); ask whether it can achieve the stated ratio for expected activated mass relative to the full-information optimum. Theorem 2 supplies the affirmative algorithmic answer, a tractable case. It suggests further questions about unequal community masses, positive \(p_b\), and how the guarantee changes as the top communities’ total mass shrinks.
These are scenarios with many agents per community and a small number of latent community types: for example, large village or shelter populations with shared community-level link patterns. The relevant distinction is by regime. A large population with a few repeated network roles is the intended case; a small group with individually distinctive ties is not. The authors should recognize both mirrors: the cascade objective, seed choice, and limited node queries are theirs, while the population and the query and seed budgets are stated in per-capita units. Their use of an SBM is not itself a collision: it randomizes the finite graph, whereas these questions make the population’s type masses the instance description.
The weak point is also central to the case: queries and seeds still act on identifiable agents, each with mass \(1/N\), because the paper’s information advantage comes from inspecting particular realized neighborhoods. The rare-type hardness mirror is an \(N\)-indexed family whose influential type’s mass tends to zero, rather than a single fixed, atomless limit. Even in the community result, the continuous object is the type distribution; network realization and local observation remain individual-level. That makes this a credible, narrow population mirror, but not a claim that the paper’s entire graph-query problem becomes a static LP over community masses.
The central problem in both results is that the paper’s object is a *realized network of identifiable vertices*. Queries reveal particular vertices’ links, and the benchmark is the best seed set for that realized graph. A community label describes who an agent is connected to *in distribution*; it does not specify that agent’s realized neighborhood. To preserve the paper’s benchmark, a type would need to carry the realized relational information that queries uncover. In a typical SBM instance, that leaves essentially vertex-level types, not a compressed society with a small support. Replacing those details with community masses changes the benchmark to one based on an average or expected network.
Theorem 1 has a separate problem: its hard instance is a clique of \(\lceil\log n\rceil\) vertices among \(n\) agents. Its influential type has mass \(\lceil\log n\rceil/n\), which tends to zero; the optimum’s activated mass tends to zero too. At any fixed positive mass for that type, a bounded number of uniform queries, depending on the mass, can find it with constant probability. The lower bound returns only when the influential mass shrinks with \(n\). One can retain that limit by tracking query *counts* and rare-type probabilities, but then the result is about sampling a vanishingly rare finite set of vertices. If queries are charged by mass, those queries cost zero in the limit. That is a real rare-type sample-complexity question, but the theorem’s lower bound does not become a nondegenerate mass-query lower bound.
Theorem 2 looks more promising because its communities can have positive population mass. Yet its guarantee uses \(K\) identifiable seeds and only \(O(\log^6 n)\) vertex queries. In the advertised sparse-seed regime, both selected seed mass and queried mass vanish. A seed can nevertheless activate a positive fraction of a large community through the realized giant component. In an atomless mass model with a regular interaction kernel, a zero-mass seed set has zero mass to propagate; reproducing the theorem’s effect requires retaining tagged individual seeds and their realized links. Giving seeds and queries positive mass avoids that singularity, but asks about a different intervention and information budget. A graphon or community-kernel model could make that new question coherent, though it would not instantiate the theorem’s local-query guarantee.
So I would resist treating either theorem as a clean continuous-population result: one relies on a vanishing rare type, and the other on zero-mass actions with individual-level network information. The negative case is not airtight, though. A query-complexity theory parameterized by community masses, with an explicit sampling oracle and retained vertex identities, could be worthwhile. Its value would come from that hybrid model; whether it counts as a ChoCo mirror depends on accepting count-based individual queries alongside a mass-described population.
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.