Fair GLASSO: Estimating Fair Graphical Models with Unbiased Statistical Behavior
Authors: Madeline Navarro
Samuel Rey
Andrei Buciulea
Antonio Marques
Santiago Segarra
Venue: NeurIPS 2024 poster (2024)
Keywords: Graphical model
fairness
graph learning
graphical lasso
Primary area: fairness

Abstract: We propose estimating Gaussian graphical models (GGMs) that are fair with respect to sensitive nodal attributes. Many real-world models exhibit unfair discriminatory behavior due to biases in data. Such discrimination is known to be exacerbated when data is equipped with pairwise relationships encoded in a graph. Additionally, the effect of biased data on graphical models is largely underexplored. We thus introduce fairness for graphical models in the form of two bias metrics to promote balance in statistical similarities across nodal groups with different sensitive attributes. Leveraging these metrics, we present Fair GLASSO, a regularized graphical lasso approach to obtain sparse Gaussian precision matrices with unbiased statistical dependencies across groups. We also propose an efficient proximal gradient algorithm to obtain the estimates. Theoretically, we express the tradeoff between fair and accurate estimated precision matrices. Critically, this includes demonstrating when accuracy can be preserved in the presence of a fairness regularizer. On top of this, we study the complexity of Fair GLASSO and demonstrate that our algorithm enjoys a fast convergence rate. Our empirical validation includes synthetic and real-world simulations that illustrate the value and effectiveness of our proposed optimization problem and iterative algorithm.

Fair GLASSO: Estimating Fair Graphical Models with Unbiased Statistical Behavior
Madeline Navarro Rice University naverice.. edu
Samuel Rey
Andrei Buciulea King Juan Carlos University andrei. undrei.buciule buciulea@urje es
King Juan Carlos University samuel. rey. escudero@urj...e
Antonio G. Marques
Santiago Segarra
King Juan Carlos University antonio. garcia. marques@urjc.es
Rice University segarraBrice. edu
Abstract
We propose estimating Gaussian graphical models (GGMs) that are fair with respect sensitive nodal attributes. Many real-world models exhibit unfair dis- criminatory behavior due to biases in data. Such discrimination known to be exacerbated when data is equipped with pairwise relationships encoded in graph. Additionally, the effect of biased data on graphical models is largely underexplored. We thus introduce faimesss for graphical models in the form of two bias metrics to promote balance in statistical similarities across nodal groups with different sensitive attributes. Leveraging these metrics, present Fair GLASSO, reg- ularized graphical lasso approach to obtain sparse Gaussian precision matrices with unbiased statistical dependencies across groups. We also propose efficient proximal gradient algorithm to obtain the estimates. Theoretically, we express the tradeoff' between fair and accurate estimated precision matrices. Critically, this includes demonstrating when accuracy can be preserved in the presence of fairness regularizer. On top of this, we study the complexity of Fair GLASSO and demonstrate that our algorithm enjoys a fast convergence rate. Our empirical validation includes synthetic and real-world simulations that illustrate the value and effectiveness of our proposed optimization problem and iterative algorithm.
Introduction
Data analysis frequently requires estimating complex dyadic relationships, which be conveniently encoded in graphical representations such as Gaussian graphical models (GGMs) 133. Myriad real-world applications model structure in data by obtaining graphs from observations, in fields including neuroscience, genomics, finance, and more 4 However, it is known that real-world data can encode historical biases which models ought not consider, such as discriminatory biases against sensitive populations [7] 8). For example, social networks often exhibit preferential relationships that may unfairly discriminate against sensitive communities IT. Moreover, the use of unfair graphs for downstream tasks is known to exacerbate existing biases [4] While accurate graphical representations are critical for applications and analyses, the propagation of undesirable bias in graph data necessitates learning models that balance both faimess and accuracy.
The long-standing popularity of GGMs for several applications, many of them high-stakes, warrants care in how we estimate them from potentially biased data. However, there no formal definition of fairness for graphical models, and existing definitions for graph-based machine learning may be applicable for obtaining fair statistical relationships. Indeed, while fairness for graph data has recently received copious attention, the study of biased graphs statistics and graph signal processing (GSP)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

is only beginning [7) Furthermore, previous works primarily consider faimess for downstream tasks, while few attempt to learn unbiased graphs from data [16H18]. We thus arrive two vital questions. First, what does it mean for graphical model to be fair? We aim to compare such notion to existing definitions of faimess on graphs. Second, how can we obtain GGMs that are fair in the presence of biased data? To address these questions, we consider estimation of fair GGMs from biased observations, where nodes belong to groups corresponding to different sensitive attributes.
We propose an optimization framework to obtain fair GGMs from potentially biased data, where statistical dependencies between nodes show no preferences for particular groups. We first define fairness for graphical models by introducing two bias metrics that measure similarities in statistical behavior between pairs of groups. Our metrics are simple and convex, yet they intuitively capture biases in terms of conditional dependence. We then propose Fair GLASSO, a penalized maximum likelihood estimator using our bias metries as regularizers, which aims to obtain sparse Gaussian precision matrices that optimally extract structural information from observed data while promoting fairer statistical behavior across node groups. We summarize our contributions as follows:
We formally define fairness for graphical models via two bias metrics, one balancing statistical dependencies evenly across all groups and a stronger alternative requiring each node be balanced across all groups. We relate our definition to other notions of fairness on graphs, where ours is specific to graphs encoding conditional dependence structures, which in turn allows greater interpretability and more detailed statistical analysis.
We present Fair GLASSO, a penalized maximum likelihood estimator for sparse Gaussian precision matrices that are unbiased according to any measure of graphical fairesss, which we demonstrate with our proposed bias metrics. We theoretically demonstrate that our approach yields a tradeoff between fairness and accuracy, which depends on the bias in the underlying graph.
The convexity of Fair GLASSO under our proposed metrics allows us to propose an efficient iterative method based on proximal gradient descent. We show that our algorithm enjoys iterations of moderate complexity and provable convergence.
We evaluate Fair GLASSO on both synthetic and real-world datasets. The former provides empirical validation of the efficiency of our algorithm and the existence of the faimess-acccuaay tradeoff. The latter shows the myriad real-world applications for which can reliably obtain graphical representations from data while also balancing statistical behavior across sensitive groups
1.1 Notation
p). For a matrix X E RexP and a set of indices C [p]², we let X denote a masking operation on X permitting non-zero entries only at indices in C. If we define DD == {r(i - 1) + i) then XL is a diagonal matrix containing the diagonal entries of X. For D := [p] denoting the complement of the set D, X = X
For any positive integer p E N, we let [p] ==
contains non-zero values of X only in its off-diagonal entries. We also let vec(X) E R² denote the vertical concatenation of the columns of X. The smallest and largest eigenvalues of a matrix X are represented respectively by Amin (X) and Xmax (X).
2 Fair Gaussian Graphical Models
GGMs succinetly model pairwise relationships in multivariate Gaussian distributions through intuitive graphical representations. We denote undirected graphs by g = (V, W), where V= [p] is the set of nodes and & C x V the set of edges connecting pairs of nodes. For graphs with weighted edges, W E RPxP encodes the topological structure of 9 such that Way * 0 and only if (i.j) E E, that is, there is an edge in E connecting nodes and j with weight W cj. Let x E Rº be random vector following a zero-mean Gaussian distribution with positive definite covariance matrix Σn > 0, that is, x ~ (0, ).). The precision matrix O = En¹ completely describes the conditional dependence structure among the variables in In particular, for any distinct pair i, E 'p). variables z; and xj are conditionally independent if and only if [@uley = 0 2 This Markovian property yields a graphical representation, where off aff-diagonaa entries of O encode the weighted edges of graph g connecting conditionally dependent variables. In this work, we aim to obtain the structure encoded in O, using observations sampled from (0, En).
When considering group fairness, we associate each variable in x with one of g groups that partition the variables according sensitive attribute [20] 21.. We represent group membership by the

---

M: 0,4654, W: 0.010, A: 0.025
M: 0.008, W: 1,576, A: 0.410
M: 0.4816 W: 8.501, A: 1.43
(a) Karate club network
(b) Dutch school network
(c) U.S. Senate network
Figure I: Three real-world networks with node groups denoted by color. Within-group edges are in blue and across group edges in red, while edge widths correspond to edge weight magnitudes. For each network, we present ("MM") the modularity of the graphs with respect to group membership [19]. ("W"") the ratio of positive to negative estimated partial correlations for within -group edges, and ("A") an analogous ratio for across-group edges. Networks (a) and (c) show high group-wise modularity, while (b) and (c) show significant preferences for positive correlations in the same group.
indicator matrix = [zi..... . Lyl {0, 1)pxs, where Zio- 1 and only if variable belongs to group E [g]. otherwise Zio- = O. Group sizes are denoted by Pa Σ Zio for every [g]- We also assume that groups are non-overlapping. thus
Σn Pa- GGMs may possess biases when a group of variables behaves significantly more or less similarly to particular groups. Indeed, individuals within the same political party tend to vote similarly [18]. In this case, entries of Oo corresponding to pairs of voters of the same party will likely be positive and larger in magnitude.
We empirically demonstrate this phenomenon in Figure I for multiple real-world networks. Fig- ures M and b show two social network examples, Zachary's 's karate club network [22 2 and the Dutch school network [24] where nodes represent individuals and edges connect them by their relationships. Figure - is a political network that connects U.S. senators if their voting patterns exhibit correlated behavior [18.. For each network, we present both their modularity with respect to group membership
[19 and comparison of their approximate partial correlations within and across nodal groups 25 26 with both metrics defined in Appendix G Figures [ and show higher group-wise modularity, in line with the ubiquitous preference for within-group connections in real- world networks [9, TO However, observe that Figures [ and с exhibit clear preference for positive correlations between nodes in the same group. Despite its presence in real-world interconnected data, this type of discriminatory behavior is typically not addressed in existing works (27). These examples inspire us to develop a definition of fairness for graphical models that accounts for both correlation bias, when behavior is highly correlated between certain groups, and connectivity bias, when connections are denser or sparser across certain group pairs.
2.1 Bias Metric for Fair Graphical Models
To address biases in both connectivity and correlations, we propose definition of group fairesss for graphical models. We consider the popular notion of demographic parity (DP), the primary choice for fairness graphs 200; however, other definitions of group fairness can be similarly adapted [21]. DP requires that outcomes be agnostic to sensitive attributes (20) 28). our case, we require estimation of graphical models with unbiased edge selection with respect to nodal groups. Thus, we present the following definition of dyadic DP for graphical models.
Definition For a graphical model with the matrix O E R encoding the underlying conditional dependence structure, we consider DP to be satisfied if
P[[Oo)ij = 1, Zia = 1] P[[Oo]e Eia = 1, E,o = Va = [g].
(I)
Note that the distribution need not be Gaussian for this definition. Intuitively, our graphical model DP requires that groups have evenly balanced connections across groups and do not behave significantly accounts for both forms of bias showcased in Figure [ connectivity bias in the support of On and correlation bias in the signs of entries in Op Not only is this definition appropriately tailored to fairness for graphical models, but
more or less similarly to certain groups. Crucially, Definition I
3

---

also provides flexibility in how we address biases. We may adjust similarities in behavior without changing the topology of the graph [14 29). but conversely, we may alter connections if correlations cannot be changed 30) Finally, note that works for fairness on graphs with weighted or signed edges are rare [27], and to the best of our knowledge no previous work has specified fairness for graphical
models that encode conditional dependencies.
We consider a graphical model unfair when there is a gap in DP, that when (T does not hold. In practice, we measure biases in GGMs by approximating the DP gap. For this purpose, we propose the following bias metric inspired by [8].
1 H = g²
2 ② pZa Pa Pa
2 D2
PaPb
hyfe
Each term in (2) compares the average within-group edge weight and the average across-group edge weight for every distinct group pair. Thus, H(@) will increase if variables belonging to two groups exhibit either significantly denser sparser connections significantly stronger or weaker correlations. As we aim to balance statistical behavior across groups, we consider obtaining precision matrices O that balance data fidelity with small values of (O). The main difference between H (+) and the related metric in [8] lies in the use of squared summands. While subtle, this modification tends to yield fairer outcomes, as group pairs are balanced overall as opposed to the metric in (18). which may favor balancing some pairs of groups over others.
In addition to we also propose a stronger alternative metric for node-wise faimess across groups,
O O
[Qpz
H node (
pg
Pa
Pb
Dęfa
which is zero and only if every variable is completely balanced across groups in terms connections correlation. This stronger metric is inspired by I8), also modified by squaring summands as for HO)). As an alternative interpretation, observe that Hnode ( increases when the correlation between the group of variable i and the i-th column of @ increases. This node-wise penalty is stronger than H H))), as we require that not only pairs of groups exhibit no preference in statistical similarities but also each node must show no preference for connecting to certain groups.
For graph- works, the predominant choice of bias metric is DP (see related works in Appendix Thus, we approach the nascent task of graphical model estimation with a familiar bias metric to verify our approach with established measurements. However, our formulation is suited to others such equalized odds (EO), defined in Appendix [ While both DP and EO popular fairness definitions, we cannot compute EO for the true preciston matrix since is conditioned on the ground truth connections. For this reason, emphasize DP for group fairness since measure of bias in the true precision matrix is critical to our theoretical interpretation of the chiress--accural tradeoff.
Fair GLASSO
3.1 Graphical Lasso for Fair GGMs
We apply our proposed metrics in 2 and 3) to estimate GGMs from observations while mitigating both connectivity and correlation biases (see Section 2). Assume that we observe n samples from the distribution N (0, Σn) collected in the data matrix X E Rexp, To estimate fair and sparse precision matrices from data, we adapt the celebrated graphical lasso method [26] 31 32), a penalized maximum likelihood approach for recovering GGMs.
Given the sample covariance matrix Σ 1 X X, we present Fair GLASSO, a version of graphical lasso for fair GGMs,
o' = argmin tr( ((Ιθ) - log det θ + cI) + Mr |00pl l1 + R2
S.l. + E M = ( Rpxr
+ ž 0, |011 < a),
(4)
where Ry denotes bias penalty measuring the fairness of O and μr, u2 2 0 tune the encouragement of sparse and fair precision matrices, respectively, For the penalty Rg, we can choose not only our

---

proposed metrics H and Hnode but also any metric for measuring bias on graphs. Similar to existing works on graph Laplacian GGMs [33], the addition of cI for e adds practicality to our approach. permitting us to obtain positive semi-definite precision matrices. The ability to estimate rank- matrices allows for disconnected graph solutions. We assume that the true precision matrix Oo has bounded eigenvalues (see 2 and As3 in Section 3.2). hence the constraint ||0|| 2 a on O. In practice, an effective a be obtained by
the spectral norm of @ for large enough overshooting its value based on the minimum eigenvalue of the sample covariance Σ. For further context of how both our proposed bias metrics and Hode and our Fair GLASSO method relate to existing works, we provide detailed review of related works in Appendix [A] We present our approach for estimating GGMs. but indeed we may consider other distributions for the problem formulation in { such as the Ising negative log-likelihood. As our theoretical analysis requires Gaussianity, we proceed under this assumption, but future work will see the application of fair regularization other distributions. Moreover, our empirical results in Section 4 show satisfactory performance optimizing (4) even for real-world datasets with non- Gaussian data.
3.2 Fair GLASSO Theoretical Analysis
We theoretically characterize the performance of Fair GLASSO. In particular, we focus on the effect of our fairness penalty in (4). Our result demonstrates the error rate of @* not only from a traditional statistical perspective but also in terms of the bias in the true precision matrix On. Indeed, as O, becomes more unfair, we expect that imposing unbiased estimates hinders estimation performance. Let the set S = {(i,j) y0]² Oj * O, + j} contain the indices of the non-zero, off-diagonal entries of Og. We first share the following assumptions on O and Z.
AS1 (Bounded sparsity) There exists a constant 8 > 0 such that the cardinality of S satisfies |S| S 8.
AS2 (Bounded spectrum) There exists a constant k such that Amin (Ex) 2 O.
AS3 (Bounded spectrum) There exists a constant k > O such that Xmax (Eo) S k < cx.
AS4 (Persistent groups) All groups have the same size, that is, Pa = p 2 for every a E [g].
Assumptions A AS2 and AS follow those from the distinguished work [32]. Note that A is imposed for simplicity, but similar results hold if we merely require asymptotically similar groups sizes, where no groups vanish as + oc. With our assumptions in place, we present our main result on the eтror rate of Fair GLASSO, the proof of which can be found in Appendix B
Theorem Assume that A to A holld and that μr X (logp)/n and μ2 = o(1. Moreover, let RH H from (2) and e 0 in (4. With probability tending to I as n. oG, there exist constants mi, m2 > such that
8) logg | - -Ouls miy
V0 V H(O))
m2
(5)
n
vP
Moreover, there exists a constant q > O such that if μ2 satisfies
qp² log
2
(6)
g2n H
then with probability tending to I as p + oc we can further guarantee that
(p + 5) logp
0 - - S m1
n
Our error bound consists of the Frobenius norm convergence rate for graphical lasso in 32 and term accounting for the bias penalty in (4) In particular, the second term (5) portrays the influence of bias in the true precision matrix O.. Theorem not only provides an intuitive error bound for fair estimation of GGMs but also exemplifies when tradeoff between fairness and accuracy may occur. When the true model O is biased, that is, H(Op) is large, then performance may suffer according to (5). However, if bias mitigation is mild enough, that is, if μ/ small enough to satisfy (6), then we instead enjoy the error rate of (32 with no adverse effect from the bias penalty. Indeed, as the true
5

---

Og becomes fairer, so too grows the range of values of μl that guarantee 7 then imposing strong bias penalty can obtain fair estimates O' while maintaining accuracy.
Thus, if Oo is unbiased,
In addition to the explicit Frobenius error rate of O", we are also interested in when we can sufficiently describe the true model behavior. Our next result shows how well Fair GLASSO solutions approximate the true distribution, which enjoys the same rate as in Theorem I proven in Appendix C
Corollary Let the assumptions of Theorem 7 hold. Then, with probabiliy tending I as n, co, there exist constants mi, mlg > such that
| Eo 1 S m/ / (p+s) 8) logp
V V9V H
ml
(8)
vP
Moreover, there exists a constant > O such that when satisfies (6. then with probability tending p + 0o we can further guarantee that
(p + logp
|00E0- 10-11 1 S 5m/
Note that a similar rate to 9 holds up to a constant if we replace Eg with Σ. Thus, we may apply |0'Σ I| p as an error metric when the true covariance matrix Eg is unavailable.
3.3 Algorithmic Implementation
If we choose Ry in 4 as H or Hnode the
Algorithm 1: Fair GLASSO from Gaussian observations.
convexity of the resul- tant problem allows us to introduce a simple yet effective algorithm for Fair GLASSO esti- mates. We base our approach on an acceler- ated proximal gradient 5
Input: Sample covariance E, weights tt and μ2, Lipschitz constant L of f-
Initialize 6
6 E M,
{()) = 1, k =.
while Stopping criteria met do
3 Proximal gradient descent: (A)
Ta/l -iVi-
Projection step: é (k) IIM (é (k)
Adaptive step size update: ((++
{1 + / + 4(1(0)02)
method known as fast iter- ative shrinkage algorithm
Accelerated update: e (+++1
(M)
(0)
4 (N) 2 1))-1))
(FISTA) [34], which is
7
Update iteration: l: = + 1.
well suited to solving non- smooth, constrained opti- mization problems. More-
end
Output EEsimmtted precision matrix e = 6 (k)
over, our ensuing FISTA approach is still applicable under other distributions as long as the associated loss in is convex and differentiable, such the negative log- likelihood of the Ising model.
We separate the Fair GLASSO objective function F(O) ʃ(@) + 1((@) into its smooth and non-smooth terms via (() and h (),, respectively. which are given by
f( = ir( tr(e)) log det ( +el #2RL ())
h())) μ | Opll
(10)
The proposed algorithm estimate @* is presented in Algorithm algorithm in Appendix D and we provide further details in Appendix E including specifying the gradient Vof and the Lipschitz constant of when RH = H RA Haode-
We discuss the steps of our
Computationally. the complexity of Algorithm Iis limited by an eigendecomposition in the projection step and matrix inverse in the proximal gradient descent step (see (50) and (5T) in Appendix D for details). Over-the-shelf implementations of these operations render a computational complexity of O(r²), However, implementations based on fast matrix multiplication may result in improved complexity of Op²*), remarkable improvement since the optimization problem involves learning p² variables. Finally, in addition to mild computational complexity, the proposed algorithm enjoys a convergence rate of O T2) which we formally state next and prove in Appendix

---

POL-1
R0. MK0
VI5I No
NFV
0.2
0.8
0.15
Iaror
0.6
Blos
Bios
10
0.05
0.2
10
0.2
0.4
10
-1
0.5
Bias data
(c) Brror
Figure 2: Estimation performance in terms of error and bias. (a) Bias and error for estimating fair graph as data becomes more biased. (b) Bias and error as graph size grows for ER graphs. (c) Bias and error for biased real-world network [3 as the number of observations grows.
Theorem Let (6 (1)
tx21 be the sequence generated by Algorithm 1 for solving the optimization problem ④ where we denote the global minimum by @* Then, for any k 2 1,
AL (0) - 1
| (R) -
(11)
o 112
where L is the Lipschitz constant of f()) and corresponds the spectral constraint in
Thus, Theorem guarantees convergence of Algorithm to the optimal solution O* uunder our constraints in (4) with either of our bias metrics in or (3) Not only the convex fairness penalties amenable to efficient algorithms with well-understood performance guarantees, we also able to guarantee that our algorithm converges with respect to the estimation variable, which is stronger than previous works' results on convergence of the objective function 35
Experiments
We illustrate the ability of Fair GLASSO to reliably estimate both synthetic and real-world graphs from data while promoting unbiased connections. Extensive experimental details including our performance metrics, the basclines with which compare, and the real-world datasets provided in Appendix G these details are summarized here. We include additional experiments on the effect of varying the hyperparameters μ41 and #2 and violating assumptions (AS1)-(AS4) of Theorem on Appendix H
We compare our method with existing approaches for both scalability and performance. In particular, we consider GL: Traditional graphical lasso (26] (ii) FGL: Fair GLASSO with R, H, (iii)
NFGL: Fair GLASSO with R Huodes (iv) FST: Network inference from spectral templates with
a group-wise bias penalty 18
36.. (v) NFST: Network inference from spectral templates with
node-wise bias penalty [15 18 and (vi) RWGL: Graphical lasso with randomly rewired edges.
We then perform GGM estimation on multiple real-world networks: (i) Karate club:
the social network of Zachary's karate club members 22 (ii) School: A contact network of high school students (37]. (iii) Friendship: The friendship network of the same high school students as in
School 37. (iv) Co-authorship: An author collaboration network (38), and (v) MovieLens: A movie recommender network [39]. Figure d demonstrateed that interconnected data may have fair or unfair relationships; thus, our experiment not only exemplifies the viability of our approach for real-world settings but also the fairness- accuraay tradeoff depending on biases in data.
4.1 Estimating Fair Graphs with Biased Data
Consider the realistic setting where our model is to be implemented in fair setting, but our observa- tions contain unfair biases [8]. We aim to obtain accurate graphical models by reducing the biases encoded in data. We consider synthetic networks whose nodes show no preferential connections, but observations become increasingly unfair, growing in preference for within-group correlations.
Figure 2 presents the error and bias from networks estimated using graphical lasso with and without bias penalties H and Hnode- As expected, all methods show increase in both error and bias the
7

---

data becomes more unfair, as our observations are not only straying from the true distribution but also tending toward unfair behavior. However, FGL and NFGL not only preserve lower bias than GI., but we also improve estimation performance. This significant result exemplifies the situation described in Section our proposed penalties not only yield unbiased estimates but also serve as informative priors when the underlying graph is fair. Thus, we enjoy improvement in both faireess and accuracy for this realistic setting.
4.2 Performance as Graph Size Increases
Fair GLASSO adapts traditional GGM learning through the bias penalty, which includes (2) and (3) To observe the regularization effect of our penalties, we compare graphical lasso both with and without bias penalties for estimating synthetic networks as the graph size p grows, which also demonstrates the
Nodes p
GL
FGL-0
FGL-1
50
2.06
0.55
0,64
200
18.80
8.14
8.87
1000
10225.74
1900.89
1893.57
Table 1: Running time in seconds of Algo-
scalability of our method. We thus implement GL via a state-of-the-art approach for comparison [26). Figure 2 shows the relationship between error and bias the estimated graphs. Each line corre- sponds to graph estimation method, and points on the lines denote the varying dimension, ranging from p = 50 (highlighted via darker, filled markers) to p = 1000.
rithm and graphical lasso via (26]
First, observe that GL achieves superior accuracy at the expense of a larger bias, while NFGL improves bias, albeit with greater error. In contrast, FGL for μl2 E (1, 10) can improve bias without sacrificing accuracy, where μ/2 10 yields the most Pareto-optimal solution. This result aligns with Theorem [ showcasing the ability of Fair GLASSO to maintain estimation performance while significantly improving the fairness of the obtained graph. Critically, even as p increases, our method enjoys relatively short running times, ranging from 0.5 seconds for 50 nodes to 30 minutes for 1000, which we show in Table [ Our implementation of the classical algorithm in (26) requires 2 seconds and 17 minutes for p 50 and p = 1000, respectively. We can then conclude that our efficient algorithm for Fair GLASSO can sufficiently handle larger graphs.
4.3 Social Network with Synthetic Signals
We next apply Fair GLASSO for the Karate club network, real-world graph with known biased connections (23) As this network famously exhibits group-wise modularity [22], we can compare different methods for estimating a real biased network. We show bias and error as the number of data samples increases from n = 102 (denoted by darker, filled markers) to n = 10 in Figure 2 Since this graph does not have data, we generate synthetic Gaussian observations on the social network. Note that we only consider synthetic samples for this real-world dataset; the remainder are equipped with set of real graph signals. In addition to the previously considered baselines, we also compare to FGL-L1 and NFGL-L1, which correspond to Fair GLASSO using the group-wise and node-wise bias metrics in 18 as the penalty Rg. These metrics may prioritize balancing some group pairs over others, as described in Section 2.1
For all methods, increasing the number of samples improves estimation error, but bias also grows since the underlying graph is unfair. Observe that all alternatives GL are able to reduce estimation bias. As expected, randomly rewiring edges from graphical lasso estimates in RWGL does mildly improve bias when compared to GI, but error also rises significantly. The methods designed for fair graph estimation achieve the greatest improvement in bias, with our proposed methods FGL and NFGL outperforming FST and NFST in both bias and error. We also observe that FGL and NFGL using our bias metrics H and Hnode with squared terms improve both fairness and accuracy over FGL-L1 and NFGL-L1 using the analogous metrics in [5] which consider sums of absolute values of each term. Moreover, not only does FGL outperform other methods in both faimess and accuracy for all n, but FGL is the only approach that simultaneously decreases bias and error. Fair GLASSO is therefore viable for estimating weal-world networks with known biased connections.
We also investigate the effect of H versus Hnode for estimating group-wise modular networks. Figure 3 visualizes three graphs learned using GL, FGL, and NFGL. Both FGL and NFGL attempt to mitigate biased connections by reducing larger weights for existing within-group edges. However, since FGL aims to improve bias in expectation, Figure 3p shows an increase in negative -ithin-group
8

---

(a) GL: Graphical lasso
(b) FGL: Fair GLASSO with bias penalty H
(c) NFGL: Fair GLASSO with bias penalty Haode
Estimated Karate club network via graphical lasso with and without penalties H and Hode- Node colors denote group membership. while edge thickness denotes edge weight magnitude and edge color its sign, with blue (red) as positive (negative) correlation. (a) Estimation via GL. (b) Estimation via FGL. (c) Estimation via NFGL.
Figure 3:
edges, that is, negative partial correlations between nodes the same group. Conversely, Figure B shows network with more balanced connections per node, where more nodes connected to new edges that are both positive and negative. This result suggests that the bias metric H for group-wise balance in expectation aligns more with existing definitions of DP, while the node-wise DP gap H Haode behaves closer to an individual fairness metric 40
4.4 Fair GGMs for Real-World Data
Finally, in Table we evaluate Fair GLASSO to estimate graphs from four real-world datasets consisting of two social networks, School and Friendship with gender as the sensitive attribute; collaboration network Co-authorship with groups representing the type of conference in which each author publishes most; and recommendation network MovieLens, where we consider binary sensitive attributes for each movie (node) denoting whether or not the movie was released after 1991. Evaluating Fair GLASSO on these datasets not only demonstrates its effectiveness on relevant real-world scenarios with biases, which are described in greater detail in Appendix G but we can also showcase performance on non-Gaussian data, such as the discrete graph signals of the School and Fri Friendship social networks. As each network varies in level of biases in their connections and observations, we show results for both weak and strong bias mitigation, that is, P2 E {1, 10%), for all fair graph learning methods.
For the relatively unbiased School and Friendship networks, our methods FGL and NFGL obtain superior estimation accuracy while sufficiently accounting for biases, particularly in comparison with FST and NEST. Unsurprisingly, we observe the lowest estimation error when μl 1 is small enough such that FGL and NFGL achieve similar bias to Ground truth. However, observe that FGL and NFGL have low estimation error even for large μ/2 = 10 which enjoys significant bias reduction. This verifies the results from Theorem and in Figure for real-world data; when the underlying graph is fair, our bias penalties serve as informative structural priors that improve performance.
For the Co-authorship network, we also observe the best accuracy using FGL and NFGL when μ12 small enough that bias is similar to that of the true network. Critically, even when #l is large, we observe errors for FGL and NFGL competitive with GL while also achieving low bias. Moreover, for the MovieLens dataset, Fair GLASSO the only method that rivals GL in accuracy while acquiring significantly fairer estimates. Indeed, FGL with #2 = 10" is the only method to achieve both low error and bias simultaneously. This implies that the observations both the Co-authorship and MovieLens datasets are biased, since high bias mitigation yielding fair estimates improves estimation performance. Thus, we demonstrate that relationships in real data can be explained by graphical models rivaling the accuracy of state-of-the-at approaches while also exhibiting fairer behavior.

---

School
Co-authorship
MovicLens
Friendship
Error
Bias
Error
Bias
Error
Bias
Error
Bias
Ground truth
0.20330
14.052
0.6791
0.1487
GL
0.2661
0.3111
0.1995
12.6102
0.0223
0.9529
0.6477
0,4068
RWGL-150
0.3497
0.3943
0.2308
12.5836
2.1919
0.9409
0.6509
0.4068
RWGL-3300
0.3775
0.5110
0.2978
12.5735
2.2002
0.9184
0.6633
0.3861
EST (J12 =
0,4383
0.8942
0,4188
0.5754
0.1724
4.0568
1.0606
0.3787
NEST (222 = 1)
0,4386
0.8924
0,4068
6.6887
0.1724
4,0568
1.1
0.3734
FST (/22- = 10%)
1.7820
1.0767
1.0801
129.5384
0.1724
4.0568
1.1924
0.0052
NEST (f22 = 10%)
1.6131
3.1971
1.0500
176.6285
0.1724
4.0568
1.1852
0,0081
FGL (a2 I)
0.1417
0,4824
0.1896
10.3317
0.0253
0.8177
0.0505
0.1657
NEGL (J22 1)
0.1417
0.4824
0.1895
11.8391
0.0253
0.8177
0.0505
0.1657
FGL (/22 = 10%)
0.1449
0.0308
0.2432
0.1899
0.0248
0.6106
0.0516
0.0153
NEGL (J22 =10%)
0.2981
0.0827
0.2708
0.7908
0.0239
0.7104
0.0873
0.0243
Table Bias and error for estimating four real-world networks. The top row shows the bias present in the true underlying network. The best performances are in bold.
5 Conclusion
This work proposes two metrics to evaluate bias graphical models, which we apply as regularizers for fair GGM estimation. In particular, we adapt DP to measure biases in the conditional dependence structure encoded graphical models, where nodes may show preferences for certain groups terms of either connections or correlations. Unlike existing works that typically only consider fairness based on the unweighted topology of known graph, we extend the concept of graph DP for the weighted connectivity patterns represented by the precision matrix of Gaussian distribution. Moreover, we apply our group fairness for graphical models to modify graphical lasso for estimating fair GGMs. Future work will more general graphical models, along with other extensions both in terms of the graph setting and fairness, which we discuss further in Appendix
Broader Impact
In this work, we proposed fair adaptation of graphical lasso, extremely prominent method for complex data analysis. The development of methods that encourage fairness is necessary to ensure ethical and trustworthy tools, particularly those applied extensively GGMs to several critical and sensitive applications. Biases present in real-world graphs are well known, such as biased connections due to gender in social network analysis or segregated communities of co-authors in different disciplines. We revealed that these graphical biases extend beyond preferences in connections to include tuthin-group correlations members to behave similarly has not been investigated for graphical models, as bias in signed edges has not been considered. Our paper contributes expanding available unbiased graph- bapphbbsedd methods, leading to extensions of other graphical models and statistical tools.
behavior. Indeed, while intuitive, the tendency for group
Moreover, as fairness on graphs is still nascent, several graph-based tasks have yet be considered under the lens of fairness. Indeed, models are typically encouraged to be unbiased with respect to independent entities, but recent years have seen greater attention paid the treatment of data equipped with graphical relationships. We not only participate in this movement, but we also extend fairness on graphs by considering weighted and signed edges for graphical models encoding conditional dependencies. This paper serves as critical step in developing fair graph-based tools, particularly as GGMs are used in several high-stake fields, including finance and medicine.
10

---

Acknowledgments and Disclosure of Funding
This work was partially supported by the Spanish AEI PID2022-18 110022-13687NN--OOG and TED2021- 130347B-100 100, the Community of Madrid via the ELLIS Madrid Unit, and the U.S. NSF under award CCF-2340481. Research was sponsored by the Army Research Office and was accomplished under Grant Number W91 ANNN-7----002 The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Office or the U.S. Army or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
References
[1] Daphne Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT press, 2009.
[2] Steffen Lauritzen. Graphical Models, volume 17. Clarendon Press, 1996.
[3] Gonzalo Mateos, Santiago Segarra, Antonio Marques, and Alejandro Ribeiro. Connecting dots:
Identifying network structure via graph signal processing, IEEE Signal Processing Magazine, 36(3):16-43, 2019.
[4] Eugene Belilovsky, Gaël Varoquaux, and Matthew B Blaschko. Testing for differences in Gaussian graphical models: Applications to brain connectivity. In Advances in Neural Information Processing Systems, volume 29, 2016.
[5] Stephen M Smith, Karla L Miller, Gholamreza Salimi-Khorshidi, Matthew Webster, Christian Beckmann, Thomas E Nichols, Joseph Ramsey, and Mark W Woolrich. Network modelling methods FMRL. Neurolmage, 54(2)8755-811, 2011.
[6] Oliver Stegle, Sarah A Teichmann, and John Marioni. Computational and analytical challenges in single-cell transcriptomics. Nature Reviews Genetics, 16(3):133- 145, 2015.
[7] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Innovations in Theoretical Computer Science, page 214 226, 2012.
[8] Anja Lambrecht and Catherine Tucker. Algorithmic bias? An empirical study of apparent gender-based discrimination the display of STEM career ads. Management Science, 65(7):2966-298 2981, 2019.
[9] Fariba Karimi, Mathieu Génois, Claudia Wagner, Philipp Singer, and Markus Strohmaier. Homophily influences ranking of minorities social networks. Scientific Reports, 8(1):11077, 2018.
[10] Yosh Halberstam and Brian Knight. Homophily, group size, and diffusion political information social networks: Evidence from Twitter. Journal of Public Economics, 143:73-88, 88, 2016.
[11] Eli Pariser. The Filter Bubble: How the New Personalized Web Is Changing What We Read and How We Think. Penguin, 2011.
[12] Avishck Bose and William Hamilton. Compositional fairness constraints for graph embeddings. In International Conference on Machine Learning, volume 97, pages 715-724, 2019.
[13] Enyan Dai and Suhang Wang. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In International Conference Web Search and Data Mining, page 2021.
[14] Peizhao Li, Yifei Wang, Han Zhao, Pengyu Hong, and Hongfu Liu. On dyadic fairness: Exploring and mitigating bias in graph connections. In International Conference on Learning Representations, 2021.
[15] Oyku Deniz Kose, Yanning Shen, and Gonzalo Mateos. Faimess-awaree optimal graph filter design. arXiv preprint arXiv:2310. 14432, 2023.
[16] Davoud Ataee Tarzanagh, Laura Balzano, and Alfred O Hero. Fair community detection and structure learning in heterogeneous graphical models. arXiv preprint arXiv:2112.05722 2023.
[17] Xiang Zhang and Qiao Wang. A unified framework for fair spectral clustering with effective graph learning. arXiv preprint arXiv:2311.13766 2023.

---

[18] Madeline Navarro, Samuel Rey, Andrei Buciulea, Antonio G Marques. and Santiago Segarra. Mitigating subpopulation bias for fair network topology inference. arXiv preprint arXiv:2403.1559/ 2024.
[19] Farzan Masrour, Tyler Wilson, Heng Yan, Pang-Ning Tan, and Abdol Esfahanian. Bursting the filter bubble: Faimess- aware network link prediction. AAAI Conference on Artificial Intelligence. 34(01):841 848, 2020.
[20] Michael Feldman, Sorelle Friedler, John Moeller, Carlos Seheidegger, and Suresh Venkatasubramanian. Certifying and removing disparate impact. In ACM International Conference on Knowledge Discovery and Data Mining, page 259-268, 2015.
[21] Moritz Hardt, Eric Price, Eric Price, and Nati Srehro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems, volume 29, 2016.
[22] Michelle Girvan and Mark E J Newman. Community structure in social and biological networks, Proceed- ings of the National Academy of Sciences of the United States of America, 99(12)7781177826 2002.
[23] Wayne W Zachary. An information flow model for conflict and fission in small groups. Journal of Anthropoloicaal Research, 33(4):452-473, 1977.
[24] Andrea Beate Knecht. Friendship selection and friends' influence: dynamics of networks and actor attributes in early udolescence. PhD thesis, University Utrecht, 2008.
[25] Arthur Dempster. Covariance selection. Biometrics, 28(1):157-173 1972.
[26] Jerome Friedman. Trevor Hastie, and Robert Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9(3):432 441, 2008.
[27] Akrati Saxena, George Fletcher, and Mykola Pechenizkiy, FairSNA: Algorithmic faimess in social network analysis. ACM Computing Surveys, 56(8): 1-4,, 2024.
[28] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairesss gerrymandering: Auditing and learning for subgroup faimess, In International Conference on Muchine Learning, volume 80, pages 2564-2572, 2018.
[29] Indro Spinelli, Simone Scardapane, Amir Hussain, and Aurelio Uncini. FairDrop: Biased edge dropout for enhancing fairness in graph representation learning. IEEE Transactions on Artificial Intelligence. 3(3): 344-354, 2022.
[30] Oyku Deniz Kose and Yanning Shen. Fair contrastive learning on graphs. IEEE Transactions on Signal and Information Processing over Networks, 8:475-488, 2022.
[31] Alexandre d' Aspremont, Onureena Banerjee, and Laurent El Ghaoui. First-order methods for sparse covariance selection. SIAM Journal on Matrix Analysis and Applications, 30(1):56-66, 2008.
[32] Adam J Rothman, Peter J Bickel, Elizaveta Levina, and Ji Zhu, Sparse permutation invariant covariance estimation. Electronic Journal of Statistics, 2, 2008.
[33] Jiaxi Ying, José Vinícius de Miranda Cardoso, and Daniel Palomar. Nonconvex sparse graph learning under Laplacian constrained graphical model. In Advances in Neural Information Processing Systems, volume 33, pages 7101-7113, 2020.
[34] Amir Beck and Mare Teboulle. fast iterative shrinnkgg-thresshollingg algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 281):133200, 2009.
[35] Sang Oh. Onkar Dalal, Kshitij Khare, and Bala Rajaratnam. Optimization methods for sparse pseudo- likelihood graphical model selection. In Advances in Neural Information Processing Systems, volume 27, 2014.
[36] Santiago Segarra, Antonio G Marques, Gonzalo Mateos, and Alejandro Ribeiro. Network topology inference from spectral templates. IEEE Transactions Signal and Information Processing over Networks, 3(3):477-43, 2017.
[37] Julie Fournet and Alain Barrat, Contact patterns among high school students. PLoS ONE, 99) 2014.
[38] Andrei Buciulea, Elvin Isufi, Geert Leus, and Antonio Marques. Learning graphs and simplicial complexes from data. In IEEE International Conference on Acoustics, Speech, and Signal Processing. pages 2024.
12

---

[39] F Maxwwell Harper and Joseph A Konstan. The MovieLens datasets: History and context. ACM Transactions Interactive Intelligent Systems, 5(4), 2015.
[40] Yushun Dong, Jian Kang, Hanghang Tong, and Jundong Li. Individual fairesss for graph neural networks: A ranking based approach. In ACM International Conference on Knowledge Discovery and Data Mining, pages 300-310, 2021.
[41] Jian Kang, Jingrui He, Ross Macicjewski, and Hanghang Tong. InFoRM: Individual faimess on graph mining. In ACM International Conference Knowledge Discovery and Data Mining, pages 379-389, 2020.
[42] Eric Kolaezyk. Statistical Analysis of Network Data: Methods and Models. Springer, 2009.
[43] Brian Baingana, Gonzalo Mateos, and Georgios Giannakis. Proximal-gradien algorithms for tracking cascades over social networks. IEEE Journal of Selected Topicx in Signal Procexsing, 8(4):563-575. 2014.
[44] Onurcena Banerjee, Laurent El Ghaoui, and Alexandre d' Aspremont. Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data. Journal of Machine Learning Research, (15):485-516, 2008
[45] Janging Fan and Runze Li. Variable selection via nonconeave penalized likelihood and its oracle properties. Journal of the American Statistical Association, 134856)) 2001.
[46] Cun-Hui Zhang, Nearly unbiased variable selection under minimax concave penalty. The Annals of Statistics, 38(2):894 942, 2010.
[47] Samuel Rey, Madeline Navarro, Andrei Buciulea, Santiago Segarra, and Antonio G Marques, Joint graph learning from Gaussian observations in the presence of hidden nodes. In Asilomar Conference Signals, Systems, and Computers, pages 53-57. IEEE, 2022.
[48] Patrick Danaher, Pei Wang, and Daniela Witten. The joint graphical lasso for inverse covariance estima- tion across multiple classes. Journal of the Royal Statistical Society, Series B (Statistical Methodology), 76 (2):373-397, 2013.
[49] Andrei Buciulea, Jiaxi Ying, Antonio G Marques, and Daniel P Palomar. Polynomial graphical lasso: Learning edges from Gaussian graph-stationary signals. arXiv preprint arXiv:2404.0262/ 2024.
[50] Nicolai Meinshausen and Peter Bühlmann. High-dimensional graphs and variable selection with the Lasso. The Annals of Statistics, 34(3), 2006. ISSN 0090-5364,
[51] Pradeep Ravikumar, Martin J Wainwright, Garvesh Raskutti, and Bin Yu. High-dimensional covariance estimation by minimizing E1-penalized log-determinant divergence. Electronic Journal of Statistics, 5, 2011. ISSN 1935-7524.
[52] Clifford I Lam and Jianqing Fan. Sparsistency and rates of convergence large covariance matrix estimation. The Annals of Statistics. 37B) 2009.
[53] Pradeep Ravikumar, Martin Wainwright, and John D Lafferty. High-dimensional Ising model selection using Él-regularized logistic regression. The Annals of Statistics, 38(3), 2010. ISSN -390-5364.
[54] Eunho Yang. Genevera Allen, Zhandong Liu, and Pradeep Ravikumar. Graphical models via generalized linear models. In Advances in Neural Information Processing Systems, volume 25, 2012.
[55] Rebecca Morrison, Ricardo Baptista, and Youssef Marzouk. Beyond normality: Learning sparse prob- abilistic graphical models the non-Gaussian setting. In Advances Neural Information Processing Systems, volume 30, 2017.
[56] Sandeep Kumar, Jiaxi Ying, Jose Vinicius de Miranda Cardoso, and Daniel Palomar, Structured graph learning via Laplacian spectral constraints. In Advances in Neural Information Processing Systems, volume 32, 2019.
[57] Madeline Navarro, Samuel Rey, Andrei Buciulea, Antonio Marques, and Santiago Segarra. Joint network topology inference the presence of hidden nodes. IEEE Transactions on Signal Processing, 2024.
[58] Samuel Rey, T Mitchell Roddenberry, Santiago Segarra, and Antonio G Marques. Enhanced graph-learning schemes driven by similar distributions of motifs. IEEE Transactions on Signal Processing, 71:3014-3023 2023.
13

---

[59] Martin Sevilla, Antonio G Marques, and Santiago Segarra. Estimation of partially known Gaussian graphical models with score-based structural priors. In International Conference Artificial Intelligence and Statistics, pages 1558-1566. 2024.
[60] Ruijia Wang. Xiao Wang. Chuan Shi, and Le Song. Uncovering the structural faimess in graph contrastive learning. Advances in Neural Information Processing Systems, volume 35, pages 52465-32473 2022.
[61] Maarten Buyl and Tijl De Bie. DeBayes: A Bayesian method for debiasing network embeddings. In International Conference on Machine Learning, volume 119, pages 1220 1229, 2020.
[62] Le Wu, Lei Chen, Pengyang Shao, Richang Hong, Xiting Wang, and Meng Wang. Learning fair repre- sentations for recommendation: graph-based perspective. ACM Web Conference, pages 2198-2208. 2021.
[63] Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards a unified framework for fair and stable graph representation learning. In The Conference on Uncertainty in Artificial Intelligence, volume 161, pages 21 14 2124, 2021.
[64] Oyku Deniz Kose and Yanning Shen. Fair node representation learning via adaptive data augmentation. arXiv:2201.08549 2022.
[65] Yushun Dong, Ninghao Liu, Brian Jalaian, and Jundong Li. EDITS: Modeling and mitigating data bias for graph neural networks. In ACM Web Conference, pages 1269. 2022.
[66] Oyku Deniz Kose and Yanning Shen. FairWire: Fair graph generation. arXiv:2402.04338 2024.
[67] Peter Bickel and Elizaveta Levina. Regularized estimation of large covariance matrices. The Annals of Statistics, 36(1):199-227, 2008.
[68] Amir Beck. First-Order Methods Optimization. STAM, 2017.
[69] Ana-Andrcea Stoica, Christopher Riederer, and Augustin Chaintreau. Algorithmic glass ceiling in social networks: effects of social recommendations on network diversity. International World Wide Web Conference, page 923-932, 2018.
[70] Chen Avin, Zvi Lotker, Yinon Nahum, and David Peleg. Modeling and analysis of glass ceiling and power incquality in bi-populated societies. In International Winter School and Conference on Network Science, pages 61-73. Springer International Publishing, 2017.
[71] Cho-Jui Hsieh, Matyas A Sustik, Inderjit S Dhillon, Pradeep K Ravikumar, and Russell Poldrack. BIG QUIC: Sparse inverse covariance estimation for million variables. In Advances in Neural Information Processing Systems, volume 26, 2013.
[72] Tianyi Yao, Minjie Wang, and Genevera I Allen. Fast and accurate graph learning for huge data via minipatch ensembles. arXiv preprint arXiv: 10..:22677 2021.
[73] Xiwen Wang, Jiaxi Ying, and Daniel Palomar. Learning large-scale MTP2 Gaussian graphical models via bridge-block decomposition. In Advances Neural Information Processing Systems, volume 36, pages 73211-73231, 2023.
14

---

A Related Work
A.1 Graph Estimation
Obtaining graphical representations from data has long stood of the most prominent tasks in several fields, including statistics, GSP, and more [ 42 Maximum likelihood estimation of GGMs first introduced by Dempster [25]. and subsequent additions of the f --norm penalty produced the famous graphical lasso approach [31 32
44). Several modifications and extensions
followed, typically proposing alternative penalties 4 45 49 and its popularity has brought about copious theoretical investigation into its performance, its limitations, and more 126 32 52) While Gaussianity is typical for estimating graphs, extensions non- non-Gaussian distributions are also well studied [53)55]. Similar approaches have found use in GSP, both under additional constraints and in more general settings
B3 36 56 57.
Most works learn graphs from data solely to preserve some notion of fidelity that may potentially be aided by prior structural assumptions 58 59 However, estimating graphs while improving performance in both accuracy and fairness in connections remains novel [18]. Moreover, to the best of our knowledge, we are the first to estimate graphical models from data while explicitly encouraging fairness in its connections, particularly in terms of both connectivity and correlation bias [16].
A.2 Fairness Graphs
Fairness in graph-based tasks has received much attention recently, particularly in the field of machine learning. In addition to group fairness 13 14], some works consider other definitions such as individual structural fairness 40
41
60 The most prevalent tasks for fairness
graphs are link prediction [2] 14
19
61
62 and node representation [2] 13 62 64), where
nodes must experience equal treatment regardless of their sensitive attributes. Some works directly alter graph structure to promote unbiased connections, but, unlike our work, this requires a known graph
29
61 65).
number works consider creating fair graphs, which share our goal of obtaining graph represen- tations that possess unbiased connectivity patterns [16 (66). This includes fair graph generative models [[66], which aims to learn distributions of graph data, whereas we learn graph structure from nodal observations. We note 18-188 as the only other works of which are aware that estimate graphs from data while considering fair outcomes. However, for [16] 17). the task is fundamentally different they aim to cluster nodes fairly without explicitly imposing fairness on graph structure.
While the task in [8] is the same as ours, we differ not only in how our samples are modeled but also in definition of fairness, which is specific graphical models encoding conditional dependence. Moreover, we provide further theoretical results, including guarantees of both error rates and algorithmic convergence.
B Proof of Theorem 1
Our proof of Theorem Tis inspired by that of (32). While some steps in this work are analogous to those of our result in Theorem []] the presence the bias penalty yields subtle differences. Thus, elaborate all steps of the proof to demonstrate deviations from the original result along with providing self- contained result for clarity. We first require the following lemma [67] Lemma A.3], which allows to bound differences between entries of estimated and true Gaussian covariance matrix entries with high probability.
Lemma (Bickel and Levina (67] For iid Gaussian random vectors Z₁ ~ (O for [n] such that Xmaax (S) co, have that
P
ZiZZe Sig
2 ne
s ci expl
(12)
where 0 is bounded, and C₁ C2 and are dependent only on k.
15

---

We proceed with the proof of (5) in the statement of Theorem ! Consider a function Q that measures
the difference in the objective of given @ E M and the true precision matrix O
Q( = tr(e)) log det e + pl1 + (2
tr -r((0,)) + log det O μu 11 1ul N2 (
ur((E - E .o)) + e θa)) (log det - log det Op)
+ + O 11 | + #2 (H) - (
(13)
We may also represent the objective difference in terms the disparity between and D. that is,
G = @ + A) for A e O. where we have
G(A) tr((2 Eo
tr(2 A (log de - A) log det Oa)
+ MI O + ااه - [.] + #2 (O A) - H H()))).
(14)
We may then use Q and to compare O and O via their difference under the objective function of proposed graphical lasso problem
By the definition of O" E .M as the minimizer of 44. we have that Q()") < 0 and thus G(A*) S
for A = = Og. If we can show that G( A for every A .M such that
9 96 (1)e
A F > min + m2
(15)
vp
where
(p + 8) log
(16)
n for some constants m1, m2 > O, then we know that || A II satisfies (5) in Theorem as desired. To this end. we obtain lower bound of G(A) and determine the conditions under which we can guarantee that G(A) 0 for any A E M such that (15) holds.
Trace difference. We begin by addressing the first term of 14). These steps analogous those of 33). By the triangle inequality, we define nonnegative values t and ty such that
In((E Mi(E-Ea)) Eo) S
CEis
[Eols)
+
Σ SS. - Eola) =:4 4 12,
(17)
for which provide upper bound. To bound f,, note that by Lemma 1 may choose any constant Cj > 0 such that
1 n Xa. Eolis
log
Eig
Eolsyl
2 c1 n
(18)
n
with probability at most dip duzp for constants d1, d2 > 0. Then, by the union sum inequality,
P max Eis
EElyy 2 a
logp
P
U
Ees
Eolyy 2 a
log
ifj
log
Σ P
Σrg EQolip c1
n
< di (p²
p)p duet < dip -ds
(19)
where > 22/dz and d3 > doc 2. We then apply the Cauchy-Schward inequality for the following bound on tj.
log |A S ay
S max
Σij Eoliy
A
(20)
ifj
n
16

---

whose probability tends to 1 as p + oo as in the right-hand side of 19
For 12, again apply the Cauchy- Sahhar inequality and Lemma to obtain
1
1/2
l2
[h [
|
< v max Ér - [Zolill |A KE(p)
plogP ||Dl|E
2 02
11
< C2rn ||
(21)
with probability again approaching 1 as p 3o.
We combine
20 and (1) to obtain a lower bound of the first term of [1)).
log
tr(( A) |
- - n
A
02 A
(22)
Log-determinant difference. We next consider the difference of log determinants in G(A) which differs from the proof of [32] as we consider an inequality (T5) rather than an equality. Consider the function f(t) log det @ + ) The derivative and second derivative of f(t) are
(1) tr((O + 11) A)
(23)
f"(t) tr (O), + ) AO, +1A)-1),
(24)
respectively. Then, the Maclaurin series expansion of f(1) with the integral form of the remainder is
f(1) - f(0)= = f() ['' (1) - v)de
(25)
so by the symmetry of Ou and A we apply the Kronecker product for log @ + A) logg det O
= -r((oA): 1 (1 -
+ + A(O, + aA) dd
= tr(-nA) - vec(A) [ (1. + @ (@o + a)) -dd rec(A). (26)
Recall that the definition of the smallest eigenvalue of matrix A Amin (A) [[]]x x Ax. We thus have
log ( + A) .log det Og
s tr (r(E - | F Arnin (f(1-1)) () + - & (Op -
| 2 / (1 Vi (0, + -'u
< (E)))=
(27)
since the eigenvalues of the Kronecker product of two matrices are the products of their eigenvalues. Then, we have that
log det Ou + A) log det θ, < A)
A
min 2 (Op + vA)
2
eE(0,1]
$ AE
||
A
+))
2
min
A(EA))
1
A
2
O + +A)
2
A(E
1
A
2
@ + |||
2
(EEA)))
A
(E
|
p)-
(28)
2
17

---

We define 7 = max 4, (1 + ||I })),, which gives us
log det O + +) log det O I tr(
1
|
F
(k
+1}) -2
2
I (r())A))
k2
A P
(29)
2r
Sparsity penalties. For the sparsity penalties, note that by the definition of S, we may follow the steps in [32] and exploit the fact that I|[@, + ا lll I| + A Abnslll + l| Ansll and
p = 01 Then, by the triangle inequality,
iu O + Alpll, I[@o)llli) 2 pnsll ||
(30)
DP gaps. Finally, we consider the difference DP gaps. Observe that H()) both differentiable and convex in O Thus, we have that
H(O, + A) (1))))
((Vo)
& IV
((V))
Ir(V=H((O))@o) (vV(((((
2 [eet( (1 + 2
N - (a' (+.ll
(31)
Moreover, recall that by definition Cab is block constant for every a, E [g]. Thus, the gradient He as in the right- ggntt-hand side of (5T) is block-wise constant with g blocks, hence it is at most rank g. We then have that
(v)((
1 v0l V
2/9
g
Σ
tr(Cnt |/Cobll
g2
a=1 byka
2
1
1/2
Ir(Cab
g² 9
1
$2
a=1 bya
4/0
(t( On)
plg2 9)
byta
1/2
4/g
ΣΣ
tr( tr(Cas 0n)
(32)
8/ - a= bota
where the last inequality holds by ||x|| S mm |x||2 for any vector x E R By the definition of H,
(o))l < A/g ((.)).
(33)
We then have the following lower bound for the difference in DP gaps,
H + + H(O)) 2 +
H(O))
>
C3g
p v H())).
(34)
P
We now combine the lower bounds for each term in 14 that is, 22
30 and
For
G < 1, we let
log
(35)
18

---

Then, we have that
log
G(A) 2
k | 1p ciV n
b112
02Tn
|
2T
+ 11
bns 111 - |A (Anslli)
12239
(())))
P
2
| 1 ci
+ _
i'
C2nn 1111Abl1--
-22
A
u2233
v H())))
2T
61
p
1
1.2
|
c
1+
1
(36)
4T
A
2
A
c2fa
(37)
h
P2C39
HH()))
(38)
4T
p
where we aim to find conditions on
A
F ensuring that each term (36). (37 and 38 are positive so (36) and (37). we obtain the following lower bounds
that G(A) > O. For the first two terms
A
4Tk 4Tk 2 (1
1
1
nm
(39)
E1
and
A > 4
(40)
respectively. For the third term 338 we have
| 4reap2
2 /H()))
(41)
(39 and 441 guarantee that G(A) is positive. Combining the conditions, we obtain sufficient condition to ensure that G(A) > 0,
All three conditions (40)
A
max 4rk
1
+ 02 rai 4TC3//2 Vp H(OO)
(42)
P
Thus, there exist constants mı, m2 > O such that with high probability n. 00,
V V (Ha)
A F > mnn + m2
(43)
VD
When this holds for any A E M, then we have shown that G(A) O. Thus, since G(A*) S 0 and
A M,, we have that
|| S miin + m2 / ((O)))
(44)
vp
with high probability. Recalling that gp = p by AS Moreover, note that if we select #2 such that
we obtain the inequality in (5). as desired.
4rk -1
D² logp n H(O))
<
1
+
+
02
C3
E1
4rk
4
p(p + 8) log ng H())))
1 C
+ 02
(45)
C3
then 42 becomes equivalent to
+ (a( (
4rk (a
| F
Tn.
(46)
and we need only satisfy A |p > mira with probability tending to as n.P - oo for any A E M. which guarantees that G > 0. Again, since G(A*) < 0. then have with high probability as
co that
U1 S minn
(47)
for small enough μ/2 dependent on the dimension p. the number of samples n, the number of groups g, and the faimness of the true precision matrix H (Oo). satisfying (7) as desired.
19

---

C Proof of Corollary |
Recall that by definition, Og20 I. Then,
| 1 II(@" - ( Eollo s k ||@ O
(48)
The result then follows from Theorem for m² = km and m² kmz-
D Optimization Algorithm Details
We provide an overview on computing the update steps for Algorithm T take gradient step for ((),, where the Lipschitz constant of f plays the role of the step size, then we perform a proximal step over the non-smooth terms in (()). The proximal step for h( (()
For each iteration, we first
)) the
soft-thresholding operation for the & norm,
(O;))) = max - X, 0) sign)
(49)
where sign(x) returns the sign of After the proximal gradient step, perform orthogonal projection IIM onto the feasible set, which in our case is given by
(M) min {max {A. 0} _l/2] VT.
(50)
with V and A respectively denoting the eigenvectors and eigenvalues of e, and with some abuse of notation we let min max ( A, 0), a 1/2] denote an element-wis wise minimum and maximum operation on the entries of A, which projects all the eigenvalues in the diagonal of A onto the interval [0, a //3..
Both the gradient fe and the Lipschitz constant I. of f contingent the choice of bias penalty. The following two lemmas provide their computation for the cases where we apply Rd = H, our DP gap measurement are deferred to Appendix
Ru Hnode its mode-wise alternative The proofs of both lemmas
Lemma Let the bias penalty Rh in (4) be given by H()) in 2 Then, the gradient of f(0) is given by
2p
Vef(O) E (0
+
tr(C...))CTT
(51)
g²
bga
where Cub == / (p2 Pa) 2a (PaPb)) pp for every a, E [g] such that a # b. Moreover, for C Enybh Cab & Co have that Vef(O) is Lipschitz with constant
1 2 g²
2p2
2u2
11
Max (C) S L
(Cabl(Cab))
(52)
92 9
byfa
Intuitively, while L1 is smaller Lipschitz constant, involves computing the eigendecomposition of a p² x p² matrix, which may be prohibitive in sisher-dimensional settings. Consequently. L provides an approximation involving only p x p matrices. The following lemma provides similar results when the node-wise DP gap Hnode is employed.
Lemma Let the bias penalty Ry in 4 be given by Hnode ( in Then, the gradient of f()) is given by
Vol(0)= ( cl) 1 + 2u0 A@
(53)
where
Zu
Zb
Za
Zb
A
(54)
pg(g - 1)2
a=1 bitta
ligha
b
Pa
pb
Moreover, Vef(O) is Lipschitz with constant
L
+ 2412 Amx (A).
(55)
20

---

For more concrete intuition, we present a brief analysis for bias metric R (0) H ( but similar analysis holds for other penalties such as ( = (()). The first step of Algorithm is proximal gradient step. Computing the gradient requires an inverse ( + <I)= and product p. both incurring O(p²) operations. The gradient step and noftthhresholding enjoy entry-wise computations with complexities (p²²). The projection step onto the set of positive semidefinite
matrices involves an eigendecomposition of Ô (k) with complexity (pr²). Finally, the step size update
only requires scalar operations, and the accelerated update of é (k+1) involves ((p²) operations, so they can be neglected.
E
Gradients and Lipschitz Constants
Here, we provide the computation of relevant gradients and Lipschitz constants for f in (TO) used in the proposed Algorithm I. Both the gradient and the Lipschitz constant of depend the choice of bias penalty ())).
E.1
Proof of Lemma 2
First, we rewrite the demographic parity ADP 2 as
H())
Σ
(56)
g2
bya
where Cab is defined in the statement of Lemma The gradient of H can be obtained as
2
9
VoH(()
(57)
-
byka
and adding the gradient of the remaining terms of f(O), the result follows
Vel(O) = E (0 + +l)
+ 2p12
Σ [C(o)
(58)
g² bgf
Next, show that the gradient of /(@) is Lipschitz, it suffices show that its Hessian is bounded. The Hessian (() can be computed as
2p2 (Cab @ C.b), g² g a=1 bbba
(0 (0+))) ((++)
(59)
and it bounded by
(a)(())l2 - (0 (0 -d+
( (++d) -1
+ g² g
2p
ΣΣ
Cas & CT.
a=1 Data
2p12
Amax (Cub) = L1-
(60)
2
a=1 byta
Moreover, also follows that
[+))( <
(0 cI) & (0+cl)
+ 2p2
g² |Cl2
2p
< 2
Amax (C) L.
Ln.
(61)
g²
Consequently, the gradient Vef(O) is Lipschitz with constants L1 < LT
21

---

E.2
Proof of Lemma] 3
For the node-bar based DP gap H Hnode ()) as (3). applying standard gradient calculus compute the gradient and the Hessian of f(@) gives
Vef(@) Σ - + e
2u2 plo
(62)
Vo (6 + el) @ (0 + +I) + 2/2 (I A).
(63)
Then, the Lipschitz constant is obtained from the following upper bound of the Hessian
1
[Vff()) < ( (++ ( +1) 122 + 2pz I A
< E
+ 2pzdmax (A) L2. (64)
Proof of Theorem
Our proof builds over the convergence result for FISTA 34 Thm. 4.4), which establishes that the sequence (e
>221 (#2)) generated by FISTA satisfies the following bound
2 00) 07
F(O F(O")= < (k: + 1)2
(655
where O' is the global minimum of the objective function of 4p. This result requires f(O), the smooth components of F(O), to be convex function with Lipschitz continuous gradient, while (,), the non-smooth components of F(O), only required to be convex.
From the expression of f(@) and h(O) in (T)) clear that both terms of our objective function are
convex. Furthermore, from Lemma 2 and Lemma 3 it follows that the gradient of f( ( is Lipschitz continuous when we consider RØ H or RH nodes so the conditions from Thm. 4.4] are
met and (65) holds.
Next, we demonstrate that the objective function F(O) is strongly convex. A function F(O) is a-strongly convex if F(+) o | || is also convex, which implies that V F(O) -l = 0. Put in words, the eigenvalues of the Hessian need be larger than for F(O) be o-strongly convex. Let fi( = (E)) log det ( + <I), whose Hessian is given by
fa = (e + a) @ (++ =
(66)
Since ④ is constrained by | 112 < applying the properties of the inverse and the Kronecker product renders the following bound on the eigenvalues of (efi(O)
1
Amin (o))
(67)
2 (++
2 4
Recall that is assumed to be small parameter such that c² < A (o)1(0) 2 I so (e) is strongly convex with constant &. hence rendering F(O) also strongly convex with the same constant.
(0). Consequently,
The last ingredient is given by 668 Thm. 5.25], which establishes that if F(O) is strongly convex with constant a, then
2 (F(() ((("))
| - 0
(68)
for every O in the domain F.
Finally, our result follows from combining (65) and 68
G Experimental Details
The following details include descriptions of datasets, baselines, and performance metrics. For synthetic experiments, we run simulations over 50 independent realizations of generated data. Moreover, excepting experiments for which we test different specific parameter values, choose optimal values of hyperparameters via grid search.
Datasets.
The numerical evaluation of the proposed algorithm is carried out over synthetic and real-world data. The main features of the different datasets are summarized in Table Additional details are given next.
22

---

Nodes (No.)
Edges
Signals (No.)
Groups
Sensitive attribute
School
Students (126)
959
Interactions (28561)
2
Gender
Co-authorship
Authors (130)
525
Keywords (1903)
Publication type
MovieLens
Movies (200)
665
Ratings (943)
2
Old/New
Friendship
Students (311)
1009
Interactions (47127)
Gender
Table 3: Properties of the real datasets used in Section 4
Synthetic data. Unless specified otherwise, graphs with p 100 nodes are sampled from an Erdós-Rényi (ER) random graph model with an average of 10 links per node, The precision matrix is set to either the combinatorial graph Laplacian [33] or an adjacency matrix with a loaded diagonal to ensure positive definiteness, and is employed to sample graph signals from zero-mean multivariate Gaussian distribution. The number of sampled signals satisfies the conditions of Theorem [ 50 independent realizations of graphs and signals are generated and report the mean performance.
For experiments based on synthetic data,
Karate club. A social network where the 34 nodes represent members from karate club and edges capture interactions between pairs of members outside the club [22 23 This dataset is famously modular with respect to groups, serving a well-known biased network of real-world individuals, Since this graph does not have associated nodal observations, we generate signals multivariate Gaussian samples as described in the previous point for synthetic data using the adjacency matrix of the social network with loaded diagonal as the precision matrix. Similarly, we evaluate experiments with this synthetic data over 50 independent realizations of generated signals with the mean performance reported.
MovieLens This novii-recommendation dataset contains ratings for 1.682 movies by 943 users, resulting in sparse data as many movies have few ratings. Biases in recommendation systems can reproduce and even exacerbate existing harmful stereotypes (g] The Movie- Lens dataset, a common benchmark for fair graph machine learning, exemplifies our ability to form unbiased models from networks used for recommendation systems. To address this sparsity, we followed the setup in [7 and selected the 200 most-rated movies as nodes, using the ratings from the 943 users as graph signals. Since the dataset lacks a ground truth graph, we report the model fit as defined in Corollary
[ rather than the error in Table 2 The sensitive attribute for each node is determined by whether the movie was released before or after 1991.
Co-authorship Fl The dataset includes papers from the ACM conference, featuring 17,431 authors, 122,499 papers, and 1, 1,903 keywords. The nodes represent a subset of these authors. The sensitive attribute associated with each author is determined by the conference type in which that author publishes the most. We demonstrate
example of data with more than two groups through the Co-authorship network with publication type as the sensitive attribute. To create the ground truth graph, we analyzed author-paper relationships and established an edge between two authors if they collaborated on a paper. For graph data generation, we utilized the total number of different keywords, with each input graph signal reflecting the frequency with which a specific author uses a particular keyword across their papers. We constructed the graph by selecting a connected subset of the authors. The associated graph signals were then used to estimate the graph through the considered methods.
Schoo Fl The dataset contains the temporal network of contacts between students in high school in Marseilles, France. In real-world social network analysis, common network characteristics such as homophily can lead to negative outcomes across gender in both social and academic settings [70]. Hence, both the School network and the Friendship network described below require scrutiny with respect to fairness, where gender is a critical consideration. The data includes the interactions of students from three classes over four days in December 2011. We used the available contact data to construct ground truth graph, where nodes represent students and edges represent all interactions between them. We
hhtpp://grouplles.org//
e hhtps://dl.ammmorr/
23

---

Error
Bias
10
10
Sparsity peualty waight
10-4
0.8
Spursity peuilty weight
10
0.8
0.6
0.6
10"2
10
0.4
0.4
10"
10
10
10-44
10"1
10
10
10
10P
10'
(a) Bias penalty weight jos
(b) Blas penalty weight
Figure 4: Performance in terms of error and bias for estimating fair precision matrix. (a) Error as parameters μl and μ22 vary. (b) Bias as parameters μl and #2 vary.
generated the signals by grouping the interactions into sets of four. Gender considered as sensitive attribute for each node.
Friendshig [1] This dataset corresponds to the contacts and friendship relations between students in nine classes at a high school Marseilles, France, over five days in December 2013. Following the same procedure as with the School dataset, we used the available contact data to generate the ground truth graph, where nodes represent students and edges represent all interactions between them. The graph signals were generated by grouping the interactions into sets of four, and gender was considered the sensitive attribute.
We compare the performance of proposed Fair GLASSO approach with the following baselines:
Baselines.
GL: The celebrated graphical lasso algorithm from 26 constitutes workhorse alternative to estimate the topology of the graph encoded in precision matrices. However, ignores the sensitive attributes of the nodes, it is prone to include biases existing in the true graph. RWGL: a naive fair alternative to graphical lasso where several edges are randomly rewired after estimating the precision matrix with GL. Since the rewiring process is independent of the sensitive attributes nodes, will render fairer estimate, but the random perturbation may yield highly inaccurate estimates. Methods denoted "RWGL-N" for some positive integer N represents RWGL with N edges rewired.
FST: fair alternative for learning the graph from stationary observations while mitigating biases in the topology via a group-wise bias penalty [18] 36 Different from graphical lasso, stationary methods assume that the covariance of the observed data is polynomial of matrix encoding the graph topology. This more lenient assumption typically comes at the expense of requiring a larger number of observations.
NEST: a variant of FST that estimates the graph topology from stationary observations including node-wise regularization to promote fairness 15 [8
Moreover, note that the notation "FGL-X" for some number X denotes FGL with μl = X, and this similarly holds for "NFGL-X".
Performance metrics. To measure the error our estimated precision matrices O" we apply the following normalized squared Frobenius enror
O | (0')=l
O
1 |
(69)
for true precision matrix Og. When such a true matrix O is unavailable, we instead apply the left- hand side of K from Corollary using the sample covariance matrix Σ estimated from observations.
To measure the bias in given precision matrix +* for nodal group memberships Z, observe that H and Hnode compute average differences edge weights within and across groups, whether

---

Error
Bias
10
10
Sparsity peualty waight
10-4
0.8
Spursity penilty weight jr1
10
0.8
0.6
0.6
10"2
10
0.4
0.4
10"
10
10
10-44
10"1
10
10a
10
10'
(c) Bias penaliy weight jos
(d) Bias penalty weight
Figure 5: Performance in terms of error and bias for estimating an unfair precision matrix. (a) Error as parameters Pl and #2 vary. (b) Bias as parameters μl and #2 vary.
group-wisc wise or wise. Thus, for our practical bias metric we normalize by edge weight to obtain
2 (T))")
(70)
that is, we take the square root of H()), which acts as squared &2 norm across distinct group pairs, and we divide by the average edge weight for unordered variable pairs.
The group-wise modularity presented in Figure I is defined in [19 that is,
(()) Σ 1 1
2
1
(71)
2s
2s
where denotes the number of nonzero entries in O To estimate partial correlation in Figure [ we apply graphical lasso without bias penalty, and entries of the resultant precision matrix denote estimates of partial correlation for every pair of variables.
Hardware details. The experiments are run on a computer with AMD Ryzen Threadripper 3970X 32-Core Processor, two Nvidia Titan RTX GPU, and 188GB of RAM.
H Additional Experiments
In this section, we provide additional simulations to demonstrate Fair GLASSO behavior under hyperparameter tuning and violation of assumptions. Figures 4 and of the attached document present Fair GLASSO performance as hyperparameters μ4 and μl2 vary when estimating fair or unfair precision matrix, respectively. Observe that when the true precision matrix is unfair, increasing H2 encourages a fairer estimate and thus increases the error. Moreover, smaller values μ22 yield greater bias for the unfair setting in Figure 2 than the fair setting in Figure 4 While larger μ2 decreases the bias both settings, the effect greater in Figure 5 for true precision matrix that is unfair.
Moreover, we provide additional simulations in Figure 6 where the precision matrix varies in sparsity (AS1), the true precision matrix is rank-deficient (AS2), and the group sizes vary (AS4). Figure O shows the classical graphical lasso result, where as the precision matrix grows denser, estimation error suffers, particularly when the sparsity penalty weight μn is larger. In Figure 6p, we demonstrate the effects of rankness on estimation performance. Indeed, the use of e permits low-rank estimates, and we observe relatively robust estimation error for different values of Finally, Figure [ shows that as the ratio between two groups becomes small, that is, the precision matrix becomes unfair due to imbalanced groups, error increases, particularly for larger u22
I Limitations and Future Work
This work focuses on group fairness via minimizing DP gap for Gaussian graphical models. While proposed definition of DP for graphical models does not require Gaussianity, the theoretical
25

---

0.00
0.00
0.04
0.3
Euoor
Tinut
0.03
0.1
0.02
0.3
10
10
10
(a) Edge probubility
(h) Amara
(c) Ratio of minority group
Figure 6: Performance in terms of the Frohenius eroor as different assumptions are violated. (a) Error true precision matrix becomes denser. (b) Error eigenvalues of true precision matrix grow close to O. (c) Error as group sizes become increasingly imbalanced.
results and optimization algorithm require assuming both Gaussian random variables and use of our proposed metrics. Interesting and critical extensions of this work include more general graphical models and other ideas of fairness. Consider for instance the following adaptation of equalized odds (EO)
i [ Zio 1, Jio = I [olli Zio 1, Z,. Va, E [g],
(72)
where @ denotes estimate of the true precision Op and Z is the group membership indicator matrix. The comparison fairness metrics for graphs warrants separate investigation since many fairness metrics in machine learning have not yet been adapted to the graph setting. Such analysis of fairness metrics ought to applied to tasks beyond graph learning and is thus out of scope of this paper. Moreover, while considered discrete sensitive attributes, also aim to promote equitable treatment for continuous sensitive traits.
Regarding the implementation of Fair GLASSO, Algoritm [ can handle any function where the smooth and non-smooth components are separable. principle, this includes non-convex functions, but the convergence result in Theorem 2 requires the smooth components to be strongly convex. Weaker results exist for convex functions (44] but no convergence guarantees are available for non-convex functions. In addition, Section 4.2 demonstrates the estimation of graphs with up to 1000 nodes. However, the computational complexity scales more than linearly with the number of optimization variables, rendering approach potentially unsuitable for graphs with millions of nodes. Nonetheless, existing works can efficiently estimate very large graphical models, potentially under additional assumptions [71.73]. We combine these approaches with our proposed fairness metrics, although we may lose our guarantee of convergence Theorem
Additional future directions include consideration of more general families of graphs. While we consider the underexplored case of signed, weighted graphs for fairness, our work is specific to graphical models encoding conditional dependence. We aim to consider more general interpretations of graphs with real-valued edges, including the novel extension to directed graphs.
26

---

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: The abstract and introduction claim that we make two contributions: we define fairness for graphical models, and we propose fair GGM estimation using proposed bias metrics. The former is provided in Section 2 and the latter in Section S
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or 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 clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: In Appendix L. detail limitations of approach based on the explicit assumptions made in the paper. Additionally, for future work we refer to the broader context of fairess and graphs point out areas outside the scope of this work.
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 encouraged to create 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 (e.g.. independence assumptions, noiseless settings, model well-specification, 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 on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should 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 is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren'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 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 a complete (and correct) proof?
Answer: [Yes]
Justification: Each theorem and derivation both in the body of the paper and in the appendix include the required assumptions and a reference to its associated proof the appendix. In
particular, Theorem I and Corollary [ iin Section 3.2 have proofs in Appendices B and
27

---

respectively, while Theorem in Section 3.3 is proven in Appendix The reference for LemmaTiis provided for its associated details and proof [67] while and their associated proofs are provided in Appendices D and respectively. The formal assumptions to AS that are needed for Theorem I and Corollary stated immediately preceding the theoretical results, while the remaining theoretical results have simpler assumptions provided the statement of the result. 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 proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, 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 be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes]
Justification: The body of the paper includes a brief description of our experimental settings in Section 4 and an in-detail description is included in Appendix G Moreover, the code, which is included in the submission for completeness, will be made available on GitHub the draft is accepted.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS 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) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to 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 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 (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code
28

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: In the supplementary material we provide the code for the experiments shown in this paper. We also share links to all publicly availably datasets in Appendix [G] The remaining datasets are synthetic, and detailed descriptions of how they are generated are provided in Appendix G
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (nttps://nips.cm
public/ www.oooaaaisssioooooooooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not 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 run reproduce the results. See the NeurlPS code and data submission guidelines (https
/pipss.cc/publlc////cccc guides/ddeeeee (wooeeuumissseeeoo ssiocoliccy for more details.
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 supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: 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?
Answer: [Yes]
Justification: Hyperparameters for optimization methods either chosen showcase specific scenarios as in Sections 4.2 and 4.4 or chosen via classical hyperparameter tuning methods as stated in Appendix G Remaining experimental details are in 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 a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or 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: [No]
Justification: Our experiments in Section 4 consist of synthetic observations in Sec- tions 4.1 4.2, and [.3). The results of the synthetic simulations are averaged over 50 trials: however, we observed low variance in the measured performances across 50 indepen- dent realizations, thus we do not provide error bars. The experiments in Section (.4 apply real networks, and we use all available signals, so variance cannot be measured, thus again need not provide statistical significance test for these results. Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
29

---

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 the standard error of the mean.
It is OK to report 1-sigma error bars, but 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 out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 8, Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: We provide at the end of Appendix G summary of the compute resources used for the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or 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 in the paper (c.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
NeurIPS Code of Ethics
Answer: [Yes]
Justification: While simulations in Section iinooliiivvvvee involve information of individuals via social network analysis, these datasets anonymized. The datasets, listed in detail in Appendix G are publicly available, and we do not provide any new data in this work that might be at risk of harmful consequences. Moreover, rather than being risk of unsafe usage, our method is designed to promote improvement in societal outcomes. Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS 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).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Following Section 5 we provide a discussion on the broader impacts of this work, which aims for improved societal outcomes.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses
(c.g., disinformation, generating fake profiles, surveillance), fairness considerations
30

---

(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 a 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
unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: We do not provide data or models with high risk of misuse.
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 is challenging. and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: 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?
Answer: [Yes]
Justification: All methods in Section with which we compare include the reference the original paper. Moreover, all real-world datasets used are publicly available and referenced appropriately, and links to these are provided in Appendix G
Guidelines:
The answer NA means that the paper does not use 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 a URL.
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, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out the asset's 's creators.
13. New Assets
31

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The code for both our method and our experiment from Section 4 are provided in the supplementary material. If this manuscript is accepted, we will release the code on GitHub for public use.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the datasettccodemmodl 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 details about compensation (if any)?
Answer: [NA]
Justification: We do not perform research using human subjects involving crowdsoureing.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Including this information 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 the main paper.
According to 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: We do not perform research using human subjects involving crowdsourcing.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
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 guidelines for their institution.
NeurlPS Code of Ethics and the
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
32


Reviews:
[{"review_id": "KxFUXnQK6k", "reviewer": "Reviewer_pQPd", "summary": "The paper introduces Fair GLASSO, a method for estimating Gaussian graphical models (GGMs) that addresses biases in data with respect to sensitive nodal attributes. The authors propose two bias metrics to promote fairness in statistical similarities across different groups, leading to the development of Fair GLASSO, a regularized graphical lasso approach. The paper also presents a proximal gradient algorithm for efficient estimation. Theoretical analysis shows the tradeoff between fairness and accuracy, and empirical results validate the effectiveness of the proposed method on both synthetic and real-world data.", "questions": "1. How sensitive is the method to the choice of hyperparameters $\\mu_1$ and $\\mu_2$?\n2. How would the approach extend to non-Gaussian graphical models?\n3. How you considered other fairness metrics beyond demographic parity?\n4. How does the computational complexity scale for very large graphs (e.g. millions of nodes)?", "limitations": "1. Only applicable to Gaussian graphical models.\n2. Focuses solely on group fairness via demographic parity.\n3. May not generalize well to more general graph structures.\n4. Theoretical guarantees assume specific conditions on the true precision matrix and group sizes.\n5. Limited exploration of the trade-offs between fairness and accuracy across different scenarios.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Novel contribution in defining fairness for graphical models and proposing methods to estimate fair GGMs.\n2. Thorough theoretical analysis including error bounds and convergence guarantees.\n3. Comprehensive empirical evaluation on both synthetic and real-world datasets.\n4. Proposed method can improve both fairness and accuracy in certain scenarios, especially when the underlying graph is fair but the data is biased.\n5. Clear explanations and intuitive visualizations of concepts and results.", "weaknesses": "1. This work is limited to Gaussian graphical models and may not be able to generalize to other types of graphical models such as ising model or covariance model.\n2. The fairness focus is mainly focusing on demographic parity and this may not be the optimal in relality. It would be better to explore other fairness definitions even though the authors claim that other definitions of group fairness can be similarly adapted.\n3. Some of the real-world datasets use synthetic signals, which may limit the real-world applicability of those specific results.\n4. The method introduces additional hyperparameters such as $\\mu_1$ and $\\mu_2$ that need to be tuned.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Rebuttal for pQPd:\n\nWe are grateful for your positive review and clear questions.\nIndeed, your review helps us clarify the utility of our approach beyond conceptual discussions.\nWe are glad to hear that you find our work novel, thorough, and comprehensive.\n\n> **Answer to Question 1.** \n\nThank you for your question.\nIndeed, as with many graphical lasso modifications, we require selection of appropriate weights for additional penalties. \nFigures 1 and 2 of the attached document present Fair GLASSO performance as hyperparameters $\\\\mu_1$ and $\\\\mu_2$ vary when estimating a fair or unfair precision matrix, respectively.\nObserve that when the true precision matrix is unfair, increasing $\\\\mu_2$ encourages a fairer estimate and thus increases the error.\nMoreover, smaller values of $\\\\mu_2$ yield greater bias for the unfair setting in Figure 2 than the fair setting in Figure 1.\nWhile a larger $\\\\mu_2$ decreases the bias in both settings, the effect is greater in Figure 2 for a true precision matrix that is unfair.\nAs hyperparameter tuning is a highly practical consideration, we will add these results to the final version if accepted.\n\n> **Answer to Question 2.** \n\nYour question allows us to clarify the flexibility of our bias metrics for graphical model estimation.\nIndeed, Gaussianity is widely used for its ubiquity and appealing statistical properties, yielding copious theoretical guarantees that we exploit for our results.\nHowever, note that Gaussianity only dictates the loss to be minimized, thus any optimization-based graph learning approach is amenable to our fairness penalties. \nMoreover, our FISTA algorithm is still applicable under other distributions as long as the associated loss is convex and differentiable, such as the negative log-likelihood of the Ising model that you mentioned.\n\n> **Answer to Question 3.** \n\nYou raise an excellent point; notions of fairness may differ by application, thus consideration of other definitions is critical.\nSince fair graphical model estimation is a novel task, we follow the custom of existing graph fairness works that employ demographic parity (DP).\nHowever, the penalty for Fair GLASSO is flexible and allows for other bias metrics.\nMoreover, as long as the chosen fairness penalty is convex and differentiable, our convergent FISTA algorithm remains applicable.\nConsider for instance the following adaptation of equalized odds (EO),\n$$\n\\\\mathbb{P}[ \\\\Theta^*\\_{ij} \\~|\\~ [\\\\mathbf{\\\\Theta}\\_0]\\_{ij},Z\\_{ia}=1, Z\\_{ja}=1 ] = \n\\\\mathbb{P}[ \\\\Theta^*\\_{ij} \\~|\\~ [\\\\mathbf{\\\\Theta}\\_0]\\_{ij},Z\\_{ia}=1, Z\\_{jb}=1 ] ~\\\\forall a,b\\\\in[g],\n$$\nwhere $\\\\mathbf{\\\\Theta}^*$ denotes an estimate of the true precision matrix $\\\\mathbf{\\\\Theta}\\_0$, and $\\\\mathbf{Z}$ is the group membership indicator matrix. \nNote that graphical EO is conditioned on the true precision matrix.\nThus, we can measure biases in estimated precision matrices but not the true one.\nFor this reason, we emphasize DP for group fairness since a measure of bias in the true precision matrix is critical to our theoretical interpretation of the fairness-accuracy tradeoff.\n\n> **Answer to Question 4.** \n\nWhile we show estimation of graphs on the order of 1000 nodes, the complexity indeed scales more than linearly with the number of optimization variables, thus our approach may not be viable for millions of nodes. \nHowever, existing works can efficiently estimate very large graphical models, potentially under additional assumptions [A1,A2,A3].\nWe can combine these approaches with our proposed fairness metrics, although we may lose our guarantee of convergence.\n\n> **Answer to Weakness 3.** \n\nFinally, we wish to clarify a concern you expressed in Weakness 3.\nWe stress that Karate club is the only real network for which we generate synthetic graph signals; all remaining real-world datasets possess data that are not synthetically generated.\nIndeed, as you noted, we wish to demonstrate the viability of Fair GLASSO in realistic settings, such as social networks with non-Gaussian data. \n\nWe thank the reviewer for your questions. You pinpointed vital practical concerns that are crucial to address in order to continue exploring fair graph learning in realistic scenarios.", "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": "M528ABbIjP", "reviewer": "Reviewer_QDSi", "summary": "Traditional graphical models may reinforce existing biases present in the data. This paper introduces a novel approach to ensure that the learned graphical models are fair across different groups or demographics.", "questions": "-  How does the proposed method differ from the joint graphical lasso [R1, R3, R4, R5], which borrows strength across the groups  within graphical models that share certain characteristics, such as the locations or weights of nonzero edges? Specifically, under AS4 and since $Z$ is an indicator matrix, $H(\\Theta)$ and $H_{\\text{node}}(\\Theta)$ are identical to the fused penalty term widely used in the joint estimation of joint graphical models; see for example [R4]. If you run joint graphical lasso [R1, R3, R4, R5], do they give similar results to yours?\n- What is the difference from existing FISTA methods for graphical models; see for example [R2].  Can you clarify how the Hessian of $f$ in the FISTA section is positive definite? It would be good if you could clarify how the rate changes with the eigenvalue of $\\nabla^2 f$.\n-  What is the the key difference in bounding the trace difference, log-determinant difference, and sparsity penalties compared to Theorem 1 of [32] and existing joint estimation of graphical models [R1, R3, R4, R5]?\n-  Can you clarify what are samples and nodes for your dataset? For example, what is the data matrix $X$ for the friendship experiment?\n- Do these datasets resemble real-world applications of the proposed Gaussian graphical models, considering that i) they include a ground truth graph and ii) nodes of social networks have binary associated samples (e.g., 0/1 interactions between people)?\n\n\n\n\n\n**Additional References**\n\n- [R1] Pircalabelu, Eugen, and Gerda Claeskens. \"Community-based group graphical lasso.\" Journal of Machine Learning Research 21.64 (2020): 1-32.\n- [R2] Oh, Sang, Onkar Dalal, Kshitij Khare, and Bala Rajaratnam. \"Optimization methods for sparse pseudo-likelihood graphical model selection.\" Advances in Neural Information Processing Systems 27 (2014).\n- [R3] Guo, Jian, et al. \"Joint estimation of multiple graphical models.\" Biometrika 98.1 (2011): 1-15.\n-  [R4] Danaher, Patrick, Pei Wang, and Daniela M. Witten. \"The joint graphical lasso for inverse covariance estimation across multiple classes.\" Journal of the Royal Statistical Society Series B: Statistical Methodology 76.2 (2014): 373-397.\n- [R5] Ma, Jing, and George Michailidis. \"Joint structural estimation of multiple graphical models.\" Journal of Machine Learning Research 17.166 (2016): 1-48.", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The authors develop a penalty method that adds a fairness penalty to the GLASSO objective.\n- As the added penalty is smooth, the authors develop a FISTA-type method to solve the optimization problem with an $\\ell_1$ nonsmooth term. Objective includes Gaussian graphical model loss + fairness penalty term +  $\\ell_1$ penalty term.\n- The authors provide experiments on both real and synthetic datasets, demonstrating the efficacy of their methods. \n- The paper is generally well-written and has a good synthetic empirical investigation.", "weaknesses": "- My main concern is that the proposed fair graphical model is essentially a joint graphical model widely studied in the existing literature. Please see below (Questions) for further clarification.\n-  The proposed penalty functions are already studied in the existing graph fairness literature. Specifically, both fairness penalty functions $H(\\Theta)$ and $H_{\\text{node}}(\\Theta)$ are from [15, 18], except that the authors replaced $| \\cdot |$ with $( \\cdot )^2$; for example, please refer to Eqs (1) and (2) in [18].\n- Since $H (\\Theta)$ and $H_{\\text{node}}(\\Theta)$ are smooth functions, the authors apply FISTA-type methods for graphical models. As FISTA and its variants are already explored in graphical models and their theoretical analyses are already provided [R2], Algorithm 1 simply applies to the smooth $f$ and nonsmooth $\\ell_1$ term. Thus, the theoretical contribution of Theorem 2 is limited.\n-  Estimation guarantees in Theorem 1 follow from existing literature on graphical model estimation, except that the authors need to handle $H(\\Theta)$ and $H_{\\text{node}}(\\Theta)$ in the proof of Theorem 1. For example, the proof of trace difference, log-determinant difference, and sparsity penalties is identical to Theorem 1 of [32]. \n- In real experiments, the ground truth of the graph is used to generate the data, and then a fair graph is estimated. However, I am concerned that this might not be considered as real experiments since, in real scenarios, the precision matrix for graphical model estimation is indeed unavailable. In addition, it is not clear that these real datasets are suitable for Gaussian graphical models, as they should consist of binary numbers (e.g., interactions between people as nodes would be 0/1). This raises questions about the applicability of the method in real-world scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Rebuttal for QDSi:\n\nWe sincerely thank you for your review and your kind words.\nWe appreciate your insightful comments and how you link our approach to existing works.\n\n> **Answer to Question 1.** \n\nThank you for your interesting question. \nYour observation is key; similar to group lasso or joint graph inference methods, we optimize group-wise submatrices of the precision matrix, but our formulation differs subtly with important consequences for fairness.\n\nJoint graph inference methods such as [R1], [R4], and [R5] assume each graph lies on the same node set, where we may treat each submatrix of $\\\\mathbf{\\\\Theta}$ for every group pair as a different graph.\nOur topological fairness only requires that the support and signs of edges are balanced on average across all group pairs. \nHowever, joint graph inference yields similar sparsity patterns for all submatrices, which is far more restrictive than balancing edges in expectation.\nMoreover, the group lasso penalties in [R3], [R4], and [R5] can achieve fairness in support, but they ignore the signs of the edges, thus they cannot balance correlation biases.\nThus, existing group lasso or joint graph learning approaches are either too restrictive or do not consider both kinds of graphical model bias.\nIn contrast, our fairness metrics can balance structure in both sparsity patterns and signed edges.\n\n> **Answer to Question 2.** \n\nThe main differences between our approach and other graphical model FISTA algorithms lie in (i) the fairness penalty in the objective function; (ii) the constraints for positive semidefinite precision matrices; and (iii) the type of convergence analysis.\nWe first note that our Fair GLASSO algorithm and the work in [R2] have different objective functions and thus different gradient updates.\nMoreover, while [R2] solves an unconstrained optimization problem, we require projection onto the feasible set after soft-thresholding.\nOn top of this, we guarantee convergence of the optimization variable, which is stronger than guaranteeing convergence of the objective function, as is done for [R2] and classical FISTA algorithms.\n\nTo show that the Hessian of $f$ is positive semidefinite (PSD), here we supplement the proof of Theorem 2 (Appendix F).\nNote that $f$ can be split as $f = f\\_1(\\\\mathbf{\\\\Theta}) + R\\_H(\\\\mathbf{\\\\Theta})$, and recall that $\\\\mathbf{\\\\Theta}$ is PSD and $\\\\epsilon > 0$.\nThen, from (39), it follows that the Hessian of $f\\_1(\\\\mathbf{\\\\Theta})$ is PSD since it is given by the Kronecker product of two PSD matrices.\nNext, note that the terms $R\\_H(\\\\mathbf{\\\\Theta})$ promoting fairness are convex, so their Hessian is also PSD, rendering the Hessian of $f$ PSD.\n\nFinally, the convergence rate in Theorem 2 depends on the Lipschitz constant $L$ and the strong convexity constant $\\\\alpha$, respectively associated with the largest and smallest eigenvalue of the Hessian of $f$.\nThus, it follows that increasing the smallest eigenvalues or decreasing the largest eigenvalues of the Hessian will improve the rate of convergence, and the converse is also true.\n\nBased on the feedback provided, we will highlight these relevant distinctions in the revised manuscript.\n\n> **Answer to Question 3.** \n\nYou are correct that the proof is similar to that of the original result in [32]. \nSince our proof is not limited by space, we aim to provide a self-contained result with enumerated steps for clarity, which can increase accessibility for audiences outside of statistics.\nWe are also careful to identify the effects of bias mitigation.\nFor example, the trace and sparsity differences do adhere to the proof in [32].\nHowever, the log-determinant difference in (18) of our paper deviates slightly from the original due to the additional bias term in the right-hand side of equation (13) in our manuscript versus equation (8) in [32].\nMoreover, our goal differs from [R1], [R3], [R4], and [R5], which show the effects on error when graphical lasso is modified to improve performance, while we formalize the tradeoff between accurate estimation versus unbiased solutions.\n\n> **Answer to Question 4.** \n\nFor Karate club, School, Friendship, and Co-authorship, nodes represent individuals, while MovieLens nodes represent movies.\nRegarding samples, the Karate club dataset is the only one without real graph signals, so we generate synthetic Gaussian data given the ground truth network.\nMovieLens graph signals represent movie ratings.\nEdges in the Co-authorship network denote collaborations, and we use keyword frequencies as signals.\nFinally, for both the School and Friendship datasets, the edges represent pairwise student interactions over all time, and the graph signals are sums of interactions over windows of time, that is, the graph signals represent time-varying node degrees as interactions vary.\n\nDetailed descriptions of the real datasets can be found in the Appendix, and we will augment Table 3 to include the interpretation of nodes and signals.\n\n> **Answer to Question 5.** \n\nYour concern is warranted since real data simulations validate our approach in practical scenarios.\nSocial network analysis is a common application of graphical models, but often no ground truth graph exists.\nHowever, we must confirm the effectiveness of Fair GLASSO.\nThe Friendship and School datasets thus demonstrate our method for realistic applications, which we can verify with ground truth graphs.\n\nCritically, we emphasize that the Karate club dataset is the only real network for which we generate synthetic graph data.\nAll other real-world datasets are each accompanied by a set of real graph signals.\nFor example, the social networks possess real discrete graph signals, yet we still observe satisfactory performance in Table 2 of our paper.\nWe hope this assuages your concern about the realism of our simulations.\n\nWe sincerely thank you for your feedback, and we will refer to your thoughtful comments to clarify our method upon updating the manuscript.", "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": "frERwrUpn8", "reviewer": "Reviewer_V8H3", "summary": "The authors propose a method for estimating Gaussian graphical models that are fair. To do this, the methodology uses Fair GLASSO, a regularized loss for estimating the precision matrix of the GGM which is fair with respect to sensitive attributes. The authors also provide theoretical results regarding the asymptotic errors of the estimated precision matrix.", "questions": "See the weaknesses section", "limitations": "The authors should elaborate on the limitations of the proposed methodology a bit more.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Overall, the paper is well written. \n- The methodology developed is sound and supported by theoretical results.\n- The experimental results show that the derived method is effective in practice.", "weaknesses": "- Please define modularity and \"partial correlations within and across groups\" for completeness. \n- Theorem 1 provides asymptotic results in terms of p, but it would be more interesting to derive results which are asymptotic in the number of data points n. Usually, the number of nodes are fixed and the number of datapoints increases.  \n- It would be interesting for authors to investigate how the results change when the assumptions are violated. \n- Also, is n fixed even as p increases to infinity in the result above? In this case, won't the covariance matrix become uninvertible when p > n? \n- The results should also include a pareto frontier between error and bias when the regularization parameters vary (but p and n are fixed)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Rebuttal for V8H3:\n\nWe thank you for your thorough review and detailed questions. \nWe are grateful for your kind words regarding the strengths of our work.\n\n> **Answer to Weakness 1.** \n\nGroup-wise modularity is computed as in reference [19] of the paper, that is,\n$$\nQ(\\\\mathbf{\\\\Theta}) = \n\\\\sum\\_{a=1}^g \\\\frac{\\\\mathbf{z}\\_a^\\\\top \\\\mathbf{\\\\Theta}\\_{\\\\bar{\\\\mathcal{D}}} \\\\mathbf{z} }{2s} - \\\\sum\\_{a=1}^g \\\\left(\\\\frac{\\\\mathbf{z}\\_a^\\\\top \\\\mathbf{\\\\Theta}\\_{\\\\bar{\\\\mathcal{D}}} \\\\mathbf{z} }{2s}\\\\right)^2,\n$$\nwhere $s$ denotes the number of nonzero entries in $\\\\mathbf{\\\\Theta}$.\nTo estimate partial correlation, we apply graphical lasso without a bias penalty, and entries of the resultant precision matrix denote estimates of partial correlation for every pair of variables. \n\nWe thank you for your comment.\nWe agree that these definitions are necessary for completeness.\nWe will add more detailed versions of these definitions in the revised paper.\n\n> **Answer to Weakness 2.** \n\nYour point is well taken, and we clarify the meaning of the theoretical result.\nThe result in Theorem 1 holds with high probability as either $n$ or $p$ increase; it is the probability of the error bound holding that converges to 1 as $p$ increases to infinity. \nWe understand that this presentation appears vague.\nThanks to your question, we will state this fact more clearly in the final version if accepted.\n\n> **Answer to Weakness 3.** \n\nThank you for this comment. \nFor lack of space, we outline the effects of violating our assumptions here, but we will provide a comprehensive discussion in the updated paper if accepted.\nWe also provide empirical demonstrations of the assumptions on estimation performance in the attached document, described in the global response.\n\nObserve that since AS1 has no restrictions on permissible values of $s$, AS1 merely defines the number of edges in the true graphical model.\n\nAS2 and AS3 bound the eigenvalues of the true covariance matrix $\\\\mathbf{\\\\Sigma}_0$.\nIn realistic settings, these eigenvalues will have finite magnitudes as in AS3, but the covariance may indeed be rank deficient, violating AS2.   \nTheoretically, this affects the log-determinant bound in equation (18) of our paper, as we cannot finitely bound the difference above with the reciprocal of the smallest eigenvalue.\nHowever, in such a case, we may instead consider Theorem 1 with $\\\\epsilon > 0$.\nWe then obtain a similar error bound, albeit perturbed by the value of $\\\\epsilon$, that is, the magnitude of $\\\\epsilon$ increases with the number of zero-valued eigenvalues of $\\\\mathbf{\\\\Sigma}_0$.\n\nFinally, AS4 can be relaxed to require only that group sizes be asymptotically similar, so no group vanishes as $p\\\\rightarrow\\\\infty$.\nIf a group vanishes, then the error bound will contain persistent terms corresponding to average edge magnitudes of the remaining groups, which cannot be balanced in connection across all groups.\n\n> **Answer to Weakness 4.** \n\nAs in our response to your Question 2, we note that our theoretical results do not require that $n$ be fixed.\nMoreover, you are correct that with insufficient samples, the empirical covariance matrix may not be invertible.\nIndeed, a major advantage of graphical lasso is that it is suitable in a low sample regime.\nThe sparsity penalty implements prior assumptions of parsimonious entries in the precision matrix to supplement inadequate information in the sample covariance matrix.\n\n> **Answer to Weakness 5.** \n\nWe appreciate your valuable suggestion.\nWe propose the following approach to show conditions on parameters $\\\\mu_1$ and $\\\\mu_2$ to guarantee Pareto optimality of Fair GLASSO.\nSay that we assume that our Fair GLASSO estimate $\\\\mathbf{\\\\Theta}^*$ has error $\\\\|\\\\mathbf{\\\\Theta}^* - \\\\mathbf{\\\\Theta}_0\\\\|_F^2 = \\\\delta$ for some $\\\\delta > 0$. \nFor any feasible precision matrix $\\\\mathbf{\\\\Theta} \\\\in \\\\mathcal{M}$ such that $\\\\|\\\\mathbf{\\\\Theta} - \\\\mathbf{\\\\Theta}_0\\\\|_F^2 \\\\leq \\\\delta$, we wish to determine the selection of $\\\\mu_1$ and $\\\\mu_2$ that guarantees $H(\\\\mathbf{\\\\Theta}^*) < H(\\\\mathbf{\\\\Theta})$, that is, that we have a Pareto optimal estimate $\\\\mathbf{\\\\Theta}^*$.\nOur proposed approach is to exploit the optimality of $\\\\mathbf{\\\\Theta}^*$, which yields\n$$\n\\\\mu\\_2 \\\\left( H(\\\\mathbf{\\\\Theta}) - H(\\\\mathbf{\\\\Theta}^*) \\\\right) \\\\geq \\\\mathrm{tr}(\\\\hat{\\\\mathbf{\\\\Sigma}}(\\\\mathbf{\\\\Theta}^*-\\\\mathbf{\\\\Theta})) + \\\\log \\\\det \\\\mathbf{\\\\Theta} - \\\\log \\\\det \\\\mathbf{\\\\Theta}^* + \\\\mu\\_1 \\\\left( \\\\| \\\\mathbf{\\\\Theta}^*\\_{\\\\bar{\\\\mathcal{D}}} \\\\|\\_1 - \\\\| \\\\mathbf{\\\\Theta}\\_{\\\\bar{\\\\mathcal{D}}} \\\\|\\_1  \\\\right),\n$$\nfrom which we derive bounds on $\\\\mu_1$ and $\\\\mu_2$ to ensure that the right-hand side is positive. \nIf our paper is accepted, we will provide the full version of the above Pareto optimality result, as requested by the reviewer.\n\nWe appreciate your high standards regarding our paper.\nWe will indeed elaborate on the limitations of our proposed work, the intuition of which your questions have helped us to develop.", "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": "W7QEgGE0lq", "reviewer": "Reviewer_fwTq", "summary": "The article explores the issue of achieving fairness in Gaussian Graphical Models (GGMs), particularly in the presence of biased data. Such biases can lead to unfair behavior in the models. To address this issue, the authors propose two bias metrics aimed at achieving statistical similarity across groups with different sensitive attributes. Based on these metrics, the authors introduce a regularized graphical lasso method called Fair GLASSO, designed to obtain sparse Gaussian precision matrices with unbiased statistical dependencies across different groups. The authors also propose an efficient proximal gradient algorithm to obtain these estimates and analyze the tradeoff between fairness and accuracy.", "questions": "(1) Can the authors provide a detailed explanation for the choice of these two bias metrics? Specifically, how do these metrics capture fairness better than other potential metrics?\n(2) Can the authors provide a detailed breakdown of the computational complexity for each step of the Fair GLASSO algorithm?\n(3) How does the proposed Fair GLASSO method perform on non-Gaussian data? Have the authors considered extensions or modifications to handle such cases?\n(4) The method relies on certain assumptions (e.g., bounded spectrum, equal group sizes). How sensitive is the performance of Fair GLASSO to violations of these assumptions?\n(5) What specific evaluation metrics were used to compare the performance of Fair GLASSO with other methods? Are these metrics the most appropriate for assessing both fairness and accuracy?\n(6) Can the authors provide more details on the real-world datasets used, specifically the nature of the sensitive attributes and the relevance of fairness in those contexts?\n(7) The paper contains some unnumbered equations, such as those on page 23. Can the authors clarify the reasons for this and provide the necessary numbering for easier reference?", "limitations": "(1) Although the paper discusses the efficiency of the Fair GLASSO algorithm, a more detailed analysis or discussion of the impact of complexity on practical applications would be better. For example, discussing potential scalability issues with larger datasets or in real-time applications could be very helpful.\n(2) The paper relies on certain assumptions, such as bounded spectrum and equal group sizes. Including a sensitivity analysis for these assumptions would be beneficial.\n(3) The paper could provide more concrete examples or case studies demonstrating the application of Fair GLASSO in real-world scenarios, beyond synthetic and small-scale examples.\n(4) Discuss the ethical implications of using Fair GLASSO in these fields. Emphasize the importance of stakeholder engagement and continuous monitoring to ensure that the implementation does not inadvertently harm the groups it aims to protect.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "（1）The authors are the first to propose definitions of fairness and bias metrics applicable to graphical models.\n（2）Through theoretical analysis and experiments, the effectiveness of Fair GLASSO in mitigating bias while maintaining model accuracy is demonstrated.\n（3）The method is compared with various existing approaches, showcasing Fair GLASSO's advantages in reducing bias and improving accuracy", "weaknesses": "（1）The implementation of the algorithm relies on complex matrix operations, which may pose high computational costs in practical applications.\n（2）Although the experiments used multiple datasets, the variety and scale of these datasets are still limited, possibly not fully representing all practical application scenarios.\n（3）There are some formatting issues in the paper, such as unnumbered equations on page 23.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Rebuttal for fwTq:\n\nWe greatly appreciate your positive feedback along with your valuable questions and suggestions. \nWe hope that our responses below maintain your positive assessment.\n\n> **Answer to Question 1.** \n\nThank you for your question.\nFor graph-based works, the predominant choice of bias metric is demographic parity (DP).\nThus, we approach the nascent task of graphical model estimation with a familiar bias metric to verify our approach with established measurements.\nHowever, our formulation is suited to other bias metrics such as equalized odds (EO), defined in the global response.\nWhile both DP and EO are popular fairness definitions, we cannot compute EO for the true precision matrix since it is conditioned on the ground truth connections.\nAs the crux of our theoretical results relies on measuring the bias in the true precision matrix, we choose DP as our bias metric.\n\n> **Answer to Question 2.** \n\nWe present a brief analysis for bias metric $H\\_\\\\mathrm{node}(\\\\mathbf{\\\\Theta})$, but a similar analysis holds for other penalties such as $H(\\\\mathbf{\\\\Theta})$.\nThe first step of Algorithm 1 is a proximal gradient step.\nComputing the gradient requires an inverse $( \\\\mathbf{\\\\Theta} + \\\\epsilon \\\\mathbf{I} )^{-1}$ and product $\\\\mathbf{A} \\\\mathbf{\\\\Theta}\\_{\\\\bar{\\\\mathcal{D}}}$, both incurring $\\\\mathcal{O}(p^3)$ operations.\nThe gradient step and soft-thresholding enjoy entry-wise computations with complexities $\\\\mathcal{O}(p^2)$.\nThe projection step onto the set of positive semidefinite matrices involves an eigendecomposition of $\\\\dot{\\\\mathbf{\\\\Theta}}^{(k)}$ with complexity $\\\\mathcal{O}(p^3)$.\nFinally, the step size update $t^{(k)}$ only requires scalar operations, and the accelerated update of $\\\\check{\\\\mathbf{\\\\Theta}}^{(k+1)}$ involves $\\\\mathcal{O}(p^2)$ operations, so they can be neglected.\n\nIf accepted, we will include these additional details in the revised version of the manuscript to strengthen its clarity.\n\n> **Answer to Question 3.** \n\nIn Table 2 of our manuscript, we estimate real-world networks from real data, such as the discrete graph signals of the School and Friendship social networks.\nThus, we empirically observe satisfactory performance even when observations are non-Gaussian, as queried by the reviewer.\nHowever, you also ask an important question: can Fair GLASSO be extended to non-Gaussian graphical models?\nGaussianity specifies the loss in the objective of Fair GLASSO, but we may consider other distributions in the optimization problem, such as the Ising negative log-likelihood.\nSuch a substitution requires altering our theoretical results, and in future work we will explore the fairness-accuracy relationship for non-Gaussian distributions.\n\n> **Answer to Question 4.** \n\nWe thank you for this question.\nIf accepted, we will provide a detailed discussion on the assumptions for Fair GLASSO.\nHere, we share a brief summary.\n\nFirst, AS1 merely defines the cardinality of the support of the true precision matrix.\n\nFor the spectrum of the true covariance matrix $\\\\mathbf{\\\\Sigma}\\_0$, eigenvalues with finite magnitudes as in AS3 is reasonable for any practical setting.\nAS2 may be violated for a rank-deficient $\\\\mathbf{\\\\Sigma}\\_0$.\nHowever, letting $\\\\epsilon>0$ addresses both theoretical and implementation concerns, where $\\\\mathbf{\\\\Sigma}\\_0$ need not be positive definite for convergence or the error bound.\nAs would be expected, the error bound becomes perturbed based on the magnitude of $\\\\epsilon>0$.\n\nThe final assumption can be relaxed to require only that no group vanishes as $p\\\\rightarrow\\\\infty$.\nIf a group vanishes, then edges cannot achieve perfect balance across all pairs of groups, which will result in a lower bound on the second term of the error upper bound.\n\nMoreover, we present additional simulations in the attached document illustrating how the assumptions affect performance.\n\n> **Answer to Question 5.** \n\nOur metrics for error and bias are described more thoroughly in Appendix G. \nWe employ the normalized squared Frobenius error, a standard metric for network inference works.\nWe follow similar intuition for bias, where we normalize measurements to compare biases across networks without being affected by changes in graph size or edge weights across graphs.\n\n> **Answer to Question 6.** \n\nIn real-world social network analysis, common network characteristics such as homophily can lead to negative outcomes across gender in both social and academic settings [A4].\nHence, the School, Friendship, and Co-authorship networks require scrutiny with respect to fairness, where gender is a critical consideration.\nFor demonstrative purposes, we use publication type as the sensitive attribute for Co-authorship as an example of data with more than two groups.\nAdditionally, biases in recommendation systems can reproduce and even exacerbate existing harmful stereotypes [A5].\nThe MovieLens dataset, a common benchmark for fair graph machine learning, exemplifies our ability to form unbiased models from networks used for recommendation systems. \nIf our work is accepted, we will include this relevant discussion in the final version.\n\n> **Answer to Question 7.** \n\nThank you for asking about the reasons for our choice.\nWe followed a common approach of numbering equations to which we refer, which serves to provide lighter notation.\nHowever, we agree with the reviewer that numbering all equations may better facilitate the understanding of our results.\nIf the reviewer deems it necessary, we will gladly make this change upon acceptance of this work.\n\nWe also appreciate your valuable suggestion regarding further discussion of ethical implications, and we will augment our broader impact discussion if accepted.", "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:
# Global

We would like to thank the reviewers for their quality comments and perceptive questions about our work. 
Below we detail the main topics discussed both in the following responses and to be added to the revised paper should it be accepted.

We provide additional discussion of Fair GLASSO to clarify its flexibility and novelty.
Thanks to the questions by reviewer QDSi, we emphasize the novelty of our method and FISTA algorithm.
We also highlight the flexibility of Fair GLASSO; our choices of demographic parity and Gaussianity are convenient for our theoretical analysis but are flexible to alternatives, as inquired by reviewers pQPd and fwTq.
For example, we may instead measure bias in graphical models via Equality of Odds (EO), which we may define as
$$
\mathbb{P}[ \Theta^*\_{ij} \~|\~ [\mathbf{\Theta}\_0]\_{ij},Z\_{ia}=1, Z\_{ja}=1 ] = 
\mathbb{P}[ \Theta^*\_{ij} \~|\~ [\mathbf{\Theta}\_0]\_{ij},Z\_{ia}=1, Z\_{jb}=1 ] ~\forall a,b\in[g],
$$
where $\mathbf{\Theta}^*$ denotes an estimate of the true precision matrix $\mathbf{\Theta}_0$, and $\mathbf{Z}$ is the group membership indicator matrix. 

In the attached document, we provide additional simulations to demonstrate Fair GLASSO behavior under hyperparameter tuning and violation of assumptions.
Figures 1 and 2 of the attached document present Fair GLASSO performance as hyperparameters $\mu_1$ and $\mu_2$ vary when estimating a fair or unfair precision matrix, respectively.
Observe that when the true precision matrix is unfair, increasing $\mu_2$ encourages a fairer estimate and thus increases the error.
Moreover, smaller values of $\mu_2$ yield greater bias for the unfair setting in Figure 2 than the fair setting in Figure 1.
While a larger $\mu_2$ decreases the bias in both settings, the effect is greater in Figure 2 for a true precision matrix that is unfair.

We elaborate on the theoretical implications of violating the assumptions for Theorem 1, as requested by reviewers V8H3 and fwTq.
Moreover, we provide additional simulations in Figure 3 of the attached document where the precision matrix varies in sparsity (AS1), the true precision matrix is rank-deficient (AS2), and the group sizes vary (AS4).
Figure 3a shows the classical graphical lasso result, where as the precision matrix grows denser, estimation error suffers, particularly when the sparsity penalty weight $\mu_1$ is larger.
In Figure 3b, we demonstrate the effects of a low-rank ground truth precision matrix on estimation performance. 
Indeed, the use of $\epsilon>0$ permits low-rank estimates, and we observe relatively robust error for different values of $\epsilon$.
Finally, Figure 3c shows that as the ratio between two groups becomes small, that is, the precision matrix becomes unfair due to imbalanced groups, error increases as we impose fairness, particularly for larger $\mu_2$.

We again thank the reviewers for taking the time to provide thorough evaluations of our submission. 
We hope that you find our responses satisfactory.

References in Author Responses:
- [A1] C.-J. Hsieh, M. A. Sustik, I. S. Dhillon, P. K. Ravikumar, and R. Poldrack, "BIG & QUIC: Sparse Inverse Covariance Estimation for a Million Variables", in *Advances in Neural Information Processing Systems*, 2013. 
- [A2] T. Yao, M. Wang, and G. I. Allen, "Fast and Accurate Graph Learning for Huge Data via Minipatch Ensembles", *arXiv preprint arXiv:2110.12067*, 2021.
- [A3] X. Wang, J. Ying, and D. Palomar, "Learning Large-Scale $MTP_2$ Gaussian Graphical Models via Bridge-Block Decomposition", in *Advances in Neural Information Processing Systems*, 2023.
- [A4] C. Avin, Z. Lotker, Y. Nahum, and D. Peleg, "Modeling and Analysis of Glass Ceiling and Power Inequality in Bi-populated Societies", in *International Conference and School on Network Science*, 2017.
- [A5] A.-A. Stoica, C. Riederer, and A. Chaintreau, "Algorithmic Glass Ceiling in Social Networks", in *International World Wide Web Conference*, 2018.

Meta-review: The paper introduces Fair GLASSO, a method for estimating Gaussian graphical models (GGMs) that ensures fairness with respect to sensitive attributes in the data. The authors propose two bias metrics to promote fairness and develop a regularized graphical lasso approach, supported by theoretical analysis. The paper also presents an efficient proximal gradient algorithm for estimation and validates the method through empirical experiments on both synthetic and real-world datasets.

Pros:

Novel Contribution: Introduces fairness concepts in the context of graphical models, which is a relatively unexplored area.
Theoretical Rigor: Provides detailed theoretical analysis, including error bounds and convergence guarantees.
Empirical Validation: Comprehensive experiments on both synthetic and real-world datasets demonstrate the effectiveness of the method.
Clear Presentation: The paper is generally well-written and explains complex concepts in an accessible manner.

Cons:
Limited Novelty: The fairness penalty functions and the FISTA algorithm are extensions of existing methods, limiting the novelty.
Limited Generalization: The method is currently limited to Gaussian graphical models and may not generalize well to other types of graphical models.
Experimental Limitations: The experiments are conducted on a limited set of datasets, which may not fully represent the diversity of real-world scenarios.
Complexity Concerns: The computational complexity of the method may pose challenges in practical applications, particularly for large-scale problems.

Things that should be addressed in the final version of the paper:

Novelty: Concerns remain about the originality of the proposed fairness metrics and the incremental nature of the technical contributions.

Generalization and Flexibility: While the authors addressed concerns regarding the method’s generalizability to non-Gaussian models, the approach is still heavily reliant on specific assumptions and may not be flexible enough for broader applications.

Experimental Validation: Despite additional experiments provided in the rebuttal, there is still a need for more diverse and large-scale datasets to thoroughly validate the method.

The paper offers a meaningful contribution to the field of fair graphical model estimation, supported by solid theoretical work and empirical validation. The remaining concerns can be addressed by authors when preparing a camera ready submission.
Decision: Accept (poster)