acceptodds
Withdrawn from ICLR 2027

A more scalable algorithm for Fair Influence Maximization with Concave Functions

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

Abstract

The Influence Maximization (IM) problem seeks a set of seed nodes that maximizes information spread in a social network. While IM has found applications in several domains, such as viral marketing, advertisement, public health and political campaigns, its solutions often concentrate influence among a subset of demographic groups, raising fairness concerns. Fair Influence Maximization (FIM) addresses this issue by requiring that influence is spread equitably across all groups. In particular, the Concave Fairness Framework (CFF), based on the poverty-reward principle of prioritizing under-reached groups, provides a general approach to FIM. However, greedy algorithms needed for its realization require a large number of Monte Carlo simulations per step, making it impractical on large networks. We here focus on a continuous relaxation of CFF, and propose a scalable algorithm for it, called FIM-SPACE. Our method works with any concave fairness function admissible in the CFF, and its runtime scales independently of the number of Monte Carlo samples required by greedy methods. We provide theoretical guarantees on the approximation quality of our approach and experimentally show that pipage rounding of its fractional solution produces a discrete seed set whose fairness and influence are competitive with those returned by the greedy baseline. Our experiments show that FIM-SPACE achieves solution quality comparable to the greedy baseline on real-world social networks, while running up to faster. This means that on larger networks, where greedy methods become intractable, our approach remains able to return high-quality fair seed sets within reasonable time.

Primary area:
optimization
Keywords:
fair influence maximization, public health, algorithmic fairness, DR-submodular optimization, social networks

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_4fscOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses fairness in social influence maximization for convex fairness metrics by developing an algorithm for seed selection that scales ϵ\epsilon close to the greedy baseline without fairness.

Critical strengths

the paper addresses the computational complexity of fair IM, for concave fair function. In this regard I can see the value of the algorithm especially when it comes to large scale networks

Critical weaknesses

the paper is really slow in its flow, at page 4 I am still reading the introduction,

The bounds need Φ′\Phi' to be bounded and Lipschitz, but u0.1u^0.1 and the log function have Φ′→∞\Phi' \to \infty as u→0u \to 0. The guarantees are thereforenot valid for two of the three tested functions

Questions for authors

SNAP ground-truth communities overlap, yet the framework assumes a partition. How were overlaps resolved? In what sense is “fairness” across 600–1,300 structural communities comparable to fairness across demographic groups?

1 comment

As for the bound on Phi', we knew this issue and a workaround has been used in our code (see answer to Reviewer 1). We will report this workaround in the paper at the next revision.

As for SNAP community, we: 1) identified all structural (possibly overlapping) communities in the graph; 2) removed all community with less than 10 nodes, and the corresponding nodes; 3) assigned each node to exactly one of the community at which she belongs. We stress that this approach has been imported by previous works in which it was been adopted to prove the effectiveness of FIMM.

Reviewer_SwboOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes FIM-SPACE, a scalable algorithm for fair influence maximization under the Concave Fairness Framework (CFF). By introducing a continuous relaxation and exploiting DR-submodularity, the method supports a general class of concave fairness functions with theoretical approximation guarantees. Experiments on real-world networks demonstrate competitive fairness and influence spread while achieving up to 70× speedup over the greedy baseline.

Critical strengths
  1. Solid theoretical foundation. The paper establishes the DR-submodularity of the continuous formulation and provides theoretical approximation guarantees, strengthening the technical contribution.
  2. Improved generality. Unlike some existing fair IM algorithms that support only restricted fairness functions, FIM-SPACE accommodates a broader class of concave fairness functions.
  3. Promising scalability improvements. The experimental results demonstrate substantial runtime reductions compared with the greedy CFF baseline while maintaining competitive solution quality.
  4. Comprehensive experimental evaluation. The paper considers multiple fairness functions, real-world datasets, and different seed budgets, providing useful evidence of the method's effectiveness.
Critical weaknesses
  1. Moderate methodological novelty. The main contribution lies in improving the scalability of an established fairness framework. The distinction from existing continuous DR-submodular optimization methods could be further clarified.
  2. Mixed performance against efficient baselines. Although the method substantially outperforms greedy CFF, its advantages over FIMM are not consistent across all datasets. For example, FIMM performs better on Amazon under the power fairness function and is faster on DBLP.
  3. Limited discussion of practical limitations. The algorithm's performance depends on graph structure and fairness-function properties. These dependencies and their implications for practical deployment deserve further discussion.
Questions for authors
  1. What are the main technical differences between FIM-SPACE and existing stochastic continuous DR-submodular optimization methods?
  2. Can the authors explain the performance degradation on Amazon under the power fairness function and identify the conditions under which FIM-SPACE is most effective?
  3. How does the proposed method perform on substantially larger networks, especially when the number of protected groups increases?
1 comment
  1. Even if our objective function is DR-submodular, it is impossible to apply directly variance-reduced DR-submodular maximization (Lian et al.). The obstacle is in the gradient oracle. Indeed, Lian et al. assume a single-level objective accessed through an unbiased stochastic gradient. In our problem the gradient is a composed function and the value of the inner function is only accessed through samples. Because the outer function is non-linear evaluating it at a sampled utility gives a biased estimate. And since the natural stochastic gradient is biased, and a single-level method like Lian et al. does not apply off the shelf, since its analysis relies on the oracle being unbiased.

Removing this bias is exactly what the compositional framework in our analysis handles, controlling the bias introduced by the outer function. This composition step is the part borrowed from the compositional line (Jiang et al.). Still their line is not for DR-submodular maximization. So neither prior result applies alone: Lian et al. gives the DR-submodular maximization analysis but assumes an unbiased single-level oracle, while Jiang et al. handles the compositional bias but not the maximization guarantee. We combine the two, compositional bias control together with the DR-submodular maximization analysis, for the fair objective. Concretely, this is why our Theorem 1 reaches the same guarantees at the same rate as Lian et al.: we reuse their potential argument (our Proposition 1 and their Lemma 3.3), while the gradient-estimation part changes to handle the composition.

  1. We do not find surprising that FIMM outperforms FIM-SPACE on power fairness functions since the former is defined and optimized only for power fairness function, while the latter is a general framework designed to work for every fairness function. Rather it is surprising that on many works FIM-SPACE achieves results that are even better than FIMM. Anyway, we agree with the reviewer that a more careful analysis of the motivations behind one algorithm outperforming the other would be useful. We will add them in the next revision of the paper.

  2. We do not have experiments on larger networks. We also expect that our algorithm still require a large amount of time if applied to very large networks. Anyway, as pointed in the answers to reviewer 1, the goal of the paper is to provide a "more scalable" algorithm than state of art and this is clearly achieved, and this achievement allows to apply our algorithm in settings where it was not applicable before.

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

The paper studies fair influence maximization in social networks, where the goal is to select a limited number of seed nodes while balancing influence across different demographic or community groups. The authors propose FIM-SPACE, a scalable stochastic optimization algorithm that maximizes a concave transformation of group-level influence. By combining reverse-reachable set sampling, continuous optimization, and variance-reduced gradient estimation, the method aims to reduce the computational cost of existing approaches. The paper establishes a theoretical approximation guarantee for the continuous objective and evaluates the algorithm on synthetic and real-world networks. Experimental results suggest that FIM-SPACE can achieve competitive fairness and influence outcomes with substantial runtime improvements in several settings, although its performance varies across datasets and fairness objectives.

Critical strengths
  1. Extends the existing CFF to continuous optimization and establishes monotonicity and DR-submodularity.

  2. Combining reverse-reachable sampling with variance-reduced stochastic optimization addresses key computational bottlenecks in fair influence maximization.

  3. Demonstrates substantial runtime improvements over greedy baselines on several real-world datasets, while maintaining competitive solution quality.

Critical weaknesses
  1. The RoF values in Table 2 appear inconsistent with the definition in Appendix C. Several values exceed the theoretical upper bound of 1, and the reported RoF values systematically equal (1−PoF1-\mathrm{PoF}), although the two metrics have different definitions. These discrepancies warrant clarification, as they make it difficult to assess the reliability of the fairness comparisons on large-scale datasets.

  2. The power fairness function (ϕ(u)=u0.1\phi(u)=u^{0.1}) does not satisfy the bounded-derivative assumptions used in the analysis, and its derivative is undefined at zero, where Algorithm 1 is initialized. Furthermore, the continuous approximation guarantee does not directly translate into a guarantee for the expected discrete fairness objective after rounding. These issues limit the extent to which the theoretical results support the algorithm's practical performance.

  3. The experimental evaluations are limited to relatively small networks, raising concerns about the scalability of the proposed algorithms.

Questions for authors

Please clarify the problems indicated in Critical Weaknesses.

1 comment
  1. We acknowledge that there is a bug in the shown RoF bounds. Single experiments results shown bounds that are correctly within [0, 1], and often even much away from 1, but after the merge of these results the strange numbers in Table2 comes out. At the moment we have been not able to fix the bug in the code, so we are going to withdraw the paper and to resubmit it only after the issue has been fixed.

  2. We knew about the issue. Indeed the code for the power fairness function starts from u close to zero, but still guaranteeing derivative to be bounded. In the next revision, we would make explicit this workaround.

  3. We agree that the algorithm may not be scalable to very large networks, and indeed, we point out this issue as to be addressed in future works. Nevertheless, our claim is that our algorithms is "more scalable" than previous ones, and this is undoubtedly proved by our experiments. We also point out that the interest towards fair influence it is mainly motivated by application of influence maximization in real-world social networks, mainly for public health objectives, more than its application in online social networks: the former networks usually have size that is comparable with the ones of the networks on which we run our experiments.

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

Related papers

Discussion (0)

Sign in to comment.