Towards Fair Graph Generation Without Sensitive Attribute

Graph generation, which aims to produce new graphs from a distribution similar to observed data, has gained increasing attention, especially as generated graphs are used in high-stakes decision-making where fairness is critical. However, most existing fair graph generation methods assume full access to sensitive attributes, an assumption often violated in practice due to privacy concerns, regulatory constraints, and missing data. To this end, we propose to solve the problem from a new perspective, where sensitive proxy inference is reformulated as a component of the graph generation pipeline, enabling the inferred proxy to guide the generation process. We further model and mitigate the impact of proxy inference errors, and provide theoretical guarantees that quantify how such errors propagate to fairness outcomes in the generated graphs, offering practical guidance for interpreting fairness when sensitive attribute is missing. Experiments on benchmark datasets demonstrate that our method consistently improves fairness while maintaining competitive generation quality.