TL;DR
This paper generalizes the famous Kempe-Kleinberg-Tardos (KKT) conjecture, proving that if local node threshold functions satisfy a higher-order version of submodularity called AD-k (Alternating Difference-$k$), the global influence spread function inherits this property. The authors prove this "local-to-global" transition for all directed acyclic graphs (DAGs) and for general graphs when $k$ is infinite, effectively bridging the theoretical gap between General Threshold and Triggering models.
What Problem Does This Paper Address?
In social network analysis, we often want to predict how information or "influence" spreads. A cornerstone of this field is the General Threshold (GT) model, where a node becomes active if the influence from its neighbors exceeds a random threshold.
A landmark conjecture by Kempe, Kleinberg, and Tardos (KKT) suggested that if the local functions governing each node are monotone and submodular (meaning more neighbors help, but each additional neighbor helps a bit less), then the global "spread function"—the expected total number of active nodes—is also monotone and submodular. While this was eventually proven, submodularity is essentially just "second-order" monotonicity.
The authors ask: Does this local-to-global relationship hold for even higher orders of monotonicity? They introduce the concept of AD-k to represent these higher-order properties and investigate whether "local AD-k" implies "global AD-k."
Methods
The authors employ a mix of combinatorial set theory and continuous mathematical analysis:
- AD-k Framework: They define a set function as AD-k if its $\ell$-th order differences have a specific alternating sign $(-1)^{\ell+1}$ for all $\ell \leq k$. Under this lens, AD-1 is simple monotonicity, and AD-2 is monotonicity plus submodularity.
- Continuous Extensions: To avoid the "intractable" nature of high-order discrete differences, the authors map set functions to multilinear extensions—continuous, differentiable functions. This allows them to use partial derivatives to prove properties more flexibly.
- Graph Transformations: To prove the conjecture for Directed Acyclic Graphs (DAGs), they use a constructive approach. They show how to transform any DAG into a layered graph by adding "dummy nodes" to eliminate skip-layer edges, proving that influence properties are preserved during this transformation.
- Mobius Inversion: For the case where $k = \infty$ on general graphs, they utilize Mobius Inversion formulas to connect the GT model to the Triggering model, a specific propagation model known to have very clean mathematical properties.
Datasets
Not discussed in the paper. As a theoretical work, the paper focuses on mathematical proofs and definitions rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- The Spectrum of Monotonicity: The paper reveals that submodularity isn't a standalone property but part of a hierarchy. AD-k provides a unified language for discussing how "diminishing returns" behave at higher levels of complexity.
- The AD-$\infty$ Bridge: A major "aha moment" is the connection to the Triggering model. Previous work showed that a GT model is equivalent to a Triggering model if and only if its local functions are AD-$\infty$. This paper completes the circle by showing the global spread function also becomes AD-$\infty$.
- Continuous is Easier: The proof strategy highlights that while social networks are discrete, treating them as continuous via multilinear extensions is a powerful tool for proving global structural properties.
- Layered Graph Equivalence: The authors demonstrate that for influence spread, any complex DAG can be simplified into a strictly layered structure without losing the underlying AD-k properties.
Key Results
- Generalization of KKT: The authors successfully generalize the KKT conjecture from AD-2 (submodularity) to any AD-k.
- DAG Proof: They prove that for any DAG, local AD-k always implies global AD-k for any integer $k \ge 1$.
- General Graph Proof ($k=\infty$): They affirm the conjecture for all social graphs (including those with cycles) when $k = \infty$.
- Characterization of Triggering Models: The results provide a deeper mathematical characterization of why Triggering models (which are AD-$\infty$) are so well-behaved compared to general threshold models.
Limitations and Future Work
- The "Middle Ground" Gap: While the conjecture is proven for $k=1, 2$ and $k=\infty$ on general graphs, it remains an open problem for $3 \le k \le n-1$ on graphs with cycles.
- Algorithmic Utility: The authors note a "disappointing" reality: even though AD-k is a stronger property than submodularity, it doesn't necessarily lead to better approximation ratios for the influence maximization problem. For example, the Max-k-Cover problem is AD-$\infty$, yet it is still NP-hard to approximate better than $1 - 1/e$.
- Future Directions: The authors suggest investigating whether AD-k can inspire new algorithms that avoid expensive function simulations, potentially leading to faster influence maximization techniques.
Summary updated