Research map / Learning theory and algorithms / Fairness

Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity

NeurIPS 2025 · Learning theory and algorithms › Fairness · approach: Fairness-constrained classification · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces Fair Minimum Labeling (FML), a temporal edge-activation design problem with group-wise reachability quotas; proves hardness, gives tree-embedding (FRT and shortest-path-tree) approximation algorithms for the two-group single-terminal case, and evaluates them on synthetic and Pokec graphs.

Problem

Designing minimum-cost temporal edge activation plans so that each node group has enough nodes temporally reaching a designated target set, under per-group coverage requirements.

Approach

Shows that the single-terminal case is equivalent to rooted Covering Steiner, and solves the two-group case via FRT tree embeddings with an exact tree DP (and a bucketed bicriteria variant), plus a graph-native shortest-path-tree reduction that prunes to a colored core.

Key results

• On Pokec at 20,000 vertices, SPT--Bounded runs in 13.58 s versus 50.80 s for FRT--Bounded (3.74x faster) with lower cost in all 40 paired trials (385.8 vs 635.4).
• In the multi-source learning experiment, the group-agnostic baseline reaches accuracy gap 0.588 (0.996 vs 0.408), while group-aware methods keep gaps around 0.03-0.04 at roughly 68-88 activation cost.
• Increasing the relaxation parameter to 0.40 reduces FRT--Bounded solver time by 19.1% and activation cost by 17.7%, at the price of about 17.5% lower minimum group coverage.

Measured effects reported in the paper

Surprising findings

• The group-agnostic baseline has the lowest activation cost (64.0) yet yields a large accuracy gap, showing low aggregate cost does not ensure representative data.
• PD--Strict has lower cost than the FRT-based exact method in the multi-source experiment (68.0 vs 75.3), despite having no proven approximation guarantee.

Limitations

• Theoretical guarantees cover only the two-group single-terminal case; multi-terminal and multi-group tree DPs are exponential in the number of groups.
• The SPT variant has no worst-case approximation guarantee; its stretch is only a diagnostic.
• Experiments use unit edge costs and small synthetic or single real graph instances, with a limited number of trials.

Experimental setup

Datasets: Pokec social network synthetic random geometric graphs synthetic Barabási–Albert graphs

Benchmarks: Pokec scalability (20,000 vertices) multi-source learning (random geometric graph, 1,024 vertices) Barabási–Albert sensitivity study

Metrics: activation cost runtime group coverage classifier accuracy accuracy gap between groups

Baselines: PD--Strict PD--Matched Covering Steiner Closest Alternating Group-Agnostic

Builds on: Minimum Labeling Minimum Steiner Labeling FRT tree embedding Covering Steiner problem Garg 2-approximation for k-MST

Closest papers by meaning

• Fair Graph U-Net: A Fair Graph Learning Framework Integrating Group and Individual Awareness (AAAI 2025 · similarity 0.84)
• Fair Resource Allocation in Multi-Task Learning (ICML 2024 · similarity 0.84)
• FairGP: A Scalable and Fair Graph Transformer Using Graph Partitioning (AAAI 2025 · similarity 0.84)
• Chasing Fairness in Graphs: A GNN Architecture Perspective (AAAI 2024 · similarity 0.84)
• Approximating Optimal Labelings for Temporal Connectivity (AAAI 2025 · similarity 0.84)
• FairMT: Fairness for Heterogeneous Multi-Task Learning (NeurIPS 2026 · similarity 0.83)