- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies verifiable influence maximization under the linear threshold model, where a platform proves that the returned seeds and their spread come from greedy maximization over its committed private network. The authors propose ZINK, a zero-knowledge proof framework that restricts the network to a DAG with fixed thresholds, prunes activated candidates through Merkle membership proofs, and is evaluated on graphs up to 5,000 nodes.
Critical strengths
S1. The problem is well motivated. Proving the greedy result over a committed but private network without revealing the network itself addresses a real tension in delegated influence maximization.
S2. The protocol is specified formally, with soundness, completeness and zero-knowledge arguments, and the implementation proves faster than general-purpose zkVMs with a constant-size aggregated proof.
Critical weaknesses
W1. The setting is overly restrictive in two ways. Almost no real social network is a DAG, so a large fraction of edges must be removed before commitment, which changes the original problem; and diffusion in practice is stochastic, whereas fixing the thresholds loses the approximation guarantee of greedy and degrades the expected influence. On top of that, the main speedup stems from this restricted setting itself, while the remaining optimizations, such as sparse graph representation, are standard practice in IM algorithms.
W2. The method is not scalable: even on simplified DAGs, proving a graph with only a few thousand nodes takes several days, and the cost grows super-quadratically with the graph size. That scale is far below real social platforms and standard IM benchmarks, and it is unclear whether ZINK can handle larger graphs. The paper also does not fully fit the scope of ICLR, since it involves no learning component.
Questions for authors
Q1. How much does cycle breaking cost in practice — what fraction of edges is removed on the datasets used, and how much do the seed set and spread change compared with the original graph?
Q2. How are the thresholds generated? Since the platform chooses them privately, could they be derived from verifiable public randomness?
Q3. What limits the size — memory or proving time? At the observed growth rate, how long would proving take at 10,000 nodes?