FairWire: Fair Graph Generation
Authors: Oyku Deniz Kose
Yanning Shen
Venue: NeurIPS 2024 poster (2024)
Keywords: Trustworthy ML
Learning over Graphs
Fair ML over graphs
Fair Graph Generation
Primary area: fairness

Abstract: Machine learning over graphs has recently attracted growing attention due to its ability to analyze and learn complex relations within critical interconnected systems. However, the disparate impact that is amplified by the use of biased graph structures in these algorithms has raised significant concerns for their deployment in real-world decision systems. In addition, while synthetic graph generation has become pivotal for privacy and scalability considerations, the impact of generative learning algorithms on structural bias has not yet been investigated. Motivated by this, this work focuses on the analysis and mitigation of structural bias for both real and synthetic graphs. Specifically, we first theoretically analyze the sources of structural bias that result in disparity for the predictions of dyadic relations. To alleviate the identified bias factors, we design a novel fairness regularizer that offers a versatile use. Faced with the bias amplification in graph generation models brought to light in this work, we further propose a fair graph generation framework, FairWire, by leveraging our fair regularizer design in a generative model. Experimental results on real-world networks validate that the proposed tools herein deliver effective structural bias mitigation for both real and synthetic graphs.

FairWire: Fair Graph Generation
O. Deniz Kose
Department of Electrical Engineering and Computer Science University of California Irvine Irvine, CA, USA okose@uci edu
Yanning Shen'
Department of Electrical Engineering and Computer Science University of California Irvine Irvine, CA, USA yannings@uci.co edu
Abstract
Machine learning over graphs has recently attracted growing attention due its ability to analyze and learn complex relations within critical interconnected systems. However, the disparate impact that is amplified by the use of biased graph structures in these algorithms has raised significant concerns for their deployment in real- world decision systems. In addition, while synthetic graph generation has become pivotal for privacy and scalability considerations, the impact of generative learning algorithms structural bias has yet been investigated. Motivated by this, this work focuses on the analysis and mitigation of structural bias for both real and synthetic graphs. Specifically, we first theoretically analyze the sources of structural bias that result in disparity for the predictions of dyadic relations. To alleviate the identified bias factors, we design novel fairness regularizer that offers versatile use. Faced with the bias amplification in graph generation models brought to light in this work, we further propose fair graph generation framework, FairWire, by leveraging our fair regularizer design in generative model. Experimental results on real-world networks validate that the proposed tools herein deliver effective structural bias mitigation for both real and synthetic graphs.
Introduction
The volume of graph-structured data has been explosively growing due to the advancement in interconnected systems. In this context, machine learning (ML) over graphs attracts increasing
attention (1), where specifically graph neural networks (GNNs) ( 3 4 have been proven to handle
complex learning tasks over graphs, such as social recommendation 5)), traffic flow forecasting (6).
Despite the increasing research focus on graph MI, the deployment of these algorithms in weal-world decision systems requires guarantees preventing disparate impacts. Here, algorithmic disparity refers to the performance gap incurred by ML algorithms with respect to certain sensitive attributes protected by anti-iiscrmmnnttoon laws or social norms (e.g., ethnicity, religion). While algorithmic bias is concern over tabular data 7 ( such bias becomes more critical for learning over graphs, as the use of graph structure in the algorithm design has been demonstrated to amplify the already existing bias (9). Motivated by this, in this work, specifically focus structural bias and consequently the disparity in the predictions of dyadic relationships among nodes. Note that since the link predictions
corresponnding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

are informed by the proximity principle (nodes connect to other nodes that are similar to themselves), the bias in graph topology is directly reflected in link prediction. For example, in social network, the denser connectivity within people from the same ethnic group leads to higher recommendation rates within these groups and may cause segregation in social relations (IO). Hence, the development of fair link prediction algorithm is of crucial importance to prevent potential segregation.
Fairness-aware algorithms typically require the knowledge of the sensitive attributes, the sharing of which can potentially create privacy concerns (.. From a scalability perspective, sharing real graphs is also accompanied by difficulties due to the ever-increasing size of graphs. All these factors contribute to the value of synthetic graph generation for a number of applications, such as recommendation systems (12), anomaly detection (13). For graph generation, data-driven models are shown to achieve state-of-the ofite--f--he-arr art results (14) [5] 16), however, the faimess aspect of these models is under-explored. Recent works demonstrate that, in general, generative models tend to amplify the already existing bias in real data (17, 18), which is a potential issue for graph generation as well.
Faced with the aforementioned structural bias issues in graphs, in this work, we first carry out theoretical analysis investigating the sources of such structural bias. Specifically, we deduce the factors that affect a commonly used bias metric, namely statistical parity (I9), for link prediction. Guided by the theoretical findings, a novel fairness regularizer, Lrai is designed, which can be utilized for various graph-relates problems, including link prediction and graph generation. In addition, an empirical analysis for a graph generation model is carried out, which reveals that the use of generative algorithms amplifies the already existing structural bias in real graph data. To resolve this issue, we design a new diffusion-based fair graph generation framework, FairWire, which leverages the proposed regularizer LrurWire The training of diffusion model in FairWire is specifically designed to capture the correlations between the synthetic sensitive attributes and the graph connectivity, which enables fair model training with the existing techniques without revealing the real sensitive information. Overall, the contributions of this work can be summarized as follows: cl) A theoretical analysis that reveals the causes of disparity in the predictions of dyadic relations between nodes is derived. Differing from the existing analyses regarding the statistical parity in link prediction, our analysis considers a more general setting where sensitive attributes can be non-binary. c2) Based on the theoretical findings, we design novel fairness regularizer, CearWWre which can be directly utilized for link prediction, as well as for graph generation models to alleviate the structural bias in task-agnostic way.
c3) We conduct an empirical analysis for the effect of graph generation models on the structural bias, which reveals the possible bias amplification related these models.
c4) Fair Wire, novel fair graph generation framework, is developed by leveraging FairWire within a diffusion model. The diffusion model is trained capture the relations between the sensitive attributes and the graph topology, facilitating fair model training without private information leakage. c5) Comprehensive experimental results over real-world networks show that the proposed framework can effectively mitigate structural bias and create fair synthetic graphs.
2 Related Work
Fairness-aware learning over graphs. awarre graph ML. has attracted increasing attention
in recent years (20) 21 22). Existing works mainly focus on: 1) Group faimess (9) 23 24 25).
2) Individual fairness (26 27). and 3) Counterfactual fairness (28 29 30). To mitigate bias in
graph ML, different strategies are leveraged, including but not limited to adversarial regularization
② 24 31 32), Bayesian debiasing (33), and graph editing (28 34 35 36 37). With a specific focus
on link prediction, (19, 388 propose fairness-aware strategies to alter the adjacency matrix, while (39) designs a fairness- aware regularizer. Differing from the majority of cxisting strategies, our proposed design herein is guided and supported by theoretical results. Specifically, we rigorously analyze the factors in graph topology leading to disparity for link prediction considering non- binabiarry sensitive attributes. Furthermore, the developed bias mitigation tool can be employed in versatile manner for training the link prediction models, as well as for training the generative models to create synthetic, fair graphs.
Synthetic Graph Generation. Generating synthetic graphs that simulate the existing ones has been a topic of interest for long time (40; 41), for which the success of deep neural networks has been demonstrated 12, 42 43) Recently, the use of diffusion-bart based graph generative models has been increasing, due to their success in reflecting several important statistics of real graphs in the synthetic

---

ones (44, 45 46 16 47 48). To the best of our knowledge, the only existing work that considers fair graph generation (49) which only outputs a graph structure without nodal features. sensitive attributes and node labels, and also requires class labels as input. Furthermore, it focuses on the disparities in generation quality for different sensitive groups as the fairness metric, which may not be predictive for the fairness performance in downstream tasks. In contrast, our scheme herein does not require any class labels or training of a particular downstream task. In addition, differing from the existing diffusion models, generation of graph topology and nodal features is guided by the sensitive attributes, which enables us to capture the correlations between the synthetic sensitive attributes and synthetic graph structure/nodal features. To the best of our knowledge, this work provides the first fairness-awe aware diffusion based graph generation framework.
3 Preliminaries
Given an input graph 9 == (V, the focus of this study is investigating and mitigating the structural bias that may lead to unfair results for learning algorithms. Here, v ("1, '22," ... .u denotes the set of nodes and & S V x V stands for the set of edges. Nodal features and the adjacency matrix of the input graph 9 are represented by X RX and A {0, 1JNN,, respectively, where Aij = 1 if and only if (c,, uy) E E. This work considers a single, potentially non-binary sensitive attribute for each node denoted by s E {1,.... K)N. In addition, S E {0, 1] represents the one-hot encoding of the sensitive attributes. For the graphs with class information, y EN denotes the class labels. Node representations output by the /th GNN layer are H with b+ E RF denoting the learned hidden representations for node U/. X; R. and 8; represent the feature vector, and the sensitive attribute of node ti respectively. Furthermore, Sy denotes the set of nodes whose sensitive attributes are equal to We define inter-edge set EX ;= (eig l E Sa, E SS, a o 6}, and intra-edge set E- := {eig ju; Sar Sp, 6}. Similarly, di := Leyev-S, Agj Ve, S, and de = Em,es, ES. Atj, Ve, E Sa are the inter- and intra-degrees of node v, respectively. Finally, UA represents the discrete uniform distribution over the elements of set A.
4 Inspection and Mitigation of Structural Bias
This section first derives the conditions for a graph topology that leads to optimal statistical parity for link prediction. Guided by the obtained conditions, faimess regularizer will then be presented. Statistical parity for link prediction is defined as Agr == [E (e.,, XUy [g(us, 03) 8 = 8y]
Eg,,,y) xUv [g(0; vz) s; + s,]l (9)) where g(U, ú2) denotes the predicted probability for an edge between the nodes and j. To the best of our knowledge, our analysis is the first theoretical
investigation for the relation between Asp and the graph topology considering multi-valued sensitive
attributes, thus it generalizes previous findings with binary sensitive attributes (19).
4.1 Bias Analysis
This subsection derives the conditions for a fair graph topology that achieves optimal statistical parity in the ensuing link prediction task. First, we will introduce the GNN model considered in this work.
GNN model: Throughout the analysis, stochastic graph view, Á, is adopted, i.e., Aiy denotes the probability of an edge between the nodes v; and Uj. and Azg AJa. Let I represent the aggregated representations by the ith GNN layer with ith row IE x [z] (1/11] : Enjev Ayc,t11 where ct+1 = W'' Then, the hidden representation output by Ith GNN layer for node i be written as E [b |b = o <E.,, Ev A., W'')) o (E [z/-1)), where W is the weight matrix and ((-) is the non- non-lincar activation employed in the (th GNN layer.
The following assumptions are made for Theorem that will be presented in this subsection:
A1:
| 1o S 8, Vo; V.
Ed
Id N N- Ye, Sk, Vk E (1, .K).
A2:
A3: Enejey A.j > [d]] Ve, e V.
3

---

These assumptions are naturally satisfied by most of the real-world graphs. Assumption A1 implies that the representations, c; 's are finite. For A2, note that most of the have considerably more intra-edges than inter-edges (50), i.e., E, [d 2 E [d Thus, unless |Sa]l > || i + (extremely unbalanced sensitive group sizes), A2 holds. Finally, A3 holds with high probability as A [d]]] = Em,Es,, "E Asj. We also demonstrate that these assumptions are valid for the real-world networks we are using in Appendix A in order to further justify them.
social networks
Building upon these assumptions, Theorem revells the factors leading the disparity between the representations of different sensitive groups obtained at any GNN layer. Specifically, it upper bounds
the term 0% ((++)
Au,UUs [h[+1 8
k:] E BA [ 8: * k:]l22 The proof of the
theorem is presented in Appendix
B
Theorem 1. The disparity between the representations of nodes in a sensitive group Sy and the representations of the remaining nodes output by the lth GNN layer, 5(1+1) caa be upper bounded by:
(1
E Eowwey Asj -1 22p
t1t S <L(8V
Pk SE
pt
+2VNA.), (1)
N
S
N- 1Sa
S
where L is the Lipschitz constant of the activation activationfuncttinn function (.). || mean(z) A., Vu, V, and p EejeSe.e 4Sa As.j: Pi := Em.sst. ES. At.-
Do E V) -
Representation disparity resulting from the aforementioned GNN-based aggregation is examined and explained by Theorem [] The commonly used fairness measures, such as statistical parity (19), are naturally a function of the representation disparity. Herein, we further investigate the said relation between the representation disparity and Agp mathematically, Specifically, for link prediction model described by a function g UU)= := h, Shy, Proposition [ directly upper bounds ASP. Here, h; denotes the representation for node v; that is employed for the link prediction task, i.e., the hidden representations in the final layer. The proof of Proposition is presented in Appendix C
Proposition 1. For a link prediction model described by g(v,, vÿ) := h. Shy, ASP can be upper bounded by:
K
|Sk|
ASP
N |||_|120mar
(2)
where ||h:l22 S q, Vv,, gmazz max b
A Aus
[h. 8 = R3] E BA (ي) [hy 8; # k 12)12).
Combining the findings of Theorem and Proposition I1 Corollary [ further demonstrates the factors (including the topological ones) that affect the resulting statistical parity in the link prediction task.
Corollary 1. For link prediction model g(vs, Uz) == (hŞ+1) Ehp+!, where h is the represen- tation created by Lth (final) GNN layer, AsP can be upper bounded by:
ASP S
K
|Syl
q (1V))LL(0O/LL))))
+ a2)) + 22VNA.).
k=1 N
Σ Enyyey Aog A 220
where d' :=
and or
[
N
[
N -11
S
4.2 A Regularizer for Fair Connections
The bias analysis in Subsection 4. brings to light the factors resulting in topological bias for probabilistic graph connectivity. Corollary [ shows that the topological bias can be minimized
if ai = 0 and ag = O. One can obtain a1 0 by ensuring Ph N- Vk. Meanwhile,
Ft
02 if p Ev c cN and px c|Sa| for any constant I. Overall, the
optimal values of Dh and pi that minimize both ai and ag follow as (x Eyyeyy Ag1Ss/ and
N2
Therefore, in order to mitigate structural bias, we can design a (xt)* (E (Eeneeev AN)
N2 regularizer that pushes the expected number of inter-edges and intra-edges towards (x²)* and (pf)":
(Sex)(1((Sex)) T),. L = Ex Ev, (Sex)(See) )as (pt)*1+ | (A ( 101-(Sen

---

(rg))) Here. e₁ E RK is the basis vector with only non-zero entry 1, at the kth element, and @ denotes the Hadamard product. Note that such a regularizer is compatible with any learning algorithm that outputs probabilities of all possible edges in the graph, e.g., topology inference algorithmss.
Although L can be applied several graph MI algorithms and its theory-guided design can promise effective topological bias mitigation, its design requires single-batch learning setting due to the definitions of P and Di (resulting in complexity growing exponentially with N). Specifically,, P% and pi are calculated based on all edge probabilities related to the all nodes in Sx. Therefore, regularizing the values of P and Pk will lead to scalability issues for large graphs. To tackle this challenge, we only focus on the optimal ratio between the expected number of intra- and inter-edges, Le., PE [Sc P N -- Vk E {1..... K), which is governed by 01 The idea is to manipulate the ratio between the expected number of intra- and inter-edges in each bini-batch of nodes for a better scalability. We call the corresponding batch-wise fairness regularizer LraieWire, which follows
E En,yee (A @ (Sex)(Sex) (Ss Enweee ( (Sea) (1x)(11 (Sex)) Jg
LrirtWire (A
|kk]
S
(3)
where B denotes the of nodes within the utilized minibatch. Note that the aforementioned versatile use of L also applies to LrairWree which can directly be used in topology inference tasks. Specifically, for link prediction, the following loss function can be employed in training to combat bias:
-ip-- BLNDEB Loe (Aij, Ais) + Fair (A, B),
where Aij denotes the predicted probability by the algorithm for an edge between U; and vy and feg is cross-entropy loss. The hyperparameter À is used to adjust the weight of fairness in training.
5 Fair Graph Generation
Generating synthetic graphs that capture the structural characteristics in real data attracts increasing attention promising remedy for scalability (ever-increasing size of real-world graphs) and privacy issues. Especially, sharing real sensitive attributes for fair model training exacerbates the privacy concerns due to the sensitive attribute leakage problem (II. Thus, creating synthetic graphs with generative models becomes instrumental in applications over interconnected systems. In this work, focus on diffusion models whose success in capturing the original data distribution has been shown for various types of networks (5 46 16 47). Despite the growing interest in these models, their effects fairness have not yet been investigated, which limits their use in critical real-world decision systems. Motivated by this, in Subsection we first empirically analyze the impact of diffusion models on the algorithmic bias by comparing the original and synthetic graphs in terms of different fairness metrics for link prediction. This empirical investigation reveals that the algorithmic bias is amplified while using generative models for graph creation. To resolve this critical issue, we develop Fair Wire in Subsection 5.2] a fair graph generation framework, which leverages our proposed regularizer Fair during the training of diffusion model.
5.1 Diffusion Models and Structural Bias
To evaluate the effect of synthetic graph generation on bias, we first sample 10 different synthetic graphs for each of the 4 real-world networks (see Table 7 in Appendix [ and Subsection 6. for more details on the datasets). Synthetic graphs are sampled using diffusion model that is trained Tollowing the setup in (47), which is a state-of-the-e the----rttt-tttt algorithm for diffusion- based graph generation. Upon creating graphs, we evaluate them for the link prediction task on the same test set (generated from the real data) and report the corresponding utility (AUC) and fairness performance. Fairness performance is measured via two widely used bias metrics, statistical parity (Asp) and equal opportunity (Ago) (19) for which lower values indicate better fairness (see Subsection 6. for more details on the link prediction model and evaluation metrics). The obtained results are presented in Table
In Table 1 G denotes the original graphs, and the synthetic graphs are represented by ğ. Overall, Table I shows that graph generation via diffusion models indeed amplifies the already existing bias in the original graphs consistently for all the considered datasets. This brings the potential bias-related issues in synthetic graph creation to light and calls for robust bias mitigation solutions.
5

---

Table 1: Comparative results
Cora
Citeseer
Accuracy (%)
Aap (%)
Aso (3))
Accuracy (%)
Aap (%)
Ao)
94.92
27.71
11.53
95.
29.05
9.53
87.29 + 1.09
35.72 # 1.74
13:27 4 0.81
92.19 = 1.06
37 .6.66 + 1.29
13.52 = 0.92
Amazon Photo
Amazoa Computer
Accuracy (%)
Asp (%)
Aso (9)
Accuracy (%)
Asp (%)
Roo(%)
96.91
32.50
8.24
96.14
22.90
4,63
94.45 0.21
33.49 0.28
10.01 0.56
94.04 1 0.26
29.56 1 0.55
6.23 0.49
5.2 FairWire: A Fair Graph Generation Framework
The proposed fairness regularizer in Subsection 4.2 LFairWirs can utilized in two different settings: i) during model training for link prediction, k2) for training a graph generation model in task- agnostic way. Note that for both cases, a model trained to predict a probabilistic graph adjacency matrix, A. upon which CaaieWire can be employed. Both use cases can facilitate several fairness- graph-based applications. That said, the bias amplification issue in generative models (also observed from Table I makes creating fair graphs via graph generation models of particular interest.
The proposed fair graph generation framework, FairWire, is built upon structured denoising diffusion models for discrete data (51). In the forward diffusion, Fair employs a Markov process to create noisy graph data samples by independently adding or deleting edges. For denoising, a message- passing neural network (MPNN) trained to predict the clean graph based on noisy samples by using the guidance of sensitive attributes (and node labels if available). Finally, we sample synthetic graphs with the guidance of synthetic sensitive attributes that are initialized based on their distribution in the original data. If input graph has also node labels, during graph generation, these node labels are sampled based on their distribution conditioned on the sensitive attributes in the original graph. In the sequel, as main novelty lies in the denoising process, we discuss the training process of FairWire (reverse diffusion process) in more detail, while the forward diffusion and sampling processes are explained in Appendix D Note that the diffusion process is presented for attributed graphs, where synthetic nodal features X are also generated. However, the proposed approach can be readily adapted to graphs without nodal features.
Reverse diffusion process: For denoising, we train an MPNN, 09 parametrized by 0 which is shown to be a scalable solution for the generation of large, attributed graphs (47). Specifically, dg inputs noisy version of the input graph and the original sensitive attributes described by X A and aims to recover the original nodal features X and graph topology A Here, A E R- xxxNN' denotes the one-hot representations for the edge labels. Note that the sensitive attributes guide the MPNN to capture the relations between them and graph topology. Therefore, the sensitive attributes are initialized and kept the same during both training and sampling (the original distribution of sensitive attributes is used to initialize them during sampling). For node v, the message passing at the Ith layer can be described as:
used to
h (1,+1) = σ () T
b + +b/l + +E (Evvi()) [w)
h (t.)) (
(0 W(..S--))
(5)
T
s((+1) 0
S Ww (1) o (b)) + E Euex(i())) (+)
S
(6)
where || stands for the concatenation operator. In this aggregation, T-
[HS S D
and b are all learnable parameters, while a--) consists of ReLU (22) and LayerNorm 53) layers. In addition, (t.0)) and h, are initialized as hidden representations created for X and time step t via multi- layer perceptrons (MLP), respectively. and ( S. After creating hidden represen- tations for nodes and their sensitive attributes, final representation for a node is generated via h, h (2.0) [ (t.1) I|... ! [|((' ||... |lh, Note that when node labels are available, their one-hot representations Y, are also employed this MPNN in the same way as S are utilized. Based on these final representations, node attributes, and edge labels are predicted. To create fair graph connections
in the synthetic graphs, we regularize the predicted edge probabilities, A, via the designed fairness

---

regularizer LraeeWire Overall, the training loss of the MPNN follows as:
Σ V. LCE X
Σ U. Lce (Aij.r Alj.) Aaraieiiee (A, B);
(7)
where À adjusts the focus on the fairness regularizer.
Remark (Applicability to general generative models): Although the designed regularizer in Subsection 4.2 is embodied in a diffusion- based graph generation framework in Subsection 5.2 Crar can be utilized in any generative model outputting synthetic graph topologies as a fairness regularizer on the connections, including but not limited to graph autoencoder-basee or random walk-based graph generation models.
Remark (Creation of synthetic sensitive attributes): We design generative framework in Subsection 5.2 that outputs synthetic sensitive attributes whose effect on the connections reflected by inputting them the training of MPNN. We emphasize that the creation of these synthetic sensitive attributes also enables the use of existing fairness-aware schemes on the created graphs without leaking the real sensitive attributes.
6 Experiments
6.1 Datasets and Experimental Setup
Datasets. In the experiments, four attributed networks employed, namely Cora, Citeseer, Amazon Photo and Amazon Computer for link prediction. Cora and Citeseer are widely utilized citation networks, where the articles are nodes and the network topology depicts the citation relationships between these articles (54). Amazon Photo and Amazon Computer are product co- p-rchurcae networks, where the nodes are the products and the links are created if two products are often bought together (55). In addition to link prediction, we also evaluate the synthetic graphs on node classification, where the German credit (56) and Pokec-n ( graphs are employed. For more details on the datasets and their statistics, please see Appendix
Experimental Setup. In this section, first report the performance of LaairWire for link pre- diction. For this task, the area under the curve (AUC) is employed as the utility metric. As fairness metrics, statistical parity and equal opportunity definitions in (19 37) are used, where
Asp = (vr.,)) UU)' [A, = 1 Au = 1, sy] - B(e,,y)) xU, [A.j = Ai = 18,, + syll-
[Air =1
sy] -0,,, (Ai 8 + sy]l and AEO
Lower values for Asp and Ago indicate better faimess performance.
To evaluate the generated synthetic graphs, we use both the link prediction and node classification tasks. Herein, we sample 10 synthetic graphs for each dataset with the trained diffusion models. Afterward, we train link prediction/node classification models (for more details on these models, please see Appendix G on the sampled graphs, and test these models on the real graphs G (the test set is the same for all baselines and FairWire). Here, we consider the scenario where there is no access to the real graphs due to privacy concerns, and the models are trained on the synthetic graphs for downstream tasks. To evaluate these synthetic graphs on link prediction, the same utility and fairness metrics employed as the utility measure with A sp = P(ū; = 1 8j = 0) P(ú; = 8y = 1)), and yj = 1. 1) being the fairness metrics.
in the link prediction task are used. For node classification, accuracy is
A EO : P(ú; = 1 y/ 1, = 0) P(ú
For more details on the training of link prediction, node classification, diffusion models, and the hyperparameter selection for FairWire and baselines, see Appendix G A sensitivity analysis is also provided in Appendix H for the effect of hyperparameter À in (4) and in 7 Note that the performance of the generative algorithms is generally reported in terms of the distances between the statistics of real data and the synthetic ones, instead of the fairness performance. For completeness, we report the distance metrics for node degree distribution and clustering coefficient distribution in Appendix
Baselines. For link prediction, fairness- aware baselines include adversarial regularization ()) Frir (37), and FairAdj (19). For graph generation, FairGen (49), is the only existing fairness- aware baseline designed for node classification. For comprehensive evaluation, we also employ adversarial regularization ( and FairAdj (19) as in-processing and post-procsssing fairness-aware strategies within the generative model. For more details the baselines, please see Appendix G
7

---

Table 2: Comparative link prediction results.
Cora
Citeseer
AUC (%)
Asp (%)
Ago (%6
AUC (%)
Asp (%)
(%)
GNN
27.01
1.38
9.11
1.43
27.40
7.37
Adversarial
87.77 + 1.64
24.33 + 6.36
2.96 = 2.24
93.53
0.51
13.97 + 10.36
6.52 + 4.68
FairDrop
94.10 + 0.81
7.86
= 4.30
4.05
0 0.32
95.92 - 0.42
13.77 = 6.15
5.60 + 1.85
FairAdj
82.01 + 1.56
14.76 0.89
7.35 = 1.24
84.76
1.08
16.00
+ 11.93
5.91 + 3.42
CraiWee
92.18 + 1.03
4.76 = 0.24
2.05
0.37
96.00 0.23
8.62 0.80
1.29 + 0.68
Amazon Photo
Computer
(%)
Asp (%)
Ago (%)
AUC (%)
Asp (%)
(%)
GNN
97.01 + 0.26
32.65 + 0.95
8.01 = 0.52
96.13 0.06
23.70 0.79
5.51 + 0.79
Adversarial
96.17 + 0.09
29.57 0.91
8.03 1.05
95, 0.12
22.72
1.11
4.71 0.99
FairDrop
96.36 + 0.33
28.63 + 1.39
8.49 + 1.54
95.61
+ 0.13
21.30
+ 0.59
4.30 + 0.77
97 25 0.11
27.75 0.52
7.11 0.41
96.05 + 0.05
20.44 0.44
4.24 0.51
Lraewine
5c)
94.85 0.32
93.86 0.23
1.02
0.21
Table 3: Comparative results for graph generation on Link Prediction.
Cora
Citeseer
AUC (%)
Asr (%)
Ago (%)
AUC (%)
Asr (%)
ABo(%) (%)
94.92
27.71
11.53
95.76
29.05
9.53
87.29 1.09
35.72
92.19 1.06
37.56
13.52 4: 0.92
FairAdj
82,13
1.07
15.47
2.39
6.26
2.05
82.67
2.78
15.45 1: 2,68
7.98 +: 1.47
Adversarial
83,66 5.64
16.35
+: 9.80
7.82 5.84
89.59
2.70
24.20 + 5.82
10.34 1: 1.66
FairWire
86.49 1::99::22 2.79 2.79
12.91 + 6.35
4.31 : 3.59
91.27 + 2.78
18.35 + 6.91
7.80 + 2.76
6.2 Link Prediction Results
Comparative results for the link prediction task are presented in Table 2 where we consider the setting FairWire is employed
faimess regularizer while training a GNN model for link prediction. The natural baseline here is to employ the same GNN model without any fairness interventions, which is denoted by GNN Table Note that in Table equals to 0.01 for Amazon Photo and the results are presented for 0.1 for Amazon Computer.
The results in Table 2 demonstrate that employing L fairness regularizer leads to better fairness measures compared to the naive baseline, while also providing similar utility. Specifically, the proposed regularizer is observed to improve both fairness metrics, Asr and Ago, with improvements ranging from 20% to 80% for every evaluated dataset compared to the natural baseline, GNN. Furthermore, the obtained results show that Laairiiee also outperforms the fairness-aware baselines Adversarial (9), FairDrop (37), and FairAdj (19) in both fairness metrics. For certain datasets (e.g.. Amazon Photo, Amazon Computer), we report the results of FairWire for different values of À to illustrate the trade-off between fairness and utility and to show that FairWire leads to a better trade-oft off compared to the other fairess- aware baselines. Note that we could include the results of FairAdj over the product networks (i.e., Amazon Photo, Amazon Computer) due to its substantial memory use during its optimization process, which led out-of-memory errors for the infrastructure we use. In addition to the improved fairness performance, it can be observed that the employment of Lraiwine generally results in the lowest standard deviation values for fairness metrics, which demonstrates the stability of the proposed strategy for bias mitigation. Overall, the results corroborate the effectiveness of Craiwire in enhancing fairness while also providing similar utility compared to the state-of-the-art fairness-aware baselines.
6.3 Results for Graph Generation
Comparative results for graph generation are presented in Tables and where the link prediction and node classification tasks are used to evaluate the synthetic graphs, respectively. In these tables, G represents the original data, and & stands for the synthetic graphs generated by the fairness-agnostic GraphMaker (47). Overall, Tables to G, faimess-agnostie synthetic graphs created via diffusion, without significant utility loss for
show that FairWire improves fairness metrics compared

---

Table 4: Comparative results for graph generation on Node Classification.
German
Pokec-n
Acc (%)
Asp (%)
Aso (%)
Acc (%)
Asp (%)
ABo(%)
70.00
2.13
1.78
68.73
8.58
9.68
FairGen
73.60
28.71
15.34
51.73
0,00
0.00
68.92 2.37
2.61 + 5.83
2.29
5.06
66.19 +: 2.05
3.63 +: 2.58
2.66 = 2.50
FairAdj
70.08 1.08
2.17 = 4.49
1.11
2.24
Adversarial
70.00 0.62
1.57 + 2.70
1.34
+ 2.86
69.36 + 0.70
2.16 + 1.73
2.73 = 2.01
FairWire
69.76 0.51
0.63
1.53
0.30 0.61
68.23 + 0.45
1.91 0.92
1.35 0.92
both link prediction and node classification. Specifically, FairWire can achieve improvements in both Asp and Ago ranging from 25% to 90% for all datasets compared to with similar utility.
Note that, for link prediction, the fairness improvement reported for FairAdj in Table accompanied by a significant utility drop. Specifically, for a larger value (i.c., À = 1). FairWire can provide better fairness measures (Agr 7.01 + 6.25 and A EO 3.06 + 2.95) Citeseer with similar accuracy (83.47 + 7.79) to Fdir Thus, the results in Table 3 demonstrate that FairWire provides a better utility//airness trade-off compared to fairness-aware baselines all evaluated datasets.
In Table 4 similar to the link prediction experiments (Table the results of FairAdj for the Pokec-n network could not be obtained due to computational limitations. For FairGen (49), we directly input the synthetic graph output by the algorithm to the node classification model we train, thus the results obtained for single synthetic graph. A possible explanation for the better accuracy of FairGen on the German dataset is that the algorithm is observed to output a denser synthetic network, which might be useful for the utility. It is observed that the synthetic graph output by FairGen for Pokec-n was not informative enough for the node classification task (we provide the codes for the FairGen algorithm in our supplementary material for the reproducibility of these results.) All in all, the results in Table Suble44signu signify that the superior performance of Fair Wire in terms of fairness/utility trade-off can also be observed for node classification, which validates the efficacy of FairWire in creating fair synthetic graphs that also capture the real data distribution.
6.4 Visualization of Synthetic Graphs
Our analysis in Subsection 4.1 reveals that the ratio of intra- (edges connecting the same sensitive group) and inter- edges (edges between different sensitive groups) is factor contributing to the structural bias. Specifically, the bias factor aj is minimized when 2 1S.
N-1 Yk, where Pi and P the expected number of intra-and inter-edges for the nodes in Sy. This finding suggests that for a graph with multiple (> 2) sensitive groups, given the sizes of sensitive groups are not catastrophically unbalanced, the number of inger- (related to pX) should be larger than the number of intra-edges (related to pt) to alleviate structural bias (i.c., |S < N (S However, for graphs encountered in several domains, the number of intra-edges is significantly larger than the number of inter-edges, due to the homophily principle (10). Motivated by this, in [i we visualize the distributions of intra- and inter-edges in synthetic graphs created by i) a fairness-agnoste strategy, GraphMaker (47), and ii) FairWire for Cora. In Figure [ intra- and inter-edges are colored with blue and red, respectively. Figure [ reveals that the graph created by GraphMaker (47) predominantly consists of intra-edges, leading to the structural bias reflected Table In contrast, Fair exhibits remarkable balancing effect, which provides potential explanation for the improvement in fairness.
Figure 1: Distribation of the intra-edges (blue) and inter-edges (red) in the synthetic graphs created for Cora dataset by Graph- Maker (47) (left) and FairWire (right).

---

7 Conclusion
This study focuses on the investigation and mitigation of structural bias for both real and synthetic graphs, where a novel fairness regularizer, LrairWre is designed to alleviate the effects of bias factors identified in a developed theoretical bias analysis. Furthermore, the proposed fairness regularizer is leveraged in fair graph generation framework, FairWire which alleviates the bias amplification observed in graph generative models. Experimental results corroborate the effectiveness of the proposed tools in bias mitigation for both real and synthetic graphs.
This paper considers the setting where sensitive attributes are available during model training, which might limit its use for certain real-world applications. Thus, one future direction of this work would be consider the partial availability of these sensitive attributes in the imput graph data. Furthermore, although we showed that real-world graphs typically satisfy the assumptions in Subsection 4.1 another possible future work we consider is deriving theoretical bias analysis without the dependency on these assumptions.
Limitations:
Acknowledgement
Work in this paper is supported by NSF ECCS 2412484.
References
[1] I. Chami, S. Abu-El-Haija B. Perozzi, C. Ré, and K. Murphy, "Machine learning on graphs: A model and comprehensive taxonomy," The Journal of Machine Learning Research, vol. 23, no. pp. 2840-3903, 2022.
[2] N. Kipf and M. Welling, "Spei-supervised classification with graph convolutional networks," in Proc. International Conference on Learning Representations (ICLR), Apr. 2017.
[3] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, "Graph attention networks," " in International Conference on Learning Representations, 2018.
[4] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, "How powerful are graph neural networks?" in International Conference Learning Representations, 2018.
[5] Yu, H. Yin, J. Li, Q. Wang, N. Q. V. Hung, and X. Zhang, "Self-supervised multi-channel hypergraph convolutional network for social recommendation." in Proceedings of the web conference 2021, 2021, pp. 413-424.
[6] M. Li and Z. Zhu, "Spatial-temporal fusion graph neural networks for traffic flow forecasting," in Proceedings of the AAAI conference on artificial intelligence, vol. 35, no. 5, 2021, pp. 4189 4196.
[7] N. Mehrabi, F. Morstatter, N. Saxena, Lerman, and Galstyan, survey on bias and fairesss in machine learning," ACM computing surveys (CSUR), vol. 54, no. 6, pp. 1-35, 2021.
[8] D. Pessach and E. Shmueli, "A review on faimesss in machine learning." ACM Computing Surveys (CSUR), vol. 55, no. 3. pp. 1-44, 2022.
[9] E. Dai and S. Wang, "Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information," in Proceedings of the 14th ACM International Conference on Web Search and Data Mining, 2021, pp. 680-688.
[10] B. Hofstra, R. Corten, F. Van Tubergen, and N. B. Ellison, "Sources of segregation in social networks: A novel approach using facebook." American Sociological Review, vol. 82, no. 3, pp. 625-656, 2017.
[11] E. Dai and S. Wang, "Learning fair graph neural networks with limited and private sensitive attribute information," " IEEE Transactions on Knowledge and Data Engineering, 2022.
[12] A. Bojehevski, O. Shchur, D. Zügner, and Günnemann, "Netgan: Generating graphs via random walks," in International conference machine learning. PMLR, 2018, pp. 610-619.
10

---

[13] L. Akoglu, M. McGlohon, and C. Faloutsos, "Rtm: Laws and a recursive generator for weighted time-evolving graphs," in 2008 Eighth IEEE International Conference on Data Mining. IEEE,
2008, pp. 701-706.
[14] N. Goyal, H. V. Jain, and S. Ranu, "Graphgen: A scalable approach to domain-agnostic labeled graph generation," in Proceedings of The Web Conference 2020, 2020, pp.
[15] Y. Li, O. Vinyals, C. Dyer, R. Pascanu, and P. W. Battaglia, "Learning deep generative models of graphs. corr abs/ 003.03324 (2018)," 1803.
[16] C. Vignac, I. Krawezuk, A. Siraudin, Wang, V. Cevher, and Frossard, "Digress: Discrete denoising diffusion for graph generation," in The Eleventh International Conference on Learning Representations, 2022.
[17] K. Schwarz, Y. Liao, and Geiger, "On the frequency bias of generative models," Advances in Neural Information Processing Systems, vol. 34, pp. 18 28-1887 136, 2021.
[18] S. Zhao, H. Ren, A. Yuan, J. Song. N. Goodman, and S. Ermon, "Bias and generalization in deep generative models: An empirical study," Advances in Neural Information Processing Systems, vol. 31, 2018.
[19] Li, Y. Wang, H. Zhao, P. Hong, and H. Liu, "On dyadic fairness: Exploring and mitigating bias in graph connections." in International Conference on Learning Representations, 2021.
[20] Y. Dong, J. Ma, S. Wang, C. Chen, and J. Li, "Fairness in graph mining: A survey," IEEE Transactions on Knowledge and Data Engineering, 2023.
[21] M. Choudhary, C. Laclau, and C. Largeron, "A survey on fairness for machine learning on graphs," arXiv preprint wxXv:2205.005366 2022.
[22] Y. Dong, O. D. Kose, Y. Shen, and J. Li, "Fairness in graph machine learning: Recent advances and future prospectives." in Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023, pp. 5794-5795.
[23] T. Rahman, B. Surma, M. Backes, and Y. Zhang, "Fairwalk: towards fair graph embedding," in Proceedings of the 28th International Joint Conference on Artificial Intelligence, 2019, pp. 3289-32955
[24] A. Bose and W. Hamilton, "Compositional fairness constraints for graph embeddings." in International Conference on Machine Learning. PMLR, 2019, pp. 715-724.
[25] J. Palowitch and B. Perozzi, "Debiasing graph representations via eestadata-orthogone train- ing," in IEEE International Conference on Advances in Social Networks Analysis and Mining (ASONAM), 2020, pp. 435-442.
[26] Y. Dong, Kang, H. Tong, and J. Li, "Individual fairness for graph neural networks: A ranking based approach," in Proc ACM Conference on Knowledge Discovery & Data Mining (SIGKDD), 2021, pp. 300-310.
[27] W. Song, Y. Dong, N. Liu, and Li, "Guide: Group equality informed individual fairness in graph neural networks," in Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, 2022, pp. 1625-1634.
[28) C. Agarwal, H. Lakkaraju, and M. Zitnik, "Towards a unified framework for fair and stable graph representation learning," in Uncertainty in Artificial Intelligence. PMLR, 2021, pp- 2114-2124.
[29] J. Ma. R. Guo, M. Wan, L. Yang, A. Zhang, and J. Li, "Learning fair node representations with graph counterfactual fairness"" " in Proceedings of the Fifreenth ACM International Conference on Web Search and Data Mining, 2022, pp. 695-703.
[30] Z. Guo, J. Li, T. Xiao, Y. Ma, and S. Wang, "Towards fair graph neural networks via graph counterfactuall" Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, 2023, pp. 669-678

---

[31] J. Fisher, A. Mittal, D. Palfrey, and C. Christodoulopoulos, "Debiasing knowledge graph embeddings." in Proc. Conference on Empirical Methods in Natural Language Processing (EMNLPP) 2020, pp. 7332-7345.
[32] D. Guo, C. Wang. B. Wang, and H. Zha, "Learning fair representations via distance correlation minimization," " IEEE Transactions on Neural Networks and Learning Systems (TNNLS), 2022.
[33] M. Buyl and T. De Bie, "Debayes: a bayesian method for debiasing network embeddings." in International Conference on Machine Learning (ICML). PMLR, 2020, pp. 1220-1229.
[34] Y. Dong. N. Liu, B. Jalaian, and J. Li, "Edits: Modeling and mitigating data bias for graph neural networks," in Proceedings of the ACM Web Conference 2022, 2022, pp. 1259-1269.
[35] O. D. Kose and Y. Shen, "Fair contrastive learning on graphs," IEEE Transactions on Signal and Processing over Networks, vol. 8, pp. 475-488, 2022.
[36] "Demystifying and mitigating bias for node representation learning," IEEE Transactions on Neural Networks and Learning Systems, 2023.
[37] Spinelli. S. Scardapane, Hussain, and A. Uncini, "Fairdrop: Biased edge dropout for en- hancing fairness in graph representation learning," IEEE Transactions on Artificial Intelligence, vol. 3, no. 3, pp. 344-3444 2021.
[38] C. Laclau, Redko, M. Choudhary, and C. Largeron, "All of the faimess for edge prediction with optimal transport," in International Conference on Artificial Intelligence and Statistics. PMIR,, 2021, pp. 1774-1782.
[39] M. Buyl and T. D. Bie, "The KL-divergence between a graph model and its fair I-projection as a fairness regularizer," in Joint European Conf. on Machine Learning and Knowledge Discovery Dutabases. Springer, 2021, pp. 351-366.
[40] X. Ying and X. Wu, "Graph generation with prescribed feature constraints," in Proceedings of the 2009 SIAM International Conference on Data Mining. SIAM, 2009, pp. 966-977.
[41] D. Chakrabarti and C. Faloutsos, "Graph mining: Laws, generators, and algorithms," ACM computing surveys (CSUR), vol. 38, no. 1, pp. 2-es, 2006.
[42] L. Rendsburg, H. Heidrich, and U. Von Luxburg, "Netgan without gan: From random walks to low-rank approximations," in International Conference on Machine Learning. PMLR, 2020, pp. 8073-8082.
[43] M. Simonovsky and N. Komodakis, "Graphvae: Towards generation of small graphs using variational autoencoders," in Artificial Neural Networks and Machine Learning- ICANN 2018: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part 1 27. Springer, 2018 pp. 412-422.
[44] J. Liu, A. Kumar, J. Ba, J. Kiros, and K. Swersky, "Graph normalizing flows," Advances in Neural Information Processing Systems, vol. 32, 2019.
[45] C. Niu, Song, Song, Zhao, A. Grover, and S. Ermon, "Permutation invariant graph generation via basee generative modeling," in International Conference on Artificial Intelligence and Statistics. PMLR, 2020, pp. 4474-4484.
[46] Jo. S. Lee, and J. Hwang, "Score-based generative modeling of graphs via the system of stochastic differential equations," in International Conference on Machine Learning. PMLR, 2022, pp. 10 302-1032000 383.
[47] M. Li, E. Kreačić, V. K. Potluru, and Li, "Graphmaker: Can diffusion models generate large attributed graphs?" arXiv preprint arXiv:2310.13833 2023.
[48] X. Chen, J. He, X. Han, and L.-P. Liu, "Efficient and degree-guided graph generation via discrete diffusion modeling," arXiv preprint arXiv:2305.04111 2023.
[49] L.. Zheng, D. Zhou, H. Tong. Xu, Y. Zhu, and J. He, "Fairgen: Towards fair graph generation," arXiv preprint ar 203.77300 2023.
12

---

[50] B. Hofstra, R. Corten, F. Van Tubergen, and N. B. Ellison, "Sources of segregation in social networks: A novel approach using facebook," American Sociological Review, vol. 82, no. 3, pp. 625-656, May 2017.
[51] J. Austin, D. D. Johnson, J. Ho, D. Tarlow, and R. Van Den Berg, "Structured denoising diffusion models in discrete state-spaces, Advances in Neural Information Processing Systems, vol. 34, pp. 17 911998111 18717 993, 2021.
[52] K. Jarrett, K. Kavukcuoglu, M. Ranzato, and Y. LeCun, "What is the best multi-stage architecture for object recognition?" in 2009 IEEE 12th international conference on computer vision. IEEE, 2009, pp. 2146-2153.
[53] L. Ba, R. Kiros, and G. E. Hinton, "Layer normalization." arXiv preprint arXiv:1607.06450 2016.
[54] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad, "Collective classifica- tion in network data," magazine, vol. 29, no. 3, pp. 93-93, 2008.
[55] O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann, "Pitfalls of graph neural network evaluation." arXiv preprint arXiv: 11X.::1811.0586.. 2018.
[56] D. Dua, C. Graff el al., "Uci machine learning repository," 2017.
[57] O. D. Kose and Y. Shen, "Fairgat: Fairees-awware graph attention networks," arXiv preprint arXiv:2303. 14591, 2023.
[58] J. Ho, C. Saharia, W. Chan, J. Fleet, M. Norouzi, and T. Salimans, "Cascaded diffusion models for high fidelity image generation," " The Journal of Machine Learning Research, vol. 23, no. 1, pp. 2249-2222 2281, 2022.
[59] C. Vignac, I. Krawezuk, A. Siraudin, B. Wang. V. Cevher, and P. Frossard, "Digress: Discrete denoising diffusion for graph generation." " in Proceedings of the 11th International Conference on Learning Representations, 2023.
[60] Erdos and A. Renyi, "On random graphs i," Publ. math. debrecen, vol. no. 290-297, p. 18, 1959.
[61] P. W. Holland, K. B. Laskey, and S. Leinhardt, "Stochastic blockmodels: First steps," Social networks, vol. no. pp. (09-137, 1983.
[62] T. Chen, W. Zhang, Q. Lu, K. Chen, Zheng, and Y. Yu, "Sydfeature: a toolkit for feature- based collaborative filtering," The Journal of Machine Learning Research, vol. 13, no. 1, pp. 3619-3622, 2012.
[63] T. N. Kipf and M. Welling, "Variational graph auto-encoders," arXiv preprint arXiv:1611.07555 2016.
[64] X. Glorot and Y. Bengio, "Understanding the difficulty of training deep feedforward neural networks," " in Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), May 2010, pp. 249-256.
[65] D. P. Kingma and Ba. "Adam: A method for stochastic optimization," arXiv preprint arXiv:1412.6988, 2014.
[66] J. Gasteiger, A. Bojchevski, and S. Günnemann, "Predict then propagate: Graph neural networks meet personalized pagerank," in International Conference on Learning Representations, 2018.
[67] M. Y. Wang, "Deep graph library: Towards efficient and scalable deep learning on graphs," in ICLR workshop on representation learning on graphs and manifolds, 2019.
[68] I. Takac and M. Zabovsky, "Data analysis in public social networks." in International Scientific Conference and International Workshop. 'Present Day Trends of Innovations', vol. 1, no. 6, May 2012.
13

---

A
Assumptions and Real-Worke Graphs
In order to show that the assumptions made in Subsection are typically valid for real-world graphs, here we present the exact values of the terms within Assumptions and for the datasets we use. Specifically, we make the following assumptions:
B Bx
A2:
Vu, E Sk. Ak E (1,..., ,K)
18t
N-18=1
A3:
Ev.eyey Aij B d
E
Vo, e V.
First, for Assumption 2, we obtained the real values of the terms 4 == EA UA [4]] and T'k
[Su]
where want 4 2 ri E (1.... ... K}. For all different sensitive groups, these values are presented in Table all the used datasets.
N-IS&l
Table 5: Validity of Assumption 2 for real- world graphs.
1s
0.0087 Yi
0.0174
0.0095
0.0035
0.0073
0.0094
0.0156
74
F5.
16
0.0024
0. 0.0022
0.0021
0.0021
0.0019
0.0019
0.018
Citeseer
lu
la
4
4
0.0028
0.0026
0.0047
0.0026
0.0039
0.0034
0.0011 1
0.0012
0.0018
0.0011
0.0013
0.0009
Amazon Photo
lg
6
4
4o
le
0.0874
0. 0.0094
0.0428
0.0214
0.0260
0.0262
0.0202
0.0484
0.0055
0.0037
0.0045
0.0057
0.0054
0.0032
0.0088
0.0088
Amazzo Compuler
lg
l
l
4
4
le
17
18
t
0.0381
0.0078
0.0178
0.0281
0.0080
0.0891
0.0376
0.0219
0.0096
0.0696
0.0023
0. 0.0033
0.0026
0.0034
0.0064
0.0024
0.0040
0.0017
0.0036
0.0024
For Assumption we present the real values of the terms Σ En.,, Asg and E E [d where
want ,n. in Table
eV Aij > E Ea [d]]. For all real-world datasets use, these values are reported
Table 6: Validity of Assumption 3 for real-world graphs.
Cora
Citeseer
Amazon Photo
Amazon Computer
Enjyy Ev Ag
10556
9104
238162
491722
B Ba.ey [d))
1.48
1.45
10.76
15.93
Overall, the results presented in both Tables 5ldd demonnstrae that the assumptions made for theoretical bias analysis in Section (.. [..e valid for the real-world graphs we are using. This supports that our analysis is applicable to most of the real-world data and settings.
B Proof of Theorem i
Here, without loss of generality, we will focus the ith GNN layer, where the input representations are represented by H' and output representations are denoted H The considered disparity measure follows as:
((+1) : =|
B
b 1+1
s;
E BA
[b/
s; +
ki
(8)
2
14

---

Let's re-write the disparity measure g(++)) by using definitions c/'1 Whe, and E. Falh?"
a V )t))
8/ 1((11)
E A
[b|+]
S; =
- -UU-s [
8 & x1112.
/
(9)
1
Σ o
Σ
Alses/
1
Σ Aneo
S
N - Sk
ByEV
"yEV
2.
Using Lemma A.1. in (57), it can be shown that olt)1) can be upper- bounded as:
)1
[1+1]]_
1
Σ DGEV
Anses)
E
Σ
Anjo
%
Sk
N
S&
v.
vifSe
BBEV
(10)
1
Σ
E
Aijo;
1
Σ
Σ
NA
Sk
N
Sk
2yEV
S. 2YEV
Then, we can divide the sums over all nodes into two: nodes in Sg and the remaining ones.
(1+1)
I
Σ
Σ
ANje N - SS
E
Σ
Anc.
+ +2VNA:
[Sk]
U.ES MyEV
v. UyEV
(1((1)
T.
1
Σ
Σ
Asje +
Σ
Σ
Aijoz
Sk
[Sk]
V.ES$ 1,
V, 1y
1
Σ
Σ
AOee + N Sk
Σ
Σ
Anjo
+2/NA.)
(1))
SK
W. e/
2
L
Σ
Skl
Aij
N - -Ss
1
Σ
Aij
Cj
RyES
0:E5%
V.RS&
Σ
Σ
Au
Σ
Auj
+2V
Cj
S
N
S&
Then, by triangle inequality, it follows that:
1/ L
(1+1)
SL
Σ
Auj
Àij
Cj
N
Sk
Ey
(12)
+
Σ My C.S.
Auj
Asj
Cj
+ 2v
+2VNA,
SA
N S&
Assumption 2 in Subsection
4.1 ensures that
S Er.es A.j
Σ Eugs, A.j
S-
0, Vu, E Sp- Furthermore, third assumption presented in Subsection guarantees that
E Av - N=13.1 Engs, A.)) S O, Vny & Se. Utilizing Assumption in Subsection c lloo S 5, Vog E V. the following upper bound can be derived.
g1+1 < L
Σ
A
Σ
Aij
8 po41)
Sk
N
St
Sy
U.ESt
(13)
+
Σ
Σ
Agj
1
Aij
8 8pa-n
+2/NA,
S
N - SA
U.
15

---

where 8 pe++ stands for an F(++1) dimensional vector with all elements being equal to 8. Then, by utilizing the definitions pk EE Aij. = Ey Aig the upper bound in can be rewritten as:
13
g(+1))
SL
Σ
Aij
Σ Asj
8 p(++)
Sk
N
Sk
2
1
+
Σ
Agj
Aij
p((+t)
+ +2VNA,
Sk
N
SS
1
I.
Pk:
PE
8
8
+
BEBEEE Ai
- Ph
2p
Pk
8 p(1
+ + NA +2VNAA
Sk
N
S
N - Skl
S
PR
Pk
Eninyey Aij Pk
-2p%
Pk
= L
18
110 110 112 + +22 NA2
N
S
N -Sk
[&
(14)
The final result follows from the inequality, 1|ō Fa++ 112 S. 88 6VF(++]];
k (1+1))
= [ [b:
k]
E BA,
[1/t1 88 + k|] 6i|11
S 8V F(+1)
pk |Sa|
Px - - |
Empyey Asj - -p% - 22
Pk
+2 NA,
N- Sk
|Sk]
(15)
which concludes the proof.
C Proof of Proposition
1
Statistical parity for link prediction defined as (19):
ASp == (r.rs)) xvv (o Uy) ss = =sy] - (i... wz)) s; + sy]l.
(16)
By considering each sensitive group explicitly, statistical parity can also be written
K
Sk (Exlo(vi N
ASP
sj k] Exlo(us, U2) 8i + 83.
k))
(17)
Define EE V, lb; that hbll22 S g, Vo, E V and it holds that ||E A
k] = P& and B 5.) h: 9; * k] = q.. We further assume
[,; s; = k]
E -, [h, 8j +
kill2 S 8 Using the definitions for pa and qu and link prediction model g0,, U3)) = h 2h,, Asp can be reformulated as:
K
Sk
ASP-
Ep.
Pk [TE)))
N
(18)
K
Syl
E(px -qh))
N
By triangle inequality, it follows that
ASP
S&
(p:
E(pt
-q+))
(19)
N
k=
16

---

Finally, by using Cauchy-Schwarz inequality and the assumption ||b:ll2 S q. Ve, E V, we can conclude that
K
Skk N
sPp
9
(px
qu)
(20)
K
Skx|
ASP
2
N
where the final inequality follows from the assumption that | A h: |
8i = k]]
E Aa se) [y 83 * kill22 I 8max.
D Diffusion Model
Diffusion Models for Graph Generation. Briefly, diffusion models are composed of two main elements: a noise model q, and a denoising neural network Φa. The noise model q progressively corrupts data to create a sequence of increasingly noisy data points. Inspired by the success of Gaussian noise for diffusion-bassee image generation (58), the earlier diffusion-based graph generation models employ Gaussian noise create noisy graph data (45) 46). However, such noise model cannot properly capture the structural properties of discrete graph connections. Motivated by this, a discrete noise model is introduced in (5I). The discrete noise model for graph structure is typically applied in the form of edge deletion and additions (16 47). After creating noisy data, a denoising network do is trained to invert this process by predicting the original graph structure A from the noisy samples. While different neural network structures are examined as candidates for the denoising network, message-passing neural networks are shown be a scalable solution for the creation of medium- to large-scale graphs (47).
Forward diffusion process: introduced in (5I), we employ Markov process herein to add noise to the input graph structure in the form of edge additions or deletions. These edge modifications can be executed by modeling the cxistenceenon--xiistenne of edge as the edge class labels, where we have 2 classes, and applying a transition matrix that switches the labels with a certain probability. Then, given A TR X denotes the one-hot representations for the edge labels, the noise model can be described by the transition matrices Q2 E T 2x2 for t = 1,, ....................... ,T, where (AA' A A'-1)= = A'-'Q' Q'a- q(A' A = A' and Q' = Q2 ... Q42 For a uniform transition model, (59) proves that the empirical data distribution (the probability for the existence of an edge) is the optimal prior distribution. Following this finding, we specifically employ the transition matrix:
Imm where I E _2x2 is the identity matrix, 1 E R² is a vector of ones, and mg E R²2 describes the distribution of edge labels in the original graph. For the assignment of a², cosine schedule utilized, where a² == cos (0.5m(t/T + s)/(1 s))² with small s value for a' = II' a Note that for categorical nodal features, the forward diffusion process follows the same procedure.
Q = a'II+
(21)
Sampling: Using the trained MPNN, synthetic graphs can be sampled iteratively. During sampling, we first sample the sensitive attributes of the nodes, S, based on its original distri- bution in the real graph. As the next step, we need to estimate the reverse diffusion iterations pa (g--1 (A' x 1 g (A,,)))), which is modeled as a product over nodes and edges (59):
Pe |
II f=1
II f=1
Pe
(22)
II Pe
(A g. S.,..t).
ISKSEN
To compute each independent term, we marginalize over the predictions of the MPNN:
A
g't
Σ pe
(A
Ag = = pe (AU = e S.t)
BEE
(23)
Σ EEEc
Po (A
Aig = e, 9¹ Aije:
17

---

where ed denotes all possible labels for edges, which are {0, 1 for an unweighted graph. Then, we can use our Markovian noise to model pa [A]
Auj = =,, e
po (A A.g -. q 0
e e A
(A
A. = =
3j
otherwise.
Note that posterior q (A Aij e, Ajj) can be computed in closed-fome using Bayes rule. Leveraging this model, G can be sampled, which becomes the input of the MPNN at the next time step.
E
Additional Details on Datasets and Datasets Statistics
For citation networks (Cora and Citeseer), the one-hot encoding representations of the words in the article descriptions constitute the binary nodal attributes. In these networks, similar to the setups in
19 37), the category of the articles is employed as the sensitive attribute. Furthermore, for product again the one-hot encodings of the words in the product reviews and the product categories are utilized as the sensitive attributes. For the evaluation of node classification, employ German (56) and Pokec-n (9) networks. Specifically, the German credit graph has 1,000 nodes representing the clients in a German bank, where the links are created based on the similarity of credit accounts. For this graph, the node labels classify clients into good vs. bad credit risks, where the clients' gender are employed as the sensitive attribute (28). In addition, Pokec-n is sampled from an anonymized version of the Pokec network of 2012 (a social network from Slovakia), where nodes correspond to users who live in two major regions, and the region information utilized as the sensitive attribute (9). The working field of the users is binarized and utilized the labels to be predicted in node classification.
co-purchase networks, nodal attributes
Table 7: Dataset statisties.
Dataset
[V]
[E]
K
Cora
2708
10556
1433
7
Ciesseer
3327
9228
3703
6
Amazon Photo
7650
238163
745
8
Amazon Computer
13752
491722
767
10
Credit
22242
Pokec-n
6185
21841
59
2
Statistical information for the utilized datasets are presented in Table 7 where the total number of nodal features and K represents the number of sensitive groups.
F Evaluation with Statistics
We evaluate the created synthetic graphs by FairWire via link prediction in Subsection 6.2 order to provide traditional evaluation scheme, here we also report the 1-Wasserstein distance between the node degree distribution and clustering coefficient distribution of original graph and the synthetic ones. Table presents the corresponding distance measures, where lower values for all metrics signify better performance. In Table ER and SBM stand for traditional baselines Erdos-Rényi model (60) anf SBM stochastic block model (61, respectively. Furthermore, as deep learning based baselines, Feature-based MF represents feature-based matrix factorization (62), GAE and VGAE stand for graph autoencoder and variational graph autoencoder (63), respectively. Finally, GraphMaker in Table 8 corresponds to diffusion-bause graph generation baseline (47). Note that all these baselines are -agnesss-gnostic..... Overall, results Table siggiif that FairWire can create synthetic graphs that follow similar distribution to the original data while also improving the fairness metrics.
G Implementation Details
Link Prediction Model. For link prediction, we train a one-layer graph convolutional network (GCN), where the inner product between the output node representations signifies the corresponding edge probability. For training, 80% of the edges are used, where the remaining edges are split equally into two for the validation and test sets. For link prediction experiments, results are obtained for five
18

---

Cora
Citeseer
Amazon Photo
Degree +
Cluster
Degree,
Cluster,
Degreel,
Cluster
ER
1.0
2.4e
8.5e -
1.4e
1.9e
4.0e*
SBM
9.6e
2.3e'
8.0e
1.4e
1.5e
3.8e*
Feature-based MF
1.3e
2.4e
1.7e
1.4e*
3.8e
4.0e*
GAE
1.3e
2.4e
1.7e
1.4e!
3.8e
4.0e
VGAE
1.4g
2.4e!
1.7e.
1.4e.
3.8e
4.0e.
GraphMaker
2.8
2.3e
5.6e
1.4e
1.1e²
1.4
FairWire
1.9
2.4c*
8.7e-1
1.4e*
8.2e
1.5
Table 8: Distances of statistical measures between the real graph and synthetic ones.
random data splits, and their average along with the standard deviations reported. The weights of the GNN model for link prediction are initialized utilizing Glorot initialization (64), where it is trained for 1000 epochs by employing Adam optimizer (65). The learning rate, the dimension of hidden representations, and the dropout rate are selected via grid search for the proposed scheme and all baselines, where the value leading the best validation set performance is selected. For learning rate the, the dimension of hidden representations, and the dropout rate, the corresponding hyperparameter spaces are (le 1, le 3e 3, le 3). (32, 128, 512). and (0.0, 0.1, 0.2), respectively.
Diffusion Model. Diffusion models are trained for 10000 epochs by employing Adam optimizer (65. where the number of diffuusion steps is 3. In the MPNN described in Subsection [3.2 hidden representation size for time step t is 32 for Cora and Citeseer and 16 for the Amazon Photo, German credit, and Pokec-n networks. In addition, hidden representation sizes for the nodal attributes and sensitive attributes are 512 and 64, respectively, for all datasets. The MPNN consists of two layers.
Node Classification Model. For node classification, we employ one-layer and two-layers APPNP (66) networks for German credit and Pokec-n graphs, respectively. For training, 50% of the nodes are used, where the remaining nodes are split equally into two for the validation and test sets. The weights of the GNN model for node classification are initialized utilizing Glorot initialization (64), where is trained for 1000 epochs by employing Adam optimizer (65). The learning rate, the dimension of hidden representations, and the dropout rate are selected via grid search for the proposed scheme and all baselines, where the value leading to the best validation learning rate the, the dimension of hidden representations, and the dropout rate, the corresponding hyperparameter spaces are (3c 2, le 3e 3). (32, 128, 512]. and f0.0, 0.1), respectively.
performance is selected. For
Hyperparameter Selection. For the link prediction task, we select the multiplier LFainine among the values (0.01, 0.05, 0.1. 0.5) via grid search (the multiplier of the cross-entropy loss is 1). The results for Lrairiire in Table are obtained for the À values 0.05, 0.1, 0.01 /0.05, 0. on Cora, Citeseer, Amazon Photo, and Amazon Computer, respectively. For adversarial regularization (9), the multiplier of the regularizer is selected via a grid search among the values {0.1, 1, 10} (the multiplier of link prediction loss is again 1). The multiplers of the adversarial regularization for the results in Table 2 are {10, 1, 1, 1} on Cora, Citeseer, Amazon Photo, and Amazon Computer, respectively. Furthermore, the hyperparameter 8 in FairDrop algorithm is tuned among the values (0.16, 0.25) (0.16 is the default value in their codes), where 0.16 led to the best faimess/utility trade-off on each dataset. For FairAdj 19), we use the hyperparameter values suggested by (19) directly for the citation networks.
are
For the generative models, we select the multiplier of LraieWire (A in among the values (0.05, 1.0, 10.0) via grid search. The results for FairWire in Table 3 are reported for the A values 10.0, 0.1 on Cora, and Citeseer, respectively (A = 0.05 for Amazon photo in Table [T]. For the results in Table 4 À cquals to 10 and 1 for German credit and Pokec-n, respectively. For adversarial regularization (9), the multiplier of the regularizer (again in the training loss of the MPNN) is selected via grid search among the values {0.001, 0.01, 0.1]. The multiplers of the adversarial regularization for the results in Table 3 are (0.01, 0.01, 0.01) respectively. Furthermore, the hyperparameter 7) in FairAdj (19) algorithm is tuned among the values (0.001, 0.005, 0.01}. where 0.001 led to the best faimess/utiltty trade-off on each dataset.
} on Cora, Citeseer, and Amazon Photo,
Baselines. Fairness-awarr baselines in the experiments include adversarial regularization ( FairDrop 377, FairAdj (19), and FairGen (49). Adversarial regularization refers to the bias mitigation technique where adversary is trained to predict the sensitive attributes. In link prediction, the
19

---

adversary is trained to predict the sensitive attributes of the nodes that are incident to the edges whose labels are of interest. Furthermore, FairDrop (37) an edge dropout strategy where the dropout probabilities vary for intra- or inter-edges so to create more balanced graph topology. FairAdj (19) optimizes a fair adjacency with certain structural constraints for link prediction in an iterative manner considering both fairness and utility. Finally, FairGen (35) focuses on the disparities in generation quality (distances between different graph statistics) for different sensitive groups and employs fairness-aware regularizers during graph generation via transformer-based model.
For graph generation experiments, GraphMaker (47) is utilized create synthetic graphs in fairness- agnostic way. While an existing work that considers fair link prediction for synthetic graphs is not available to the best of our knowledge, we employ adversarial regularization (9) as an mn-prcessiing bias mitigation strategy during the training of the MPNN described in Subsection 5.2 Furthermore, we use FairAdj (19) as a post-processing bias mitigation strategy on the synthetic graphs generated via GraphMaker, and the processed synthetic graphs are then evaluated for the link prediction and node classification tasks.
H Sensitivity Analysis
In order to examine the impact of hyperparameter selection faimesss improvements, the sensitivity analyses for the proposed tools are executed with respect to the hyperparameter A.The results are obtained for changing À values for both the link prediction (see 4 and graph generation (see (7) experiments and reported in Tables 9 10 Overall, the results signify that both LraieWire in the link prediction and FairWire, lead to better fairmess measures compared to the natural baselines within wide range of hyperparameter selection.
Table 9: Sensitivity Analyses for Different Tasks
Cora
Citeseor
Link Prediction
AUC (%)
Asp (%)
Ago (%)
AUC (%)
Asp (%)
Ago (%)
GNN
94.43 0.74
27.01 + 1.38
9.11 + 1.43
96.16 + 0.28
27.40 1.24
7.37 1.33
À 0.01
93.85 + 1.06
16.17 + 4.50
5.58 1.18
95.55 0.66
17.38 7.80
6.55 2.33
À 0.05
92.18 + 1.08
1.76 0.24
2.05 + 0.37
96 18 + 0.46
12:43 0.57
5.11 = 0.86
0.1
1.05
Amazon Photo
Amazon Computer
Link Prediction
(UC(%)
Agr (%)
ARG (%)
AUC (%)
Agr (%)
ARo (%)
GNN
97.01 1: 0.26
32.65 d: 0.95
8.01 0.52
96.13 0.06
23.70 0.79
5.51 0.79
4: 0.52
0.41
0.08
0.63
À 0.05
94.85 1 0.32
24.61 1: 0.96
6.24 1: 1.22
96.17 = 0.13
22.74 = 0.39
5.50 1: 0.51
4: 5.12
Citescor
Amazon Photo
Graph Generation
AUC
Asr (%)
Ago (%)
AUC (%)
Asr (%)
ABo (%)
92.19
37.56 + 1.29
+ 0.92
0.21
33.49 0.28
+ 0.56
À 0.01
92.03 1 0.80
36.43 1: 1.44
13.11 1: 0.71
93.41 D.34
27.18 5.45
5.45
0.80
0.05
91.89 + 1.37
29.40 + 4.34
9.56 1.20
93.88 0.40
25.27
0.76
3.13
0.30
À = 0.1
91.27 + 2.78
18.35 6.91
7.80 2.66
88. = 5.12
17. 78.78.75
7.27
1.48 # 1.00
Table 10: Sensitivity Analysis for Graph Generation on Cora
Cora
AUC (%)
Agp (%)
Ágo (%)
87.29 1.09
35.72 + 1.74
13.27 0.81
1.0
88. 76 1.23
27.86 4 2.84
10.76 1.50
10.0
2.79
+ 6.35
4.31 3.59
A 50.0
82.91 + 8.06
9.86 4 6.54
3.47 +: 2.58
20

---

I Additional Graph Generation Results
Due to limited space, we present the comparative results for graph generation on Amazon Photo in Table 11 for link prediction.
Table 11: Graph generation results on Amazon-Phote
Amazon Photo
(%)
(%)
Aso (%)
96.91
32.58
8.21
94.45 + 0.21
33.49 + 0.28
10.01 + 0.56
Adversarial
94.24 1: 1.20
29.17
2.83
7.06
2.63
Fair
25.27
Similar to the link prediction experiments (Table 2), the results of FairAdj for the Amazon Photo network could not obtained due to computational limitaaion Overall, the results reported in Table conclude again that FairWire provide the best utility/faimess trade-off compared other aaireess-wware baselines.
11
J
Computational Resources
Experiments carried over on 4 NVIDIA RTX A4000 GPUs.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: For cl, please see Subsection 4. The contribution in c2 presented in 4.2 For c3 and c4, please check Subsections 5.1 and respoectively. Finally, the experimental results emphasized c5 presented Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Please see Limitations in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiaatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
22

---

Answer: [Yes]
Justification: Our assumptions are explicitly presented Subsection 4.1 proofs are available in Appendices and
Furthermore, all
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversell, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
The proposed regularizer is presented with its derivation in Subsections 4.1 and 4.2 Furthermore, for reproducibility of the empirical evaluation, our codes are provided within the supplementary material of this submission. All experimental settings are also described in Subsection 6.1 and Appendix G
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
23

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Codes to reproduce all the results in Section are provided in the supplemen- tary material to this submission.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
publite/giidee//deeebbbmisss wnt.ssabisssoooooooooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
//nips /nips.cc/puut
guides/ PwoddSSumiissioooool....oooooooo
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Please see Subsection 6.1 and Appendix G
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All experimental results are obtained for multiple random seeds and their average together with standard deviations are reported.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
24

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Computational resources used for the experiments are clarified in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpps:/neuurps. htcc/p/bbicc/thiccccceeeeell...d
Answer: [Yes]
Justification: To the best of our knowledge, our research is completely compliant with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This work addresses possible bias propagated by ML algorithms. Hence, it in fact helps mitigate crucial negative impact of ML.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
25

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Citation and Amazon networks provided by the DGL library (67). which is explained and the corresponding license is explicitly provided in the README file in our supplementary material. Furthermore, the Pokec dataset, used in this study, was created and presented in (68), which is again mentioned the README file in our supplementary material.
Justification:
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
26

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, palasets.papersstt paperswi thcode. com con/dataset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
27

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "lVavWATtzJ", "reviewer": "Reviewer_wVX7", "summary": "The impact of generative learning algorithms on structural bias is investigated in this paper. The authors provide a theoretical analysis on the sources of structural bias which result in disparity. Then a novel fairness regularizer is designed to alleviate the structural bias for link prediction tasks over graphs. Furthermore, a fair generation framework called FairWire is proposed by leveraging the fairness regularizer in a generative model. Finally, extensive experiments on synthetic and real datasets are conducted to show the effectiveness of mitigating structural bias in machine learning algorithms on graphs.", "questions": "1. The author introduce GraphMaker as a backbone generative model and claimed that this method considers the bias mitigation when generating new graphs. Does it mean that FairWire can not been used on other generative models?\n2. In the experiments, for the supervised tasks the author use link prediction tasks results, while for generation tasks, the author use node classification tasks results. What is the results of node classification tasks for supervised tasks? It would be better that the same tasks are used to evaluate both the supervised and generative tasks.\n3. The authors claim the contribution in fairness over generative graph algorithm, but also provides a lot experimental results on supervised tasks. What is the difference in structural bias problem over generative tasks and supervised tasks?\n4. From the experimental results, FairWire makes the performance of AUC worse. What is the influence of FairWire on the accuracy of the GNN model? Does it influence the model training or that because GNN models conducts bias on different samples? \n5. From the theoretical analysis of the paper, we have to know the sensitive group first, how would you define and select sensitive groups? What kind of influence does sensitive group have on GNN and the proposed FairWire method?", "limitations": "The authors adequately addressed the limitations of their methods. And It is hard to foresee any potential negative societal impact of this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The theoretical analysis on the sources of structural bias is novel and intuitive, which provides an interesting perspective on what causes the bias problem in machine learning algorithms over graphs.\n2. The design of the regularizer and fair graph generation model address the challenges and theory reasonably. Besides, sufficient experiments are provided to prove the better performance on mitigating the structural bias problem.\n3. The paper's writing is good, and the overall structure is clear.", "weaknesses": "1. This paper aims to address the fairness in graph generation. But there are not sufficient experiments on different representative backbone generation models. The authors only provide one backbone generation model, I suggest more representative backbone generation model to solidify the effectiveness.\n2. This paper provides the theory and algorithm based on the sensitive group which may limit the use to real world graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their insightful comments regarding our work. We have addressed the Reviewer’s comments, and placed our responses to each comment below. Please note that references written in [R#] format are provided at the end of this rebuttal, whereas the ones in [#] format correspond to the respective references in the paper.\n\n**Q1:** Thank you for this question. \n\nThe proposed fairness regularizer (Eq. 3) in FairWire can be utilized in any generative model outputting probabilistic graph topologies, including but not limited to graph autoencoder-based or random walk-based graph generation models (see Remark [*Applicability to general generative models*] in the submission). In other words, although our submission focuses on its use for graph diffusion models, the proposed framework provides a versatile use with different graph generative models.\n\nThat said, to address the reviewer's comment, we also obtained results for the use of $\\mathcal{L}_{\\text{FairWire}}$ in a variational graph autoencoder-based (VGAE-based) graph generation [R1]. Note that VGAE does not inherently possess the ability to generate synthetic node features  and sensitive attributes. Thus, we used the real nodal features and sensitive attributes with the synthetic graph structures for evaluation. Tables below report the link prediction results, with models trained over real ($\\mathcal{G}$) and synthetic graphs for Cora and Citeseer networks (see Experimental Setup in Subsection 6.1). These additional results also confirm the effectiveness of our proposed tool for fair graph generation.\n\n|  Cora | AUC (%)  | $\\Delta _ {SP} $(%) | $\\Delta _ {EO} $(%) | \n| :--- | :----:  |  :----:  | ---: |\n| $\\mathcal{G}$ |**94.92** | 27.71 | 11.53 |\n| VGAE | 92.51| 34.99 | 9.40|\n| FairWire | 92.00|  **5.08**  |  **2.07**|\n\n|  Citeseer | AUC (%)  | $\\Delta _ {SP} $(%) | $\\Delta _ {EO} $(%) | \n| :--- | :----:  |  :----:  | ---: |\n| $\\mathcal{G}$ |**95.76** | 29.05 | 9.53 |\n| VGAE | 92.30| 33.79 | 9.62|\n| FairWire | 92.79|  **4.05**  |  **1.88**|\n\n**Q2:** Thank you for this question. \n\nWe would like to clarify that for graph generation, we present our results for both link prediction (see Table 3) and node classification (see Table 4). In addition to graph generation, we also present supervised link prediction results in Table 2 to exemplify another use of the proposed regularizer. In fact, our regularizer can be employed for any training scheme outputting edge probabilities (e.g., supervised link prediction, graph generation).\n\n**Q3:** First, we would like to clarify that our link prediction and node classifications results in Tables 3 and 4 are obtained over synthetic graphs created via generative models. In addition to them, we also wanted to demonstrate the effectiveness of the proposed regularizer for a different learning framework to show its versatile use (i.e., supervised link prediction) in Table 2.  \n\nApart from this clarification, we want to thank you for your insightful question. While it has been demonstrated that learning over real graphs for supervised tasks leads to algorithmic bias due to the structural bias in graphs [11], use of synthetic graphs makes the fairness issue more complex and challenging to resolve. As generative models learn to mimic the frequent patterns in real data (i.e., well-represented groups), there is a high probability that they will overlook the patterns exhibited within under-represented groups. Hence, they are prone to amplify the already existing structural bias [48]. We also confirmed this structural bias amplification empirically via our results in Table 1, which shows that the use of generative models worsens all fairness metrics over four different real-world datasets and motivates our proposed framework. \n\n**Q4:** In general, for all fairness-aware interventions, we expect to observe a fairness/utility trade-off [R2, R3], as bias mitigation algorithms introduce a fairness-related metric to consider in addition to utility, which typically leads to a solution that is not optimal for utility-only considerations. Thus, the observed utility/fairness trade-off is a natural outcome of introducing the proposed fairness regularizer (Eq. 3) in training to make it fairness-aware. Note that a similar trade-off can also be observed for our fairness-aware baselines (Adversarial, FairAdj, FairDrop) as well. Our results in Tables 2, 3, and 4 demonstrate that FairWire typically leads to the best utility/fairness trade-off compared to these works. \n\n**Q5:** In fairness literature, sensitive attributes are defined as the ones on which we do not want our algorithm’s predictions to depend for fair decision making. For example, recidivism predictions made by a ML model should not be related to the ethnicity of the convicts, making ethnicity the sensitive attribute and different ethnic groups the sensitive groups. Overall, the selection of sensitive groups is mainly governed by the application in which the learning model is used. \n\nIn most of the fair ML literature, it is a common practice to assume that the sensitive attributes are known and given, see [7, 24, 27]. Furthermore, the real-world datasets we employed in our experiments and the sensitive groups within them have been used in existing fairness-aware graph ML works, see e.g., [11, 36, 27, 19]. \n\nWe hope this explanation addresses your concern.\n\n---\n[R1] T. N. Kipf et al., “Variational graph auto-encoders,” NeurIPS Workshop on Bayesian Deep Learning, 2016.\n\n[R2] S. Dehdashtian et al., \"Utility-Fairness Trade-Offs and How to Find Them,\" CVPR, 2024.\n\n[R3] M. Pannekoek et al., \"Investigating trade-offs in utility, fairness and differential privacy in neural networks,\" arXiv preprint arXiv:2102.05975 (2021).", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "2E84pk2NoL", "reviewer": "Reviewer_miG4", "summary": "This work considers the problem of fairness in learning over graphs. Namely, it adopts a criterion for fairness that quantifies the probability of a relationship existing between nodes whose sensitive attribute value matches (intra-edges) versus not (inter-edges). It first derives theoretical results that bound the discrepancy between the two, and uses these insights to design a \"fairness regularizer\" that is compatible with both link prediction and synthetic graph generation tasks. The authors perform an evaluation on these two tasks, outperforming existing baselines in fairness metrics while preserving the core utility metric (e.g., accuracy).", "questions": "Please address the potential weakness discussed above. Additional questions and comments:\n\nC1. Could you discuss what happens if there is >1 sensitive attribute? Do your results already apply via some transformation, or what would be required to generalise to this case?\n\nC2. Line 131-32: I think this claim needs to be scoped to e.g. *social* networks, as this is definitely not always the case (see e.g. ref [2] above).\n\nC3. Line 153: maximization is over $k$ presumably?\n\nC4. Line 167; Eq 3: $\\mathbf{Se}_{k}$ not defined as far as I can tell.\n\nC5. Experiments in 6.2: I think it should be discussed what \"base GNN\" is being used. Appendix G mentions it is a GCN -- but what is the justification for using a single layer?\n\nC6. I think it's worth summarizing the choice and justification for the considered sensitive attributes in the main text (currently in Appendix E).\n\nC7. Table 5 is overflowing the margins, consider wrapping in `\\resizebox`", "limitations": "Limitations and potential negative social impacts are discussed, although the latter only superficially, and I think it deserves more discussion given the primary area of the paper is fairness.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper considers a problem that has been studied previously but is original in the way it approaches it. The quality of the work is high and contains both theoretical insights and thorough experiments. The organisation of the paper is clear and the writing quality is also high. The topic is significant and relevant to the NeurIPS community. Reproducibility is also good as code is provided and experiments are described clearly.", "weaknesses": "The paper is very well executed. In my opinion, its main weakness is that the considered fairness definition is adopted without a convincing justification. It is rather well-known in the network science literature [1,2] that individuals tend to form connections with those that are similar to them. Therefore, I do not understand why this characteristic is framed as inherently \"bad\" and something that should be corrected when training a model for link prediction or graph generation. I think this deserves a proper justification and discussion. However, this may be a point that is broader than the paper itself. \n\n[1] McPherson, M., Smith-Lovin, L., & Cook, J. M. (2001). Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1), 415-444.\n\n[2] Newman, M. E. (2003). Mixing patterns in networks. Physical review E, 67(2), 026126.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for the supportive and constructive remarks, as well as valuable comments. We have presented our responses to the Reviewer’s questions below.\n\n**Weakness:** Regarding the comment under Weaknesses, we agree with the reviewer that “individuals tend to form connections with those that are similar to them,” and we would like to clarify that such links between similar nodes in graphs are not necessarily bad, instead such connectedness generally provides additional information and is leveraged in graph ML. However, while admittedly entailing useful information for learning, the homophilic relations built based on sensitive attributes may amplify the bias in predictions [R1]. For example, it has been shown that ad recommenders display racial biases between users with similar preferences [R2], where the denser connectivity between the users from the same ethnicity in the corresponding social networks might amplify this issue. Our proposed framework aims to mitigate the structural bias leading to such discriminatory predictions in the decision systems requiring fairness considerations.\n\n**C1:** We thank the Reviewer for this insightful question. \n\nIn case we have multiple sensitive attributes, the proposed scheme can be extended in two possible ways: \n\n*Approach 1-* Applying multiple regularizers: Multiple fairness regularizers (see Eq. 3) corresponding to different sensitive attributes can be introduced and optimized jointly during the training. In fact, we do consider such an extension as a potential framework.\n\n*Approach 2-* Redefining inter/intra-edges: We can change the definition of inter- and intra-edges, where if the norm distance of multiple sensitive attributes between different nodes is lower than a certain threshold, the corresponding edges can be referred as intra-edges, while the remaining edges become inter-edges. Afterwards, we can try to balance the predicted probabilities for intra- and inter-edges with a regularizer for a better fairness. \n\n**C2:** Thank you for this comment. We agree with the reviewer and in our final submission, we will specify that this claim generally holds for social networks. \n\n**C3:** Thank you for this valuable comment. Indeed, the maximization is over k, which will be clarified better in the final submission and the corresponding equation will be corrected.\n\n**C4:** In Preliminaries, we define $\\mathbf{S}$ as the one-hot encoding of sensitive attributes; and $\\mathbf{e} _ {k}$ is defined in Line 168 as the unit vector whose only non-zero index is k (thanks to your comment, we have realized that there is a typo in its dimension, where it will be corrected to $\\mathbb{R}^{k}$ in the final submission). The term $\\mathbf{S}\\mathbf{e}_{k}$ is the matrix multiplication of these two terms. \n\n**C5:** Thank you for this question. \n\nFor link prediction, we had also obtained results with Common Neighbor (CN) [R3] and two-layer GCN models, where one-layer GCN led to the best AUC performance for our datasets. Thus, we chose our base GNN to be a one-layer GCN.\n\nWe will further clarify this in Appendix G in our final version. \n\n**C6:** We would like to kindly mention that the datasets and sensitive attributes are also used in prior fair graph ML studies; including the baselines Adversarial, FairDrop, and FairAdj. Hence, we followed the same experimental setup in said studies without choosing the sensitive attributes by ourselves, for fair comparison. We will mention this in the final version. \n\nThat said, from a purely mathematical point of view, the fairness problem considered in our study can be regarded as the problem of decorrelating the system output from a particular attribute associated with the nodes, regardless of the attribute’s relevance to real life. In this sense, the selection of sensitive attributes is not expected to affect the evaluation of such decorrelation from an algorithm design point of view.\n\n**C7:** Thank you for your keen observation, we will fix this issue in our final submission.\n\n--- \n\n[R1] E. Dai and S. Wang, “Learning fair graph neural networks with limited and private sensitive attribute information,” IEEE Transactions on Knowledge and Data Engineering, 2022.\n\n[R2] Latanya Sweeney. 2013. Discrimination in online ad delivery. Queue 11, 3 (2013), 10–29.\n\n[R3] Liben-Nowell, David, and Jon Kleinberg. \"The link prediction problem for social networks.\" Proceedings of the twelfth international conference on Information and knowledge management. 2003.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "bJiRDhAyEx", "reviewer": "Reviewer_bPaX", "summary": "In this submission a graph diffusion model with fairness correction is introduced for graph generation. The model is also applied for link prediction. The authors introduce a graph regularizer for fairness based on a theoretical bound for subgroup distance and representation distance. This analysis is newly introduced by the authors. The authors apply the regularizer to link prediction, examining the accuracy-fairness tradeoff. The authors then test fair graph generation by examining link prediction and node classification tasks, but replace the training graphs with fairness-corrected generated graphs. Empirically it is shown that this greatly improves fairness while marginally reducing accuracy.", "questions": "(1) In the second experiment type (S6.3), which link prediction model was trained on the generated graphs? And was the FairWire regularization also applied to the link prediction model during training?\n\n(2) From Fig 1 we can see that FairWire effectively removes intra-edges from generated graphs. However, the structure of the generate graphs is not quite evident. Can the graphs be visualized in a more productive way? Maybe the adjacencies can be row-sorted into their communities.\n\n(3) The authors derive two fairness criterion $\\alpha_1$ and $\\alpha_2$, though $\\alpha_2$ is ignored at the mini-batch level for scalability. Can the authors give more intution about $\\alpha_2$ and why it should ultimately not matter when applied in practice?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper has key straightforward strengths that contribute to my \"weak accept\" rating. First, the method seems to perform well, within the scope of the intended contributions. The paper is generally well-written and the presentation is clear. Furthermore the theoretical results are satisfactory. They appear correct and they properly motivate the method.", "weaknesses": "There is some missing/glossing-over existing work. The authors claim that the theoretical analysis is novel, however ref [24] in the paper also includes a theoretical analysis with >2 binary categories. It would be good for the authors to discuss this work and compare with their own. Also, the authors should consider citing \"Debiasing Graph Representations via Metadata-Orthogonal Training\" (doi/10.1109/ASONAM49781.2020.9381348), which seems relevant to the problem (also includes a fairness correction over potentially >2 attributes).\n\nThere are a non-trivial amount of clarity and presentation issues, which I discuss in my list of questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to sincerely thank the Reviewer for the raised points. We have addressed all points raised by the Reviewer, and presented our responses below.\n\n**Weakness:** We thank the Reviewer for this comment under Weaknesses. \n\nIn [24], it is stated that:\n\n“For clarity and simplicity, we consider the case of a single binary sensitive attribute, with the theoretical intuitions naturally generalizing to the multiattribute and multi-class settings.”. Hence, in their theoretical analysis, [24] considers a single, binary sensitive attribute, while we take multi-valued sensitive attributes into account in our analysis. \n\nIn addition, we want to clarify that our analysis is the first theoretical investigation for the relation between $\\Delta _ {\\mathrm{SP}}$ and the graph topology considering multi-valued sensitive attributes. The analysis in [24] concludes that if the weight of the adversarial regularizer is set to infinity, the equilibrium of their objective is achieved when there is zero mutual information between the sensitive attribute and the node embeddings. However, setting the weight of the adversarial regularizer to infinity is impractical, which limits the applicability of their analysis. Thus, there are significant differences in the theoretical findings of [24] and our work, where we specifically focus on structural bias and its analytic relation to a well-accepted bias metric $\\Delta _ {\\mathrm{SP}}$ for non-binary sensitive attributes, which was not explored before to the best of our knowledge.\n\nWe thank the Reviewer for pointing out this related work (doi/10.1109/ASONAM49781.2020.9381348), which we will cite in the final submission.\n\n**Q1:** Thank you for this insightful question. \n\nThe same link prediction model is used for link prediction (S6.2) and graph generation (S6.3) experiments, whose details are provided in Appendix G. Furthermore, we did not apply any extra fairness intervention on FairWire during link prediction model training (including FairWire regularization). FairWire only modifies the training for graph generation, as we wanted to evaluate the effectiveness of structural debiasing that is executed in a task-agnostic way. \n\n**Q2:** Thank you for this suggestion. \n\nBased on this comment, we created the visualizations for row-sorted adjacencies (based on sensitive attributes) of the real Cora network and its synthetic version created by FairWire. The created figures are presented in the attached PDF document to the General Rebuttal. The figures confirm our previous finding that, with the employment of FairWire, the links between nodes become less correlated with the sameness of sensitive attributes of the nodes. Specifically, for the real graph, most links are built within the same sensitive group (diagonal entries), while the link formation becomes more uniform across different sensitive groups after applying FairWire. \n\nIn addition, in order to provide structural information, we present the 1-Wasserstein distance between the node degree distribution and clustering coefficient distribution of the original graph and the synthetic graphs created by FairWire in Appendix F.\n\nWe hope this reply addresses your concerns.\n\n**Q3:** Thank you for raising this point. We would like to clarify that our submission does not conclude or claim that $\\alpha _ {2}$ does not matter for fairness. In fact, the consideration of $\\alpha _ {2}$ together with $\\alpha _ {1}$ might further benefit the fairness. The corresponding solutions for $( p _ {k} ^ { \\omega } ) ^ { * }$ and $(p _ {k} ^ {\\chi}) ^ {*}$ for this case are presented in Subsection 4.2. However, as the reviewer mentioned, a regularizer that is designed based on both $\\alpha _ {1}$ and $\\alpha _ {2}$ cannot be employed in a mini-batch setting, which limits its use, especially for generative models. Since the main focus of FairWire is mitigating structural bias in graph generation, which can only be trained in a mini-batch setting for medium to large-scale graphs due to a complexity growing exponentially with the number of nodes, we focused on a design that can be used in a broader range of learning settings. Our experimental results confirm the effectiveness of the proposed fairness regularizer, which typically provides the best fairness/utility trade-off compared to state-of-the-art fairness-aware baselines.", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank the Reviewers for their detailed reviews and constructive suggestions. We have addressed the questions raised by the Reviewers, and presented the detailed responses in a point-to-point manner.

Meta-review: This paper proposes a graph generation approach with fairness consideration. The authors offer theoretical analysis to bound the representation disparity between a specific group and the remaining nodes and the statistical parity. These theoretical results further lead to the proposed FairWire that aims to push the generated graph to have a desired number of intra-/inter-edges.


All reviewers appreciate the theoretical analysis of this work and acknowledge the empirical performance of FairWire. There are concerns about the clarity in terms of math notations and experiments (e.g., visualizing results in node classification, choice of base GNN, analysis of results). The authors' responses are quite comprehensive and address the concerns well. Another concern raised by the reviewers is that the paper adopted the fairness definition without much justification. I agree that whether a fairness consideration is the appropriate or not is often a much broader topic involving many disciplines. And a more comprehensive justification from many disciplines or regulations would be more ideal, though the justification we often provide is either hypothetical from empirical results or event reported in news articles.  Though being a valid concern, I think this is relatively a minor issue given the volume of works in fair graph learning, especially on group fairness and dyadic fairness.


Overall I think this paper offers a good theoretical understanding toward group/dyadic fairness with multi-valued sensitive attribute, and I recommend acceptance.
Decision: Accept (poster)