DiffIM: Differentiable Influence Minimization with Surrogate Modeling and Continuous Relaxation

• URL: http://arxiv.org/abs/2502.01031v1
• Date: Mon, 03 Feb 2025 03:54:23 GMT
• Title: DiffIM: Differentiable Influence Minimization with Surrogate Modeling and Continuous Relaxation
• Authors: Junghun Lee, Hyunju Kim, Fanchen Bu, Jihoon Ko, Kijung Shin,
• Abstract summary: Influence minimization (IMIN) is the problem of manipulating the structures of an input graph to reduce the propagation among nodes. We propose DiffIM, a novel method for IMIN with two differentiable schemes for acceleration. We show that each proposed scheme significantly improves speed with little (or even no) IMIN performance degradation.
• Score: 23.06479920145709
• License:
• Abstract: In social networks, people influence each other through social links, which can be represented as propagation among nodes in graphs. Influence minimization (IMIN) is the problem of manipulating the structures of an input graph (e.g., removing edges) to reduce the propagation among nodes. IMIN can represent time-critical real-world applications, such as rumor blocking, but IMIN is theoretically difficult and computationally expensive. Moreover, the discrete nature of IMIN hinders the usage of powerful machine learning techniques, which requires differentiable computation. In this work, we propose DiffIM, a novel method for IMIN with two differentiable schemes for acceleration: (1) surrogate modeling for efficient influence estimation, which avoids time-consuming simulations (e.g., Monte Carlo), and (2) the continuous relaxation of decisions, which avoids the evaluation of individual discrete decisions (e.g., removing an edge). We further propose a third accelerating scheme, gradient-driven selection, that chooses edges instantly based on gradients without optimization (spec., gradient descent iterations) on each test instance. Through extensive experiments on real-world graphs, we show that each proposed scheme significantly improves speed with little (or even no) IMIN performance degradation. Our method is Pareto-optimal (i.e., no baseline is faster and more effective than it) and typically several orders of magnitude (spec., up to 15,160X) faster than the most effective baseline while being more effective.

Related papers

• Gradient Descent Efficiency Index [0.0]
  This study introduces a new efficiency metric, Ek, designed to quantify the effectiveness of each iteration. The proposed metric accounts for both the relative change in error and the stability of the loss function across iterations. Ek has the potential to guide more informed decisions in the selection and tuning of optimization algorithms in machine learning applications.
  arXiv  Detail & Related papers  (2024-10-25T10:22:22Z)
• Unifews: Unified Entry-Wise Sparsification for Efficient Graph Neural Network [10.556366638048384]
  Graph Neural Networks (GNNs) have shown promising performance in various graph learning tasks, but at the cost of resource-intensive computations. Previous studies attempt to reduce the computational budget by leveraging graph-level or network-level sparsification techniques. We propose Unifews, which unifies the two operations in an entry-wise manner considering individual matrix elements.
  arXiv  Detail & Related papers  (2024-03-20T03:07:30Z)
• Revisiting Edge Perturbation for Graph Neural Network in Graph Data Augmentation and Attack [58.440711902319855]
  Edge perturbation is a method to modify graph structures. It can be categorized into two veins based on their effects on the performance of graph neural networks (GNNs) We propose a unified formulation and establish a clear boundary between two categories of edge perturbation methods.
  arXiv  Detail & Related papers  (2024-03-10T15:50:04Z)
• PREM: A Simple Yet Effective Approach for Node-Level Graph Anomaly Detection [65.24854366973794]
  Node-level graph anomaly detection (GAD) plays a critical role in identifying anomalous nodes from graph-structured data in domains such as medicine, social networks, and e-commerce. We introduce a simple method termed PREprocessing and Matching (PREM for short) to improve the efficiency of GAD. Our approach streamlines GAD, reducing time and memory consumption while maintaining powerful anomaly detection capabilities.
  arXiv  Detail & Related papers  (2023-10-18T02:59:57Z)
• ELRA: Exponential learning rate adaption gradient descent optimization method [83.88591755871734]
  We present a novel, fast (exponential rate), ab initio (hyper-free) gradient based adaption. The main idea of the method is to adapt the $alpha by situational awareness. It can be applied to problems of any dimensions n and scales only linearly.
  arXiv  Detail & Related papers  (2023-09-12T14:36:13Z)
• Accelerated primal-dual methods with enlarged step sizes and operator learning for nonsmooth optimal control problems [3.1006429989273063]
  We focus on the application of a primal-dual method, with which different types of variables can be treated individually. For the accelerated primal-dual method with larger step sizes, its convergence can be proved rigorously while it numerically accelerates the original primal-dual method. For the operator learning acceleration, we construct deep neural network surrogate models for the involved PDEs.
  arXiv  Detail & Related papers  (2023-07-01T10:39:07Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  We introduce a simple yet effective contrastive model named Localized Graph Contrastive Learning (Local-GCL) In spite of its simplicity, Local-GCL achieves quite competitive performance in self-supervised node representation learning tasks on graphs with various scales and properties.
  arXiv  Detail & Related papers  (2022-12-08T23:36:00Z)
• Error-Correcting Neural Networks for Semi-Lagrangian Advection in the Level-Set Method [0.0]
  We present a machine learning framework that blends image super-resolution technologies with scalar transport in the level-set method. We investigate whether we can compute on-the-fly data-driven corrections to minimize numerical viscosity in the coarse-mesh evolution of an interface.
  arXiv  Detail & Related papers  (2021-10-22T06:36:15Z)
• Efficient Differentiable Simulation of Articulated Bodies [89.64118042429287]
  We present a method for efficient differentiable simulation of articulated bodies. This enables integration of articulated body dynamics into deep learning frameworks. We show that reinforcement learning with articulated systems can be accelerated using gradients provided by our method.
  arXiv  Detail & Related papers  (2021-09-16T04:48:13Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem. We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent. Our algorithm is applied to solve problems with one variable under the sparsity constraint.
  arXiv  Detail & Related papers  (2020-06-16T13:41:54Z)

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.