Group fairness without demographics using social networks

David Liu, Virginie Do, Nicolas Usunier, Maximilian Nickel

TL;DR

This paper introduces a "group-free" fairness framework that leverages social network homophily to reduce outcome inequalities without requiring sensitive demographic labels like race or gender. By using continuous pairwise similarities derived from network structure instead of discrete group memberships, the authors provide a privacy-respecting way to address fairness that naturally handles complex group intersections.

What Problem Does This Paper Address?

Traditional algorithmic fairness relies on "group fairness," which aims to equalize outcomes across protected groups. However, this approach has two major flaws:

  1. Privacy and Legality: Collecting sensitive demographic data (race, disability status, etc.) is often invasive, risky, or legally prohibited.
  2. Rigidity: Standard methods use coarse, predefined groups. They often fail to protect people at the intersection of multiple groups (e.g., Black women) or groups not explicitly defined in law, a problem known as "fairness gerrymandering."

The authors address the challenge of achieving group fairness without demographics, treating it as one of the key open problems in the field.

Methods

The core idea is to use homophily—the sociological principle that similar people tend to connect in social networks—as a proxy for group membership.

  • Similarity Kernels: Instead of assigning users to discrete groups, the authors infer pairwise similarities between individuals using the network's topology. They primarily use Laplacian Eigenmaps to embed nodes into a latent space where distance reflects similarity.
  • Group-Free Inequality Measure: They extend economic inequality indices (like Generalized Entropy) from discrete partitions to similarity kernels. This allows them to define "between-group" inequality without ever explicitly defining what the groups are.
  • Theoretical Grounding: The authors prove that their measure satisfies "generalized additive decomposability," meaning it behaves like traditional group fairness metrics when groups are known, but generalizes smoothly to the "group-free" setting.
  • Optimization: They apply this measure as either a constraint or an objective in three different tasks:
  • Node Classification: Re-labeling nodes to distribute positive outcomes more fairly.
  • Information Access: Selecting "seed" nodes in a network to ensure information spreads equitably across latent groups.
  • Recommender Systems: Balancing item exposure across different types of users.
Figure 1: Examples of how similarity kernels (K) can recover latent block structures in networks with varying embedding dimensions (d).

Datasets

The authors evaluated their approach on four real-world social networks that include ground-truth demographic labels (used only for evaluation, not by the algorithm):

  • PolBlogs: A network of political blogs (labels: liberal or conservative).
  • Email-EU: An email network within a research institution (labels: department).
  • Lastfm-Asia: A music service social network (labels: country).
  • Deezer-Europe: A music streaming network (labels: gender).

Key Insights and Ideas

  • Network as a Proxy: Social networks are rich with information about unobserved attributes. Even without labels, the "birds of a feather" pattern allows fairness interventions to target the right people.
  • Avoiding "All-or-Nothing" Costs: Naive approaches that try to first detect communities (clusters) and then apply fairness often fail because community detection is noisy. Small, erroneously detected groups can lead to "all-or-nothing" optimization failures. The continuous similarity approach is much more robust.
  • Robustness to Confounding: The authors theoretically bound how much non-sensitive attributes (like shared hobbies) might "pollute" the fairness measure. They show that as long as the sensitive attribute is a significant driver of network formation, the method remains effective.
Figure 2: Theoretical bounds on the group-free inequality measure in the presence of confounding non-sensitive attributes.

Key Results

  • Classification: On the PolBlogs dataset, the method reduced ground-truth inequality from 0.85 to 0.04 by modifying only 32% of labels.
  • Information Access: The group-free approach consistently achieved lower ground-truth inequality for a given "seed budget" compared to vanilla reach maximization and even specialized individual fairness baselines.
  • Recommendation: On the Lastfm-Asia network (which has high homophily), the group-free method achieved utility-fairness trade-offs nearly as good as "group-aware" methods that had full access to demographic labels.
  • Failure Case: On the Deezer-Europe network, the method performed poorly for gender fairness. This is because the network was sparse and gender did not drive strong homophily in that specific context, highlighting a key dependency on network structure.

Limitations and Future Work

  • Homophily Dependency: The method only works if the sensitive attribute actually drives network connections. If a network is "heterophilous" (opposites attract) or simply lacks community structure for a specific attribute, the method fails.
  • Hyperparameter Sensitivity: Performance depends on choosing the right embedding dimension ($d$) and kernel function, which can be difficult without ground-truth labels for tuning.
  • Privacy Nuance: While the method doesn't infer discrete labels, it still uses network structure which can be sensitive. It is "privacy-respecting" in that it avoids explicit categorization, but it doesn't offer formal guarantees like Differential Privacy.
  • Future Work: The authors suggest exploring more complex network models (like Graph Neural Networks) to infer similarities and investigating how to handle networks where multiple attributes drive homophily simultaneously.

Summary updated

Abstract

Group fairness is a popular approach to prevent unfavorable treatment of individuals based on sensitive attributes such as race, gender, and disability. However, the reliance of group fairness on access to discrete group information raises several limitations and concerns, especially with regard to privacy, intersectionality, and unforeseen biases. In this work, we propose a "group-free" measure of fairness that does not rely on sensitive attributes and, instead, is based on homophily in social networks, i.e., the common property that individuals sharing similar attributes are more likely to be connected. Our measure is group-free as it avoids recovering any form of group memberships and uses only pairwise similarities between individuals to define inequality in outcomes relative to the homophily structure in the network. We theoretically justify our measure by showing it is commensurate with the notion of additive decomposability in the economic inequality literature and also bound the impact of non-sensitive confounding attributes. Furthermore, we apply our measure to develop fair algorithms for classification, maximizing information access, and recommender systems. Our experimental results show that the proposed approach can reduce inequality among protected classes without knowledge of sensitive attribute labels. We conclude with a discussion of the limitations of our approach when applied in real-world settings.
BibTeX
@inproceedings{liu2023group,
  author = {David Liu and Virginie Do and Nicolas Usunier and Maximilian Nickel},
  title = {{Group fairness without demographics using social networks}},
  booktitle = {FAccT},
  year = {2023},
  url = {https://openreview.net/forum?id=CquGdyqFYj},
}
Figure