We study the degree-weighted work required to compute ℓ1-regularized PageRank using the standard accelerated proximal-gradient method (FISTA). For non-accelerated methods (ISTA), the best known worst-case work is O((αρ)−1), where α is the teleportation parameter and ρ is the ℓ1-regularization parameter. It is not known whether classical acceleration methods can improve 1/α to 1/α while preserving the 1/ρ locality scaling, or whether they can be asymptotically worse. For FISTA, we show a negative result by constructing a family of instances for which standard FISTA is asymptotically worse than ISTA. On the positive side, we analyze FISTA on a slightly over-regularized objective and show that, under a confinement condition, all spurious activations remain inside a boundary set B. This yields a bound consisting of an accelerated (ρα)−1log(α/ε) term plus a boundary overhead vol(B)/(ρα3/2). We also provide graph-structural sufficient conditions that imply such confinement.
Figures & tables
Figure 1: Adjacency density. For each boundary size ∣B∣ we visualize the adjacency matrix via a binned edge-density heatmap (bin size 20 ), where each pixel shows the fraction of possible edges between a pair of bins (log-scaled; colormap magma with white below 10−4 ). Dashed lines mark the core | boundary | exterior block boundaries. The plots show the clique (upper-left block), the boundary circulant band, the nearly dense exterior block, and the sparse cross-region interfaces.
Figure 2: Work vs. vol(B) . Work by ISTA and FISTA against vol(B) .
Figure 3: Sweeps at fixed ∣B∣=600 . Figure 3(a) shows the ρ -sweep with a dense core (clique) on a fresh randomized graph per ρ ; Figure 3(b) shows the ρ -sweep with a sparse core (connected, 20% of clique edges) on a fresh randomized graph per ρ . Figure 3(c) sweeps α at a fixed tolerance ε=10−6 on a single instance constructed so that the no-percolation condition holds at the smallest swept value, with parameters selected by an inexpensive auto-tuning step ( Appendix F ). Figure 3(d) sweeps the tolerance ε at fixed α=0.20 on the baseline unweighted instance.
Figure 4: Real graphs: work vs. α . Work to reach tolerance 10−8 as a function of α , with ρ=10−4 fixed. Curves show mean over 300 random seeds; shaded bands are interquartile ranges.
Figure 5: Real graphs: work vs. KKT tolerance. Work to reach ε , with α=0.20 and ρ=10−4 fixed. Curves show mean over 300 random seeds; shaded bands are interquartile ranges.
Figure 6: Real graphs: work vs. ρ . Work to reach 10−8 as a function of ρ , with α=0.20 fixed. Curves show mean over 300 random seeds; shaded bands are interquartile ranges.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 7: Iterations vs. per-iteration work tradeoff. Each point is a seed node (same seeds as in the sweep experiments), at α=10−3 , ρ=10−4 , and ε=10−8 . The x -axis is the iteration ratio NF/NI and the y -axis is the per-iteration work ratio (WF/NF)/(WI/NI) . Markers distinguish seeds where FISTA is faster/slower in total work.
Figure 8: Degree distributions on the real datasets. The heavier-tailed degree profiles (notably com-Orkut ) amplify the impact of transient exploration.