Fair Online Influence Maximization
Authors: Xiangqi Wang
Shaokun Zhang
Jose Efraim Aguilar Escamilla
Qingyun Wu
Xiangliang Zhang
Jian Kang
Huazheng Wang
Venue: Accepted by TMLR ()

Abstract: Fair influence maximization in networks has been actively studied to ensure equity in fields like viral marketing and public health. Existing studies often assume an offline setting, meaning that the learner identifies a set of seed nodes with known per-edge activation probabilities. In this paper, we study the problem of fair online influence maximization, i.e., without knowing the ground-truth activation probabilities. The learner in this problem aims to maximally propagate the information among demographic groups, while interactively selecting seed nodes and observing the activation feedback on the fly. We propose Fair Online Influence Maximization (FOIM) framework that can solve the online influence maximization problem under a wide range of fairness notions. Given a fairness notion, FOIM solves the problem with a combinatorial multi-armed bandit algorithm for balancing exploration-exploitation and an offline fair influence maximization oracle for seed nodes selection. FOIM enjoys sublinear regret when the fairness notion satisfies two mild conditions, i.e., monotonicity and bounded smoothness. Our analyses show that common fairness notions, including maximin fairness, diversity fairness, and welfare function, all satisfy the condition, and we prove the corresponding regret upper bounds under these notions. Extensive empirical evaluations on three real-world networks demonstrate the efficacy of our proposed framework.

Published in Transactions on Machine Learning Research (06/2025)
Fair Online Influence Maximization
Xiangqi Wang"1, Shaokun Zhang?; Jose Efraim Aguilar Escamilla?, Qingyun Wu?, Xiangliang Zhang', Jian Kang", Huazheng Wang
University of Notre Dame
Pennsslvonia State University
Oregon State University
University of Rockester
Reviewed on OpenReview:
net/ forum? id= R1N *Corresponding author: xvang76ênd. edu, huazheng, wang@oregonstate edu
Abstract
Fair influence maximization in networks has been actively studied ensure equity fields like viral marketing and public health. Existing studics often assume an offline sctting, mcaning that the learner identifies set of seed nodes with known per-edge activation probabilities. In this paper, we study the problem of faár online influence mazimization, iee, without knowing the ground-truth activation probabilities. The learner in this problem aims to maximally propagate the information among demographic groups, while interactively selecting seed nodes and observing the activation feedback on the fly. We propose Fair Online Influence Maximization (FOIM) framework that can solve the online influence maximization problem under wide range of fairness notions. Given a fairness notion, FOIM solves the problem with combinatorial multi-armed bandit algorithm for balancing exploration-exploitatioo and offline fair influence maxinization oracle for seed nodes selection. FOIM enjoys sublinear regret when the fairness notion satisfies two mild conditions, i.e., monotonicity and bounded smoothness. Our analyses show that common fairness notions, including maximin fairness, diversity fairness, and welfare function, all satisfy the condition, and we prove the corresponding regret upper bounds under these notions. Extensive empirical evaluations on (hree real-world nerworks demonstrate the efficacy of our proposed framework
1 Introduction
Influence maximization (IM) (ermpe et al. 2003) has been extensively studied with applications in viral marketing (Chen et al., 2010 and public health (Valente & Pumpuang) 2007 Yaday et al., 2018). Classic influence maximization aims to select a set of seed nodes a social network to maximize the spread of influence (i.c., expocted number of inffuenced nodes). The problem is typically formulatod as a stochastic diffusion process (Kempe al., 2003 Csókás & Vinkó 2022) in directed graph, with the edge weights representing the probabilities that the source nodes can activate target nodes.
Recently, there has been an increase in concerns regarding algorithmic fairness motivated by recent studies
on fair influence maximization (Farnadi et al. 2020 Tsang el. al. 2019 Fish et al. 2019 Becker et al. 2020
Rahmattalabi et al. 2021 Feng et al. 2023 These studies have primarily consider egalitarian utility (the number of influenced nodes across demographic groups) over the classic utilitarian utility (the total number of influenced nodes). With advent of official regulations such as GDPR (European Parliament & Council of the European Union), fair algorithms that control discrimination have received renewed interest. For example, consider health organization aiming to provide information related to preventive care against pandemicc to as many people possible. Due to limited resources, the health organization is expected to select a set of influencers (seed nodes) who would propagate the vital information to others in a social network. By following egalitarian utility, an ideal choice of influencers would ensure a certain portion of at-risk individuals from some minority (or protected) group will see the information.
"The code be found httpp: pettpa://githen hwt.://b...co/iiingggggn/////

---

Published in Transactions on Machine Learning Research (06/2025)
To date, solutions to fair infiuence maximization almost exclusively assume offinne setting. meaning that the activation probabilities are known a priori (Farnadi et al. 2020 Rahmattalabi et al. 2021: Tsang et al.) 2019; Rahmattalabi et al.) 2019). However, the activation probabilities may not be fully observable in many real-world applications. Prior works in fair offlie influence maximization often obtain this information via simulations over data collected ofline without fairness considerations (Rahmattalabi et al. 2021 p.
Consequently, the estimated probabilities could likely be inconsistent for individuals in a minority group due to bias introduced in the offline data selection (e.g., fewer logged activations for individuals from the protected group). Based on the estimated information, this discrepancy can result in sub-optimal seed selection for fair offline influence maximization. This motivates the study of fair online influence mazimization, whose goal is to estimate the activation probabilities by repeatedly interacting with the network to maximize the information diffusion among demographic groups.
There are three key challenges in fair online influence maximization that must be addressod to develop efficient algorithms. The first challenge deals with the (i.e., across different. demographic groups). Second, the combinatorial nature of the influence maxinization problem makes finding the optimal seed set an NP-hard problem (Kempe et al. 2003). Thus, it is non non-trivial to solve the NP-hard combinatorial problem with a good exploration-oxplotaaieee trade-off under the fairness constraint.
tradcoff under a fairness constraint
The third key challenge to fair online influence maximization is a theoretical challenge. While bandit- based solutions are natural for online influence maximization without fairness considerations, exlending their theoretical analysis to fair online scenarios introduces complications. Rigorous regret analyses for bandit-basee solutions typically require the reward function to satisfy specific conditions such as submodularity (Hazan &
Kale 2012 Chen et al. 2018 Perrault et al. 2020), monotonicity, and bounded smoothness (Chen et al., Wang & Chen 2017a Wen et al. 2016). However, when considering an egalitarian reward function it is important to ensure the aforementioned characteristics hold for target fair metric.
2014
In this paper, we tackle both algorithmic and theoretical challenges and propose a framework named FOIM for Fair Qnline Influence Maximization. To lackle the algorithmic challenge, FOIM first runs a combinatorial multi-armed bandit (CMAB) algorithm for parameter estimation and balancing exploration-esplootttiio on the fly, and then applics an offline fair influence maximization oracle (Tsang ct al., 2019 Farnadi et al. 2020 to lackle the NP-hard problem of selecting seed nodes. FOIM allows a wide range of fairness constraints (Tsang et al. 2019 Rahmattalabi et al.) 2021], and can incorporate any desired CMAB algorithm. We provide theoretical guarantees in terms of sublinear regret bounds on the FOIM framework under various group fairness notions. In a nutshell, our theoretical results generalize existing analyses of CMAB-based online influence maximization without fairness considerations. A key insight of our analysis shows that the common group-fairness reward functions such as maxmin fairness (Tsang et al. 2019), , diversity fairness (Tang ct al. 2019 Rahmattalabi et al., 2021), and welfare functions (Rahmattalabi et al. 2021]. all satisfy the monotonicity and bounded smoothness conditions, which allows us to leverage existing analysis of CMAB algorithms and online influence maximization (Chen et al. 2014 Wen et al.] 2016: Wu et al. 2019).
We study the fair online influence maximization problem, whose goal is to improve the quality of activation probabilities and seed node selection on the fly. To the best of our knowledge, this is the first study on fair online influence maximization problem.
We propose a generie FOIM framework that uses a CMAB algorithm for balancing exploration-exploitttio and an offline fair influence maximization oracle for seed nodes selection.
Theoretically, show that common group fairness notions for influence maxinization all satisfy mono- tonicity and bounded smoothness conditions and prove the corresponding sublinear regret upper bound for each fairness notion.
We conduct extensive experiments on three real-worke datasets. We compare the performance of FOIM with different CMAB algorithms and fairness oracles. Experimental results confirms the effectiveness of FOIM under different fairness notions.
2

---

Published in Transactions on Machine Learning Research (06/2025)
2
Related Work
Fair influence maximization aims to maximize the influence spread with consideration of fairness
Farnadi
et al.
2020
Tsang et al.; 2019 Fish et al.
2019 Becker et al. 2020; Rahmattalabi et al. 2021 p.
Existing
works
on fair influence maximization mainly consider two types of fairness notions: group fairness Tsang
ct al.
2019
Rahmattalabi et al.)
2021 Farnadi et al. 2020 and individual fairness (Fish et al. 2019 Becker
itt al.,
2020
For group fairness, Tsang et al. (2019) propose multi-objective Frank-Wolfe based algorithm
to ensure maximin fairness and diversity fairness. Rahmaltalabi et al. introduce the welfare function which
generalizes maximin fairness and diversity fairness, as fairness notion.
Farnadi et al. 2020 utilize mixed integer programming for fair influence maximization with respect to four different fairness notions (equality, equity, maximin fairness, and diversity fairness). For individual fairness, Fish et al.] 2019) use the welfare function to maximize the minimum probability of individuals receiving the information. [ocker ct al. achieve individual fairness in influence maximization through randomization. Our work is substantially different. from these two lines of research. Compared with [Tsang et al. (2019);
Rahmattalabi et al. (2021); Farnadi et al. (2020) that study influence maximization in offline setting, we consider an online setting where the activation probabilities are not given, and we aim to estimate the activation probabilities by interacting with the network. Additionally, Fish et al. (2019) and Becker et al. (2020) study individual fairness which is a different fairness notion to the focus of this paper, i.e., group lairness.
Online influence maximization assume that the activation probabilities are not known a priori. Several works have been proposed to solve online influence maximization problems with combinatorial multi-armed bandit, including CUCB (Chen et al. 2014), IMLinUCB (Wen et al., 2016) and IMFB (Wu et al. 2019). The key idea is to regard the propagation probability of edges in the graph as the arms of bandits and learn the combinatorial set of arms as super arm in the online setting. More specifically, CUCB (Chen et al., 2014), one of the most fundamental CMAB-based online inffuence maximization algorithms, is an extension of the upper confidence bound (UCB) algorithm (Auer el al. 2002) to the combinatorial setting that achieves asymplotic optimal regret. IML (Wen et al., 2016) applies LinUCB (Li et al. 2010), a classic contextual bandit. state-of-the-an online influence maximization algorithm, which takes network assortativity and factorizes the edge weights into latent factors. It is worth noting that both ICB and IMFB are based on CUCB and can achieve asymptotic optimal
algorithm, for online influence maximization. IMFB (Wu al.) 2019)
regret. However, none of them CCen et al. 2014 Wu et al.] 2019 Wen et al. 2016) take fairness into consideration, whereas our work aims to solve online influence maximization under fairness constraints.
3 Background
Influence maximization. The classical Influence Maximization (IM) problem formulation considers a directed graph G = (V; F),,, where and represent the set of nodes and edges in the graph, respectively. The graph is further equipped with edge weights μ == M2, Mi Vi E (1...., [E]}, p E [0, 1] for any edge e; E E. These weights represent. the probability that an active node will influence some neighbor node according to some diffusion model. In our case, exclusively consider the independent cascade (IC) model (Kempe et al. 2003).
Formally, solving an IM problem involves choosing some seed set S E 2 with cardinality constraint |S] K influencing the largest number of nodes under some diffusion model.
S == arg max IG(S) s.t. |8|5 K, SE2V
(1)
where S* represents the optimal seed set maximizing influence spread for graph G, and Ia(S) is the expected number of influence nodes achieved by seed set S.
Influence maximization is a well-known NP-hard problem (Kempe et al. 2003 Nemhauser et al., 1978
This result, mainly due to the combinatorial nature of finding a seed sct, makes finding an optimal solution computationally challenging. To circumvent this problem, most proposed learning algorithms follow a 'two-step' approach. First, the learning algorithm estimates the edge weights f using previously collected
3

---

Published in Transactions on Machine Learning Research (06/2025)
data. Then, algorithm (known as oracle) chooses an approximate seed set S. The key to attaining computationally tractable algorithm is to assume that the oracle algorithm is an (a, papprropproinn oracle. Definition 1 ((a, Approxxxiiiiiiin Oracle (Chen et al. 2014)). An (a, p)-ppppoiinaaionn Oracle, in the context of Influence Maximization, is defined as any algorithm that can produce a seed set $ E 2 given estimated edge weights ft obeying the following probabilily:
Pr 2a 28.
where (S) is the reward function corresponding to the chosen seed set given edge weights jt.
Intuitively, an (a, apppppooiintooon oracle is allowed to produce seed sets that deviate by a fraction a from the thcoretical best with probability at least B. This helps in reducing the computational burden the oracle algorithm by accepting approxinate solutions. For example, in greedy oracle ar is set as 1- with B set as 1.
Online IM. Online IM is referred as not assuming the known per-odge activation probability beforchand, in contrast to offline influence maximization. Specifically, aims to simultaneously seek the influential nodes (exploitation) and estimate the social network (exploration). And the combinatorial multi-armed bandit (CMAB) framework is natural choice that can balance the exploration-exploitatie trade-off (Wen al.,
2016
Wu et al. 2019: Chen et al. 2014 Vaswani & Lakshmanan 2015
Given the graph G and cardinality K, an online solution typically follow the following procedure. At each step 4 the learner first chooses a set of seed nodes S, E V with cardinality limit K based on historical information, by performing offline IM (regardless of fair or not) algorithms according to the current estimation the graph. Here, these algorithms regard the solution obtained as an ORACLE. We denote it as S, = ORACLE(G, Pr. K), where de represents the estimation of per-edge activation probability at step Then, the learner updates the estimation for the graph with S, as the seed set. (S,) is utilized to represent the corresponding reward, which might be modified with fair constraints. The learner's objective is to minimize the expected cumulative regret by finding a sequence of seed nodes ò over a finite T rounds of interactions:
Σ rr (S) - Tp (s.) II.....
Regret =
(3)
Note that the reward function (Se) is a general notation that can represent not only influence spread but also other reward functions such as fair IM reward.
Fairness in IM. Given its applicability to worldworld problems, the IM problem highlights fairness as a major concern algorithm design. Previous litcrature has introduced various fairness metrics like maximizing minority group welfare in graph through IM process, but incorporating fairness in an online sotting remains challenging due to the lack of consensus on effective fairness integration. This paper presents algorithmic design framework that generalizes fairness measures while enabling theoretical regret analysis within the Combinatorial Multi-armed Bandit (CMAB) framework, specifically designed for online applications.
4 The Fair Online Influence Maximization (FOIM) Framework
We begin the presentation of our novel FOIM framework by exlending our formulation of influence max- imization (IM) to include fairness. Starting from a set of seed nodes S, we use Ia,c, (S) to denote the expected number of influenced nodes that belong to not necossarily disjoint group (or community) C.. In one diffusion proces:] we use the set u {ui, u2, ddve to represent the probability of each node being activated. We employ u = [Cal
(S) to represent the expected fraction of the nodes being activated in group C. Additionally, given graph G and any feasible set of seed nodes S, we use Es to denote the set of edges in the subgraph induced from graph G, where the subgraph is formed by seed nodes S. We also employ Eg to represent the set of edges reachable from seed set in one IC diffusion process.
We refer diffusion process as a single cycle influence within network G, where influenced nodes allowed attempt. influence neighhor nodes once.
4

---

Published in Transactions on Machine Learning Research (06/2025)
Formally, given graph G, fair influence marimization aims to find set of nodes S under cardinality constraint K, which maximizes the influence spread, where Ta,c, (S) denotes the influenced nodes by some seed set S with respect to community C..
S = arg max ISISK CIEC
E Ia,c(S)
(4)
Using slight abuse of notation, we let (kk be the maximum number of influence nodes that can be achieved with cardinality constraint k
lc(k) = Σ
(8,) s.1. s
(5)
CLEC
4.1 Fairness Constraints
In this section, we demonstrate how our FOIM framework effectively incorporates various fairness constraints, covering most of the fairness aspects introduced in prior literature. After presenting the studied fairness metrics, we propose the FOIM algorithm. In addition, we provide discussion of FOIM on TPM condition in Appendix A.13
FOIM with maximin fairness. Maxmin fairness proposed by Tsang et al. 2019 Diana et al. 2021
measures the influence of the minimal group in the influence maximization algorithm. Given any feasible seed nodes S, the IM reward function with maximin fairness constraint
Ia,c, AC,E0 |C&]
maxminn j
(5) min
(6)
is the proportion of the expected number of influenced nodes for group C2 to its population, and j denotes the edge weights in the graph. Searching the seed nodes with this reward function could be described
[c. where Ia,c, (S)
$ arg max (ena)mmn(()) SES
FOIM with diversity fairness. The key idea of the diversity fairness constraint from Tsang et al. (2019) is that no group benefits more by leaving the IM game and allocating its proportional resources internally, For the i-th group C, we define k; /|C|//|CC as the fair allocation of influenced nodes in C, based on group size, where K is the seed budget. Let G[C₁] denote the subgraph induced by nodes in C₁, while keeping their original connections in G. To satisfy the diversity fairness constraint, the selected seed nodes S should satisfy
Ic.c, (8) 2 (k)), AO2 E C.
Then given any feasible seed nodes S and graph G (V; E;,,, the IM reward function with diversity fairness is defined as
Ec,ec la.. (S) if Equation g
holds
diversiby
(9)
0
otherwise.
And searching the seed nodes for Eq. 9 is
$ = arg max diversityy (S)).
(10)
FOIM with welfare function. The welfare function (Rahmattalabi et al. 2021 a reward function that generalizes multiple fairness notions IM, including marimin fairness and diversily fairness. encourages uniform influence among different groups, with the trade-off between fairness and efficiency adjusted by a hyperparameter Mathematically, the welfare reward function is
Σ (19)))1))) /0,
a +
welffare()
3EC
(11)
Σ
log_lo,(
if
5

---

Published in Transactions on Machine Learning Research (06/2025)
where ut denotes the expected fraction of the influenced vertices of community c, and vf 2 0, Ve C. Notably, when a + -0; equation
11 is equivalent to the reward function for maximin fairness (Equation G
4.2 FOIM Algorithm
Now, we introduce the proposed Fair Online Influence Maximization (FOIM) framework, which solves fair online influence maximization problem with wide range of fair rewards. Notably, the proposed FOIM framework is a general framework that supports the integration of any combinatorial multi-armed bandit. (CMAB) algorithm under certain conditions. In Section 5 we prove that these conditions are naturally satisfied in common fair rewards and demonstrate that FOIM could achieve sublinear regret, (Chen al.
2014 Kveton al., 20140. We present the FOIM framework in Algorithm !
Algorithm 1: Fair Online Influence Maximization (FOIM)
1: Input Graph G, time budget T, seed nodes size K, reward function (S()), edge weight estimator of CMAB A(G, rt) fair oracle FairORACLE(G, Pr, K).
Initialize t for in (1...., T do ii + A(G, (I-,, // estimate edge weights
5: S-=FaiOORACEE(G iu, K) // obtain seed nodes
6: Ti rr,))(())) // obtain rewards
7: end for
For instance, if CUCB (Chnn et al., 2014] serves as backbone A, P estimated independently with UCB (Stone 2010) algorithm each time step. If belongs IMLinUCB (Wen et al. 2016), á estimated with the contextual bandit LinUCB algorithm with an additional imput of edge features. Another worth mentioned imput is the fair oracle FaiORRALEEGG, fi, K), which identifies the optimal seed nodes based the current estimated edge weights. Actually, any fair offline CMAB algorithms with (a. 8) approximation guarantee could be utilized, such as multi-objective Frank-Wolf, algorithm (Tsang et al. 2019) and Mixed
Integer Programming (MIP) (Farnadi et al. 2020
Given the graph G and cardinality K, FOIM runs with the following procedure: at each step t, CMAB algorithm estimates the edge weights f according the regret rı-1 and Ωt-1 from at last time step. Then, FairORACIE obtains the seed nodes based the current. estimated edge weights fúr and calculate the regret. for the obtained seed nodes. The procedure repeats until the given time budget T is reached. In addition, give the time complexity analysis of FOIM framework in Appendix A.12
5 Theoretical Analysis
It has been demonstrated that CMAB algorithm will achieve sublinear regret bound when the corresponding reward function satisfies both monotonicity and bounded smoothness conditions (Chen et al.) 2014 Wu et al. 2019 Wen et al. 2016). Here we first show the monotonicity and bounded smoothness conditions for fairness metrics below.
Condition 1. Given graph G = E)), we require the following two conditions on the fair online IM reward rS) for FOIM:
Monotonicity, Given any feasible seed nodes S, the expected reward (S) is monotonically nondecreasing with respect to the edge weights of the graph, i.e., if Vi E (1...., El.. μ4 I pig then we have r,((S) S (S).
-Bounded smoothness. There exists a continuous, strictly increasing (thus invertible) function f(.) with S(0)- 0, called bounded smoothness function, such that for two and pi, and for any A > O, we have (S) - (S) f(A), if max/p 4. A.
iEEs

---

Published in Transactions on Machine Learning Research (06/2025)
Note that FOIM is general framework for fair online influence maximization based on CMAB algorithms. Specifically, we prove that the reward function with multiple fairness constraints satisfies the monolonicity and bounded smoothness conditions, implying the generality of FOIM being the solution to fair online influence maximization with different fairness constraints.
5.1 Fairness Analaysis
Maximin fairness. In Lemmal 1 we show that the reward functions for fair online influence maximization with maximin fairness satisfy Condition ] i.c., monotonicity and bounded smoothness.
Lemma 1. Given graph G (V; E; p), the IM reward function with marimin fairness constraint satisfies monolonicily. It also salisfies bounded smoothness with smoothness function f(x) = |E|z.
Proof. We first prove the monotonicity and then show the reward function satisfies bounded smoothness.
P1 Monotonicity, Given two graph G and G' with the set of edge weights and şl respectively, if Vi E (1...., Bl, H4 $ M4 it is easy to have AO, E C:
(S, (S).
(12)
Let C2 and Cp be the groups receiving the minimum proportional influence in G and G' respectively:
Ia,c, (S)
Iacc, (S)
= arg min CjEC' |c,l
arg min CjEC
(13)
|Cyl
Regardless of whether i = i' or i i V we have:
Is)c,(S)
Ia,c,
Ia Ia.o,
<
<
(14)
Cil
Cppl
Crpl
Therefore:
(mazinnS) = (S)
marminn (5).
(15)
|Cyl
12'
Thus, the monotonicity property rp (mazmii(S) (S) < p (mmmmmi is proven.
P2 Bounded smoothness under f(x) = EEx. Without loss of generality, suppose there exists graph G and G' with edge weights μ and μL, respectively, Vi E μ² = #4 + A, 0. According to monotonicity of the reward function, we have r y.masmin (S) S " (azzmin(S) for any feasible seed nodes S. For any edge i= (v. u) E És, the increase of activation probability between and every node reachable from in G' brought by i-th edge is at most A compared with it in graph G.
Let Cmin and C'nin be the demographic groups receiving the minimum proportional influence respectively. If C'min C² C' the total increase of influence nodes in Cman bringing by any edge in Eg is at most [AmiulA. So the total increase of IM reward function with maximin fairness constraint in G is [Cmsn A.
and G',
Tomil
If Cmin # C'mino the total increase of IM reward function must be smaller than Lor.Cmen (9) Ja (8) [Cmaal
[mmaa
considering Cmin * minn and group Cmin achieves the smallest number of influenced nodes as portion to its
population in G. Since Ia Ic.Cm.n (8) is bounded by A, the reward increase is also bounded by A.
[Cmin]
Here we let = [Esl. The total reward increase bringing by edges set És at most sA < EEJA. Since increasing the weights odges that either cannot be reached from seed nodes 5 or belong to Es does not lead to an increase in reward, the reward improvement solely benefits from Ég. We conclude that the IM utility function with maximin fairness satisfies bounded smoothness with f(x) |F|
7

---

Published in Transactions on Machine Learning Research (06/2025)
Diversity fairness. We show in Lemma 2 that the reward function for fair online influence maximization with diversity fairness satisfies Condition i.e., monotonicity and bounded smoothness.
Lemma 2. Given graph G EV) the reward function for fair online influence mazimization with diversity foirness constraint satisfies monotonicity. It also satisfies bounded smoothness with smoothness function f(z) = B|[ + |
Proof. We first prove the monotonicity and then show the reward function satisfies bounded smoothness. In addition, need to use Lemma g to assist our proof and Lemma has detailed proof referred in Appendix A.9.
Lemma 3. If the diversily constraind is salisfied with ,a, the constraint will not be violated after the lifting of (adding A to p))
P1 - Monotonicity, Given two graph G and G' with the set of edge weights and je respectively, if 14 S M4 Vj (1....,[EE) holds, is trivial that for class C₁
la.c, (S) S (S)
IkTc)(kk) S lo)c)((k)
(16)
(1) Suppose both G and G' satisfy diversity constraint given S. By Equation
16 and Equation g we have
Σ C.EC
Ja.c, diversisy S diversssy (S)
Σ (s)
(17)
CLEC
(2) Suppose least of G and G' violates the diversity constraint given S. By Equation 16 it is impossible that G' satisfies the diversity constraint while G' violates (see more details in Lemma Then
If both G and G' violate the diversity constraint, have that r pdiversity (S) -ry Alueerssty (S) 0: diveraity (S) > 0.
If G' violates the diversity constraint while G' satisfies, we have that r pdiversity 0 and T
diversity (S). Thus, the reward function is monotone, i.e., (diversity (S) S T
P2 Bounded smoothness under f(x) = |E||V/ Vl. The proof is irregular as it results in a bounded
smoothness function of the form ((x) = kr B. Therefore, its detailed proof and the rationale behind this
form are provided in Appendix A.10
Welfare function. With that in mind, we show in Lemma ! that the reward function for fair online influence maximization with welfare function as fairness constraint satisfies monotonicity and bounded smoothness (Condition D
Lemma 4. Given graph G E)p,, the IM reward function with welfare function as fairness constroint satisfies monotonicity. It also satisfies bounded smoothness with the smoothness function as
[[E]II(((1 11]1/a, [|EIIV|2*]/0
-
fa
f(x)
if0 < <
(18)
i 0,
where = min((uf]Vc C}).
Proof. We first prove the monotonicity and then show the reward function satisfies bounded smoothness.
P1 - Monotonicity. As shown in Rahmattalabi et al. (2021). the welfare function monotone with respect to the expected fraction influenced nodes in each group. For graphs G and G' with edge weights and μl, welfoore wellfore(S) (S). Thus, increasing edge if μ S p/. Vi (1,..., El], then a & wf,, Ve E C, implying weifare (5) S ry weights preserves monotonicity of the reward function.
f)() [i +e+ 2) loge] if O: the analysis is similar to a case.
8

---

Published in Transactions on Machine Learning Research (06/2025)
Given graph G and any feasible seed nodes S, we use Fis to denote the set of edges in the subgraph induced from graph G. We employ Ess, to represent the set of edges reachable from seed set S in the expected IC diffusion process. Suppose there exists graph G and G' with edge weights μ and y' respectively, where μ4 = M4 + A, Vi E E, > O. The reward increase in G' solely benefits from the weight improvement in edges set Eg.. For any edge E Eg, the total increase of the reward function bought by edge i most Σ (1c + A)))/a Σ (1e(419)))aa rEC²
P2 Bounded smoothness under Equation 18
aEC
compared with it in graph G. Due to space limitation, we defer the detailed discussion of the upper bound Σ (Ic((u + A)9) /a Σ (lc((e))) /a in Appendix A.11 In short summary, by Appendix A.11 have DEC
eEC the following bounded smoothness function
((1 + x/ - 1)/a
if 21
((x)
V 1//2//aa
if <
(19)
[BI ((((((())) + - < <
where == min((u(Vv C}).
Fairness notion incompatible with FOIM. While compatible with most fairness metrics in the literature, it should be noted that FOIM may not be universally applied to all fairness notions for influence maximization due to the requirement of theoretical analysis. One example is equity defined in Farnadi et al. (2020). Intuitively, equity asks for the expected number of influenced nodes within a group, denoted as C,, is proportionate to its population ratio
E [la.c. (5) I
(20)
E la (S)
[V]
This fairness notion violates theoretical requirement of monotonicity. Consider μ= + A where the increase of weight is on edges within the subgraph formulated by group C, and the increased spread does not propagate to groups other than C. Consequently, only the spread in C₁ would increase, while the spread in other
groups remains the same. Thus, E [Ta,c, (S)] would have larger share in E [To (S)), yet TVT
[C] is the same
and violates Equation 20
5.2 FOIM Fair Regret Analysis
In this section, we analyze the regret bound for the proposed FOIM framework. We investigate the regret for FOIM with CUCB, which resembles the analysis of other online TM algorithms such as IMLinUCB (Wen) ct al. 2016 and IMFB (Wu et al. 2019). In particular, we explore how regret will change when the fair IM reward employed. We primarily present the problen-dependent. regret bounds (Chen el. al.] 2014 Audiberl & Bubeck 2009 Audibert et al. (011)) under different fairness notions. We define mi, and Ar,max as the minimum and maximum regret gaps among all bad sced sets that contain edge i, respectively, where cach regret gap is given by A.j = ax.ar (rrr((*)) (S,)))
Theorem 1 (Maximin fairness regret). According to Lemma 1 the regret of CUCB under marimin fairness is
24.1ER.11
x2
+1)= -I -maa
(21)
(6(I....B1),,K.55 Anin Pi
Note that the problem-dependent regret is in O(nT/A). The proof is detailed in Appendix A.4
Theorem 2 (Diversity fairness regret). According to Lemma 2 the regret of CUCB under diversity fairness is
Σ
12 T T (A min -V1)>> min +
12 T A
+
+
R Am
(22)
P:(VV - -mnax)
2
KE B.....//.. K:
Notably, when 1, the function fxx simplifies f(x) |/||, which corresponds the bounded smoothness function of the original TM problem, making the proof benign.
9

---

Published in Transactions on Machine Learning Research (06/2025)
This regret is also in OIn T/A). For detailed proof, please refer to Appendix A.3 Theorem 3 (Welfare function regret). According to Lemaaa welfare function under different a values.
analyze the regret of CUCB under
When 1 S # 2, we have the regret
12x In (Aiox))-
(4 mén
)²
x² 2
+1
E Amxx +
Σ
max
24
A min
12 TA
BD
2 1)
ETV
man
(a -
2)p;
12 (28-1)|_[1]
K250
(23)
When 2, we have the regret as
E
18 I8 In
36
maz
π²a +1
LELA
max
(24)
P
p.
When 0 < < 1, have regret bound
12a I (Aima)) )
(A (min) 1-
E
12hn A min
+
n²
+1
F Amax
*E (E)) KesD
[iBÎL A min
(a
2)pz [IεĪII]]
2
When a < 0, we have regret bound as
2²
24
12 In T A
12a In T
(A (A
1
2 +1
+1
Amax max
max
Amar:
P:
[1+0]" "aree"--e"
e" JaIV
min
pi
(a + 2)ps
[
K,50
(25)
For the detailed proof, please refer to appendix A.5
6 Empirical Results
We assess FOLM with CMAB backbones under multiple fairness metrics, detailing datasets and bandit variants, then report results that confirm superior performance and show the algorithm accurately recovers edge weights- key to optimal influence maximizalion.
6.1 Cumulative Regret Comparison
Datasets, We conduct our experiments on five real-world networks namely NBA, German, Pokec-z, and
bail, which are commonly used for fair graph learning (Dai & Wang 2020 Ma et al.
2022). as well as YouTube. Detailed dataset statistics and descriptions are deferred Table and Appendix A.7
Sensitive
Activation
Dataset
Nodes
Edges
Attribute
Probability
NBA
400
16,570
Country
Jaccard index of nodes
German
1,000
24,970
Age
Dice ratio of nodes
Pokec-z
6,185
15,321
Sex
Cosine similarity of nodes
Bail
18,876
403,977
Race
Cosine similarity of nodes
YouTube
1,144,890
2,987,624
Community
Cosine similarity of nodes
Table 1: Dataset statistics
CMAB algorithms. We compare four different combinatorial multi-armed bandit (CMAB) algorithms FOIM, including CUCB (Chen et al. 2014), e-greedy (Kempe et al. 2003), IMLinUCB (Wen et al., 2016), and IMFB (Wu et al.] (2019).
CUCB (Chen et al. 2014 It estimates the per-edge activation probability independently and uses the upper confidence bound of the estimation to balance exploitation and exploration.
Fairness SaairnessDData/tee Data/treeeeeaete maan///eee/ee/////////eee/a /aatee/as/m////ass/t/// datasett
10

---

Published in Transactions on Machine Learning Research (06/2025)
e-greedy (Kempe et al. 2003). It estimates the per-edge activation probability independently and uses E-gredyy to balance exploitation (with probability 1 - -)) and exploration (with probability 6)-
IMLinUCB (Wen et al. 2016) (LinUCB). It is modee--nndeeendent contextual bandit algorithm that requires features on the receiving nodes as input to estimate the reachability between node pairs.
IMFB (Wu et al. 2019). is a factorization bandit a algorithm that factorizes the activation probability
on the edges into latent. factors on the corresponding nodes.
Offline oracle. In addition to the CMAB algorithm, another key component in the propose FOIM framework is the fair oracle, which is the fair offline influence maximization algorithm for seed node selection. In our experiments, we use two different fair oracles, namely multi-objective Frank-Wold (FW) algorithu (Tsang let al. 2019) (with suffix -FW) and mixed integer programming (MIP) (Farnadi al., 2020) (with suffix -MIP) To demonstrate the efficacy of using fair oracle, use degrec discount (Chen et al. 2009) (i.c.,
methods without suffix), which is an offinn inftuence maximization without fairness consideration, as oracle.
Reward and regret. For maximin fairness, we set the reward function as Equation (6) for diversity fairness, we set. the reward function as Equa- tion (9; and for welfare function, the reward function is defined in Equa- tion [T]. The cumulative regrets for all methods are calculated using Equa- tion (.. Optimal reward is calculated by the fair IM oracle using ground- truth activation probabilities.
CUCB-MIP
egred-Min MIP egred
IMFB-MIP MIP
LinUCB -MI
CUCB
IMFB
LinUCB
MIP Diversity Regret
MIP Maximin Regret
150
Regret
100
Regret
2
50
0
50 100
150
200
0
50
100 150
200
Iteration Times
Iteration Times
Hyperparameter settings. In all experiments, the dimensionalities for the susceptibility factor in IMLinUCB and the latent factors in IMFB are both set to 20. The seed set volume is set to K = 300 for Pokec-z and bail datasct, and K- 10 for NBA and K 50 for German datasct respectively.
Figure 1: Cumulative regrets under maximin fairness and diver- sity fairness in NBA. Methods with suffix -MIP use mixed integer programming (Farnadi et al.) 2020): as offline oracle with fairness consideration. Methods without suffix use degree discount (Chen et al. 2009) as the offline oracle.
Activation probability. For all datasets, we select the first features for each dataset with the sensitive attribute included. Then we initialize the activation probability with the heuristics as presented in Table between node features.
Regret with fairness constraints under FW oracle. In Figure 3 and Figure 2 we present the experimental results on the offectiveness of FOIM in reducing the cumulative regret for maximin fairness, diversity fairness, and welfare function (a = 2, a = 0.5, and a = 22) with multi-objective Frank- Wolfe (FW) algorithm [Tang al.] 2019) oracle. From the figures, we observe that the cunulative regret with fairness constraints achieved under the fair oracle is significantly lower compared to other CMAB frameworks. This highlights the effectiveness of FOIM in improving the fairness of the algorithms.
Regret with fairness constraints under MIP oracle (Farnadi et al., 2020). We also test the regret of FOIM with MIP Farnadi et al.) 2020) as oracle on maximin fairness and diversity fairness. Figure ] presents the regret with MIP oracle on the NBA dataset. From the figure, we obtain similar observation that FOIM with MIP can achieve lower cumulative regret.
6.2 Estimation Error Analysis
The empirical findings presented in our study provide substantial evidence supporting the accuracy and integrity our fair experiment. In order to evaluate the performance of different experiments conducted under fair or submodular oracles, we quantitatively analyze the estimation error. This error metric captures the absolute discrepancy between the estimated activation probability Pe. and ground-truth probability Pe over observed edges. Thus we are est estinaning the trend of ff., Pel-
11

---

Published in Transactions on Machine Learning Research (06/2025)
CUCB
IMFB
egred
LinUCB
LinUCB-FW
CUCB-FW
egred-FW alpha=-2 Regret
IMFB-FW
le3
alpha=0.5 0.5 Regret
1e2
alpha = Regret
1e5
NBA Regret
1.5
0.5
2
0.0
50
100
150
200
50
100
150
200
50
100
150
200
Iteration time
Iteration time
Iteration time
105
le5
1.5
1.5
pokec Regret
1.0
2
0.0
Iteration time
lteration time
Iteration time
Figure 2: Cumulative regrets and their standard deviation under welfare function (a==0 (a= 2, 0.5) 5) in Pokec-z and NBA. Methods with suffix -FW use the multi-objective Prank-Wolft algorithm (Tsang et al. 2019) offline oracle with fairness consideration. Methods without suffix use degree discount (Chen et al. 2009 oracle.
CUCB
IMFB
LinUCB NBA Diversity Regret
egred
LinUCB-FW
CUCB-FW
egred-FW
IMFB-FW
NBA Maximin Regret
1s2
Jel repokecc Maximin Regret
tespokec Diversity Regret
1.00
Regret
Regret
Regret
0.75
Regret
0.50
0.25
50
100
150
200
50
100
150
200
50
100
150
200
50
150
200
Iteration time
Iteration time
Iteration time
Iteration time
Figure 3: Cumulattve regrets and their standard deviation under maximin fairness, diversity fairness in NBA and Pokec-z dataset. Methods with suffix -FW use the multi-objective Frank-Wolfe algorithm (Taang et al. 2019 as offline oracle with fairness considcration. Methods without suffix use degree discount (Chen et al. 2009 as the oflline oracle.
Upon careful examination of the results in Figure 4 it becomes apparent that the disparity estirnation error between the fair oracle and the submodular oracle is not significant. This observation suggests that the fair oracle performs nearly effectively submodular oracle like degrec discount. Consequently, this comparative analysis lends support to the validity of our fair experiment and lends credence to the notion that the fair modification implemented in our study is both reasonable and efficacious.
NBA alpha plot
6.3 Additional Experiments
0.20
IMFB
UnUCD
Estimation Error
In Appendix A.8.2 we provide additional results on German, Bail and Youtube datasets with similar observations to prove fair regret smaller result. with FOIM and scalability to millions of nodes. addition, we also provide offline and online influ- ence comparison in Appendix A.8.6 and trade-off between fair metries and influence in Appendix A.8.7 We also additionally provide theoretical FOIM time complexity analysis and real- time running result in Appendix A.12 additional empirical proof.
0.15
UnLCD-FW
CUCD-TW
0.10
0.05
0
50
100
150
200
Iteration Times
Figure 4: Estimation error of activation probabilities in NBA.
12

---

Published in Transactions on Machine Learning Research (06/2025)
7 Conclusion and Future Work
To promote equity and inclusivity in the online environment, we propose the FOIM framework, which combines fair offline influence maximization solutions with online combinatorial bandit models. We demonstrate the feasibility of using fairness constrained reward and oracle in combinatorial bandit algorithms. Additionally, we provide a thorough analysis of regret bounds of FOIM using the CUCB algorithm as an example. Empirical comparisons three real-world datasets highlight the superior performance in terms of regret under fairness notions, and we validate the efficiency and accuracy through estimation error. However, it is important to note that our analysis currently focuses on group fairness notions, We consider to explore individual fairness as future work.
Acknowledgements
Jose Efraim Aguilar Escamilla and Huazheng Wang are supported in part by National Science Foundation under grant IIS-2403401.
References
Jean-Yves Audibert and Sébastien Bubeck. Minimax policies for adversarial and stochastic bandits. In Annual Conference Computational Learning Theory, 2009.
Jean-Yves Audibert, Sébastien Bubeck, and Gábor Lugosi. Minimax policies for combinatorial prediction games. In Annual Conference Computational Learning Theory, 2011.
Peter Auer, Nicolò Cosa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., 47(2-3):235 256, May 2002. ISSN 0885-6125. doi: 10.003/A:10013399005522 URL
doi wttp://o....rr......33//1/////
Ruben Becker, Gianlorenzo D' D'angelo, Sajjad Ghobadi, and Hugo Gilbert. Fairness in influence maximization through randomization. ArXiv, abs/2010.03333, 2020.
Christian Borgs, Mickey Brautbar, Jennifer T. Chayes, and Brendan Lucier. Maximizing social influence in nearly optimal time. In ACM-STAM Symposium Discrete Algorithms, 2012. URL httpps//aap semanticscholar www.alarrrrr/oouuusssssao 149::94399933
Lixing Chen, Jie Xu, and Zhuo Lu. Contextual combinatorial multi-armed bandits with volatile arms and submodular reward. Advances in Newral Information Processing Systems, 31, 2018.
Wei Chen, Yajun Wang, and Siyu Yang. Efficient influence maximization in social networks. In Knowledge Discovery and Data Mining, 2009.
Wei Chen, Chi Wang, and Yajun Wang. Scalable influence maximization for prevalent. viral marketing in large-scale social networks. Proceedings of the 16th ACM SIGKDD international conference Knowledge discovery and data mining, 2010.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit and its extension to probabilisti- cally triggered arms. J. Mach. Learn. Res., 17:50:1-50:33 2014.
Eszter Julianna Csókás and Tamás Vinkó. An exact method for influence maximization based on deterministic linear threshold model. Central European Journal of Operations Research, 31:263 286, 2022.
Enyan Dai and Suhang Wang- Say no to the discrimination: Learning fair graph neural ners with limited sensitive attribute information. Proceedings of the 14th ACM International Conference on Web Search and Data Mining, 2020. URL httpss///ppi..eemmmiicooooooooee
Emily Diana, Wesley Gill, Michael Kearns, Krishnaram Kenthapadi, and Aaron Roth. Minimax group fairness: Algorithms and experiments. Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Sociely, 2021.
13

---

Published in Transactions on Machine Learning Research (06/2025)
European Parliament and Council of the European Union. Regulation (EU) 2016/679 of the European Parliament and of the Council. URL https://data: attps::/aaaa.euroqa...lll sur.opp..u/ell//rrg///00///
G. Farnadi, Behrouz Babaki, and Michel Gendreau. unifying framework for lairness-aware influence maximization. Companion Proceedings of the Web Conference 2020, 2020.
Yuting Feng, Ankitkumar N. Patel, Bogdan Cautis, and Hossein Vahabi. Influence maximization with fairness at scale. Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023. URL https::/ppp.semaatiiccchhoo... www.ssssennicccco......
Dtg/Corpps.D::250633775 259063763
Benjamin Fish, Ashkan Bashardoust, Danah Boyd, Sorelle A. Friedler, Carlos Eduardo Scheidegger, and Suresh Venkatasubramanian. Gaps information access social networks? The World Wide Web Conference, 2019.
Elad Hazan and Satyen Kale. Online submodular minimization. Journal of Machine Learning Research, 13 (10), 2012.
David Kempe, Jon Kleinberg, and Êva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD, pp. 137-146. ACM, 2003.
Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight regret bounds for stochastic combinatorial bani-sandits. ArXiv, abs/ 05//1411.044 2014.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 670, 2010.
Jing Ma, Ruocheng Guo, Mengting Wan, Longqi Yang, Aidong Zhang, and Jundong Li. Tearning fair node representations with graph counterfactual fairness. Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, 2022. URL 245853686
httpa///////ttt/////..a/ooaatata sttp:s////p.ssennnniccccholll Ang/CorpusID:
George L. Nemhauser, Laurence A. Wolsey, and Marshall L.. Fisher. An analysis of approximations for maximizing submodular set functions i. Mathematical Programming, 14:265 294, 1978.
Pierre Perrault, Jennifer Healey, Zheng Wen, and Michal Valko. Budgeted online influence maximization. International Conference on Machine Learning, pp. 7620-7631. PMLR, 2020.
Aida Rahmattalabi, Phebe Vayanos, Anthony Fulginiti, Eric Rice, Bryan Wilder, Amulya Yadav, and Milind Tambe. Exploring algorithmic fairness in robust graph covering problems. Advances in neural information processing systems, 32, 2019.
Aida Rahmattalabi, Shahin Jabbari, Himabindu Lakkaraju, Phebe Vayanos, Max Tzenberg, Ryan Brown, Eric Rice, and Milind Tambe. Fair influence maximization: A welfare optimization approach. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 11630-11638, 2021.
Peter Stone. Reinforcement learning. In Encyclopedia of Machine Learning and Data Mining, 2010.
Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, and Yair Zick. Group-lairness in influence maximization. In International Joint Conference on Artificial Intelligence, 2019.
Thomas W. Valente and Patchareeya Pumpuang. Identifying opinion leaders promote behavior change. Health Education & Behavior, 34:881 896, 2007.
Sharan Vaswani and Laks V. S. Lakshmanan. Influence maximization with bandits. ArXie, abs/1503 has/1503300024 2015.
Qinshi Wang and Wei Chen. Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications. In NIPS, 2017a.
14

---

Published in Transactions on Machine Learning Research (06/2025)
Yua- Wang and Yuxin Chen. Improving online inffuence maximization with regret minimization. In Proceedings of the 94th International Conference Machine Learning (TCML), pp. 3598-3000 1088-3607, 2017b.
Zheng Wen, Branislav Kveton, Michal Valko, and Sharan Vaswani. Online influence maximization under independent cascade model with semi-bandit feedback. In NTPS, 2016.
Qingyun Wu, Zhige Li, Huazheng Wang, Wei Chen, and Hongning Wang. Factorization bandits for online influence maximization. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.
Amulya Yadav, Bryan Wilder, Eric Rice, Robin Petering, Jaih B. Craddock, Amanda Moshioka-Maxwell Mary Hemler, Laura Onasch-Vera, Milind Tambe, and Darlene Woo. Bridging the gap between theory and practice in influence maximization: Raising awareness about hiv among homeless youth. In International Joint Conference on Artificial Intelligence, 2018.
15

---

Published in Transactions on Machine Learning Research (06/2025)
A Appendix
A.1 Preliminary
In this part, we present the mathematical notations employed in our theoretical inference. Specifically, the problem description and its associaled notations are detailed in Table 2
Symbol
Description
G
Directed graph
V
Node set
E
Edge set
C
Group i nodes in V
Edge weights
u
Node activatation probability
S
Seed set
K
Maximum size of scod
IG(S)
Expected number of influenced nodes by S
Ig,c, (S)
Expected number of nodes in group C, inftuenced by seed set S
(k)
Maximum number of nodes influence nodes under cardinality i Pr (S) a (S*)) B
(a, appappppooiin
Ess
Set of edges in the subgraph induced from G by seed nodes S Optimization objective function with edge weights μ and seed set $
(S)
Table 2: Summary of notation used in problem description.
Notation used in regret inference. We begin by introducing the notations used in this paragraph. With approximation guarantee (a, 5), we define seed nodes as a bad set (5) < a (rrr((S)) where (S*) denotes the global optimal reward. The set of bad seed nodes is defined as SB {S rp < <arrn(S*),, In CMAB, each edge in the graph represents the arm in the bandit. We let S B, = {S E SB l E Es} denotes the set of bad seed nodes where the ith edge is expected to be reached. We order all bad seed nodes in S B,i S1 ",,; B., SK; B in increasing order of their expected rewards, where K; SS B.il-
For any bad seed set S SB, with approximation guarantee (a, f), define approximate regret Ag = a (S*) (S)... For the ins edge i E [1....,/E)) with K; > 0 and reward order index j E {l..... K,). we define A iJ = A Additionally, for convenience purpose, we let A max = - and A A == AiK. Morcover, we define A_mx VE(1..... Ki
max A Amaxe and Amin iE(1..... EI
min A
A.2 Quoted Theorems
Our thcorctical analysis rely on the following theorems from CUCB (Chn et al. Theorem 4 (Theorem of CUCB (Chen et al. 2014 The (a, 3) approzimation regret of the CUCB algorithm T rounds using an (a, capprooitotiii oracle is at most
2014
Ainay
x² +1) +
Σ
(Aimtn P.) Aluan
en (a,
.18 Amax:
(26)
2
(E 1.)...,
where p² min;ee1,..... Pi, and
12InT
24
en (A. p) = max
.0<p<1
(27)
(A))
Theorem (Theorem of SUCBBChee approcimation oracle. Let p" (i.n.e( Pt. > O and w > 0, the regret of CUCB is at most
al.)
Consider CMAB problem with an (a. 9)- Tf the bounded smoothmess function f(x) = x²d for some
2014)).
27
12
w/2
T1-w/2
x2 +1
E AmAma
AmaN
Σ
24 Mi
max
(28)
2
p"
Te LE))
16

---

Published in Transactions on Machine Learning Research (06/2025)
A.3 Regret of Diversity Fairness
Here provide detailed proof for regret of diversily fairness in Equation 22
For diversity fairness, the bounded smoothness function we use is f(x) = | + [V and its corresponding inverse function is (A) = [
Then, to determinc (r(A.p), our objective is to compare (ー-(ا)) and 2 following &r (A
T 24InI) shown Theorem To make such a comparison, important note A S [V.. max 17 (A))"
Consequently, | (A-IV]> is evidently greater than 2. As result, conclude that (r 12tn TEVV
(A VVP
Finally, provide the regret bound. By employing Theorem have the following regret formula:
T +1)
E A max
Σ
12hn 18
12 T [E]2. VI2
( - IV1) Pi
PN
[V--Ajnax
max
[
Din
C. 8,50
(29)
Since
(MVI-A) is negative, remove it and obtain
1n T A min
12 2
x2 +1)
P Amar) +
-1E
(30)
(A min - |V])2p;
2
KEE,K,O
A.4 Regret of Maximin Fairness
In this section, we provide a detailed proof for the regret of maximin fairness in Equation 21
For maximin fairness, we choose the bounded smoothness function as f(x) E|
Then, to determine é (r) need to compare (--" and 2. Because the objective function of maximin
dll 2.
fairness is proportion, we can naturally infer that 0 S A < 1. Consequently, we have A
And
12
eventually, we get that (T(A,p)
A'p
Finally, we show the regret bound. By employing Theorem
the regret upper bound is as follows.
Σ
24 2 In
+
+11
|mlxAmax
(31)
min Pi
2
(I K
A.5 Regret of Welfare Function
Here provide the detailed proof of regret of welfare function in Section 5.1
A.5.1 When a 2
Based on Equation 18) the bounded smoothness function we use is f(x) |V|,
To derive the upper bound for f(x), we analyze AS using Lagrange median theorem. By transforming (f)A, into difference form, which is A) Σ ((d((((w))))))) for ue I we u A, where we LEC
represents the corresponding gradient parameter used in Lagrange median theorem, can bound it with A and obtain the upper bound as (A) = Σ (lc]+(A)). This implies that f(x) V is valid form cEC
of bounded smoothness function when 1. Additionally, aim to provide upper bound for f(z) in the form of f(x) "aa" For f(x) = |E|l [[++)"=1] the upper bound bounded smoothness function is f(x) [2 1)z². This result can be obtained by comparing the gradients and coincident starting points of the two functions.
17

---

Published in Transactions on Machine Learning Research (06/2025)
In summary, can have three forms of bounded smoothness function: (()) = | f(x) | and f(x) = | -0
[ (-=))=1
To determine p), we use f(x) | [1+2)*-1 and discuss it case by case.
Note that have (T(A, max 12 (ク)ー")
24 Our main goal is compare the relationship p between If [[]) and with f (A) [V
1)- Based on the above expression and definition,
if [E| à) 1 V2 we have lT Sr(A,p) p) 24 Otherwise, if TElV 1) s /2" we have
er (A, p) (-""")))""
12In
(r(A,p) T is mathematically impossible. If (r(,,)) = 24 happens to be true, can re-formulate ab
the requirement ( (εilv + 1) + to (1+ / )d < 1+ sg -T Given the magnitude of [E] and [V]
assumed in the G and the disparity between exponential and lincar functions, the aforementioned incquality is almost impossible to be satisfied.
In conjunction with Amaz IV| the extreme case, solving ad |i||]] + +1s (1 + / gives logi yz 2.
Thus we have (T),
Tn (- if 2 logi - 2.
Finally, we provide the problem-dependent regret bound. We (T(A,p) to derive the final regret result. In Theorem | for the sake of brevity, use f(z) y2" to provide an upper bound for regret.
When a 2 log1+ v2 in the case where logi+ //
2, we apply Theorem with f(z) = [22 1)x². And the regret bound is applicable
2 and #2
12a In (Aine))
1-
(A 1- min
Σ
A 12 T
min
+2 +
+1
|F
Amax
IC (E(1...,111) [8]) Ki30
A
PE
13/=a1/1|1 (a 2) pe
2
If a 2, we simply apply Theorem
with f(x) 3/ and get
Σ
36|E
(A simum)
(
|5 max
(32)
Pr
(E.......JE -.
In summarr, if we take consideration of all cases, and notably include the fact that for a 2 1 there would always have f(x) = E the case of S a < logı 1/ 2, the regret upper bound would be same as original CUCB bound. We have the regret bound as follows.
If 1 S a & logi+ 1/2 2, we have the regret as
24 IIIIEEET
122 +1)
E Amax
(33)
A A Ps
NE ED
K,50
If logi
25 a o 2, we have the regret as v2
12a Ia T' (Aimaz)
(A min
11
In A
x²
( [BI) K2
12th
A
pi
(a - 2)p;
2
2
11
E
Amax
(34)
If 2, we have the regret
Σ
VInT.
Vl T(A Alman)
+
( ? +1)
| Amax
P4
(35)
SE(1
K,50
18

---

Published in Transactions on Machine Learning Research (06/2025)
A.5.2 When 0<aa <<asl
In this case, we use the bounded smoothness function f(z) - |
To analyze ēr (A, p), our main goal is compare the relationship between if / {()) and 2, which entails
comparing A
0
with 2. Since the upper bound is | if a 2
2 Lاا then (r p) = 24
log
However, it is trivial that, 2 2 [B] cannot be attained since a E (0, 1]. Thus, for 00 < S 1, we have
log?
(r(A,p) = T 12
Finally, the problem-dependent regret bound is
In 7
(Aioaz) )= - (A min)
1
1n A
x²
min
+
+1
L Amax
(36)
KE(......B) (8)) K,S0
A
min Pi
(a 2)p; [
2
A.5.3 When a <0
Specifically, in this case, have f(x) = [ for f(x) can be easily achieved by employing gradient and ensuring that the starting and ending points coincide. uvent we can have two ((x), which respectively are f(x) = |E|[V] (I+e)"=c" r- and f(x) =
1 The determination of an upper bound a
Then we analyze p). Given that (A) = (εāliT + + -e for the f(x) [ the objec-
tive would be to compare (AA) with 2. By solving the inequality, know that 1 [ ( + e 2 12hr would result in p)) (A)) To solve the aforementioned inequality, is evident that
a V + + e. In the extreme scenario where Amar = [V] the requirement for (r = 12 is ad (εilvT + +) would result in (T(A 24
(E
(F-1(
Z 2 M + -. Yet the condition x2 < (
Similar to previous cases, now would have 0 as the solution to the following equation.
V2
t) E
(37)
E
12 Hence, when a > 8, the expression for (r(A.p) p) is given by T (A))ap' (r(A,p) 24
Otherwise, when a < 8, it becomes
Finally, provide the problem-dependent regret bound. As proceed to upper bounded smoothness function f(x) = |E|l|| (1+e)*-e" x into Theorem 4 we obtain the following problem-dependen regrets:
By applying Theorem with f(x) ya0", have the following problem-dependent regret bound
If a 2 0, we have the regret as
12 T A
12xln
(A (Amin)
n² 2
men
+
+ +1
- -1E|-Amax
(38)
4E (E B)
min
P.
(a
2)pt
[Toto- [illil
Ki50
If 0, we have the regret
2 +1
24
[E Amax +
Amaz
(39)
2
Pi
A.6 Problem- Sodblem-nndeeendentt Regret
In this section, we outline the procedural steps to obtain the problem-independer regret bound for maximin fairness, diversity fairness, and welfare function. The focus of this section is to outline the procedural steps
19

---

form of Published in Transactions on Machine Learning Research (06/2025)
involved in obtaining the grblee--iddeendden form of regret for Maximin Fairness, Diversity Fairness and Welfare Function.
A.6.1 Problem-independe regret bound for maximin fairness
By utilizing the function f()) E and applying Theorem wc derive the regret follows
1n P
nx? 2
+1)
E Amxx
(40)
A.6.2 Problem-independent regret bound for diversity fairness
Since previous works, bounded smoothness and Theorem under the assumption that f(0) = 0. We need introduce the justification of assumption f(0) * 0 in bounded smoothness can still be employed to give problen-independent regret guarantee. So modify the proof steps in CUCB of Theorem 5 to give modified goblem-indeeendeer regret upper bound. The result of such modification would be that have additional 2cT regret bound, where [(x) + yat
Thus, for f(x) = [V|+, we can have the following regret bound
48 E 3TIn
TT (1+1) -1E)- + 2/
(41)
A.6.3 Problem-independent regret bound for welfare function
Here we respectively discuss the
regret in regard the value of and & (T,,,p).
When 2 1: The value of (r (A.p) can be seen in Appendix A.5.1 and use f(x) in form of f(x) y2"
which is f(x) (2 - 1)x² Then by utilizing Theoren we can have problem-independent regret follows.
If 1 < a 10g1+ 2 a = 2, we have the problem-independeen regret as
48 3TIn V
(mr 1
+1)
[E]
(42)
max
If 1o 2 a # 2, have the prolem-indepenni regret as
V (2 1)[ a
12 (l)
2 max
+
LEIAnan
(43)
2 --a a
D²
When 0 < a 1: The value of (r(A.p) can be seen in Appendix | for problem--nndependent bound derived from Theorem would be
A.5.2 and can simply use f(x)
5 Thus the problem-indeeenndet regret
2
V
El)V) p
π E Amax
+1
(44)
2
When a < 0: The f(x) here would be f(x) = | (I+e)
x = Thus, by applying Theorem
we have
the following regret upper bound under the condition that a 2
2
[1 +c) ed]
12
+
1
+
T2
2 +1) 1F
1FF-Amma A
(45)
2 +
p
20

---

Published in Transactions on Machine Learning Research (06/2025)
In addition, would like to point that, for 0, we have that (r(A.)) 24 With the different (r(A.p) form, the problem-indepeadent regret in Theorem 5 would be employed without the 4/2 p T T1-w/2 part, resulting in upper regret bound same to problem-dependent case, i..,
2x [2 T
2 ?/2
24
+1) 2
1 |B/-Ammx +
Σ
A
Amaz
(46)
Pi
(E(1.....))) |B)
A.7 Dataset Descriptions
In our experiments, we use various widely-used benchmark datasets for fair graph learning: NBA, German, Pokec-z, bail and Youtubo. These datasets are common datasets used in in fair graph learning. For example, NBA dataset dataset was used in GEAR (Ma al. 2022) with Race sensitive attribute. We use the same sensitive attribute as in references. Attributes like (Race, etc) sensitive in real scenarios when considering fair online inftuence maximization. The detailed dataset descriptions are as follows.
used in FairGNN (Dai & Wang 2020 with Nationality as sensitive altribule and Bail
NBA a social network of NBA players on Twitter. Two players (nodes) are connected one follow another Twitter. We use the nationality of each user as the sensitive attribute.
German is a similarity graph of clients in Germany bank. Nodes are the clients, and two nodes are connected if their credit accounts are similar. We use the age of cach client the sensitive attribute.
Pokeo-z is sub-network of the Slovakian social network Pokec of one province. Each node is user in the selected province, and edges represent the friendship relationship among users. We use the biological sex of each user as the sensitive attribute.
YouTube is a social network of user friendship relationship on the video-sharing web platform YouTube. Each node is a user on YouTube, and two nodes are connected they form the friendship with cach other. We use the community membership of each user as the sensitive attribute.
A.8
Additional Experiments
In this section, we provide evidence as additional support for our Experiments part.
Submodular Oracle
CUCB-gred
egred-degree
A.8.1 Comparison
between different submodular oracles
1.0
IMFS-gred
dégree
Regret
Limi, diedgree
We compare the performance of FOIM with two submodular oracles: degree discount and greedy strategy. From Figure 5 we can conclude that the two compared submodular oracles have many similar regret. Thus, in our experiments the main body (i.e., Figure 3 and Figure 2 only degree discount.
Un..C--gred
0.5
0.0
50
100
150
200
A.8.2 Experiments on German
Iteration Times
We provide additional experimental results on German dataset, shown in Figure 6 From the figure, we observe that the IMLinUCB has poor performance in German, as the regret of IMLinUCB is much larger. This might be duc to a few reasons. First, for a dense network like German, the seed size we select is relatively large. Second, the sensitive attribute, i.c., age, contains more possible sensitive attribute values (non-binary), making the objective function insensitive context, which critical in IMLinUB.. Other than IMLinUCB, we can still observe the superiority of fair oracle under maximin regret in German.
Figure 5: Cumulative regrets using submodular oracles in NBA. Methods with sullix -degree use use degree discount (Chen et al., 2009) as the offline oracle, while methods with suffix -greedy use greedy selection as the offline oracle.
21

---

Published in Transactions on Machine Learning Research (06/2025)
A.8.3 Experiments bail dataset
We present additional experimental results bail dataset, shown in Figure We employed the MIP fair oracle and compared it with the results of baselines, and this figure serve additional proof of the superiority of fair oracle when the reward is fair.
A.8.4 Scalability demonstration
To demonstrate our algorithm's scalability to large graph dataset spanning million of nodes, we tested FOIM on Youtube dataset with MIP as fair oracle and compared with the baselines. The results can be seem in Figure and can serve as additional proof the performance FOIM framework. Due to the size of dataset and computation resource constraint, we only ran on one time and thus there no deviation.
IMFB
UiuCo
UnUCB-FW
CUCD-FW
egred-FWl
MFD-FW
Maximin Regret
Diversity Regret
20
alpha-0.3 Regret
alpha-2 Regret
led
alpha m Regret
Regret
Regre ett
Reogee
Regrat
0.0
Iteration time
Iteraation time
lteration time
Iteration time
Iteration time
Figure 6: Cumulative regrets under maximin fairness, diversity fairness, and welfare function (a 2, 0.5) in german. Methods with suffix -FW use the multi-objective Frank Wolfe algorithm (Taang et al.
2019)
offline oracle with fairness consideration. Methods without sufiix use degree discount (Chen et al. the oflline oracle. Shaded area refers to the standard deviation of the corresponding method across different. runs.
2009 as
egred
LiNUCS-FW
agred-FM
Maximin Regret
Diversity Regret
alpha=0.3 Regret
alpha=2 Regret
alpha=:2 Regret
Regret
Regret
Regret
Regret
Regret
30
200
130
200
30
200
130
200
32
Iteration
150
150
200
32
Iteration
300
130
200
50
Iteration time
102
130
200
Figure 7: Cumulative regrets under maximin fairness, diversity fairness, and welfare function (a 2, 0.5) in bail. Methods with suffix -MIP use the Mixed Integer Programming algorithm (Farnadi 2020 oflline oracle with fairness consideration. Methods without sullix use degree discount (Chen al. the offline oracle. Shaded area refers to the standard deviation of the corresponding method across different runs.
2009)
epslon-gred
CUCB
IMD
UnUCD
LIHUCD-MPP
CUCD-MIP
egred- MIP
IMTD-MPP
Diversity Regret
alpha-2 Regret
1e3
alpha=2 Regret
te7
Regret
107
alpha--2 Regret
Regret
begget
Reggen
2.5
60 Iteration time
60 Iteration time
60
80
62 Iteration time
Iteration time
Iteration time
Figure 8: Cumulative regrets under maximin fairness, diversity fairness, and welfare function (a -= 0.5 in Youtube dataset. Methods with suffix -MIP use the Mixed Integer Programming algorithı (Farnadi et al. 2020 as offline oracle with fairness consideration. Methods without suffix use degree discount (Chen et al. 2009 as the offline oracle.
2,
22

---

Published in Transactions on Machine Learning Research (06/2025)
A.8.5 Regret between FOIM and offline fair oracle
We evaluate the regret performance of a Frank- Wolfe oflline oracle on the NBA dataset using the diversity fairness metric, under perturbed activation probabilities. Specifically, Gaussian noise sampled from M/ 0.05²) is added to the base activation probabilities to simulate realistic imperfections offline estimates. Dottod line in Figure presents a generally higher cumulative regret.
This setup highlights the sensitivity of offline methods to noise in activation estimates. In contrast, the adaptive online methods dynamically adjust to the true graph structure and exhibit lower expected regret under the same noise conditions.
A.8.6 Experiment of comparison between offline fair algorithms and online fair algorithms.
To support the claim in Introduction part 'Conse- quently, is likely that the estimated probabilities are inconsistent with respect to individuals in the minority group due to bias introdueed in the of- fline data selection (e.g-; less logged activations for individuals from the protected group)", per- formed a new experiment on pokec dataset with 'Sex" as sensitive tttribute and select the group with labeled as Sex="1'. We set seed size as 300 to observe the performance of influenced nodes the last round of online learning (100 iterations) and compare it to the output of offline oracle (MTP al- gorithm). We evaluate the results on the metric of estimation error, which is the absolute of the gap between estimated propagation probability and ground truth probability. We need to note that the estimation error in ofline algorithm is more related offline data selection, which is like data sampling process and somehow independent of the operating of Frank-Wolfe algorithm and other fair oracles like MIP For example, MIP, the offline data selection is achieved by Monte Carlo Sampling. To report and ensure the reliability of our evaluation, we report Table 3 with standard deviation after 5 parallel executions.
NBA Diversity Regret
I4BB
LinUCa
1.25
Li
egred-FW
Regret
1.00
MFB-FW
FW Offline (pert.)
0.25
0.00
0
25
50
75
100
125
150
175
200
Iteration Time
Figure 9: Diversity regret NBA. Dashed line: FW-
Offline with (00, 0.05²).
MiP(ofline)
CUCB
IMFB
IMLinUCB
Estimation error
0.219 + 0.047
0.177 0.055
0.199 + 0.022
0.151 + 0.050
Influenced nodes
1488 + 14.2
1120 + 10.7
1507 + 18.8
1525 15.0
Table 3: Comparison between online fair algorithus and oflline fair algorithms
We record the comparison in the Table 3 The experiment indicates that the final seed selection of fair online learning might be better than offline fair algorithm and supports the statement 'It may further result sub-optimal seed selection for fair offline influence maximization that relies on the estimated information.".
A.8.7 Influence spread and fairness trade-off
In addition to the online and offline fair algorithm comparison, we also report new results of influence spread of fair algorithms and baselines at Table g measured by the number of activated nodes at the last round (T' = 200) on the Pokec-Z dataset, which includes 6,185 nodes in total. Compared to their non-fair counterparts that only maximize influence, we observe that fair algorithms by FOIM achieve similar or smaller influence spread under different metrics. Specifically, influence spread is almost not affected by diversity fairness. For maximin fairness and welfare function, the spread is ~ 30 smaller than non-fair baselines with IMLinUCB and IMFB, two efficient algorithms that reverage/cstimatt reduced influence spread under fairness constraints is expected and is the price of trading-off between fairness and influence.
features of nodes and edges. The
23

---

Published in Transactions on Machine Learning Research (06/2025)
Table 4: Influence spread and fairness trade-off on the Pokec-Z dataset.
Influence
Maximin fairness
Diversity fairness
Welfare (a = 0.5)
a = 2
= -2
CUCB
1289
1298
1243
1221
1251
epsilon-greedy
1246
1234
1238
1237
1217
IMFB
1481
1437
1483
1460
1471
IMLinUCB
1387
1334
1419
1338
1409
CUCB-FW
1038
1324
1220
1163
1132
epsilon-gredy-FW
974
1372
1259
1056
1190
IMFB-FW
1110
1431
1177
1192
1192
IMLinUCB.FW
1074
1383
1188
1074
1116
A.9 Additional Proof of Diversity Fairness
In this section, we provide the additional proof of diversity fairness that if the diyersity constraint is satisfied in G with utility vector as μe, the constraint will not be violated for G' where ,4, = + A.
Proof. If the diversity constraint is satisfied with μ, the constraint will not be violated after the lifting of μ (adding A to μ))
If we only investigate on an edge j and let n4 n4 + A, the increase of Ta.c, (S) is larger than Tatc,) (ks) would complete the proof, as the general proof of lifting z is just a combination of each increase to edge propagation weight.
Thus, we give the formal proof of setting 14 = My + A to have the increase of Ta,c, (S) is larger than Tata,)(k
Case 1. If edge μÿ is out of G[Ci], the proof naturally stands. We can notice that Iata, (k:) is the maximal expectation that fair allocation kę can achieve on the deduced subgraph G[C,], which is independent of edge By out of the subgraph. Since we have condition that la.c, (5) 2 (ks) before the liftin((addig A) process, yet adding edge U2 is out of G[C,) would only possibly increase on lc,c.()), completing the proof in this case.
Case 2. If edge μj is within G[C.), the proof goes the followings. We consider the case that we lift edge B4 to nt and the increase of spread to be A, and we mark the end node of (4 as y. Thus, the increase of la,c; (S) and (k)) is determined by the increased spread starting from y. The the increase of la would be at most (la1c.(v)) and the increase of (S) would be Alar,c (y) at most. However, the increase would not always reach the maximal value like Alo(c.)(()) and ATo,c, (y). Since the spread from y is not on an emply graph, the nodes in C, may already be activated. For example, AloTc.(()) would have non-zero influence to its neighbors, yet the neighbors already have activation probability of 1.0 as they are seed nodes.
2.1 We first discuss about when (T and Alc (v) are the increases. We look at the volume relationship between Algjc (y) and Ale c, (v). As G'[C,) is subgraph of G', implying that the increase of (o))((V) is also made To ,,. (y) in C₁, so (v) would only be larger or equal than (o)c)(V) in C2 as it would spread to groups other than C; and may propagate back to C, making the influence strictly larger.
2.2 We analyze the case when increase starting from y in each metric is smaller than (l) and Ale c.. (3) in this part.
This case would happen as the increase spreading from y is not on an emply graph, and each node in Ca has already has it's expected activation probability due to the (S));((S I .,, (S). For example, if we employ (T as increase, and ATo(c.(V)) would have allocated increase in each node in C, Yet there exists such constraint that for each node in C, the allocated increase plus it's original expected activation probability must be smaller than 1, explaining why this case happen. As in some nodes, due to the existing of the constraint, the increase could only be smaller than the allocation of spread from y.
For each node o in class C,,, we have the following notations. P. the what (v) has on node o, and R. is the allocation of (ki) on node o, M,, is the allocation of To (v); and B, of (e.c,()). They represent.
24

---

Published in Transactions on Machine Learning Research (06/2025)
what the activation probability of each node in different diffusion process. For example (o)()(()) can be expressed as Eoec, Po: and R. = 1 or B, = represents is seed node.
APo
vo V 1 AP, R 20 R
Gaino
(47)
VOE C. 1, AP. - R. 50
Due to the existence of the constraint in Equation 47 we can divide the nodes in C2 into two groups respectively in considering (S) and Ia,c, (S). We annotate node set as {o E A,, & 1 - Roj, node set O as fo C, A., I 51-Bo) For node o in Q or θ, the increase would be AP, and AMo. Yet for node in C. Ω C; 6, the increase would be 1 R. and B,-
We compare the increase of spread in Cj under the constraint. For increase under Ikic,(kk), the general spread would be Even -0 (1-Ro). And for the increase of Ig. c. (S) would be Loco AM Loot Bo) following the same logic. We target to compare the relationship between the both constrained increase.
Since we already have relationship of Ia.c, (v) and (o)c,(y), lanc, (kz) and IG (c,,c(()) Case2 and our pre-condition, and the conditions can be expressed as A D.Ec Po S A.DEC, Mo: Eoec, Ro $ E.occ, B.. Combining these two conditions with Equation 47
have
Hereby we larget to have Eocc, Eoeg + 1) minused by Loec, (1- Lo (AM, and compare it to O. After calculation, we can have the gap expressed as Loec,
-APa) - (AP.+ + Bo 1). Since only in set C, - θ, AM, + B, -1 can be positive and reach the
Rb 1) + -oEc;- maximal value, which means we can have Evec, (AMM, + B, - 1) 1 -osc-e
+ B, - 1). Thus we
can have the final result represented as Eoec, (AM, AP,) Eoec,-n (n Ro + AM, + B.). Taking
the conditions and constraints into consideration, the final result would be larger than 0.
A.10 Bounded Smoothness for Diversity Fairness
Proof. We consider two cases here.
(1) Given feasible seed nodes S, both and G' satisfy diversity constraint, In this case, the problem is oquivalent to influence maximization without fairness constraint with reward function being Thus, it satisfics bounded smoothhess with function f(x) |E]|V|> (Chen et al., 2014).
(2) Given feasible seed nodes S, at least one of G and G' violates the diversity constraint. Similarly, by Lemma it is impossible that G satisfies the diversity constraint while G' violates. Then
If both G and G' violate the diversity constraint, we have that r pdiversity = r p diverssty (S) 0.
If violates the diversity constraint while G' satisfies, the largest reward increase is achieved by replacing Ny with p4 in G Vi E f1..... EE'), which will make ry ddiversity > 0. Given that the diversity constraint is already satisfied in the graph, the increase of the reward brought by edge i in Es is at most [V If we regard the reward increase brought by Ég as a sequential process, i.c., the reward increase is brought by each edge in Es sequentially, then the total increase of the reward brought by És in G' must be smaller than (s 1)[V|A + h, where h denotes the reward increase bought by the first edge making r piiversity + O. Since h [V,, we have dlversity (S) - ( (s 1)] + VV [E||AAA IV].
Combining (1) and (2), we complete the proof for bounded smoothness with smoothness function f(x) | + V..
A.11 Detailed Steps of Bounded Smoothness of Welfare Function
In this section, comprehensive analysis presented, clucidating the upper bound derivation for the expression of bound function, |c| (Mr +A)" -aa""" (a")" within the context of the welfare function, associated with value of a. Given and A, define g(u²) |e| (u (u'' Therefore, the maximum increase of the welfare reward
25

---

Published in Transactions on Machine Learning Research (06/2025)
function bought by any edge equals to Σ g(a)). Here we take the derivative of g with respect to any ut" aEC
We have ag 3u = (u + --f)a-1
(1) If 1: Since 0 < v² S 1, we have 8g 0. Therefore, g(u") is strictly increasing regard to uc. Ouc In this case, have the upper bound for the increase of the welfare reward function bring by any edge
Σ A)))/a Σ (lc)//a
OEC
GEC
(2)
1: we have Th < O. Therefore, g(²) is strictly decreasing with regard to u.. Consequently, we have the upper bound for the increase of the welfare reward function bring by any edge ((d((A)))/a
nEC
(3) II a < O: we let min((u E C)). Since Ve E C, of 2 0, we have e 2 0. Since 0g
< <0, the welfare Ba reward function achieves the largest vale under the condition that Vo E C, ur = E. Therefore, the upper bound equals to the welfare IM reward increase when Vc E C, uf = G, i.., E (ld(c A)9)/a (ld())/a
EEC
CEC
A.12 Time Complexity Analysis
In this part, we delve into the comparison between FOIM algorithms and original online IM algorithms. Notably, FOIM also operates within the CMAB framework, akin to the foundational online algorithms.
Taking the example of the CUCB algorithm, its time complexity is expressed (Chen et. al., 2014). Consequently, the bottleneck of our analysis hinges on the computational cost associated with the ORACLE, denoted as ORACLEttme Intuitively, the time complexity tends to be higher for fair oracles compared to unfair ones, due to trade-off between efficiency and fairness.
The time complexity would be O (|=)+m)) log" 2 I (Tsang et al. 2019) for of Frank-Wolfe fair oracle, |C,1 is the
where is the number of demographic groups, k is the number of seed nodes, b max;,y Ja.c, ( maximum normalized influence to demographic group, an error residual, and 8 is the probability threshold where and ô exists in the (a, 3) approximation (Taang et al. 2019). However, the time complexity for unfair oracle like general greedy and degree discount is 31 E POLY(e (Borgs et al. 2012
Kempe
et al. 2003).
In addition, at the Table 5 we report the average running time of our algorithm (with suffix -FW) and non-fair algorithms (without suffix) in the table above. The Youtube dataset (the largest dataset) is run on Google Cloud with N4 VM and Google Axion Processor including 32 vCPUs and 128 GB of DDR5 memory, while other datasets are tested on an AMD 5800H CPU. The non-fair methods (without suffix) use the efficient. degree discount oracle, while the fair algorithms use the multi-objective Frank-Wolf, as fair oracle.
From the table, observe that FOLM algorithms tend to have larger running time but are within the acceptable range. For examplc, on the largest dataset, Youtube, fair algorithms are five to six times slower than the non-fair baseline. The additional running time is because the fair ORACLE is slower to solve the optimization problem and could be further reduced given more efficient fair offline IM solvers in the future.
Table 5: Average running time of algorithms on various datascts.
Algorithm
NBA
Pokee-Z
German
Bail
Youtube
CUCB
0:00:15
0:01:14
0:00:57
0:08:48
0:33:41
epsilon-greedy
0:00:12
0:01:01
0:00:46
0:07:31
0:30:18
IMFB
0:00:38
0:02:13
0:02:20
0:14:48
0:59:49
IMLinUCB
0:00:26
0:02:03
0:04:53
0:12:57
0:47:48
CUCB-FW
0:02:32
0:12:47
0:06:21
1:03:45
3:46:39
epsilon-greddy-FW
0:02:24
0:12:10
0:06:07
0:53:00
3:30:51
IMFB-FW
0:03:06
0:13:59
0:08:53
1:38:29
4:18:06
IMLinUCB-FW
0:02:57
0:13:43
0:08:05
1:27:26
4:03:00
26

---

Published in Transactions on Machine Learning Research (06/2025)
A.13 Discussion of TPM Condition
In the context of OIM SOTA algorithms, the Tightening Probability Mass (TPM) condition Wang & Chen (2017b); Wen et al. (016) provides a smoothness assumption that is weaker and more broadly applicable than the classical bounded smoothness condition. We investigate whether common fairness-aware objective functions satisfy this condition. In particular, we compare the behavior Diversity Fairness and Maximin Fairness under TPM.
Theorem 6 (TPM Condition). Let μ and pl two influence probability vectors over the edge set, and let S be seed set. A reward function rS( satisfies the Tightening Probability Mass (TPM) condition if there ezists constant B > 0 such that
(n B 1 pu m/l-
(48)
where of is the probabilily that edge is aclivaled (f.e., Inaversed) under the influence process given seed set S.
Diversity Fairness Violates the TPM Condition.
Proof. Assume seed set S marginally satisfies the diversity constraint under edge probabilities resulting in a non-zero reward:
(S) >
(49)
Now perturb single edge probability by a small amount e, yielding a probability vector μ², This small change may violate the diversity constraint, causing the reward to drop sharply:
(S) 0.
(50)
Thus, the reward difference constant:
- - (x) 0,
(51)
whereas the TPM term vanishes as c c-+ 0:
-
(52)
Therefore, there exists no constant B such that
(sn(S) - (y)( Σ pl p 1 --1b,
(53)
implying that the TPM condition fails for any B. Hence, the diversity fairness objective does not satisfy the TPM condition.
Maximin Fairness Satisfies the TPM Condition.
Proof. Define the maximin fairness reward as
maxmin (S) = min IGo(S,
(54)
CEC
|C|
where (G μu) denotes the expected influence on group Let μ be a perturbed influence probability voctor.
For any group C, have:
IGo(S.p)
(G)(Spp')
[Gc( IGo(S,
(55)
[C]
C
27

---

Published in Transactions on Machine Learning Research (06/2025)
Assuming the Independent Cascade (IC) model and Lipschitz contimuity of the influence function over edge weights:
-
Σ
lue -
(56)
iE
where Es is the set of edges that may be activated under seed set S. It follows that:
IG
IGo(S,
|C|
Σ iE
Pi
8
14
141-
(57)
Taking the worst-case deviation over all groups:
1 maxminn
(S)
maxminn
(5)
max CEC
Σ
ps 104 li
14/1-
(58)
|C|
iEEs
Letting
B max CEC C
(59)
finally obtain:
1 mumaiin (S)
//
maxmin
(S)1s Σ
p |1: 141
(60)
iEEs
which satisfies the TPM condition.
28


Reviews:
[{"review_id": "SRLs50E2Fp", "reviewer": "Reviewer_3xCC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The paper is clearly written and easy to follow.\n* It provides theoretical analysis on fairness regret and the properties of fairness metrics.\n* Several experiments are conducted using real-world datasets.\n* The fair online influence maximization problem is practically relevant.\n\nWeaknesses:\n\n* Key components of the proposed FOIM algorithm (e.g., CMAB) are borrowed from previous work. The theoretical results, specifically the (α, β)-approximation guarantee, also heavily rely on existing literature.\n* The time complexity of the proposed algorithm is not provided. Is the complexity exponential or polynomial? Please clarify the exact form.\n* For FOIM using the welfare function, since the expression depends on α, it would be clearer to denote it explicitly as $r_\\mu(S, \\alpha)$\n* It would be helpful to report the running times for the experiments across different iterations.\n\nQuestions:\n\n* In Equation (8), why does $I_{G, [C_i]}$ depend only on the value k and not on the specific nodes selected?\n* In Figure 1, why is the regret of IMFB always zero in the left plot?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes FOIM (Fair Online Influence Maximization) to select the most influential seeds in social networks under the fairness constraints. Different with traditional methods, FOIM learns edge activation probabilities dynamically in an online setting and ensures equitable influence across demographic groups under certain fairness metrics. It integrates a combinatorial multi-armed bandit (CMAB) approach with fairness-aware selection criteria. The authors adopts traditional fairness metrics, such as maximin and diversity fairness, providing theoretical guarantees with sublinear regret bounds. Experiments conducted on real datasets demonstrate the performance of the proposed FOIM.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "please see weaknesses above", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UAcDSkgwEn", "reviewer": "Reviewer_4wdB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n1. Considering the fairness in the online influence maximization problem is meaningful and valuable. \n2. This paper considers different well-studied fairness definition. \n3. This paper shows that the reward function under these fairness constraint satisfies monontonicity and bounded smoothness. \n4. The work compares the empirical performances of classic OIM algorithms under different fairness oracles. \n\nWeakness: \nOne of the key concerns is the correctness of the results. In Section 5.2, the regret depends on $1/\\mu^*$ (or $1/\\mu_i$) where $\\mu^*$ is the minimum weight of the edge. But in Chen et al. (2014), this term is $1/p^*$ (or $1/p_i$) which represents the minimum triggering probability of edges that can be exponentially smaller than $\\mu^*$. Please check this. \n\nThe definition of $\\Delta_{\\min}, \\Delta_{\\max}...$ are all not introduced before used. \n\nThe writing is not clear enough and can still be improved. Some important definitions are missing. \n1. In Section 4, the definition of group (community) is not introduced. Should different groups be disjoint or not? \n2. If different groups are disjoint, (4) is equivalent to (1). \n3. In (11), the group is denoted as $c$ while it is denoted as $C_i$ in previous parts. It is not clear what is the definition of $u$. The definition should be consistent across the full paper. \n4. When introducing the fairness constraint, what is the formal definition of the regret? \n5. The end of Lemma 2: missing a period\n6. More introduction of the oracles should be provided. Such as the value of $\\alpha$ and $\\beta$ for the oracles introduced. \n\nDiscussion: \nFor the OIM problem, the state-of-the-art result depends on the TPM condition instead of the bounded smoothness condition [Wang & Chen, 2017; Wen et al., 2016)]. Do the authors try to validate whether the reward function satisfy the TPM condition?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the fair online influence maximization (OIM) problem. The OIM problem has been extensively studied in the literature. This paper first introduces the fairness constraint. It considers different notions of fairness, including the maxmin fairness, diversity fairness, and welfare function. The main contribution of the work is that it verifies the reward function under these notions of fairness satisfies the monontonicity and bounded smoothness properties. Thus applying existing works naturally gets a theoretical guarantee for the regret.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the above weakness part.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "MSrSpVib9Z", "reviewer": "Reviewer_q7Vx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n1. To consider online setting in for Fair Influence Maximization is novel and  would be interesting for researchers of the field. \n2. To map a fairness constraint into a reward function that makes the framework general for many fairness constraints, is an advantage of this framework.\n3. Providing theoretical guarantees such as regret analysis gives a good basis for comparison of these approaches with the future algorithms.\n4. The problem is well motivated and estimating the edge weights in an online fashion does make sense since there is no appropriate offline data that takes into account fairness constraints (therefore, the existing works lead to poor estimation for minority group edges and they probably would suffer higher regret).\n5. The paper is mostly well-written.\n\n# Weaknesses\n- There are a number of things that are not clear to me and it would be great if you could elaborate more:\n  1. It lacks some explanation about the problem of group-based Fair Influence maximization. i.e. something like: In this setting, we aim to maximize the influence over a number of communities. Meaning that the summation of the influence of all groups should be maximized as opposed to not caring about which part of the graph is gonna receive the resources. This is written in math in section 4, but the intuition is  not really explained in words. \n  2. It lacks clarity of some of the steps through the analysis of the work. For instance:\n      - It does not explain why equations 12 or 14 hold. \n      - Lemma 1, P2 i.e. bounded smoothness for maximin fairness constraint, is not so clear why it holds. \n      - The reader has to spend some time to figure out why some of the steps hold while t it is the responsibility of the author. Sometimes it is not so difficult to find out why, and sometimes it is dependent on who the reader is. So, I believe it needs to be explained.\n- Regarding the empirical evaluations:\n  1.  I think it makes sense that when optimizing for a fair objective, the algorithm which takes fairness into account outperforms one that doesn't. But I am not sure if this is what the paper needs to show. Rather, since the claim is that having an online mechanism to estimate the weights improves the regret when fairness is taken into account, I think it makes more sense to compare the result of some fair offline influence maximization with an online approach. \n  2. We are searching for sublinear regret while in the three of figures 1, 2 and 3, some of the approaches are showing linear regret. Although the figures are showing improvement in the initial steps of the algorithm, we don't know which ones are going to reach sublinear regret faster.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper has introduced the first **Fair Online Influence Maximization (FOIM)** framework which considers online learning for Fair Influence Maximization problems taking into account group fairness perspective. \n\n\nThe FOIM framework combines ideas from :\n  - online Influence Maximization and \n  - Fair Influence Maximization.\n\nThe framework is general in a sense that it can combine many Online Influence Maximization approaches with Many fairness constraints which are the ones that satisfy the two mentioned properties of Monotonicity and Bounded smoothness.\n\nThis paper investigates three different existing fairness constraints to define rewards and analyzes the regret bound of combining them with  an instance of combinatorial multi-armed bandit approach (CMAB).\n\nAnd finally, they have empirically shown that these combinations outperforms the online influence maximization algorithms that do not take fairness into account. Moreover, they have shown that using fair oracle would lead to similar estimation of the graph weights compared to submodular oracles.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The paper needs to improve on the weakness points I made earlier in **Strengths and Weaknesses** box.\n2. There are some typos or notation abuse in the paper:\n      - Lemma 3, P1: $i$ is used both for each edge and enumeration of the community $C_i$, in other words, does $C_i$ refer to the $i^{th}$ community or the community that includes $i^{th}$ edge?\n      - Appendix A.1, maybe you mean $\\mathcal{S}$ and not $S$ in the definition of $S_B$?\n      - In section 5, $\\mu'$ is not explained. In other words, you are defining $G$  but not $G'$.\n3. I suggest to add the mathematical definition of the error metric in section 6.2\n4. Figure 1. seems to be the result of one run of the algorithms only. since the standard deviation is not shown in the plot which is required. \n5. The colors of different figures should be consistent.\n6. Figure 2 misses definition of one color which makes things confusing.\n7. In section 6.2, the paper claims that fair oracle performs similar to submodular oracle. But it is not elaborated or well-motivated why this is important.", "broader_impact_concerns": "Based on my current understanding, I do not think this work needs a broader impact concern section.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two reviewers have given the recommendation "Leaning Accept", and one reviewer has given the recommendation "Accept". After reading the paper, the reviews, and the discussion, I recommend to accept this paper with minor revision.

Specifically, I recommend the authors to make the following revisions:

1) Please make all the revisions promised in the author responses below.

2) Please improve the writing of Section 6. In particular, please add a paragraph at the beginning of Section 6 to summarize the experiment results. Also, please make the figures larger so they are easier to read.

3) In Algorithm 1, the authors refer to $\mathcal{A}$ as "CMAB algorithm". I do not think this is an appropriate name. Specifically, $\mathcal{A}$ only estimates the edge weights, but does not choose the seed nodes, so it is just part of a "CMAB algorithm". I think probably we should call it "edge weight estimator", and clarify that it can be an optimistic edge weight estimator.

4) There seems to be a typo in the Reference. Two papers with the same title "Online Influence Maximization under Independent Cascade Model ..." but different authors have been cited.

5) possible typo: under equation 1, "and $I_G(S)$ is the maximum number of influence nodes ...", I think "maximum" should be "expected".
Decision: Accept (poster)