Minimax Optimal PageRank under Row-Level Differential Privacy

PageRank turns directed links into node-importance scores, but a node's outgoing-link profile can encode sensitive behavior. We study differential privacy under replacement of one entire outgoing row on a fixed public node set. We propose two differential private PageRank mechanisms under row-level privacy, i.e., the full outgoing-link profile. Both proposed mechanisms share a regularized query that combines degree flooring with a cap on the mass transmitted by each node. We prove global row-sensitivity bounds and quantify regularization bias. DP PageRank–Full Vector adds calibrated Gaussian noise to release all ranking scores, while DP PageRank–Top $k$ uses Gumbel perturbations to release only the set of top nodes. We provide their utility guarantees as deviation from original non-private PageRank. We also develop lower bounds. The lower bounds match the upper bounds of our algorithms for dense networks, under both score estimation and the top-$k$ set recovery. Numerical studies on three real datasets and simulated networks further support the overwhelming superiority of our mechanisms.