Abstract Influence estimation (IE) and influence maximization (IM) are among the most extensively studied problems in social network analysis. Assuming diffusion (i.e., the spread of diseases) within a social network, IE aims to estimate the influence (i.e., the number of infected nodes) for a given set of seeds; and IM aims to identify a given number of seed nodes that maximize the influence. For both IE and IM, widely-adopted strategies involve repeating Monte Carlo (MC) simulations of diffusion over and over for various seed sets, which is computationally expensive. In this work, we present Monte Carlo Simulator+ (MONSTOR+), an inductive machine learning method designed to estimate the influence of given seed-node sets in social networks under two diffusion models—the independent cascade (IC) model and the linear threshold (LT) model. Due to its inductive nature, MONSTOR+ is applicable to seed-node sets and social networks not included in the training data. MONSTOR+, with its ability to accurately estimate influence through a single forward pass, can greatly accelerate existing IM algorithms by replacing repeated MC simulations. In our experiments, MONSTOR+ exhibits high IE accuracy, achieving 0.955 or higher Pearson and Spearman correlation coefficients in unseen real-world social networks. Notably, MONSTOR+ is about 5 to 3000 times faster than repeated MC simulations with similar IE accuracy. For IM problems, IM algorithms equipped with MONSTOR+ are more accurate than state-of-the-art competitors in 81.5 and 77.8% of IM use cases under the IC model and LT model, respectively.

Continual Learning (CL) is the process of learning ceaselessly a sequence of tasks. Most existing CL methods deal with independent data (e.g., images and text) for which many benchmark frameworks and results under standard experimental settings are available. Compared to them, however, CL methods for graph data (graph CL) are relatively underexplored because of (a) the lack of standard experimental settings, especially regarding how to deal with the dependency between instances, (b) the lack of benchmark datasets and scenarios, and (c) high complexity in implementation and evaluation due to the dependency. In this paper, regarding (a) we define four standard incremental settings (task-, class-, domain-, and time-incremental) for node-, link-, and graph-level problems, extending the previously explored scope. Regarding (b), we provide 35 benchmark scenarios based on 24 real-world graphs. Regarding (c), we develop BeGin , an easy and fool-proof framework for graph CL. BeGin is easily extended since it is modularized with reusable modules for data processing, algorithm design, and evaluation. Especially, the evaluation module is completely separated from user code to eliminate potential mistakes. Regarding benchmark results, we cover \(3\times\) more combinations of incremental settings and levels of problems than the latest benchmark. All assets for the benchmark framework are publicly available at https://github.com/ShinhwanKang/BeGin .

Are users of an online social network interested equally in all connections in the network? If not, how can we obtain a summary of the network personalized to specific users? Can we use the summary for approximate query answering? As massive graphs (e.g., online social networks, hyperlink networks, and road networks) have become pervasive, graph compression has gained importance for the efficient processing of such graphs with limited resources. Graph summarization is an extensively-studied lossy compression method. It provides a summary graph where nodes with similar connectivity are merged into supernodes, and a variety of graph queries can be answered approximately from the summary graph. In this work, we introduce a new problem, namely personalized graph summarization, where the objective is to obtain a summary graph where more emphasis is put on connections closer to a given set of target nodes. Then, we propose Pegasus, a linear-time algorithm for the problem. Through experiments on six real-world graphs, we demonstrate that Pegasus is (a) Effective: node-similarity queries for target nodes can be answered significantly more accurately from personalized summary graphs than from non-personalized ones of similar size, (b) Scalable: it summarizes graphs with up to one billion edges, and (c) Applicable to distributed multi-query answering: it successfully replaces graph partitioning for communication-free multi-query processing.