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

Online link recommendation on evolving graphs is performative: by choosing which candidate links to show users, the system changes which links form and what feedback it later observes. Consequently, fairness estimates from logged outcomes can be misleading and may drift after deployment when the recommendation policy is updated. We introduce COPF (Counterfactual Online Performative Fairness), a decision-layer framework for deployment-stable fairness monitoring and control in online link recommendation. COPF (i) defines group-level opportunity gaps over exposure (shown vs. not shown) counterfactuals, (ii) makes them estimable by explicit exploration and by logging the probability (propensity) that each candidate is shown, and (iii) audits and controls fairness using residual outcome indistinguishability (OI) over a configurable auditor family with graph-aware doubly robust (GA-DR) estimators. We provide a noisy transfer theorem showing that Residual-OI on estimated GA-DR residuals implies bounds on exposure-counterfactual group gaps under temporal mixing and bounded local interference, and we instantiate an online multicalibration auditor together with a primal-dual controller. Experiments on two TGB streams and a controlled synthetic bipartite stream show that COPF reduces worst-case spikes in exposure-counterfactual group disparities with modest impact on ranking utility. Our code is available at https://github.com/lsnnnnnnnn/COPF.

Many online platforms recommend links: people to follow, pages to visit, or items to review. These recommendations do more than predict future behavior; they shape what users see, which links are created, and what data the system learns from later. This feedback loop makes fairness difficult to measure, because a group may seem to receive fewer positive outcomes simply because it was offered fewer opportunities. This paper studies how to monitor and reduce this problem in online link recommendation. We introduce COPF, a framework that sits on top of an existing recommendation model. COPF occasionally explores different recommendations, records how likely each candidate was to be shown, and uses these logs to estimate what would likely have happened if a candidate link had been shown or not shown. It then checks whether the benefit of being shown is similar across groups and adjusts future exposures when large disparities appear. Experiments on temporal graph benchmarks and a controlled synthetic dataset show that COPF can reduce sudden increases in group disparities while keeping recommendation quality mostly intact.