Target PageRank: Matching Prescribed PageRank Scores via Budgeted Edge Additions

Abhijnan Chakraborty; Abhinav Jain; Amitabha Bagchi; Avishek Mukhopadhyay; Parth Gupta; Sayan Ranu

REVIEW

Target PageRank: Matching Prescribed PageRank Scores via Budgeted Edge Additions

Parth Gupta, Abhinav Jain, Avishek Mukhopadhyay, Amitabha Bagchi, Sayan Ranu, Abhijnan Chakraborty

Social and Information Networks · Submitted 4 Nov 2026

Pith's verdict: Solid theoretical results (NP-completeness and inapproximability) for a novel PageRank manipulation problem; heuristics are reasonable but lack optimal baseline comparison. Worth publishing with minor revisions.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on November 6, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 6 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2611.06782 (version 3)

Pith IDTJEZVWNX, Pith's permanent record of this paper and its review

CitationAbhijnan Chakraborty, Abhinav Jain, Amitabha Bagchi, Avishek Mukhopadhyay, Parth Gupta, Sayan Ranu. "Target PageRank: Matching Prescribed PageRank Scores via Budgeted Edge Additions." arXiv:2611.06782 (2026). https://pith.science/paper/TJEZVWNX

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

The main thing to know about this paper is that the hardness results are rigorous and the problem formulation is genuinely new. Target PageRank — matching prescribed absolute PageRank scores on multiple target nodes under an exact edge-addition budget — hasn't been studied before, and the authors prove NP-completeness and constant-factor inapproximability with clean reductions. The proofs are solid: the gadget construction is carefully parameterized, the parameter x is explicitly shown to satisfy the required inequalities, and the NP-membership verification via exact rational linear algebra is a nice touch. The inapproximability proof is a correct gap reduction. The MILP formulation is exact but acknowledged to be unscalable.

The heuristics (G1, G2, RWH) are well-motivated and the experimental evaluation on Amazon datasets is thorough, with sensitivity analysis on key hyperparameters. The paper honestly discusses when each heuristic works best and why (e.g., RWH loses advantage on the Clothing dataset due to extreme hubs).

Soft spots: The experiments never compare against the optimal solution, even on small graphs where the MILP could run. The authors list this as future work, but it leaves a gap in judging how far from optimal the heuristics are. The free parameters (k, ou, hl, c, β) are tuned via grid search, but there's no discussion of sensitivity beyond the sweet-spot plots; a reader might wonder how robust the results are to choices outside the search range. Finally, no error bars or statistical tests are reported, which is a minor weakness for an empirical section.

These concerns are proportionate: the theoretical contribution stands independently, and the heuristics are presented as practical approximations, not optimal solutions. The paper is honest about its limitations.

This paper is for the computational social systems / network science community, especially anyone working on PageRank manipulation, fairness in recommendation, or graph design. It deserves a serious referee. I would accept after minor revisions — ideally, a small-scale MILP comparison on graphs with 10–20 nodes to calibrate heuristic quality, though this is not a deal-breaker.

Referee report

Minor objections (6)

[Section 11 (Proof of Theorem 2)] The paper asserts that the inapproximability result 'holds for every ℓ_k-norm with 1 ≤ k ≤ ∞' without proof or justification. While the gap reduction for ℓ1 extends trivially to any norm that yields zero error only for exact equality, the claim should be either briefly justified or modified to avoid overstatement.
[Section 8 (Experimental Evaluation)] The experimental results lack error bars or statistical significance tests. Adding standard deviations over multiple runs (where applicable) or at least stating that results are reported for specific hyperparameter choices would improve confidence in the comparisons.
[Section 8.5.2 (Variation With ou)] The paragraph explaining the 'sweet spot' in ou is insightful but would benefit from a more quantitative discussion, e.g., noting how the optimal ou relates to the fraction of over-/under-exposed nodes in the dataset.
[Section 5 (G1 Algorithm)] Typo: 'pagerank traffic' should be 'PageRank traffic'; also 'the the' appears in Section 8.5.2 (line after Fig. 8 caption) – please proofread.
[Section 8.4.2] The average similarity metric is defined but the reference item embeddings are not described in full detail; reproducibility would be improved by citing or briefly specifying the embedding method used.
[Section 9 (Conclusion)] The paper mentions future work to compare against the optimal MILP solution on smaller graphs; this is a sensible path and acknowledging the limitation now is appropriate.

How Pith checks papers → · Full audit of this paper → · Review history (2 revisions) →

The paper

The paper claims

Deciding whether B edge additions can set prescribed PageRank scores is NP-complete.

The reading

The paper studies the problem of modifying a directed graph by adding exactly B edges so that the PageRank scores of a chosen set of target nodes match a given target vector. It proves that the decision version is NP-complete and that the natural ℓ1 optimization version admits no polynomial-time constant-factor approximation unless P = NP. This establishes fundamental computational limits for link-structure engineering to achieve specified PageRank outcomes, a problem motivated by fairness and exposure control in recommendation systems. In response, the paper develops three heuristics that trade off accuracy, computational cost, and edge relevance, and evaluates them on real-world and synthetic networks.

What carries the argument

The central machinery for hardness is a gadget graph (Figure 12) with m item nodes and c center nodes, where the target PageRank scores on the centers encode a balanced partition constraint. The proof relies on the concept of sum-optimal addition multisets (each item node sends exactly one outgoing edge to some center), and uses the linear PageRank equations to relate center PageRank to group mass from items. A key step is selecting a parameter x such that two strict inequalities hold, ensuring that only sum-optimal additions can achieve the target scores and that the desired proportionality conditions are equivalent to a balanced partition. For the optimization variant, the gap reduction uses the same gadget: any constant-factor approximation can distinguish zero from positive ℓ1 error. On the algorithmic side, the heuristics use exposure-bias definitions (difference between current and target PageRank) and random-walk centrality scores to identify cluster centers, combined with min-cost matching for edge selection.

Extended reading notes

Core claim

The paper shows that the 'Target PageRank' problem—determining whether exactly B edge additions can achieve a prescribed absolute PageRank vector on a target node set—is NP-complete. The proof uses a reduction from a generalized balanced partition problem via a gadget graph whose center nodes encode the target scores, exploiting linear relations between center PageRank and the total group mass from item nodes. For the ℓ1-minimization variant, the paper proves that no polynomial-time algorithm can achieve any finite multiplicative approximation factor unless P = NP, using a gap reduction that detects zero-error solutions. This strong inapproximability holds for all ℓ_k norms. Motivated by this hardness, the authors propose heuristics: simple exposure-bias matching (G1), greedy score-based selection (G2), and a random-walk Hungarian method (RWH) that incorporates node similarity. Experiments on Amazon product-review networks show that all heuristics reduce ℓ1 error, with RWH offering the best trade-off between error and edge relevance.

Load-bearing premise

The NP-completeness reduction assumes a fixed damping factor α and that the gadget parameter x can be chosen to satisfy two strict inequalities derived from the instance; if these inequalities cannot be satisfied for a given α or if the instance sizes are too small, the reduction may not apply.

Editorial extensions

If this is right

Exact or constant-factor approximate solutions to Target PageRank are computationally intractable in general (unless P = NP), so practical applications must rely on heuristics or additive approximations.
The NP-completeness result extends to the variant where fewer than B edges are allowed (Corollary 1), and to all ℓ_k norms (Theorem 2), broadening the scope of the hardness.
The MILP formulation provides an exact but potentially expensive method for small instances, useful for benchmarking heuristics.
The heuristics demonstrate that substantial reductions in ℓ1 error are achievable on real-world recommendation networks, with the Random Walk Hungarian (RWH) heuristic offering the best trade-off between error and edge similarity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the gadget construction could be adapted to other centrality measures (e.g., HITS or eigenvector centrality), similar hardness results might hold, suggesting that many network design problems with prescribed scores are inherently hard.
The paper's inapproximability result does not rule out additive approximations; future work could characterize the best achievable additive error in polynomial time.
The heuristics' reliance on exposure bias and random-walk clustering could inspire new approaches for other graph-modification problems, such as controlling PageRank fairness or combating opinion manipulation.
The experimental comparison on Amazon datasets provides a practical baseline; however, alternative definitions of the target score (e.g., based on user satisfaction metrics) could yield different algorithmic opportunities.

Original abstract

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.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-05: 1 request, 7,602 input tokens.

What the abstract itself states, as probabilities: claims first 0.04 · states limitation 0.83 · human participants 0.02 · controlled comparison 0.15 · randomized assignment 0.01 · states quantitative result 0.35 · compares with prior results 0.46 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

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$ \textsc{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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	PageRank is widely used to quantify the importance of nodes in directed networks.	background 1.00	0.03	0.02	asserted 1.00
s1	In applications such as recommendation systems, it is increasingly important that the PageRank distribution provides a fair representation of node exposure.	background 0.98	0.05	0.02	asserted 0.96
s2	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}$.	background 0.89	0.08	0.04	asserted 0.93
s3	In this paper, we study this problem under an edge-addition budget $B$, where exactly $B$ edges may be added to the graph.	contribution 0.61	0.35	0.04	asserted 0.95
s4	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.	result 0.97	0.94	0.20	asserted 1.00
s5	After this, we define the $\ell_1$ \textsc{Target PageRank} problem in which we seek to minimize the $\ell_1$ distance between the target vector and resultant vector.	contribution 0.85	0.90	0.07	asserted 0.98
s6	We show that this optimization problem admits no polynomial-time multiplicative constant-factor approximation unless $P=NP$.	result 0.98	0.94	0.16	asserted 1.00
s7	Motivated by these hardness results, we propose two greedy heuristics for approaching the target PageRank vector.	contribution 0.66	0.92	0.07	asserted 0.98
s8	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.	method 0.66	0.93	0.05	asserted 1.00
s9	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.	method 0.52	0.95	0.11	asserted 0.94

What kind of paper the classifier reports this is: method or tool 0.74 · evidence from proof or derivation 0.77.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** Node In-degree Distribution selected scores on 𝑇 . In

**Figure 3.** Variation with Target Sets is highly likely that these nodes, along with the ones they are connected to are contained in the 2-HOP target set. So, 2-HOP essentially filters out the clusters in the graph and the over-exposed nodes become the cluster centers. So, RWH has no advantage over other 2 heuristics in terms of computing cluster centers to add edges. Secondly, we observed that the over-exposed nodes have so high PageRank that adding edges from them to under-exposed nodes causes the PageRank of under-exposed nodes to shoot up much beyond their target, thereby increasing the…

**Figure 6.** Time Taken 8.5 Effect of Hyper-Parameters We study the effect of hyper-parameters on the performance of heuristics. 8.5.1 Variation with k. In

**Figure 7.** Variation with 𝑘 (No. of Cluster Centers) 8.5.3 Variation With hl

**Figure 9.** Variation With hl 8.6.1 Graph Generation. We have used the Barabasi-Albert model [10] to generate directed graphs that follow power law for node indegrees and have constant out-degree. We fix the number of nodes in the graph to be 50000 and the out-degree of each node as 10. The graph is generated as follows: (1) Start with a network of 10 nodes (no edges). (2) Add new nodes. For each new node added, add edges as follows: • With probability 𝑝 ∈ [0, 1], add an edge from the new node to 10 randomly chosen existing nodes. • With probability 1−𝑝, the new node connects to𝑚 = 10 existing…

**Figure 10.** Variation with 𝑝 (a) Target: 2-HOP (b) Target: WHOLE

**Figure 11.** Variation with 𝜆 then showed that minimizing the ℓ1-distance between the resulting and desired absolute PageRank scores on the target nodes admits no polynomial-time multiplicative constant-factor approximation unless 𝑃 = 𝑁 𝑃. We also formulated the problem as a mixed-integer linear program (MILP), while noting the scalability limitations of this approach. Motivated by these computational challenges, we proposed multiple heuristics, including methods that incorporate node similarity when selecting edges to add, and evaluated their performance on multiple Amazon datasets. In future…

**Figure 12.** Gadget used for reduction We will extend the reduction performed by [4] to Target PageRank Problem. We first define a general version of partition problem as follows: Problem 3. (𝑝1, 𝑝2, . . . , 𝑝𝑐 )-Balanced Partition Problem : We are given a vector 𝒑 of𝑐 ≥ 1 positive integers with 𝑔𝑐𝑑 (𝑝1, 𝑝2, . . . , 𝑝𝑐 ) = 1 and a multiset W = {𝑤1,𝑤2, ...,𝑤𝑚 } of 𝑚 positive integers. All integers are encoded in binary, and each occurrence of an item has its own index. Let 𝑆𝑈 𝑀(𝑋) denote the sum of elements of multiset 𝑋. Does there exist a partition W1,W2, . . . ,W𝑐 of W such that 𝑝𝑗 × 𝑆𝑈 𝑀(W𝑖)…

Showing 10 of the paper's 12 figures. See all figures in the PDF ↗ Figures reproduced from arXiv:2611.06782 by the authors.

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.