Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving Networks

Influence Maximization (IM), which aims to select a set of users from a social network to maximize the expected number of influenced users, has recently received significant attention for mass communication and commercial marketing. Existing research efforts dedicated to the IM problem depend on a strong assumption: the selected seed users are willing to spread the information after receiving benefits from a company or organization. In reality, however, some seed users may be reluctant to spread the information, or need to be paid higher to be motivated. Furthermore, the existing IM works pay little attention to capture user's influence propagation in the future period as well. In this paper, we target a new research problem, named Reconnecting Top-l Relationships (RTlR) query, which aims to find l number of previous existing relationships but being stranged later, such that reconnecting these relationships will maximize the expected benefit of influenced users by the given group in a future period. We prove that the RTlR problem is NP-hard. An efficient greedy algorithm is proposed to answer the RTlR queries with the influence estimation technique and the well-chosen link prediction method to predict the near future network structure. We also design a pruning method to reduce unnecessary probing from candidate edges. Further, a carefully designed order-based algorithm is proposed to accelerate the RTlR queries. Finally, we conduct extensive experiments on real-world datasets to demonstrate the effectiveness and efficiency of our proposed methods.

INTRODUCTION
Over the past few decades, the rise of online social networks has brought a transformative effect on the communication and information spread among human beings. Through social media platforms (e.g., Twitter), business companies can spread their products information and brand stories to their customers, politicians can deliver their administrative ideas and policies to the public, and researchers can post their upcoming academic seminars information to attract their peers around the world to attend. Motivated by real substantial applications of online social networks, researchers start to keep a watchful eye on information diffusion [4,23], as the information could quickly become pervasive through the "word-of-mouth" propagation among friends in social networks.
Influence Maximization (IM) is the key algorithmic problem in information diffusion research, which has been extensively studied in recent years. IM aims to find a small set of highly influential users such that they will cause the maximum influence spread in a social network [3,23,37,40]. To fit with different real application scenarios, many variants of the IM problem have been investigated recently, such as Topic-aware IM [5,17,29,30], Time-aware IM [14,20,39,47], Community-aware IM [28,42,45,48], Competitive IM [2,32,36,43], Multi-strategies IM [7,24], and Out-of-Home IM [51,53]. However, some critical characteristics of the IM study fail to be fully discussed in existing IM works. We explain these characteristics using the two observations below.
Observation 1. Some business companies wish their product information would be spread to most of their customers in the period after they spent their budgets on their selected seed users (e.g., Apple releases its new iPhone every September. They want to find optimal influencers in social networks to appeal to as many users as possible to purchase the new iPhone in the year ahead). However, most of the existing IM works modelled the social networks as static graphs, while the topology of social networks often evolves over time in the real world [8,26]. Therefore, the seed users selected currently may not give good performance for influence spread in the following time period due to the evolution of the network. To satisfy Apple's requirement, we would better predict the topology evolution of social networks in the following period and select seed users from the predicted network.
Observation 2. Existing IM studies dedicated to the influence maximization problem depend on a strong assumption -the selected seed users will spread the information. However, some of the chosen individual seed users may be unwilling to promote the product information for various reasons. Moreover, most startups and academic groups may not have the budget to motivate the seed users to spread their product or academic activities information.
Our Problem. The aforementioned observations motivate us to propose and study a novel research problem, namely Reconnecting Top-Relationships (RT R). Given a directed evolving graph G = { } −1 0 , a parameter , and an institute U contains a group of users, RT R asks for reconnecting a set of estranged relationships (e.g., edges that have ever existed in G while disappearing in the near future snapshot graph ). Reconnecting the selected edges in RT R query to will maximize the number of influenced users in that are influenced by the members of U.  Note: the given users' group U are marked as black icons and covered by blue color, 0 is the snapshot of the directed evolving graph G = { } −1 0 at time 0, and is the predicted graph snapshot of G at time ; the greyish dotted edges in represent the relationship between users exists in G while disappearing in ; the purple dotted lines represent the new adding edges in ; the edge of two red icons which covered by yellow color is the query result of RT R problem. Example 1.1 (Motivation). LinkedIn 1 is a business and employment oriented online social network. It provides a social network platform to allow members to create their profiles and "connect" to each other, representing real-world professional relationships. Members can also post their activity information (e.g., employment Ads) on LinkedIn. The study of RT R can significantly enhance the stickiness of members in LinkedIn without any budgets paid by members or LinkedIn itself. Figure 1 presents an evolving social network with ten members and their relationships. Suppose a research group (e.g., black icons) will host an online virtual academic seminar next month. They post the seminar information on LinkedIn because they wish to attract as many researchers as possible to join their seminar in the month ahead (e.g., ). By answering the RT R query, LinkedIn can find out the optimal estranged relationships (e.g., among the greyish dotted edges), in which reconnecting them (e.g., red icons) will maximize the spread of seminar information in the coming month. To reconnect the estranged relationships, a possible way is to send an email to the related users' platform Inbox and notify them of the recent news of their old friends. Therefore, the study of RT R query will benefit both users and the social media platform. The members will be more willing to keep active in the network platforms, which provide them a free and efficient information post service.
To the best of our knowledge, this is the first IM study that draws the inspiration from the intersection of (1) topology evolving prediction of social networks, and (2) no additional cost. As a result, the following challenges are important to be addressed. Challenges. The first challenge is how to predict the topology of social networks in a specified future period. To deal with this challenge, we adopt the link prediction method [50] to predict the network structure evolution in evolving networks. The other challenge is the complexity of RT R query problem. Unlike traditional IM studies that aim to find Top-influential users, our RT R focuses on the edges discovery. The existing IM algorithms are not applicable to address the RT R query, and a more detailed analysis 1 https://www.linkedin.com/ the number of generated sketch subgraphs in the SBG method is presented in Section 4.1. Thirdly, our RT R query may return different results for different given user groups, while the IM problem only needs to be queried one time to get the most influential users.
To address these algorithmic challenges, we first propose a sketchedbased greedy (SBG) algorithm to answer the RT R query of a given group. Besides, a candidate edges reducing method has been proposed to boost the SBG algorithm's efficiency. Furthermore, we carefully designed a novel order-based SBG algorithm to accelerate the RT R query. Contributions. We state our major contributions as follows: • We introduce and formally define the problem of Reconnecting Top-Relationships (RT R) for the first time, and explain the motivation of solving the problem with real applications. We also prove that the RT R query problem is NP-hard. • We propose a sketch-based greedy (SBG) approach to answer the RT R queries. Besides, we present the pruning method to boost the efficiency of the SBG algorithm by reducing the number of candidate edges' probing. • To further accelerate the RT R query, we elaborately design a novel order-based algorithm to answer the RT R query more efficiently. • We conduct extensive experiments to demonstrate the efficiency and effectiveness of our proposed algorithms using real-world datasets.
Organization. The remainder of this paper is organized as follows. First, we present the preliminaries in Section 2 and formally define the RT R problem in Section 3. Then, we propose the sketch-based greedy approach and the accelerate method in Section 4. We further present a new order-based algorithm to efficiently answer the RT R query in Section 5. After that, the experimental evaluation and results are reported in Section 6. Finally, we review the related works in Section 7 and conclude this work in Section 8.
We define a directed evolving network as a sequence of graph snapshots G = { } −1 0 , and {0, , 1, .., − 1} is a set of time points. We assume that the network snapshots in G share the same vertex set. Let represent the network snapshot at timestamp ∈ [0, −1], where each vertex in is a social user in , each edge = ( , ) in represents a cyber link or a social relationship between users and in . Similar to [11,21], we can create "dummy" vertices at each time step to represent the case of vertices joining or leaving the network at time (e.g., where is the set of vertices truly exist at ). Besides, each edge ( , ) ∈ in is associated with a propagation probability ( , ) ∈ [0, 1]. Table 1 summarizes the mathematical notations frequently used throughout this paper.

Link Prediction
Link prediction is an important network-related problem firstly proposed by Liben-Nowell et al. [31], which aims to infer the existence of new links or still unknown interactions between pairs of nodes based on their properties and the currently observed links.
Given a directed evolving graph G = −1 0 with the time points set {0, 1, .., − 1}, in this paper, we use the recent link prediction method [49,50], named learning from Subgraphs, Embeddings, and Attributes for Link prediction (SEAL) method, to predict the graph structure of snapshot graph of G at the future time point . Specifically, SEAL is a graph neural network (GNN) based link prediction method that transforms the traditional link prediction problem into the subgraph classification problem. It first extracts the ℎ-hop enclosing subgraph for each target link, and then applies a labeling trick, called Double Radius Node Labeling (DRNL), to add an integer label for each node relevant to the target link as its additional feature. Next, the above-labeled enclosing subgraphs are fed to GNN to classify the existence of links. Finally, it returns the predicted graph of evolving graph G at time point .

Influence Maximization (IM) Problem
To better understand the IM problem, we first introduce the influence diffusion evaluation of given users. The independent cascade (IC) model [23] is the widely adopted stochastic model which is used for modeling the influence propagation in social networks. In the IC model, for each graph snapshot , the propagation probability ( , ) of an edge ( , ) is used to measure the social impact from user to . This probability is generally set as ( , ) = 1 ( ) , where ( ) is the degree of . Every user is either in an activated state or inactive state. 0 be a set of initial activated users, and generates the active set for all time step ≥ 1 according to the following randomized rule. At every time step ≥ 1, we first set to be −1 ; Each user activated in time step has one chance to activate his or her neighbours with success probability ( , ). If successful, we then add into and change the status of to activated. This process continues until no more possible user activation. Finally, is returned as the activated user set of 0 .
Let ( , ) be the number of vertices that are activated by in graph snapshot on the above influence propagation process under the IC model. The IM problem aims to find a size-seed set with the maximum expected spread ( ( , )). We define the IM problem as follows: Definition 2.1 (IM problem [23]). Given a directed graph snapshot = ( , ), an integer , the IM problem aims to find an optimal seed set * satisfying, Let be the maximum expected spread of any size-seed set, then we have = ( ( * , )).

Reverse Reachable Sketch
The Reverse Influence Set (RIS) [3] sampling technique is a Reverse Reachable Sketch-based method to solve the IM problem. By reversing the influence diffusion direction and conducting reverse Monte Carlo sampling [25], RIS can significantly improve the theoretical run time bound.
Definition 2.2 (Reverse Reachable Set [3]). Suppose a user is randomly selected from . The reverse reachable (RR) set of is generated by first sampling a graph from , and then taking the set of users that can reach to in .
By generating 1 RR sets on random users, we can transform the IM problem to find the optimal seed set , while can cover most RR sets. This is because if a user has a significant influence on other users, this user will have a higher probability of appearing in the RR sets. Besides, Tang et al. [41] proved that when 1 is sufficiently large, RIS returns near-optimal results with at least 1− | | −1 probability. Therefore, the process of using the RIS method to solve the IM query contains the following steps: 1 Generate 1 random RR sets from . 2 Find the optimal user set which can cover the maximum number of above generated RR sets. 3 Return the user set as the query result of IM query problem. Theorem 2.1 (Complexity of RIS [40]). If 1 ≥ (8 + 2 ) · | | · | | + | | + 2 · 2 , RIS returns an (1 − 1 − ) approximate solution to the IM problem with at least 1 − | | −1 probability.

Forward Influence Sketch
The Forward Influence Sketch (FI-SKETCH) method [9, 10, 35] constructs a sketch by extracting the subgraph induced by an instance of the influence process (e.g., the IC model). Then, it can estimate the influence spread of a seed set using these subgraphs accurately with theoretical guarantee. The process of using the FI-SKETCH method to solve the IM query contains the following steps: 1 Generate 2 sketch subgraph by removing each edge = ( , ) from with probability 1 − , . 2 Find the optimal user set , while the average number of users reached by within 2 constructed sketches graphs is maximum. 3 Return the user set as the query result of IM query problem. Theorem 2.2 (Complexity of FI-SKETCH [9]).
) approximate solution to the IM problem with at least 1 − | | −1 probability.

PROBLEM DEFINITION
In this section, we formulate the Reconnecting Top-Relationships (RT R) query problem and analyze its complexity. Definition 3.1 (RT R Problem). Given a directed evolving graph G = { } −1 0 , the parameter , and a group of users U, the problem of Reconnecting Top-Relationships (RT R) asks for finding an optimal edge set with size in predicted graph snapshot of G at time , where the expected spread of U will be maximized while reconnecting edges of in (e.g., = ⊕ ). Formally, In the following, we conduct a theoretical analysis on the hardness of the RT R problem.
Proof. We prove the hardness of RT R problem by a reduction from the decision version of the maximum coverage (MC) problem [22]. Given an integer and several sets where the sets may have some elements in common, the maximum coverage problem aims to select at most of these sets to cover the maximum number of elements. Furthermore, we need to discuss the existence of a solution that the MC problem is reducible to the RT L problem in polynomial time.
Given a directed evolving graph G, a group of users U, and the predicted snapshot graph from G, we reduce the MC problem to RT L with the following process: (1) For a given group U, we compute the influence users set of U as (U, ); (2) ∀ ∈ G\ , we create a set with the elements collected from the influenced users (U, ) − (U, ) while = ⊕ ; (3) We set the reconnecting edges of RT L as , which is the same as the input of . The above reduction can be done in polynomial time. Since the Maximum Coverage problem is NP-hard, so is the RT L problem. □ Theorem 3.2 (Influence Spread). The influence spread function (.) under the RT R problem is monotone and submodular.

SKETCH BASED GREEDY ALGORITHM
To answer the RT R query problem, we first predict the graph structure of the given evolving graph G at by using the link prediction method [50]. According to Theorem 3.2, the influence spread function of RT R is submodularity and monotonicity. Therefore, one possible solution of the RT L problem is to use the greedy approach to iteratively find out the most influential edge , in which reconnecting in predicted snapshot graph will maximize the influence spread of given users group U in (e.g., = ⊕ ). So far, the remaining challenge of RT R query is to evaluate the effect of a reconnected edge on the influence spread of U in .

Existing IM Approaches Analysis
As mentioned in [23], we can estimate the influence spread of given users by using the Monte Carlo simulation. Specifically, given users group U, we simulate the randomized diffusion process with U in for R times. Each time we count the number of active users after the diffusion ends, and then we take the average of these counts over the R times as the estimated number of influenced users of U. However, the Monte Carlo simulation method is much time-consuming and cannot be used in the large graph. Later on, Borgs et al. [3] proposed a Reverse Reachable Sketch-based method to the IM problem, named Reverse Influence Set (RIS) sampling, and the extended versions of the RIS method [33,34,40] were widely used to answer the IM problem as the state-of-the-art IM query methods. The Reverse Influence Set (RIS) sampling technique is a Reverse Reachable Sketch-based method to the IM problem. By reversing the influence diffusion direction and conducting reverse Monte Carlo sampling, RIS can significantly improve the theoretical run time bound of the IM problem.
Unfortunately, the RIS sampling method is not suitable for answering our RT R query. That is because the RIS sampling is designed to find the Top-most influential users in a graph, but our RT R query focuses on reconnecting several optimal edges to enhance a given user group's influence spread. In particular, the RIS sampling method transforms the IM problem to find the optimal seed set by generating 1 RR sets, while can cover most RR sets. The RR sets only contain the user's information while discarding the graph sketch (e.g., the edge's information). Therefore, if we use the RIS sampling to answer the RT R query, we have to recompute the RR sets for each edge insertion during the RT R query process, which is time-consuming and unrealistic in large graphs.

FI-Sketch based Greedy Algorithm
Facing the challenges mentioned above, we propose a sketch-based greedy (SBG) method to answer the RT R query. Precisely, we first set 3 as a sufficient number of generated sketch subgraphs in our SBG method to theoretically ensure the quality of the returned results for the RT R query (i.e., the details of how 3 should be set will further discuss in Section 4.3). Then, we use the FI-SKETCH to evaluate the effect of a new adding edge on the influence spread of a given users group U based on the 3 generated sketch subgraphs. Compared with the RIS approach, the graph structure information was contained in the generated 3 sketch subgraphs during the process of the FI-SKETCH approach (refer to Section 2.4), so that we do not need to recompute the sketches while the edges update.
The details of the SBG method are described in Algorithm 1. In the pre-computing phase (Lines 1-3), we predict the snapshot graph using the link prediction method [50], and then generate 3 random sketch graphs by removing each edge = ( , ) from with probability 1 − , . Besides, based on Definition 3.1, we initialize ∈ {G \ } as the candidate edges set of the RT R query. In the main body of SBG (Lines 4-6), we use the greedy method to iteratively find the number of optimal reconnecting edges. Specifically, in each iterative, we call the FI-SKETCH Function to find out the optimal edge from the candidate edge set and add into set , while reconnecting the selected edge can maximize the influence diffusion of given users group U. Meanwhile, given an edge , the FI-SKETCH Function returns back the influenced users evaluation results by using the Forward Influence Sketch method mentioned in Section 2.4 (Lines [8][9][10][11][12][13][14]. Finally, we return edges set as the result of RT R query (Line 7). Complexity. The time complexity of calling the FI-SKETCH function for each candidate edges is O ( 3 · | |), while the space complexity is O ( 3 · (| | + | |)). Hence, the time complexity and space complexity of SBG algorithm are O ( · | | · 3 · | |) and O ( 3 · (| | + | |)), respectively.

Theoretical Analysis of SBG
In this part, we will establish our theoretical claims for SBG. Specifically, we analyze how 3 should be set to ensure our SBG method returns near-optimal results to RT R query with high probability. Our analysis highly relies on the Chernoff bounds [19].
Let U be a group of users, be the selected reconnecting edges, R 2 be the number of generated sketch subgraphs in the SBG algorithm (Algorithm 1), and (U, ) be the total number of additional reached users by U in each sketch subgraph after reconnecting edges in . From [35], the expected value of ( U, ) R 2 equals the expected influence diffusion enhance by reconnecting edges of in . Then, we have the following lemma.
Proof. Each sketch subgraph in the SBG algorithm is generated by removing each edge with 1− ( ) probability. From [35], we can observe that the expected value of the average number of reached users to U in all sketch subgraphs is equal to the expected spread of U in . From the above relation of equality, we can easily deduce that [ Proof. We can prove Theorem 4.1 by tweaking the proof in Theorem 2.1 of [40]. Let be the probability of U can activate a fixed user after reconnecting edges in in . Based on Lemma 4.2, Then, we have Let = 2| | . Based on Lemma 4.1, we have Thus, Theorem 4.1 is proved. □ utilizing the greedy algorithm of maximum coverage problem [22], which produces a (1 − 1 ) approximation solution (mentioned in Theorem 3.1). Finally, by combining the above two approximation ration 2 and (1− 1 ), we can conclude the final approximation ration of our SBG method for solving RT R query problem is (1 − 1 − ) with at least 1 − | | − probability. □

Reducing # Candidate Edges
Since the SBG algorithm's time complexity is cost-prohibitive, which would hardly be used for dealing with the sizeable evolving graph. In this subsection, we present our optimization method by pruning the unnecessary potential edges in candidate edge set . The core idea behind this optimization strategy is to eliminate the edges in which will not have any benefit to expend the influence spread of given users group U while reconnecting it.
We use the symbol U to denote that can be reached by U. In order to reduce the size of , we present the below theorem to identify the quality reconnecting edge candidates (denote as ) from . Theorem 4.3 (Reachability). Given a directed snapshot graph and a users group U, if an edge = ( , ) is selected to reconnect, one of its related users (i.e., or ) requires to be reached by U in ; that is ∈ implies U or U in .
Proof. We prove the correctness of this theorem by contradiction. The intuition is that at least one pathway exists from a user to all of its influenced users in social networks. For the selected edge = ( , ), if both the user and are not reached by the users group U, then the pathway between U and does not exist. Therefore, reconnecting the edge does not bring any benefits to the expansion of influence spread starting from U, which contradicts with Definition 3.1. Thus, the theorem is proved. □   Figure 2 shows a snapshot graph with 10 nodes and 9 edges. The candidate edges set of RT R is = {( 3 , 4 ), ( 5 , 6 ), ( 6 , 10 )}. For a given user group U = { 1 }, the pruned candidate edge set would be = {( 5 , 6 ), ( 6 , 10 )} due to 6 U.
Based on Theorem 4.3, we present a BFS-based method for pruning the candidate edge set in graph with a given users group U. The core idea of the BFS-based algorithm is to traverse the graph starting from the nodes in U by performing breadth-first search In Algorithm 2, we outline the major steps of the BFS-based method for processing the pruning. Initially, each user in graph are marked a visiting status as FALSE (Line 2). Then, for the users in a given group U, we update its visiting status as TRUE (Lines 3-5). Further, we process a BFS search starting from root user ∈ U, and update the status of each visited users as TRUE (Lines 6-12). Next, based on Theorem 4.3, we reduce all candidate edges = ( , ) from while both and have the FALSE visited status (Lines 13-17), and finally, we return the pruned candidate edges set (Line 18). Complexity. Obviously, for a given group U, the time complexity of Algorithm 2 is O (| | + | | + | |), and the space complexity is O (| |). Furthermore, the occupied space by Algorithm 2 will be released after the pruned candidate edges is returned. For each RT R query with a new given users group U as input, we need to recall the BFS-based pruning method to reduce the size of candidate set with time cost O (| | + | | + | |), which is the main drawback of the BFS-based pruning method.

THE IMPROVEMENT ALGORITHM
Although the SBG algorithm and its optimization method can successfully answer the RT R query problem, it is still time-consuming to handle the sizeable social networks. To address this limitation, in this section, we propose an ordered sketch-based greedy algorithm, which can significantly reduce the number of edges influence probing at each iterative of RT R query process, so as to answer the RT R query more efficiently.

Algorithm Overview
Let G = { 0 , 1 , ..., −1 } be an evolving graph. We first use the temporal link prediction method [56] to predict the future snapshot of graph , and the potential reconnecting edges will be selected from candidate edges set = {G \ }. Before introducing the core idea of our Order-based SBG algorithm, we first briefly review using the SBG algorithm to answer the RT R query and analyze the bottleneck of the SBG algorithm.
For each given users group U, the SBG algorithm aims to find reconnecting edges by iteratively probing each edge in to find out the edge in which reconnecting will bring the maximum benefits to the influence spread of U. The time complexity of influence spread by reconnection of an edge is O ( 3 · | |), which is the bottleneck of the SBG algorithm.
To deal with the above limitation of the SBG method, we propose an Order-based SBG algorithm, which focuses on reducing the number of edges probing in each iteration by using our elaboratively designed two-step bounds approach together with the order-based probing strategy. Specifically, we first generate a label index (UBL) to store the first step upper bound of influence spread expansion for each candidate edge ∈ w.r.t 1 ( ) (in Section 5.2). Then, we generate the initial second-step upper bound ( 2 ) for (i.e., 2 . ) from 1 ( ) of the UBL index. Next, in the influence spread expansion estimation query processing of each given users group U and probing edge , we narrow the second-step upper bound of and update the 1 ( ) value of UBL index, while the narrowed second-step upper bound will be served the optimal edge finding in the following iterations (in Section 5.3). Finally, we order the candidate edges by their 2 values. The edge probing at the current iteration will be early terminated while the second upper bound of probing edge is less than the present influence spread expansion estimation value (in Section 5.4).

Upper Bound Label (UBL) Construction
This section introduces how to build the label index (UBL) for each candidate edge. The UBL index contains two parts, including (1) the 3 sketch subgraphs ; (2) the first-step bound 1 ( ) of each candidate edge and its updating status. The details of UBL construction procedure is shown in Algorithm 3.
From Section 2.4, we first generate 3 sketch subgraphs from the predicted snapshot graph that will be used for the future influence spread estimation (Line 2). Then, for each candidate edge in , we initialize its updating mark (i.e., ( )) as 0. Meanwhile, we compute the number of vertices in that can be reached from as the first step upper bound of , denoted as 1 ( ) (Lines 3 -6). Finally, we store the Labeling Scheme (L, ) for RT R query processing (Line 7). Complexity. The time complexity of sketch subgraphs generation is O ( 3 · | |), and the 1 labeling construction of all candidate edges in is (| | · | |). Therefore, the time complexity of UBL construction is O ( 3 · | |+| | · | |). Besides, the space complexity of UBL index construction is O ( 3 · (| | + | |) + | |), while storage sketch subgraphs has space complexity ( 3 · (| | + | |)) and generating 1 labeling of edges in has space complexity of O (| |).

Influence Spread Expanding Estimation
Here, we present the influence spread expansion estimation of given users group U and edge . Further, we also introduce the strategies of narrowing the two-step upper bounds of (i.e., 1 ( ) and 2 ( )) during the above estimation process.

End Function
The details of the influence spread expansion estimation are described in Algorithm 4. For a given users group U and edge = ( , ), the Sketch-Estimate Function aims to compute the incremental of U's influence spread while reconnecting edge in graph . It takes sketch subgraphs , query edge and group U, influenced marking array , two-step bound 1 and 2 , and returns the influence spread expansion value of to U. We initialize two variable and as 0 (Line 2). Then, an inner loop fetches the total number of the reached nodes for in each sketch subgraph ∈ but not be reached by U (i.e., update the value of 2 as / 3 , which is also the influence spread expansion value of (Line 12); we also update 1 ( ) and remark ( ) = 1 of L when the original mark L. ( ) = 0 (Line 13 -15). Finally, the influence spread expansion of is returned (Line 16). It is remarkable that with the increasing number of RT R queries for different given users group U, the more edges' first-step upper bound 1 will be narrowed, so as to the performance of the later RT R query with new users group will increase with no additional cost. Complexity. It is easy for us to derive that the time complexity and space complexity of Algorithm 4 are O ( 3 · | |) and O ( 3 · | |), respectively.
Example 5.1. Figure 3 shows a running example of our two step bounds generation. For a given graph in Figure 2, we first identify the candidate edges set = {( 3 , 5 ), ( 5 , 6 ), ( 6 , 10 )}. Then, we compute the first-step bound of each edge in (e.g., 1 ( 3 , 5 )) and set its initial flag as −1. During the process of each RT L query with different given users group U, we will prune the candidate edges set from to , and call the Sketch-Estimate Function (e.g., Algorithm 4) to estimate the influence spread expansion of each probing edge (e.g., 2 = ( 5 , 6 )) from . Meanwhile, during the above process, we get a byproduct of 2 , the second step upper bound 2 ( 2 ), which can be used to narrow the first upper bound of 2 (e.g., 1 ( 2 ) ← 2 ( 2 )). Once 1 ( 2 ) is updated, 2 's flag also needs to be changed to +1.

Order-based SBG for RT R Query Processing
In the previous parts of this section, we have overviewed the main idea of our order-based SBG algorithm. We also have introduced the details of two essential blocks of our Order-based SBG algorithm: (i) the UBL construction and (ii) the Sketch-Estimation Function. In the rest of this section, we will discuss the details of the Order-based SBG algorithm. The details of the Order-based SBG algorithm are described in Algorithm 5. It takes an integer , a users group U, the candidate edges , and UBL index (L, ) as inputs, and returns a set of optimal reconnecting edges that maximizes the influence spread of U. We initialize a set as empty, an empty Priority queue that will be used to store the 2 information of candidate edges related to U, and an array to mark whether a node can be reached by U or edges in at each sketch subgraphs (Line 1). Then, we reduce the candidate edges from by using Algorithm 2, and record the reduced candidate edges into set (Line 2). For each edge in , we get 's first-step upper bound 1 ( ) from UBL index, and set 1 ( ) as the initial second-step upper bound value of (i.e., 2 ( ) = L. 1 ( )), and then push ( , 2 ( )) into priority queue (Lines 3 -16). Next, we mark the nodes which are reached by U in each sketch subgraphs of (Lines 5 -7). Further, in each iteration, we probe the candidate edges in priority queue in order based on their 2 value, and then call Sketch-Estimation Function to compute the influence spread expansion of the probing edge , the edge probing in this iteration will be early terminated once the front edge from Q is less than the currently maximum influence spread expansion value (Line 8). After finding out the optimal edge , we update the mark of nodes reached by in each sketch subgraphs (Lines 13 -17). Finally, it returns the optimal reconnecting edge set having maximum influence spread expansion of U (Line 25). Complexity. The time complexity of Algorithm 5 is O (| | + 3 · | | + · | | · 3 · | |). Besides, the space complexity is O (| | +

EXPERIMENTAL EVALUATION
In this section, we present the experimental evaluation of our proposed approaches for the RT L queries: the sketch based greedy algorithm (SBG) in Section 4.2; the candidate edges pruning method to accelerate SBG (CE-SBG) in Section 4.4; and the Order-based SBG solution (O-SBG) in Section 5.4.

Experimental Setting
We implement the algorithms using Python 3.6 on Windows environment with 2.90GHz Intel Core i7-10700 CPU and 64GB RAM.
Baseline. To the best of our knowledge, no existing work investigates the RT R problem. To further validate, we use our SBG algorithm as the baseline algorithm to compare with CE-SBG and O-SBG. This is because the well-known RIS based IM methods [34,40] are hardly used in the RT R query (i.e., mentioned in Section 4.1). Meanwhile, our SBG algorithm is extended from the FI-sketch IM method (i.e., SG algorithm [10]), while the SG algorithm performs well within the existing IM efforts, which has been validated in the state-of-the-art IM benchmark study [1]. Datasets. We conduct the experiments using five publicly available datasets from the Large Network Dataset Collection 2 : eu-core, Col-legeMsg, mathoverflow, ask-ubuntu, and stack-overflow. The statistics of the datasets are shown in Table 2. We have averagely divided all datasets into graph snapshots (e.g., = ( , ), ∈ [1, ]), where is the node and is the edges appearing in the time period of in each dataset. Parameter Configuration. Table 3 presents the parameter settings. We consider four parameters in our experiments: the number of queries , the size of given users group |U|, reconnecting edges size , and the number of snapshots . Besides, the near future snapshot +1 is generated by using the recent link prediction method [50] In each experiment, if one parameter varies, we use the default values for the other parameters. Besides, we set 3 = 200, which is consistent with [1].

Efficiency Evaluation
We study the efficiency of the approaches for the RT L problem regarding running time under different parameter settings. Figure 4 shows the average running time of our proposed methods by varying between 1 to 40. The running time of the algorithms follows similar trends, where SBG consumes maximum time to process an RT R query. On average, O-SBG is 65 to 99 times faster than CE-SBG, and 90 to 167 times faster than SBG. Also, CE-SBG is about 3 to 11 times faster than SBG in different datasets when varies from 2 to 40. Notably, when is larger than 30, the SBG algorithm fails to return the result of the RT R query within one day. As expected, the running time of both three approaches significantly increases when is varied from 1 to 40. Besides, the growth of running time in O-SBG is much slower than the other two algorithms. This is because the probing candidate edges will increase in all three approaches when increases, and O-SBG has the smallest number of probing candidate edges among the three approaches (refer to Figure 5).

Varying Reconnecting Edges Set Size .
The number of probing candidate edges of SBG, CE-SBG, and O-SBG with varying are presented in Figure 5(a)-5(d). As can be seen, the probing candidate edges of O-SBG is much less than SBG and CE-SBG for all values of . For example, when = 20, the probing candidate edges of SBG, CE-SBG, and O-SBG in mathoverflow are 91, 850, 28, 588, and 547, respectively. Besides, the number of probing candidate edges increases in all three approaches with the increase of , and O-SBG probing the least number of candidate edges in all three approaches. This result has verified the above explanation     Figure 7 shows the running time of the approaches by varying the size of users group U from 1 to 8. The results show similar findings that O-SBG outperforms CE-SBG and SBG as it utilizes the two step bounds to significantly reduce the probing candidate edges. For example, O-SBG can reduce the running time by around 150 times and 31 times compared with SBG and CE-SBG respectively under different |U| settings on the mathoverflow dataset.

Varying Snapshot Size .
We compare the efficiency of our proposed algorithms by varying the graph snapshots size from 20 to 100. Figure 8 presents the running time with varied values of . The results show similar finding that O-SBG outperforms SBG and CE-SBG in all datasets. Besides, we notice a similar running time trend in the proposed three methods when varies. Note that the running time does not always keep the same correlation with the varies of . This is because the performance of all three proposed approaches highly depends on the graph structure, and the number of snapshots does not show a perceptible effect on the network structure.   Figure 9 reports the average running time of O-SBG on mathoverflow. As we can see, the running time of O-SBG scales linearly with the increase of .

Effectiveness Evaluation
In this experiment, we evaluate the number of expanding influence users produced by the RT L problem with different datasets and approaches in Figure 10 - Figure 12 by varying one parameter and setting the others as defaults. As can be seen, the average number of influenced users of RT R queries in dense graphs is significantly larger than in sparse graphs for all three approaches. Figure 10 shows the average number of influenced users of all three approaches O-SBG, CE-SBG, and SBG on four datasets with varying . For example, in Figure 10 = 986, temporal edges = 332, 334, average degree = 25.28), respectively. Similar pattern can also be found in Figure 11 - Figure 12 as more influenced users be returned in dense graphs than in sparse graphs. In addition, Figure 11 reports that the influenced users of all three approaches do not always keep the same correlation with the increases of U. Figure 12 shows that the number of influenced users by all three approaches significantly increases when changes from 1 to 40. For example, the numbers of influenced users by O-SBG, CE-SBG, and SBG when setting as 40 are 23 times, 11 times, and 15 times larger than setting as 1 in the mathoverflow dataset. From the above experimental results, we can conclude that reconnecting the top-relationship query is necessary to maximize the benefits of expanding the influenced users of a given group.

RELATED WORK 7.1 Influence Maximization
Influence maximization (IM) was first formulated by Domingos et al. [13] as an algorithmic problem in probabilistic methods. Later on, Kempe et al. [23] modeled IM as an algorithmic problem in 2003. As the IM problem is NP-hard, all existing methods focus on approximate solutions, and a keystone of these algorithmic IM studies is the greedy framework. The existing IM algorithms can be categorized into three categories: simulation-based, proxy-based, and sketch-based. Simulation-based approaches. The key idea of these approaches is to estimate the influence spread ( ) of given users set by using the Monte Carlo (MC) simulations of the diffusion process [23,27,54]. Specifically, for a given users set , the simulation-based approaches simulate the randomized diffusion process with for times. Each time they count the number of active users after the diffusion ends, and then take the average of these counts over the times. The accuracy of these approaches is positively associated with the number of . The simulation-based approaches have the advantage of diffusion model generality, and these approaches can be incorporated into any classical influence diffusion model. However, the time complexity of these approaches are cost-prohibitive, which would hardly be used for dealing with sizeable networks. Proxy-based approaches. Instead of running heavy MC simulation, the proxy-based approaches estimate the influence spread of given users by using the proxy models. Intuitively, there are two branches of the proxy-based approaches, including (1) Estimate the influence spread of given users by transforming it to easier problems (e.g., Degree and PageRank) [6,15]; and (2) Simplify the typical diffusion model (e.g., IC model) to a deterministic model (e.g., MIA model) [6] or restrict the influence propagation range of given users under the typical diffusion model to the local subgraph [16], to precisely compute the influence spread of given users. Compared with the simulation-based approach, a proxy-based approach offers significant performance improvements but lacks theoretical guarantees. Sketch-based approaches. To avoid running heavy MC simulations and reserve the theoretical guarantee, the sketch-based approaches [3,9,10,33,35,40] pre-compute a number of sketches Q   under a specific diffusion model, and then speed up the influence evaluation based on the constructed sketches. Compared with the simulation-based approaches, the sketch-based approaches have a lower time complexity under a theoretical guarantee. Unfortunately, the sketch-based approaches are not generic to all diffusion models because the generated sketches of the sketch-based approaches are relay on the underlying diffusion models.

Link Prediction
Link prediction (LP) is an important network-related problem, first proposed by Liben-Nowell et al. [31]. The LP problem aims to infer the existence of new links or still unknown interactions between pairs of nodes based on the currently observed links. After decades study, a series of LP methods were proposed, including: similarity approaches [18,55], probabilistic approaches [12,44], hybrid approaches [46,52], and deep learning approaches [38,49,50].
In this paper, we use the SEAL method [49,50] to predict the structure of the near future (i.e., time point ) snapshot graph (i.e., ) for a given evolving graph. Furthermore, for each given users group U, our RT R query problem aims to reconnect a set of edges in to maximize the number of influenced users of U in , which is quite distinct from all existing IM works.

CONCLUSION
In this paper, we studied the problem of Reconnecting Top-Relationships (RT R), which aims to find previous existing relationships but being estranged subsequently, such that reconnecting these relationships would maximize the influence spread of given users group. We have shown that the RT L query problem is NP-hard. We developed a FI-Sketch based greedy (SBG) algorithm to solve this problem. We further devised an edge reducing method to prune the candidate edges that the given users' group cannot reach. Moreover, an order-based SBG method has been designed by utilizing the submodular characteristic of the RT L query and two well-designed upper bounds. Lastly, the extensive performance evaluations on real datasets also revealed the practical efficiency and effectiveness of our proposed method. In the future, we will focus on developing more efficient approaches to deal with the RT R queries in hyper scale networks.


Active-Learning-as-a-Service: An Automatic and Efficient MLOps System for Data-Centric AI

The success of today's AI applications requires not only model training (Model-centric) but also data engineering (Data-centric). In data-centric AI, active learning (AL) plays a vital role, but current AL tools 1) require users to manually select AL strategies, and 2) can not perform AL tasks efficiently. To this end, this paper presents an automatic and efficient MLOps system for AL, named ALaaS (Active-Learning-as-a-Service). Specifically, 1) ALaaS implements an AL agent, including a performance predictor and a workflow controller, to decide the most suitable AL strategies given users' datasets and budgets. We call this a predictive-based successive halving early-stop (PSHEA) procedure. 2) ALaaS adopts a server-client architecture to support an AL pipeline and implements stage-level parallelism for high efficiency. Meanwhile, caching and batching techniques are employed to further accelerate the AL process. In addition to efficiency, ALaaS ensures accessibility with the help of the design philosophy of configuration-as-a-service. Extensive experiments show that ALaaS outperforms all other baselines in terms of latency and throughput. Also, guided by the AL agent, ALaaS can automatically select and run AL strategies for non-expert users under different datasets and budgets. Our code is available at \url{https://github.com/MLSysOps/Active-Learning-as-a-Service}.

Introduction
Data-centric AI is an emerging topic that focuses on engineering data to develop AI applications with off-the-shelf machine learning (ML) models [14]. Previous efforts are mainly model-centric AI that assumes a static environment. In this environment, 1) the data collection and engineering are done, 2) and continuously developing ML models to achieve high performance on test sets is the main target [16]. However, real-world AI applications are facing more complicated scenarios, which can not be adequately addressed by model-centric AI. For instance, researchers and practitioners have to spend a lot of time on data preparation, including data labeling [9], and error detection [27]. Meanwhile, they also need to monitor the data, so that they can update models in time when a distribution drift is detected [23]. Treating these issues only from a model-centric view will lead to a sub-optimal solution. Therefore, to further improve and democratize AI applications, a lot of efforts are now turning to data-centric or combining model-centric and data-centric [14].
Though the concept of data-centric AI has been proposed very recently, many pioneering studies whose core contributions lie in data engineering have already been proposed [43,50]. Among them, one vital direction is active learning (AL) [37]. The motivation of AL is to reduce manual labeling efforts while maintaining and even improving ML models' performance [49,43,17,15,6,2,1,56,31]. Specifically, it is well-known that ML models are very data-hungry. Therefore, to reach a high performance (e.g., accuracy) that meets application requirements, people always need to label a large amount of data. This process is extremely time-consuming and labor-intensive and thus often becomes the bottleneck of ML application development. To cope with the issue, AL selects the most representative yet diverse training samples from a large training data pool by utilizing AL strategies. Then, it only sends the selected samples to an oracle (e.g., human annotators) to label. Next, ML models will only be trained on these labeled sub-datasets. By doing so, we can still obtain an ML model with competitive performance but save labeling and training costs a lot.
However, utilizing AL is a non-trivial task. First, selecting a suitable AL strategy for a specific scenario given the budget and target accuracy is hard for both experts and non-experts. As a result, users have to run AL in a trial-and-error manner, resulting in huge time and monetary waste. Second, applying AL to AI application development is not simply searching for, selecting, or implementing AL strategies. Instead, users have to build a backend to run the AL pipeline, tailored for their applications in their environment (e.g., a private cluster and AWS). In other words, they need to undertake much repetitive engineering work with boilerplate code. Third, users have to consider the efficiency and cost issues, as AL often runs on a vast dataset, and some AL strategies (e.g., committee-based [11,32]) require running more than one ML model for data selection. Under-consideration will result in a long process time and additional cost. Though several open-source AL tools [12,20,51,47] lower the barrier of applying AL, and they can meet neither automation nor efficiency requirements.
To address these issues, we propose an automatic and efficient backend for AL. Our AL system, named Active-Learning-as-a-Service (ALaaS) (Figure 1). It can select AL strategies automatically given the budget and target accuracy without specifying an AL strategy. Also, it can run AL strategies on large datasets efficiently by utilizing single or distributed multiple devices. Specifically, ALaaS adopts the server-client architecture to perform AL tasks and can be deployed easily on both laptops and public clouds as a service. To achieve high efficiency, it implements a stage-level parallelism method to run AL tasks by fully utilizing hardware resources and reducing waiting time. Meanwhile, more acceleration techniques such as data cache and batching [10,54,53] are utilized to further speed up the AL process. Besides, for users who have difficulty selecting a suitable AL strategy, ALaaS provides a predictive-based successive halving early-stop (PSHEA) procedure to automatically select and run AL with an only budget and target accuracy inputs. In addition to that, our system also considers accessibility and modularity, so that users can use many AL strategies in our AL zoo with ease, and experts can propose more advanced AL strategies for new scenarios. Experiments show that 1) our ALaaS outperforms all other baselines in terms of latency and throughput, and 2) the PSHEA procedure can predict future accuracy and select suitable AL strategies under different settings. Further ablation studies show the effectiveness of our design and reveal more insightful conclusions.

Related Work
This section presents the related work, including three categories: Active Learning (AL) algorithms and tools, Data-centric AI, and MLOps.

AL Algorithms and Tools
We categorize AL strategies into three classes, namely, diversity-based, uncertainty-based, and hybrid sampling. Diversity-based methods [52,43] are designed to select the most diverse samples from the whole dataset to represent it. Uncertainty-based methods [49,40,17] aim to select the samples that can not be identified confidently by current ML models and then use these samples to further  Figure 1: An overview of our ALaaS with human-in-the-loop. Our system adopts a server-client architecture. The data scientist first collects the unlabeled data and sends them to the AL server using an AL client, where an AL agent, a data cache and multiple workers will select data samples collaboratively and efficiently. The selected samples will be sent to a human oracle for labeling and then for updating models.
improve ML models. Hybrid methods [22,4] combine both the above-mentioned methods. Our system supports all of these methods and runs them more efficiently.
Many open-source AL tools have been developed to benefit both academia and industry, including ModAL [12], DeepAL [20], Libact [51], and ALiPy [47]. Our ALaaS is inspired by these tools and further improves AL efficiency and accessibility by adopting the MLOps concept. The detailed comparison is summarized in Table1.

Data-centric AI
Data-centric AI is proposed to improve AI application performance by engineering datasets rather than only focusing on models. Recent Data-centric AI competitions and workshops [14] demonstrate many exciting studies from academia and industry. Inspired by the pioneering work, many datacentric methods have been proposed for different areas, including Natural Language Processing (NLP) [50,44], Computer Vision (CV) [21,7], Robotics [30], etc. Also, a new benchmark [16] has been built for pushing forward data-centric AI research. To the best of our knowledge, ALaaS is the first MLOps system for efficient AL from the data-centric view.

MLOps
MLOps (Machine Learning Operation) aims to streamline the ML model development and reduce the AI application maintenance cost. Many MLOps systems have been proposed for both data-centric AI and model-centric AI [39]. From a data-centric view, labeling tools (e.g., labelme [41]), data cleaning tools (e.g., ActiveClean [26]), data drift monitors and many others, can all be regarded as MLOps systems. From a model-centric view, there are model store systems [48], model continuous integration [54,38] tools, training platforms [24], and deployment platforms [8], etc. Different from these systems, ALaaS is designed specifically for executing human-involved AL tasks more efficiently.

System Design and Architecture
This section first highlights our Active-Learning-as-a-Service (ALaaS) with two key features, then details the workflow and the core optimizations of the system as shown in Figure1. protocol: "grpc" host: "0.0.0.0" port: 60035 replicas: 1 Figure 2: An AL service can be easily configured and started with YML files.

ALaaS Highlights
We highlight two key features provided by our system, namely efficiency and automation. These features are also our design principles, leading the implementation to consider both experts (e.g., data scientists and machine learning engineers) and non-experts (e.g., customers with little domain knowledge) all the time. Besides, we list the main differences between our system and other existing tools in the table1.
Efficiency. Different from previous ALaaS python tools, our system is developed as a machine learning service. As a service, in addition to providing various AL strategies, our ALaaS offers efficiency to users by employing a lot of optimization technologies, including a pipeline process [34], ML serving backend adoption [36], and caching.
Automation. To further lower the barrier to use, an AL system should ensure that it can be utilized by non-AL experts with minimal effort and without writing much code. To this end, we design an AL agent to automate the AL strategy selection and the data selection procedures. With the AL agent, non-experts only need to input target accuracy and budget, then sit and wait for the final results.

ALaaS Workflow
As shown in Figure 1, ALaaS adopts the service-client architecture to abstract complex AL algorithms into web-based services, enabling an out-of-the-box user experience. Specifically, first, users only need to prepare a configuration file including basic settings like model name and serving device by following the provided templates, as shown in Figure 2. Then, with very few lines of code (LoCs), users can start both the AL client and AL server. Next, users will push their unlabeled datasets to the AL server. The dataset can be stored either in the local disk or AWS S3 [45]. Meanwhile, if users do not specify an AL strategy, ALaaS will invoke an AL agent to automatically select suitable strategies to perform data selection tasks to approach users' accuracy targets constrained by budget. Finally, the AL server will return a selected dataset for human labeling as well as further model updating.

ALaaS Optimization
Different from previous methods only providing AL strategy for accessibility, our ALaaS achieves high efficiency and automation by implementing a pipeline processing with a data cache, and an AL agent including a performance predictor and a loop controller.
Pipeline. As shown in Figure3, we divide the processing into three stages, downloading (red color), pre-processing (blue color), and AL (green color). Once users start to send datasets, the ALaaS server will parse the datasets' Uniform Resource Identifier (URI) [5] in the AL client and pipeline the data downloading and data pre-processing to reduce the hardware waiting time and improve the processing speed. Meanwhile, we implement a data cache to temporarily store the processed samples. By doing so, we further improve the processing speed. The reason is public clouds usually adopt the computation and storage separation design, and transferring the data back and forth between the current computation node to the storage node is very time-consuming. After the AL server receive a batch (batch size depends on users' settings) of raw samples, it will send them to optimized inference workers with ML serving backend for pre-processing (e.g., embedding calculation). Finally, those workers can return the processed data to the AL server for final data selection, then send the selected results back to the AL client. We observe that even with such a simple pipeline optimization, ALaaS's processing speed can become 10x times faster than the other open-source platforms (see Section 4.2).
AL agent. The AL agent implements a Predictive-based Successive Halving Early-stop (PSHEA) procedure (as shown in the Algorithm 1) to help users who are unsure about selecting AL strategies. Specifically, it includes a performance predictor and a loop controller. The performance predictor is a negative exponential forecasting model [25]. It predicts the next-round accuracy that can be achieved by a certain AL strategy under certain budget settings. The loop controller is to run many AL strategies as 'candidates' first and then decide which one should be eliminated at the current round (i.e., an early-stopping mechanism). After several rounds of reaching pre-defined targets (e.g., budget or accuracy), most AL strategies will be eliminated and the left strategies with the selected data samples will be suggested to users. This design is mainly based on the conclusion that no AL strategy can outperform all others under all settings [18]. With this AL agent, non-experts can utilize ALaaS in a cost-efficient manner rather than trying all AL strategies in a brute force manner.

System Evaluation
This section presents the quantitative evaluation of our systems. We first compare our system with other open-source platforms. Then we benchmark our system from different perspectives to demonstrate its efficiency and accessibility. 2. unlabeled data set ξ with size τ ; 3: 3. the maximum labeling budget b max (b max ≤ τ ); 4: 4. active learning strategy set L; 5: a 0 ← pre-train the deep active learning model and get the initial evaluation accuracy. 6: initialize 1. the maximum evaluation accuracy a max = a 0 ; 7: 2. active learning round r = 0; 8: 3. labeled data set d l ← ∅ for strategy l; a * l ← train a negative exponential forecasting model on historical a l and predict the 18: active learning accuracy a * l in the next round; 19: b total ← b total + b l r calculate the consumed total budget. 20: end for 21: r ← r + 1 22: a max ← update the best evaluation accuracy among all strategies; 23: if number of strategy in L > 1 then /* strategy-level early-stopping */ 24: stop and remove the strategy l with the least a * l from L; 25: end if 26: end while

Evaluation setup
We implement our ALaaS with Python, gRPC, etc., and conduct a set of benchmark studies with the following settings.
Hardware & Software. We conduct experiments on AWS EC2 and an Apple Mac Mini (M1 Chip). Our integrated data processing worker is NVIDIA Triton Inference Server [36].
Dataset. We evaluate our system on CIFAR-10 [28] and SVHN datasets. CIFAR-10 includes 50,000 training images and 10,000 test images. SVHN contains 600,000 images and we randomly sample 3,000 images as the test set and 10,000 images as the AL set to be labeled.
Model. We use the widely deployed ResNet-18 [19] model to benchmark systems under many settings. We only fine-tune ResNet-18's last layer with the AL-selected and human-labeled samples.

Comparison with other AL open source tools
The first experiment compares the efficiency of ALaaS with that of other baselines.
Settings. In this experiment, we simulate a one-round AL process, which applies AL methods to scan the whole dataset to generate a sub-pool at one-time. This sub-pool includes samples that will be used to improve an existing ML model further. Specifically, we first train an ML model with randomly selected 10,000 images from the CIFAR-10 training set as the initial model. Next, we use different AL tools to serve the whole AL pipeline on an AWS 3x.large CPU/GPU EC2. For all tools, we use the same AL strategy named least confidence sampling [29]. Finally, these tools will select 10,000 samples from the rest 40,000 images in the training set and we will compare their latency and throughput for an efficiency evaluation.
Results & Insights. The results are shown in Table2. Compared to other tools, our ALaaS achieves the lowest latency and highest throughput while still maintaining the same updated model evaluation accuracy. This efficiency improvement can be attributed to two sides. First, our ALaaS implements stage-level parallelism which reduces the device idle time extremely. Second, ALaaS allows us- ing multi-threads and distributed processing workers (e.g., Triton inference server for embedding extraction) to accelerate the data selection.

ALaaS Characterization
We further benchmark our ALaaS with different system settings. The first experiment is to evaluate different AL strategies re-implemented in our system. The second experiment explores the system efficiency on different batch sizes. The third experiment evaluates the proposed AL strategy autoselection procedure with an early-stopping algorithm.

AL strategy impact
Our ALaaS already provides many out-of-the-box AL strategies in AL Strategy Zoo for users. This experiment evaluates these strategies re-implemented by ALaaS from accuracy and efficiency views to provide more insights. All settings are the same as in the previous experiment.

Results & Insights. The evaluation model accuracy of different methods is shown in Figure4a.
Core-Set [43] achieves the highest accuracy with no surprise as it is designed for CNNs in Computer Vision (CV) tasks. Meanwhile, Diverse Mini-Batch (DBAL) [55] and Margin Confidence sampling (MC) [29] have the second and the third highest accuracy respectively, though they have proposed for a long time. This indicates that even in the deep learning (DL) era, conventional methods (e.g., calculating margins) still play a vital role and can cooperate with DL well.
The throughput comparison is shown in Figure4b. The least confidence sampling (LC) has the highest throughput while Core-Set selection achieves the lowest throughput. Given the accuracy 4aand the throughput 4b results, we can conclude that the accuracy improvement of Core-Set comes from its heavy design while conventional sampling methods like MC balances the trade-off between the accuracy and the efficiency well.

Batch size impact.
Settings. We evaluate the batch size (BS) impact on the public cloud (i.e., AWS with S3). We first store the CIFAR-10 dataset on an AWS S3 bucket. We then start ALaaS on a laptop to simulate an end-to-end AL process, including downloading data from other devices, pre-processing data, and selecting samples with an AL strategy. The other settings are the same as the first experiment.
Results & Insights. Our ALaaS can manage the whole process steadily and efficiently with different batch sizes, as shown in Figure4c. We can observe many interesting phenomena. First, BS = 1 and BS = 2 have very close throughput. Second, the increasing trend from BS = 4 to BS = 16 is dramatic. Third, after BS = 16, the increasing trend will stop. We attribute the reason that the transmission time accounts for a large proportion of the total processing time when the batch size is small. Therefore, the throughput improvement is marginal at the beginning. Then, as the batch computation time becomes the largest part of the total processing time, the improvement is dramatic. Finally, when the batch size reaches the computation capacity, this increasing diminishes.

PSHEA procedure evaluation.
Settings. We evaluate our AL agent with the PSHEA procedure on both CIFAR-10 and SVHN datasets. For both CIFAR-10 and SVHN experiments, we simulate an 8-round AL procedure.
Results & Insights. We first use the least confidence sampling strategy to evaluate the effectiveness of our accuracy prediction model mentioned in the Algorithm1. From Figure5a, we observe that the prediction model can foresee the accuracy very accurately, laying a solid foundation for later AL strategy auto-selection. Then, we run our AL agent with PSHEA. The AL agent will launch all 7 AL strategies as candidates in the first round and then eliminate strategies round by round. As shown in Figure5b, for two different datasets, our AL agent selects different AL strategies under different budges (i.e., the percentage of the labeled data in this experiment). This observation aligns with the conclusion from previous studies [18] and further shows the necessity of multi-round auto-selection, as no AL method can always out perform others under different budgets and datasets. Our method early stops many of the AL selection processes and helps to save running costs. INIT

Conclusion
This paper presents a new MLOps system, named ALaaS, for data-centric AI. ALaaS adopts the philosophy of Machine-Learning-as-Service and implements a server-client architecture, so users can use AL as a web service. Meanwhile, our system employs stage-level parallelism, data cache, and batching to improve AL running efficiency. Furthermore, it includes an AL agent with a predictivebased successive halving early-stop (PSHEA) procedure to select suitable AL strategies for users under different budgets and accuracy targets. Experiments show that our system has lower latency and higher throughput compared to all other baselines. Experiments also show that the auto-selection process can help users eliminate low-performing AL strategies earlier and save cost. We release our code at GitHub to facilitate the AL research.