Fair Graph Distillation
Authors: Qizhang Feng
Zhimeng Jiang
Ruiquan Li
Yicheng Wang
Na Zou
Jiang Bian
Xia Hu
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Distillation
Algorithmic Fairness
TL;DR: A frame work for fair graph distillation.

Abstract: As graph neural networks (GNNs) struggle with large-scale graphs due to high computational demands, data distillation for graph data promises to alleviate this issue by distilling a large real graph into a smaller distilled graph while maintaining comparable prediction performance for GNNs trained on both graphs. However, we observe that GNNs trained on distilled graphs may exhibit more severe group fairness problems than those trained on real graphs. Motivated by this observation, we propose \textit{fair graph distillation} (\Algnameabbr), an approach for generating small distilled \textit{fair and informative} graphs based on the graph distillation method. The challenge lies in the deficiency of sensitive attributes for nodes in the distilled graph, making most debiasing methods (e.g., regularization and adversarial debiasing) intractable for distilled graphs. We develop a simple yet effective bias metric, called coherence, for distilled graphs. Based on the proposed coherence metric, we introduce a framework for fair graph distillation using a bi-level optimization algorithm. Extensive experiments demonstrate that the proposed algorithm can achieve better prediction performance-fairness trade-offs across various datasets and GNN architectures.

Fair Graph Distillation
Qizhang Feng', Zhimeng Jiang', Ruiquan Li", Yicheng Wang', Na Zou', Jiang Bian', Xia Hu* 'Texas A&M University. UUniversity of Science and Technology of China, Unnieerstty of Florida, *Rice University
Abstract
As graph neural networks (GNNs) struggle with large-scale graphs due to high computational demands, graph data distillation promises to alleviate this issue by distilling a large real graph into a smaller distilled graph while maintaining comparable prediction performance for GNNs trained on both graphs. However, we observe that GNNs trained on distilled graphs may exhibit more severe group fairness issues than GNNs trained on real graphs for vanilla and fair GNNs training. Motivated by these observations, we propose fair graph distillation (FGD), an advanced graph distillation approach to generate fair distilled graphs. The chal- lenge lies in the deficiency of sensitive attributes for nodes in the distilled graph, making most debiasing methods (e.g., regularization and adversarial debiasing) intractable for distilled graphs. We develop a simple yet effective bias metric, named coherence, for distilled graphs. Based on the proposed coherence metric, we introduce a framework for fair graph distillation using a bi-level optimization algorithm. Extensive experiments demonstrate that the proposed algorithm achieve better prediction performance-fairnes trade-offs across various datasets and GNN architectures.
Introduction
Real-world data, like chemical molecules, social networks, and transportation networks, can be represented as graphs [Han et al. 2002a Ling et al. 2023a Jiang et al.. 2022a Ying et al. 2018 Ling et al., 2023b Tong al. 2020 Han al. [022b]] Graph neural networks (GNNs) excel at capturing structural information but struggle with large-scale graphs due to memory consumption
and computational expense caused by the neighborhood explosion problem (Hamilton al. 2017
Liu et al., 2023c). This cost becomes unaffordable in situations requiring repeated GNN training.
such neural architecture search and continual learning (Liu al., [0188] Zhou al.) 2019 Li and
Hoiem] 2017 Liu et al. [203b]] Dataset distillation is a promising solution to address computation challenges by generating small, informative distilled data for neural network training in downstream
2021a l b Nguyen et al., 2021]. Techniques like dataset tasks [Jin et al.) 2021 2022, Zhao et al. condensation [Zhao et al. [2221b] Jin et al. [202] can significantly reduce training data size without major performance degradation in the image and graph domains. However, focusing solely on prediction performance may introduce fairness issues, as sensitive information can be condensed into distilled data for prediction. A natural question is raised: Is the model trained the distilled gruph fair, and if not, how can we achieve fair gruph distillation?
In this work, we focus on the group fairnes for node classification tasks under binary sensitive attribute setting. We discover that GNNs trained on distilled small graphs exhibit more severe group faimess issues than those on real graphs. In other words, graph distillation can even amplify graph
"Group fairness ensures equitable treatment diverse demographic groups by algorithms Mehrabi et 2021]. Such as in mortality prediction, issues arise when true positive rates significantly ditfer between sensitive groups. Group faireess metrics will be introduced in Section 5.1
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

data bias, which challenges the applicability of graph distillation in high-stake applications [Mehrabi al., [ Suresh and Guttag] 2 To this end, we propose a fair graph distillation framework to offer significantly reduced graph size and also better utility-fairness trade-off while maintaining predictive performance.
Many debias methods explicitly use sensitive attributes, but these are inherently missing in distilled graphs because they are excluded from the data attributes and the meaning of the attributes may change during the optimization process. In this paper, we point out the relationship between the space of real graphs and the space of distilled graphs and develop a simple estimator of sensitive attributes and introduce bias measurement called consistency. We then propose a bi-level optimization algorithm for fair graph distillation: the outer loop generates a fair and informative distilled graph using gradient matching and coherence loss, while GNNs train on distilled graphs in the inner loop. In nutshell, the contributions can be summarized as follows:
To our knowledge, this is the first paper to identify group fairness issues in conventional graph distillation methods with binary sensitive attributes, motivating the formulation of fair graph distillation problem in node classification tasks.
We discover the relationship between the space of real graphs and the space of distilled graphs. We develop a bias metric called coherence for distilled graphs and propose a bi-level optimization framework using this metric to achieve fair graph distillation.
We perform extensive experiments various real-world datasets and GNN architectures to validate the effectiveness of the proposed FGD algorithm. Results demonstrate that FGD achieves a better accuracy- -ecuracy-fairees trade-off compared to vanilla graph distillation methods and numerous baselines.
2
Preliminaries
2.1 Notations
We consider node classification tasks given a graph dataset 9 = {A, X, S) with nodes. Here, A E [0,1)NxN is the adjacency matrix, and A.j = 1 represents there exists an edge between node and j. X E R is the node feature matrix, where D is non-sensitive feature dimension for each node. Y E (0, 1........ C-1] denotes the node labels over C classes. For simplicity, we consider a binary sensitive attribute S (0, 1) IT is the sensitive membership diago- nal matrix. II ss = 1 if and only if i-th node belongs to sensitive group s. The distilled small graph dataset
009
0.00
0000
is marked as g = {A', X',Y") Y'} which contains N' nodes and N' < N. Note that elements of the dis- tilled adjacency matrix satisfy A'y- E [0, 1] and no sen- sitive attributes exist in G'. The latent node represen- tation of real graph is Z. and the span space of it is span( Z) = E w < < N, R]. Sim- ilar definition of Z' and span (Z') for distilled graph.
AJC
Figure 1: AUC and Apr of the GNN trained on real graph data and distilled graph data. Both utility and fairness per- formance deteriorates after vanilla graph distillation.
2.2 Graph Distillation via Gradient Matching
The purpose of graph distillation is to generate a distilled graph g' such that the GNN model, denoted GNN, with parameters 0. trained on distilled graph performs comparably to the model trained on the real graph G. The objective can be formulated as the following bi-level optimization problem:
min L (GNN ga' X), YY s.t go' arg min L (GNN,
Y')
where 8 denotes the optimal parameter trained on distilled small graph g', and C(+, -) denotes the loss function. To tackle the above optimization problem, the gradient matching method Zhao et al.
'The sensitive attribute S represents the attribute that the respondents do not want to be disclosed, such as gender age. Sensitive attribute S is not included in the normal features X.

---

2021a is proposed. The intuition is to let the GNN parameters 6 trained on distilled graph follow similar path the GNN parameters & trained on the real graph during model optimization. The gradient of the GNN parameters is forced to be the same over the real and distilled graphs:
min Σ (VoC(9)) VoL(())
where -(.,)) is distance function, I' is the number of steps of model parameters trajectory, and 8º. 08" denotes the model parameters trained on & and G' at time step t, respectively. The gradient calculated on G and G' is denoted as VoL(g) = VoL(GNN, (A, Y) and VoL(g") = VoL (GNN,, X') Y"), respectively.
3 Bias Measurement for Distilled Graph
In this section, we empirically demonstrate the fairness issue in the distilled graph. Motivated by this, we pursue fair graph distillation. Although distilled graphs lack sensitive attributes S', observe that between the node representations the real and distilled graphs: their barycenter remain consistent, and their spaces also consistent. We leverage this phenomenon to develop simple, effective bias measurement for distilled graphs.
3.1 Is Graph Distillation Really Fair?
Our empirical investigation assesses the faimess of graph distillation across various datasets and architectures. We compare the utility (AUC) and fairness (demographic parity (ADP) [Beutel et 2017]) of GNNs trained on real graphs and those trained on distilled graphs created by the vanilla graph distillation method. The utility and fairness performance are shown in Figure T We can find that: For datasets like Pokec-n, German, and Credit, distilled wraph-based GNNs have higher DP and lower AUC performance, suggesting compromise fairness and prediction performance. We also notice that, for Pokec-z and Recidivism datasets, these GNNs exhibit lower ADP and significantly lower AUC performance (shown in Table [ indicating a trade-off between improved fairness and reduced prediction performance. We observe similar results when using other fair GNN models. More details can be found Appendix [E] Motivated by these observations, we aim to find a better prediction performance and fairness trade-off via chasing the fair graph distillation method.
3.2 Geometric Connections in Data Distillation
The distilled data can be generated via minimizing gradient distance in Equation 2
To simplify the analysis, we consider D(..)) as Euclidean distance and those model parameters during optimization trajectory satisfying 0 ~ Pg. where Po certain but unknown parameters' distribution. Therefore, the objective can be transformed as
(ay?")
St
min Ea-P, VoL(G) VoL(G))1
(3)
IM Figure Geometric intuition sen- sitive attribute estimation. The projec- tion distance indicates the extent to which the node belongs to the sensi- tive group. (a) Unfair node represen- tations have a large coherence bias. (b) Fair node representations have small coherence bias.
61
We consider three assumptions of the model parameters' dis- tribution and the convergence for loss minimization.
Assumption 3.1 (Model parameters' distribution). We as- sume that each model parameter in the last softmax layer satisfies the same distribution.
Assumption 3.2 (Loss minimization). We assume that exists at least one distilled dataset that minimizes Equation 3
Theorem 3.3 (Consistent Span Space). empirically show
that span Z RJ span Z) via calculating the principle angles between them. We also provides the rigorous proof of E span Z) under distribution matching in Appendix D
Theorem 3.4 (Consistent Geometric Barycenters). Under Assumptions
3.7 and 3.2 the barycenter
of the last representation for the optimal distilled graph and the real graphs are consistent, i.e.
N EN
t En z Please proof in Appendix
3

---

3.3 Sensitive Attribute Estimation
The consistent span space and geometric barycenter suggest that we can estimate sensitive attributes from the representations of both distilled and real graphs. We frame sensitive attribute estimation as classification problem: Given a data representation x' E Z', what is the probability that æ' belongs to the sensitive group?
Ridge regression for distance measurement. Notice that the representation of each sensitive group for the real graph is known, we define Zo and Zι as the representation matrix for sensitive group
and $ To measure the probability that z' belongs these two sensitive groups, we first find the closest vector Zproj Z q E Span( Z.) to approximate the representation z', and then use the norm of z' Sproj to measure the distance between z' and sensitive group Z, Specifically, we adopt ridge regression find the optimal coefficient vector q*, which can be formulated as
Dist(z', Ze) = | - 2 q" l
(4)
s.t q" = arg min 7 7| 2," 911 + 1|q113
(5)
q
where y is the hyperparameter for ridge regression. For the optimal q², we have
-2, p" = ='=z'-- Z q- = -2, (Z,,) Z,z',
(6)
where T represents matrix transpose, pz is approximately the projection onto the orthogonal comple- ment of the subspace span(Z.) Z.). The proof is in Appendix
can be viewed Sensitive attribute soft estimation. Since p" = -., (I+,2,2))) Z
as approximately the projection of x onto the orthogonal complement of sensitive group Ze ||p' is small if is in sensitive group Z, and large otherwise. The probability of the given data representation z belongs to the sensitive group Z, can further be inferred via a softmax function:
exp (-> ||2)l2)
n (=')
E [0,
exp (-> ||'1|2)
where À is the temperature hy hyperparameter. The sensitive attribute probability of x' for distilled graph can be estimated as probability distribution [====(x²)) (='),(zz)) 3,), n- (z')), where x ===0(21) ) + π --= (x') = 1.
3.4 Bias Measurement
Given the estimated sensitive attribute probability for z' of each distilled node, how can we measure the bias for them? For fair representation, we can not distinguish which representation more likely to be specific sensitive group. Therefore, we adopt simple surrogate bias measurement, named coherence, the variance of the estimated sensitive group membership. Given the whole distilled data representation Z' ZN:] the bias can be defined as:
N'
N
Col) Var T (Z')
1 N
Σ
T (2))))
1
n
(2/h)
N7 ==1
Note that 0
(Z') (Z')=
Coh (Z'), and we adopt abbreviation Coh Z')
Geometric intuition. The intuition of sensitive attribute estimation, as illustrated in Figure 2 can be grasped from geometric standpoint. In a toy example with a two-dimensional data representation, z' E IR2, we consider two demographic groups for a binary sensitive attribute. The subspace spanned by the data representations from these groups is denoted by S and St Data representations to be estimated are z6 and z/- pg. pl and ph: p is the projection of z and 2 onto the orthogonal complement of S and 8 As for fair data representation, zero coherent encourages all representations aligned with a "line" so that all representations are with the same normalized similarity with sensitive (a) shows the case which the data representation biased where 2/1 and z can be easily distinguished. Figure (b) shows that fairer data representation they are less separable.
groups. Figure (a)
For multiple-value sensitive attribute, can average coherence Coh(Z') across all sensitive groups

---

Syrthetic
Graph
Synthenizer
Inner Loop Oplimization Updale
LCE
X
MLP
GAN Layer
Matching
Loop Optmization Update
Oohernnce
Xx
LCoh
49
Figure 3: An overview of the proposed framework. The synthesizer generates the attribute matrix and adjacency matrix of the distilled small graph g'. The Cross-Entropy loss LcE guides the update of GNNs model during the inner optimization loop. Gradient matching loss Less and coherence loss Lcoh guide the update of the synthesizer during the outer optimization loop for utility and faimeess.
4 Methodology
4.1
Problem Statement
Based on the proposed coherence metric, we argue that if Coh (2) is reduced, bias in the distilled graph can be mitigated. As result, if GNNs are trained on such distilled graphs, bias issues in downstream tasks could also be alleviated. 'The problem is formally defined as: Given an undirected attributed network G = (A, X, Y. S), our goal obtain an debiased distilled graph g' = {A', X', Y') via reducing Coh, so that the fairness issues of GNNs trained on G' is mitigated. Hence the overall objective goal for generating fair and condensed graph is:
min LGM + aLCoh (GNN go' (A',''), G,NNN go (A, X)) g'
s.t 08" = arg min Lox (GNN, X'), Y")
(8)
4.2 Fair Graph Distillation Loss
Gradient Matching Loss. We adopt gradient matching, shown in equation 2 for graph distillation to distill useful information for node classification tasks. However, treating both X" and A' learnalle parameter [ and directly optimizing A' is unaffordable due to O(N2) computation complexity. Following previous work Jin et al. [202]] we parameterize A' as a function of X':
A/, Sigmoid MLP [ (
MLP ((ar); a(l))
where A', is i-th row, j-th column A', MLP,, is a multi-layer neural network parameterized with controlled to be symmetric since A = A' Sigmoid function pushes A' close to 0 or to encourage its sparsity. For simplicity, we denote the reduce the complexity to O(N).
á and [::+] denotes concatenation. Note that
parameterized adjacency matrix A In this way,
The distance metric D measures the similarity of gradients over the real graph and distilled graph. We adopt the summation of the gradient distance over all layers as the final gradient distance:
VoL(G), VoL(g)) = Σ IV
(VoL(g),
(10)
'The distilled label Y' sampled from real label Y with the same class probability. and it is fixed.

---

where VoL(g); is the i-th column vectors of the gradient matrices. Hence the loss objective for the graph distillation module given by:
T Σ D (VV
LCM = Ea
(11)
where G- A'',,, Y",Y l is the training epoch, and O, is well-trained GNNs model parameters. To reduce the impact parameter initialization, the initial model parameters Bu are sampled from distribution of random initialization.
Coherence loss. In Section 3.4 we introduce coherence as bias metric for distilled data. To mitigate bias, we use coherence bias as a regularization for fair synthesis. This calculation employs real graph node attribute X and distilled node attribute X' to estimate sensitive group memberships but overlooks structural bias in graph data. Given the GNN propagation mechanism, bias can exist in both node attributes and graph structure Dong et al. [2022] Even without attribute bias, node representation may still be biased if structural bias is present.
Work by Dong et al. [2022] suggests that structural bias can be measured through graph representation bias. Leveraging this, we aim for low coherence in node attributes and representations to fully remove bias from distilled graph. Specifically, we introduce attribute and structural coherence decrease attribute and structural bias, respectively, by minimizing the variance sensitive group membership estimation for node attributes and representations. Given real graph data a distilled graph g' {'', X', Y'), ,',Y",,
(A, X, Y .) and we feed them into a L-layer GNN, where the I-th layer latent representation in the GNN is denoted as Z. The latent representation for node attribute after I-hop propagation contains both attribute bias as well as structural bias. Note the node attribute X and X' before propagation Zo and Zy get set of latent presentation (Zo; Zi,..., ...y Zr.} for G and (Z) Zi, ] for G'. The objective to measure bias of Zj is:
exp (-X|IC*
Col( (2) Var (T' (Z)) = Var
(12)
Σ, exp exp((=A1 2
where C = -1 2FI
II is introduced in Sec 4.1 Since we consider the binary
sensitive attribute, j is set as 0 without losing generality and is omitted in the notations as T (-) = (-)) After considering all the latent representations, the coherence loss objective defined as the summation of all coherence over all layers, i.e.,
L Var (T (Zi))
LCoh Σ Coh(ZZ) 1=0
(13)
1=0
Prediction loss for GNN training. The GNNs model is trained on distilled graph g' (A', X', Y') with prediction loss. We adopt T--laee GNNs model, where 0 is the parameter of the GNN. We also adopt cross-entropy loss by default:
LCE L LGNN, (A','), YY),
(14)
4.3 Final Objective and Training Algorithm
Outer loop optimization. In the outer loop, we optimize the fair graph synthesizer with gradient matching loss and coherence loss:
min LaM + a
(15)
X" A'
where a is a hyperparameter to regularize the debiasing intensity. The distilled node attribute X' and the distilled node label Y' are initialized with the nodes uniformly sampling from real graph data G.
Inner loop optimization.
The GNN parameter 0 is optimized the inner loop:
min LeE (GNN, (A', x'), Y").
(16)
6
Instead of using the real graph data G to calculate the loss, we use the distilled graph g'. It empirically shows good performance and better efficiency. But the adversarial training baseline uses needs the sensitive attribute for discriminator training.

---

Table 1: Comparison on utility and bias mitigation between GNNs with real graph data (denoted as Real), the distilled small graph without debiasing (denoted as Vanilla), and debiased distilled graph (denoted as FGD) as input. 1 denotes the larger, the better; & denotes the opposite. The best ones are in bold. The better performers in Vanilla and FGDare underlined.
GCN
SGC
GraphSAGE
Real
Vanilla
FGD
Real
Vanilla
FGD
Real
Vanills
PGD
ACCT
%
66.66110
70.79:0.1%
67.13-0.4%
7K191022%
70.301044%
77.161008%
00.91
20.47:0.0%
70.2610.58
Poloc-x
72.161055%
65.66117
7121100%
67
72.0704%%
Anp
4.5-1.3%
17.-11%
4
1.0-1.7%
Axo
1.7%
2.19.13%
1.19 1.0%
1.8%.19%
4.7.002%
125
2:50 1250
2,56 1,258
ACC
7199103%
50
20.00127
7L161088
65061094
713110.3
52.0012.22
55 55.00
ALCT
78.15102%
51.0942.9%
05.751955
76.34000%
07.5620.1%
53.95-2.6
23%
Polece-n
F1
6992+-04%
46.1+468
19
6763-088
63.55-01
14
58. 58.75-6.19
63 2.36+2.0%
Spp
43-911%
500=0.5%
0.9--14%
2.36-288
LIVE 1A
Aso
1/4106%
5.20
2.2610.14
4620,88
1.4.006
28123,08
1.03 1.58
74.31102%
57.51448
17.89159%
7494112%
7137104%
57.3220.44
59.761599%
Germnn
94.24-01% %
13112-04
Ane
4.8
5381336
1ON
336:288
110:288
13:00%
300198
5
0.61-65%
Aro
2.50-22.%
LOEELS
244-0-18
028:025
2
0.52.04%%
ACC 1
80.34100%%
16921194
1ISILOIS
1141
11.610.%
0..5
1..66...1%
ALCT
75
68
25
12
05
11.121025
71. 16.
Cradit
F1
88.41 10.0%
8547520%
47.3
88.01000
85 06
85 37
07.00-0.8
Spr
Ago
3.12H066%
9.54455%
119+0.3
7.14-0.5%
1.566.11
592+0.59
6.22-40%
3.4-0.9
%
85.00001%%
73. 13
73.66
ACC
%7.7610000%
71.96
75
02.24:0.1%
72:23-0664
75
75.84-128 1.2
70:47:55
Racidivimm
92.32+4U0%
35.90+3.9%
769440.5
60 60:77-088
92.35-0115
Sgr
1.5.0.9
T0KI67'
Ago L
3.45:00.5%
1A150.55
0.46:0.2%
8.55=022
2.69
133--085
3.566:33
0.93-000%
0.4%
5
Experiments
We design experiments to validate the effectiveness of the proposed framework FGDand answer the following research questions: RQ.1 How well can FGD mitigate the bias in the distilled graph and alleviate the fairness issue of the GNNs trained on the distilled small graph? RQ.2 How well can FGD balance the trade-off between accuracy and bias mitigation compared with other debiasing baselines? RQ.3 Can FGD further improve the utility or bias mitigation as an add-on module to other bias mitigation methods?
5.1 Experimental setting
Datasets.
We use five real-world datasets, including Pokec-z, Pokec-n DDi and Wang 2021 Takac
and Zabovsky 2012). German, Credit, and Recidivism [Agarwal et al. 2021 The detailed setting of the datasets is Appendix F
GNN Models. We adopt three popular GNN variants in our experiments, including GCN [Kipf and Welling 2016 SGC (Wu et al. 2019], GraphSAGE [Hamilton et al. 2017].
Baselines. Given the absence of fair graph distillation work, we compare our approach with four
baselines. (1) Real uses real graph data to train a GNN model. (2) Vanilla applies a vanilla graph
distillation algorithm (Jin et al. 2022 for distilled graph data learning and GNN model training. (3) FairGNN (Dai and Wang [022 trains a fair GNN model adversarially on real graph data, aiming
to achieve good prediction while fooling discriminator. (4) EDITS (Dong al. 2022 is model- agnostic debiasing method that rewires graph data for fair GNNs.
Evaluation Metries. We evaluate model performance from model utility and bias measurements. Good performance represents low bias and high model utility. For model utility metrics, we adopt accuracy (ACC), the area under the receiver operating characteristic curve (AUC), and F1 score to measure prediction performance. For bias measurement, we adopt two commonly used fairness metrics, i.e., demographic parity (ADp) and equal opportunity (A [Beutel et al.
2017 Louizos
et al. 2015). Denote the binary label as y E {0. 1}. and sensitive attribute as E (0. 1). " 00
denotes the model prediction. The violation of DP and EO are given by App PP
0) P(ğ = 1 s = 1)), and A = PP
y 1, s 0) - P(g 1 y 1,3 1)).
7

---

Pakoc
Octmen
Gredk
divism
541
Loda
1213
Helave
AGI
AUAC
ALC
36
AII
AUC
Pakec
Pakee
Garman
Credk
Recidvor
1.44
RC
-e wide
E20
AUC
AUC
CAT 540
AUC
20
013
AUC
A00
Figure 4: Trade-off comparison between FGDand other baselines for five real-world graph datasets.
5.2 Debiasing distilled Graph
In response to RQ.1, we assess FGD's bias mitigation and prediction performance across various GNN architectures and datasets, as shown in Table We compare the ADP and Ago values of GNNs trained on real graphs (Real), vanilla distilled graphs (Vanilla), and debiased distilled graphs via FGD (FGD). Key findings include: (1) Models trained on Real graphs consistently outperform Vanilla and FGD in utilityy though FGD's 's utility matches or surpasses Vanilla. (2) FGD consistently yields lower bias than Vanilla, and outperforms Real on out of datasets, excluding Poken-n.
We compare the coherence bias of distilled graphs generated by Vonilla and FGD methods across five real-world datasets with the GCN architecture (Table 2 Our analysis reveals that FGD reduces unfairness, reflected in lower coherence bias in the distilled graphs. This consistency confirms the effectiveness of coherence bias measure of distilled graph bias.
5.3 Trade-Off Comparison
In response to RQ.2, we compare the trade- off between model utility and bias mitigation against other baselines using the GCN archi- tecture. We utilize the Pareto frontier Ishizaka and Nemery 2013) to evaluate our approach's utility-fairness trade-off, using different hyper- parameters. The Pareto frontier graphically rep- resents optimal trade-offs in multi-objective op- timization. We use AUC as the utility metric and ADP and Eo as fairness metrics. Higher AUC and lower A A EO are preferred, so models with Pareto frontier curves closer to the bottom right corner (AUC on the horizontal axis and A Eo on the vertical) have better trade-off performance.
Table 2: Coherence bias comparison between
vanilla distilled graph (denoted as Vanilla) and fair distilled graph (denoted as FGD). The lower, the better. The best ones are marked bold. The ar- chitecture model is GCN.
Vanilla
FGD
Pokec-z
0.009468
1.002123(-77577)))
Pokec-n
0.004464
(000432(-90.322
German
0.012772
Credit
0.011864
0.0028661 75.84%)
Recidivism
0.000098
0.000038( (.000038(661.22%)
61.22%%
Figure 4 shows the results for models trained on the real graph, the distilled graph debiased by baseline methods (vanilla graph distillation, FairGNN, and EDITSS) and the distilled graph debiased by FGD. We can observe: (1) From a model utility perspective, FGD performs comparably to other baselines, like vanilla graph distillation, FairGNN, and EDITS 7 information for node classification. (2) In terms of bias mitigation, all baselines show effectiveness. with FGD exhibiting the best results. (3) When considering the fairits- trade-off, FGD's Pareto front curve lies the bottom right corner of all baselines, signifying it offers the best balance. Thus, FGD outperforms other baselines in balancing model utility and bias mitigation.
suggesting it preserves sufficient
5.4 Add-on Module
SEDITS publishes fair graph for German, Credit and Recidivism dataset on Github *Out of memory (OOM) issue appears when running EDITS on Pokec-z and Pokec-n datasets.
8

---

In addition to its superior trade-off performance, our method, FGD, can enhance other debiasing baselines like FairGNN and EDITS by acting as an add-on debias module. This compatibil- ity is due to the fact that these baselines can replace the cross-entropy loss in the GNN train- ing module. To answer RQ.3, we conducted experiments on the Credit dataset comparing FairGNN/EDITS performance with and without FGD. As shown in Figure 5 FairGNN/EDITS coupled with FGD delivers better utility- fairness trade-off, demonstrating FGD's 's potential to boost other debias methods.
Credit
Credit
Ouza TeRChN
PCD EDITS
0.04
EDITS
062
640
040
348
6.0
6.0
048
Figure 5: Trade-off comparison between FairGNN, EDITS and FairGNN+FGD, EDITS+FGD on Credit dataset.
utility-fairness
Related Work
Dataset Distillation & Knowledge Distillation. Dataset Distillation (DD) and Knowledge Distilla- tion (KD) are methods to improve the efficiency of training deep neural networks. DD synthesizes small dataset encapsulating the knowledge of larger one, achieving comparable model perfor-
mance [Wang et al., 2018 Kim et al.) 2022 Lee et al. 2022 Zhao et al. 202 Yang et al. 2022]. employs a livle optimization approach, with dataset condensation (DC) speeding up the pro- cess via gradient matching of model parameters. DD also helps with repeated training privacy applications like continual learning, neural architecture search, and
scenarios. Meanwhile, graph data condensation methods have been developed for node and graph classification tasks [Jin et al. 2022]. KD, on the other hand, enhances computational efficiency through model compression and acceleration. It trains a compact student model using the knowledge from larger teacher model Gou et al. [202I]To To address the scarcity and high complexity labeled data in GNNs, knowledge distillation (KD) was introduced to enhance existing GNNs Liu al. (2023a). Wang et al. [023], also for fairness problem Dong et al. [2023]. While KD focuses on model compression, DD targets data compression, each improving efficiency from model-centric and data-centric perspectives.
Fair Graph Learning. Fairness in machine learning has attracted many research efforts Chuang
and Mrouch 2020 Zhang et al. 20188 Du et al. [202]] Jiag al. 2022b Han et al. 2023 Jiang et al.
2023]. Many technologies are introduced in graph neural networks to achieve fair graph learning in
node classification tasks, including optimization with regularization (Jiang et al. 2022a rebalancing
Zeng et al.) 2021]. adversarial learning [Dai and Wang 2021 Bose and Hamilton [2019] Fisher et al.
2020] and graph rewiring (Köse and Shen 2021 Dong et al. [022]. For link prediction, dyadic
fairness and corresponding graph rewiring solutions are also developed in [Li et al.) [2021). Another
line of work focuses on solving the individual fairness problem on the graph data (Sng al. [0022]
Dong et al.
2021
Kang et al. 20200
7 Conclusion
Despite the ability of graph distillation to condense valuable graph data, this study finds that the vanilla method can worsen fairness issues. Therefore, we introduce a fair graph distillation process to generate fair distilled graph data. As the distilled graph lacks the nodes' sensitive attributes, conventional fair methods cannot be directly applied. However, we identify consistent geometric phenomenon in graph distillation to estimate these sensitive attributes. We also introduce a new bias metric, coherence, and propose bi-level optimization framework, FGD, for fair graph distillation. Experimental results validate FGD's effectiveness in mitigating bias while maintaining model utility across various GNN architectures and datasets. Future work will focus addressing individual fairness issues and non- non-binary sensitive attribute conditions, among other aspects, as discussed in Appendix H
Acknowledgements
We are deeply grateful to the National Science Foundation for their unwavering support. This research was substantially facilitated by the funding from grants IIS-1939716 and 11S-1900990.

---

References
C. Agarwal, H. Lakkaraju, and M. Zitnik. Towards a unified framework for fair and stable graph representation learning. In Uncertainty in Artificial Intelligence, pages
PMLR, 2021.
A. Beutel, Chen, Z. Zhao, and H. Chi. Data decisions and theoretical implications when adversarially learning fair representations. arXiv preprint arXiv:/077.00075. 2017.
A. Bose and W. Hamilton. Compositional fairness constraints for graph embeddings. In International Conference on Machine Learning, pages 715-724. PMIR, 2019.
C.-Y. Chuang and Y. Mroueh. Fair mixup: Fairness via interpolation. In International Conference on Learning Representations, 2020.
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 Web Search and Data Mining, pages 680-688, 2021.
Y. Dong, J. Kang, H. Tong, and J. Li. Individual fairness for graph neural networks: A ranking based approach. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 300-310, 2021.
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, pages 1259-1269, 2022.
Y. Dong, B. Zhang, Y. Yuan, N. Zou, Q. Wang, and J. Li. Reliant: Fair knowledge distillation for graph neural networks, In Proceedings of the 2023 SIAM International Conference on Data Mining (SDM), pages 154-162. SIAM, 2023.
M. Du, S. Mukherjee, G. Wang, R. Tang, A. H. Awadallah, and X. Hu. Fairness via representation neutralization. arXiv preprint arXiv:2106.1266 2021.
J. Fisher, A. Mittal, D. Palfrey, and C. Christodouulppouls. Debiasing knowledge graph embeddings. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 7332-7345, 2020.
J. Gou, B. Yu, S. J. Maybank. and D. Tao. Knowledge distillation: A survey, International Journal of Computer Vision, 129:1789-1819, 2021.
W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning large graphs. Advances in neural information processing systems, 30, 2017.
X. Han, Z. Jiang N. Liu, and X. Hu. G-mixup: Graph data augmentation for graph classification. arXiv preprint ar www::2222200111111 2022a.
Li, and X. Hu. Geometric graph representation learning via X. Han, Z. Jiang, N. Liu, Q. Song, Li, maximizing rate reduction. In Proceedings of the ACM Web Conference 2022, pages 1226-1237, 2022b.
X. Han, Z. Jiang, H. Jin, Z. Liu, N. Zou, Q. Wang, and X. Hu. Retiring Sidelta (eex: New distribution-lewe metrics for demographic parity. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. httpsttss:///
nett:forum
A. Ishizaka and P. Nemery. Multi-criteria decision analysis: methods and software. John Wiley & Sons, 2013.
Z. Jiang, X. Han, C. Fan, Z. Liu, N. Zou, A. Mostafavi, and X. Hu. Fmp: Toward fair graph message passing against topology bias. arXiv preprint 22Xv:22002.01887 2022a.
Z. Jiang, X. Han, C. Fan, F. Yang, A. Mostafavi, and X. Hu. Generalized demographic parity for group fairness. In International Conference on Learning Representations, 2022b.
Jiang, X. Han, H. Jin, G. Wang, R. Chen, N. Zou, and X. Hu. Chasing fairness under distribution shift: a model weight perturbation approach. 2023.
10

---

W. Jin, L. Zhao, S. Zhang, Y. Liu, J. Tang, and N. Shah. Graph condensation for graph neural networks. arXiv preprint arXiv:2110.07580, 2021.
W. Jin, X. Tang, Jiang, Z. Li, Zhang. J. Tang, and Yin. Condensing graphs via one-step gradient matching. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 720-730, 2022.
Kang, He, R. Maciejewski, and H. Tong. Inform: Individual fairness on graph mining. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 379-389, 2020.
J. Kim, J. Kim, J. Oh, S. Yun, H. Song, J. Jeong, J.-W. Ha, and O. Song. Dataset condensation via efficient synthetic-data parameterization. In International Conference Machine Learning. pages 11 1100-1111111 118.. PMLR, 2022.
T. N. Kipf and M. Welling. Semi- ceni-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1609, 029072 2016.
Ö. D. Köse and Y. Shen. Fairness-aware node representation learning. arXiv:2106.0539, 2021.
arXiv preprint
S. Lee, S. Chun, S. Jung, S. Yun, and S. Yoon. Dataset condensation with contrastive signals. In International Conference on Machine Learning, pages 12352-12364. PMLR, 2022.
Li, Y. Wang. H. Zhao, P. Hong, and H. Liu. On dyadic fairesss: Exploring and mitigating bias in graph connections. In International Conference on Learning Representations, 2021.
Z. Li and D. Hoiem. Learning without forgetting. IEEE transactions on pattern analysis and machine intelligence, 40(12):2935 2947, 2017.
H. Ling, Z. Jiang, M. Liu, S. Ji, and N. Zou. Graph mixup with soft alignments. In International Conference on Machine Learning. PMLR, 2023a.
H. Ling. Z. Jiang, Y. Luo, S. Ji, and N. Zou. Learning fair graph representations via automated data augmentations. In International Conference on Learning Representations, 2023b.
H. Liu, K. Simonyan, and Y. Yang. Darts: arXiv:1806.09053 2018.
Differentiable architecture search. arXiv preprint
J. Liu, T. Zheng, G. Zhang, and Q Hao. Graph-based knowledge distillation: A survey and experimental evaluation. arXiv preprint arXiv:2302.14644, 2023a.
Liu, Z. Jiang, S. Zhong, K. Zhou, L. Li, R. Chen, S.-H. Choi, and X. Hu. Editable graph neural network for node classifications. arXiv preprint arXiv:2305. /5529, 2023b.
Z. Liu, K. Zhou, 7. Jiang, I.. Li, R. Chen, S.-H. Choi, and X. Hu. DSpar: An embarrassingly simple strategy for efficient GNN training and inference via degree- based sparsification. Transactions Machine Learning Research, 2023c. ISSN 2835-8856. URL https::/ net/ Forum?id=SaVExFuuzg
C. Louizos, K. Swersky, Y. Li, M. Welling, and R. Zemel. The variational fair autoencoder. arXiv preprint www.:xv111.008..00 2015.
N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan. survey on bias and fairness in machine learning. ACM Computing Surveys (CSUR), 54(6):1-35, 2021.
T. Nguyen, R. Novak, L. Xiao, and J. Lee. Dataset distillation with infinitely wide convolutional networks. Advances in Neural Information Processing Systems, 34:5186-5195 2021.
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 on Knowledge Discovery and Data Mining, pages 1625-1634, 2022.
H. Suresh and V. Guttag. framework for understanding unintended consequences of machine learning, arXiv preprint 191.00190. 2, 2019.

---

L. Takac and M. Zabovsky. Data analysis in public social networks. In International scientific conference and international workshop present day trends of innovations, volume 1. Present Day Trends of Innovations Lamza Poland, 2012.
A. Tong, J. Huang, G. Wolf, D. Van Dijk, and S. Krishnaswamy, Trajectorynet: A dynamic optimal transport network for modeling cellular dynamics. In International conference on machine learning. pages
PMLR, 2020.
T. Wang. J.-Y. Zhu, A. Torralba, and A. A. Efros. arXiv: 1811.10999 2018.
Dataset distillation.
arXiv preprint
Y. Wang, B. Hooi, Y. Liu, and N. Shah. Graph explicit neural networks: Explicitly encoding graphs for efficient and accurate inference. Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pages 148-356, 2023.
F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger. Simplifying graph convolutional networks. International conference on machine learning, pages 6861-6871. PMLR, 2019.
Yang, Z. Xie, H. Peng, M. Xu, M. Sun, and P. Li. Dataset pruning: Reducing training data by examining generalization influence. arXiv preprint arXiv:2205.09322 2022.
R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and Leskovee. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference knowledge discovery & data mining, pages 974-983, 2018.
Z. Zeng, Islam, K. N. Keya, Foulds, Y. Song, and S. Pan. Fair representation learning for heterogeneous information networks. In Proceedings of the International AAAI Conference on Web and Social Media, volume 15, pages 877-887, 2021.
B. H. Zhang, B. Lemoine, and M. Mitchell. Mitigating unwanted biases with adversarial learning. In Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, pages 335-340, 2018.
B. Zhao, K. R. Mopuri, and H. Bilen. Dataset condensation with gradient matching. ICLR, 1(2):3, 2021a.
B. Zhao, K. R. Mopuri, and H. Bilen. Dataset condensation with gradient matching. ICLR, 1(2):3 2021b.
K. Zhou, Q. Song, X. Huang, and X. Hu. Auto-gnn: Neural architecture search of graph neural networks. arXiv preprint arXhh:1909003/66 2019.
12

---

A Training Algorithm
The training algorithm for fair graph distillation is shown in Algorithm I
Algorithm Fair Graph Distillation
Training graph data 9 = (X A,S, S,Y), Y) hyperparameters a, temperature 7, number of alternative optimization step Tott, distilled label Y'.
Input:
Initialize X' based on real attributes, synthesizer model Φ and GNNs model
fort= = to Tatt do
1. Train GNNs model using distilled graph 9 and Equation 13 to obtain GN No.
2. Given GNNs model G.N No. calculate the gradient distance ((VoL()), VoL(G)) over the
real graph and distilled graph Gz
3. Calculate coherence loss based on GNNs model GN No., real graph G and distilled graph 9%-
4. Train synthesizer model using prediction loss as Equation [66
end for
Output: The fair distilled graph g' {A','',
B Proof of Theorem 3.4
We consider GNNs model learn node presentation 2; the real graph G and then followed linear classifier W = [wo.... wc-1] and softmax layer, where wy is the weight vector connected to the j-tj output neuron. We first focus on the relation between the latent representation and the gradient of the linear classification layer. It is easy to obtain the cross-entropy loss J; (J() for i-th node with label yı in real graph G (distilled graph G') as follows:
Jj -log log exp(w)), zi)
(17)
Σn exp(w 2.)
D5 Dw,
Then we define gradient over weight vector as gi. graph. If j = Yi. we can obtain
Jwe and g
the real and distilled
Ex exp(wx 2;)
g1.y
exp( Ww 2;)
exp(w)) 2;) Ex exp(w0 2;) - cxp'(w), 2i)
Ex exp(w 2x))²
exp(w, 22))
+ Σn exp(w, 2z)
zin
(18)
Similarly, for j # we have
exp(w, T
y, z;)
g Σn exp( w 2,,)
2i,
(19)
In other words, the gradient of the loss for i-th node with label with respect to the weight vector connected the j-th output neuron is given by
2;) D Σ. exp(pp ! zz))
exp(w v.
1 1=y;
(00)
Based Assumption 3.1 each model parameter in the last softmax layer satisfies the same distribu- tion. In other words, the expectation of all predictions are the same, i.e.,
exp(w, 22:) Ep, Σx exppxxu w 2x)
exp(w 2i)
Ep.
(21)
exp((W) 2;
13

---

Note that the gradient calculation is based on backpropagation, the gradient for the last linear classification layer is quite critical for the gradient of other layers. Hence we consider the gradient of the last linear classification layer in the real graph, shown by
N
Banpa V Vw, [()) = EaNP,
1
Σ
gi.l
N
1=1
24
Z
(22)
NC
(+g:=
Similarly, we have the gradient of the last linear classification layer in the distilled graph follows:
Bg N., ((g')
EaNPo
Σ
ghyl
N
i=1
N'
Σ
Σ 4 (/./=ı)
(23)
N'C
Under assumption 3.2 it is easy to know that the optimal solution to minimizing the objective ming. Pg V (g)) VwL(g)) satisfy VwL(9) Vw L(g'.
"i'g'.-iime Since the distilled label
is sampling to keep class label probability, have [(bg]=/ 1(:g,/H for any class index i. Therefore, based on Equations and (23). we have the optimal distilled graph satisfy
N
2
(24)
N
N
==1
C Proof of Ridge Regression
Define objective function J 711= 2 9l13 1 +1q1//, is easy obtain
OJ
22 (z' Z 9) 2q =
(25)
dq
Therefore, the optimal q" 7 ZZ,, 1 -'' Therefore, the projection representation z' in the complement space of sensitive group Z, is given by
Z' = 2 ++ ZZ,Z,,,) Z.z'
(26)
D More Results on Consistent Span Space
We conduct experiments to measure the distance between span ()) and span(Z)) using principle angles between subspaces and emperically shows that span(Z) span(Z') in the real dataset.
The concept principal angle is used in linear algebra to measure the similarity between two subspaces of a vector space. It helps quantify how close or far apart these subspaces are. Given subspace, L, M C RR, with dim
2 dim = m, there are m principal angles between L and < Am between L and M are recursively defined, where
M denoted 0 01 02
xx,y y
111]
cos (0.) = min
x Ex M.x x yk, |
(27)
Notably, when the subspaces are aligned, the principal angels are close O. We report the average principal angles of (2) and span(Z') on all datasets as following:
Pokec-z: 1.08 x 10-6
Pokec-n: 1.03 x 10-6
German: 4.84 x 10-7
14

---

Credit: 2.57 x 10-?
Recidivism: 3.87 x 10-7
In the experiments, the principal angles of span(Z) and span(Z') on all dataset are nearly This indicates that the distance between space span (2)) and space span Z) are quite small in practice.
Additionally; we would like mention that [1] provides the rigorous proof of z' span| Z)) for distribution matching under several assumptions (although we can not prove it under gradient matching setting). According to formulas 21 from [1], is assumed that (1) the **Iinear extractor**
te _ + Eº such that & < d, 0 [8,,] Rx 04 N( 1) and for an input z, vx)(x) Oz.
When using distribution match method for data condensation, we have:
AL Oz
2Egldd12
2 IN
1 N
2j
Σ
E
Oz
2
j=1
j=1
where d = 8
KIa by definition of 0, and La is the identity matrix of Rd. the projection components of span(Z)+ remain zero throughout the optimization process of DM. And we use z; to initialize z,, thus z' E (2). However, in the implementation we use gradient matching instead of distribution matching.
( 2 N NY
Σ Z1
E [TT0]
Table 3: Statistical Information on Datasets
Dataset
# Nodes
# Attributes
# Edges
Avg. dogree
Sens
Label
Pokec-n
6,185
21.844
7.06
Region
Working field
Pokeo-z
7,659
59
29,476
7.70
Region
Working field
German
1,000
27
21,242
44.50
Gender
Credit status
Credit
30,000
13
1,436.858
95.80
Age
Future default
Recidivism
18,876
18
321,308
34,00
Race
Bail decision
E
Preliminary Motivation
We have added experiments comparing the fairness performance of various fair GNNs trained on synthetic and real graph data. Specifically, we report the results (using demographic parity (DP), equal opportunity (EO), and individual unfairness (IND) Song et al. [2022] as metrics) with EDITS Dong
2022 FairGNN Dai and Wang [202T] InFoRM Kang al. 2020], and REDRESS Dong al.
et al. an in processesing debiasing method, and InFoRM and REDRESS focus on individual fairness. We encountered out-of-memon (OOM) issues when implementing GUIDE and REDRESS on an NVIDIA GeForce RTX A.5000 (24GB GPU memory), so we used InFoRM as the baseline. Due to the extensive training time required for REDRESS, we only report results on the German dataset for REDRESS. We use demographic parity (DP), equal opportunity (EO), and individual unfairness (IND) as metrics.Taan Table demonstrates the result. From Table we can see that in terms of the group fairness metrics (DP, EO), the fairness problem becomes uniformly worse on the Credit, German, and Pokecn datasets for all debiasing methods. For the Recidivism dataset, the distilled graph shows fewer fairness issues (lower DP or EO), especially for the EDITS method. This may result from the drop in utility of the model trained on the distilled graph (AUC is too low). As shown in Figure 4 of our paper, FGD can achieve a better performance-faitt fainnnsssf trade-off compared to the baselines.
2021 on five datasets in our paper. EDITS is pre- processccing debiasing method, FairGNN
F Dataset Statistics
The Pokec dataset consists of millions of anonymized user profiles from Slovakia's most popular social network in 2012, with information such as gender, age, hobbies, interests, education, and working field. The dataset was sampled into Pokec-z and Pokec-n based on user province, with region the sensitive attribute. The task is to predict user working field.
Pokec.
15

---

Table 4: Utility and group faimess comparison between real graph and distilled graph with various debias method. Bold value indicates worse fairness performance.
Recidivism
Credit
Gernian
Pokeen
Pokocz
Distilated
Dusillated
Distilated
ALCTT
0.971
0.688
0.740
0.704
0.668
D.506
DCM
OGM
O0M
ODM
EDETS
1211
01307
01088
01027
01X09
DCK
OCM
D0X
GDM
0.023
DOM
ALCT
0.977
0.799
0.720
0.742
0.685
0.782
0.075
0.784
PORGNN
D31
0.055
0.466
0.022
0.123
0.010
0
0.005
0.044
0.022
0J837
BO1
0.037
0.07
0.091
0.011
0.011
0.086
0.062
0,051
0.038
ACC1
0.906
0.708
0.741
0.717
0.62
0.538
0.343
0.644
0.751
0.788
InFoRM
ED1
0011
01024
618
0102
6104
01001
0.135
0.174
0153
0085
0011
0101Y
0009
0003
0015
0009
00000
0008
8048
0J038
338149
ALCT
00M
GOM
OOM
OOM
0.119
0.83
0OM
00M
DOM
OOM
REDRESS
13P1
00M
GOMI
0OM
COM
0005
0.043
0CM
OUM
O0XI
ODSI
0OM
GOM
00M
Table 5: Parameter study of a. All the value is in scale of x x002.
Q
AUC
App
Bias
0.04
74.75
0.84
0.88
0.19
0.5
69.42
0.66
0.43
0.15
0.6
69.37
0.58
0.16
0.14
1.0
65.35
0.00
0.00
0.11
German. The German Graph credit dataset has 1,000 client records with attributes like Gender and Loannmount, used to classify individuals as good or bad credit risks. The similarity between node attributes is calculated using Minkowski distance and nodes are connected if the similarity is 80% of the maximum similarity.
Credit. Credit dataset, consisting 30,000 individuals with features such as education, credit history, age, and derived spending and payment patterns. The similarity between two node attributes calculated using Minkowski distance as the similarity measure and the credit defaulter graph network is constructed by connecting nodes with similarity of 70% of the maximum similarity between nodes.
The US state court bail outcome dataset (1990-2009) contains 18,876 defendant records with past criminal records, demographic attributes, etc. The similarity between node attributes is calculated using Minkowski distance and nodes connected if the similarity is 60% of the maximum similarity.
Recidivism.
G G.1 Parameter Study
More Experimental Details
Here we aim to study the sensitivity of FGD w.r.t. hyper-parameters. Specifically, we show the parameter study of a on Recidivism dataset. Here a controls the intensity regularize the coherence bias of the distilled small graph. The results in Table indicate that a can control the debiasing and utility performance of the distilled small graph.
G.2 Implementation Details
Synthesizer training, We adopt Adam optimizer for synthesizer training with 0.0002 learning rate. MLP, à consists of 3 linear layer with 128 hidden dimension. The outer loop number 16 while the inner loop is 4 for each epoch. For each experiment, we train with a maximum of 1200 epochs and 3 independent runs. The temperature parameter y
10. X' and ø are optimized alternatively.
GNN training. We adopt Adam optimizer for GNN training with 0.005 learning rate. All GNN models are 2 layers with 256 hidden dimensions. For Pokec-z, Pokec-n, German, Credit, and Recidivism the training epochs are 1500, 1500, 4000, 1000, and 1000 respectively.
16

---

020
s=0
100
Real s-0
Real s=1
Real s=1
012
615
Vanilla
Real center
FGD
Syn cen_te
010
000
0:0
25
-0.75
012
1.02
8000
60809
1.00
(a)
(b)
Figure 6: (a) shows the visualization of node representations from real graph and distilled graph, as well as their barycenter, on Credit dataset, after PCA. (b) shows the visualization of geometric intuition of node from real graph and distilled graph on Credit dataset.
G.3 More Visualization
We also visualize the node representation using PCA. We could observe that the barycenter of node from real graph and distilled graph is very close. And The distribution of node representation after being normalized to the circumference is consistent with the geometric intuition shown in Figure
H Limitations and Future Work
H.1 Non-binary Sensitive Attribute
For categorical sensitive attributes, if only one sensitive membership group's 's embeddings are far away from others, then the mean embeddings will still be close to the majority embeddings, especially for many categories, resulting in low variance (coherence). We argue that only this group with distant embedding (a small portion of samples) can have their sensitive attribute detected using embedding distributions. From metric perspective, we adopt the maximized Apr over any sensitive attribute group pair, the bias should be large due to considering the worst case. The proposed coherence may not work well this scenario, and an advanced coherence can be developed for this case, e.g., the maximized variance over any sensitive group pair. We leave the advanced coherence development for categorical, multiple, or even continuous sensitive attributes future work.
H.2 Individual Fairness
we find that all datasets suffer from a surprisingly more severe individual fairness problem (much higher IND score) when the model trained on the distilled graph, even if use InFoRM or REDRESS. This could be an interesting direction for future work, and we will add related work section.
From Table
discussion with references
H.3
Other Tasks
Our paper mainly focuses node classification tasks and it is possible to extend our method to other tasks or other group fairness problems. For instance, FGD may alleviate group fairness issues in link prediction tasks by reducing the coherence bias among different link groups. Exploring other tasks (e.g., recommendation, graph classification) or other fairesss metrics (e.g., individual fairness, rank fairness) could be interesting for future work.
17


Reviews:
[{"review_id": "6u7NRibmki", "reviewer": "Reviewer_QWwu", "summary": "This paper focuses on the task of graph distillation (GD) from a fairness perspective. The authors found that current GD method amplifies bias in GNN training compared to training on original graphs. Since the distilled graphs do not contain node attributes, it's intractable to directly apply previous debiasing methods. To address this issue, the authors first made assumptions on the representation space of the distilled graph. Then they propose to measure the bias in the distilled graph representations using the least square distance between the distilled representations and the subgroup representations in the original graph. Technically a variance-based regularization is utilized to punish the model w.r.t. this measure. Extensive experiments demonstrate that the proposed method can benefit GNN training on distilled graphs with improved fairness.", "questions": "See comments above.", "limitations": "See comments above.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper studies a novel topic and has its applicability in real-world scenarios. And it might bring in broader impact and more discussions on the characteristics and caveats of data distillation in other domains.\n\n2. The experiments are thorough.", "weaknesses": "1. The authors' design of the coherence loss in section 3.4 is confusing to me. Figure 2 shows that the intuition is to minimize the distance between z0 and z1 (as depicted by the red arcs in the figure), and this makes sense because fair representations should coincide in the attribute dimension. However, the definition in section 3.4 actually is the variance within group 0 or 1, and reducing this variance would only lead to more compact representations in each group, instead of bringing the two groups closer. Since the main contributions of this paper are based on this design, the authors should clarify this in a more rigorous manner.\n\n2. The empirical results on Pokec-z, German and Credit all show that the vanilla GD method can achieve comparable utilities with real graphs (within 5% accuracy gap) and worse fairness. Meanwhile, the results on Pokec-n and Recidivism show significantly worse utilities (up to 20% or 30% gap in accuracy), but better fairness. The improved fairness on these two datasets questions the motivation of this paper, that is the finding that the current GD method worsens GNN fairness. Also, I may wonder whether the authors have tuned the vanilla method right on these two datsets given such a large utility gap.\n\n3. There is not much logical connection between the theorems in sections 3.2 and the following part of the paper. Even if the span space does not match, or the barycenters are not consistent, it doesn't matter with the proposed method. The authors may need to justify the necessity of these theorems.\n\n4. Some typos. In the introduction part, the authors term the bias measurement as *consistency* (line 43), while it's *coherence* in other places. Line 143, it should be projection of z' instead of z. The defition of coherence loss in section 3.4 misses a superscript 2, since without this the formula is constant 0.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# 1. The authors' design of the coherence loss in section 3.4 is confusing\nThe confusion stems from a misunderstanding of the coherence loss definition in section 3.4. Here, the function $\\mathbf{\\pi}^s\\left(\\boldsymbol{Z}^{\\prime}\\right)$ represents the probability for **all samples** belonging to the sensitive group $s$. The index $s$ represents the index in a sensitive attribute prediction vector instead of specifying samples. For binary sensitive attribute case, it is necessary to satisfy  $\\mathbf{\\pi}^1\\left(\\boldsymbol{Z}^{\\prime}\\right)+\\mathbf{\\pi}^0\\left(\\boldsymbol{Z}^{\\prime}\\right)=1$ for probability prediction. Therefore, the term $\\operatorname{Coh}^s\\left(\\boldsymbol{Z}^{\\prime}\\right)$ indicates the variance of the probability for **all samples**, not just the variance within group 0 or 1.\n\nWe provide a comprehensive statement on how to estimate sensitive attribute and how to integrate such estimation into coherence loss in Sections 3.3 and 3.4, respectively. The intuition behind this design is related to the absence of sensitive attributes in the distilled graphs, which prevents the segregation of synthetic nodes into different sensitive groups. \n\nThis forms a key research challenge addressed in our work, and we'll take the reviewer's advice to further clarify this point in the revised manuscript to prevent any confusion. The figure and the related description were meant to simplify the understanding of the concept, and we'll make sure that they are consistent with the more rigorous mathematical description.\n\n# 2. Utility performance gap on Pokec-n and Recidivism dataset.\nThanks for this great point. We have meticulously tuned the vanilla distillation method for these datasets, taking into consideration the reduction rate. We report the **updated results on Pokec-n and Recidivism datasets** as follows. For the Credit dataset, we used a reduction rate of 0.08 (meaning that the number of nodes in the distilled graph is 8% of the original graph), as it's the largest applicable reduction rate for that specific dataset. And we use this for all datasets to control the setting.\nWe conduct new experiments for the Pokec-n and Recidivism datasets, where we utilized larger reduction rates of 0.32 and 0.16, respectively:\n|            |      |   GCN   |      |\n|:----------:|:----:|:-------:|:----:|\n|            |      | Vanilla |  FGD |\n|            | ACC↑ |   62.16  | 61.84 |\n|            | AUC↑ |   65.82  | 64.59 |\n|   Pokec-n  |  F1↑ |   57.38  | 58.62 |\n|            |  DP↓ |   5.83  | **0.84** |\n|            |  EO↓ |   6.34  | **1.94** |\n|      -      |     -     |        -   |     -    |\n|            | ACC↑ |   78.18  | 77.51 |\n|            | AUC↑ |   75.83  | 75.84 |\n| Recidivism |  F1↑ |   63.84  | 61.98 |\n|            |  DP↓ |   5.25  | **1.34** |\n|            |  EO↓ |   3.49  | **1.98** |\n\n1. **Utility Improvement**: The utility performance of the model improves when trained on a larger distilled graph but exhibits worse fairness performance.\n2. **Utility Gap Attribution**: The utility gap observed is attributable to the distillation method itself.\n3. **Fairness Issue Persistence**: Even when the utility performance is subpar, the fairness problem still exists and is a concern.\n4. **Our Method's Advantage**: Compared to the vanilla distillation method, our Fair Graph Distillation (FGD) enhances fairness performance while maintaining utility performance.\n\n# 3. Logical connection between the theorems and the following part of the paper.\nThe theorem presented in section 3.2 demonstrates the relation between the real data and distilled data, which serves as the rationality of sensitive attribute estimation. Specifically, **the distilled data and the real data reside in a similar semantic space**, which can be supported in Section 3.2 and Appendix D. Consequently, the sensitive estimation of distilled data is determined by the projection onto the orthogonal complement of the subspace spanned by real data from each sensitive group. Our theorem supports the rationality of the proposed estimation method.\n# 4. Some typos. \nThank you for your careful review and for identifying these inconsistencies and typos. We sincerely appreciate your suggestion.\n\n1. **Bias Measurement Term**: We acknowledge the discrepancy between the terms \"consistency\" and \"coherence.\" We will standardize the terminology throughout the paper.\n2. **Line 143 Error**: You are correct, and it should indeed be the projection of \\(z'\\) instead of \\(z\\). This will be corrected.\n3. **Coherence Loss Definition**: The variance calculation in section 3.4 is a typo, and we will revise it.\nWe will ensure that all of these corrections are implemented in the revised version of the manuscript. Thank you once again for your invaluable input.\n\n\n"}, {"review_id": "pn5UI6cyCt", "reviewer": "Reviewer_LkqE", "summary": "This paper discovered the fairness problem in the distilled GNN methods and then introduce a fair graph distillation process to generate fair distilled graph data. To propose the algorithm, they also introduce a new bias metric, coherence, and propose a bi-level optimization framework, FGD, for fair graph distillation. Theoretical analysis are provided. Experimental results validate FGD’s effectiveness in mitigating bias while maintaining model utility across various GNN architectures and datasets.", "questions": "1. What is the full name of FGD？ The full needs to be provided when this word first appears.\n2. Why the sensitive attribute S is a diagonal matrix, not a vector with the dimension of number of node? Is it for computation convenience?\n3. Some terminology needs simple description, such as span space and barycenter.\n4. Is this methods only applicable to node classification task? Can it be extended to link prediction or graph classification?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tGood presentation. This paper is easy and comfortable to read and follow.\n2.\tSolid theoretical analysis and experimental validation.\n3.\tThis paper is the first paper to solve the fairness problem in distilled GNN lines, which have good novelty and contribution.\n", "weaknesses": "1. Some terminology needs simple descirption. It is better to include some preliminary knowledge or terminology description to make paper more self-included.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# 1. What is the full name of FGD？ The full needs to be provided when this word first appears.\nThe acronym FGD stands for Fair Graph Distillation. We will include the full name in Line 54.\n\n# 2. Why the sensitive attribute S is a diagonal matrix, not a vector with the dimension of number of node? Is it for computation convenience?\nWe will revise the sensitive attribute $\\mathbf{S}$ as  $\\mathbf{s}$ in Lines 56 & 66 & 169. It should be a vector with the dimension of number of nodes.\n\n# 3. Some terminology needs simple description, such as span space and barycenter.\nThank you for pointing out the need for clarification on specific terminology. We provide the explanation on \"span space\" and \"barycenter\" as follows:\n- **Span Space**: The span space refers to the geometric space that is spanned by a specific set of vectors. It encompasses all the possible linear combinations of node representations.\n- **Barycenter**: The barycenter is referred to as the center of node representations within the same sensitive attribute group. It represents a central point that summarizes the distribution of the data.\n\nWe will include these simple descriptions in the revised manuscript.\n\n\n# 4. Is this methods only applicable to node classification task? Can it be extended to link prediction or graph classification?\nThanks for this great point. Our proposed method primarily focuses on the node classification task since the coherence loss is specifically designed for node-level sensitive attribute information leakage measurement. \n\nFor link prediction tasks, it is not easy to extend our method. The main reason is that the fairness definition for link prediction (e.g., **dyadic fairness [1]**) is significantly different from that in node classification. We have added the discussion on extending our method in link prediction in **Appendix H.3**. As for graph classification, to the best of our knowledge, there is not any fairness literature on this task. The reason is that the dataset for graph classification is molecular, and thus there is no sensitive attribute.\n\n[1] Li, Peizhao, et al. \"On dyadic fairness: Exploring and mitigating bias in graph connections.\" International Conference on Learning Representations. 2020.\n\n"}, {"review_id": "gBcWC16kk0", "reviewer": "Reviewer_5Zjc", "summary": "This paper aim to address the issue of fairness in graph data distillation, a process that condenses large real graphs into smaller distilled versions for more manageable computation with GNNs. They proposed FGD by introducing a new bias metric called coherence and using a bi-level optimization algorithm, which has shown to provide improved performance-fairness trade-offs in numerous experiments.", "questions": "See the weaknesses.", "limitations": "Whether the proposed framework can be applied to graph-level tasks, not just node-level ones.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.\tThis paper studies an interesting issue of fairness within distilled graphs, which arises due to the absence of sensitive features.\n2.\tThis paper devised a bias measurement named coherence specifically for distilled graphs, and suggests a framework utilizing this metric to facilitate the realization of fair graph distillation. The theoretical analysis in this paper is well founded.\n3.\tThe authors have conducted a thorough experimental analysis, and the presented results indicate that the proposed framework is adaptable to numerous renowned GNNs. This framework improves the trade-off between prediction performance and fairness across a range of datasets, signifying the framework's effectiveness and wide-ranging applicability.\n", "weaknesses": "1.\tAre there any fairness studies in dataset distillation in other fields such as computer vision and natural language processing? If so, there is a lack of discussion comparing the proposed framework with other similar works.\n2.\tThe time and space complexity are not mentioned.\n3.\tIn terms of methodology, this paper primarily uses strategies that were already developed before, and the unique contribution is the incorporation of a new loss term, Overall, the technical contribution of this work seems incremental.\n4.\tThe experimental part is inadequate, lacking integration of the proposed framework with large-scale and advanced GNNs, experiments in large datasets and the extra overhead of proposed framework.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# 1. Are there any fairness studies in dataset distillation in other fields?\nIn the existing literature, fairness studies related to dataset distillation in the fields of CV or NLP are not commonly found. The only fair distillation work we can found is [1]n which studies the fairness problem on the data distillation for text classification tasks based on adversarial method. \nTo our knowledge, our work is the first paper addressing group fairness issues on **graph distillation**, and we focus on graph data due to the unique challenge as graph is non-euclidian data.\nWe will include a section in the revised manuscript to discuss the novelty of our work considerations to other fields.\n\n[1] Han, Xudong, et al. \"Towards Fair Dataset Distillation for Text Classification.\" (SustaiNLP). 2022.\n\n# 2. The time and space complexity are not mentioned.\nWe provide the time and space complexity analysis as follows:\n\n1. **Forward Process of GCN**:\n    - On the original graph time and space complexity: $O\\left(r^L N d^2\\right)$ and $O\\left(r^L N d + N^2\\right)$, where $r$ is the number of sampled neighbors per node, $L$ is the number of layers, and $N$ and $d$ are the number of nodes in real data and hidden units, respectively.\n    - On the condensed graph time and space complexity: $O\\left(L N^{\\prime 2} d + L N' d\\right)$ and $O\\left(L N^{\\prime 2} + L N' d\\right)$, where $N'$ the number of nodes in distilled data .\n\n2. **Backward Propagation**:\n    - The time complexity of calculating the second-order derivatives is an additional $O\\big(\\left|\\boldsymbol{\\theta}\\right| N'(N'+d)\\big)$, where $\\left|\\boldsymbol{\\theta}\\right|$ is the number of parameters in $\\theta$. The space complexity is $O( |\\boldsymbol{\\theta}|^2 + N'(N'+d))$.\n\n3. **Coherence Loss**:\n    - The time and space complexity are $O\\left(L N^{\\prime 2} d \\right)$ and $O\\left(L N^{\\prime 3} d \\right)$, respectively.\n\nWe will add this complexity analysis in the revised manuscript.\n\n# 3. The technical contribution of this work seems incremental.\nWe respectively disagree with this comment. We clarify that one of the contributions is to find the fairness issue in graph distillation problem, which is interesting and novel. As for our technical contribution (i.e., coherence loss), it is significant and non-trivial. For distilled graph, the sensitive attribute is missing and thus it is challenging to identify the bias for node representation in distilled graph data. To tackle this challenge, we find the geometric connections in data distillation and provide the rationale for sensitive attribute estimation. In this way, the estimated sensitive attribute information can be used to measure the bias for the distilled graph. We believe that the proposed coherence loss is significant and non-trivial. \n# 4. Experiments on large-scale and advanced GNNs. The extra overhead of proposed framework.\nIt is infeasible to conduct the experiment for large-scale graph datasets in a fairness community since there is no public larger graph dataset.  The datasets we use in the paper are the most common in the graph fairness field. For large-scale GNN structure, we have conducted additional experiments using **GraphSAINT**, a well-known large-scale GNN method. We also record the 100 epoch training time for the vanilla distillation and FGD:\n\n|            |      |      |   GraphSAINT   |      |\n|:----------:|:----:|------|:-------:|:----:|\n|            |           | Real | Vanilla |  FGD |\n|            | ACC↑ |    70.84  |   64.56  | 63.73 |\n|            | AUC↑ |   78.19   |   70.43  | 71.94 |\n| Pokec-z|  F1↑ |   70.94    |   67.84  | 66.74 |\n|            |  DP↓ |   9.18   |   7.33  | 2.70 |\n|            |  EO↓ |   10.82   |   6.58  | 2.06 |\n|            |  100 epoch time |       |   59.8s  | 143.2s |\n|            |   |      |      |   |\n|            | ACC↑ |   69.74   |   61.45  | 58.34 |\n|            | AUC↑ |   75.19   |   62.48  | 60.84 |\n| Pokec-n|  F1↑ |   69.71   |   53.51  | 50.39 |\n|            |  DP↓ |    3.64  |   5.65  | 3.98 |\n|            |  EO↓ |    1.42  |   2.98  | 2.15 |\n|            |  100 epoch time |       |   55.9s  | 125.0s |\n|            |   |      |      |   |\n|            | ACC↑ |   71.17   |   70.63  | 70.06 |\n|            | AUC↑ |   68.83   |   56.68  | 55.30 |\n| German |  F1↑ |   82.34   |   82.11  | 79.83 |\n|            |  DP↓ |   4.74   |   5.25  | 3.53 |\n|            |  EO↓ |   3.57   |   3.49  | 2.62 |\n|            |  100 epoch time |       |   10.8s  | 23.6s |\n|            |   |      |      |   |\n|            | ACC↑ |   80.73   |   77.82  | 78.83 |\n|            | AUC↑ |   75.18   |   71.59  | 71.82 |\n| Credit |  F1↑ |    88.38  |   85.15  | 86.04 |\n|            |  DP↓ |   8.86   |   12.25  | 6.09 |\n|            |  EO↓ |   5.25   |   11.49  | 2.36 |\n|            |  100 epoch time |       |   67.8s  | 179.8s |\n|            |   |      |      |   |\n|            | ACC↑ |   93.37   |   71.38  | 70.72 |\n|            | AUC↑ |   96.18   |   70.28  | 69.71 |\n| Recidivism |  F1↑ |   90.63   |   58.94  | 61.63 |\n|            |  DP↓ |   6.15    |   3.49  | 2.93 |\n|            |  EO↓ |    4.53  |   2.48  | 1.94 |\n|            |  100 epoch time |       |   48.4s  | 64.9s |\n\nFrom the results, it is seen that our proposed FGD method maintains competitive utility performance while improving fairness metrics. While there is an increase in training time for FGD compared to the vanilla distillation method, the improvement in fairness metrics demonstrates the effectiveness of our approach in addressing fairness without compromising utility. \n\n# 5. Whether the proposed framework can be applied to graph-level tasks, not just node-level ones.\n\nFor graph classification task, to the best of our knowledge, there is not any fairness literature on this task. The reason is that the dataset for graph classification is molecular, and thus there is no sensitive attribute. We have added the discussion on extending our method in link prediction in **Appendix H.3**."}, {"review_id": "2rceEUjbva", "reviewer": "Reviewer_jsrW", "summary": "This paper proposes fair graph distillation (FGD), as an advanced graph distillation approach to generate fair distilled graphs. FGD focuses on the group fairness issue in graph distillation methods and aims to generate fair distilled graphs with respect to sensitive attributes for nodes. This paper proposes a simple yet effective metric for measuring the bias in representation space, namely coherence, for distilled graphs, and a bi-level optimization framework to generate fair graph distillations iteratively. Experimental results illustrate that the proposed methods can achieve  performance-fairness trade-offs across various datasets and architectures. ", "questions": "- Is FGD capable of handling muti-class cases? In the paper authors mentioned to use average coherence to optimize the distilled graph, yet there are no experiments on this.\n- What is the computational complexity of the overall algorithm?", "limitations": "- The distilled graphs can't achieve comparable performance compared with original graphs.\n- The presented method is only tested in binary classification scenario.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This paper considers group fairness issue, which is novel in graph distillation.\n- The proposed metric for bias measurement is simple yet convincing.\n- The theorems and algorithms introduced in paper is well presented.\n- Experimental results show the effectiveness of FGD in debiasing distillation.", "weaknesses": "- More baselines in graph distillation are needed. For example, *FairGNN* and *EDITS* are introduced as baselines in debiasing, while no graph distillation methods (such as [1]) are compared. \n- Results in Table 1 shows that distilled graphs could achieve some improvements in debiasing, while the AUC performance drops significantly (e.g. from 94% to 70%), which is unacceptable for node classification.\n\n\n[1] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset Condensation with Gradient Matching. In ICLR 2021", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# 1. More baselines in graph distillation are needed.\nThe vanilla baseline we utilized in our work is derived from the graph data condensation method introduced in [2] tailored for graph data using gradient matching, which is the same as [1]. Thus, [1] can not be directly adopted in graph data due to the lack of distilled adjacency matrix. We only choose [2] as our only vanilla graph data distillation baseline.\n\n[1] Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset Condensation with Gradient Matching. In ICLR 2021\n\n[2] Jin, Wei, et al. \"Graph condensation for graph neural networks.\" ICLR 2022.\n\n# 2. Utility performance drop.\nThanks for this great point. We have meticulously tuned the vanilla distillation method for these datasets, taking into consideration the reduction rate. In the original experiments, we used a reduction rate of 0.08 (meaning that the number of nodes in the distilled graph is 8% of the original graph) for all datasets. The small distilled graph leads to significantly worse utilities. Therefore, in the new experiments, we increase the reduction rate to 0.32 and 0.16 to increase the accuracy performance for the Pokec-n and Recidivism datasets, respectively. We report the **updated results on Pokec-n and Recidivism datasets** as follows.\n|            |      |   GCN   |      |\n|:----------:|:----:|:-------:|:----:|\n|            |      | Vanilla |  FGD |\n|            | ACC↑ |   62.16  | 61.84 |\n|            | AUC↑ |   65.82  | 64.59 |\n|   Pokec-n  |  F1↑ |   57.38  | 58.62 |\n|            |  DP↓ |   5.83  | **0.84** |\n|            |  EO↓ |   6.34  | **1.94** |\n|      -      |     -     |        -   |     -    |\n|            | ACC↑ |   78.18  | 77.51 |\n|            | AUC↑ |   75.83  | 75.84 |\n| Recidivism |  F1↑ |   63.84  | 61.98 |\n|            |  DP↓ |   5.25  | **1.34** |\n|            |  EO↓ |   3.49  | **1.98** |\n1. **Utility Improvement**: The utility performance of the model improves when trained on a larger distilled graph but exhibits worse fairness performance.\n2. **Utility Gap Attribution**: The utility gap observed is attributable to the distillation method itself.\n3. **Fairness Issue Persistence**: Even when the utility performance is subpar, the fairness problem still exists and is a concern.\n4. **Our Method's Advantage**: Compared to the vanilla distillation method, our Fair Graph Distillation (FGD) enhances fairness performance while maintaining or even improving utility performance.\n\n# 3. What is the computational complexity of the overall algorithm?\nWe provide the time and space complexity analysis as follows:\n\n1. **Forward Process of GCN**:\n    - On the original graph time and space complexity: $O\\left(r^L N d^2\\right)$ and $O\\left(r^L N d + N^2\\right)$, where $r$ is the number of sampled neighbors per node, $L$ is the number of layers, and $N$ and $d$ are the number of nodes in real data and hidden units, respectively.\n    - On the condensed graph time and space complexity: $O\\left(L N^{\\prime 2} d + L N' d\\right)$ and $O\\left(L N^{\\prime 2} + L N' d\\right)$, where $N'$ the number of nodes in distilled data .\n\n2. **Backward Propagation**:\n    - The time complexity of calculating the second-order derivatives is an additional $O\\big(\\left|\\boldsymbol{\\theta}\\right| N'(N'+d)\\big)$, where $\\left|\\boldsymbol{\\theta}\\right|$ is the number of parameters in $\\theta$. The space complexity is $O( |\\boldsymbol{\\theta}|^2 + N'(N'+d))$.\n\n3. **Coherence Loss**:\n    - The time and space complexity are $O\\left(L N^{\\prime 2} d \\right)$ and $O\\left(L N^{\\prime 3} d \\right)$, respectively.\n\nWe will add this complexity analysis in the revised manuscript.\n\n# 4. The distilled graphs can't achieve comparable performance compared with original graphs.\nWe have achieved comparable performance compared with the original graphs via tuning the reduction rate. Please see #2 for detailed response.\n\n# 5. The presented method is only tested in binary classification scenario?\nThank you for noting this limitation. Extending our approach to categorical, multiple, or continuous sensitive attributes indeed presents new challenges. We have discussed such an extension in **Appendix H.1** and leave it for future work.\n"}]

Author rebuttal:

Meta-review: This paper studies a novel problem, fair graph distillation, since vanilla method can worsen fairness issues. This paper introduces a bias measure, coherence, and propose a bi-level optimization method to generate fair graph distillation. Experiments show that the proposed method can achieve a good trade-offs between performance and fairness over various datasets and GNN architectures.
Decision: Accept (poster)