Suppose you want to seed a health message among homeless youth, or a product among users of a platform whose friend lists you can only read through a rate-limited interface. You cannot see the whole social network. Every time you learn someone's ties, you pay for it in an interview or an API call. The best current methods for this setting spend that budget discovering which community each person belongs to, so that the chosen seeds (the people who start the cascade) cover different communities instead of piling into one. These methods assume each person belongs to exactly one community. Real people belong to several. They also ignore the cheap side information you usually have before paying anything, such as a profile, an intake form, or a list of paper keywords. Two consequences follow. Seeds that sit in overlapping communities get double-counted, and the budget is spent crawling people whose communities could have been guessed from their attributes alone.
This note proposes treating every node that has been sampled but not yet crawled as a cold-start node: its attributes are known, its edges are not. A small model maps its attributes to a predicted mix of community memberships. The method then pays to crawl that node only when the prediction is uncertain or the node looks like a promising seed. Seeds are chosen to cover membership mass across overlapping communities, not to fill discrete blocks. The bet is that overlap and attribute informativeness, two properties that today's exploratory methods throw away, can be turned directly into query savings.
Core Claim
In exploratory influence maximization (choosing $k$ seeds to maximize expected cascade size on a network revealed only through paid queries), the dominant method is ARISEN from Influence Maximization with an Unknown Network by Exploiting Community Structure (also Maximizing Influence in an Unknown Social Network). It jumps to random nodes, crawls short walks around them, corrects degree bias with rejection sampling, estimates community sizes under a disjoint stochastic block model, and spreads seeds across blocks. It reaches influence comparable to full-knowledge greedy after querying 20–35% of the network.
We claim two things. On attributed networks with overlapping communities, a policy that predicts each sampled node's membership composition from attributes should reach the same spread with substantially fewer edge-revealing queries. That policy crawls selectively by membership uncertainty and selects seeds by a membership-coverage objective. Second, the gain should grow with the amount of overlap and with attribute informativeness. It should vanish, and not turn negative, when either goes to zero.
That last condition is what makes the claim falsifiable. If the gain does not track overlap, overlap modeling is not what is helping. If it does not track attribute informativeness, the cold-start predictor is not what is helping.
The seed objective is a surrogate. Write $\pi_{s} \in \Delta^{K-1}$ for node $s$'s estimated membership composition over $K$ communities, and $\hat n_c$ for the estimated size of community $c$. We maximize
$$f(S) = \sum_{c=1}^{K} \hat n_c \Big[1 - \prod_{s \in S} \big(1 - \pi_{s,c}\big)\Big],$$
the expected community mass touched by seed set $S$ when a seed activates community $c$ with probability equal to its membership share. The function $f$ is monotone and submodular, so greedy selection carries the usual $1-1/e$ guarantee on the surrogate. When memberships are one-hot, it reduces to ARISEN-style allocation: one seed per community, largest communities first. Whether the surrogate tracks true spread is an empirical question, and we test it.
One honesty point shapes the design. A node that truly has zero edges cannot start a cascade. "Cold" here means "edges unobserved," not "edges absent." The cold-start component is used to triage exploration, not to seed isolated newcomers.
Research Program
The system has three parts.
The first is the membership predictor. It takes a node's attributes and outputs a composition $\pi$ together with an uncertainty estimate. We use an ensemble of community-weighted logistic models, following On Learning Community-specific Similarity Metrics for Cold-start Link Prediction. That work gives brand-new, edgeless vertices soft multi-community memberships from content and shows that community-specific metrics beat global ones, because a keyword predictive in one community is irrelevant in another. We reuse its mechanism, but our training labels come from the exploration itself. Every crawled node yields a structural membership estimate from its revealed neighborhood. Optionally, the predictor is warm-started on an earlier snapshot of the same domain. The structural estimates on crawled subgraphs come from a link-community factorization in the spirit of Link Community Detection Using Generative Model and Nonnegative Matrix Factorization. That method clusters edges rather than nodes, so a node's memberships are read off its incident edges, and its iterative bipartitioning chooses $K$ without manual tuning. As a variant, we parameterize compositions in isometric log-ratio coordinates, following Aitchison Embeddings for Learning Compositional Graph Representations. That paper maps simplex vectors to unconstrained Euclidean space so that the geometry of membership ratios is preserved under gradient descent, and it is transductive. We use only its parameterization, inside an inductive predictor, and treat it as an ablation rather than a core commitment.
The second is the query policy. After each jump, the attributes are free. The policy crawls the node only if one of two conditions holds: the predictor's uncertainty on $\pi$ exceeds a threshold, or the node's marginal gain under $f$ is in the current top candidates. This mirrors the observation in Network Inference and Influence Maximization from Samples that some nodes are worth learning precisely and others are not. Community sizes $\hat n_c$ are estimated as in ARISEN, but with fractional memberships replacing block indicators. This removes the double-counting that a disjoint size estimate commits on overlapping nodes.
The third is seed selection: greedy maximization of $f$ over crawled candidates. A final local refinement uses Monte Carlo spread on the revealed subgraph.
The analysis has two parts. We give a bound relating $f$ to true spread on overlapping block models, where within-community cascades saturate. We then measure empirically where that relation breaks on real graphs. Permanence and Community Structure in Complex Networks found that disjoint methods collapse once inter-community mixing reaches about $\mu = 0.6$, so we expect the surrogate to weaken there too and will report that regime.
Baselines
The naive reference points are random seeds and the friends-of-friends heuristic, run under the identical query budget. The friends-of-friends heuristic queries a random node and nominates its highest-degree neighbor. ARISEN's authors report beating such field heuristics by 20–50% in spread. These baselines anchor what "doing nothing clever" achieves.
The strongest competitor is ARISEN itself, because it is the only method in the file that optimizes seeds under paid jump-crawl queries. We run it under the same budget, counted as edge-revealing queries, with attributes free to all methods. The same diffusion models are used: independent cascade, weighted cascade and trivalency, the latter two following A Community-Aware Framework for Social Influence Maximization. Spread is evaluated with the same Monte Carlo protocol and an equal hyperparameter search budget. No reported result was found on Lacuna for ARISEN on DBLP, PubMed, BlogCatalog or the Citation dataset; the file reports only the 20–35%-of-network and 20–50%-over-heuristics figures on field networks. We therefore rerun it ourselves. Beating it means one of two outcomes at matched seed budget $k$ on graphs with substantial overlap. Either we reach ARISEN's final spread with at least 30% fewer queries, or we achieve higher spread at every budget level, with seed-resampled confidence intervals excluding zero. In either case we must not be worse on zero-overlap synthetic graphs.
To give ARISEN a fair shot at using attributes, we add an attribute-augmented version in which jumped nodes are assigned to k-means attribute clusters, used as disjoint blocks.
As upper references with full graph knowledge, we run CELF++ greedy and Community-IM (Louvain plus progressive budgeting) from A Community-Aware Framework for Social Influence Maximization. They are reported as fraction-of-ceiling, not as competitors.
Three ablations isolate the key ingredients. The first replaces $\pi$ with its argmax, which is the overlap test. The second removes the attribute predictor and crawls every jumped node, which is the cold-start test. The third swaps log-ratio coordinates for a plain softmax, which tests the geometry.
Why not just…?
Why not just run ARISEN with Louvain on the crawled subgraph and ignore overlap? This is the most likely real threat on graphs with weak overlap, and the argmax ablation settles it directly. The evidence that it falls short is indirect. Community-IM's authors acknowledge that their disjoint framework ignores cross-community propagation and leaves overlap as future work. Permanence-based analysis shows disjoint assignments degrade at high mixing. If the argmax ablation matches the full method on the real benchmarks, we will conclude that overlap does not matter for seeding in practice and report that.
Why not just regress expected spread directly from attributes and pick the top $k$? This skips communities entirely and could work if attributes encode degree. Its known weakness is redundancy. In The Importance of Communities for Learning to Influence, COPS selects seeds from cascade logs alone by pruning candidates whose second-order spread overlaps. The baseline that picks top individual marginal influencers underperformed it, because its seeds clustered in the same community. We include an attribute-to-spread regressor, trained on the same crawled labels, so this comparison is measured rather than assumed.
Why not just crawl more and drop the attribute model? If queries are cheap, this wins by construction. That is why the attribute-informativeness sweep is central. When attributes are synthetic noise, the uncertainty gate should send nearly every node to crawling and recover ARISEN's behavior. When attributes are informative, the savings should appear. If savings are absent even with informative attributes, the cold-start component is dead weight.
Proposed Experiments
The synthetic study uses overlapping block models in which a controlled fraction of nodes belong to two or three communities. Attributes are generated from memberships with a tunable signal-to-noise ratio. We sweep both axes and plot query savings against ARISEN at matched spread. The decisive prediction is a gain surface that is near zero along both the zero-overlap and zero-signal edges and rises jointly with both.
The real-graph study uses attributed networks from the file whose communities naturally overlap. These are DBLP, with keyword attributes and venue-based communities as studied in the cold-start link prediction work, plus PubMed, BlogCatalog with interest groups, Cora, Citeseer, and the 2,555-paper Citation dataset from An Improved Random Walk Based Community Detection Algorithm. For temporal warm-starting on DBLP, the predictor is trained on an earlier snapshot and evaluated on a later one.
We report spread versus queried fraction under the three diffusion models for seed budgets 10 to 100, along with queries needed to reach 90% of the CELF++ ceiling. We also report the rank correlation between $f$ and Monte Carlo spread across candidate seed sets, broken down by estimated mixing level.
A final check examines the cases where ARISEN wins. If those cases concentrate at high mixing, where we predicted the surrogate weakens, that supports the account. If they appear at low mixing, the coverage objective is mis-specified and must be revised before any further claim is made.
References
- Influence Maximization with an Unknown Network by Exploiting Community Structure
- Maximizing Influence in an Unknown Social Network
- On Learning Community-specific Similarity Metrics for Cold-start Link Prediction
- Link Community Detection Using Generative Model and Nonnegative Matrix Factorization
- Aitchison Embeddings for Learning Compositional Graph Representations
- Network Inference and Influence Maximization from Samples
- Permanence and Community Structure in Complex Networks
- A Community-Aware Framework for Social Influence Maximization
- The Importance of Communities for Learning to Influence
- An Improved Random Walk Based Community Detection Algorithm