Source-linked AI summary
Deep Graph Representation Learning and Optimization for Influence Maximization
Chen Ling, Junji Jiang, Junxiang Wang, My Thai, Lukas Xue, James Song, Meikang Qiu, Liang Zhao
TL;DR
Influence maximization remains challenging because existing methods struggle with efficient optimization, complex diffusion patterns, and flexible node-centrality constraints. DeepIM learns latent seed-set representations jointly with diffusion models and adaptive constrained objectives; experiments report the best results across application scenarios, while its diffusion modeling assumes monotonicity.
Problem
Learning-based influence maximization is limited by difficult objective optimization, complex unknown diffusion processes, and adaptation across node-centrality-constrained variants.
Method
DeepIM learns latent seed-set representations jointly with an end-to-end graph diffusion model and uses a constrained objective for flexible seed-set inference.
Results
DeepIM achieves the best results among state-of-the-art methods for finding influence-maximizing seed sets across various application scenarios.
Takeaways & Limitations
DeepIM provides a more robust and generalized learning-based framework that can characterize diversified diffusion dynamics and adapt seed-set inference to multiple constraints.
Takeaways & Limitations
The diffusion model assumes monotonicity, meaning influence spread increases when the selected seed set grows.
Abstract
from arXiv · showhide
Influence maximization (IM) is formulated as selecting a set of initial users from a social network to maximize the expected number of influenced users. Researchers have made great progress in designing various traditional methods, and their theoretical design and performance gain are close to a limit. In the past few years, learning-based IM methods have emerged to achieve stronger generalization ability to unknown graphs than traditional ones. However, the development of learning-based IM methods is still limited by fundamental obstacles, including 1) the difficulty of effectively solving the objective function; 2) the difficulty of characterizing the diversified underlying diffusion patterns; and 3) the difficulty of adapting the solution under various node-centrality-constrained IM variants. To cope with the above challenges, we design a novel framework DeepIM to generatively characterize the latent representation of seed sets, and we propose to learn the diversified information diffusion pattern in a data-driven and end-to-end manner. Finally, we design a novel objective function to infer optimal seed sets under flexible node-centrality-based budget constraints. Extensive analyses are conducted over both synthetic and real-world datasets to demonstrate the overall performance of DeepIM. The code and data are available at: https://github.com/triplej0079/DeepIM.
1. Introduction
Influence maximization seeks seed users that maximize information spread, but learning-based methods remain limited by optimization, diffusion-modeling, and constraint-adaptation challenges. DeepIM addresses these challenges through continuous seed-set representations, end-to-end diffusion learning, and adaptive constrained optimization.
- Motivation: Influence maximization selects seed users to maximize influence spread in a social network, including applications such as viral marketing.The problem is commercially important because initially selected users can spread product adoption through their social connections.
- Challenges: Learning-based influence maximization remains difficult because discrete objective optimization, diversified diffusion characterization, and node-centrality-constrained adaptation are unresolved.Existing methods face scalability issues from repeatedly updating node embeddings and computing influence spread, while often relying on prescribed diffusion models.
- DeepIM: DeepIM embeds the discrete optimization domain into continuous space and learns expressive seed-set representations jointly with an end-to-end graph diffusion model.The framework directly optimizes latent seed-set representations while learning the underlying diffusion process.
- DeepIM: DeepIM introduces a constrained optimization objective that infers optimal seed sets under arbitrary node-centrality-related constraints.This objective is designed to improve solution adaptivity across influence-maximization variants.
- Evaluation: Extensive experiments on four real-world datasets show that DeepIM achieves the best seed-set influence results among state-of-the-art methods across application scenarios.The reported evaluation compares DeepIM with other methods in varied settings.
2. Related Work
Prior influence-maximization research includes traditional simulation, proxy, and heuristic methods and newer learning-based approaches using deep learning and reinforcement learning. DeepIM uses graph neural networks to characterize diffusion patterns and estimate influence end to end.
- Traditional Methods: Traditional influence-maximization methods are categorized as simulation-based, proxy-based, and heuristic-based, often achieving near or exact solutions under specific diffusion models.Their reported performance depends on prescribed diffusion assumptions.
- Learning-Based Methods: Learning-based methods address traditional methods’ limited generalization ability by applying deep learning and reinforcement learning to influence maximization.Existing approaches commonly learn latent embeddings of nodes or networks and use current node embeddings during selection.
- Graph Neural Networks: Graph neural networks alternate node-feature transformation with neighbor-information aggregation to produce node or graph representations.Different aggregation and combination functions induce different GNN models.
- Graph Neural Networks: DeepIM leverages GNNs to characterize underlying diffusion patterns and construct an end-to-end model for influence estimation.The model applies learned graph representations to information-diffusion estimation.
3. Problem Formulation
Influence maximization selects a seed set whose diffusion through a graph maximizes the number of influenced nodes. The formulation exposes limitations of existing learning-based methods, including scalability problems and dependence on specific diffusion models.
- Formal Definition: Given graph G, influence maximization selects an optimal seed set x ⊆ V to maximize the number of influenced nodes under a diffusion model M(x, G; θ).The diffusion model may use infection probabilities or GNN aggregation and combination parameters.
- Formal Definition: The seed-set vector x ∈ {0, 1}^|V| indicates membership, while the output y ∈ R+ measures the total number of infected nodes.Each element x_i equals 1 when node v_i belongs to the seed set and 0 otherwise.
- Formal Definition: The generic problem requires selecting k users from V as the seed set to maximize influence spread, with optimal seed set x̃ producing maximal spread.The seed-set size is constrained by k.
- Existing Limitations: Existing learning-based frameworks face scalability problems because they repeatedly update latent embeddings for every node at each selection or optimization step.This cost becomes severe for million-scale networks.
- Existing Limitations: Existing frameworks are often tailored to specific diffusion models, limiting their ability to represent more general diffusion processes.The cited examples explicitly model M(·) using diffusion assumptions such as IC and LT.
4. DeepIM
DeepIM learns a compressed latent representation of seed sets together with an end-to-end monotonic diffusion model, then optimizes seed selection in continuous latent space. Its unified inference framework supports efficiency-oriented prediction and flexible node-centrality-based budget constraints.
- Learning Representation of Seed Set: DeepIM uses an autoencoder to represent seed sets with a lower-dimensional latent variable and jointly learn the seed-set distribution and diffusion process.The latent representation is intended to preserve seed-set expressiveness while reducing optimization difficulty.
- Seed Node Set Inference: Seed-set inference samples a latent variable from the learned distribution and iteratively updates it to maximize predicted influence spread.The diffusion predictor can be switched between the GNN teacher and lightweight student model to trade efficiency against efficacy.
- Learning Representation of Seed Set: Its GNN-based diffusion model maps seed sets and graph topology to influence spread through node-level infection probabilities and a final normalization function.The model first aggregates multi-hop neighborhood information, then converts infection probabilities into total spread.
- Learning Representation of Seed Set: Monotonicity constraints ensure that enlarging the seed set does not decrease predicted spread or node infection probabilities.The framework defines score monotonicity over spread and infection monotonicity over per-node infection probabilities.
- Learning Representation of Seed Set: The training objective combines diffusion prediction, seed-set reconstruction, and knowledge distillation losses in an end-to-end optimization.A lightweight student model directly predicts influence spread from the latent variable, avoiding the teacher model’s multi-step computation during efficient inference.
- Seed Node Set Inference: A unified generalized budget constraint supports seed inference under different node-level costs or centrality-based budgets.The constraint weights each selected node by F(v_i, G), with k representing the actual budget.
5. Experiment
Experiments evaluate DeepIM across multiple diffusion models, datasets, baselines, budget constraints, runtime settings, and a Jazz visualization. DeepIM generally achieves stronger influence spread and faster inference than comparison methods.
- Experiment setup: Experiments use six real-world datasets and one 50,000-node synthetic graph, with IC, LT, and SIS diffusion models generating training data.Seed sets are sampled at sizes proportional to each network, and diffusion outcomes provide the training pairs.
- Comparison methods: DeepIM is compared with traditional, learning-based, online, and budget-constraint influence-maximization methods.The comparison includes IMM, OPIM-C, SubSIM, IMINFECTOR, PIANO, ToupleGDD, OIM, CELF, and the student model DeepIMs.
- IC model: Under IC diffusion, DeepIM achieves overall better performance than other methods across all datasets.The evaluation reports percentage of final infected nodes after 100 diffusion rounds for seed budgets of 1%, 5%, 10%, and 20%.
- LT model: Under LT diffusion, DeepIM and DeepIMs outperform other methods by an average of 200% on Jazz and 30% on the Synthetic dataset.With 20% of the Synthetic dataset selected as seeds, DeepIM can spread influence through the whole network, while other methods infect at most 70%.
- Budget-constraint IM: With degree-based budget constraints, DeepIM generally outperforms CELF across networks, with larger margins under LT and fewer influence-spread fluctuations.Figure 2 varies node-size growth across 1%, 5%, 10%, and 20% under IC and LT models.
- Scalability analysis: DeepIM runtime grows near-linearly with graph size and is on average 20% faster than IMINFECTOR, while DeepIMs improves inference time by up to 90% over DeepIM.The runtime comparison uses 10% of nodes as seeds.
- Graph diffusion visualization: The Jazz case study visualizes 20% seed nodes and final infection status, with blue, red, and grey indicating seeds, infected nodes, and uninfected nodes.Node size represents degree, and the study reports better influence spreading by DeepIM.
6. Conclusion
DeepIM addresses influence maximization by learning seed-set representations and diversified diffusion patterns, then inferring seed sets under flexible node-centrality-based constraints. Experiments on synthetic and real-world datasets demonstrate advantages over existing state-of-the-art methods.
- DeepIM characterizes seed-set probabilities and searches for more optimal seed sets in continuous space.
- Two learning-based diffusion models characterize diversified diffusion dynamics with efficiency and efficacy guarantees.
- A novel objective function supports seed-node inference under multiple constraints for different influence-maximization application schemes.
- Experiments and case studies on synthetic and real-world datasets demonstrate DeepIM's advantages over existing state-of-the-art methods.
A. Proofs
The proofs establish monotonicity properties of the GNN-based influence model and justify the optimization terms used for seed-set learning. They also show that the GAT model satisfies the conditions required for score and infection monotonicity.
- The influence model is infection monotonic because its composed graph operations are non-decreasing.
- The GAT model satisfies Theorem 1's conditions, so its influence model is score and infection monotonic.
- The model is also score monotonic because both the graph-based influence function and reconstruction mapping are non-decreasing.
- Equation (8)'s first term is an MSE that drives predicted influence toward the fully infected target.
- Equation (8)'s second term uses negative log-likelihood for node-selection probabilities constrained to [0, 1].
- The final optimization objective combines the influence-prediction loss and the seed-selection probability loss.
B.1. Data
The study evaluates DeepIM on six networks spanning collaboration, citation, infrastructure, coauthorship, and social-media settings. These datasets include both undirected and directed network structures.
- Jazz is a musicians' collaboration network in which nodes are musicians and edges represent shared band participation.
- Cora-ML is a citation network of computer-science papers, with directed edges representing citations.
- Power Grid represents the US Western States Power Grid, with edges as power-supply lines and nodes as generators, transformers, or substations.
- Network Science is a coauthorship network whose nodes are scientists and edges represent collaborations.
- Digg and Weibo are directed social-media follower networks involving post visibility or tweet cascades.
B.2. Hyperparameter Setting.
Experiments configure several diffusion patterns and use a specified GAT-based diffusion estimator for DeepIM. Table 5 compares methods under the non-progressive SIS setting, while Figure 4 visualizes influence spread on Jazz.
- The weighted-cascade IC model sets each edge's propagation probability to the inverse in-degree of its destination node.
- The LT model samples each node's threshold uniformly from [0.3, 0.6], while SIS uses infection and recovery probabilities of 0.001.
- DeepIM uses a 2-layer GAT diffusion-estimation model with 4 attention heads per layer and 64 dimensions per attention channel.
- Table 5 compares methods under the SIS diffusion pattern, with the best result highlighted in bold.
- Figure 4 encodes node degree by size and infection status by color: blue seeds, red infected nodes, and grey uninfected nodes.
B.3. IM under Non-progressive Diffusion Model
Under the non-progressive SIS diffusion model, DeepIM remains robust despite more complicated dynamics that reduce performance across models. It outperforms other methods by an average of 10% across all datasets.
- 10% average improvement: DeepIM outperforms other methods across all datasets under the non-progressive SIS model.SIS allows nodes to switch from activated to de-activated, producing more complicated diffusion dynamics.
B.4. Case Study: Graph Diffusion Visualization
A case study visualizes selected seeds and final infection states on the Jazz dataset for 10% and 20% initial seed-set sizes. DeepIM achieves similar final influence spread across these sizes and performs better with lower cost than competing methods.
- The visualization marks seed nodes in blue, infected nodes in red, and uninfected nodes in grey.The case study uses the smaller Jazz graph and compares 10% and 20% initial seed-set sizes.
- DeepIM achieves better influence spread while showing little difference between the two seed-set sizes, indicating lower cost than competing methods.The visualization is consistent with the results reported in Table 2.