| paper | DiffIM: Differentiable Influence Minimization with Surrogate Modeling and Continuous Relaxation |
| authors | Junghun Lee, Hyunju Kim, Fanchen Bu, Jihoon Ko, Kijung Shin |
| venue | AAAI 2025 |
| 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 \(\mathcal{T}\), rational type masses \(\mu\), seed fractions \(s_a\), type-to-type contact rates \(\lambda_{ab}\), activation probabilities \(p_{ab}\), horizon \(H\), blocking costs \(q_{ab}\), budget \(B\), and \(\varepsilon>0\), choose retained-contact fractions \(\rho\in[0,1]^{\mathcal{T}\times\mathcal{T}}\) satisfying \(\sum_{a,b}q_{ab}(1-\rho_{ab})\le B\) to obtain an \(\varepsilon\)-optimal value of \(\sum_b z_{b,H}\), where \(x_{b,0}=s_b\mu_b\), \(z_{b,h}=\sum_{\ell=0}^{h}x_{b,\ell}\), and \(x_{b,h+1}=(\mu_b-z_{b,h})\left(1-\exp\left(-\sum_a\lambda_{ab}p_{ab}\rho_{ab}x_{a,h}/\mu_b\right)\right)\).
A finite-type exchangeable stochastic-contact IC population: \(\mu_a\) is the mass of type \(a\), \(x_{a,h}\) is newly influenced mass, \(\rho_{ab}\) is the retained fraction of \(a\)-to-\(b\) contact mass, and the objective is total influenced mass under a blocking budget.
For arbitrary identity-level graphs, \(\mu\), \(\lambda\), and \(p\) do not determine multi-step influence because neighborhood overlaps, components, and path correlations are lost; the proposed recurrence therefore relies on an additional exchangeable-mixing assumption.
fatal: False
The mirror covers Problem 1 and Theorem 1 in a typed exchangeable-contact regime; it leaves Theorem 2, Lemma 1, the surrogate GNN analysis, gradient-selection schemes, and the empirical comparisons untouched.
The strongest honest case rests on one anchor: Theorem 1, “Influence minimization (Problem 1) is NP-hard.” This theorem is proved in the paper, in Appendix A.1. I would not use Theorem 2 as a second anchor: its non-submodularity claim is cited from Yan et al. (2019), and it is not itself a complexity classification.
My lead mirror is Typed Continuum IC Edge-Blocking, or \(\mathrm{TC\text{-}IMIN}_{\infty}\).
The regime is a large platform or public-health contact system with \(N\) users but only \(\tau\) exchangeable diffusion-relevant types, where \(N\gg\tau\). A type includes everything the model uses: seed status, outgoing contact intensities, activation probabilities, incoming contact class, and the cost of disabling that contact channel. Thus two users of the same type are interchangeable. Plausible examples are repeated local communities, account-role classes, or large cohorts of users subject to the same recommendation and moderation policy.
The society is a rational mass vector \(\mu\in\mathbb{Q}^{\tau}\), where \(\mu_a\) is the fraction of users of type \(a\). Let \(S\subseteq T\) be the seed types. For every ordered pair of types \(a,b\), let \(\lambda_{ab}\) be the expected number of contact attempts made by one active \(a\)-user toward type \(b\), and let \(p_{ab}\) be the probability that such a contact activates its target.
The intervention is a retained-contact vector \(\rho\in[0,1]^{T\times T}\). Here \(\rho_{ab}\) is the fraction of the \(a\)-to-\(b\) contact mass retained; \(1-\rho_{ab}\) is the fraction blocked. Given rational costs \(q_{ab}\) and budget \(B\), feasible interventions satisfy
\[ \sum_{a,b}q_{ab}(1-\rho_{ab})\le B. \]
This is population continuity: the intervention removes mass of a large class of links, rather than choosing among named individual edges.
For a finite horizon \(H\), define \(z_{a,h}\) as the cumulative influenced mass of type \(a\) by time \(h\), with \(z_{a,0}=\mu_a\) for \(a\in S\) and \(z_{a,0}=0\) otherwise. In the \(K\to\infty\) clone limit, where each type contains \(K\mu_a\) exchangeable users and contacts are uniformly distributed within target types,
\[ z_{b,h+1} = z_{b,h} + (\mu_b-z_{b,h}) \left( 1- \exp\left( -\sum_{a\in T} \frac{\lambda_{ab}p_{ab}\rho_{ab}}{\mu_b} (z_{a,h}-z_{a,h-1}) \right) \right). \]
The continuous problem is:
\[ \min_{\rho\in[0,1]^{T\times T}} \quad \Phi_H(\rho):=\sum_{b\in T}z_{b,H} \qquad \text{subject to } \sum_{a,b}q_{ab}(1-\rho_{ab})\le B. \]
In a standard finite-precision version, the instance also contains rational \(\varepsilon>0\), and a solution is a feasible \(\rho\) whose influence is within \(\varepsilon\) of the optimum. The unbounded-horizon version replaces \(z_{b,H}\) by the least fixed point \(z_{b,\infty}\).
This is recognisably the paper’s problem. It preserves the same IC diffusion semantics, the same target—minimise expected spread—and the same action—block links. The difference is that the network is now given by a distribution over exchangeable users and type-level contact channels. The recurrence is not merely the paper’s GNN surrogate: it is the law-of-large-numbers limit of a finite population of cloned users. The paper’s \(\rho\)-relaxation therefore supplies useful methodological precedent, but it is not itself the ChoCo mirror; the primary continuous object here is \(\mu\).
For the general problem, I would expect continuum-specific hardness, rather than simply claiming that Theorem 1 transfers. The discrete NP-hardness may disappear because individual edge choices and integrality have been removed. But the resulting finite-dimensional problem is still a genuinely computational optimization problem: changing one retained contact rate changes later exposure, which changes the marginal value of every other contact rate. For \(H\ge2\), the objective is a coupled nonlinear cascade over \(\tau^2\) continuous variables. The likely source of hardness is therefore the interaction among type-level contact masses, not the number of individual users.
That expectation generates useful subsidiary questions: whether bounded \(\tau\) or \(H\) gives an FPT approximation scheme; whether acyclic or low-rank contact matrices yield polynomial algorithms; whether the objective has any usable continuous analogue of submodularity; how accurately finite-\(N\) edge deletions round a solution \(\rho\); and whether DIFFIM’s gradient rule has a provable approximation guarantee in this typed setting.
The scope is deliberately narrow. This mirror covers Problem 1 and Theorem 1 only. It does not claim to continuize the GNN architecture, the training procedure, the experimental Pareto comparisons, or the paper’s other diffusion models.
The weakest point is that the original paper permits arbitrary identity-level graphs, whereas this mirror assumes exchangeable users and bulk link interventions. If the authors regard arbitrary individual topology as the essential scientific object, they may reject the typed model as a different problem. The answer is that the paper’s formal anchor is influence minimization under IC, not a particular real-world graph: a large typed contact network is a legitimate high-multiplicity instance regime of that formal problem. Still, the loss of identity-level topology is a real limitation, and it is why I would present this as one strong continuous mirror—not as a claim that every instance of the paper admits one.
The proponent’s only anchor is Theorem 1, and it does not survive as stated. The problem is not that the continuous version might become easy; that would be a valuable Class A result. The problem is that \(\mathrm{TC\text{-}IMIN}_{\infty}\) is not a high-multiplicity version of the theorem’s computational object.
In the paper, influence is determined by the full identity-level graph. A node’s effect depends not merely on its number of contacts to each class, but on which particular nodes those contacts reach, how neighborhoods overlap, and which paths share edges. Consequently, \(\mu\), \(\lambda\), and \(p\) do not determine \(\sigma(S;G,p)\). Graphs with the same type masses and the same type-to-type contact intensities can have different multi-step influence because they have different components, overlaps, and path correlations. The proposed recurrence is therefore not the law-of-large-numbers limit of the paper’s arbitrary graph model without additional random-mixing assumptions; it is the equation of a new mean-field epidemic model.
The “complete type” repair makes this worse. To preserve the original IC objective, a type would have to contain enough of a node’s rooted network position—and, for finite-horizon influence, enough joint neighborhood information—to determine reachability. For arbitrary graphs this produces essentially one type per relevant position, destroying the \(N\gg\tau\) regime. Repeated local communities do not solve the issue: their same-copy relations are not captured by type marginals. Adding community labels, motif structure, or a graphon restores the missing topology, but then the computational input is a network relation or a distribution over whole network motifs, not a society distribution over agent types.
The intervention also changes the problem. The paper chooses a deterministic set of \(b\) named edges. The proposed \(\rho_{ab}\) chooses a fraction of a type-channel and replaces \(p_{ab}\) by \(p_{ab}\rho_{ab}\). That multiplication is valid for independently randomized blocking in a homogeneous mixing model, not for arbitrary deterministic edge deletion: correlated deletion patterns can change reachability even when the same fraction of edges is removed. Thus \(\rho\) is a bulk link-control variable, not a mass representation of the paper’s feasible edge sets. Indeed, the paper already introduces essentially this kind of continuous relaxation of edge decisions; it is continuity of the intervention space, which ChoCo expressly distinguishes from continuity of the population.
The strongest possible repair would retain a graphon or a repeated-motif structure and ask for edge-blocking control over it. That could be worthwhile network science. But it is either an infinite-dimensional network-continuum problem, a finite-block mean-field model, or a configuration problem over whole motif-level deletion plans. None is a population-only continuization of Theorem 1. In the repeated-motif case, the original hard graph remains the real computational object and the population mass merely records how many copies exist; in the graphon case, the continuous object is the contact relation rather than the society.
So the proponent has proposed a plausible new mean-field influence-control programme, but not a faithful ChoCo mirror. Since the paper supplies no second named computational anchor, defeating Theorem 1 defeats the entire positive case. The negative case is weakest only in the broad informal sense that graphon and repeated-community models may independently be interesting; they do not, however, establish a worthwhile continuous mirror of this paper under the programme’s population-continuization requirement.
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.