Source-linked AI summary
Fair Top-k Katz Centrality via Graph Design
Ivan Qin, Prudence Wong, Lutz Oettershagen
TL;DR
Fairness interventions for graph centrality often target score mass or modify the scoring rule rather than the composition of the displayed top-k set. This paper formalizes minimum-edit Katz top-k design, develops a boundary-focused scalable algorithm, and establishes strong inapproximability of the objective.
Problem
Fairness interventions often do not directly control which groups appear in a displayed Katz top-k ranking, even though group centrality mass below the cutoff may be substantial.
Source: §1 · p. 1Method
The paper derives Katz sensitivity expressions for boundary-crossing pairs and develops BLADE, which uses score-based direct-target batches and warm-started Katz updates.
Source: §1 · p. 2, §5.1 · p. 4Results
The minimum-edit problem admits no polynomial-time constant-factor approximation unless P = NP.
Source: §1 · p. 2Takeaways & Limitations
Top-k representation changes can be targeted through boundary exchanges, and BLADE retains this principle while avoiding dense Katz-kernel maintenance.
Source: §1 · pp. 1–2Graph edits can alter individual exposure and opportunity, and the method should not be the sole basis for high-stakes decisions.
Source: Ethical Considerations · p. 10
Abstract
from arXiv · showhide
Centrality measures are widely used to rank nodes in networked data, but fairness interventions for graph centrality typically target global score mass or modify the centrality operator rather than controlling who appears in the displayed top-k ranking. We study this top-k setting for Katz centrality. Given a target group proportion, an admissible set of directed edge additions, and a fairness tolerance, the goal is to find the smallest edit set whose resulting Katz top-k ranking satisfies the target representation constraint. We formalize this problem as Fair Top-k Katz Centrality Design and show that the minimum-edit objective is strongly inapproximable, ruling out worst-case polynomial-time approximation guarantees unless P = NP. We then derive closed-form Katz sensitivity expressions showing that useful edits are boundary-driven: they must help promotable nodes outside the top-k set overtake opposing nodes inside it. Based on this structure, we develop BLADE, a scalable boundary-link algorithm that avoids dense Katz-kernel maintenance by using score-based direct-target batches and warm-started Katz updates. Experiments on synthetic and real-world networks show that BLADE reaches the desired top-k representation using far fewer edits than natural baselines, while scaling to large real-world graphs and preserving the original ranking structure.
1 Introduction
The paper targets representation in the displayed Katz top-k set, where changing group-wide score mass alone may not change which nodes cross the selection cutoff. It formulates a minimum-edit graph-design problem and develops a boundary-focused method for achieving a target composition.
1 Introduction
- Top-k fairness concerns the displayed group composition: substantial group centrality mass below the cutoff may still leave that group nearly absent from the selected nodes.Representation changes when nodes cross the selection boundary, so improving aggregate centrality alone is not generally sufficient.Source: §1 · p. 1
- The Fair Top-k Katz Centrality Design Problem seeks the smallest set of admissible directed edge additions that brings the Katz top-k ranking within a target group-proportion tolerance.The intervention changes the graph while keeping the ranking mechanism fixed.Source: §1 · pp. 1–2
- Katz sensitivity analysis identifies useful edits by whether they help promotable nodes outside the top-k overtake opposing nodes inside it.The relevant score changes are therefore tied to boundary gaps, not global score redistribution.Source: §1 · pp. 1–2
- BLADE preserves boundary-exchange logic while using score-based direct-target batches and warm-started Katz updates instead of dense Katz-kernel maintenance.The paper also describes a dense frontier-search reference algorithm based on exact pairwise differential gains.Source: §1 · p. 2
- The minimum-edit objective is strongly inapproximable, ruling out polynomial-time constant-factor approximation guarantees unless P = NP.The paper also derives exact Katz sensitivity formulas for directed edge additions.Source: §1 · p. 2
- Across synthetic and real-world networks, BLADE reaches the target top-k representation with few edits while preserving ranking stability.The evaluation includes million-node graphs.Source: §1 · p. 2
2 Related Work
Prior fairness work intervenes on ranked lists, scoring rules, centrality mechanisms, or graph structure. This paper's objective is the discrete group composition of a Katz top-k ranking under a minimum-cardinality set of edge additions.
2 Related Work
- This work differs by seeking a prescribed group composition in a Katz top-k set using the minimum-cardinality set of edge additions.It intervenes on graph structure rather than post-processing the ranking or modifying the centrality rule.Source: §2 · p. 2
- Fair ranked-list methods commonly constrain prefixes or alter exposure, attention, or scoring rules on fixed scores or rankings.FA*IR and extensions enforce group-fairness constraints on prefixes of top-k rankings [48].Source: §2 · p. 2
- Fairness work for PageRank and related centrality scores modifies operators, transitions, or edges, while other studies examine drivers of minority representation among highly ranked nodes.The cited factors include homophily, group mixing, observation bias, and network growth [29] [34] [38].Source: §2 · p. 2
- Graph interventions have addressed fairness in downstream tasks including clustering, link prediction, recommendation, representation learning, and information flow.Network-design work has also sought to improve designated nodes' centrality or ranking positions [5].Source: §2 · p. 2
3 Preliminaries and Problem Definition
The paper defines Katz top-k representation and an edge-addition design objective, then establishes that minimizing edits is strongly inapproximable. The model works in a Katz-valid regime and specifies deterministic tie handling.
3 Preliminaries and Problem Definition
- Katz centrality is defined through a kernel that aggregates discounted directed walks, and the top-k fairness measure is the squared deviation between protected-group share and its target.The objective is zero at the target and treats over- and under-representation symmetrically.Source: §3 · p. 3
3.1 Graph Design Model
- The graph-design model minimizes the number of admissible directed edge additions needed to reach a fairness tolerance, with Katz-valid parameters maintained throughout edits.The top-k set contains exactly k nodes, with ties broken deterministically and fairness used to resolve equal-score alternatives.Source: §3.1 · p. 3
3.2 Hardness
- No polynomial-time constant-factor approximation exists unless P = NP, even for α = 1/2 and directed acyclic input graphs.The proof uses a gap-preserving reduction from Independent Set on 3-regular graphs; the associated threshold decision problem is NP-hard.Source: §3.2 · p. 3
4 Structural Properties of the Katz Kernel
The paper derives closed-form score changes for directed edge additions and uses pairwise differential gains to analyze ranking changes. These expressions motivate focusing on which nodes can cross the top-k boundary.
4 Structural Properties of the Katz Kernel
- A single directed edge addition has a closed-form marginal Katz update, allowing candidate edges to be scored without recomputing the kernel from scratch.The score boost depends on the tail's Katz score, head-to-target kernel proximity, and feedback amplification.Source: §4 · p. 3
- Promoting a node requires increasing its score relative to nodes it must overtake, motivating differential rather than absolute gains.A positive differential gain reduces the current pairwise gap; accumulated gain at least equal to that gap closes it.Source: §4 · pp. 3–4
- The differential gain factors into a positive edge-dependent scalar and a kernel gap determined by the head node and target pair.The head determines the gain's sign through relative discounted-walk weights, while the tail affects magnitude but not sign.Source: §4 · p. 4
5 Frontier-Guided Algorithms
The algorithms target fairness changes at the top-k boundary rather than reshaping Katz scores globally. They use exact boundary-gap search as a reference and develop BLADE to search more scalably without maintaining a dense Katz kernel.
5 Frontier-Guided Algorithms
- No polynomial-time algorithm can provide approximation guarantees for the Fair Top-k Katz Centrality Design Problem unless P = NP.The paper therefore targets practical efficiency with frontier-guided algorithms focused on pairs whose relative order can change top-k group composition.Source: §5 · p. 4
5.1 Top-𝑘Frontier Principle
- A frontier pair matches a promoted node outside the top-k with an opposing node inside it; closing their score gap is the local operation for changing group composition.The frontier can be windowed by ordering outside candidates by decreasing Katz score and inside opposing nodes by increasing score.Source: §5.1 · p. 4
5.2 Dense Frontier Search
- Dense greedily tests positive-gain edits for frontier pairs and commits prefixes that improve the fairness objective or reduce the targeted gap without worsening fairness.Its exact kernel-based gains and tentative updates with rollbacks make it a small-graph reference method.Source: §5.2 · p. 4
5.3 Blade: Scalable Boundary-Link Search
- BLADE avoids dense-kernel gains by considering actionable promoted candidates near the boundary and building direct-target edge batches from high-score sources.It anchors gap estimates on the lowest-scoring opposing node currently in the top-k, then updates Katz scores with warm-started Jacobi iterations after committing a batch.Source: §5.3 · pp. 4–5
- BLADE's proxy uses the tail node's Katz score but ignores kernel amplification and spillover to the opposing boundary node.It never overestimates the direct score increase of the target, but may overestimate or underestimate differential gain against the opposing node.Source: §5.3 · p. 5
- With q=2, BLADE can choose a one-edge promotion for z instead of spending two edges to promote y with q=1.The figure's q=1 choice uses edges (w,y) and (x,y), while q=2 also evaluates z and selects (u,z).Source: Figure 2 · p. 5, §5.3 · p. 5
5.4 Complexity
- BLADE uses O(n + m) space and avoids dense kernel maintenance, tentative rollbacks, and scans over all admissible edges.Each outer round includes score sorting, candidate and source scanning, and warm-started Jacobi updates.Source: §5.4 · p. 6
6 Experiments
Experiments assess edit efficiency, scalability, and sensitivity. BLADE reaches the target on all six real-world networks and offers a scalable alternative to exact and dense boundary methods.
6.1 Experimental Setup
- Real-network experiments use k=100, parity, and zero tolerance; the unconstrained edge set includes all missing directed non-self-loops, alongside a local two-hop alternative.The unconstrained set is an algorithmic benchmark, not a claim that every missing edge is a valid deployment intervention.Source: §6.1 · p. 7
6.2 Results
- On small synthetic instances, Blade reaches every tested target, runs orders of magnitude faster than exact Opt, and uses only a few additional edits.Opt gives the fewest edits when it finishes, but begins timing out as graph size increases.Source: Figure 3 · p. 7, §6.2 · p. 7
- Blade’s batching preserves edit counts while making it about 5.1× faster on Penn and 5.9× faster on Pokec than Blade-NoBatch.Blade stays within the one-hour limit on all six real-world datasets; it takes 25.77 seconds on Penn and 101.09 seconds on Pokec.Source: §6.2 · p. 8
- On all six real-world networks, Blade reaches zero final unfairness at parity, while baselines are substantially less reliable.The evaluation uses k=100, a 50% protected-group target, and zero tolerance.Source: §6.2 · p. 7, Table 2 · p. 8
- With two-hop admissibility, Blade reaches the target on all six real-world datasets, requiring 5,601 edits versus 5,546 with unconstrained additions.Three datasets require exactly the same number of edits in both settings.Source: Table 3 · p. 8, §6.2 · p. 8
- After intervention, mean Overlap@100 is 0.85, shared-node Kendall τ averages 0.975, and full-ranking Spearman correlation exceeds 0.9999 on every dataset.Kendall τ is at least 0.943 among nodes shared by the original and post-intervention top-100 sets.Source: §6.2 · p. 8, Table 5 · p. 9
- Wider boundary search reduces mean edits from 2.60 at q=1 to 2.20 at q=2 and 1.00 at q≥5 in planted instances, with no real-world edit-count change beyond q=2.These planted instances deliberately make the highest-scoring candidate not the cheapest to promote.Source: Figure 4 · p. 9, §6.2 · p. 9
- Across tested cutoffs, edit ratios stay low and around 1% even at the largest k; edit costs also depend chiefly on the gap between the target and initial group composition.For example, Hopkins needs 87 edits for π=0.5 and 483 for π=0.3; Blogs needs 4 and 606, respectively.Source: §6.2 · pp. 8–9, Figure 5 · p. 9
7 Conclusion
The paper frames fair top-k Katz ranking as minimizing admissible edge additions to reach a target group representation, and presents BLADE as a scalable intervention. Experiments report that it achieves the target with few edits while preserving ranking stability.
7 Conclusion
- The Fair Top-k Katz Centrality Design Problem minimizes admissible edge additions needed to achieve target group representation in the Katz top-k set.The paper also reports strong hardness results and derives Katz sensitivity formulas.Source: §7 · p. 9
- Experiments show that BLADE improves top-k representation with few edits relative to graph size while preserving ranking stability.The paper identifies extending the framework to other centrality measures, multi-group targets, and richer graph interventions as future work.Source: §7 · p. 10
Ethical Considerations
Graph edits can improve aggregate group representation while changing individuals’ exposure and opportunity. The paper flags assumptions about group labels, targets, and permissible interventions as potential privacy, consent, and governance concerns.
Ethical Considerations
- Graph edits can alter individual exposure and opportunity even when aggregate group representation improves.The formulation assumes legitimate access to group labels, target proportions, and admissible interventions; the authors advise against using the method as the sole basis for high-stakes decisions.Source: Ethical Considerations · p. 10
- The authors recommend stakeholder-defined targets, consented and application-valid edits, audits of individual and subgroup outcomes, and human oversight.Source: Ethical Considerations · p. 10
A Omitted Proofs
The omitted proofs use a reduction from Independent Set on 3-regular graphs to establish hardness for the fair top-k Katz design objective. The proof also establishes that checking a proposed edit set is polynomial-time, while threshold decision remains NP-hard.
A Omitted Proofs
- In the reduction, selecting an independent set of size ℓ yields exactly ℓ red candidates in the top-k positions below the selector tails.If no independent set of size ℓ exists, every feasible edit set has size at least Q.Source: A Omitted Proofs · pp. 11–12
- The gap construction implies that no polynomial-time ψ-approximation exists unless P = NP.The proof distinguishes YES instances, where a solution is smaller than Q, from NO instances, where every feasible solution is at least Q.Source: A Omitted Proofs · p. 12
- Given an edit set, feasibility can be checked in polynomial time, but distinguishing OPT_ε ≤ ℓ from OPT_ε ≥ Q is NP-hard.Thus the threshold decision problem is NP-hard.Source: A Omitted Proofs · p. 12
B Population-Proportional Targets
The appendix reports population-proportional target results for six datasets. Its table notes distinguish Katz and PageRank rankings and identify timeout and memory-limit cases.
B Population-Proportional Targets
- Katz and PageRank methods use different rankings, so their initial top-k group counts can differ.The table notes mark one-hour limits as OOT and insufficient-memory termination as OOM; Penn and Pokec GapGreedy runs also have specified timeout handling.Source: B Population-Proportional Targets · p. 13
- Population-proportional target results are tabulated for Blogs, Hopkins, Retweet, Deezer, Penn, and Pokec.The supplied captions identify the table scope but do not provide outcome values.Source: Table 8 · p. 14, Table 9 · p. 14, Table 10 · p. 14