acceptodds
Withdrawn from ICLR 2027

ZINK: Privacy-preserving and Verifiable Influence Maximization in Social Networks

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Influence maximization (IM) is a fundamental problem in social networks, where the goal is to identify a set of seed nodes that can maximize the spread of influence. While many existing IM algorithms assume full access to the network structure or rely on online learning, these social graphs maintained by real-world platforms (e.g., TikTok) are often derived from sensitive user interactions and are proprietary. Despite having a strong incentive to help advertisers identify effective seed nodes, e.g., to promote their ad services, these platforms face significant constraints due to privacy concerns and intellectual property protections. As a result, the major users of IM algorithms often lack access to the underlying social network. To address this tension, we propose ZINK, a zero-knowledge proof (ZKP) framework for influence maximization. ZINK allows the platform to compute and prove the effectiveness of IM results (i.e., a set of seed nodes that maximizes influence spread) over a proprietary yet cryptographically committed social network, without revealing any information beyond the IM result itself. However, IM problem is inherently complex, and naïve solutions for ZKP protocols is often impractical for a non-trivial social network. Thus, we introduce several practical assumptions and optimizations that make ZKP for IM tractable and efficient. We implement ZINK and evaluate it on real-world datasets, showing that it scales to networks with thousands of nodes. Compared to commercial ZKVMs, ZINK manifests up to 42.72× speed up in proof generation with a moderate verification cost and constant proof size.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
zero-knowledge proof, influence maximization, social network analysis, privacy-preserving machine learning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_9T9bOpenReview ↗
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?

Reviewer_6Ky2OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a zero-knowledge proof-based mechanism for privacy preserving influence maximization. The paper considers a well-known influence maximization graph topology, where the goal is to select "k" seed nodes to maximize the total number of nodes influenced at the end. The paper considers a linear threshold model where a node becomes active (influenced) if the total influence from neighboring nodes exceed a threshold.

Critical strengths

In real-world settings influence maximization is considered in settings where data is usually sensitive, hence a privacy-preserving approach is important in this context.

Critical weaknesses

My main concern is that I think the paper is out of scope for ICLR. The core contributions are on the security application to a well-known data mining problem, rather than to representation learning or deep learning.

In particular, main contribution is to apply zero-knowledge primitives to a well-known greedy influence propagation/maximization algorithm (Algorithm 1). While the paper proposes some optimization enhancements (e.g., topological optimization via acyclicity, strategic pruning via activation analysis, privacy-preserving pruning via random permutation), I think the core contributions is the systems security application. I do not think the core contributions are to deep learning or representation learning.

I think the paper could be a better fit for a security or data mining conference.

Questions for authors

The paper demonstrates a nice application of using zero-knowledge primitives for privacy-preserving influence maximization, however, the core contributions are on the security application to the greedy graph-based influence maximization algorithm, rather than representation learning.

It would be helpful if the authors can clarify the relevance of the proposed work to the ICLR community, and the core contributions in this context.

Reviewer_vx5cOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes ZINK, a zero-knowledge proof framework for privacy-preserving and verifiable influence maximization. It enables a platform to prove the correctness of greedy seed selection without revealing its underlying social network. Several optimizations are introduced to reduce proof-generation overhead. Experiments demonstrate substantial speedups over general-purpose zkVMs on networks containing up to 5,000 nodes.

Critical strengths
  1. The integration of zero-knowledge proofs with influence maximization addresses an interesting privacy and trust problem.
  2. The proposed optimizations effectively reduce proof-generation overhead, demonstrating meaningful efficiency improvements over general-purpose zkVMs.
  3. The framework provides a new perspective on verifiable graph optimization without exposing sensitive network information.
Critical weaknesses
  1. Limited diffusion models. The framework only considers the Linear Threshold (LT) model under restrictive assumptions. Its applicability to other widely used models, particularly the Independent Cascade (IC) model, remains unclear.
  2. Limited experimental scalability. The experiments involve networks with at most 5,000 nodes, which is insufficient to demonstrate scalability for realistic large-scale social networks.
  3. Restrictive network assumptions. The reliance on directed acyclic graphs substantially limits practical applicability, since real social networks typically contain numerous cycles.
  4. Limited connection to machine learning. The main contributions focus on cryptographic verification rather than advances in influence modeling or learning algorithms, raising concerns about the paper's fit with ICLR.
Questions for authors
  1. Can ZINK be extended to the IC model and cyclic networks? What are the main technical challenges?
  2. How would the proof-generation time and memory requirements scale to networks with millions of nodes?
  3. Can the authors clarify the advantages of ZINK over alternative privacy-preserving IM frameworks in practical deployment scenarios?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.