DANCE: Dual Unbiased Expansion with Group-acquired Alignment for Out-of-distribution Graph Fairness Learning

We are truly grateful for the time you have taken to review our paper, your insightful comments and support. Your positive feedback is incredibly encouraging for us! In the following response, we would like to address your major concern and provide additional clarification.

Q1. High computational cost. DANCE use multiple modules (graph expansion, adversarial learning, alignment, and disentanglement), which increase computational costs.

Thanks for your comment. We have included the efficiency analysis and comparison as follows. From the result, we can observe that our method has a competitive computation cost. In particular, we provide the following analysis:

• Complexity analysis. The computing complexity of our framework mainly depends on (a) Dual graph expansion, (b) Group-acquired alignment and (c) Representation disentanglement. Let $N_{syn}$ be the number of synthesized nodes. Then, since logits can be obtained from the previous epoch, for (a), we need $\mathcal{O}(N^2_{syn})$ extra time for anchor and auxiliary nodes sampling, $\mathcal{O}(N_{syn}d)$ for feature mixup and $\mathcal{O}(N_{syn}/N\cdot|\mathcal{E}|)$ for generating synthesized edges. Meanwhile, adversarial learning on synthesized data takes $\mathcal{O}((N+N_{syn})d^2)$. For (b) and (c), the complexity for the target and sensitive encoder is $\mathcal{O}(2L|\mathcal{E}|d+2Nd^2)$ with $L$ layers while the view alignment takes $\mathcal{O}(N|\mathcal{B}|d)$ with total $|\mathcal{B}|$ positive and negative pairs. Compared with FatraGNN [1], the additional complexity is $\mathcal{O}({N}^2_{syn}+(N_{syn}+N|\mathcal{B}|)d+N_{syn}/N\cdot|\mathcal{E}|)$, mainly from the dual graph augmentation and contrastive learning modules, which are carefully controlled in our implementation.

• Practical training overhead. From a practical standpoint, we have provided the time complexity and training time of our DANCE to further demonstrate its computational efficiency in comparison to other baselines. The results indicate that our framework maintains a competitive computation cost compared with baselines.

In summary, our method has a competitive computation cost in comparison with the baseline. We will include the above discussion in our revised version.

Q2. The authors do not provide case studies that illustrate why DANCE is superior than other methods.

Thank you for the insightful comment! We have provided t-SNE visualizations that offer a qualitative comparison of the learned representations between DANCE and the benchmark model (FatraGNN). These visualizations help illustrate how DANCE better achieves fair and discriminative representations.

The colors in the plots represent different combinations of sensitive attributes and target labels:

• Pink: sensitive = 1, y = 0
• Green: sensitive = 0, y = 0
• Grey: sensitive = 1, y = 1
• Blue: sensitive = 0, y = 1

FatraGNN [1] (Benchmark) t-SNE Results:

Pokec_z: https://anonymous.4open.science/r/DANCE_ICML_2025-BD70/Fatra_pokec_z_tsne.png

Pokec_n: https://anonymous.4open.science/r/DANCE_ICML_2025-BD70/Fatra_pokec_n_tsne.png

DANCE t-SNE Results:

Pokec_z: https://anonymous.4open.science/r/DANCE_ICML_2025-BD70/DANCE_pokec_z_tsne.png

Pokec_n: https://anonymous.4open.science/r/DANCE_ICML_2025-BD70/DANCE_pokec_n_tsne.png

Compared to FatraGNN, DANCE exhibits a much clearer separation between target labels (i.e., the blue/grey cluster vs. the pink/green cluster), while sensitive attributes are not clustered, indicating reduced sensitive information leakage. In contrast, the benchmark method (FatraGNN) shows all four colors more uniformly mixed, with no clear separation based on target labels, suggesting entanglement of sensitive and target information.

This case study provides intuitive evidence that DANCE achieves better separation of semantic information while mitigating bias from sensitive attributes, thereby demonstrating its superiority over existing methods.

Reference

[1] Li Y, Wang X, Xing Y, et al. Graph fairness learning under distribution shifts, Proceedings of the ACM Web Conference 2024. 2024: 676-684.

Thanks again for appreciating our work and for your constructive suggestions. Please let us know if you have further questions.

We are truly grateful for the time you have taken to review our paper, your insightful comments and support. Your positive feedback is incredibly encouraging for us! In the following response, we would like to address your major concern and provide additional clarification.

Q1. The framework involves multiple sophisticated modules, potentially increasing the difficulty of implementation and complexity. Also, the author did not discuss the time complexity for the proposed method: how expensive it is to adopt it in practice? Generally the discussions on computational cost, scalability, and efficiency is limited. What are the computational overheads introduced by the proposed approach, particularly in comparison to simpler fairness-aware methods?

Thanks for your comment. We have included the efficiency analysis and comparison as follows. From the result, we can observe that our method has a competitive computation cost. In particular, we provide the following analysis:

• Complexity analysis. The computing complexity of our framework mainly depends on (a) Dual graph expansion, (b) Group-acquired alignment and (c) Representation disentanglement. Let $N_{syn}$ be the number of synthesized nodes. Then, since logits can be obtained from the previous epoch, for (a), we need $\mathcal{O}(N^2_{syn})$ extra time for anchor and auxiliary nodes sampling, $\mathcal{O}(N_{syn}d)$ for feature mixup and $\mathcal{O}(N_{syn}/N\cdot|\mathcal{E}|)$ for generating synthesized edges. Meanwhile, adversarial learning on synthesized data takes $\mathcal{O}((N+N_{syn})d^2)$. For (b) and (c), the complexity for the target and sensitive encoder is $\mathcal{O}(2L|\mathcal{E}|d+2Nd^2)$ with $L$ layers while the view alignment takes $\mathcal{O}(N|\mathcal{B}|d)$ with total $|\mathcal{B}|$ positive and negative pairs. Compared with FatraGNN [1], the additional complexity is $\mathcal{O}({N}^2_{syn}+(N_{syn}+N|\mathcal{B}|)d+N_{syn}/N\cdot|\mathcal{E}|)$, mainly from the dual graph augmentation and contrastive learning modules, which are carefully controlled in our implementation.

• Practical training overhead. From a practical standpoint, we have provided the time complexity and training time of our DANCE to further demonstrate its computational efficiency in comparison to other baselines. The results indicate that our framework maintains a competitive computation cost compared with baselines.

In summary, our method has a competitive computation cost in comparison with the baseline. We will include the above discussion in our revised version.

Q2. The rationale behind prioritizing negative pairs with identical sensitive labels.

Thanks for your comment. Below we provide both the rationale analysis and empirical evidence to support prioritizing negative pairs with identical sensitive attributes in the group-acquired alignment objective.

• Rationale Analysis. The rationale behind prioritizing the negative pairs is to mitigate the encoder’s reliance on sensitive attribute information during representation learning. When $z _ p\in\mathbf{Z} _ {ig}$, both the positive and negative samples share the same sensitive attributes as the anchor node. Therefore, the encoder no longer considers sensitive attribute information a valuable feature for fairness learning. When $z _ p\in\mathbf{Z} _ {sg}$, the positive samples have different sensitive attributes from both the anchor and the negative samples. If the encoder learns sensitive attribute information, the similarity between the positive samples and the anchor will decrease, while the similarity between the negative samples and the anchor will increase, which is contrary to the objective of the loss function.

• Empirical Evidence. To validate this design, we performed a comparative experiment where negative pairs were sampled solely based on differing target labels, without considering sensitive attributes (denoted Var 1 in the following table). The results are summarized below:

From the result, we can find DANCE significantly outperforms Var 1 on fairness metrics. This indicates that prioritizing negative pairs with identical sensitive attributes plays a key role in learning representations that are both fair and robust under distribution shifts.

Reference

[1] Li Y, Wang X, Xing Y, et al. Graph fairness learning under distribution shifts, Proceedings of the ACM Web Conference 2024. 2024: 676-684.

Thanks again for appreciating our work and for your constructive suggestions. Please let us know if you have further questions.

We are truly grateful for the time you have taken to review our paper, your insightful comments and support. Your positive feedback is incredibly encouraging for us! In the following response, we would like to address your major concern and provide additional clarification.

Q1. The performance under the same distribution.

Thank you for your comment. We have added the performance of our model and several baselines under the same distribution setting as below. From the results, our method achieves better performance compared with baselines. We will add these results to our revised version.

Q2. Does it mean every component, even the mixup, will contribute to the fairness results?

Thank you for the comment. In our framework, each component is designed to address a specific challenge in out-of-distribution (OOD) graph fairness learning, and our ablation results demonstrate that each module makes a meaningful contribution to the final fairness performance.

Specifically, we expand the graph data in both the structural space and the feature space. The unbiased Mixup module enlarges the decision boundary of minority groups, helping to rebalance representation across sensitive attributes. The adversarial learning module simulates worst-case distribution shifts by introducing challenging perturbations in feature space, enhancing the model's robustness. Building on this expanded data, the group-acquired alignment module aligns representations across groups while discouraging the use of sensitive attributes, and the representation disentanglement module explicitly separates sensitive and target information to further reduce bias.

Together, these components form a cohesive design, and the degradation observed in fairness metrics upon removing any one of them confirms that each module plays a critical role in achieving fairness under distribution shifts.

Q3. In Table 3, while the C3-Var3 cell has better $\Delta DP$ performance, other cells (C-Var3) show significantly lower performance

Thank you for the comment. We have provided the following explanation:

• Complicated Graph Data. Real-world graph datasets (such as Credit-Cs) exhibit considerable variability in their structural properties—such as homophily and sensitive group imbalance. As shown in the table below, these graph datasets have different and complicated characteristics, which could result in performance fluctuation. Overall, our full model shows better performance in comparison with the model variant in most cases, which validates the effectiveness of the proposed method.

• Previous Observations. Similar cross-dataset variations have been observed in prior studies. For instance, [2] observes that fairness improvements can vary significantly across different datasets when evaluating fairness-aware GNN methods. As shown in Table 1 of [2], RFR exhibits large fluctuations in $\Delta$DP between the Adult (1.0, 2.0) and Adult (3.0, 6.0) subsets, while its $\Delta$DP performance remains relatively stable across the ACS-E (1.0, 2.0) and ACS-E (3.0, 6.0) subsets. This illustrates that the underlying data distribution plays a crucial role, and that fairness improvements achieved on one subset may not generalize consistently across others.

Q4. Novelty of DANCE

Thanks for your comment. The innovations of this work include:

• Data-centric perspective. We explore an underexplored yet important OOD graph fairness learning problem from a data-centric perspective, achieving better performance compared to baselines.

• A unified graph fairness learning framework. Our framework is a unified approach that combines dual unbiased graph expansion and group-acquired alignment to minimize the domain gap while ensuring fairness.

• Theoretical analysis. We provide a theoretical analysis demonstrating that our framework can control information propagation between different groups for fairness learning and ensure the convergence of the loss function.

[1] Laclau C, et al. A survey on fairness for machine learning on graphs. arXiv, 2022.

[2] Jiang et al., Chasing fairness under distribution shift: A model weight perturbation approach, NeurIPS 2023.

Thanks again for appreciating our work and for your constructive suggestions.

We are truly grateful for the time you have taken to review our paper and your insightful review. Here we address your comments in the following.

Q1. Why Theorem 3.1 can show that the graph diffusion method can precisely control the propagation of information between different groups?

To clarify the intuition behind the assumption in Theorem 3.1, we rewrite it as follows:

First, we prove that for any $i \in \mathcal{V} _ s$, there exists $j \in \mathcal{V} _ {-s}$ such that:

$$\left[\sum _ {r=0}^{\infty} \theta^r ({T} _ {\text{anc}}^r {H}^{(l-1)})\right] _ {ij} \neq 0.$$

By the definition of $A _ {anc}$, for any $i \in \mathcal{V} _ s$ we can get $A _ {anc,ik} > 0$, where $k \in \mathcal{V} _ s \cup \{v _ {syn}\}$. And there exists $j \in \mathcal{V} _ {-s}$ satisfying $A _ {anc,v _ {syn}j} > 0$. This implies that for any $i \in \mathcal{V} _ s$, there exists a path $i \to v _ {syn} \to j$ with $j \in\mathcal{V} _ {-s}$, where $A _ {anc,iv _ {syn}} > 0$ and $A _ {anc,v _ {syn}j} > 0$. For path length $r _ 0 = 2$, we can get $[T _ {anc}^2] _ {ij} = \sum _ {k \in V} [T _ {anc}] _ {ik}[T _ {anc}] _ {kj} \\ \geq \frac{A _ {anc,iv _ {syn}}}{D _ {anc,i}} \cdot \frac{A _ {anc,v _ {syn}j}}{D _ {anc,v _ {syn}}} > 0$. Similarly, for $r _ 0 > 2$ with the path $i = k _ 0 \to k _ 1 \to \cdots \to k _ {r _ 0} = j$, we have $[T _ {anc}^{r _ 0}] _ {ij} \geq \prod _ {s=1}^{r _ 0} \frac{A _ {anc,k _ {s-1}k _ s}}{D _ {anc,k _ {s-1}}} > 0$. Therefore, we can get $\left[\sum _ {r=0}^\infty \theta _ r (T _ {anc}^r H^{(l-1)})\right] _ {ij} > 0$.

Then, we prove by mathematical induction that $\forall i \in \mathcal{V} _ {-s}, j \in \mathcal{V} _ s$, we have:

$$\left[\sum_{r=0}^\infty \theta_r (T_{anc}^r H^{(l-1)})\right]_{ij} = 0.$$

Base case ($r=0$): For $i \in \mathcal{V} _ {-s}$ and $j \in \mathcal{V} _ s$, the identity matrix satisfies $[T _ {anc}^0] _ {ij} = \delta _ {ij} = 0.$

Inductive step: Assume $\forall r \leq n$ and $\forall i \in \mathcal{V} _ {-s}$, $j \in \mathcal{V} _ {s}$, $[T _ {anc}^r] _ {ij} = 0$. For $r = n+1$, we have $[T _ {anc}^{n+1}] _ {ij} = \sum _ {k \in \mathcal{V} _ s} [T _ {anc}^n] _ {ik}[T _ {anc}] _ {kj} + \sum _ {k \in \mathcal{V} _ {-s}} [T _ {anc}^n] _ {ik}[T _ {anc}] _ {kj}$.

$\forall k \in \mathcal{V} _ {s}$, the inductive hypothesis implies $[T _ {anc}^n] _ {ik} = 0$. $\forall k \in \mathcal{V} _ {-s}$, by the definition of $A _ {anc}$, $A _ {anc,kj}=0$. Therefore, we can get $[T _ {anc}^{n+1}] _ {ij} = 0$.

By mathematical induction, $\forall r \geq 0$, $[T _ {anc}^r] _ {ij} = 0$, which leads to $\left[\sum _ {r=0}^\infty \theta _ r (T _ {anc}^r H^{(l-1)})\right] _ {ij} = 0$.

This assumption reflects that the graph diffusion method in DANCE can shield minority groups from majority interference while permitting essential cross-group feature learning. This distinction justifies the assumption and highlights the geometric intuition behind Theorem 3.1.

Q2. Some essential references are not included.

We will include the following discussion into our revised version:

Additionally, FairGB [1] introduces a counterfactual node mixup strategy, generating synthetic samples by interpolating node features and labels across different demographic groups to address demographic group imbalances. Similarly, FDGNN [2] and RFCGNN+ [3] design counterfactual augmentations by varying sensitive or label values while preserving the original adjacency matrices to learn fairer representations. In comparison with these methods, our method specifically focuses on mixing minor sensitive group nodes with those of different sensitive attributes to generate challenging samples that extend decision boundaries, thereby enhancing generalization and fairness.

Q3. What is to be understood by ‘challenging’ in this context?

In our context, we use the term “challenging” samples to refer to those that are difficult to classify but strategically designed to improve generalization and fairness. Specifically:

• Synthesized nodes located near class decision boundaries are generated via Mixup (Eq. 7) between minor group nodes and auxiliary nodes. These samples exhibit higher prediction uncertainty and encourage the model to refine its classification boundaries [4].
• Adversarial learning (Sec. 3.2) introduces perturbations that further amplify this uncertainty, thereby enhancing the model’s robustness and fairness under distribution shifts.

In summary, “challenging” refers to samples that are difficult to classify but strategically beneficial for improving both generalization and fairness.

[1] Rethinking fair graph neural networks from re-balancing. KDD 2024

[2] Disentangled contrastive learning for fair graph representations. Neural Networks, 2025

[3] Toward fair graph neural networks via real counterfactual samples. KAIS, 2024

[4] Self-supervised graph-level representation learning with adversarial contrastive learning, TKDD, 2023