Many-Objective Evolutionary Influence Maximization: Balancing Spread, Budget, Fairness, and Time

• URL: http://arxiv.org/abs/2403.18755v2
• Date: Thu, 28 Mar 2024 14:05:56 GMT
• Title: Many-Objective Evolutionary Influence Maximization: Balancing Spread, Budget, Fairness, and Time
• Authors: Elia Cunegatti, Leonardo Lucio Custode, Giovanni Iacca,
• Abstract summary: The Influence Maximization (IM) problem seeks to discover the set of nodes in a graph that can spread the information propagation at most. This problem is known to be NP-hard, and it is usually studied by maximizing the influence (spread) and,Alternatively, optimizing a second objective. In this work, we propose a first case study where several IM-specific objective functions, namely budget fairness, communities, and time, are optimized on top of influence and minimization of the seed set size.
• Score: 3.195234044113248
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Influence Maximization (IM) problem seeks to discover the set of nodes in a graph that can spread the information propagation at most. This problem is known to be NP-hard, and it is usually studied by maximizing the influence (spread) and, optionally, optimizing a second objective, such as minimizing the seed set size or maximizing the influence fairness. However, in many practical scenarios multiple aspects of the IM problem must be optimized at the same time. In this work, we propose a first case study where several IM-specific objective functions, namely budget, fairness, communities, and time, are optimized on top of the maximization of influence and minimization of the seed set size. To this aim, we introduce MOEIM (Many-Objective Evolutionary Algorithm for Influence Maximization) a Multi-Objective Evolutionary Algorithm (MOEA) based on NSGA-II incorporating graph-aware operators and a smart initialization. We compare MOEIM in two experimental settings, including a total of nine graph datasets, two heuristic methods, a related MOEA, and a state-of-the-art Deep Learning approach. The experiments show that MOEIM overall outperforms the competitors in most of the tested many-objective settings. To conclude, we also investigate the correlation between the objectives, leading to novel insights into the topic. The codebase is available at https://github.com/eliacunegatti/MOEIM.

Related papers

• Unlearning as multi-task optimization: A normalized gradient difference approach with an adaptive learning rate [105.86576388991713]
  We introduce a normalized gradient difference (NGDiff) algorithm, enabling us to have better control over the trade-off between the objectives. We provide a theoretical analysis and empirically demonstrate the superior performance of NGDiff among state-of-the-art unlearning methods on the TOFU and MUSE datasets.
  arXiv  Detail & Related papers  (2024-10-29T14:41:44Z)
• Influence Maximization via Graph Neural Bandits [54.45552721334886]
  We set the IM problem in a multi-round diffusion campaign, aiming to maximize the number of distinct users that are influenced. We propose the framework IM-GNB (Influence Maximization with Graph Neural Bandits), where we provide an estimate of the users' probabilities of being influenced.
  arXiv  Detail & Related papers  (2024-06-18T17:54:33Z)
• Influence Maximization in Hypergraphs using Multi-Objective Evolutionary Algorithms [2.726292320658314]
  The Influence Maximization (IM) problem is a well-known NP-hard problem over graphs. We propose a multi-objective EA for the IM problem over hypergraphs.
  arXiv  Detail & Related papers  (2024-05-16T15:31:28Z)
• Common pitfalls to avoid while using multiobjective optimization in machine learning [1.2499537119440245]
  There has been an increasing interest in exploring the application of multiobjective optimization (MOO) in machine learning (ML) Despite its potential, there is a noticeable lack of satisfactory literature that could serve as an entry-level guide for ML practitioners who want to use MOO. We critically review previous studies, particularly those involving MOO in deep learning (using Physics-Informed Neural Networks (PINNs) as a guiding example) and identify misconceptions that highlight the need for a better grasp of MOO principles in ML.
  arXiv  Detail & Related papers  (2024-05-02T17:12:25Z)
• Intuition-aware Mixture-of-Rank-1-Experts for Parameter Efficient Finetuning [50.73666458313015]
  Large Language Models (LLMs) have demonstrated significant potential in performing multiple tasks in multimedia applications. MoE has been emerged as a promising solution with its sparse architecture for effective task decoupling. Intuition-MoR1E achieves superior efficiency and 2.15% overall accuracy improvement across 14 public datasets.
  arXiv  Detail & Related papers  (2024-04-13T12:14:58Z)
• Predicting Infant Brain Connectivity with Federated Multi-Trajectory GNNs using Scarce Data [54.55126643084341]
  Existing deep learning solutions suffer from three major limitations. We introduce FedGmTE-Net++, a federated graph-based multi-trajectory evolution network. Using the power of federation, we aggregate local learnings among diverse hospitals with limited datasets.
  arXiv  Detail & Related papers  (2024-01-01T10:20:01Z)
• Towards Running Time Analysis of Interactive Multi-objective Evolutionary Algorithms [23.815981112784552]
  This paper provides the first running time analysis (the essential theoretical aspect of EAs) for practical iMOEAs. We prove that the expected running time of the well-developed interactive NSGA-II for solving the OneMinMax and OneJumpZeroJump problems is $O(n log n)$ and $O(nk)$, respectively.
  arXiv  Detail & Related papers  (2023-10-12T14:57:47Z)
• Deep Graph Representation Learning and Optimization for Influence Maximization [10.90744025490539]
  In Influence (IM) is formulated as selecting a set of initial users from a social network to maximize the expected number of influenced users. We propose a novel framework DeepIM to generatively characterize the latent representation of seed sets. We also design a novel objective function to infer optimal seed sets under flexible node-centrality-based budget constraints.
  arXiv  Detail & Related papers  (2023-05-01T15:45:01Z)
• GraMeR: Graph Meta Reinforcement Learning for Multi-Objective Influence Maximization [1.7311053765541482]
  Influence (IM) is a problem of identifying a subset of nodes called the seed nodes in a network (graph) IM has numerous applications such as viral marketing, epidemic control, sensor placement and other network-related tasks. We develop a generic IM problem as a Markov decision process that handles both intrinsic and influence activations.
  arXiv  Detail & Related papers  (2022-05-30T03:48:51Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)
• On the Global Optimality of Model-Agnostic Meta-Learning [133.16370011229776]
  Model-a meta-learning (MAML) formulates meta-learning as a bilevel optimization problem, where the inner level solves each subtask based on a shared prior. We characterize optimality of the stationary points attained by MAML for both learning and supervised learning, where the inner-level outer-level problems are solved via first-order optimization methods.
  arXiv  Detail & Related papers  (2020-06-23T17:33:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.