Title: COPF: An Online Framework for Deployment-Stable Counterfactual Fairness in Evolving Graphs

Abstract:

Online link recommendation systems operating on dynamic graphs are inherently performative; the act of selecting which candidate links to display to users directly influences which connections are established and subsequently shapes the feedback the system receives. As a result, fairness metrics derived from logged outcomes may be deceptive and subject to drift once the deployment policy is modified. To address this, we propose COPF (Counterfactual Online Performative Fairness), a decision-layer framework designed to ensure stable fairness monitoring and control during the deployment of online link recommendations. COPF operates by (i) quantifying group-level opportunity gaps based on counterfactuals of exposure (i.e., whether a link was shown or withheld); (ii) rendering these gaps estimable through explicit exploration and by recording the propensity score—the probability that each candidate link was displayed; and (iii) auditing and regulating fairness via residual outcome indistinguishability (OI), evaluated over a customizable auditor family utilizing graph-aware doubly robust (GA-DR) estimators. We establish a noisy transfer theorem demonstrating that Residual-OI, calculated on estimated GA-DR residuals, yields bounds on exposure-counterfactual group gaps, provided there is temporal mixing and bounded local interference. Furthermore, we implement an online multicalibration auditor coupled with a primal-dual controller. Empirical evaluations on two TGB data streams and a controlled synthetic bipartite stream indicate that COPF effectively mitigates worst-case spikes in exposure-counterfactual group disparities while imposing only a minimal penalty on ranking utility. Our code is available at https://github.com/lsnnnnnnnn/COPF.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC