Source-linked AI summary
The Local-to-Global AD-k Conjecture is Resolved
Wei Chen
TL;DR
The open question was whether local AD-k structure in a general threshold diffusion model is preserved globally, including on cyclic graphs at finite higher orders. The paper proves this for every k and finite directed graph using signed triggering weights and a decision-tree partition. The result resolves Chen et al.’s conjecture, while possible algorithmic implications of negative-weighted triggering sets remain a direction to investigate.
Problem
It remained unresolved whether local AD-k influence functions imply a globally AD-k influence spread function on cyclic directed graphs at finite orders 3 ≤ k < |V|.
Source: §1 · pp. 1–2Method
Results
Takeaways & Limitations
The proof represents general-threshold diffusion through reachability in live-edge graphs whose triggering sets may have negative weights, an extension whose algorithmic implications remain open to investigation.
Source: §8 · p. 11Individual triggering-set weights of rank greater than k may be negative, so the signed measure is not a probability distribution.
Source: §3 · p. 5
Abstract
from arXiv · showhide
AD-k stands for Alternating Differences through order k, and it is a property of set functions denoting that the first order difference of the set function is nonnegative (a.k.a. monotnocity), the second order difference is nonpositive (submodularity), and so on with signs alternating through order k. Chen et al. [1] conjectured that in an influence diffusion model called the general threshold model originally defined by Kempe et al. [2], if every local influence function is AD-k, then the global influence spread function is also AD-k, for any (possibly cyclic) directed graph and any k. This paper provides a complete proof showing that the conjecture is true. The proof utilizes M\"obius inversion, reverse reachable sets, and decision tree partition techniques and extends the probability distribution of node triggering sets into a generalized algebraic structure allowing negative weights for triggering sets. The extension to negative-weighted triggering sets may be of independent interest and may have further algorithmic implications.
1 Introduction
The paper proves the local-to-global AD-k conjecture for every k and finite directed graph, resolving the remaining cyclic, finite-order cases. Its proof combines Möbius inversion, reverse reachability, decision-tree partitioning, and signed triggering weights.
1 Introduction
- Local-to-global preservation for monotone submodular influence functions is algorithmically relevant because it supports a (1 − 1/e)-approximation guarantee for greedy seed selection.The general threshold model includes classical diffusion models such as independent cascade, linear threshold, and triggering.Source: §1 · pp. 1–2
- AD-k requires set-function differences to alternate in sign through order k, extending monotonicity and submodularity to higher orders.AD-1 is monotonicity, while AD-2 is equivalent to monotonicity together with submodularity.Source: §1 · p. 2
- The open cases were cyclic directed graphs at finite orders 3 ≤ k < |V|; earlier results covered k = 1, 2, DAGs at every order, and AD-∞ on general directed graphs.The paper notes these cases had not previously been resolved to the authors’ knowledge.Source: §1 · p. 2
- The proof establishes that local AD-k influence functions yield a globally AD-k influence spread function for every k on every finite directed graph.It extends triggering-set weights to allow negative values and uses Möbius inversion, reverse reachable sets, and decision-tree partitioning.Source: §1 · p. 2
- Prior compounding results for higher-order alternating functions do not address feedback dependencies from directed cycles.The paper’s proof roadmap proceeds from signed triggering representations through reachability and a decision-tree partition to the theorem.Source: §1 · pp. 2–3
2 Model and Statement
The section states that local AD-k influence functions imply AD-k target-activation probabilities and influence spread. It frames the model using node-level influence functions, random thresholds, and a triggering-model reachability representation.
2 Model and Statement
- In the general threshold model on a finite directed graph, each vertex has a monotone local function over its in-neighbors and independently draws a threshold uniformly from [0, 1].Source: §2 · p. 3
- The triggering model represents each node’s sampled triggering set as incoming live edges, so diffusion from seeds is reachability in the resulting graph.The triggering model is a subclass of the general threshold model.Source: §2 · p. 3
- AD-k requires the alternating-difference condition for orders up to k and sets A disjoint from the base set S.The supplied definition introduces the condition but does not specify its full displayed inequality.Source: §2 · p. 3
- If every local function is AD-k, then each target activation probability and the influence spread are AD-k.This is the local-to-global theorem stated for the general threshold model.Source: §2 · p. 3
3 Möbius Inversion and Signed Triggering Weights
This section uses Möbius inversion to define signed triggering weights from a local influence function. Boolean-interval mass properties connect those weights to local AD-k inequalities, although individual weights above order k may remain negative.
3 Möbius Inversion and Signed Triggering Weights
- The signed triggering measure q is defined from the local influence function using its differences, with q(∅) = 1 − f(N).For nonempty T, q(T) is given by an alternating-sign difference of f at N \ T.Source: §3 · p. 4
- Möbius inversion on the Boolean lattice and inclusion–exclusion establish the stated Boolean-interval mass identities for q [17].A Boolean interval [A, B] consists of the sets between A and B under inclusion.Source: §3 · pp. 4–5
- When f is AD-k, the resulting local interval inequalities constrain aggregate signed masses, but individual q(T) weights of rank greater than k may still be negative.Thus q is not treated as a probability distribution.Source: §3 · p. 5
4 Signed Triggering and Live-edge Graph Reachability
A signed triggering-set representation reproduces threshold-model terminal-state expectations, including on graphs with cycles. The proof uses this equivalence to connect target activation with reverse reachability.
Signed Triggering Simulation
- The signed triggering simulation equates threshold-model expectations of terminal-state statistics with signed live-edge reachability, even on cyclic graphs.The triggering-set weights still sum to one, although individual weights may be negative.Source: §4 · pp. 5–6
Cyclic Graphs
- Progressiveness keeps each node's queried active-neighbor sets nested and ensures exposure terminates after finitely many activations, even with cycles.The exposure procedure computes the same terminal active set as the usual synchronous process.Source: §4 · p. 6
Transcript Argument
- Matching local answer patterns makes each complete transcript's signed trigger weight equal its threshold-model probability.Independence makes transcript probabilities products of local factors; summing over transcripts establishes the simulation.Source: §4 · p. 6
Alternative Proof
- A polynomial-continuation argument offers an alternative proof that the threshold and signed live-edge terminal-set expressions agree.Both are polynomials in the local table entries and agree on the open set of genuine positive trigger distributions.Source: §4 · p. 7
Target Activation
- For a target node, activation is equivalent to the seed set intersecting its reverse-reachable set in the live-edge graph.The simulation lemma applies to the target-activation indicator, yielding its threshold-model activation probability.Source: §4 · pp. 6–7
5 Alternating Differences as Reachability Cylinders
The section expresses a target's alternating activation difference as the signed mass of a reachability event. The event requires every node in A to reach the target and no node in S to do so.
Cylinder Identity
- For a fixed live-edge graph, the signed alternating difference of the target-activation indicator equals the indicator of a reachability cylinder.The cylinder fixes reachability for nodes in A and non-reachability for nodes in S, leaving other nodes unrestricted.Source: §5 · p. 7
Signed-Mass Reduction
- Substituting the signed triggering representation makes the global alternating difference equal the signed mass of C(A, S; t).Thus, proving the AD-k inequality reduces to showing this event has nonnegative signed mass.Source: §5 · pp. 7–8
Reachability Event
- The cylinder event C(A, S; t) requires every a in A to reach t while no s in S reaches t.The alternating sum vanishes if a forbidden node reaches t or if any required node fails to reach it.Source: §5 · pp. 7–8
6 A Bounded-positive Edge-query Decision Tree
An edge-query decision tree partitions the reachability event into product Boolean intervals. Its bounded-positive condition limits each local lower endpoint to at most |A| queried-present edges.
Bounded-positive Partition
- The edge-query decision tree partitions the reachability cylinder into disjoint product Boolean intervals with local lower endpoints of size at most |A|.Each leaf fixes present and absent edge choices while leaving unqueried edges free.Source: §6 · p. 8
Two-phase Search
- Phase I finds the forward closure of S and rejects if it contains t; Phase II searches outside that closure for paths from each a in A to t.The tree accepts only after all required searches succeed.Source: §6 · p. 8
Local Bound
- The two search phases expose present edges at different heads, bounding the positive queried edges per head by |A|.The phase bounds do not accumulate; this keeps local interval factors within the AD-k guarantee when |A| ≤ k.Source: §6 · pp. 8–9
Recognition and Partition
- The accepting leaves are disjoint and partition C(A, S; t), so their interval masses can be summed to obtain the cylinder's mass.The recognition argument shows that every configuration in the cylinder is accepted and no configuration outside it is.Source: §6 · pp. 8–9
7 Proof of the Theorem
The proof translates signed differences into reachability-cylinder mass, then uses a bounded-positive decision-tree partition to establish nonnegativity and AD-k for arbitrary target nodes and eligible disjoint sets.
7 Proof of the Theorem
- A triggering-set configuration induces a fixed live-edge graph, where the reverse reachable set identifies seed sets that activate the target.For a fixed configuration, h_T(X) indicates whether seed set X activates t.Source: §7 · p. 9
- The signed difference equals the product signed mass of a reachability cylinder, but this equality alone does not establish nonnegativity because atomic weights may be negative.Applying the difference operator uses its linearity over finite sums.Source: §7 · pp. 9–10
- A bounded-positive decision-tree partition decomposes the cylinder into disjoint accepting leaves, whose nonnegative local factors yield nonnegative products and a nonnegative sum.Combining this bound with the signed-mass identity proves the required alternating difference is nonnegative.Source: §7 · p. 10
- Because the target and eligible disjoint sets are arbitrary, the proof establishes that the global influence spread function σ is AD-k.The target t and disjoint sets A, S may be arbitrary with 1 ≤ |A| ≤ k.Source: §7 · p. 10
8 Conclusion
The paper proves Chen et al.’s local-to-global AD-k conjecture using a signed triggering-set measure. It also frames negative-weight triggering sets as a possible route to further algorithmic implications.
8 Conclusion
- Möbius inversion, reverse reachable sets, and decision-tree partitioning prove Chen et al.’s local-to-global AD-k conjecture.The proof allows negative triggering-set weights because the partition uses aggregate weights of order at most k, which the local AD-k property makes nonnegative.Source: §8 · p. 11
- General threshold models with local AD-k properties can retain live-edge reachability representations even when triggering sets have negative weights.The triggering model is equivalent to AD-∞, and its triggering sets underlie reverse influence sampling algorithms [11, 12, 13].Source: §8 · p. 11
- Whether extended triggering sets with negative weights have algorithmic implications remains an open direction for investigation.The paper identifies this as a direction worth pursuing further.Source: §8 · p. 11