Several defenses against citation gaming rest on computational hardness. The argument is that if finding the optimal manipulation of an impact metric is NP-hard, or W[1]-hard (intractable even when the attacker's budget is small), then gaming the metric is impractical. Two examples: the consolidation–disruption (CD) index, which scores whether a paper displaced or reinforced the work it built on, and fusionCite, a Google Scholar-style merging rule that discards duplicate and self-citations. Worst-case hardness, however, says nothing about whether a cheap greedy attacker gets close to optimal on real citation graphs. The literature that proved the hardness results names this as its open question. We propose to answer it with measurements plus certificates. On real citation data, we will run greedy manipulators against these metrics. We will prove when the attacker's objective has diminishing returns, which is what makes greedy provably near-optimal. We will also compute, for each real instance, an upper bound on how much better an optimal attacker could have done.
The main claim is that the right robustness criterion for a bibliometric defense is how approximable the attacker's objective is, not how hard it is to optimize exactly. We expect the CD index to fail this test in an instructive way. When the attack consists of added citations that cite a target paper but none of its references, the CD gain has diminishing returns, so greedy is near-optimal and the hardness shield is empty. Hardness can only bite through structural interactions: controlled papers citing each other, or new citations that also touch the target's references. We will measure how often real cartel-like configurations fall into that regime.
Background and the gap
Hardness-as-defense comes from two papers. How Hard Is It to Impact the Impact of Your Paper? models the citation network as a directed acyclic graph and studies three attacks on the CD index. Merging papers is W[1]-hard. Adding $k$ dummy papers is W[2]-hard in $k$. Deleting papers is tractable when the target score is exactly 1 and W[1]-hard otherwise. The paper explicitly leaves open whether greedy heuristics can still inflate the index in real networks. h-Index Manipulation by Undoing Merges shows that splitting merged profile entries games sumCite and unionCite optimally in linear time, but becomes NP- and W[1]-hard under fusionCite. On Google Scholar AI profiles it finds median h-index gains of 4 points for senior researchers and 1–2 for younger ones, usually from touching only one or two articles. Both papers motivate this project: they establish the barrier and point at its weakness. Neither analyzes approximation.
The method comes from Maximizing the spread of influence through a social network. That work showed that expected spread under cascade models is monotone and submodular, meaning each added element helps less as the set grows. The greedy algorithm, which repeatedly adds the element with the largest marginal gain, is therefore within a factor $1-1/e$ of optimal. On the arXiv hep-ph collaboration network, greedy beat high-degree seeding by 18%. We reuse the proof pattern and the greedy algorithm, but apply them to an adversarial objective (the manipulator's gain) rather than a cooperative diffusion objective. That paper does not consider this setting.
Content- and topology-aware defenses constrain the attack model rather than supply it. These include the PageRank-index, COIRank, and GLAD. A realistic attacker must avoid the conflict-of-interest patterns these methods downweight. We therefore also test greedy attacks that are restricted to citations crossing collaboration and affiliation boundaries.
Core claim, stated precisely
For a target paper $p$, let $F$ be the number of papers citing $p$ but none of its references, $B$ the number citing both, and $R$ the number citing only its references. Then
$$\mathrm{CD}(p) = \frac{F - B}{F + B + R}.$$
Consider an attack that adds one more "$p$-only" citation. It raises $F$ by one, and its gain is
$$\Delta = \frac{F-B+1}{n+1} - \frac{F-B}{n} = \frac{2B + R}{n(n+1)}, \qquad n = F+B+R.$$
The numerator $2B+R$ does not change under such additions, while $n$ grows, so each successive addition gains less. Now take an attacker who can add at most $k$ citations and wants to raise the summed CD of a set of target papers. When every available action is additive and $p$-only, the objective is a sum of concave functions of counts. It is therefore monotone submodular, and greedy achieves $1-1/e$. Hardness must therefore come from actions that break additivity: one added citation that also cites a reference of the target (it moves $R$ into $B$), or a controlled paper that is simultaneously a target and a reference of another target.
We will quantify how far such objectives depart from diminishing returns using the submodularity ratio $\gamma$. This is the largest $\gamma \in [0,1]$ such that, for every attack set $L$ and every disjoint set $A$ of further actions, the sum of the single-action gains of $A$ from $L$ is at least $\gamma$ times the gain of adding all of $A$ at once. Greedy's guarantee degrades smoothly to $1-e^{-\gamma}$. The empirical question is what $\gamma$, or a data-dependent lower bound on it, looks like on real citation graphs.
Research Program
Theory. The first stage characterizes the attack objectives formally. For CD addition attacks we will prove submodularity in the additive regime. We will then bound $\gamma$ as a function of simple structural quantities: the fraction of candidate citations that touch a target's references, and the depth of citation chains among controlled papers. We will also show which reductions in Yang's hardness proofs rely on configurations with $\gamma$ near zero. For fusionCite splitting, the h-index is a threshold function and is not submodular. We therefore define a smoothed surrogate, the sum over articles of citation counts truncated at a candidate h value, run greedy on the surrogate, and check the true h-index gain.
Certificates. The second stage builds certificates. For a submodular objective, the value of the greedy set plus the sum of the top-$k$ remaining marginal gains upper-bounds the optimum. For weakly submodular objectives, the same bound divided by $\gamma$ applies. This gives, on every real instance, a checkable bound on how much an optimal attacker could exceed the greedy attacker, without solving the hard problem. On small instances we will also solve exactly with integer programming to check the certificates' tightness.
Measurement. The third stage runs these attacks across datasets and metrics. We will report the metric inflation a greedy attacker achieves per unit budget, the certified gap to optimum, and how both change when the attacker must evade conflict-of-interest filters.
Baselines
The do-nothing reference is the metric's unmanipulated value together with a random attacker. The random attacker spends the same budget of $k$ added citations or splits on uniformly chosen feasible actions. It calibrates how much of any gain comes from choosing actions well rather than from budget alone.
The first structural heuristic is a high-degree attacker, the analogue of the centrality seeding that Kempe et al. beat by 18% in spread on hep-ph. It spends its budget on the targets with the smallest denominators $n$, or for splitting, on the most-cited merged articles. It is the natural competitor because it is what a lazy but informed manipulator would do. It gets the same action pool and budget. Greedy beats it if it achieves higher inflation at equal $k$ on a majority of instances, with a paired test.
The strongest existing method is exact optimization. For fusionCite, this means the exact or linear-time procedures and the realistic-scenario evaluation of van Bevern et al., who report median h-index gains of 4 points for senior and 1–2 for younger researchers under unionCite. For fusionCite and for CD manipulation specifically, no reported result was found on Lacuna for greedy or heuristic attack performance. We will run an integer-programming exact attacker under a fixed wall-clock budget, identical across instances. Greedy "matches" the exact attacker if it reaches at least 95% of its gain wherever the solver finishes. It "beats" exact attack in practice if it keeps near-certified-optimal gains on large instances where the solver times out.
The key ablation removes non-additive actions from the action pool, which restricts the attacker to $p$-only citations. This isolates whether the gap between greedy and optimum is driven by exactly the interactions our theory predicts.
Why not just…?
Why not just run an exact solver, since real profiles are small? This is a real threat. van Bevern et al. found that one or two articles usually suffice, which suggests real fusionCite instances may be easy to solve exactly. If the integer program solves every Google Scholar profile instantly, that already answers the open question: hardness provides no protection there. We would report it as such. The greedy certificates matter at the scales where exact solving should fail, namely cartel-level attacks on many targets in APS or Microsoft Academic citation graphs. The solver-timeout curves in our experiments will show where that boundary lies.
Why not just report empirical inflation from any reasonable heuristic, without approximation theory? Empirical inflation alone cannot distinguish "the metric is robust" from "the heuristic is weak". The certificate supplies that distinction, and the $\gamma$ analysis tells a metric designer which structural feature, such as reference overlap, actually makes attacks hard. The additive-action ablation tests whether the theory predicts where greedy loses ground.
Why not just rely on detectors such as COIRank or GLAD instead of analyzing attacks? Detectors like COIRank and GLAD are trained or tuned on known conflict and anomaly patterns. GLAD reports an F1 of 0.9075 on a MAG subset. An attacker optimizing under a filter-evasion constraint is a different distribution. We will measure how much greedy inflation survives when the action pool excludes co-author and same-affiliation citations. That quantity tells us whether detectors and hardness together close the gap.
Proposed Experiments
For fusionCite we use the Google Scholar AI profiles (ai10-2011, ai10-2013, ijcai-2013) from van Bevern et al.. For the CD index we use the APS Physical Review C citation graph (30,596 papers) from COIRank, which carries the affiliation and co-authorship data needed for the evasion constraint. For scale we use the Microsoft Academic Search computer-science graph (1.6M publications) from Jolly et al.. On APS we simulate cartels by choosing a group of co-authors, their papers as targets, and their future papers as the citation budget. We sweep $k$ and the cartel size.
The metrics are metric inflation per unit budget, the ratio of greedy gain to exact gain where exact is solvable, the certified optimality gap elsewhere, and estimated $\gamma$. Four checks settle the proposal. First, on APS, greedy should reach at least 90% of certified optimum for CD attacks in the additive regime, which would support the submodularity claim. Second, the certified gap should widen measurably as reference-overlapping actions are admitted, which would support the claimed source of hardness. Third, under fusionCite, greedy on the smoothed surrogate should recover most of the h-index gain of exact splitting. If it does not, fusionCite's hardness is a genuine practical defense and we would say so. Fourth, requiring filter evasion should shrink but not eliminate greedy CD inflation, which would indicate whether hardness adds protection beyond conflict-of-interest detection.
References
- How Hard Is It to Impact the Impact of Your Paper?
- h-Index Manipulation by Undoing Merges
- Maximizing the spread of influence through a social network
- The Pagerank-Index: Going beyond Citation Counts in Quantifying Scientific Impact of Researchers
- Identifying Anomalous Citations for Objective Evaluation of Scholarly Article Impact
- Deep Graph Learning for Anomalous Citation Detection
- Unsupervised Anomaly Detection in Journal-Level Citation Networks