Fairness-Aware Estimation of Graphical Models

Question 2: In Algorithm 1, the first step is to initialize local graph estimates for all groups. When the number of groups is large, the sample sizes of certain groups could become small, which may affect the accuracy of the local graph estimates. How will the accuracy of the local graph estimates affect the global graph estimate?

Response: Thank you for your insightful question. In Algorithm 1, we initialize local graph estimates for all groups, and we recognize that small sample sizes in certain groups could impact the accuracy of these local estimates. The accuracy of local graph estimates is indeed crucial, as these estimates form the foundation for the global graph estimate. When local estimates are based on small sample sizes, they may be less reliable, potentially introducing bias or variance that can propagate to the global graph estimate.

One possibility for handling the challenges of limited samples in certain subgroups is the bilevel optimization approach [SXC2022]. In this framework, the lower-level optimization learns subgroup-specific local graph matrices using the limited data available, guided by a fair model informed by the overall dataset. This approach is theoretically sound and empirically validated to improve fairness without sacrificing accuracy, even when some subgroups have limited samples. However, the bilevel formulation for graph learning can be computationally expensive as it requires hyper-gradient computations. Further, this approach requires novel estimation and convergence analysis. Therefore, we will add this as a future direction.

Weakness 1: The optimality analysis requires the convexity of the loss function, and it remains unclear how the performance would be affected if the loss function were non-convex, which is common in machine learning. For example, if we use an encoding network to convert the data X into a representation space and compute the loss in the representation space, then the loss function would be non-convex.

Response: We appreciate the reviewer’s insightful comment. We completely agree that one limitation of our nonsmooth multi-objective optimization work is the reliance on the convexity of the loss function. However, many existing theoretical results and estimation algorithms for graphical models using single-objective optimization also rely on the convexity of objectives to estimate graphical models. For example, please refer to QUIC[HSD2014], SQUIC[BS2016], PISTA[STY2023], GISTA[GRR2012], OBN[OON2012], and ALM[SG2010]

On the other hand, we agree that converting the data $X$ into a representation space, such as using $UU^T$ in the objective or constraints, which can be used for clustering or computing the loss in the representation space, could make the problem nonconvex [KYC2020]. However, we know that standard proximal gradient methods for nonconvex optimization or their alternative variants for nonconvex alternating optimization (e.g., for $U$ and graph matrix $\Theta$) can still be applied [BST2013]. Hence, the proximal multi-objective method developed for GMs in this paper can be extended to nonconvex graph optimization. This may require new proof techniques and estimations, which can be considered for future work. We will discuss this in the future work section.

Weakness 2: There is just one baseline used in the experiments, which was published in 2012. It could strengthen the experiment section if modern GM estimation methods are used as baselines.

Response: Thank you for your feedback. We appreciate your suggestion to include more modern GM estimation methods as baselines. To address this, we have conducted additional experiments using several state-of-the-art GLasso algorithms. Specifically, we have applied different algorithms, including PISTA[STY2023], GISTA[GRR2012], and OBN[OON2012], to GLasso on synthetic data to demonstrate the robustness and effectiveness of our framework beyond ISTA.

ISTA was initially chosen as a baseline due to its simplicity and widespread use in sparse inverse covariance estimation. This provided a strong reference point for evaluating our method’s performance. However, recognizing the importance of a comprehensive evaluation, we have now compared our framework against more advanced baselines.

The results, detailed in the revised version of our paper and the attached one-page PDF file, show that our proposed framework consistently outperforms these modern baselines in terms of enhancing fairness while maintaining competitive performance. This comprehensive evaluation underscores the advantages of our approach across various scenarios.

Question 1: Can the proposed method be applied to the estimation of directed graphs, like causal graphs?

Thank you for your insightful question. While our proposed method is primarily designed for undirected graphical models like Gaussian Graphical Models and Ising Models, the principles of our fairness-aware optimization framework could potentially be adapted for directed graphs, such as causal graphs. Unlike many fair supervised methods[GKK2019,JCM2022,PLL2022], our method does not use label information, and unlike previous methods for fair clustering or community detection[CKL2017,BCF2019], our method does not use node attributes. Our fairness metric preliminarily works with the disparity of global and local losses, i.e., using group-specific and global data to construct the objective. Hence, it is not specific graph-dependent as a fairness metric. Although the objective function differs for various graphical models, our new fairness notion (pairwise graph disparity error) remains the same. Although our current work focuses on undirected graphs, we believe that with appropriate adjustments, our framework could be extended to handle directed graphs, ensuring fairness without disrupting causal dependencies. This presents a promising area for future research. Thank you for your constructive question, which has helped us consider the broader applicability of our method.

To our knowledge, There are indeed a few works on fair graphical models that significantly differ from this work. The most relevant works to this study are [68, ZW2023, NRB2024, ZW2024]. Specifically, [68] initiated the learning of fair GMs using an $\ell_1$-regularized pseudo-likelihood method for joint GMs estimation and fair community detection. [ZW2023, ZW2024] proposed a fair spectral clustering model that integrates graph construction, fair spectral embedding, and discretization into a single objective function. Unlike these models, which assume community structures, our study formulates fair GMs without such assumptions. Concurrently with this work, [NRB2024] proposed a regularization method for mitigating subpopulation bias for fair network topology inference. To our knowledge, this methodology significantly differs from ours, as we focus on developing three classes of fair GMs (Gaussian, Covariance, and Ising models) for imbalanced groups without node attributes, aiming to automatically ensure fairness through non-smooth multi-objective optimization.

Weakness 3: Moreover, the paper ... predefined assumptions in the theoretical section.

Response: Thank you for your comment.

Firstly, the method in the referenced paper, ``Fair Community Detection and Structure Learning in Heterogeneous Graphical Models,'' is specifically designed for scenarios where there are inherent community or cluster structures in the data. If the clustering were based on the number of observations (N) instead of the number of variables (P), setting the number of clusters to one would essentially imply that there is only one community. This would not address the issue of fairness as intended by the method. In such a scenario, the concept of fair community detection loses its relevance since there would be no differentiation between groups to balance fairness. Hence, the method is not applicable when the number of clusters is equal to one.

Secondly, the method assumes that the nodes are clusterable. However, in our case, we do not make such assumptions, as many applications involve graphs with nested structures rather than distinct communities. For example, consider a sparse graph with hub nodes [TML2014] or star graphs. In this setting, the nodes may not form distinct communities, challenging the method's assumptions.

Finally, we do not assume the existence of attributes on nodes, whereas the referenced method does. This can restrict applications such as gene network analysis (Section 5.1), where nodes could be genes that do not have attributes. In brain amyloid/tau accumulation network analysis (Section 5.2), nodes are regions of interest (ROIs) that do not have sensitive attributes. The requirement for nodes to have attributes limits the method's applicability in these contexts.

We will clarify these distinctions in the related work section.

Weakness 4: In Section 4.8, ... in the subsequent sections.

Response: We appreciate the reviewer’s feedback regarding the trade-off analysis in Section 4.8. We acknowledge that the discussion on the shortcomings in runtime and potential future work was insufficiently detailed. We have expanded our discussion to include specific strategies to address these issues and outline potential future work.

One promising direction to accelerate the graphical model part of our algorithm is the adoption of faster optimization techniques. Specifically, the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) has shown significant improvements in optimization efficiency in various contexts. By integrating FISTA into our framework, we can achieve considerable runtime reductions without compromising the accuracy and convergence properties of our models, as presented in Table 2 in the attached one-page PDF file.

Another factor impacting runtime is the number of groups considered. Reducing the number of groups or selecting representative sample groups can effectively manage computational complexity. One potential approach is the method proposed by [SXC2022], which suggests selecting a sample of groups randomly in each iteration of the optimization process to balance computational efficiency and model accuracy. By implementing a strategic sampling of groups, we can maintain the robustness and fairness of our models while significantly reducing the runtime. This approach will be explored in future work to optimize the balance between computational demands and model performance.

Weakness 1: In the introduction and related works section, the paper does not provide complete information about GMs. Additionally, the paper does not clearly explain why it focuses on only three types of GMs instead of providing a general framework. The author needs to clearly highlight any difficulties encountered when applying this framework to each type of model.

Limitation 1: Firstly, the introduction lacks a comprehensive overview of current GMs and does not explain why the focus is on only three types of GMs rather than GMs in general.

Limitation 3: Lastly, the implementation of different GMs requires distinct theorems with specific assumptions, which could limit the development and extension of the framework.

Response: We appreciate the reviewer’s comments and would like to clarify our approach further. Our paper focuses on three types of GMs: Gaussian Graphical Models, Gaussian Covariance Graph Models, and Binary Ising Graphical Models. These models were chosen because they represent a diverse set of widely used GMs with distinct characteristics and applications. Each type poses unique challenges in terms of estimation and fairness, making them suitable for demonstrating the effectiveness and versatility of our proposed framework.

Importance of Each Graph Model: Each of the three graph models (GLasso, sparse covariance estimation, and binary Ising model) addressed in our paper is of significant interest to the research community. Each of these models has been extensively studied and typically warrants dedicated papers. Here are a few examples to illustrate their importance:

GLasso:

• Pavlenko, Tatjana, Anders Björkström, and Annika Tillander. "Covariance structure approximation via gLasso in high-dimensional supervised classification." Journal of Applied Statistics 39.8 (2012): 1643-1666.

• Mazumder, Rahul, and Trevor Hastie. "The graphical lasso: New insights and alternatives." Electronic journal of statistics 6 (2012): 2125.

• Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. "Sparse inverse covariance estimation with the graphical lasso." Biostatistics 9.3 (2008): 432-441.

• Witten, Daniela M., Jerome H. Friedman, and Noah Simon. "New insights and faster computations for the graphical lasso." Journal of Computational and Graphical Statistics 20.4 (2011): 892-900.

Sparse Covariance Estimation:

• Bien, Jacob, and Robert J. Tibshirani. "Sparse estimation of a covariance matrix." Biometrika 98.4 (2011): 807-820.

• Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. "Sparse inverse covariance estimation with the graphical lasso." Biostatistics 9.3 (2008): 432-441.

• Bickel, Peter J., and Elizaveta Levina. "Regularized estimation of large covariance matrices." (2008): 199-227.

• Cai, Tony, Weidong Liu, and Xi Luo. "A constrained ℓ 1 minimization approach to sparse precision matrix estimation." Journal of the American Statistical Association 106.494 (2011): 594-607.

Binary Ising Model:

• Ravikumar, Pradeep, Martin J. Wainwright, and John D. Lafferty. "High-dimensional Ising model selection using ℓ 1-regularized logistic regression." (2010): 1287-1319.

• Anandkumar, Animashree, et al. "High-dimensional structure estimation in Ising models: Local separation criterion." The Annals of Statistics (2012): 1346-1375.

General Framework Applicability: While our algorithm is indeed a general framework applicable to various types of graphs, we chose to focus on GLasso, sparse covariance estimation, and binary Ising models to provide detailed parameters and convergence guarantees specific to each model. These models were selected to demonstrate the versatility and robustness of our framework. A more general assumption might dilute these specific details and potentially miss important information relevant to each individual model. By concentrating on these three, we ensure a comprehensive analysis, which includes specific parameter tuning and convergence properties, thus providing a stronger and more practical contribution to the field.

In summary, our paper’s focus on these three specific GMs is a deliberate choice to balance the depth and breadth of our contributions, ensuring detailed and practically relevant results. We believe this approach is beneficial for the community, as it provides clear and actionable insights for these widely studied models.

Weakness 2: In the second paragraph of Section 2 (Related Work on Fairness), the author does not discuss related works concerning fairness in GMs estimation. By focusing solely on fairness in unsupervised learning, the paper may limit readers' ability to gain a comprehensive understanding of the research field and the distinctiveness of the proposed method.

Limitation 2: Secondly, the discussion of related work on fairness in GM estimation is insufficient and needs clearer explanations.

Response: We appreciate your comments and agree that a more comprehensive discussion on fairness in graph model (GM) estimation would enhance the reader’s understanding. In our revised manuscript, we will include a dedicated paragraph to review the related works, specifically focusing on fairness in GM estimation.

Weakness 3: Limited baseline: The paper could benefit from more extensive comparisons with existing fairness-aware methods in graphical models other than ISTA (the only baseline used in Table 2). This would help to contextualize the performance and advantages of the proposed framework.

Question 3: It's mentioned that ISTA is used as baseline. What are other possible baselines? Why in particular choose ISTA as baseline?

Response: Thank you for your valuable feedback. In response to your concern, we have conducted additional experiments to apply our multi-objective optimization framework to several state-of-the-art GLasso algorithms. We specifically focused on synthetic data to showcase the robustness and effectiveness of our framework beyond the ISTA algorithm.

We initially chose ISTA as a baseline due to its simplicity and widespread use in sparse inverse covariance estimation, making it an ideal reference point. However, understanding the necessity for a more comprehensive evaluation, we have now included comparisons with advanced baselines such as PISTA[STY2023], GISTA[GRR2012], and OBN[OON2012].

Our additional experiments, detailed in the revised version of our paper, demonstrate that our framework consistently outperforms these advanced baselines in enhancing fairness while maintaining competitive performance. Specifically, all new baseline methods reached the optimal loss for GLasso. When applying our multi-objective optimization framework, Fair GLasso achieved comparable results and significantly reduced pairwise graph disparity error. This comprehensive evaluation underscores the advantages of our approach in various scenarios, reinforcing its robustness and effectiveness.

Limitation: The paper discuss the complexity limitation of the work but did not solve it.

Response: We appreciate the reviewer’s observation regarding the time-consuming nature of our learning algorithm. Given our use of a multi-objective optimization framework, it is expected that the process would be more time-intensive. Nonetheless, our primary goal remains to offer a simple yet effective framework for fair graph learning. We recognize the need to enhance the computational efficiency of our method and outline potential directions to achieve this.

Firstly, the time complexity is partly due to the local graph learning phase. This can be significantly accelerated by utilizing fast graphical model algorithms such as QUIC[HSD2014], SQUIC[BS2016], PISTA[STY2023], GISTA[GRR2012], OBN[OON2012], and ALM[SG2010]. Integrating these faster algorithms into the multi-objective optimization process can substantially improve the overall efficiency of our learning algorithm.

Secondly, the growing number of objectives in the multi-objective optimization solver can also increase time complexity. To address this, we propose randomly selecting a subset of objectives in each iteration. This approach can reduce the computational load while preserving the model's fairness and performance.

To support our discussion, we conducted additional experiments using GLasso. In the first experiment, we generated synthetic data, including two subgroups, as described in the appendix of our paper. We applied various optimization algorithms to both the local graph learning and multi-objective optimization processes. The detailed numerical results, presented in Table 2 of the attached one-page PDF file, show that all tested optimization algorithms for GLasso achieved optimal loss while maintaining fairness improvements. Notably, GISTA and OBN for GLasso, along with FISTA for multi-objective optimization, significantly enhanced learning efficiency.

In the second experiment, we generated a synthetic dataset with ten subgroups to validate our strategy for reducing time complexity. In each iteration of the multi-objective optimization, we randomly selected three objectives. The numerical results in Table 2 of the attached one-page PDF file indicate that this strategy effectively reduces runtime without substantially compromising model performance.

These findings underscore the potential of our proposed methods to improve the computational efficiency of the learning algorithm while maintaining fairness and performance. We appreciate the reviewer’s feedback and believe these enhancements will further strengthen our framework.

Weakness 1: Fairness metric: The choice and justification of fairness metrics used in the evaluation could be more thoroughly discussed. This would provide a clearer understanding of how fairness is quantified and the implications of these choices.

Question 1: Could you elaborate more on the choice of fairness metrics, disparity error, used in your evaluation? What might be the implications for using such metric compared to other metrics, like those stemming from counterfactual evaluation?

Response: We appreciate the reviewers’s feedback on the need for a more thorough discussion of the fairness metrics used in our evaluation. We understand that the choice and justification of fairness metrics are critical for providing a clear understanding of how fairness is quantified and the implications of these choices.

In our work, we introduced the concept of graph disparity error as the primary fairness metric. This metric measures the difference in loss between the global model $\Theta$ and the optimal local models $\Theta_1^*, \Theta_2^*, \ldots, \Theta_K^*$ for each subgroup. The rationale behind this choice is rooted in the unsupervised nature of our task. Unlike supervised learning, which can leverage labeled data to define fairness metrics such as demographic parity (DP)[JHF2022] or equalized odds (EO)[RBC2020], our unsupervised learning context lacks such labels. Therefore, we require a fairness metric that does not rely on label information.

The graph disparity error metric was chosen because it effectively captures the notion of fairness by ensuring that the model’s performance is balanced across different subgroups. By minimizing this error, we aim to ensure that no subgroup is disproportionately favored or disadvantaged, thereby promoting a more equitable model. Despite this, our proposed graph disparity error actually aligns with the goals of DP by promoting a balanced representation of all subgroups. The global graph obtained from our method represents a central integration of local graphs, ensuring that the influence of each subgroup is balanced. This inherent balance aligns with the core objective of DP without the use of labeled data.

In our revised version, we further include the following paragraph to improve the discussion of the fairness metrics:

“In this work, we employ graph disparity error as our primary fairness metric. This metric measures the difference in loss between the global model and the optimal local models for each subgroup. Our choice is motivated by the unsupervised nature of our task, which lacks labeled data typically required for metrics such as demographic parity or equalized odds. Graph disparity error provides a label-independent measure of fairness, ensuring balanced model performance across subgroups. By minimizing this error, we reduce bias introduced by the data distribution, promoting an equitable model where no subgroup is disproportionately favored or disadvantaged. This approach aligns with the core objectives of demographic parity, as our global graph integrates local graphs, balancing the influence of each subgroup. Thus, our metric effectively quantifies fairness in high-dimensional graphical models, providing a robust framework for fair graph learning.”

Weakness 2: Unconvincing experiment results: While the authors claim that the proposed method "approach enhances fairness without compromising performance" in line 306, Table 1 indicates that 6 out of 7 datasets experience lower F1 scores, suggesting worse performance.

Question 2: While the authors claim that the proposed method improves fairness without compromising performance, Table 1 indicates that 6 out of 7 datasets experience lower F1 scores, suggesting worse performance. Could you clarify this discrepancy and provide a more detailed interpretation of Table 1?

Response: We appreciate the reviewer’s comments on the experimental results and the interpretation of Table 1. We would like to clarify our claim that the proposed method enhances fairness without compromising performance.

Firstly, it is important to recognize the inherent trade-off in multi-objective optimization frameworks that balance fairness and accuracy. While our method prioritizes fairness, this may lead to a slight decrease in the $F_1$ score, as reflected in Table 1. However, these decreases are minimal and within acceptable ranges, indicating that the overall performance of the model remains robust. The marginal reductions in $F_1$ scores result from the necessary adjustments to ensure fair representation across all subgroups. We include this analysis in Section 4.8, Trade-Off Analysis.

To be more accurate, we would like to clarify our claim in our revised version as follows: “This approach enhances fairness without compromising performance significantly, validated by experiments on synthetic and real-world datasets.”

I thank the authors for providing additional results. I think the experiment sections looks stronger now and is willing to raise my score by 1.

Weakness 3: The authors employ multi-objective optimization, suggesting that the loss in GMs and pairwise graph disparity are at odds. However, many papers indicate that this is not always the case. For example, the paper "Is There a Trade-Off Between Fairness and Accuracy? A Perspective Using Mismatched Hypothesis Testing" by S. Dutta et al. (ICML 2020) discusses this. How do the authors justify their approach in light of such findings?

Response: We appreciate the reviewer's comment on the trade-off between fairness and accuracy. The paper by S. Dutta et al. (ICML 2020) argues that the observed trade-off may stem from the real-world application of biased datasets rather than an intrinsic limitation of the algorithms themselves. They emphasize the importance of considering ideal distributions when evaluating fairness and accuracy and highlight the potential of active data collection to improve fairness without compromising accuracy. In our work, we focus on the algorithm's fairness. Classical graphical models aim to achieve optimal loss for the given data distribution but may propagate and amplify existing biases. Our fairness-aware optimization framework aims to mitigate these biases systematically at the algorithmic level, independent of the data distribution.

While classical graphical models achieve optimal loss, they do not inherently address fairness concerns. Our multi-objective optimization framework explicitly incorporates a fairness criterion, balancing the trade-off between minimizing loss and reducing pairwise graph disparity. Multi-objective optimization is a promising approach for integrating fairness considerations into machine learning models. Prior works, such as [MBS2020], have formulated group fairness as a multi-objective optimization problem with separate objectives for each sensitive group’s risk. This strategy aligns closely with works like [PAG2021] and [MSG2021], which enhance fairness in classification. Further exploration by [PBD2022], and [KHF2018] demonstrates the effectiveness of multi-objective optimization in improving fairness in unsupervised PCA algorithms.

These efforts underscore the growing consensus on the potential of multi-objective optimization to address fairness issues in machine learning. On the other hand, existing solutions may not adequately address fairness in nonsmooth or high-dimensional settings, where our framework offers novel insights and solutions. To our knowledge, ours is the first nonsmooth multi-criteria method for fairness, applicable to other problems involving nonsmooth regularizations such as sparse fair PCA or fair supervised learning based on ERM with sparsity/norm-one regularization.

Limitation 1: The applicability for real problems

Response: Thank you for your comment. We have provided the real-world applications of our proposed method in Section 4 ( Experiment). Specifically, in Sections 4.4 and 4.5, we analyzed the application of the fair GLasso on the Gene Regulatory Network and the Brain Amyloid/Tau Accumulation Network. Section 4.6 explored the application of Fair CovGraph in Credit Dataset, which promotes a more equitable credit system. In addition, we demonstrated the application of the Fair binary Ising model on Music Recommendation Systems in Section 4.7. These real-world examples illustrate the practical applicability of our proposed method.

Limitation 3: The study is limited to Gaussian, Gaussian Covariance, and Binary Ising models.

Response: Thank you for your comment. Our paper focuses on three types of graphical models: Gaussian Graphical Models, Gaussian Covariance Graph Models, and Binary Ising Graphical Models. These models were chosen because they represent a diverse set of widely used GMs with distinct characteristics and applications. Indeed, each of these models is of significant interest to the research community and has been extensively studied. For example:

• GLasso: Widely used for sparse inverse covariance estimation, as demonstrated by Friedman et al. (2008) [FHT2008] and Witten et al. (2011)[WFS2011].

• Sparse Covariance Estimation: Important for large covariance matrix estimation, with notable contributions from Bickel and Levina (2008)[BL2008] and Cai et al. (2011)[CLL2011].

• Binary Ising Model: Crucial for high-dimensional discrete data, highlighted by the work of Ravikumar et al. (2010)[RWL2010].

While our algorithm is a general framework applicable to various types of graphs, we focused on GLasso, sparse covariance estimation, and binary Ising models to provide detailed parameters and convergence guarantees specific to each model. This focus ensures a comprehensive analysis, including specific parameter tuning and convergence properties, thus providing a stronger and more practical contribution to the field. Generalizing too broadly might dilute these specific details and overlook important model-specific insights.

In summary, our focus on these three specific GMs balances the depth and breadth of our contributions, ensuring detailed and practically relevant results. We believe this graphical model estimation approach is beneficial for the community, offering clear and actionable insights for these widely studied graphical models.

Weakness 4: The learning algorithm appears to be very time-consuming. Do the authors have any comments on this aspect of their method?

Question 1: Practical graphs and practical fairness problems have high K and P values. This will raise the computational complexity to the extent that it may question the applicability of the method. Do the authors have comment on this?

Question 2: What if the number of protected groups (like in the case of age) is high? How do the authors comment on these cases with regards to complexity analysis?

Limitation 2: It does not scale well

Response: We appreciate the reviewer’s observation regarding the time-consuming nature of our learning algorithm. Given the multi-objective optimization framework we employ, it is indeed expected to be more time-intensive. However, our primary goal is to provide an automatic (without any additional regularization or related hyperparameter tuning) and effective framework for fair graph learning. We acknowledge the importance of improving the computational efficiency of our method and outline potential future directions to address this concern.

Firstly, the time complexity partly arises from the local graph learning phase. This can be significantly accelerated using existing fast graphical model algorithms such as QUIC[HSD2014], SQUIC[BS2016], PISTA[STY2023], GISTA[GRR2012], OBN[OON2012], and ALM[SG2010]. Incorporating faster algorithms into the multi-objective optimization process can also enhance the overall efficiency of our learning algorithm.

Secondly, the increase in time complexity can also be attributed to the growing number of objectives in the multi-objective optimization solver. To mitigate this, we propose selecting a subset of objectives randomly in each iteration. This approach can reduce the computational load without significantly compromising the model's fairness and performance.

To validate our discussion, we conducted additional experiments using GLasso. In the first experiment, we generated synthetic data following the procedure detailed in the appendix of our paper, which includes two subgroups, each having 1000 observations and 100 variables. We applied various optimization algorithms to both the local graph learning and the multi-objective optimization processes. The detailed numerical results, presented in Table 2 of the attached one-page PDF file, demonstrate that all tested optimization algorithms for GLasso achieved optimal loss while maintaining performance improvements in fairness. Notably, GISTA and OBN for GLasso, along with FISTA for multi-objective optimization, significantly improved learning efficiency. We also repeated this experiment for high P values (P = 200), and the detailed numerical results presented in Table 2 of the attached one-page PDF further validate the improved efficiency of faster graphical model algorithms.

In the second experiment, we generated a synthetic dataset with ten subgroups to validate our approach to reducing time complexity. In each iteration of the multi-objective optimization, we randomly selected three objectives. The numerical results in Table 2 of the attached one-page PDF file indicate that this strategy effectively reduces runtime without substantially sacrificing model performance.

These results highlight the potential of our proposed methods to improve the computational efficiency of the learning algorithm while maintaining fairness and performance. We appreciate the reviewer’s feedback and believe these enhancements will further strengthen our framework.

Weakness 1: The authors only consider one criterion of fairness, which is achieving equal loss among subgroups. How do the authors justify focusing solely on this criterion? Additionally, how might incorporating other fairness criteria impact the results?

Weakness 5: Why do the authors not use more widely accepted metrics for fairness comparison and instead refer only to the difference in loss between subgroups?

Response: Thank you for your insightful comments. Our primary focus on the difference in loss between subgroups as a fairness criterion stems from the unsupervised nature of our task. In unsupervised learning, unlike supervised learning, we lack labeled data that are typically used to define fairness criteria such as demographic parity (DP)[JHF2022] and equalized odds (EO)[RBC2020]. Specifically, incorporating other fairness criteria like DP and EO, while beneficial for providing a broader perspective on fairness, typically requires labeled data to assess prediction distributions and accuracy across groups. This makes them less applicable to our unsupervised context.

This necessitated the development of a new fairness criterion, which we introduce as graph disparity error, solely based on the group-specific and global losses. Indeed, our proposed graph disparity error aligns with the goals of DP by promoting a balanced representation of all subgroups using the loss function. Graph disparity error measures the difference in graph loss between a global model $\Theta$ and the optimal local models $\Theta_1^*, \Theta_2^*, \ldots, \Theta_K^*$ for each subgroup $k \in [K]$. This is validated through our experiments in Section 4. For example, Figure 2 illustrates the comparison of original graphs utilized in synthetic data creation for two groups: graph reconstruction using standard GMs and fair graph reconstruction via Fair GMs. The figure demonstrates that Fair GMs produce more balanced and fair graph reconstructions across different subgroups compared to standard GMs, thereby supporting the effectiveness of the proposed graph disparity error in achieving fairness.

While future research on graphical model estimation could explore more widely accepted fairness metrics in supervised learning, our current work establishes a disparity error-based approach. It is worth mentioning that our nonsmooth multi-objective optimization framework for graphs is novel in this area and flexible enough to incorporate other fairness objectives. Future research can build on our framework to explore additional fairness metrics.

We have incorporated some of these discussions into the introduction of the revised paper. Thank you.

Weakness 2: Many recent works utilize reinforcement learning to discover fair structures. For instance, the paper "Rethinking Bias Mitigation: Fairer Architectures Make for Fairer Face Recognition" by S. Dooley et al. (NeurIPS 2023) explores such an approach. How do the authors justify their method compared to these more comprehensive approaches?

Response: We appreciate your comments and suggestions. The above paper explores the inherent biases in neural network architectures used for face recognition and proposes a novel approach to mitigate these biases through neural architecture search (NAS) and hyperparameter optimization (HPO). By conducting the first large-scale analysis of the impact of different architectures and hyperparameters on bias, the authors discovered that biases are baked into the architectures themselves. They designed a search space based on high-performing architectures and used NAS and HPO to jointly optimize for fairness and accuracy, considering sensitive attributes.

Although your suggested reference might be useful in the context of neural networks, such as graph neural networks, our problem is significantly different and is not related to neural architecture search or supervised learning. Indeed, our model focuses on unsupervised fair graph learning and does not involve any neural architecture search. Many standard fairness metrics, such as demographic parity or equalized odds, originally developed for supervised learning and widely used in neural networks, may not apply here. Our method is inspired by the idea that equal loss among subgroups ensures that no single group is disproportionately disadvantaged by the learned model, which aligns with established fairness definitions in the unsupervised machine learning literature.

We have added further discussion to the revised paper. Thank you.

I thank the authors for addressing my concerns. I have read the rebuttal.

Here are my post-rebuttal comments: Weakness 1 and 5: The loss disparity between K sub-groups seems rational to me. Just please bold in the paper that you need to have access to the label of the sensitive attribute. Weakness2: What I meant was to using reinforcement learning instead of multi-objective optimization. Please discuss it in the related work section. weakness 3: Nothing new is added by the authors. My question remains. weakness 4: I agree with the authors. Using the strategies, the computational overhead can indeed be reduced. Limitation 1: Thanks for bringing it into my attention. Limitation 3: Nothing new is added and the question remains. The authors can have a brief discussion about this in the paper.

Given all the comments, I stick to my rating.

The study is limited to Gaussian, Gaussian Covariance, and Binary Ising models.

I have noticed that the reviewer "1oDX" also asked about why the authors focus only on Gaussian case. This needs to be discussed in the paper.

We sincerely appreciate your feedback and the time you’ve taken to review our work. We would like to clarify that our work encompasses more than just the Gaussian case. Specifically, we address three canonical graphical models in statistical learning:

• Inverse Covariance Estimation,
• Covariance Estimation, and
• Ising Model Estimation.

It is crucial to emphasize that the Ising model is not Gaussian; it represents a distinct type of graphical model, particularly used for binary data.

Moreover, many other types of graphical models or statistical graph learning approaches can be viewed as variants derived from these canonical models.

We further elaborate on this below.

Firstly, we review two canonical types of graphical models (we have eliminated the discussion on Covariance Estimation as it falls under the category of Gaussian models for continuous data):

Ising Model for Binary Data: This model is defined by a probability distribution over binary variables. The distribution is determined by the so-called Boltzmann distribution:

Here, $\Theta$ (graph matrix) is a symmetric matrix, and $Z(\Theta)$ is the partition function that normalizes the density.

These models are primarily designed for binary data [HT2009, RWL2010].

Gaussian Graphical Model for Continuous Data: This model is suitable for continuous variables. The Gaussian graphical model is defined by the following distribution:

where $\mathbf{x} \sim \mathcal{N}(0, \Sigma)$, $\Sigma$ is the covariance matrix, and $\Theta=\Sigma^{-1}$ ( graph matrix) represents the precision matrix.

This model is widely used for continuous data [MB2006, YL2007, ABG2008, FHT2008, RZY2008].

Secondly, as we mentioned earlier, the Ising model is not designed for Gaussian cases but specifically for binary data rather than continuous data. This distinction makes the Ising model particularly suitable for applications involving binary data, such as modeling interactions between binary states in statistical physics or capturing binary decisions in social networks.

Finally, many other types of graphical models or statistical graph learning approaches can be viewed as variants derived from these two canonical models. For example,

• Graphical models for ordinal variables [GLM2015] assumes that the (categorical) data are generated by discretizing the marginal distributions of a latent multivariate Gaussian distribution.

• Mixed Graphical Models [CLL2017] combines Ising and Gaussian models to handle mixed data, including both continuous and discrete variables.

• Structured Graphical Models [KYC2020] combines Gaussian graphical models with spectral graph theory for joint clustering and graph learning, as well as bipartite graph learning.

Our current framework effectively addresses these canonical forms of graphical models—Gaussian for continuous data and Ising for binary data—within a single paper. Additionally, it can be extended to other models derived from these canonical forms, some of which are listed above.

We believe that our non-smooth multi-objective framework is novel for graphical model analysis and addressing fairness issues. It provides tools for a rich class of graphical model estimation, and corrects the biases present in traditional approaches to graphical model estimation.