In this study, we propose a novel model EAGLE for target-oriented dialogue generation. Without relying on any knowledge graphs, our method integrates the global planning strategy in both topic path generation and response generation given the initial and target topics. EAGLE comprises three components: a topic path sampling strategy, a topic flow generator, and a global planner. Our approach confers a number of advantages: EAGLE is robust to the target that has never appeared in the training data set and able to plan the topic flow globally. The topic path sampling strategy samples topic paths based on two predefined rules and use the sampled paths to train the topic path generator. The topic flow generator then applies a non-autoregressive method to generate intermediate topics that link the initial and target topics smoothly. In addition, the global planner is a response generator that generates a response based on the future topic sequence and conversation history, enabling it to plan how to transition to future topics smoothly. Our experimental results demonstrate that EAGLE produces more coherent responses and smoother transitions than state-of-the-art baselines, with an overall success rate improvement of approximately 25% and an average smoothness score improvement of 10% in both offline and human evaluations.

Competitive Influence Maximization (CIM) aims to maximize the influence of a party given the competition from other parties in the same social network, like companies find key users to promote their competitive products on the social network to achieve maximum profit. Recently, learning-based solutions are introduced to tackle the competitive influence maximization problem. However, such studies focus on the static nature of social networks. This paper proposes a deep reinforcement learning-based framework employing network embedding, termed as DRL-EMB, to tackle the CIM problem on evolving social networks. The DRL-EMB key objective is to find the best strategy to maximize the party's reward, considering budget and competition with information propagation and network evolving being run in parallel. We validate our proposed framework with the DRL-based model using hand-crafted state features (DRL-HCF) and heuristic-based methods. Experimental results show that our proposed framework, DRL-EMB, achieves better results than heuristic-based and DRL-HCF models while significantly outperforming the DRL-HCF model in terms of time efficiency.

Recent studies have considered the reinforcement and deep reinforcement learning models to address the competitive influence maximization (CIM) problem. However, these models assume complete network topology information is available to address the CIM problem. This assumption is unrealistic as it is difficult to obtain complete social network data and requires exhaustive efforts to obtain it. In this work, we propose a deep reinforcement learning-based (DRL) model to tackle the competitive influence maximization on unknown social networks. Our proposed model has a two-fold objective: the first is to identify the time when to explore the network to collect network information. The second is to determine key influential users from the explored network, using optimal seed-selection strategy considering the competition in the social network. Moreover, we integrate the transfer learning in DRL to improve the training efficiency of DRL models. Experimental results show that our proposed DRL and transfer learning-based DRL models achieve significantly better performance than heuristic-based methods.

In this work, we propose a GPU-accelerated algorithm for frequent pattern(FP) mining without candidate generation. We observe that the existing FP-growth algorithm has critical characteristics unsuitable for GPU, including the tree data structure, deep recursion and heavy dynamic memory allocations. By utilizing iterative execution and collectively allocating memory on GPU, our proposed method significantly reduce the latency caused by large memory allocations of original FP-growth. Experiment results show that our solution outperforms baselines, including sequential FP-growth with CPU only and existing GPU-accelerated Apriori and FP-growth, on various data sets with a significant speedup, from several times to hundred times.

Network embedding aims at learning an effective vector transformation for entities in a network. We observe that there are two diverse branches of network embedding: for homogeneous graphs and for multi-relational graphs. This paper then proposes MARINE, a unified embedding framework for both homogeneous and multi-relational networks to preserve both the proximity and relation information. We also extend the framework to incorporate existing features of nodes in a graph, which can further be exploited for the ensemble of embedding. Our solution possesses complexity linear to the number of edges, which is suitable for large-scale network applications. Experiments conducted on several real-world network datasets, along with applications in link prediction and multi-label classification, exhibit the superiority of our proposed MARINE.

We generalize the winning price model to incorporate the deep learning models with different distributions and propose an algorithm to learn from the historical bidding information, where the winning price are either observed or partially observed. We study if the successful deep learning models of the click-through rate can enhance the prediction of the winning price or not. We also study how different distributions of winning price can affect the learning results. Experiment results show that the deep learning models indeed boost the prediction quality when they are learned on the historical observed data. In addition, the deep learning models on the unobserved data are improved after learning from the censored data. The main advantage of the proposed generalized deep learning model is to provide more flexibility to model the winning price and improve the performance in consideration of the possibly various winning price distributions and various model structures in practice.

Research of social recommendation aims at exploiting social information to improve the quality of a recommender system. It can be further divided into two classes. Explicit social recommendation assumes the existence of not only the users' ratings on items, but also the explicit social connections between users. Implicit social recommendation assumes the availability of only the ratings but not the social connections between users, and attempts to infer implicit social connections between users with the goal to boost recommendation accuracy. This paper proposes a unified framework that is applicable to both explicit and implicit social recommendation. We propose an optimization framework to learn the degree of social correlation and rating prediction jointly, so these two tasks can mutually boost the performance of each other. Furthermore, a well-known challenge for implicit social recommendation is that it takes quadratic time to learn the strength of pairwise connections. This paper further proposes several practical tricks to reduce the complexity of our model to be linear to the observed ratings. The experiments show that the proposed model, with only two parameters, can significantly outperform the state-of-the-art solutions for both explicit and implicit social recommender systems.

In this paper, we propose SUbsequence Matching framework with cell MERgence (SUMMER) for online subsequence matching between histogram-based stream synopsis structures under the dynamic time warping distance. Given a query synopsis pattern, SUMMER continuously identifies all the matching subsequences for a stream as the bins are generated. To effectively reduce the computation time, we design a Weighted Dynamic Time Warping (WDTW) algorithm, which computes the warping distance directly between two histogram-based synopses. Furthermore, a Stack-based Overlapping Filter Algorithm (SOFA) is provided to remove the overlapping subsequences to avoid the redundant information. Finally, we design an optional refinement module to relax the subsequence range limit and improve the matching accuracy. Our experiments on real datasets show that the proposed method significantly speeds up the pattern matching without compromising the accuracy required when compared with other approaches.

Given a graph, can we find a set of patterns, of which the cost of storing these patterns is economic (or satisfying specific user needs) but their coverage includes the entire graph? We denote these patterns by principal patterns of the given graph since they can be regarded as its composition elements, which can be a signature for summarizing a graph of various sizes. Note that different principal patterns can contribute different sizes of graph coverage so they are not necessarily the frequent patterns. In this paper, we show that the recursive method can obtain the optimal solution while the greedy algorithms can find approximations with lower time complexity. Furthermore, we propose an effective pruning method that can be combined with both algorithms such that the mining process is even more efficient and scalable. Experiment results show that the proposed algorithms can efficiently and effectively discover the principal patterns.

In this paper, we propose a method to realize the Barabási-Albert (BA) model for generating large scale-free networks with preferential attachment. To our knowledge, the existing implementations of the BA model are still not very efficient because they failed to manage the temporary data of the network generating process properly by ignoring the inherent power law degree distribution property. To address this problem, we propose to leverage data structures including a prefix sum max heap and index arrays, which can competently manage nodes with different amount of connections. The proposed method is also friendly to the computing system with non-volatile memory (NVM) as main memory. Reducing long-latency write operations is the key to improve the efficiency of NVM, while the proposed method can ultimately save not only read operations but also significant amount of writes. We compare our proposed method with the baseline methods by generating networks of size from 102nodes to 108nodes. Experiment results show that the proposed method can save up to 50% of write counts. Furthermore, when using the phase change memory, a new byte-addressable non-volatile memory, as main memory, the proposed method can be almost two times faster.

We in this paper explore a novel model of influence minimization for the need to effectively prevent the outbreak of epidemic-prone spread on networks. The current network-blocking models usually report the expected number of infected nodes under the limited number of cutting edges. However, to control the epidemic-prone spread such as dengue fever, epidemiologists tend to deploy a cost-effective intervention with low outbreak risk, but the outbreak risk cannot be estimated based on the expectation of infected count. We in this paper explore the first solution to estimate the probability that can successfully bound the infected count below the out-of-control threshold, which can be logically mapped to the outbreak risk and can facilitate the authority to adaptively adjust the intervention cost for the need of risk control. We elaborate upon the proposed MCP (standing for Maximization of Containment Probability) problem and show that it is a NP-hard challenge without the submodular property. We further devise an effective measurement of sufficient number of Monte Carlo iterations based on the relative error of Monte Carol integration. The experimental results show that our proposed algorithm with small iterations can deliver the qualified guarantee of containment probability, demonstrating its feasibility for real applications.

In this paper, we study a novel problem of influence maximization in social networks: Given a period of promotion time and a set of target users, each of which can be activated by its neighbors multiple times, we aim at maximizing the total acceptance frequency of these target users by initially selecting k most influential seeds. The promising viral marketing paradigm on social network is different from the current research in two main aspects. First, instead of maximizing the message spread over the entire social network, we focus on the target market since the business vendors almost specify the target users before designing its marketing strategy. Second, the status of a user is no longer a binary indicator representing either active or inactive. In the new model the user status turns to be an integer value reflecting the amount of influences delivered to that user. In this paper, we prove the NP-hard nature of this challenging problem.

In this paper, we study an important issue whether the network properties on mobile social networks are still similar to these on traditional web-based social networks. To explore such answers is important since the paradigm shift has already happened from PC-based access to mobile access nowadays. In this paper, we focus on Instagram, which is a remarkable mobile-based photo sharing platform, as the reference network. We comprehensively study its network properties in the quantitative sense, and reveal some interesting results. Surprisingly, some properties in Instagram are highly diverse from these characteristics in traditional social networks such as Facebook and Twitter. We thus state that traditional assumptions on the network properties should be re-verified when developers devise social applications, such as the advertisement strategies, for mobile networks. We also conclude that the new research spectrum is highly demanded on network analysis and social technologies for the next-generation mobile-based social platform.

We study the fundamental k-nearest neighbor (kNN) search problem on distributed time series. A server has constantly received various reference time series Q of length X and seeks the exact kNN over a collection of time series distributed across a set of M local sites. When X and M are large, and when the amount of query increases, simply sending each Q to all M sites incurs high communication bandwidth costs, which we would like to avoid. Prior work has presented a communication-efficient kNN algorithm for the Euclidean distance similarity measure. In this paper, we present the first communication-efficient kNN algorithm for the dynamic time warping (DTW) similarity measure, which is generally believed a better measure for time series. To handle the complexities of DTW, we design a new multi-resolution structure for the reference time series, and multi-resolution lower bounds that can effectively prune the search space. We present a new protocol between the server and the local sites that leverages multi-resolution pruning for communication efficiency and cascading lower bounds for computational efficiency. Empirical studies on both real-world and synthetic data sets show that our method reduces communication bandwidth by up to 92%.

Online social connections allow users to share and spread information with others. Different users play various roles on information diffusion: some are influential within a community and some make information widely spread across communities. This paper aims to unveil the hidden relationships between nodes and information diffusion in the context of communities from the big Twitter diffusion data with a million-scale social network, as a complement to existing link-based diffusion analysis (e.g. the strength of weak ties). We identify six types of well-known community-aware roles of nodes, and examine their diffusion capability on propagating information within/across communities, using information flows via retweet and mention in Twitter. We find nodes acting as community bridges are exposed to more information and more dominative on spread information within/across communities. Community-aware roles are also validated via supervised learning to be effective for detecting the most diffusive information propagators.

Nowadays, companies are usually strongly interested in discovering the latent social influences among their customers since the information is highly valuable to their marketing strategies. In this paper, we study how to model the influence probabilities among the customers of a telecommunication company by analyzing their call records and mobile web browsing histories. We first construct a directed network using the phone call records. We verify whether the statistical properties of our constructed network follow the commonly known social network properties. Next, we propose several heuristics to measure the influence probabilities between users in the constructed network by analyzing both the call records and the mobile web browsing histories. Finally, we evaluate our proposed measurements by two prediction tasks, including predicting the lengths of a call and estimating the number of common website visits between two users. The results show that our proposed measurements are effective with better prediction accuracy.

We consider a novel distributed learning problem: A server receives potentially unlimited data from clients in a sequential manner, but only a small initial fraction of these data are labeled. Because communication bandwidth is expensive, each client is limited to sending the server only a small (high-priority) fraction of the unlabeled data it generates, and the server is limited in the amount of prioritization hints it sends back to the client. The goal is for the server to learn a good model of all the client data from the labeled and unlabeled data it receives. This setting is frequently encountered in real-world applications and has the characteristics of online, semi-supervised, and active learning. However, previous approaches are not designed for the client-server setting and do not hold the promise of reducing communication costs. We present a novel framework for solving this learning problem in an effective and communication-efficient manner. On the server side, our solution combines two diverse learners working collaboratively, yet in distinct roles, on the partially labeled data stream. A compact, online graph-based semi-supervised learner is used to predict labels for the unlabeled data arriving from the clients. Samples from this model are used as ongoing training for a linear classifier. On the client side, our solution prioritizes data based on an active-learning metric that favors instances that are close to the classifier's decision hyperplane and yet far from each other. To reduce communication, the server sends the classifier's weight-vector to the client only periodically. Experimental results on real-world data sets show that this particular combination of techniques outperforms other approaches, and in particular, often outperforms (communication expensive) approaches that send all the data to the server.

In the aspect of a Demand-Side Platform (DSP), which is the agent of advertisers, we study how to predict the winning price such that the DSP can win the bid by placing a proper bidding value in the real-time bidding (RTB) auction. We propose to leverage the machine learning and statistical methods to train the winning price model from the bidding history. A major challenge is that a DSP usually suffers from the censoring of the winning price, especially for those lost bids in the past. To solve it, we utilize the censored regression model, which is widely used in the survival analysis and econometrics, to fit the censored bidding data. Note, however, the assumption of censored regression does not hold on the real RTB data. As a result, we further propose a mixture model, which combines linear regression on bids with observable winning prices and censored regression on bids with the censored winning prices, weighted by the winning rate of the DSP. Experiment results show that the proposed mixture model in general prominently outperforms linear regression in terms of the prediction accuracy.

In the real-world, people would acquire or accept the same item, which can be a product, a service, or an event, multiple times. Meanwhile, an individual in a social network may influence others again and again. To address this phenomenon, we propose MIMA, a novel influence propagation model that describes the Multiple Influences and Multiple Acceptances of an individual on some item in a social network. MIMA models two important behaviors of influence and adoption: the marginal increase of a person's influence ability on others diminishes as he or she owns more that item, and the desire of a person to accept one more item will decrease as he or she already owns some. With the MIMA model, we study a new influence maximization problem in a social network where a person may accept the item multiple times: to select k initial promoters such that the final total acceptance volume of all people in the network is maximum. We prove this problem is NP-hard and propose greedy and heuristic algorithms. Experimental results show that the greedy algorithm achieves the best influence spread when compared to the existing algorithms. The influence spread of the heuristic algorithm is only slightly worse than that of the greedy algorithm but can save significant computation time.

In this work, we investigate the impact of social influence of a Facebook fan page on movie box offices. We aim to enhance the accuracy of predicting the box office by leveraging the social influence among users in the fan page. We develop the Global Influence Model to compute the user influence and predict the engagements between the fan page and users. In addition, we propose the Linear Box Office Revenue Prediction Model to bridge the gap between Facebook fan pages and the box offices by utilizing the social influence and some statistics obtained from Facebook fan pages. By considering the social influence, the accuracy of forecasting box offices for movies can be improved significantly.

In this paper, we tackle a novel type of interesting queries - shortest unique substring queries. Given a (long) string S and a query point q in the string, can we find a shortest substring containing q that is unique in S? We illustrate that shortest unique substring queries have many potential applications, such as information retrieval, bioinformatics, and event context analysis. We develop efficient algorithms for online query answering. First, we present an algorithm to answer a shortest unique substring query in O(n) time using a suffix tree index, where n is the length of string S. Second, we show that, using O(n·h) time and O(n) space, we can compute a shortest unique substring for every position in a given string, where h is variable theoretically in O(n) but on real data sets often much smaller than n and can be treated as a constant. Once the shortest unique substrings are pre-computed, shortest unique substring queries can be answered online in constant time. In addition to the solid algorithmic results, we empirically demonstrate the effectiveness and efficiency of shortest unique substring queries on real data sets.

In M2M applications, it is very common to encounter the ad hoc snapshot query that requires fast responses from many local machines in which all the data are distributed. In the scenario when the query is more complex, the communication cost for sending it to all the local machines for processing can be very high. This paper aims to address this issue. Given a reference set of multiple and large-size patterns, we propose an approach to identifying its k nearest and farthest neighbors globally across all the local machines. By decomposing the reference patterns into a multi-resolution representation and using novel distance bound designs, our method guarantees the exact results in a communication-efficient manner. Analytical and empirical studies show that our method outperforms the state-of-the-art methods in saving significant bandwidth usage, especially for large numbers of machines and large-sized reference patterns.

Closeness centrality measures the communication efficiency of a specific vertex within a network while the average path length (APL) measures that of the whole network. Since the nature of these two measurements is based on the computation of all-pair shortest path distances, one can perform the breadth-first search method starting at every vertex and obtain the two measurements. However, as the edge counts in the real-world networks like Facebook increase over time, this naive way is obviously inefficient. In this paper, we proposed CENDY, an efficient approach to updating Closeness centrality and average path length in Dynamic networks when there is an edge insertion or deletion. In CENDY, we derived some theoretical properties to quickly identify a set of vertices whose shortest path changed after an edge update, and then update the closeness centralities of those vertices only as well as the APL of the graph by a few of single-source shortest path computations. We conducted extensive experiments to show that, when compared to the existing methods of computing exact or approximate values, CENDY outperformed others in significantly low update time while providing exact values of the two measurements on various real-world graph datasets.

An object can move with various speeds and arbitrarily changing directions. Given a bounded area where a set of objects moving around, there are some typical moving styles of the objects at different local regions due to the geography nature or other spatiotemporal conditions. Not only the paths that the objects move along, we also want to know how different groups of objects move with various speeds. Therefore, given a set of collected trajectories spreading in a bounded area, we are interested in discovering the typical moving styles in different regions of all the monitored moving objects. These regional typical moving styles are regarded as the profile of the monitored moving objects, which may help reflect the geoinformation of the observed area and the moving behaviors of the observed moving objects. In this paper, we present DivCluST, an approach to finding regional typical moving styles by dividing and clustering the trajectories in consideration of both the spatial and temporal constraints. Different from the existing works that consider only the spatial properties or just the interesting regions of trajectories, DivCluST focuses more on typical movements in local regions of a bounded area and takes the temporal information into account when designing the criteria for trajectory dividing and the distance measurement for adaptive $(k)$-means clustering. Extensive experiments on three types of real data sets with specially designed visualization are presented to show the effectiveness of DivCluST.

Errors in measurement can be categorized into two types: systematic errors that are predictable, and random errors that are inherently unpredictable and have null expected value. Random error is always present in a measurement. More often than not, readings in time series may contain inherent random errors due to causes like dynamic error, drift, noise, hysteresis, digitalization error and limited sampling frequency. Random errors may affect the quality of time series analysis substantially. Unfortunately, most of the existing time series mining and analysis methods, such as similarity search, clustering, and classification tasks, do not address random errors, possibly because random error in a time series, which can be modeled as a random variable of unknown distribution, is hard to handle. In this paper, we tackle this challenging problem. Taking similarity search as an example, which is an essential task in time series analysis, we develop MISQ, a statistical approach for random error reduction in time series analysis. The major intuition in our method is to use only the readings at different time instants in a time series to reduce random errors. We achieve a highly desirable property in MISQ: it can ensure that the recall is above a user-specified threshold. An extensive empirical study on 20 benchmark real data sets clearly shows that our method can lead to better performance than the baseline method without random error reduction in real applications such as classification. Moreover, MISQ achieves good quality in similarity search.

We present PROUD -- A PRObabilistic approach to processing similarity queries over Uncertain Data streams, where the data streams here are mainly time series streams. In contrast to data with certainty, an uncertain series is an ordered sequence of random variables. The distance between two uncertain series is also a random variable. We use a general uncertain data model, where only the mean and the deviation of each random variable at each timestamp are available. We derive mathematical conditions for progressively pruning candidates to reduce the computation cost. We then apply PROUD to a streaming environment where only sketches of streams, like wavelet synopses, are available. Extensive experiments are conducted to evaluate the effectiveness of PROUD and compare it with Det, a deterministic approach that directly processes data without considering uncertainty. The results show that, compared with Det, PROUD offers a flexible trade-off between false positives and false negatives by controlling a threshold, while maintaining a similar computation cost. In contrast, Det does not provide such flexibility. This trade-off is important as in some applications false negatives are more costly, while in others, it is more critical to keep the false positives low.

We present LeeWave --- a bandwidth-efficient approach to searching range-specified k -nearest neighbors among distributed streams by LEvEl-wise distribution of WAVElet coefficients. To find the k most similar streams to a range-specified reference one, the relevant wavelet coefficients of the reference stream can be sent to the peer sites to compute the similarities. However, bandwidth can be unnecessarily wasted if the entire relevant coefficients are sent simultaneously. Instead, we present a level-wise approach by leveraging the multi-resolution property of the wavelet coefficients. Starting from the top and moving down one level at a time, the query initiator sends only the single-level coefficients to a progressively shrinking set of candidates. However, there is one difficult challenge in LeeWave: how does the query initiator prune the candidates without knowing all the relevant coefficients? To overcome this challenge, we derive and maintain a similarity range for each candidate and gradually tighten the bounds of this range as we move from one level to the next. The increasingly tightened similarity ranges enable the query initiator to effectively prune the candidates without causing any false dismissal. Extensive experiments with real and synthetic data show that, when compared with prior approaches, LeeWave uses significantly less bandwidth under a wide range of conditions.

In applications of multiple data streams such as stock market trading and sensor network data analysis, the clusters of streams change at different time because of the data evolution. The information of evolving cluster is valuable to support corresponding online decisions. In this paper, we present a framework for Clustering Over Multiple Evolving sTreams by CORrelations and Events, which, abbreviated as COMETCORE, monitors the distribution of clusters over multiple data streams based on their correlation. Instead of directly clustering the multiple data streams periodically, COMET-CORE applies efficient cluster split and merge processes only when significant cluster evolution happens. Accordingly, we devise an event detection mechanism to signal the cluster adjustments. The coming streams are smoothed as sequences of end points by employing piecewise linear approximation. At the time when end points are generated, weighted correlations between streams are updated. End points are good indicators of significant change in streams, and this is a main cause of cluster evolution event. When an event occurs, through split and merge operations we can report the latest clustering results. As shown in our experimental studies, COMET-CORE can be performed effectively with good clustering quality.

In the data stream environment, the patterns generated at different time instances are different due to data evolution. As time progresses, the behavior and members of clusters usually change. Hence, clustering continuous data streams allows us to observe the changes of group behavior. In order to support flexible clustering requirements, we devise in this paper a Clustering on Demand framework, abbreviated as COD framework, to dynamically cluster multiple data streams. While providing a general framework of clustering on multiple data streams, the COD framework has two advantageous features, namely, one data scan for online statistics collection and compact multiresolution approximations, which are designed to address, respectively, the time and the space constraints in a data stream environment. The COD framework consists of two phases, i.e., the online maintenance phase and the offline clustering phase. The online maintenance phase provides an efficient mechanism to maintain summary hierarchies of data streams with multiple resolutions in time linear in both the number of streams and the number of data points in each stream. On the other hand, an adaptive clustering algorithm is devised for the offline phase to retrieve approximations of desired substreams from summary hierarchies according to clustering queries. We propose two summarization techniques, based on wavelet and regression analyses, to construct the summary hierarchies. The regression-based summary hierarchy approximates the data stream more precisely and provides better clustering results, at the cost of slightly longer time than and twice the storage space as the wavelet-based one. An adaptive version of COD framework is designed to make a selection between a wavelet-based model and a regression-based model for building the summary hierarchy. By the adaptive COD, we can obtain clustering results with almost the same quality as the regression-based COD while using much less storage space for the summary hierarchy. As shown in the complexity analyses and also validated by our empirical studies, the COD framework performs very efficiently in the data stream environment while producing clustering results of very high quality.

In the data stream environment, the patterns generated by the mining techniques are usually distinct at different time because of the evolution of data. In order to deal with various types of multiple data streams and to support flexible mining requirements, we devise in this paper a clustering on demand framework, abbreviated as COD framework, to dynamically cluster multiple data streams. While providing a general framework of clustering on multiple data streams, the COD framework has two major features, namely one data scan for online statistics collection and compact multiresolution approximations, which are designed to address, respectively, the time and the space constraints in a data stream environment. Furthermore, with the multiresolution approximations of data streams, flexible clustering demands can be supported.