Owned-Variable Frank-Wolfe for Masterless Influence Maximization

Suppose a social network is split among several organizations, such as regional platforms, data silos, or mobile operators. Each one holds only its own users and the edges pointing into them. Together they want to choose $k$ "seed" users whose activation spreads a message as widely as possible. This is influence maximization: picking a small starting set that maximizes the expected size of a random cascade. No party may see the whole graph, and no coordinator is trusted.

The natural move is to borrow decentralized optimization, where agents average copies of a shared parameter vector with their neighbors until they agree. We argue that template is wrong here. In this problem nobody needs to agree on a shared vector, because each agent owns the decision variables of its own users. What couples the agents is the cascade itself, which crosses organizational boundaries, together with the shared budget. We propose a Frank-Wolfe method (a gradient method that moves toward the best feasible corner of the constraint set rather than projecting) built around this ownership structure. Agents exchange only small partial products for the random cascades that cross their borders, plus a few scalars for the budget. Communication should then scale with how much influence crosses boundaries, not with the size of the graph. The method keeps the $(1-1/e)$ guarantee available for this non-convex problem, and every iterate respects the budget.

Core Claim

Reverse Influence Sampling (RIS) estimates spread by sampling random target users and recording every user who could have reached them in a sampled cascade. Each such record is called a reverse-reachable (RR) set. RIS turns the intractable spread computation into a coverage problem (Tang et al.). With $\theta$ sampled RR sets $\mathcal{R}$ over a graph with $N$ users, and a fractional seed vector $x \in [0,1]^N$, the relaxed objective and its gradient are

$$F(x) = \frac{N}{\theta}\sum_{R \in \mathcal{R}} \Big[1 - \prod_{u \in R}(1-x_u)\Big], \qquad \frac{\partial F}{\partial x_u} = \frac{N}{\theta}\sum_{R \ni u} \prod_{w \in R,\, w \neq u}(1-x_w).$$

This is the multilinear extension of a coverage function. It is continuous DR-submodular, meaning gradients shrink as $x$ grows. It is non-convex, but Frank-Wolfe still achieves $(1-1/e)$ on it (Mokhtari et al.). The differentiable form is the same one Chen et al. used to obtain exact RIS gradients on a single machine.

The structural observation is this. When users are partitioned across agents, the product for each RR set factors into one term per agent the set touches. An RR set that stays inside agent $a$ costs nothing to communicate. An RR set that crosses into agent $b$ requires $a$ and $b$ to exchange a single number: the log of their factor. RR sets are connected through graph edges, so the agents an RR set touches form a connected piece of the agent-adjacency graph. The exchange therefore stays peer-to-peer.

The Frank-Wolfe direction step over the budget $\sum_u x_u \le k$ selects the $k$ users with the largest gradient across all agents. Agents can do this with a gossip search over a single scalar threshold. Each Frank-Wolfe iterate is a convex combination of feasible points, so the budget is never violated at any iteration. Prior decentralized methods for coupled constraints obtain that property only for convex objectives (violation-free coupling).

Relation to Prior Work

Two lines of work supply the method, and both assume the wrong variable structure. Decentralized Continuous Greedy (Mokhtari et al.) runs Frank-Wolfe with gradient tracking on a sum of local submodular objectives. Each agent keeps a full copy of $x$ and averages it with neighbors, at $O(1/\epsilon^3)$ rounds for discrete objectives. DeGTFW/DeSGTFW (Xie et al.) reduces this to $\tilde O(1/\epsilon)$ rounds, at the cost of mini-batches that grow as $t^2$.

Both methods assume that agent $i$ can evaluate its own local term $f_i$. In partitioned influence maximization this fails: the spread of agent $a$'s users depends on edges held by agent $b$. Both methods also send $N$-dimensional vectors in every message. We drop the shared copy entirely. Each agent stores and updates only its own coordinates.

A second line motivates the problem by showing what breaks. DIIMM (Tang et al.) documents a "partitioning paradox": splitting nodes across workers degrades greedy coverage. DIIMM avoids the paradox by splitting RR sets instead, but it relies on a master node that becomes the memory and failure bottleneck. Community-aware influence maximization (Umrawal and Aggarwal, Umrawal et al.) runs greedy inside each community and allocates the budget progressively. It ignores cross-community edges and needs a coordinator. Our boundary-product exchange is a direct, masterless repair of exactly that blind spot.

A third line constrains the design. Accelerated gradient tracking (Song et al.) requires strong convexity. The research file also notes that neighbor averaging under non-convexity can pull copies into high-loss regions between basins. DINGO (Crane and Roosta) extends guarantees beyond convexity by minimizing the gradient norm, but it can stall at saddle points. On a coverage relaxation, the fractional optimum typically sits on the budget boundary with a nonzero gradient, so driving the gradient norm to zero targets the wrong points.

Our design avoids both problems. There are no averaged copies to disagree, and the guarantee comes from DR-submodularity, not from reaching a stationary point.

Research Program

Distributed RR-set sampling. Each agent samples RR-set roots among its own users in proportion to its share of the graph. It runs the reverse search over incoming edges it holds. When the search reaches a user owned by agent $b$, it hands the remaining search to $b$. Each crossing RR set receives an identifier, and every agent it touches records only its own members.

Gradient computation with lazy boundary messages. For each crossing RR set, agent $a$ maintains $s_{a,R} = \sum_{w \in R \cap V_a}\log(1-x_w)$. Frank-Wolfe moves $x$ by a step of size $1/T$, so these sums change slowly. Agents resend $s_{a,R}$ only when it has drifted by more than a tolerance $\delta$. We will analyze the resulting gradient error by adapting the inexact-gradient argument behind DCG. The target bound is $(1-1/e)\,\mathrm{OPT}$ minus an RIS sampling term, a term of order $k\delta$, and an $O(1/T)$ term.

Distributed top-$k$ step. Agents bisect on a gradient threshold. Each bisection step uses one gossip round of counting via push-sum, which also handles directed links (Nedic et al.). To keep the step feasible under approximate counts, agents round down, so the selected set may be smaller than $k$ but never larger. This preserves the budget at every iteration.

Rounding to a seed set. Each agent first applies pipage rounding within its own coordinates. It then passes its leftover fraction along a spanning tree of agents. Pipage rounding does not decrease the coverage relaxation in expectation, so this rounding keeps the guarantee.

Extension to budget saving. Second, we treat the budget-saving objective of Chen et al.. Adding a concave reward for unspent budget makes the objective neither monotone nor DR-submodular. That reward depends only on the total spend $\sum_u x_u$, which agents can track as one averaged scalar. We therefore expect the owned-variable structure to carry over to a decentralized version of their proximal-gradient method. The goal is to match its $(1/2-\epsilon)$ guarantee without a central machine.

Baselines

The reference point that ignores decentralization is centralized RIS greedy (IMM) run on the full graph, together with centralized ProxGrad-RIS for the budget-saving variant. These give an upper reference on spread. We report every method's spread as a ratio to this reference, evaluated on held-out RR sets plus 10,000 Monte Carlo cascades.

The naive decentralized reference ignores boundaries. Each agent runs IMM on its own subgraph with budget $k\cdot|V_a|/N$, and boundary edges are discarded. This is what an organization would do with no cooperation.

The strongest existing system is DIIMM (Tang et al.). It reports a 31x to 56x speedup over IMM on a 64-core server across Facebook, Google+, LiveJournal, and Twitter. The file contains no reported absolute spread values for it. We will run it with the same RR-set budget $\theta$ and the same total cores, and we grant it the master node it requires. Beating it means matching its spread within 1% while having no node whose memory or communication grows with the total number of RR sets.

The community-aware method with progressive budgeting (Umrawal et al.) reports 3,782 s versus 17,359 s for CELF++ on Facebook, and 16,465 s versus 250,241 s on Epinions. We give it the same partition our agents use and a coordinator for budget allocation.

The strongest decentralized competitor is the obvious combination of DeSGTFW (Xie et al.) or DCG with RIS gradients. To make it runnable at all, each agent computes gradients from the RR sets it fully holds, with the same boundary exchange as ours. The method keeps a full $N$-dimensional copy of $x$ and tracks gradients by averaging. The file has no reported result for either method on influence maximization; their only real-data evaluation is MovieLens facility location. We tune its step-size schedule with the same number of trials as ours.

Three ablations isolate our ingredients. Removing the boundary exchange tests whether cross-border cascades matter. Setting $\delta=0$ (exact messages every iteration) measures the cost of lazy updates. Replacing the threshold step with a step that relaxes the budget through a penalty tests whether all-iteration feasibility costs spread.

Why not just…?

Why not just use DIIMM with a master? If a trusted coordinator with enough memory exists, DIIMM is likely faster, and we do not claim otherwise. Our claim applies only to settings without a master: no party may hold all RR sets, or a single point of failure is unacceptable. The DIIMM authors themselves identify master saturation as their limit. The experiment reports peak per-node memory and communication. If our method required any agent to hold close to $\theta$ RR sets, that would show it has merely rebuilt a master.

Why not just run DCG/DeSGTFW with RIS gradients? This is the real threat. Its weaknesses are concrete. Each message carries $N$ numbers, and the $t^2$ mini-batch schedule of Xie et al. inflates computation on each agent. Its local objectives are not computable without exactly the boundary exchange we propose. Once that exchange is given to it, the remaining difference is consensus copies versus owned variables. If it matches our spread at comparable bytes on LiveJournal-scale graphs, the owned-variable claim is wrong and we will say so.

Why not just partition by community and run local greedy? The community method is fast on high-modularity graphs, so it may be adequate there. It discards cross-border influence, and its optimal allocation relies on submodularity, which the budget-saving variant breaks. A sweep from Louvain partitions to random partitions will show where it collapses relative to our method.

Proposed Experiments

We will use SNAP-style networks from the file under the Independent Cascade model: Facebook, Bitcoin, Wikipedia, Epinions, NetHEPT, Flixster, Google+, and LiveJournal, with Twitter as a scale test. The DM network is used for the budget-saving variant, where Chen et al. report a 30x speedup of RIS gradients over plain stochastic gradient descent. Agent counts range from 4 to 256. Partitions are either Louvain communities, which model natural silos, or random, which maximizes boundary crossings. The communication graph is the agent-adjacency graph, with $k \in \{10, 50, 100\}$.

We measure five things: spread ratio to centralized IMM, total and per-agent bytes, communication rounds, peak per-agent memory, and the maximum budget violation over all iterations. The last should be zero for our method.

Two checks decide the outcome. First, as the fraction of crossing RR sets rises from community to random partitions, the boundary-blind baselines should lose spread. Our method should stay within 1–2% of centralized IMM while its bytes grow roughly linearly in the number of crossing RR sets. If bytes grow with $N$ instead, the core claim fails. Second, against the consensus-copy DeSGTFW variant with identical boundary information, our method should reach the same spread with at least an order of magnitude fewer bytes on graphs above $10^7$ edges. This factor is our working expectation: our messages are per crossing RR set, while consensus messages are $N$-dimensional vectors. We will also state the regime honestly: with many agents and random partitions, nearly every RR set may cross a boundary, and the advantage may shrink toward that of centralized RIS.