InFoRM: Individual Fairness on Graph Mining

TLDR

Algorithmic bias and fairness in graph mining are largely nascent, with most work focusing on group fairness while individual fairness remains underexplored. This study introduces the first principled framework for individual fairness in graph mining (InFoRM), defining a quantitative bias measure and proposing three complementary mitigation strategies. The authors formulate the bias measure and three optimization‑based debiasing frameworks—targeting the input graph, the mining model, and the results—using efficient solvers applicable to multiple graph mining tasks, and analyze the cost of enforcing fairness. Experimental evaluation on real‑world datasets demonstrates that incorporating individual fairness changes original mining outcomes and that the proposed methods are effective and broadly applicable.

Abstract

Algorithmic bias and fairness in the context of graph mining have largely remained nascent. The sparse literature on fair graph mining has almost exclusively focused on group-based fairness notation. However, the notion of individual fairness, which promises the fairness notion at a much finer granularity, has not been well studied. This paper presents the first principled study of Individual Fairness on gRaph Mining (InFoRM). First, we present a generic definition of individual fairness for graph mining which naturally leads to a quantitative measure of the potential bias in graph mining results. Second, we propose three mutually complementary algorithmic frameworks to mitigate the proposed individual bias measure, namely debiasing the input graph, debiasing the mining model and debiasing the mining results. Each algorithmic framework is formulated from the optimization perspective, using effective and efficient solvers, which are applicable to multiple graph mining tasks. Third, accommodating individual fairness is likely to change the original graph mining results without the fairness consideration. We conduct a thorough analysis to develop an upper bound to characterize the cost (i.e., the difference between the graph mining results with and without the fairness consideration). We perform extensive experimental evaluations on real-world datasets to demonstrate the efficacy and generality of the proposed methods.