W1

Thanks for pointing this out. We made the proposed correction in the manuscript.

W2

Strategy A and Strategy B have the same mutual fairness score since they are equally (un)fair. Namely, they have the same distance from the diagonal. On the other hand, transporting Strategy A onto Strategy B has the highest cost as they are at a maximum (Euclidean) distance apart from each other. In a sense, the two strategies are ``symmetric'' in terms of unfairness. We would be glad to exemplify this further in the final version of the paper.

W3: The generalizability to multi-groups

We agree with the reviewer that the multi-group case requires more detail. In future versions of the manuscript, we will include a dedicated appendix for the $m$-group case, which we summarize below.

In the case of $m$ groups, the outreach distribution is a probability distribution $\gamma$ on the hypercube $[0,1]^m$; i.e., $\gamma$ now lives in $\mathcal P([0,1]^m)$. The reference distribution can again be taken to be the ``ideal'' distribution $\gamma^\ast=\delta_{(1,\ldots,1)}$ which encodes the case in which all members of all groups receive the information. As for the transportation cost, we can define it to be to distance between any given point $x=(x_1,\ldots,x_m)$ in the hypercube and the diagonal line. We can call this distance $d(x)$. An expression of $d$ can be found via simple geometric arguments. With this the fairness metric becomes

$

\textsf{Fairness}(\gamma)
=
1-
a
\mathbb{E}_{x\sim\gamma}[d(x)],

$

where the constant $a>0$ is again chosen so that $\textsf{Fairness}(\gamma)$ is between 0 and 1. Then, $\beta$-$\textsf{Fairness}(\gamma)$ can be defined analogously.

Finally, since we once again provide a closed-form expression, there is no need to numerically solve optimal transport problems, as in the 2D case presented in the paper. Also, note that we do not resort to the multimarginal optimal transport problem, which would indeed cause exponential complexity in the dimensionality.

Q1: I still don't understand why the example scenario is unfair.

The proposed example refers to the final configuration

$

\gamma_b = 0.25 \cdot \delta_{(0,0)} + 0.25 \cdot \delta_{(1,1)} + 0.25 \cdot \delta_{(0,1)} +0.25 \cdot \delta_{(1,0)} 

$

where $\delta_{(i,j)}$ indicates the delta distribution centered at $(i,j)$, $i,j\in[0,1]$. The distribution $\gamma_b$ encompasses the case in which in 25% of the cases anyone in Group 1 receives the information and none in Group 2 receives it ($0.25 \cdot \delta_{(1,0)}$) and in 25% of the cases anyone in Group 2 receives the information and none in Group 1 receives it ($0.25 \cdot \delta_{(0,1)}$). Therefore, in 50% of the cases, everyone in one group receives the information, as none in the other group receive it ($0.25 \cdot \delta_{(1,0)} + 0.25 \cdot \delta_{(0,1)}$).

This represents a highly unfair outcome: referring to the example proposed by the reviewer, this means that half of the time we are in the situation of Strategy A or Strategy B, namely half of the time, there is one group that has no access to the information spread. We hope we have been able to clarify the doubt.

We thank the reviewer for the time spent reviewing our paper and for their constructive feedback.

Dear Area Chair,

we wanted to notice you about this comment

"I thank the authors for providing clarification and the extra explanation on the generalizability to mullti-groups. The rebuttal solved most of my concerns. I still don't quite agree with Q1, but it is not critical in the paper. Thus, I would like to raise the score to 5."

from reviewer 1BeY. We are not sure if there is any technical problem on the platform but the comment is not visible to us anymore. However, we can still see the comment among our notifications.

Thank you very much for your help.

The Authors

W1(/Q1): Potential Scalability Issues

We thank the reviewer for the positive feedback and insightful comments. We first address both scalability aspects as follows:

Definition of fairness metric with $m$-groups:

We agree with the reviewer that the multi-group case requires more detail. In future versions of the paper, we will include an appendix for the $m$-group case, which we summarize below.

In the case of $m$ groups, the outreach distribution is a probability distribution $\gamma$ on the hypercube $[0,1]^m$. The reference distribution can again be taken to be the ``ideal'' distribution $\gamma^\ast=\delta_{(1,\ldots,1)}$ which encodes the case in which all members of all groups receive the information. As for the transportation cost, we can define it to be to distance between any given point $x=(x_1,\ldots,x_m)$ in the hypercube and the diagonal line. We can call this distance $d(x)$. An expression of $d$ can be found via simple geometric arguments. With this the fairness metric becomes $\textsf{Fairness}(\gamma)=1-a\mathbb{E}_{x\sim\gamma}[d(x)],$ where the constant $a>0$ is again chosen so that $\textsf{Fairness}(\gamma)$ is between 0 and 1. Then, $\beta$-$\textsf{Fairness}(\gamma)$ can be defined analogously. Finally, since we once again provide a closed-form expression, there is no need to numerically solve optimal transport problems, as in the 2D case presented in the paper. Also, note that we do not resort to the multimarginal optimal transport problem, which would indeed cause exponential complexity in the dimensionality.

Scaling with Large Graphs

Appendix D.2 details the computational complexity of the algorithm, assuming sparse graphs. Additionally, we tested on a range of datasets summarized in Appendix B::Tab. 1. When considering sparse datasets, we see a linear growth of the computational complexity with the number of graph nodes. While we still accommodate time-complexity growth with the growth of the seedset size $|S|$, the SIM problem in the literature usually keeps them small subject to its definition. $R=1000$ worked well across all datasets (see Appendix E::Tab. 2-5 for error-bars). Moreover, if the graphs aren't sparse (as we tested with dataset DZ), computation time grows additionally with $|E|$ as highlighted in App. D.2.

In practice, for datasets like INS with ~500,000 nodes and edges, generating a new seedset candidate can take around ~5 hours on computational resources declared in App. F, and is the usual bottleneck in the entire algorithm.

Computational precision in approximating joint distribution

Approximating outreach distribution is also limited by the extent to which we discretize the probability space. Added to this, if the graph is dense enough to present numerically close joint outreach sample points, we are forced to bucket them into a single support point in the probability space, trivializing the optimization problem and making similar seedset selections look equally fair and efficient.

Moreover, one can see exponential growth in handling the discrete support space with the number of groups $m$, if we increase the precision/discrete bucket size of the support space. For our experiments, discretizing $[0, 1]^m, m=2$ space with $100$ buckets for each group meant handling $100^2=10^4$ points in probability space. Nonetheless, since we provide a closed-form expression for the fairness metric, bypassing the computation of the optimal transport problem, its evaluation does not suffer from an increased discretization.

We will include a detailed discussion on time complexity and scalability in the final version of the paper.

L1: Network Topology

Network topology: We discuss the impact of network topology in Sec. 3.2, and we will expand on this point in the final version of the paper. In short, when the conduction probability is too small or too large, network topology does not play a major role. When the conduction probability is moderate, network topology starts playing a role, mainly through the number of cross-group edges (CE):

CE% is small (~5%, APS): Such datasets encode group interaction information in the edges themselves, that is, an edge likely means nodes belong to the same group. In such cases, baseline greedy algorithms (bas_g) already perform well as they rely only on the edge connectivity which is extremely reliable here. S3D does not significantly improve on their selection, both in efficiency and fairness.

CE% is balanced (40-50%, HS, AH): These datasets reflect that groups interact well across each other and hence any seedset selection largely ends up getting a fair outreach. Since bas_g already has proven near-optimal efficiency guarantees too, S3D performing significantly better than bas_g is again unlikely.

CE% is moderate (5-30%, AV (datasets ids $0, 2, 16, 20$), IV): These are the non-trivial cases not covered above. And here bas_g isn't lucky enough to reliably leverage the existence of edges into group information. Hence, S3D usually outperforms the baseline in these cases, achieving similar efficiency scores and significantly improving fair outreach through its seedset selection.

CE% is high (>50%): This case was never observed where nodes interact more across groups than in their own groups. However, as long as the existence of edges doesn't reliably signal group information, we expect S3D to perform well based on a similar analysis.

Moderate outreach in dense graphs (\INS, DZ): Graphs where $|E|$ substantially exceeds $|V|$, the outreach variance across sample sub-graphs is too low to be captured in the discretized space we experimented in (100x100 units in $[0,1]^2$), even for moderate $p$. This leads to single-point concentrated joint-distribution plots across several seedsets S3D tries to evaluate, all of them leading to the same OT score/$\beta$-fairness.

We thank the reviewer for the positive assessment of our paper and their constructive feedback.

The introduction of the mutual fairness metric represents a significant contribution. And, the author addressed my issue.

W1: Lack of theoretical guarantees for the S3D algorithm

We thank the reviewer for the positive feedback. To first address the point regarding the lack of theoretical guarantees: The S3D algorithm is similar to non-convex optimization methods such as Simulated Annealing. Such algorithms do not have theoretical guarantees but do have a long history of empirical success. We think that obtaining theoretical guarantees would be an excellent avenue for future work.

For further details on S3D, let $f: \mathcal{P}(V) \rightarrow [0, 1]$ be the $\beta$-fairness set-evaluation function defined in the power-set of the graph vertex set $V$. The function can then evaluate any seedset, $S \subseteq V$ for its $\beta$-fairness. Now for iterative optimization purposes, S3D Algorithm 1::3-8 defines a sampling process to define neighbors $\hat{S}$ of $S$ through its outreach $V_S$. Then S3D essentially follows non-convex optimization of $f$ using Simulated Annealing under Metropolis Sampling at a constant temperature. While Simulated Annealing does not have strict mathematical guarantees to find the global optimum in finite time, its empirical success is well understood in non-convex optimization.

While Simulated Annealing usually runs for finite iterations defined by an empirically tested temperature schedule, we ran Simulated Annealing under several constant temperatures to estimate the performance of S3D against baselines and concluded that a number of iterations $k \in [500, 1000]$ usually works well in practice. Hence any decaying temperature schedule that translates total iterations in this range should work fine.

Q1

The optimal transport discrepancy $W(\gamma,\gamma^*)$, appearing in line 184, is computed between two probability distributions: the probability measure $\gamma$ and the desired probability measure $\gamma^*$. The symbol $\pi$, instead, refers to the transportation plan and it is the optimization variable associated with the optimal transport problem. In line 184, the explicit expression of the solution of the optimization problem is already given, for this reason, $\pi$ does not appear. The subscript $(x_1,x_2)\sim \gamma$, instead, indicates that the samples $x_1,x_2$ are drawn from the probability distribution $\gamma$. We will further clarify these aspects in the text.

We thank the reviewer for the positive assessment of our paper and their constructive feedback.

W1

We agree that the multi-group case requires more detail. We will include a dedicated appendix. With $m$ groups, the outreach distribution is a distribution $\gamma$ on $[0,1]^m$. The reference distribution is again the ``ideal'' distribution $\gamma^\ast=\delta_{(1,\ldots,1)}$ which encodes the case in which all members of all groups receive the information. As for the transportation cost, we can define it to be to distance between any given point $x=(x_1,\ldots,x_m)$ and the diagonal line. We can call this distance $d(x)$. An expression of $d$ can be found via simple geometric arguments. Then, $\textsf{Fairness}(\gamma)=1-a E_{x\sim\gamma}[d(x)]$ where $a>0$ is so that the metric is between 0 and 1. Then, $\beta$-fairness can be defined analogously. Since we have a closed-form expression, there is no need to numerically solve OT problems, as in the paper. Also, we do not resort to multimarginal OT, which would cause exponential complexity in $m$.

W2

The example we draw inspiration from to design our metric, however, is an actual occurrence in our experiments. For the APS dataset with greedy fair heuristic, which exploits the notion of equity (Fig 3c in the paper, Fig a in the PDF), the samples are distributed in a way such that a consistent percentage (~30%) of the members in group 1 receive the information and way fewer members of group 2 receive it, and vice-versa. We show in Fig 5a that our algorithm can counteract unfair occurrences by moving the distribution closer to the diagonal (Fig b in the PDF). We will put more emphasis on this in the final version.

W3

We agree that the $R$ leading to a statistically strong result depends on the dataset: the varied geometry of various subgraphs that the sampling of the edges produce, the exact complexity of the joint-outreach distribution (ground-utility distribution in this context), and the uncertainty of the quantities we sample/approximate throughout our experiments. App. E: Tab. 2-5 highlight the level of uncertainty, being < 3% in $2\sigma$ error-bar. To generate these bars using the $R$ values, we run each configuration 100 times, leading to instances using $100R = 10^5$ independent subgraph samples, sufficiently more than/of the same order in the relevant literature. We will highlight this in the revision.

W4

We show earlier in the paper that our metric is more informative than the equity metric, both mathematically (Sec 3.1) and with a vast amount of experiments (Sec 3.2). Fig 4 confirms these findings by noticing that the two metrics show significantly different trends across different propagation probabilities, rather than their absolute closeness. E.g., in Fig 4, the higher conduction prob. makes the same setup "relatively" unfair when seen from our metric's lens, totally opposite of what expected outreach highlights, establishing a non-trivial and fundamental difference in them.

W5

The reviewer is correct. There was a mislabeling in Fig 5b-d. Fig 5b is a comparison between the greedy heuristics versus S3D with greedy baseline and Fig 5d is a comparison between the degree centrality heuristics versus S3D with degree centrality baseline. The behavior in Fig 5d is now in sync with the corresponding metric dots in Fig 6's last subfigure. This also agrees with our understanding that the greedy strategy already has a theoretic efficiency lower-bound guarantee, unlikely to be surpassed (see Fig. 6 last subfigure). What S3D achieves is a tradeoff for ~1% efficiency to get a >2% gain in fairness against greedy heuristics. Whereas against degree centrality heuristics, there is a substantial gain in both fairness and efficiency. We have corrected the figures in the PDF.

Q1

It is the delta distribution at $(i,j)\in [0,1]^2$. We will mention this in the final version.

Q2

Thanks for pointing out this inaccuracy. Indeed, the transportation cost is $\Vert z(x_1,x_2,y_1,y_2)-x\Vert=\frac{\sqrt{2}}{2}|(x_2-x_1)-(y_2-y_1)|.$ The factor $\sqrt{2}/2$ is then dropped for normalization purposes, to ensure that the metric is between 0 and 1. In our applications, the reference distribution lies on the diagonal ($y_1=y_2$) which (after normalization) yields the same expression $|x_1-x_2|$. Thus, this inaccuracy does not affect our experiments. We detailed the computations and fixed Eq (2)-(3) in the revision.

Q3

The alg. hrtg is based on equity. We will mention it in the paper.

Q4

The reviewer is correct.

Q5

Correct. We will mention this in the revision.

Q6

When we consider information propagation from $S$ to generate the list $V_S$ of nodes reachable from $S$ (line 3), we use this $V_S$ to generate a candidate seedset $\hat{S}$ using iteration in lines 5-8, adding a new seed per step. This seed in each step, $v \sim V_S$, incrementally reduces the list $V_S$ by removing nodes from it that are reachable from $v$. Ideally, the reachability of $v$ alone is again defined by the nodes reachable via Independent Cascade (IC) starting from this seed. So, one might end up running IC $|S|$ many times, for all $v\in\hat{S}$. To approximately solve this problem, we create $V_{\hat{S}}$ (line 7) only considering nearest neighbors up to a constant depth from $v$ (fixed iterations of BFS from $v$). This constant is a fraction of the largest graph diameter.

Q7

We appreciate the suggestion and will implement it.

Q8

This behavior can also be seen well in the example in Fig. 14, where the reasoning is instantly perceptible. For visualization/computation reasons, $[0,1]^2$ is discretized into 100x100 (real-world datasets) or 10x10 (Fig 14) blocks. Meanwhile, the possible outreach fraction realizations (rational numbers), depending on the graph geometry and the number of graph nodes and selected seeds, are bucketed into the closest buckets. So, the visualization may appear as a pattern of "rectangles" which represent the buckets of the discretized space. These are more prominent with smaller datasets.

Limitations

Please refer to W1.