Prior Signal Editing for Graph Filter Posterior Fairness Constraints

Emmanouil Krasanakis, Symeon Papadopoulos, Ioannis Kompatsiaris, Andreas SymeonidisarXiv 2021 · arXiv

TL;DR

This paper introduces a novel framework for ensuring fairness in graph-based recommendation systems by editing input data ("priors") rather than final outputs ("posteriors"). By leveraging the inherent mathematical robustness of graph filters, the proposed FairEdit algorithm successfully mitigates disparate impact against protected groups while preserving high recommendation accuracy. This approach provides a theoretically grounded, low-parameter solution to algorithmic bias in relational data.

What Problem Does This Paper Address?

Graph filters—such as personalized PageRank and heat kernels—are widely used to rank nodes and power recommendation systems in social networks, citation webs, and software engineering. They work by propagating initial node attributes (priors) across the graph's edges to produce final recommendation scores (posteriors).

However, if the underlying graph structure or the initial data contains historical biases, the graph filter will propagate and potentially amplify these biases. This leads to disparate impact, where a protected group (e.g., based on gender, ethnicity, or niche research topics) receives systematically lower recommendation scores.

The challenge lies in mitigating this bias without destroying the utility of the system. Existing approaches either alter the graph topology (which is computationally expensive and structurally disruptive) or directly manipulate the output scores. Direct output manipulation breaks the structural consistency provided by the graph, severely degrading recommendation quality (measured by the Area Under the ROC Curve, or AUC).

Methods

The authors propose a paradigm shift: Prior Signal Editing. Instead of fixing the outputs, they use a low-parameter surrogate model to subtly adjust the input priors ($q$) into edited priors ($q_{est}$) so that the natural propagation mechanism of the graph filter yields fair outputs ($r_{est}$).

Building on their own previous work (FairPers), the authors introduce FairEdit, which features three key methodological innovations:

  1. Error-Based Perturbations: Instead of using raw differences between priors and posteriors, FairEdit utilizes the absolute value of these differences, making the model parameters highly explainable.
  2. Explicit Prior Retention: A new parameter ($a_0$) is introduced to explicitly control how much of the original, high-quality prior signal is retained, balancing fairness and accuracy.
  3. KL-Divergence Objective: The training objective replaces mean absolute error with Kullback-Leibler (KL) divergence. This treats the scores as probability distributions, preventing a few high-scoring outlier nodes from dominating the optimization process.

Theoretical Justification: Crucially, the paper provides a mathematical framework (Theorems 2 and 3) proving that because graph filters are naturally robust to small input perturbations, even a "coarse" editing mechanism with very few parameters can successfully guide the system to a locally optimal, fair state.

Datasets

The authors evaluated their approach on a diverse corpus of 12 real-world graphs spanning multiple domains:

  • Social Networks: Facebook0, Facebook686, Twitter
  • Citation Networks: ACM, Citeseer, DBLP, Pubmed
  • Co-purchase Networks: Amazon
  • Software Dependency Graphs: Ant, Log4J, Maven, Squirrel

These datasets vary drastically in size (from 170 nodes in Facebook686 to nearly 1 million nodes in DBLP) and structural properties, providing a robust benchmark for generalization.

Key Insights and Ideas

  • Work With the Filter, Not Against It: Modifying final recommendation scores discards the relational context generated by graph propagation. By editing the inputs instead, the algorithm allows the graph's natural structure to maintain predictive quality.
  • Coarse Approximations Suffice: You do not need a massive, complex neural network to fix bias in graph filters. Due to the spectral properties of positive definite graph filters, loose approximations of optimization gradients are mathematically sufficient to reach local fairness optima.
  • Outlier Mitigation is Critical: In graph data, highly connected "super-nodes" can easily skew standard error metrics. Shifting the optimization loss to KL-divergence ensures that the fairness adjustments are robust against these distribution outliers.

Key Results

  • Robust Fairness Enforcement: FairEdit and its constrained variant (FairEdit-C) consistently achieved or exceeded the standard 80% pRule threshold (a metric evaluating statistical parity) across the majority of the 12 test graphs.
  • Superior Quality Preservation: When maximizing fairness, FairEdit achieved at least 3% higher average AUC compared to the previous state-of-the-art prior-editing method (FairPers), and significantly outperformed direct score redistribution methods (like LFPRO), which suffered severe drops in utility.
  • Synergy with Post-Processing: When paired with the "sweep ratio" (a technique used to improve community detection), FairEdit-C saw an accuracy boost of up to 4% in AUC while simultaneously improving fairness metrics by roughly 2%.

Limitations and Future Work

  • The DBLP Exception: The authors noted an outlier in their results: FairEdit failed to meet the 80% pRule constraint on the massive DBLP dataset when using personalized PageRank. They attribute this to the graph's specific eigenvalue ratio, suggesting that tighter approximation terms are required for certain graph topologies.
  • Future Directions: The authors plan to extend this optimization framework to other complex objectives, such as directly maximizing smooth relaxations of the AUC metric. They also aim to mathematically calculate a strict lower bound on the minimum number of parameters required for effective prior editing.

Summary updated

Abstract

Graph filters are an emerging paradigm that systematizes information propagation in graphs as transformation of prior node values, called graph signals, to posterior scores. In this work, we study the problem of mitigating disparate impact, i.e. posterior score differences between a protected set of sensitive nodes and the rest, while minimally editing scores to preserve recommendation quality. To this end, we develop a scheme that respects propagation mechanisms by editing graph signal priors according to their posteriors and node sensitivity, where a small number of editing parameters can be tuned to constrain or eliminate disparate impact. We also theoretically explain that coarse prior editing can locally optimize posteriors objectives thanks to graph filter robustness. We experiment on a diverse collection of 12 graphs with varying number of nodes, where our approach performs equally well or better than previous ones in minimizing disparate impact and preserving posterior AUC under fairness constraints.
BibTeX
@misc{krasanakis2021prior,
  author = {Emmanouil Krasanakis and Symeon Papadopoulos and Ioannis Kompatsiaris and Andreas Symeonidis},
  title = {{Prior Signal Editing for Graph Filter Posterior Fairness Constraints}},
  year = {2021},
  eprint = {2108.12397},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2108.12397},
}
Figure