A2072
Title: Node ranking on directed graphs under outgoing-link-profile differential privacy
Authors: Wanjie Wang - National University of Singapore (Singapore) [presenting]
Abstract: Node ranking algorithms on directed graphs transform link structure into node importance, influence, and authority. However, a node's outgoing link profile may reveal sensitive preferences, affiliations, or relationships. This work studies outgoing link profile differential privacy, where neighboring directed graphs differ in one node's entire outgoing link profile. The focus is on two canonical ranking algorithms, PageRank and HITS authority scores, with perturbation-guided private mechanisms designed for both. For PageRank, row-level sensitivity is driven by low out-degree nodes. A transition regularization mechanism is introduced that raises small out-degrees, truncates the spectral norm, and then adds calibrated Gaussian noise. For HITS authority scores, perturbation analysis shows that stability is governed by the eigengap of $A^\top A$; this instability is addressed through an eigengap-based propose-test-release mechanism that privately certifies stability before releasing a noisy score vector. For both mechanisms, row-level privacy guarantees and accuracy bounds are proven with trade-off effects on regularization parameters. Numerical experiments show that these methods improve the recovery of top-ranked nodes and reduce relative $\ell_2$ error compared with edge-DP baselines after privacy-budget conversion. This is the first work to develop differentially private algorithms for directed-graph node ranking under outgoing link profile privacy.
