Learning to Augment Graphs: Machine-Learning-Based Social Network Intervention With Self-Supervision

• Published in: IEEE transactions on computational social systems 2024-06, Vol.11 (3), p.3286-3298
• Main Authors: Chang, Chih-Chieh, Lu, Chia-Hsun, Chang, Ming-Yi, Shen, Chao-En, Ho, Ya-Chi, Shen, Chih-Ya
• Format: Article
• Language: English
• Subjects: Algorithms; Clustering; Embedding; Graph optimization problems; Graph theory; Linear programming; Machine learning; network intervention; Optimization; Peer-to-peer computing; reinforcement learning; Self-supervised learning; Social networking (online); Social networks; Synthetic data; Task analysis; Training
• ISSN: 2329-924X; 2329-924X; 2373-7476
• DOI: 10.1109/TCSS.2023.3340230

This article proposes a machine learning (ML)-based approach to solve a graph optimization problem, named network intervention with limited degradation (NILD), which aims at adding new edges to augment the graph to minimize the local clustering coefficient (LCC) of a target node. The main application of NILD is to perform network intervention , to improve the mental well-being of individuals. This article proposes a new framework, named network intervention with self-supervision (NISS), which employs reinforcement learning and self-supervised learning (SSL) to effectively solve the problem. We propose two new effective pretext tasks in SSL, Distance-to-target prediction task and LCC increment prediction task to improve the model performance. In addition, we also propose two new embedding approaches, neighborhood embedding (NE) and constraint property embedding (CPE), to capture the structural information of the graph. Extensive experiments on multiple real social networks and synthetic datasets show that our proposed approach significantly outperforms the other state-of-the-art baselines, including ML-based baselines and deterministic algorithms.