Source-linked AI summary
Sketch-based Influence Maximization and Computation: Scaling up with Guarantees
Edith Cohen, Daniel Delling, Thomas Pajor, Renato F. Werneck
TL;DR
Influence maximization and influence queries become difficult to scale on very large networks, while greedy remains the quality benchmark. This paper introduces sketch-based SKIM and influence oracles, achieving scalable computation with probabilistic guarantees close to Greedy.
Problem
Influence queries and maximization require efficient, near-optimal computation, but greedy influence maximization does not scale to modern large networks.
Method
The paper uses combined per-node bottom-k reachability sketches to estimate influence, implement greedy maximization, and answer seed-set queries from sketches.
Results
With very high probability, every prefix achieves at least 1 − (1 − 1/s)^s − ϵ times the optimum influence for its size.
Takeaways & Limitations
SKIM can produce a full approximate influence-versus-seed-size Pareto front for networks with billions of edges.
Takeaways & Limitations
Exact influence computation is #P-hard, and existing greedy implementations do not scale beyond networks with roughly 10^6 edges.
Abstract
from arXiv · showhide
Propagation of contagion through networks is a fundamental process. It is used to model the spread of information, influence, or a viral infection. Diffusion patterns can be specified by a probabilistic model, such as Independent Cascade (IC), or captured by a set of representative traces. Basic computational problems in the study of diffusion are influence queries (determining the potency of a specified seed set of nodes) and Influence Maximization (identifying the most influential seed set of a given size). Answering each influence query involves many edge traversals, and does not scale when there are many queries on very large graphs. The gold standard for Influence Maximization is the greedy algorithm, which iteratively adds to the seed set a node maximizing the marginal gain in influence. Greedy has a guaranteed approximation ratio of at least (1-1/e) and actually produces a sequence of nodes, with each prefix having approximation guarantee with respect to the same-size optimum. Since Greedy does not scale well beyond a few million edges, for larger inputs one must currently use either heuristics or alternative algorithms designed for a pre-specified small seed set size. We develop a novel sketch-based design for influence computation. Our greedy Sketch-based Influence Maximization (SKIM) algorithm scales to graphs with billions of edges, with one to two orders of magnitude speedup over the best greedy methods. It still has a guaranteed approximation ratio, and in practice its quality nearly matches that of exact greedy. We also present influence oracles, which use linear-time preprocessing to generate a small sketch for each node, allowing the influence of any seed set to be quickly answered from the sketches of its nodes.
1 Introduction
The paper addresses the scalability limits of influence queries and greedy Influence Maximization on large diffusion networks. It introduces sketch-based methods—SKIM and influence oracles—that provide scalable computation with approximation guarantees.
- Problem setting: Influence queries require graph searches across multiple propagation instances and do not scale when many queries target graphs with millions of nodes.Influence Maximization is even harder, being NP-hard, while exact single-seed influence in binary IC is #P hard.
- Contributions: The paper introduces SKIM, a highly scalable sketch-based approximation of greedy Influence Maximization with performance guarantees.SKIM uses combined reachability sketches that summarize each node’s influence coverage across ℓ propagation instances using bottom-k min-hash sketches.
- Contributions: Influence oracles use almost-linear preprocessing to answer seed-set influence queries efficiently from only the sketches of the query nodes.The approach supports both fixed propagation instances with average influence and IC models with expected influence.
- Guarantees and scalability: For all s ≥1, SKIM’s first s selected nodes achieve with very high probability an influence of at least 1 −(1 −1/s)s −ϵ times the same-size optimum.Residual instances maintain greedy-selection accuracy, while adaptive execution exploits skewed influence distributions for faster running time.
- Empirical scope: SKIM can run exhaustively on networks with billions of edges, producing a full approximate influence-versus-seed-size Pareto front.This exposes the pattern that a small fraction of nodes can influence a large fraction of the network.
2 Model
The model represents diffusion using propagation instances over a shared node set, with influence defined by reachable nodes and aggregated across instances or probabilistic distributions. It formalizes influence queries, fast post-preprocessing influence oracles, and fixed-size influence maximization.
- Propagation model: A propagation instance G = (V, E) defines a seed set’s influence as the number of nodes reachable from it through forward paths.A node is reachable when it belongs to the seed set or has a forward path from a seed node.
- Propagation model: The input may contain ℓ≥1 propagation instances sharing V, with influence aggregated as average single-instance influence.Instances can be derived from cascade traces or generated by a probabilistic model.
- Propagation model: Under Independent Cascade, influence is defined as the expectation over a distribution of instances that share the node set V.The probabilistic model specifies a distribution G over instances G ∼G.
- Queries and maximization: Influence queries evaluate Inf(G, S), while influence oracles enable very fast queries after efficient preprocessing.Queries use a seed set S ⊂V.
- Queries and maximization: Influence maximization seeks a seed set S ⊂V of given size |S| = s with influence close to the maximum.The objective is to efficiently compute an approximately optimal fixed-size seed set.
3 Combined Reachability Sketches
Combined reachability sketches summarize node reachability across multiple graph instances or directly under a probabilistic IC model using at most k rank values. Bottom-k estimators recover reachability cardinality or influence with high-probability relative-error guarantees.
- Multiple instances: For ℓ≥1 graph instances, a node’s combined reachability set contains every reachable node-instance pair, and influence averages nodes reached from at least one seed.The set is Ru = {(v, i) | u ⇝G(i) v}.
- Multiple instances: Each node receives a bottom-k min-hash sketch containing the k smallest independent random ranks among its combined reachability pairs.With one instance, these sketches coincide with Cohen’s reachability sketches.
- Estimation guarantees: With k = (2 + c)ϵ−2 ln n and c > 1, relative error above ϵ occurs with probability at most 1/nc, enabling high-probability accuracy for all node influences.The guarantee follows from Chernoff bounds applied to the estimator.
- Permutation ranks: Structured permutation ranks support direct unbiased cardinality estimation over D = nℓ elements using 1 + (k −1)(D −1)/(T −1), where T is the kth-smallest rank.Permutation ranks can also be converted to random ranks using the exponential distribution.
- Probabilistic IC model: For a binary IC model, sketches retain at most k ranks and represent the limit of sketches over infinitely many generated instances, with influence estimated as n(k −1)/(T −1).Structured permutation ranks make the representation independent of the number of instances by considering the first kn ranks.
4 SKIM: Sketch Space IM
SKIM approximates greedy influence maximization using partial reachability sketches and residual problems, selecting nodes by estimated marginal influence. With high probability, every prefix of its output achieves a (1 − 1/e − ϵ) approximation to the corresponding optimum.
- Algorithm design: SKIM selects nodes whose estimated marginal gains are close to maximum, computing sketches only until the best candidate is revealed and maintaining a residual problem.This approximates exact Greedy while limiting sketch computation.
- Sketch construction: The first node whose combined sketch reaches size k has maximum estimated influence under the bottom-k cardinality estimate.The estimate depends on the kth-smallest sketch rank, τu, which is sufficient for cardinality estimation.
- Residual updates: After selecting a node, SKIM removes covered node-instance pairs, updates remaining sketches by deleting covered ranks, and resumes processing from the residual rank threshold.This preserves partial sketches while continuing rank-ordered exploration.
- Approximation guarantee: 1 − 1/e − ϵ: with probability 1−1/n^Ω(c), every prefix of SKIM’s node permutation achieves this approximation to the same-size optimum.The guarantee applies for all seed-set sizes s ∈ [n].
- Running time: O(km ln n): the total number of rank insertions is bounded by this quantity, based on an expected O(k ln n) insertions at each node.Residual-problem updates themselves take linear time in the total instance-graph size.
- Empirical behavior and adaptivity: Experiments found SKIM’s seed-set influence much closer to exact greedy than worst-case bounds indicate, while adaptive error estimation can tune k to target accuracy and confidence.The adaptive approach provides tighter confidence bounds than worst-case analysis.
5 Influence Oracles
The influence oracle precomputes an O(k)-size combined reachability sketch for every node, enabling fast, unbiased influence estimates for arbitrary seed sets. Its union estimator runs in O(|S|k log |S|) time, while sketch construction uses O(k Pℓ i=1 |E(i)|) computation and O(nk) additional storage.
- Oracle construction: The oracle precomputes combined reachability sketches Xv of size O(k) for every node v.Preprocessing uses O(k Pℓ i=1 |E(i)|) computation and O(k) working storage per node.
- Influence estimation: Influence queries for a seed set S are estimated from its node sketches in O(|S|k log |S|) time.The estimate is nonnegative, unbiased, and well concentrated; the relative-error exceedance probability decreases exponentially with a > 1.
- Influence estimation: The estimator computes the influence of S by estimating the union cardinality of the nodes’ reachability sets and dividing by the number of instances.It can use all at most k|S| sketch values rather than only the kth smallest threshold.
- Influence estimation: The Cohen–Kaplan estimator is computable in O(|S|k log |S|) time and minimizes variance given the information available in the sketches.It can achieve up to a factor of lower CV when the reachability sets are sufficiently disjoint.
- Oracle construction: Combined sketches are formed by taking the bottom-k values across per-instance reachability sketches, with O(k P i |E(i)|) construction time and O(nk) additional storage.For a single instance, reachability sketches can be computed using at most mk edge traversals in total.
6 Experiments
Experiments show that SKIM achieves influence quality close to established methods while substantially reducing running time, including on graphs with nearly two billion edges. The influence oracle further provides near-linear preprocessing and fast seed-set queries with low error.
- Parameter evaluation: 64 sampled instances and k = 64 sketch entries provide a practical quality–runtime tradeoff: larger values yield only modest additional quality, while SKIM remains fastest across seed-set sizes.Increasing ℓ beyond 64 yields modest improvements, and increasing k beyond 64 does not improve solution quality by much anymore.
- SKIM performance: SKIM’s influence values are very close to IRIE’s, while it is significantly faster and gains greater speedups for 1000 than 50 seeds.IRIE’s running time grows linearly with the number of seed nodes, whereas SKIM’s decreases with the residual problem size.
- SKIM performance: SKIM and TIM+ are extremely close in quality, with SKIM faster on most instances except Friendster, Twitter, and Slovakia⊤.With 1000 seeds, their running times are generally never more than a factor of three apart.
- SKIM performance: SKIM computes a sequence whose every prefix approximately maximizes influence, whereas TIM+ must be rerun to obtain a smaller seed set.This gives SKIM approximately optimized solutions across seed-set sizes from one computed sequence.
- Parameter evaluation: SKIM matches IRIE’s solution quality but is significantly faster under both weighted cascade and uniform IC schemes.The comparison uses TwitterFollowers as input.
- Influence oracle: On LiveJournal, oracle sketches require 2.3 GiB of space and 34 minutes to compute; queries take 1–2 µs for one node and 5.2 ms for 1000 seeds.Preprocessing times are reasonable, space consumption is essentially linear in nodes, query time is almost independent of graph size, and error stays well below 10% for one [truncated].
7 Conclusion
The paper presents scalable sketch-based algorithms for binary influence computation, including SKIM for influence maximization and sketch-based influence oracles. It also outlines future work on timed influence and Jaccard similarity estimation.
- Contributions: SKIM scales greedy influence maximization by several orders of magnitude to graphs with billions of edges.It is implemented in sketch space.
- Contributions: SKIM computes a node sequence whose every prefix has a probabilistic approximation-quality guarantee close to Greedy’s.The guarantee applies to each prefix of the sequence.
- Contributions: The paper also presents sketch-based influence oracles that process instances nearlinearly before estimating influence.The supplied passage ends after “estimate,” so no further oracle capability is specified.
- Future work: Future work will develop SKIM-like algorithms for timed influence, considering infection speed and scope when edge lengths represent transition times.The planned setting extends the sketch-based approach to timed diffusion.
- Future work: Future work will use sketches to estimate the Jaccard similarity between two nodes’ influence sets.The authors believe this is an effective similarity measure.