CS Paper Radar

Fair Top-k Katz Centrality via Graph Design

Ivan Qin, Prudence Wong, Lutz Oettershagen

cs.SI ·submitted 2026-09-03 14:18 UTC · v1

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Link prediction in complex networks via fusing node centrality and local similarity indices: a fair-protocol reassessment and parameter design principles

cs.SI ·2026-09-09 ·Yingying Zhang, Chengye Zhao
benchmark similarity 0.64
Abstract · 34 pages, 13 tables, 6 figures, 50 references

We reassess a published fusion method under a fair protocol. Local similarity indices are cheap but score every node pair without common neighbors zero, and weighting them by a node centrality product, as proposed for PageRank, is not robust once the protocol is made comparable across indices; on our eight-network panel the reported improvement does not survive that protocol for six of the seven local indices. We study these issues in a unified piecewise framework that modulates the local score multiplicatively by a centrality product when local information suffices and uses a small-dose centrality product as a completion term when it does not. A scale analysis and a reassessment on eight real-world networks (five-fold cross-validation, exhaustive negative samples) trace this to the O(n^-2) scale of the PageRank product, whose modulation factor is then a near-identity map, and to its rank correlation with degree exceeding 0.89; control arms show scale calibration is necessary but not sufficient. The min-max normalized DomiRank product instead has an O(1) range and substantial non-degree content, and a grid search yields unified parameters (omega=5, c=0.1) under which DR-JC/HPI/SO significantly outperform their local baselines already at the dataset level (p=0.027 and 0.035), the remaining four at the fold level only; DR-RA attains an average AUC of 0.9257, above nine of ten comparison methods, whereas degree-only preferential attachment reaches only 0.7736. Mechanism decomposition shows the two mechanisms contribute differently across index families and should be dosed separately, yielding a safety boundary 0 < c <= 0.3, a plateau omega in [0.5, 12] and a near-critical plateau sigma in [0.7, 0.95]. Two negative results bound the claim: under a degree-corrected benchmark the gains over local baselines vanish and reverse in sign, and the AUC gains do not translate into top-L hit rate.

0.16

Target PageRank: Matching Prescribed PageRank Scores via Budgeted Edge Additions

cs.SI ·2026-11-04 ·Parth Gupta, Abhinav Jain, Avishek Mukhopadhyay, Amitabha Bagchi, Sayan Ranu +1 more
similarity 0.63
Abstract · 16 pages, 12 figures

PageRank is widely used to quantify the importance of nodes in directed networks. In applications such as recommendation systems, it is increasingly important that the PageRank distribution provides a fair representation of node exposure. This motivates the problem of making minimal changes to a graph so that the PageRank values of a given set of target nodes $T$ match a desired vector $\boldsymbol{t}$. In this paper, we study this problem under an edge-addition budget $B$, where exactly $B$ edges may be added to the graph. We show that deciding whether a multiset of exactly $B$ added edges can make the target nodes attain their desired absolute PageRank scores is NP-complete. After this, we define the $\ell_1$ Target PageRank problem in which we seek to minimize the $\ell_1$ distance between the target vector and resultant vector. We show that this optimization problem admits no polynomial-time multiplicative constant-factor approximation unless $P=NP$. Motivated by these hardness results, we propose two greedy heuristics for approaching the target PageRank vector. We additionally propose a Random Walk Hungarian (RWH) heuristic that addresses the addition of edges between dissimilar nodes by incorporating a penalty for such edges. Finally, we evaluate the proposed heuristics on several real-world and synthetic datasets and compare their performance in terms of PageRank accuracy, computational efficiency, and the relevance of the added edges.

0.17

Semi-Monotonicity for Spectral Centrality Measures

cs.SI ·2026-09-21 ·Paolo Boldi, Davide D'Ascenzo, Flavio Furia, Sebastiano Vigna
theory similarity 0.61
Abstract

Score monotonicity and rank monotonicity are properties describing the behavior of a centrality measure when an arc is added to a network: the former requires that the score of the target of the arc should increase, the latter that its importance with respect to the remaining nodes should not deteriorate. While in directed networks almost all classical centrality measures satisfy both properties, in undirected networks they fail for most measures: adding an edge can reduce the score or the rank of one of its endpoints. Semi-monotonicity is a recently introduced weaker property for undirected networks, requiring that at least one of the two endpoints of the new edge enjoys monotonicity, and it is known to hold for closeness, harmonic centrality, distance-decay centralities and betweenness. In this paper we study semi-monotonicity for three classical spectral centrality measures: eigenvector centrality, Katz's index, and PageRank. We prove that all of them are strictly rank semi-monotone on connected undirected graphs, and that all of them are also score semi-monotone, (the only exception being eigenvector centrality when scores are normalized by projecting the constant vector on the dominant eigenspace, for which we provide a counterexample). In particular, adding an edge can never decrease the PageRank of both its endpoints, which answers a question left open in previous work.

0.19

Rewiring the Majority: Structural Median Opinion Control in the Friedkin-Johnsen Model

cs.SI ·2026-10-15 ·Elisabetta Biondi, Chiara Boldrini, Andrea Passarella, Marco Conti
similarity 0.60
Abstract · 11 pages,5 figures

Opinion control under the Friedkin-Johnsen (FJ) model has traditionally focused on modifying individual users, for example by changing their opinions or susceptibility to social influence. We study a complementary problem: can collective outcomes be steered by modifying the interaction network instead? We formulate structural median control as an edge-addition problem aimed at moving the equilibrium median beyond a target threshold. We show that the problem is NP-hard even under highly restricted settings and propose both continuous optimization methods and computationally lighter opinion-aware heuristics for selecting edge additions. Experiments on synthetic and real-world networks reveal that intervention success depends jointly on network topology, the placement of favorable opinions, and user susceptibility. Structural interventions produce the largest shifts when opinion placement and network structure allow added edges to create useful influence pathways toward the target outcome. Finally, under a homogeneous reference setting, we compare structural and node-level interventions using normalized budgets and a degree-weighted cost model. We show that, although node interventions often appear stronger under normalized budgets, structural interventions become competitive and frequently more cost-effective once the higher cost of targeting high-reach users is taken into account.

0.26

Minimum Membership Dominating Set and Its Generalization: Leafage vs. Asteroidal Number

cs.DS ·2026-11-10 ·Yuma Tamura, Daichi Wakayama, Akira Suzuki, Xiao Zhou
published similarity 0.58
Abstract · Accepted for publication in IPEC2026

The Dominating Set problem is known to be fixed-parameter tractable when parameterized by leafage, a structural graph parameter defined on chordal graphs. We investigate whether this tractability extends to its variants with natural constraints. Specifically, we study the Minimum Membership Dominating Set problem and its generalization, the Min. $(σ, ρ)$-Dominating Set problem. Given a graph $G$ and a positive integer $\ell$, Minimum Membership Dominating Set asks whether there is a dominating set $D$ such that every vertex in $G$ is dominated by at most $\ell$ vertices in $D$. We first show a negative result: Minimum Membership Dominating Set parameterized by leafage plus $\ell$ is W[1]-hard, demonstrating that even this natural constraint serves as a severe barrier to designing FPT algorithms. To complement this, we present an XP algorithm for the Min. $(σ, ρ)$-Dominating Set problem parameterized by asteroidal number plus $μ$, where $σ$ and $ρ$ are finite sets of non-negative integers and $μ$ is the maximum value in $σ\cup ρ$. Note that asteroidal number generalizes leafage to arbitrary graphs. Combining this algorithm with our structural bound that every graph $G$ admits a dominating set such that no vertex is dominated by more than $7\mathsf{an}(G)-6$ vertices, where $\mathsf{an}(G)$ denotes the asteroidal number of $G$, we show that Minimum Membership Dominating Set admits an XP algorithm parameterized solely by asteroidal number.

0.32

Close and Sort: Exact Maximum-Likelihood Aggregation of Cyclic Rank-Two Preferences

cs.DS cs.IRcs.LGstat.ML ·2026-11-07 ·Kehan Liu, Zhaoyun Chen, Xianquan Yan
publishedcode/data similarity 0.57
Abstract · 10 pages, 3 figures, 5 tables. Accepted at the 20th ACM International Conference on Web Search and Data Mining (WSDM 2027). Code: https://gi…

Pairwise probabilities arise in rank aggregation, recommendation, and human or LLM evaluation, yet converting them into a maximum-likelihood list is a weighted Kemeny problem and is NP-hard in general. Known exact algorithms for rank-two tournaments use only comparison signs and do not optimize this likelihood. We show that the weighted problem is exactly solvable when the skew-symmetric log-odds matrix $W_{ij}=\log(p_{ij}/p_{ji})$ has rank two, including when the induced preferences contain cycles. Writing $W_{ij}=\det(h_i,h_j)$ and adding the closing vector $h_0=-\sum_i h_i$ turns the objective into twice the signed area of a closed polygon. This geometry yields CloseSort, which polar-sorts the $n+1$ edge vectors, cuts after $h_0$, and returns a global maximum-likelihood order in $O(n\log n)$ time from the factors. The same geometry identifies the runner-up and gives a stability certificate beyond exact rank two. When the smallest determinant $δ$ of two consecutive edges in the closed angular cycle is positive, it is exactly the best-to-runner-up log-likelihood gap. For $W=W_0+E$, the CloseSort order of $W_0$ has regret at most $\sum_{i<j}|E_{ij}|$ on $W$ and remains optimal whenever this sum is below $δ$, a worst-case tight threshold. In 5,120 determinant-logit simulations, increasing the observations per pair from 4 to 64 raises the fraction on which rank-two projection outperforms the empirical plug-in optimum from 68.6% to 85.7%. On 3,600 Arena-Hard LLM-judge profiles drawn from 63 systems and ten judges, the leading rank-two component captures 89.2% of the log-odds energy. On profiles containing a directed majority triangle, CloseSort reduces normalized regret by 44% relative to Borda and improves the mean normalized objective over each of eight baselines. With factors supplied, it is 8,407 times faster than exact dynamic programming on 18-item rankings.

0.52

Fair Bubble Sort: Provably Optimal Fair Ranking with Continuous Sensitive Attributes

cs.LG cs.CYcs.DS ·2026-11-17 ·Antonio Ferrara, Fabio Vitale, Atsushi Miyauchi, Francesco Bonchi
top venuetheorycode/data similarity 0.57
Abstract · 35 pages, 9 figures, 4 tables. Accepted at NeurIPS 2026. Code: https://github.com/Ambress92/FairBubbleSort

Most fair-ranking methods assume categorical protected attributes, requiring continuous attributes such as age or income to be discretized into groups. This introduces arbitrary thresholds, loses fine-grained information, and ignores the natural ordering of the attribute. In this paper, we study the problem of fair ranking with continuous protected attributes without relying on thresholding. We introduce Continuous Pairwise Parity (CPP), a fairness notion based on Kendall correlation between ranking positions and the protected attribute, and seek rankings that satisfy a prescribed CPP constraint while minimizing their Kemeny distance from an initial score-based ranking. To solve this problem, we propose Fair Bubble Sort (FBS), an efficient post-processing algorithm based on targeted adjacent swaps. We prove that FBS is exactly optimal for the unweighted Kemeny distance and provide approximation guarantees for the score-weighted setting. FBS is output-sensitive, with running time determined by the number of swaps required to meet the fairness constraint. Experiments on synthetic and real-world datasets show that FBS is scalable and consistently outperforms discretization-based baselines, achieving a superior fairness-accuracy Pareto front.

0.54

PreGress: Ranking-Native Pre-training and Prompting for Graph Node Ranking

cs.IR cs.LG ·2026-08-10 ·Lujie Ban, Jiasheng shi, Yingli Zhou, Kaiwen Xue, Daiyin Wang +3 more
similarity 0.57
Abstract

Node ranking is a fundamental problem in graph information retrieval, measuring the relative importance of nodes and supporting a wide range of applications such as influence analysis, recommendation, and graph-based retrieval augmented generation. However, exact computation of graph-based ranking measures is often computationally prohibitive at scale. Existing GNN-based ranking methods provide scalable approximations, but they are typically tailored to individual ranking criteria and require retraining for each downstream task, which limits their transferability and efficiency. Recent graph pre-training approaches aim to enable knowledge transfer across tasks, yet their learning objectives are largely misaligned with node ranking, resulting in suboptimal adaptability to ranking-oriented applications. To address these limitations, we propose PreGress, the first ranking-native pre-training and prompting framework for supporting a wide range of node ranking tasks. PreGress performs multi-task pre-training using our carefully designed objectives, including degree centrality prediction and attribute reconstruction, to jointly capture structural and attribute information. To support heterogeneous ranking criteria, we design lightweight, task-specific prompt modules that adapt a frozen ranking backbone to downstream tasks without full retraining. Experiments on six public graphs and two real-world query-to-item benchmarks---Yelp2018 and MovieLens-100K---together with a controlled five-criterion graph-access study demonstrate strong ranking quality with low task-specific state overhead.

0.04