Influence Maximization Across Private Graph Silos

Picking a few people to seed a message so that it spreads as far as possible through a social network is called influence maximization. It is a well-solved problem when one party holds the whole network. Real networks are often split across organizations that cannot pool their data: telecom carriers, hospital referral systems, competing platforms. Each one sees its own users and their links, and only the edges that cross between organizations tie the pieces together.

The obvious workaround has each organization pick its own best seeds and then merges the picks. This is the graph analogue of a familiar federated-learning failure. When clients hold non-identical data, each client's local optimum drifts away from the global one, and averaging their solutions fails. Here, each organization's private view of influence misjudges how influence actually flows across the boundary. We propose a protocol that keeps each organization's edges and cascade logs private yet recovers the centralized approximation guarantee. Its communication cost grows with how often sampled influence paths cross organizational boundaries, not with the size of the graph. We also give a measurement study showing when the naive merge is good enough and when it collapses.

Core Claim

The standard scalable technique, reverse influence sampling, avoids simulating cascades forward. It picks a random target node, walks backward over randomly "live" edges, and records every node that could have reached the target. The resulting reverse-reachable (RR) set is a sample of who could influence that target. Seed selection then becomes a coverage problem: choose $k$ nodes that appear in as many RR sets as possible. Distributed Influence Maximization for Large-Scale Online Social Networks (DIIMM) makes one observation that matters for us. It partitions the RR sets across machines while keeping every candidate seed visible to all machines, and this preserves the $(1-1/e-\epsilon)$ guarantee. By contrast, partitioning nodes across machines, as GREEDI does, causes a "partitioning paradox": quality decays as the number of machines grows. DIIMM assumes one trusted data center that can trace any path.

Our claim is that a federated version is possible because coverage decomposes cleanly. Give each RR set a random identifier. Each silo then holds only the fragment of that RR set that falls inside its own nodes. A coordinator needs nothing beyond a bit vector over identifiers recording which RR sets are already covered. With that vector, the silo that owns a candidate seed can compute the candidate's marginal gain locally.

Three things cross organizational lines: boundary-crossing queries during backward sampling, covered-identifier bits, and per-candidate gain counts. Raw edges, cascade logs, and community labels never do. We expect the gap between the naive per-silo merge and centralized seeding to track a measurable quantity: the fraction of RR sets that span more than one silo, which we call the boundary mass. The protocol should close that gap at a communication cost roughly proportional to the same quantity.

Research Program

The first component is distributed backward sampling. Under the independent cascade model, an active node gets one random chance to activate each neighbor. This model is equivalent to drawing a random subgraph in which each edge is independently "live". Each silo can therefore draw its own live edges for sample $r$ from a seed it alone holds. To build RR set $r$, the silo owning the root runs a backward search over its own live edges. When the search reaches a node with an incoming cross-silo edge, it sends a query of the form "which of your nodes reach boundary node $x$ in sample $r$". The query goes to the silo that holds that edge's live/dead draw, and the exchange continues until no new crossings appear.

We will batch these queries across many samples, so the number of communication rounds is bounded by the depth of boundary crossings rather than by the number of RR sets. We will also cache each silo's backward closure from its boundary nodes for each sample.

The second component is coordinated lazy greedy selection. Each silo reports upper bounds on its candidates' marginal gains. The coordinator then requests exact recomputation only for the current leaders, which is the same lazy-update logic DIIMM and Scalable Fair Influence Maximization (FIMM) use centrally. The coordinator broadcasts newly covered identifiers after each pick. Because each RR set is still a uniform random sample of the global process, the standard concentration argument behind the $(1-1/e-\epsilon)$ guarantee carries over unchanged. What changes is only who computes which count.

The third component is a leakage analysis. We will characterize what each party learns. The coordinator learns gain counts and covered identifiers. A silo learns the existence of live cross-silo edges, which its own endpoints already reveal. We will add calibrated noise to reported gain counts and measure the cost in spread.

As a stress test for statistical heterogeneity, silos will estimate edge probabilities from cascade logs of very different volumes. This yields interval uncertainty of uneven width across silos. We will run the protocol with the lower-upper bound selection of Robust Influence Maximization (RIM). RIM shows that its robust ratio degrades sharply as interval width grows. That paper assumes centralized cascade logs; we ask whether silos with thin logs dominate the worst case.

Baselines

The naive reference point is per-silo IMM with proportional budgets. Each silo runs reverse influence sampling on its own subgraph with cross-silo edges dropped and receives a share of $k$ proportional to its node count. This requires zero communication, so any protocol must justify its traffic against it.

The second baseline is a GREEDI-style merge. Each silo proposes its local top-$k$, and the coordinator re-runs greedy over the union using only locally estimated spreads. This is the distributed scheme DIIMM shows suffers the partitioning paradox, and it is the strongest privacy-respecting method available off the shelf.

The upper reference is centralized IMM on the pooled graph, which is what DIIMM parallelizes. DIIMM reports a 31x to 56x speedup over IMM on 64 cores and preserves the $(1-1/e-\epsilon)$ ratio on graphs up to the 1.5-billion-edge Twitter network. However, no reported result was found on Lacuna for absolute seed-set spread of IMM on our evaluation graphs, so we will compute it ourselves.

The key ablation is our protocol with boundary queries disabled. This produces truncated RR sets with identical coordination machinery, and it isolates the value of cross-silo sampling from the value of shared coverage bookkeeping.

All methods receive the same graphs, the same edge probabilities, the same number of RR sets per unit of $\epsilon$, and the same $k$. Spread is scored by 10,000 forward Monte Carlo simulations on the true pooled graph, held out from all methods. Beating the GREEDI merge means a spread gap to centralized IMM that is statistically indistinguishable from zero, while the merge's gap grows with silo count and boundary mass. Beating the naive baseline is required only where boundary mass is high. Below a threshold we expect to lose to it on cost.

Why not just…?

Why not just let each silo pick its own seeds? When organizations align with tight communities, few RR sets cross boundaries, and per-silo selection may be nearly optimal at zero cost. This is a real threat, not a strawman. Our experiments sweep from community-aligned partitions, which have low boundary mass, to random partitions, which have high boundary mass. The deliverable is the crossover curve. If the gap stays small even under random partitions on all graphs, the protocol is unnecessary and we will report that.

Why not just merge local proposals, as GREEDI does? DIIMM gives both proof and measurements that set-partitioned merging degrades as partitions multiply, because no machine sees overlapping coverage. Our silo-count sweep tests whether that degradation persists when partitions follow organizational rather than arbitrary lines.

Why not centralize the graph under differential privacy or secure multiparty computation? Adding noise to individual edge probabilities distorts exactly the parameters RIM shows seed quality is fragile to. Running full IMM inside secure computation pays cryptographic cost on every edge traversal. We will include an edge-noise centralization baseline at matched privacy accounting to show the spread lost.

Why not train a learned influence estimator federatedly? MONSTOR reaches rank correlation of 0.998 or higher on unseen graphs. However, it is trained centrally, it is restricted to independent cascade, and it gives no approximation guarantee. Learning its messages across silos would still require cross-silo propagation, so the boundary problem returns.

Proposed Experiments

We will use graphs whose community labels provide realistic silo boundaries. These include DBLP (72,875 nodes, 1,352 communities), Youtube, Amazon, and Flixster as used by FIMM, NetHEPT from RIM, and LiveJournal and Google+ from DIIMM for scale. Communities will be grouped into 2 to 64 silos either by community or at random, and we will report boundary mass for each configuration.

Metrics are Monte Carlo spread relative to centralized IMM, total bytes and rounds of communication, and spread under added gain-count noise. The decisive checks are three. First, the protocol matches centralized spread within confidence intervals at every silo count. Second, the gap left by the naive and GREEDI baselines rises with boundary mass, which is the drift-like failure we predict. Third, protocol communication scales with boundary mass rather than edge count.

For the heterogeneity stress test, we will fit edge probabilities from per-silo log subsets of varying size. We will then report the robust ratio as in RIM, which reports that on Flixster Topic 8 uniform edge sampling needed over 77,000 samples per edge to reach a robust ratio of 0.8, versus 33,000 for cascade-guided sampling. The test asks whether directing extra log collection to thin-log silos recovers the robust ratio faster than uniform collection.