| paper | d4-conf-ijcai-2017-0684 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper’s only numbered result is Definition 1, and its NP-hardness statement is background cited to earlier work. Its own contribution reports experimental comparisons, including a 38% gain, but gives no numbered theorem, lemma, corollary, or proposition asserting a computational result. Therefore bit (a) fails, even though a block-population follow-up can be formulated.
fails bit a — no named computational result to mirror
The candidate model covers a type-level version of partial-observation seed selection, but no named result of the paper; it leaves the reported heuristic comparisons and their node-specific boundary structure unmirrored.
This paper has no qualifying named computational result to use as an anchor. It has a numbered *Definition 1* for reverse reachable sets, but no numbered theorem, lemma, corollary, or proposition asserting a complexity or algorithmic result. Section 2.1 says that fully observable influence maximization is NP-hard, citing Kempe et al. [10]; that is background, not a result proved here. The paper’s own central findings—such as degree heuristics outperforming IMM at low visibility, and a reported gain of up to 38% with one seed—are empirical results in Section 4, not named results of the required kind. I would not relabel any of these as an anchor.
The strongest positive case I can make is therefore a candidate mirror of the paper’s underlying problem, not an anchor-based case. It is plausible in a large organization or online network where many people fall into a relatively small number of exchangeable groups, such as role and region, with similar influence rates across groups. The regime would have \(N\) people and \(\tau\) types, with \(N\gg\tau\). The seed budget would need to grow with the population: a fixed number of seeds, as in the paper’s main experiments, does not naturally become positive seed mass.
One precise follow-up problem would be *Continuous Partial-Observation Influence Maximization*. An instance gives types \(T\), rational masses \(\mu_t\) summing to one, a set \(A\subseteq T\) of observable, seed-eligible types, and a seed-mass budget \(\kappa\). It also gives a finite rational distribution \(\Pi\) over possible full type-to-type cascade-rate matrices, conditioned on the observed network data. A decision is an allocation \(x_t\in[0,1]\) for \(t\in A\), with \(\sum_{t\in A}\mu_t x_t\le\kappa\): \(x_t\) is the fraction of type \(t\) seeded. For each rate matrix \(\Lambda\) in the support of \(\Pi\), start with activated fractions \(a_{t,0}=x_t\) on \(A\) and \(0\) elsewhere, and iterate
\[ a_{j,r+1} = a_{j,r} + (1-a_{j,r}) \left( 1-\exp\left[-\sum_{i\in T}\mu_i\Lambda_{ij}a_{i,r}\right] \right). \]
The objective is to maximize the expected final activated mass,
\(\mathbb{E}_{\Lambda\sim\Pi}\left[\sum_{j\in T}\mu_j a_{j,\infty}\right]\).
A computational version could ask for a rational allocation within additive \(\varepsilon\) of the optimum. The type-level rates are the continuum limit of independent cascade probabilities scaled as \(1/N\).
The authors could plausibly recognize this as their seed-selection problem in a high-multiplicity, partially observed regime. Their stated future work on generative models for unseen network structure gives the distribution over completions a natural foothold. This mirror would cover their partial-observation seed-selection model and the low-visibility empirical comparisons, but it would not mirror a named result or establish a complexity conclusion. My tentative expectation is continuum-specific hardness for the exact general optimization when \(\tau\) and the support of \(\Pi\) vary, due to the coupled nonlinear spread objective. Fixed-type or structured cases may admit useful algorithms. I would not infer hardness transfer from the discrete problem: proportional seed budgets and divisible seed mass change the decision space.
The weakest point is substantial: the type model smooths away the individual network structure that the paper’s boundary-node heuristics exploit, while the paper’s strongest gains occur with very few seeds, precisely where individual identities matter most. So this is a credible follow-up mirror only in an extensive-budget, exchangeable-network regime—not a positive anchor for the paper’s reported results.
There are no qualifying anchors to defeat: the paper’s only numbered result is Definition 1, for reverse reachable sets. Its NP-hardness statement is background cited to earlier work, and its own findings—including the reported 38% improvement—are empirical, not named complexity results. That is the strongest reason not to treat this paper as a positive case for the programme.
The proposed type-level optimization also loses the information that drives this paper’s contribution. Its heuristics use the observed boundary nodes’ particular neighborhoods to guess where influence can travel in the hidden graph. A complete type for that problem would need to preserve relevant network position and connections. On arbitrary observed graphs, that can leave nearly every node as its own type, so aggregation gives little high-multiplicity benefit. Coarser types such as role or region erase the node-specific boundary signal the paper exploits. A distribution over type-to-type rates can describe a block model, but that is a different network regime from the paper’s observed-subgraph problem.
The stated cascade recurrence has a further mismatch: it lets all already-active mass attempt to activate others again each round, whereas independent cascade gives each node one attempt per edge. Using newly activated mass would repair that issue, so it is not by itself a decisive objection. But the repair still describes a mean-field block model with divisible seed mass. The paper’s experiments emphasize very small seed sets; a fixed number of seeds has vanishing mass as the population grows. Scaling the budget with population size is a reasonable co-modification, but it changes the regime and does not mirror the paper’s strongest reported result.
A richer continuous model could retain heterogeneous observed neighborhoods or use a graphon or generative model. That might be a worthwhile new influence-maximization problem, especially for large, exchangeable populations. But preserving enough network detail to capture this paper’s signal risks making the type space grow with the population; imposing exchangeability instead changes the model. On the evidence here, the proposed mirror is not a strong mirror of the paper’s contribution.
The negative case is strongest as a judgment about this paper: it offers no named computational result for the programme to classify, and the suggested continuous formulation departs from the node-level partial-observation setting. The universal claim that no scenario could yield a worthwhile mirror is weaker. A well-designed block-population version could be sensible; the paper simply does not establish that it is the same problem.
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.