Search

Name disambiguation is a key and also a very tough problem in many online systems such as social search and academic search. Despite considerable research, a critical issue that has not been systematically studied is disambiguation on the fly — to complete the disambiguation in the real-time. This is very challenging, as the disambiguation algorithm must be accurate, efficient, and error tolerance. In this paper, we propose a novel framework — CONNA — to train a matching component and a decision component jointly via reinforcement learning. The matching component is responsible for finding the top matched candidate for the given paper, and the decision component is responsible for deciding on assigning the top matched person or creating a new person. The two components are intertwined and can be bootstrapped via jointly training. Empirically, we evaluate CONNA on two name disambiguation datasets. Experimental results show that the proposed framework can achieve a 1.21-19.84 percent improvement on F1-score using joint training of the matching and the decision components. The proposed CONNA has been successfully deployed on AMiner — a large online academic search system. [ABSTRACT FROM AUTHOR]

Bipartite graphs widely exist in real-world scenarios and model binary relations like host-website, author-paper, and user-product. In bipartite graphs, a butterfly (i.e., $2\times 2$ 2 × 2 bi-clique) is the smallest non-trivial cohesive structure and plays an important role in applications such as anomaly detection. Considerable efforts focus on counting butterflies in static bipartite graphs. However, they suffer from high time and space complexity when the bipartite graph of interest is given as a stream of edges. Although there are methods for approximately counting butterflies from bipartite graph streams, they suffer from either low accuracy or high time complexity. Therefore, it is still a challenge to accurately estimate butterfly counts from bipartite graph streams in a short time. To address this issue, we develop novel algorithms by exploiting the bipartite nature, which subtly integrates sampling and sketching techniques. We provide accurate estimators for butterfly counts and derive simple yet exact formulas for bounding their errors. We also conduct extensive experiments on a variety of real-world large bipartite graphs. Experimental results demonstrate that our algorithms are up to 20.0 times more accurate and up to 286.3 times faster than state-of-the-art methods under the same memory usage. [ABSTRACT FROM AUTHOR]

Heterogeneous graph embedding aims at learning low-dimensional representations from a graph featuring nodes and edges of diverse natures, and meanwhile preserving the underlying topology. Existing approaches along this line have largely relied on meta-paths, which are by nature hand-crafted and pre-defined transition rules, so as to explore the semantics of a graph. Despite the promising results, defining meta-paths requires domain knowledge, and thus when the test distribution deviates from the priors, such methods are prone to errors. In this paper, we propose a self-learning scheme for heterogeneous graph embedding, termed as self-guided walk (SILK), that bypasses meta-paths and learns adaptive attentions for node walking. SILK assumes no prior knowledge or annotation is provided, and conducts a customized random walk to encode the contexts of the heterogeneous graph of interest. Specifically, this is achieved via maintaining a dynamically-updated guidance matrix that records the node-conditioned transition potentials. Experimental results on four real-world datasets demonstrate that SILK significantly outperforms state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Twitter, a microblogging platform, has developed into an increasingly invaluable information source, where millions of users post a great quantity of tweets with various topics per day. Heterogeneous information networks consisting of multi-type objects and relations are becoming more and more prevalent as an organization form of knowledge and information. The task of linking an entity mention in a tweet with its corresponding entity in a heterogeneous information network is of great importance, for the purpose of enriching heterogeneous information networks with the abundant and fresh knowledge embedded in tweets. However, the entity mention is ambiguous. Additionally, tweets are short and informal, making it difficult to mine enough information from a single tweet for entity linking. In this paper, we propose an unsupervised iterative clustering framework TELHIN to link multiple similar tweets with a heterogeneous information network jointly. Our framework takes three dimensions of tweet similarity into consideration: (1) content similarity, (2) temporal similarity, and (3) user similarity. The appropriate weights of different similarity dimensions for each entity mention are learned iteratively based on the metric learning algorithm by leveraging the pairwise constraints generated automatically. Experiments on real data demonstrate the effectiveness of our framework in comparison with the baselines. [ABSTRACT FROM AUTHOR]

Heterogeneous information network (HIN) embedding aims at learning the low-dimensional representation of nodes while preserving structure and semantics in a HIN. Existing methods mainly focus on static networks, while a real HIN usually evolves over time with the addition (deletion) of multiple types of nodes and edges. Because even a tiny change can influence the whole structure and semantics, the conventional HIN embedding methods need to be retrained to get the updated embeddings, which is time-consuming and unrealistic. In this paper, we investigate the problem of dynamic HIN embedding and propose a novel Dynamic HIN Embedding model (DyHNE) with meta-path based proximity. Specifically, we introduce the meta-path based first- and second-order proximities to preserve structure and semantics in HINs. As the HIN evolves over time, we naturally capture changes with the perturbation of meta-path augmented adjacency matrices. Thereafter, we learn the node embeddings by solving generalized eigenvalue problem effectively and employ eigenvalue perturbation to derive the updated embeddings efficiently without retraining. Experiments show that DyHNE outperforms the state-of-the-arts in terms of effectiveness and efficiency. [ABSTRACT FROM AUTHOR]

Stream processing is used in various fields. In the field of big data, stream aggregation is a popular processing technique, but it suffers serious setbacks when the order of events (e.g., stream elements) occurring is different from the order of events arriving to the systems. Such data streams are called “non-FIFO steams”. This phenomenon usually occurs in a distributed environment due to many factors, such as network disruptions, delays, etc. Many analyzing scenarios require efficient processing of such non-FIFO streams to meet various data processing requirements. This paper proposes an efficient scalable checkpoint-based bidirectional indexing approach, called $CPiX$ C P i X , for faster real-time analysis over non-FIFO streams. CPiX maintains the partial aggregation results in an on-demand manner per checkpoint. CPiX needs less time and space than the state-of-the-art approach. Extensive experiments confirm that CPiX can deal with out-of-order streams very efficiently and is, on average, about 3.8 times faster than the state-of-the-art approach while consuming less memory. [ABSTRACT FROM AUTHOR]

Many datasets including social media data and bibliographic data can be modeled as graphs. Clustering such graphs is able to provide useful insights into the structure of the data. To improve the quality of clustering, node attributes can be taken into account, resulting in attributed graphs. Existing attributed graph clustering methods generally consider attribute similarity and structural similarity separately. In this paper, we represent attributed graphs as star-schema heterogeneous graphs, where attributes are modeled as different types of graph nodes. This enables the use of personalized pagerank (PPR) as a unified distance measure that captures both structural and attribute similarities. We employ DBSCAN for clustering, and we update edge weights iteratively to balance the importance of different attributes. The rapidly growing volume of data nowadays challenges traditional clustering algorithms, and thus, a distributed method is required. Hence, we adopt a popular distributed graph computing system Blogel, based on which, we develop four exact and approximate approaches that enable efficient PPR score computation when edge weights are updated. To improve the effectiveness of the clustering, we propose a simple yet effective edge weight update strategy based on entropy. In addition, we present a game theory based method that enables trading efficiency for result quality. Extensive experiments on real-life datasets offer insights into the effectiveness and efficiency of our proposals. [ABSTRACT FROM AUTHOR]

In recommendation tasks, we model user preferences by learning node representations (i.e., user and item embeddings) based on the observed user-item interaction data, which is a bipartite graph. Graph Neural Networks (GNNs) are widely used to refine the representations by exploring the topology of the graph: embeddings of neighbors are propagated to each node to reconstruct its embeddings. However, the propagation strategy in existing GNNs is empirical and defective: (1) a substantial proportion of links are missed in the sparse observed graph, which causes ineffective and biased propagation; and (2) the propagation weights are determined by a coarse pre-defined rule, which only takes the degree of nodes into consideration. In this paper, we propose a dense and data-driven propagation mechanism for GNNs. Considering the graph we use to propagate embeddings in recommendation tasks is extremely sparse, we complement it and use the predicted graph as the new propagation tool. We learn the propagation matrix from the data, and propose a Self-propagation Graph Neural Network (SGNN). Since it is very space- and time-consuming to maintain a large and dense propagation matrix, we factorize it for storing and updating. In this paper, we propose three methods to complete the sparse graph and construct the propagation matrix: (1) we complete the graph based on a recommendation model; (2) we measure the node distance based on spectral clustering; (3) we predict missing links of the graph based on predictive embeddings. In SGNN, the embeddings can be propagated to not only the observed neighbors, but also the potential yet unobserved neighbors, and the propagation weights are learned based on the connection strength. Comprehensive experiments on three real-world datasets demonstrate the effectiveness and efficiency of our proposed model: SGNN outperforms recent state-of-the-art GNNs significantly. Codes are available on https://github.com/Wenhui-Yu/LCFN. [ABSTRACT FROM AUTHOR]

Multi-Task Learning (MTL) is a learning paradigm in machine learning and its aim is to leverage useful information contained in multiple related tasks to help improve the generalization performance of all the tasks. In this paper, we give a survey for MTL from the perspective of algorithmic modeling, applications and theoretical analyses. For algorithmic modeling, we give a definition of MTL and then classify different MTL algorithms into five categories, including feature learning approach, low-rank approach, task clustering approach, task relation learning approach and decomposition approach as well as discussing the characteristics of each approach. In order to improve the performance of learning tasks further, MTL can be combined with other learning paradigms including semi-supervised learning, active learning, unsupervised learning, reinforcement learning, multi-view learning and graphical models. When the number of tasks is large or the data dimensionality is high, we review online, parallel and distributed MTL models as well as dimensionality reduction and feature hashing to reveal their computational and storage advantages. Many real-world applications use MTL to boost their performance and we review representative works in this paper. Finally, we present theoretical analyses and discuss several future directions for MTL. [ABSTRACT FROM AUTHOR]

Multi-relational learning on knowledge graphs infers high-order relations among the entities across the graphs. This learning task can be solved by label propagation on the tensor product of the knowledge graphs to learn the high-order relations as a tensor. In this paper, we generalize a widely used label propagation model to the normalized tensor product graph, and propose an optimization formulation and the scalable Low-rank Tensor-based Label Propagation algorithm (LowrankTLP) to infer multi-relations for two learning tasks, hyperlink prediction and multiple graph alignment. The optimization formulation minimizes the upper bound of the noisy-tensor estimating error for multiple graph alignment, by learning with a subset of the eigen-pairs in the spectrum of the normalized tensor product graph. We also provide a data-dependent transductive Rademacher bound for binary hyperlink prediction. We accelerate LowrankTLP with parallel tensor computation which enables label propagation on a tensor product of 100 graphs each of size 1000 in less than half hour in the simulation. LowrankTLP was also applied to predicting the author-paper-venue hyperlinks in publication records, alignment of segmented regions across up to 26 CT-scan images and alignment of protein-protein interaction networks across multiple species. The experiments demonstrate that LowrankTLP indeed well approximates the original label propagation with better scalability and accuracy. [ABSTRACT FROM AUTHOR]

The natural gas tightly correlates with our everyday life. However, driven by gray incomes, some users are prone to stealing gas by refitting the equipment without permission. Especially for the boiler room users in winter, this phenomenon appears more rampant. Traditional gas-theft detection methods highly rely on the on-site inspection, where exists ineffective and randomness. With the rapidly deployed IoT sensors, we can collect real-time gas consumption data to analyze users’ behavior patterns, where the gas-theft suspects could be discovered early and accurately. In this paper, we propose a data-driven approach, named SVOC, to detect gas-theft suspects among boiler room users. Our approach consists of a scenario-based data quality detection algorithm, a deformation-based normality detection algorithm, and an One-Class Support Vector Machine (OCSVM) based anomaly detection algorithm. Specifically, considering the temporal proximity between the gas consumption and the outdoor temperature, the normality detection algorithm adopts a similarity-based deformation correlation to detect normal boiler room users out of abnormal ones. Then, we employ OCSVM as the anomaly detection algorithm to capture various features across multiple data sources, aiming to distinguish gas-theft suspects from the remaining irregular users. Here, the detected normal and abnormal users are fed into the OCSVM for training and prediction, respectively, which can overcome the label scarcity problem. We conduct extensive experiments on a real-world dataset during one heating season. The results demonstrate distinct advantages of our approach over various baselines. We have developed a real-time system on the cloud, providing daily gas-theft suspects for gas companies. [ABSTRACT FROM AUTHOR]

Entity resolution (ER) identifies data instances referring to the same real-world entity and has received enormous research attention. In this paper, we examine the task of ER from a broader perspective, with its input extended from textual records, which are conventionally studied in the literature, to other modalities such as check-in sequences, GPS trajectories and surveillance video frames to generate new applications. Our goal in this paper is to design an effective model to uniformly support all these ER applications with different input formats. Technically, we fully exploit the semantic contexts of embedding vectors for the pair of input instances. In particular, we propose an integrated multi-context attention framework that takes into account self-attention, pair-attention and global-attention from three types of context. The idea can be further extended to incorporate attribute attention in order to support structured datasets. We conduct extensive experiments on a diverse class of entity resolutions tasks, including tasks on unstructured, structured and dirty textual records, check-in sequences, GPS trajectories and surveillance video frames. The experimental results verified the effectiveness and generality of our model. When compared with strong baselines in these applications, our model can achieve superior or comparative performance. [ABSTRACT FROM AUTHOR]

Network alignment is a critical task in a wide variety of fields. Many existing works leverage on representation learning to accomplish this task without eliminating domain representation bias induced by domain-dependent features, which yield inferior alignment performance. This paper proposes a unified deep architecture (DANA) to obtain a domain-invariant representation for network alignment via an adversarial domain classifier. Specifically, we employ the graph convolutional networks to perform network embedding under the domain adversarial principle, given a small set of observed anchors. Then, the semi-supervised learning framework is optimized by maximizing a posterior probability distribution of observed anchors and the loss of a domain classifier simultaneously. We also develop a few variants of our model, such as, direction-aware network alignment, weight-sharing for directed networks and simplification of parameter space. Experiments on three real-world social network datasets demonstrate that our proposed approaches achieve state-of-the-art alignment results. [ABSTRACT FROM AUTHOR]

Many modern navigation systems and map-based services do not only provide the fastest route from a source location $s$ s to a target location $t$ t but also provide a few alternative routes to the users as more options to choose from. Consequently, computing alternative paths has received significant research attention. However, it is unclear which of the existing approaches generates alternative routes of better quality because the quality of these alternatives is mostly subjective. Motivated by this, in this paper, we present a user study conducted on the road networks of Melbourne, Dhaka and Copenhagen that compares the quality (as perceived by the users) of the alternative routes generated by four of the most popular existing approaches including the routes provided by Google Maps. We also present a web-based demo system that can be accessed using any internet-enabled device and allows users to see the alternative routes generated by the four approaches for any pair of selected source and target. We report the average ratings received by the four approaches and our statistical analysis shows that there is no credible evidence that the four approaches receive different ratings on average. We also discuss the limitations of this user study and recommend the readers to interpret these results with caution because certain factors may have affected the participants’ ratings. [ABSTRACT FROM AUTHOR]

To obtain reliable results from conflicting data in mobile crowdsensing, numerous truth discovery protocols have been proposed in the past decade. However, most of them do not consider the data privacy of entities involved (e.g., workers and servers), and several existing privacy-preserving truth discovery protocols either provide limited privacy protection or have heavy computation and communication overheads due to iterative computation and transmission over large ciphertexts. In this paper, we aim to propose privacy-preserving and lightweight truth discovery protocols to tackle the above problems. Specifically, we carefully design an anonymization protocol named AnonymTD to delink workers from their data, where workers’ data are computed and transmitted without complicated encryption. To further reduce each worker's overheads in the scenarios where workers are willing to share their weights, we resort to the perturbation technology to propose a more lightweight truth discovery protocol named PerturbTD. Based on workers’ perturbed data, two cloud servers in PerturbTD complete most of the workload of truth discovery together, which avoids the frequent involvement of workers. The theoretical analysis and the comparative experiments in this paper demonstrate that our two protocols can achieve our security goals with low computation and communication overheads. [ABSTRACT FROM AUTHOR]

Scholar name disambiguation remains a hard and unsolved problem, which brings various troubles for bibliography data analytics. Most existing methods handle name disambiguation separately that tackles one name at a time, and neglect the fact that disambiguation of one name affects the others. Further, it is typically common that only limited information is available for bibliography data, e.g., only basic paper and citation information is available in DBLP. In this study, we propose a collective approach to name disambiguation, which takes the connection of different ambiguous names into consideration. We reformulate bibliography data as a heterogeneous multipartite network, which initially treats each author reference as a unique author entity, and disambiguation results of one name propagate to the others of the network. To further deal with the sparsity problem caused by limited available information, we also introduce word-word and venue-venue similarities, and we finally measure author similarities by assembling similarities from four perspectives. Using real-life data, we experimentally demonstrate that our approach is both effective and efficient. [ABSTRACT FROM AUTHOR]

The online retail market shows a sharp increase in traffic during holiday sales. The ability to distinguish customers who will likely purchase is critical for provisioning traffic and for providing cost-effective promotions. This paper uniquely studies the browsing and purchasing behaviors of online shoppers during a yearly sale event in China, the world’s largest online marketplace. Based on 31 million action logs gathered from wide residential areas, we characterize the steps leading to purchases and determine their precursors. We investigate the effect of time (e.g., date, time of date), environment (e.g., platform, viewed category), and action (e.g., session time, clicks, sequence) on purchases. Action cues from shopping behaviors can be used for early detection. While most shoppers start with strong intentions to purchase, yet the moment of ordering comes rather impulsively within 30 seconds to several minutes of browsing. The predictive accuracy reaches as a high AUC of 0.924. The findings in this paper provide an understanding of traffic during mega sale events that can help online shops plan and provide a better user experience for upcoming shopping festivals. [ABSTRACT FROM AUTHOR]

Quantitative analysis is a solid, well established mathematical technique that can be used to analyze the result of survey(s) in a specific field. Survey analysis is usually based on the study of the effect of independent variables on a dependent variable. Although quantitative analysis can use an R-Squared value as a method to measure the strength of the relationship between the independent and dependent variables, it does not capture the effect of participants’ ambiguity when answering questionnaires. The source of such ambiguity stems from the process of completing the survey, whereby the respondent may have answered most of the independent questions with ease, but has difficulty in responding to the overall dependent question (or vice versa). The objective of this paper is to demonstrate the use of fuzzy logic as a mechanism to measure the uncertainty faced by participants when filling a questionnaire. Based on the participants’ responses to the independent variables, the proposed technique uses fuzzy logic inference to measure the subjectivity (qualitative aspect) of the participants’ response to the dependent variable. Beyond quantitative analysis, augmentation with such a fuzzy module can provide clearer picture to analysts when analyzing the survey results. In this paper, Cloud acceptance survey will be used as a vehicle to provide step-by-step explanation of the proposed augmentation technique to unleash the hidden knowledge in similar cases to cloud computing long survey questionnaire where participants may change their mind at the end of the survey causing uncertainty represented in discrepancy of the collected data. The proposed technique would only be valid for long surveys like the presented Cloud computing acceptability where uncertainty in the data is inevitable. [ABSTRACT FROM AUTHOR]

Event logs that are recorded by information systems provide a valuable starting point for the analysis of processes in various domains, reaching from healthcare, through logistics, to e-commerce. Specifically, behavioral patterns discovered from an event log enable operational insights, even in scenarios where process execution is rather unstructured and shows a large degree of variability. While such behavioral patterns capture frequently recurring episodes of a process’ behavior, they are not limited to sequential behavior but include notions of concurrency and exclusive choices. Existing algorithms to discover behavioral patterns are context-agnostic, though. They neglect the context in which patterns are observed, which severely limits the granularity at which behavioral regularities are identified. In this paper, we therefore present an approach to discover contextual behavioral patterns. Contextual patterns may be frequent solely in a certain partition of the event log, which enables fine-granular insights into the aspects that influence the conduct of a process. Moreover, we show how to analyze the discovered contextual behavioral patterns in terms of causal relations between context information and the patterns, as well as correlations between the patterns themselves. A complete analysis methodology leveraging all the tools presented in the paper and supplemented by interpretations guidelines is also provided. Finally, experiments with real-world event logs demonstrate the effectiveness of our techniques in obtaining fine-granular process insights. [ABSTRACT FROM AUTHOR]

While recent developments of neural network (NN) models have led to a series of record-breaking achievements in many applications, the lack of sufficiently good datasets remains a problem for some applications. For such a problem, we can however exploit a large number of unstructured text corpora as an external knowledge to complement the training data, and most prevailing neural network solutions employ word embedding methods for such purposes. In this paper, we propose LDA-Reg, a novel knowledge driven regularization framework based on Latent Dirichlet Allocation (LDA) as an alternative to the word embedding methods to adaptively utilize abundant external knowledge and to interpret the NN model. For the joint learning of the parameters, we propose EM-SGD, an effective update method which incorporates Expectation Maximization (EM) and Stochastic Gradient Descent (SGD) to update parameters iteratively. Moreover, we also devise a lazy update and sparse update method for the high-dimensional inputs and sparse inputs respectively. We validate the effectiveness of our regularization framework through an extensive experimental study over real world and standard benchmark datasets. The results show that our proposed framework not only achieves significant improvement over state-of-the-art word embedding methods but also learns interpretable and significant topics for various tasks. [ABSTRACT FROM AUTHOR]

Machine learning research, particularly in genomics, is often based on wide shaped datasets, i.e. datasets having a large number of features, but a small number of samples. Such configurations raise the possibility of chance influence (the increase of measured accuracy due to chance correlations) on the learning process and the evaluation results. Prior research underlined the problem of generalization of models obtained based on such data. In this paper, we investigate the influence of chance on prediction and show its significant effects on wide shaped datasets. First, we empirically demonstrate how significant the influence of chance in such datasets is by showing that prediction models trained on thousands of randomly generated datasets can achieve high accuracy. This is the case even when using cross-validation. We then provide a formal analysis of chance influence and design formal chance influence estimators based on the dataset parameters, namely its sample size, the number of features, the number of classes and the class distribution. Finally, we provide an in-depth discussion of the formal analysis including applications of the findings and recommendations on chance influence mitigation. [ABSTRACT FROM AUTHOR]

Competition between Points of Interest (POIs) refers to the situation in which two POIs directly or indirectly provide similar services to secure businesses. A large portion of prior studies on competition analysis focuses on mining textual data, e.g., news articles and social comments. However, the increasing availability of human mobility and mobile query data enables a new paradigm for analyzing the competitive relationships among POIs, which remains largely unexplored. To this end, in this paper, we attempt to mine large-scale online map search query data for better understanding POI competitive relationships. Based on a co-query POI graph built from the map search query data, we develop a novel neural graphlet-based prediction framework to predict the competitive relationships among POIs. A unique perspective of our model is to infer latent POI competitive relationships by integrating multiple distinct factors, e.g., graphlet structure, geographical distance, and regional features, reflected in map search query data and POI data. Finally, we conduct extensive experiments on real-world datasets to demonstrate the effectiveness of the proposed framework, and show that our framework outperforms all baselines with a significant margin in all evaluation metrics. [ABSTRACT FROM AUTHOR]

In plenty of real-life tasks, strongly supervised information is hard to obtain, and thus weakly supervised learning has drawn considerable attention recently. This paper investigates the problem of learning from incomplete and inaccurate supervision, where only a limited subset of training data is labeled but potentially with noise. This setting is challenging and of great importance but rarely studied in the literature. We notice that in many applications, the limited labeled data are with certain structures, which paves us a way to design effective methods. Specifically, we observe that labeled data are usually with one-sided noise such as the bug detection task, where the identified buggy codes are indeed with defects, while codes checked many times or newly fixed may still have other flaws. Furthermore, when there occurs two-sided noise in the labeled data, we exploit the class-prior information of unlabeled data, which is typically available in practical tasks. We propose novel approaches for the incomplete and inaccurate supervision learning tasks and effectively alleviate the negative influence of label noise with the help of a vast number of unlabeled data. Both theoretical analysis and extensive experiments justify and validate the effectiveness of the proposed approaches. [ABSTRACT FROM AUTHOR]

It is widely acknowledged that the success of deep learning is built upon large-scale training data and tremendous computing power. However, the data and computing power are not always available for many real-world applications. In this paper, we address the machine learning problem where it lacks training data and limits computing power. Specifically, we investigate domain adaptation which is able to transfer knowledge from one labeled source domain to an unlabeled target domain, so that we do not need much training data from the target domain. At the same time, we consider the situation that the running environment is confined, e.g., in edge computing the end device has very limited running resources. Technically, we present the Faster Domain Adaptation (FDA) protocol and further report two paradigms of FDA: early stopping and amid skipping. The former accelerates domain adaptation by multiple early exit points. The latter speeds up the adaptation by wisely skip several amid neural network blocks. Extensive experiments on standard benchmarks verify that our method is able to achieve the comparable and even better accuracy but employ much less computing resources. To the best of our knowledge, there are very few works which investigated accelerating knowledge adaptation in the community. This work is expected to inspire the topic for more discussion. [ABSTRACT FROM AUTHOR]

Knowledge graph embedding is an effective way to represent knowledge graph, which greatly enhance the performances on knowledge graph completion tasks, e.g., entity or relation prediction. For knowledge graph embedding models, designing a powerful loss framework is crucial to the discrimination between correct and incorrect triplets. Margin-based ranking loss is a commonly used negative sampling framework to make a suitable margin between the scores of positive and negative triples. However, this loss can not ensure ideal low scores for the positive triplets and high scores for the negative triplets, which is not beneficial for knowledge completion tasks. In this paper, we present a double limit scoring loss to separately set upper bound for correct triplets and lower bound for incorrect triplets, which provides more effective and flexible optimization for knowledge graph embedding. Upon the presented loss framework, we present several knowledge graph embedding models including TransE-SS, TransH-SS, TransD-SS, ProjE-SS and ComplEx-SS. The experimental results on link prediction and triplet classification show that our proposed models have the significant improvement compared to state-of-the-art baselines. [ABSTRACT FROM AUTHOR]

Currently, electroencephalogram (EEG) is mostly analyzed in a supervised way, which requires EEG labels (e.g., EEG classification). With the ever-increasing amount of unlabeled/mislabeled EEG in neuropsychiatric disorder diagnosis, BCI, and rehabilitation, manually labeling of EEG data is a labor intensive and time-consuming process, and few labs have developed algorithms to analyze EEG in an unsupervised manner (i.e., EEG clustering). In this paper, we propose a cooperative game inspired approach to cluster multi-trial EEG data. The idea is to map multi-trial EEG clustering to the coalition formation in a cooperative game, and then identify cluster center (the EEG trial with highest Shapley value) and assign EEG trials into proper clusters based on their cross correlation-transformed Shapley values. We demonstrate the mapped EEG cooperative game is convex, and it leads to an algorithm for multi-trial EEG clustering named CoGEEGc. The CoGEEGc yields high-quality multi-trial EEG clustering with respect to intra-cluster compactness and inter-cluster scatter. We show that CoGEEGc outperforms 15 state-of-the-art EEG or time series clustering approaches through detailed experimentation on real-world multi-trial EEG datasets. Comparison against 15 methods with four theoretical properties of clustering further illustrates the superiority of CoGEEGc, as it satisfies two properties while other approaches only satisfy one. [ABSTRACT FROM AUTHOR]

With the proliferation of online social networks, the identification or classification of real-life relationship between users has been very useful for many applications such as financial fraud detection. In real life, usually people with different relationships would present gifts with special meanings to each other on different dates. In many Asian cultures, especially in Chinese culture, the red packet is a traditional form of monetary gift. With the rapid development of the Internet, people gradually began to give electronic red packets instead of paper ones as the means of money gifting on social network platforms. As motivated, in this paper we advocate a novel approach that exploits users’ red packet interactions for users relationship identification on WeChat, one of the largest social platforms in China. Specifically, we analyze the WeChat red packets network, identify the real-life relationship types between users through mining the semantic information of the amount and sending time of each red packet. In order to better capture the red packet gifting behaviors between users for relationship identification, on one hand, we construct an Amount-Date Graph and apply the graph embedding method to learn embeddings of the amount and sending date of each red packet. On the other hand, we propose a novel sequential model, Cross & Attention Sequence Model (CASM), which explicitly learns the interactions between the latent semantic information of each red packet’s amount and sending date in the red packets sequence between two users. To validate our approach, we conduct comprehensive experiments on a real-world WeChat Users Red Packets dataset that involves 8 kinds of real-life relationships. The experiments show that our proposed approach performs significantly better than baselines and achieves 81.70 percent prediction accuracy. [ABSTRACT FROM AUTHOR]

To solve the information explosion problem and enhance user experience in various online applications, recommender systems have been developed to model users’ preferences. Although numerous efforts have been made toward more personalized recommendations, recommender systems still suffer from several challenges, such as data sparsity and cold-start problems. In recent years, generating recommendations with the knowledge graph as side information has attracted considerable interest. Such an approach can not only alleviate the above mentioned issues for a more accurate recommendation, but also provide explanations for recommended items. In this paper, we conduct a systematical survey of knowledge graph-based recommender systems. We collect recently published papers in this field, and group them into three categories, i.e., embedding-based methods, connection-based methods, and propagation-based methods. Also, we further subdivide each category according to the characteristics of these approaches. Moreover, we investigate the proposed algorithms by focusing on how the papers utilize the knowledge graph for accurate and explainable recommendation. Finally, we propose several potential research directions in this field. [ABSTRACT FROM AUTHOR]

Periodicity is a frequently happening phenomenon for social interactions in temporal networks. Mining periodic communities are essential to understanding periodic group behaviors in temporal networks. Unfortunately, most previous studies for community mining in temporal networks ignore the periodic patterns of communities. In this paper, we study the problem of seeking periodic communities in a temporal network, where each edge is associated with a set of timestamps. We propose novel models, including $\sigma$ σ -periodic $k$ k -core and $\sigma$ σ -periodic $k$ k -clique, that represent periodic communities in temporal networks. Specifically, a $\sigma$ σ -periodic $k$ k -core (or $\sigma$ σ -periodic $k$ k -clique) is a $k$ k -core (or clique with size larger than $k$ k ) that appears at least $\sigma$ σ times periodically in the temporal graph. The problem of searching periodic core is efficient but the resulting communities may be not enough cohesive; the problem of enumerating all periodic cliques is not efficient (NP-hard) but the resulting communities are very cohesive. To compute all of them efficiently, we first develop two effective graph reduction techniques to significantly prune the temporal graph. Then, we transform the temporal graph into a static graph and prove that mining the periodic communities in the temporal graph equals mining communities in the transformed graph. Subsequently, we propose a decomposition algorithm to search maximal $\sigma$ σ -periodic $k$ k -core, a Bron-Kerbosch style algorithm to enumerate all maximal $\sigma$ σ -periodic $k$ k -cliques, and a branch-and-bound style algorithm to find the maximum $\sigma$ σ -periodic clique. The results of extensive experiments on five real-life datasets demonstrate the efficiency, scalability, and effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

Since inaccuracies commonly exist in many applications, data uncertainty has become an important problem in database systems. To deal with data uncertainty, probabilistic databases can be used to store uncertain data, and querying facilities are provided to yield answers with confidence. However, the results from a query or mining process may not be reliable when the uncertainty propagates in the systems. In this paper, we leverage the power of crowdsourcing by designing a set of Human Intelligence Tasks, or HITs in short, to ask a crowd to improve the quality of uncertain data. In particular, we consider crowds consists of workers with diverse accuracy rates when answering the HITs. We design solutions to maximize the data quality with minimal number of HITs. There are two obstacles for this non-trivial optimization, which lead to very high computational cost for selecting the optimal set of HITs. First, members of a crowd may return incorrect answers with different probabilities. Second, the HITs decomposed from uncertain data are often correlated. We have addressed these challenges in this paper by designing an effective approximation algorithm and an efficient heuristic solution, especially for crowds with diverse individual accuracy rates. To further improve the efficiency, we derive tight lower and upper bounds for effective filtering and estimation. Extensive experiments on both a simulated crowd and a real crowdsourcing platform are conducted to evaluate our solutions. [ABSTRACT FROM AUTHOR]

Network data in real-world tends to be error-prone due to incomplete sampling, imperfect measurements, etc.; this in turn results in inaccurate results when performing network analysis or modeling, such as node classification and link prediction, on these flawed networks. In this paper, we aim to reconstruct a reliable network from a flawed, undirected, unweighted network, a process referred to network enhancement. More specifically, network enhancement aims to detect the noisy links that are observed in the network but should not exist in the real world, as well as to predict the missing links that do indeed exist in the real world yet remain unobserved. While some attempts have been made to detect either noisy links or missing links, few of these works have considered unifying these two tasks, even though they are inter-dependent and capable of mutually boosting each others’ performance. In this paper, we therefore propose E-Net, an end-to-end graph neural network model, to leverage the mutual influence of these two tasks in order to achieve both goals more effectively. On one hand, detecting noisy links can benefit the performance of missing link prediction, while on the other hand, predicting missing links can provide indirect supervision for detecting noisy link detection when the labels of these noisy links are unavailable. Moreover, by proposing a subgraph extraction mechanism based on random walk with restart, the model can be scaled up to large networks and is able to preserve the local and global structural characteristics. The experimental results on several types of large networks demonstrate that the proposed model obtains an improvement of 10.7 percent on average in terms of F1 for predicting missing links, along with an average of 3.7 percent improvement in terms of precision for detecting noisy links compared with the state-of-the-art baselines. [ABSTRACT FROM AUTHOR]

Modern Medical Information Systems very often comprise Medical Devices and governed by regulations which require stringent Risk Management activities to be implemented to minimize the occurrence of safety risks. Currently, the reference standard adopted by manufacturers for Risk Management is ISO 14971, which, however, was devised for traditional (mostly hardware) Medical Devices and does not either take into account the peculiarities of modern Medical Information Systems, or define a formal methodology to conduct Risk Assessment. Moreover, the approaches currently implemented by manufacturers typically aims at obtaining qualitative Risk Assessment results. Within the so-delineated application scenario, this paper proposes a methodology for the Dynamic Probabilistic Risk Assessment of Medical Information Systems, by specifically looking at medical devices that are intended as one of the most relevant components in such systems. The methodology complies with ISO 14971 and improves current practices because it allows the analyst to conduct a quantitative analysis, also taking into account the temporal dimension. It relies on a Probabilistic Risk Model, defined as a set of Markov Models, which is model-checked to obtain quantitative information about the risks. The proposed methodology is also adopted to improve definitively the Medical Device post-market surveillance, which is currently implemented as a ”wait for an incident” activity. In other words, currently a manufacturer sets up a service that has to ”react” to an incident by starting an investigation activity. Instead, the methodology proposes the adoption of risk models defined during the development phase also to re-assess periodically the risks related to the product during the post-market surveillance. This may prevent some incidents because risks are assessed using data collected in the field (no longer guesstimated as during the development phase) and taking into account the temporal effects on probability distributions (such as the deterioration of hardware/software components over the time). [ABSTRACT FROM AUTHOR]

In this paper, we study an automatic hypothesis generation (HG) problem, which refers to the discovery of meaningful implicit connections between scientific terms, including but not limited to diseases, chemicals, drugs, and genes extracted from databases of biomedical publications. Most prior studies of this problem focused on the use of static information of terms and largely ignored the temporal dynamics of scientific term relations. Even when the dynamics were considered in a few recent studies, they learned the representations for the scientific terms, rather than focusing on the term-pair relations. Since the HG problem is to predict term-pair connections, it is not enough to know with whom the terms are connected, it is more important to know how the connections have been formed (in a dynamic process). We formulate this HG problem as a future connectivity prediction in a dynamic attributed graph. The key is to capture the temporal evolution of node-pair (term-pair) relations. We propose an inductive edge (node-pair) embedding method named T-PAIR, utilizing both the graphical structure and node attribute to encode the temporal node-pair relationship. We demonstrate the efficiency of the proposed model on three real-world datasets, which are three graphs constructed from Pubmed papers published until 2019 in Neurology, Immunotherapy, and Virology, respectively. Evaluations were conducted on predicting future term-pair relations between millions of seen terms (in the transductive setting), as well as on the relations involving unseen terms (in the inductive setting). Experiment results and case study analyses show the effectiveness of the proposed model. [ABSTRACT FROM AUTHOR]

Unsupervised spectral feature selection (USFS) methods could output interpretable and discriminative results by embedding a Laplacian regularizer in the framework of sparse feature selection to keep the local similarity of the training samples. To do this, USFS methods usually construct the Laplacian matrix using either a general-graph or a hyper-graph on the original data. Usually, a general-graph could measure the relationship between two samples while a hyper-graph could measure the relationship among no less than two samples. Obviously, the general-graph is a special case of the hyper-graph and the hyper-graph may capture more complex structure of samples than the general graph. However, in previous USFS methods, the construction of the Laplacian matrix is separated from the process of feature selection. Moreover, the original data usually contain noise. Each of them makes difficult to output reliable feature selection models. In this paper, we propose a novel feature selection method by dynamically constructing a hyper-graph based Laplacian matrix in the framework of sparse feature selection. Experimental results on real datasets showed that our proposed method outperformed the state-of-the-art methods in terms of both clustering and segmentation tasks. [ABSTRACT FROM AUTHOR]

The Cox proportional hazards model is a popular semi-parametric model for survival analysis. In this paper, we aim at developing a federated algorithm for the Cox proportional hazards model over vertically partitioned data (i.e., data from the same patient are stored at different institutions). We propose a novel algorithm, namely VERTICOX, to obtain the global model parameters in a distributed fashion based on the Alternating Direction Method of Multipliers (ADMM) framework. The proposed model computes intermediary statistics and exchanges them to calculate the global model without collecting individual patient-level data. We demonstrate that our algorithm achieves equivalent accuracy for the estimation of model parameters and statistics to that of its centralized realization. The proposed algorithm converges linearly under the ADMM framework. Its computational complexity and communication costs are polynomially and linearly associated with the number of subjects, respectively. Experimental results show that VERTICOX can achieve accurate model parameter estimation to support federated survival analysis over vertically distributed data by saving bandwidth and avoiding exchange of information about individual patients. The source code for VERTICOX is available at: https://github.com/daiwenrui/VERTICOX. [ABSTRACT FROM AUTHOR]

The task of point of interest (POI) recommendation aims to recommend unvisited places to users based on their check-in history. A major challenge in POI recommendation is data sparsity, because a user typically visits only a very small number of POIs among all available POIs. In this paper, we propose AUC-MF to address the POI recommendation problem by maximizing Area Under the ROC curve (AUC). AUC has been widely used for measuring classification performance with imbalanced data distributions. To optimize AUC, we transform the recommendation task to a classification problem, where the visited locations are positive examples and the unvisited are negative ones. We define a new lambda for AUC to utilize the LambdaMF model, which combines the lambda-based method and matrix factorization model in collaborative filtering. Many studies have shown that geographic information plays an important role in POI recommendation. In this study, we focus on two levels geographic information: local similarity and global similarity. We further show that AUC-MF can be easily extended to incorporate geographical contextual information for POI recommendation. Specifically, we propose two novel methods to incorporate geographical information in AUC-MF. Different from most existing models where the contextual information are incorporated into the objective function, the incorporation of contextual information in AUC-MF is a refinement of the model and a sampling strategy. The sampling strategy could speedup convergence and the refining of recommendations is independent of training of the model. This mechanism also enables AUC-MF to be able produce recommendations refined towards different contextual information, with minimum computational cost. Experiments on two datasets show that the proposed AUC-MF outperforms state-of-the-art methods significantly in terms of recommendation accuracy. [ABSTRACT FROM AUTHOR]

Domain adaptation aims at extracting knowledge from auxiliary source domains to assist the learning task in a target domain. In classification problems, since the distributions of the source and target domains are different, directly using source data to build a classifier for the target domain may hamper the classification performance on the target data. Fortunately, in many tasks, there can be some features that are transferable, i.e., the source and target domains share similar properties. On the other hand, it is common that the source data contain noisy features which may degrade the learning performance in the target domain. This issue, however, is barely studied in existing works. In this paper, we propose to find a feature subset that is transferable across the source and target domains. As a result, the domain discrepancy measured on the selected features can be reduced. Moreover, we seek to find the most discriminative features for classification. To achieve the above goals, we formulate a new sparse learning model that is able to jointly reduce the domain discrepancy and select informative features for classification. We develop two optimization algorithms to address the derived learning problem. Extensive experiments on real-world data sets demonstrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

In this work we study the distance distribution computation problem. It has been widely used in many real-world applications, e.g., human genome clustering, cosmological model analysis, and parameter tuning. The straightforward solution for the exact distance distribution computation problem is unacceptably slow due to (i) massive data size, and (ii) expensive distance computation. In this paper, we propose a novel method to compute approximate distance distributions with error bound guarantees. Furthermore, our method is generic to different distance measures. We conduct extensive experimental studies on three widely used distance measures with real-world datasets. The experimental results demonstrate that our proposed method outperforms the sampling-based solution (without error guarantees) by up to three orders of magnitude. [ABSTRACT FROM AUTHOR]

Spatial crowdsourcing (SC) allows requesters to crowdsource tasks to workers based on location proximity. To preserve privacy, the location should not be disclosed to untrustworthy entities (even the SC platform). Previous solutions to preserve workers’ location privacy require an online trusty third party (TTP), which is not practical in reality. In this paper, we design a framework that allows the SC platform to assign tasks to nearest workers in an online manner without knowing their actual locations. We propose an encryption algorithm to encrypt the locations of tasks and workers, and design an indexing method that assigns tasks to workers without losing too much privacy. We prove that there exists a trade-off between efficiency and security theoretically, which can be controlled based on user preference. We verify our method on real-world datasets and experimental results show that our method is efficient, effective and practical. [ABSTRACT FROM AUTHOR]

So-called spatial web queries retrieve web content representing points of interest, such that the points of interest have descriptions that are relevant to query keywords and are located close to a query location. Two broad categories of such queries exist. The first encompasses queries that retrieve single spatial web objects that each satisfy the query arguments. Most proposals belong to this category. The second category, to which this paper's proposal belongs, encompasses queries that support exploratory user behavior and retrieve sets of objects that represent regions of space that may be of interest to the user. Specifically, the paper proposes a new type of query, the top- $k$ k spatial textual cluster retrieval ($k$ k -STC) query that returns the top- $k$ k clusters that (i) are located close to a query location, (ii) contain objects that are relevant with regard to given query keywords, and (iii) have an object density that exceeds a given threshold. To compute this query, we propose a DBSCAN-based approach and an OPTICS-based approach that rely on on-line density-based clustering and that exploit early stop conditions. Empirical studies on real data sets offer evidence that the paper's proposals can find good quality clusters and are capable of excellent performance. [ABSTRACT FROM AUTHOR]

Many real-world datasets are given in the stream of entity-identifier pairs, and measuring data distribution on these datasets is fundamental for applications such as privacy protection. In this paper, we study the problem of computing the cumulative distribution for different cardinalities (i.e., the number of distinct entities owning the same identifier). However, previous sketch-based methods cost large memory space especially when there are a large number of identifiers, and sampling-based methods require much time for cardinality estimation. A recent work KHyperLogLog combines both sketch and sampling methods but it is wasteful to separately build a HyperLogLog sketch of large size for identifiers with small cardinalities. To address these challenges, we propose a memory-efficient method EV-HLL, which designs a shared structure to store all sampled identifiers and their entities and utilizes additional sketches to track value updates during the sampling procedure. Meanwhile, EV-HLL provides real-time unbiased estimations according to value changes whenever a new entity-identifier pair arrives. We evaluate the performance of EV-HLL and other state-of-the-arts on real-world available datasets. Experimental results demonstrate that comparing to other methods, EV-HLL effectively reduces their memory usage with the same estimation accuracy and has higher accuracy with the same memory usage. [ABSTRACT FROM AUTHOR]

Triangle count is a critical parameter in mining relationships among people in social networks. However, directly publishing the findings obtained from triangle counts may bring potential privacy concern, which raises great challenges and opportunities for privacy-preserving triangle counting. In this paper, we choose to use differential privacy to protect triangle counting for large scale graphs. To reduce the large sensitivity caused in large graphs, we propose a novel graph projection method that can be used to obtain an upper bound for sensitivity in different distributions. In particular, we publish the triangle counts satisfying the node-differential privacy with two kinds of histograms: the triangle count distribution and the cumulative distribution. Moreover, we extend the research on privacy preserving triangle counting to one of its applications, the local clustering coefficient. Experimental results show that the cumulative distribution can fit the real statistical information better, and our proposed mechanism has achieved better accuracy for triangle counts while maintaining the requirement of differential privacy. [ABSTRACT FROM AUTHOR]

Short text clustering has far-reaching effects on semantic analysis, showing its importance for multiple applications such as corpus summarization and information retrieval. However, it inevitably encounters the severe sparsity of short text representations, making the previous clustering approaches still far from satisfactory. In this paper, we present a novel attentive representation learning model for shot text clustering, wherein cluster-level attention is proposed to capture the correlations between text representations and cluster representations. Relying on this, the representation learning and clustering for short texts are seamlessly integrated into a unified model. To further ensure robust model training for short texts, we apply adversarial training to the unsupervised clustering setting, by injecting perturbations into the cluster representations. The model parameters and perturbations are optimized alternately through a minimax game. Extensive experiments on four real-world short text datasets demonstrate the superiority of the proposed model over several strong competitors, verifying that robust adversarial training yields substantial performance gains. [ABSTRACT FROM AUTHOR]

Human behaviors in recommendation systems are driven by many high-level, complex, and evolving intentions behind their decision making processes. In order to achieve better performance, it is important for recommendation systems to be aware of user intentions besides considering the historical interaction behaviors. However, user intentions are seldom fully or easily observed in practice, so that the existing works are incapable of fully tracking and modeling user intentions, not to mention using them effectively into recommendation. In this paper, we present the Intention-Aware Sequential Recommendation (ISRec) method, for capturing the underlying intentions of each user that may lead to her next consumption behavior and improving recommendation performance. Specifically, we first extract the intentions of the target user from sequential contexts, then take complex intent transition into account through the message-passing mechanism on an intention graph, and finally obtain the future intentions of this target user from inference on the intention graph. The sequential recommendation for a user will be made based on the predicted user intentions, offering more transparent and explainable intermediate results for each recommendation. Extensive experiments on various real-world datasets demonstrate the superiority of our method against several state-of-the-art baselines in sequential recommendation in terms of different metrics. [ABSTRACT FROM AUTHOR]

The reachability problem on directed graphs, asking whether two vertices are connected via a directed path, is an elementary problem that has been well-studied. In this paper, we study a variation of the elementary reachability problem, called the sink-reachability problem, which can be found in many applications such as static program analysis, social network analysis, large scale web graph analysis, XML document link path analysis, and the study of gene regulation relationships. To scale sink-reachablity analysis to large graphs, we develop a highly scalable sink-reachability preserving graph reduction strategy for input sink graphs, by using a composition framework. That is, individual sink-reachability preserving condensation operators, each running in linear time, are pipelined together to produce graph reduction algorithms that result in close to maximum reduction, while keeping the computation efficient. Experiments on large real-world sink graphs demonstrate the efficiency and effectiveness of our compositional approach to sink-reachability preserving graph reduction with a reduction rate of up to 99.74 percent for vertices and a rate of up to 99.46 percent for edges. [ABSTRACT FROM AUTHOR]

Capturing the dynamics in user preference is crucial to better predict user future behaviors because user preferences often drift over time. Many existing recommendation algorithms – including both shallow and deep ones – often model such dynamics independently, i.e., user static and dynamic preferences are not modeled under the same latent space, which makes it difficult to fuse them for recommendation. This paper considers the problem of embedding a user's sequential behavior into the latent space of user preferences, namely translating sequence to preference. To this end, we formulate the sequential recommendation task as a dictionary learning problem, which learns: 1) a shared dictionary matrix, each row of which represents a partial signal of user dynamic preferences shared across users; and 2) a posterior distribution estimator using a deep autoregressive model integrated with Gated Recurrent Unit (GRU), which can select related rows of the dictionary to represent a user's dynamic preferences conditioned on his/her past behaviors. Qualitative studies on the Netflix dataset demonstrate that the proposed method can capture the user preference drifts over time and quantitative studies on multiple real-world datasets demonstrate that the proposed method can achieve higher accuracy compared with state-of-the-art factorization and neural sequential recommendation methods. [ABSTRACT FROM AUTHOR]

Given a dataset $\mathcal S$ S composed of $g$ g subsets with each data item belonging to one of them, multiset membership lookup takes an item $e$ e as input and outputs a binary answer whether $e\in {\mathcal S}$ e ∈ S and, in case of yes, the ID of the subset to which $e$ e belongs. Overlaid upon while more sophisticated than the canonical membership lookup, multiset membership lookup emerges as a pivotal functionality in many computing and networking paradigms. The quest to achieve high-speed, high-accuracy lookup with limited memory cost makes lookup algorithm design a challenging task, particularly when the data items arrive as a stream. In this paper, we devise compact data structures and lookup algorithms that are amendable for hardware implementation, while guaranteeing high lookup accuracy and supporting interactive query processing. We first propose multi-hash color table, a variant of Bloom filter, to encode subset IDs compactly and map the ID of an item to its subset ID. We further construct a more balanced data structure called balanced multi-hash color table to improve the compactness by integrating the state-of-the-art load balancing technique. We complete our work by addressing the case of batch arrivals and design a batched recording algorithm optimizing the memory efficiency. We give both theoretical and empirical analysis to characterize and evaluate the performance of the proposed algorithms in terms of lookup accuracy, memory and access efficiency. [ABSTRACT FROM AUTHOR]

In this paper, we study a new variant of trajectory similarity search from the context of continuous query processing. Given a moving object from $s$ s to $d$ d , following a reference route $T_r$ T r , we monitor the trajectory similarity between the reference route and the current partial route at each timestamp for online detour detection. Since existing trajectory distance measures fail to adequately capture the deviation between a partial route and a complete route, we propose a partial trajectory similarity measure to bridge the gap. In particular, we enumerate all the possible routes extended from the partial route to reach the destination $d$ d and calculate their minimum distance to $T_r$ T r . We consider deviation calculation in both euclidean space and road networks. In euclidean space, we can directly infer the optimal future path with the minimum trajectory distance. In road networks, we propose an efficient expansion algorithm with a suite of pruning rules. Furthermore, we propose efficient incremental processing strategies to facilitate continuous query processing for moving objects. Our experiments are conducted on multiple real datasets and the experimental results verify the efficiency of our query processing algorithms. [ABSTRACT FROM AUTHOR]

Community detection is one of the most fundamental problems in social network analysis, while most existing research focuses on unsigned graphs. In real applications, social networks involve not only positive relationships but also negative ones. It is important to exploit the signed information to identify more stable communities. In this paper, we propose a novel model, named stable $k$ k -core, to measure the stability of a community in signed graphs. The stable $k$ k -core model not only emphasizes user engagement, but also eliminates unstable structures. We show that the problem of finding the maximum stable $k$ k -core is NP-hard. To scale for large graphs, novel pruning strategies and searching methods are proposed. We conduct extensive experiments on 6 real-world signed networks to verify the efficiency and effectiveness of proposed model and techniques. [ABSTRACT FROM AUTHOR]

Social recommendation has emerged to leverage social connections among users for predicting users’ unknown preferences, which could alleviate the data sparsity issue in collaborative filtering based recommendation. Early approaches relied on utilizing each user’s first-order social neighbors’ interests for better user modeling, and failed to model the social influence diffusion process from the global social network structure. Recently, we propose a preliminary work of a neural influence Diffusion Network (i.e., DiffNet) for social recommendation L. Wu, P. Sun, Y. Fu, R. Hong, X. Wang, and M. Wang, “A neural influence diffusion model for social recommendation,” in Proc. Int. ACM SIGIR Conf. Res. Develop. Inf. Retrieval, 2019, pp. 235–244.. DiffNet models the recursive social diffusion process for each user, such that the influence diffusion hidden in the higher-order social network is captured in the user embedding process. Despite the superior performance of DiffNet, we argue that, as users play a central role in both user-user social network and user-item interest network, only modeling the influence diffusion process in the social network would neglect the latent collaborative interests of users hidden in the user-item interest network. To this end, in this paper, we propose DiffNet++, an improved algorithm of DiffNet that models the neural influence diffusion and interest diffusion in a unified framework. By reformulating the social recommendation as a heterogeneous graph with social network and interest network as input, DiffNet++ advances DiffNet by injecting both the higher-order user latent interest reflected in the user-item graph and higher-order user influence reflected in the user-user graph for user embedding learning. This is achieved by iteratively aggregating each user’s embedding from three aspects: the user’s previous embedding, the influence aggregation of social neighbors from the social network, and the interest aggregation of item neighbors from the user-item interest network. Furthermore, we design a multi-level attention network that learns how to attentively aggregate user embeddings from these three aspects. Finally, extensive experimental results on four real-world datasets clearly show the effectiveness of our proposed model. We release the source code at https://github.com/PeiJieSun/diffnet. [ABSTRACT FROM AUTHOR]