FairWire: Fair Graph Generation

Summary

In this submission a graph diffusion model with fairness correction is introduced for graph generation. The model is also applied for link prediction. The authors introduce a graph regularizer for fairness based on a theoretical bound for subgroup distance and representation distance. This analysis is newly introduced by the authors. The authors apply the regularizer to link prediction, examining the accuracy-fairness tradeoff. The authors then test fair graph generation by examining link prediction and node classification tasks, but replace the training graphs with fairness-corrected generated graphs. Empirically it is shown that this greatly improves fairness while marginally reducing accuracy.

Strengths

This paper has key straightforward strengths that contribute to my "weak accept" rating. First, the method seems to perform well, within the scope of the intended contributions. The paper is generally well-written and the presentation is clear. Furthermore the theoretical results are satisfactory. They appear correct and they properly motivate the method.

Weaknesses

There is some missing/glossing-over existing work. The authors claim that the theoretical analysis is novel, however ref [24] in the paper also includes a theoretical analysis with >2 binary categories. It would be good for the authors to discuss this work and compare with their own. Also, the authors should consider citing "Debiasing Graph Representations via Metadata-Orthogonal Training" (doi/10.1109/ASONAM49781.2020.9381348), which seems relevant to the problem (also includes a fairness correction over potentially >2 attributes). There are a non-trivial amount of clarity and presentation issues, which I discuss in my list of questions.

Questions

(1) In the second experiment type (S6.3), which link prediction model was trained on the generated graphs? And was the FairWire regularization also applied to the link prediction model during training? (2) From Fig 1 we can see that FairWire effectively removes intra-edges from generated graphs. However, the structure of the generate graphs is not quite evident. Can the graphs be visualized in a more productive way? Maybe the adjacencies can be row-sorted into their communities. (3) The authors derive two fairness criterion $\alpha_1$ and $\alpha_2$, though $\alpha_2$ is ignored at the mini-batch level for scalability. Can the authors give more intution about $\alpha_2$ and why it should ultimately not matter when applied in practice?

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes

Summary

This work considers the problem of fairness in learning over graphs. Namely, it adopts a criterion for fairness that quantifies the probability of a relationship existing between nodes whose sensitive attribute value matches (intra-edges) versus not (inter-edges). It first derives theoretical results that bound the discrepancy between the two, and uses these insights to design a "fairness regularizer" that is compatible with both link prediction and synthetic graph generation tasks. The authors perform an evaluation on these two tasks, outperforming existing baselines in fairness metrics while preserving the core utility metric (e.g., accuracy).

Strengths

The paper considers a problem that has been studied previously but is original in the way it approaches it. The quality of the work is high and contains both theoretical insights and thorough experiments. The organisation of the paper is clear and the writing quality is also high. The topic is significant and relevant to the NeurIPS community. Reproducibility is also good as code is provided and experiments are described clearly.

Weaknesses

The paper is very well executed. In my opinion, its main weakness is that the considered fairness definition is adopted without a convincing justification. It is rather well-known in the network science literature [1,2] that individuals tend to form connections with those that are similar to them. Therefore, I do not understand why this characteristic is framed as inherently "bad" and something that should be corrected when training a model for link prediction or graph generation. I think this deserves a proper justification and discussion. However, this may be a point that is broader than the paper itself. [1] McPherson, M., Smith-Lovin, L., & Cook, J. M. (2001). Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1), 415-444. [2] Newman, M. E. (2003). Mixing patterns in networks. Physical review E, 67(2), 026126.

Questions

Please address the potential weakness discussed above. Additional questions and comments: C1. Could you discuss what happens if there is >1 sensitive attribute? Do your results already apply via some transformation, or what would be required to generalise to this case? C2. Line 131-32: I think this claim needs to be scoped to e.g. *social* networks, as this is definitely not always the case (see e.g. ref [2] above). C3. Line 153: maximization is over $k$ presumably? C4. Line 167; Eq 3: $\mathbf{Se}_{k}$ not defined as far as I can tell. C5. Experiments in 6.2: I think it should be discussed what "base GNN" is being used. Appendix G mentions it is a GCN -- but what is the justification for using a single layer? C6. I think it's worth summarizing the choice and justification for the considered sensitive attributes in the main text (currently in Appendix E). C7. Table 5 is overflowing the margins, consider wrapping in `\resizebox`

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations and potential negative social impacts are discussed, although the latter only superficially, and I think it deserves more discussion given the primary area of the paper is fairness.

Summary

The impact of generative learning algorithms on structural bias is investigated in this paper. The authors provide a theoretical analysis on the sources of structural bias which result in disparity. Then a novel fairness regularizer is designed to alleviate the structural bias for link prediction tasks over graphs. Furthermore, a fair generation framework called FairWire is proposed by leveraging the fairness regularizer in a generative model. Finally, extensive experiments on synthetic and real datasets are conducted to show the effectiveness of mitigating structural bias in machine learning algorithms on graphs.

Strengths

1. The theoretical analysis on the sources of structural bias is novel and intuitive, which provides an interesting perspective on what causes the bias problem in machine learning algorithms over graphs. 2. The design of the regularizer and fair graph generation model address the challenges and theory reasonably. Besides, sufficient experiments are provided to prove the better performance on mitigating the structural bias problem. 3. The paper's writing is good, and the overall structure is clear.

Weaknesses

1. This paper aims to address the fairness in graph generation. But there are not sufficient experiments on different representative backbone generation models. The authors only provide one backbone generation model, I suggest more representative backbone generation model to solidify the effectiveness. 2. This paper provides the theory and algorithm based on the sensitive group which may limit the use to real world graphs.

Questions

1. The author introduce GraphMaker as a backbone generative model and claimed that this method considers the bias mitigation when generating new graphs. Does it mean that FairWire can not been used on other generative models? 2. In the experiments, for the supervised tasks the author use link prediction tasks results, while for generation tasks, the author use node classification tasks results. What is the results of node classification tasks for supervised tasks? It would be better that the same tasks are used to evaluate both the supervised and generative tasks. 3. The authors claim the contribution in fairness over generative graph algorithm, but also provides a lot experimental results on supervised tasks. What is the difference in structural bias problem over generative tasks and supervised tasks? 4. From the experimental results, FairWire makes the performance of AUC worse. What is the influence of FairWire on the accuracy of the GNN model? Does it influence the model training or that because GNN models conducts bias on different samples? 5. From the theoretical analysis of the paper, we have to know the sensitive group first, how would you define and select sensitive groups? What kind of influence does sensitive group have on GNN and the proposed FairWire method?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors adequately addressed the limitations of their methods. And It is hard to foresee any potential negative societal impact of this work.

Thanks

The authors have satisfactorily addressed my concerns. I have raised the presentation score and the overall score.