d4-conf-aaai-2025-2677

My lead is a continuous, typed-population version of the paper’s robust dynamic influence maximization problem. It has a plausible regime: a large regional platform, public-health network, or misinformation response system where many people fall into a small number of exchangeable groups, campaigns reach percentages of groups, and contact patterns change between discrete update periods. For example, \(N\) people might occupy \(\tau\) feature and contact-role types, with \(\tau \ll N\). The update periods stay discrete; the population is what becomes continuous.

The anchor is Theorem 1, proved in this paper (with its proof deferred to the extended version). It guarantees that, with probability at least \(1-\delta_1-\delta_2\), at every time \(t\), the union \(S_t^c=\bigcup_{i=1}^{T}S_t^{(i)}\) of the algorithm’s candidate seed sets satisfies
\[ \min_{\theta\in\Theta}\sigma_{\theta,t}(S_t^c) \ge \left(1-\frac1e-\gamma-3\epsilon_1\right) \max_{S\subseteq V_t:\,|S|\le k}\min_{\theta\in\Theta}\sigma_{\theta,t}(S) -2\epsilon_2. \]
Here \(\gamma\) is the paper’s greedy-update drift term: for incremental updates it is the maximum, and for fully dynamic updates the sum, of the weighted objective loss caused by changes during successive greedy additions. The theorem requires
\[ \ell \ge d\left(\frac{2Bdmn}{\epsilon_2}\right)^d \log\left(\frac{2Bdmn}{\epsilon_2\delta_2}\right), \qquad T\ge \frac{2\log \ell}{\epsilon_2^2}, \]
and gives amortized running time
\[ O\!\left( \frac{n^2\ell^2T c_p c_r}{k^2\epsilon_1^3} \log n\, \log\left(\frac{nTk}{\delta_1}\right) \right). \]
The result combines robustness to a continuous hyperparameter with dynamic-network updates. It is an approximation result, not a hardness result. The paper’s hardness discussion in §3.4 is not stated as a numbered theorem, so I would not use it as an anchor here.

The mirror I would hand to a prover is Typed-Mass Robust Dynamic IC. Its instance has a finite type set \(A\) of size \(\tau\), with rational masses \(\mu_a^r\) summing to one at each discrete update period \(r\). A type specifies the node features and the network role that matter to the model: seed eligibility, if relevant, and a finite-support joint degree law describing its contact pattern with each type. At each period, a directed multitype configuration model generates the contact network from these masses and contact laws. The input also gives a hyperparameter set \(\Theta=[-B,B]^d\) and an IC transmission function \(H(\theta,x_{ab})\) for contacts from type \(a\) to type \(b\). Updates change type masses or contact laws, representing cohort entry and exit or changes in contact patterns.

A decision is a seed-mass vector \(z^r\), where \(0\le z_a^r\le\mu_a^r\) and \(\sum_a z_a^r\le\kappa\), for a campaign budget of fraction \(\kappa\) of the population. For each \(\theta\), let \(\Phi_{\theta,r}(z^r)\) be the limiting expected fraction of the population activated by the IC cascade when \(\lfloor Nz_a^r\rfloor\) members of each type are seeded:
\[ \Phi_{\theta,r}(z^r) = \lim_{N\to\infty} \frac{1}{N}\, \mathbb E[\text{number activated}]. \]
The model class requires these limits to exist. The problem is to compute, at every update period, a feasible \(z^r\) maximizing
\[ \min_{\theta\in\Theta}\Phi_{\theta,r}(z^r). \]
For an approximation version, the output must be within additive \(\varepsilon\) of that optimum at each period. The complexity question is whether that can be done with useful amortized update time in \(\tau\), \(d\), the degree-law support, and input bit length, rather than in the number \(N\) of people.

This is a real population continuization: \(\mu_a^r\) is a fraction of society, and \(z_a^r\) is a fraction of a type being seeded. Network structure is part of the instance because diffusion is relational; it is not being replaced by a type histogram alone. That is also the co-modification the mirror needs to remain faithful to the paper’s question. The types record the contact roles needed to define the stochastic network, while the hyperparameter uncertainty and robust spread objective remain. The paper’s authors could plausibly recognize this as their problem in an exchangeable, high-multiplicity network regime, though not as a mirror of arbitrary named-node graphs.

I expect a Class A result for additive approximation with fixed \(\tau\) and \(d\), and finite-support type contact laws: the limiting cascade is a finite-type process, and the hyperparameter dependence is low-dimensional and Lipschitz. Whether the runtime can be polynomial in \(\tau\) and \(d\), whether efficient guarantees survive fully dynamic changes to the contact laws, and whether hardness returns as the number of types grows are open questions. This is a prediction, not a consequence of Theorem 1.

The weakest point is the network model. In the paper, two nodes with identical features can still have very different neighborhoods, and those differences can control influence spread. Grouping people by features alone would lose information central to the authors’ problem. My mirror handles that by restricting attention to populations with exchangeable contact structure and including contact role in the type and contact law. That makes the regime plausible and the question precise, but narrower than the paper’s arbitrary evolving networks. If preserving arbitrary topology is essential to the authors, this mirror may not pass their recognition test.