Search

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]

Ride-sourcing services are now reshaping the way people travel by effectively connecting drivers and passengers through mobile internets. Online matching between idle drivers and waiting passengers is one of the most key components in a ride-sourcing system. The average pickup distance or time is an important measurement of system efficiency since it affects both passengers’ waiting time and drivers’ utilization rate. It is naturally expected that a more effective bipartite matching (with smaller average pickup time) can be implemented if the platform accumulates more idle drivers and waiting passengers in the matching pool. A specific passenger request can also benefit from a delayed matching since he/she may be matched with closer idle drivers after waiting for a few seconds. Motivated by the potential benefits of delayed matching, this paper establishes a two-stage framework which incorporates a combinatorial optimization and multi-agent deep reinforcement learning methods. The multi-agent reinforcement learning methods are used to dynamically determine the delayed time for each passenger request (or the time at which each request enters the matching pool), while the combinatorial optimization conducts an optimal bipartite matching between idle drivers and waiting passengers in the matching pool. Four tailored reinforcement learning methods, delayed multi-agent deep Q learning (Delayed-M-DQN), delayed multi-agent actor-critic (Delayed-M-A2C), delayed multi-agent Proximal Policy Optimization (Delayed-M-PPO), and delayed multi-agent actor-critic with experience replay (Delayed-M-ACER), are developed. Through extensive empirical experiments with a well-designed simulator, we show that the proposed framework is able to remarkably improve system performances, by well balancing the trade-off among pick-up time, matching time, successful matching rate. [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]

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]

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]

This paper investigates the stochastic optimization problem focusing on developing scalable parallel algorithms for deep learning tasks. Our solution involves a reformation of the objective function for stochastic optimization in neural network models, along with a novel parallel computing strategy, coined the weighted aggregating stochastic gradient descent (WASGD). Following a theoretical analysis on the characteristics of the new objective function, WASGD introduces a decentralized weighted aggregating scheme based on the performance of local workers. Without any center variable, the new method automatically gauges the importance of local workers and accepts them by their contributions. Furthermore, we have developed an enhanced version of the method, WASGD+, by (1) implementing a designed sample order and (2) upgrading the weight evaluation function. To validate the new method, we benchmark our pipeline against several popular algorithms including the state-of-the-art deep neural network classifier training techniques (e.g., elastic averaging SGD). Comprehensive validation studies have been conducted on four classic datasets: CIFAR-100, CIFAR-10, Fashion-MNIST, and MNIST. Subsequent results have firmly validated the superiority of the WASGD scheme in accelerating the training of deep architecture. Better still, the enhanced version, WASGD+, is shown to be a significant improvement over its prototype. [ABSTRACT FROM AUTHOR]

Reorganizing bus frequencies to cater for the actual travel demands can significantly save the cost of the public transport system. Many, if not all, previous studies formulate this as a bus frequency optimization problem that tries to minimize passengers’ average waiting time. On the other hand, many investigations have confirmed that the user satisfaction drops faster as the waiting time increases. Consequently, this paper studies the bus frequency optimization problem considering the user satisfaction. Specifically, for the first time to our best knowledge, we study how to schedule the buses such that the total number of passengers who could receive their bus services within the waiting time threshold can be maximized. We propose two variants of the problem, FAST and FASTCO, to cater for different application needs and prove that both are NP-hard. To solve FAST effectively and efficiently, we first present an index-based $(1-1/e)$ (1 - 1 / e) -approximation algorithm. By exploiting the locality property of routes in a bus network, we further propose a partition-based greedy method that achieves a $(1-\rho)(1-1/e)$ (1 - ρ) (1 - 1 / e) approximation ratio. Then we propose a progressive partition-based greedy method to further boost the efficiency while achieving a $(1-\rho)(1-1/e-\varepsilon)$ (1 - ρ) (1 - 1 / e - ɛ) approximation ratio. For the FASTCO problem, two greedy-based heuristic methods are proposed. Experiments on a real city-wide bus dataset in Singapore have been conducted to verify the efficiency, effectiveness, and scalability of our methods in addressing FAST and FASTCO respectively. [ABSTRACT FROM AUTHOR]

This paper presents a rigorous but tractable study of sparsity. We postulate a definition of sparsity that is as broad as possible, so that it generates all the various measures that are useful in practice, but narrow enough that the fundamental properties of generalized sparsity still hold. As we work through the various ways of demonstrating the advantageous properties of sparsity, we illustrate its meaning from geometrical and operational perspectives. Thereafter, we construct specific measures of sparsity which are successfully qualified in complexity analysis and sparse optimization scenarios. Overall, our main objective is to construct measures of sparsity that will facilitate and enhance the design of the next innovative sensing technologies. [ABSTRACT FROM AUTHOR]

It has been an important task for recommender systems to suggest satisfying activities to a group of users in people’s daily social life. The major challenge in this task is how to aggregate personal preferences of group members to infer the decision of a group. Conventional group recommendation methods applied a predefined strategy for preference aggregation. However, these static strategies are too simple to model the real and complex process of group decision-making, especially for occasional groups which are formed ad-hoc. Moreover, group members should have non-uniform influences or weights in a group, and the weight of a user can be varied in different groups. Therefore, an ideal group recommender system should be able to accurately learn not only users’ personal preferences but also the preference aggregation strategy from data. In this paper, we propose a novel end-to-end group recommender system named CAGR (short for “Centrality-Aware Group Recommender”), which takes Bipartite Graph Embedding Model (BGEM), the self-attention mechanism and Graph Convolutional Networks (GCNs) as basic building blocks to learn group and user representations in a unified way. Specifically, we first extend BGEM to model group-item interactions, and then in order to overcome the limitation and sparsity of the interaction data generated by occasional groups, we propose a self-attentive mechanism to represent groups based on the group members. In addition, to overcome the sparsity issue of user-item interaction data, we leverage the user social networks to enhance user representation learning, obtaining centrality-aware user representations. To further alleviate the group data sparsity problem, we propose two model optimization approaches to seamlessly integrate the user representations learning process. We create three large-scale benchmark datasets and conduct extensive experiments on them. The experimental results show the superiority of our proposed CAGR by comparing it with state-of-the-art group recommender models. [ABSTRACT FROM AUTHOR]

The design of fusion engines is a subject of great importance in a variety of fields. In this paper, we focus on the problem of linear fusion at the feature level for multiple signal matrices with noises, with the features being extremal eigenvectors. When given multiple similarity matrices, the objective is to find an estimate of the latent signal eigenspace. The concentration result for the inner product of features from different matrix samples is developed, utilizing the random matrix theory. Based on of the theoretical results, we proposed an efficient algorithm, EigFuse, to solve the constrained data-driven optimization problem with different level of noises. Our method is of high efficiency by comparing it with state-of-the-art baseline approaches with multiple noise levels. Comprehensive experiments on several synthetic as well as real-life networks demonstrate our method’s superior performance. [ABSTRACT FROM AUTHOR]

In this paper, we focus on co-selection of instances and features in the semi-supervised learning scenario. In this context, co-selection becomes a more challenging problem as data contain labeled and unlabeled examples sampled from the same population. To carry out such semi-supervised co-selection, we propose a unified framework, called sCOs, which efficiently integrates labeled and unlabeled parts into the co-selection process. The framework is based on introducing both a sparse regularization term and a similarity preserving approach. It evaluates the usefulness of features and instances in order to select the most relevant ones, simultaneously. We propose two efficient algorithms that work for both convex and nonconvex functions. To the best of our knowledge, this paper offers, for the first time ever, a study utilizing nonconvex penalties for the co-selection of semi-supervised learning tasks. Experimental results on some known benchmark datasets are provided for validating sCOs and comparing it with some representative methods in the state-of-the art. [ABSTRACT FROM AUTHOR]

We consider a class of nonconvex regularized optimization problems, which appear frequently in machine learning and data processing. Due to the structure of the problems, the iteratively reweighted algorithm was developed and applied to the consensus optimization. In this paper, we propose the acceleration of this scheme by adding an inertial term in each iteration. The proposed algorithms inherit the advantages of classical decentralized algorithms: they can be implemented over a connected network, in which the agents communicate with their neighbors and perform local computations. We also employ the diminishing stepsizes technique for the iteratively reweighted algorithm and consider its acceleration. In specific cases, our algorithms reduce to existing decentralized schemes and also indicate novel ones. Mathematically, we prove the convergence for both algorithms with several assumptions on the objective functions. With Kurdyka-Łojasiewicz property, convergence rates can be derived for constant stepsize case. Numerical results demonstrate the efficiency of the algorithms. [ABSTRACT FROM AUTHOR]

Large-scale optimization has become an important application for data management systems, particularly in the context of statistical machine learning. In this paper, we consider how one might implement the join-and-co-group pattern in the context of a fully declarative data processing system. The join-and-co-group pattern is ubiquitous in iterative, large-scale optimization. In the join-and-co-group pattern, a user-defined function $g$g is parameterized with a data object $x$x as well as the subset of the statistical model $\Theta _x$Θx that applies to that object, so that $g(x | \Theta _x)$g(x|Θx) can be used to compute a partial update of the model. This is repeated for every $x$x in the full data set $X$X. All partial updates are then aggregated and used to perform a complete update of the model. The join-and-co-group pattern has several implementation challenges, including the potential for a massive blow-up in the size of a fully parameterized model. Thus, unless the correct physical execution plan be chosen for implementing the join-and-co-group pattern, it is easily possible to have an execution that takes a very long time or even fails to complete. In this paper, we carefully consider the alternatives for implementing the join-and-co-group pattern on top of a declarative system, as well as how the best alternative can be selected automatically. Our focus is on the SimSQL database system, which is an SQL-based system with special facilities for large-scale, iterative optimization. Since it is an SQL-based system with a query optimizer, those choices can be made automatically. [ABSTRACT FROM AUTHOR]

Keyword search has been widely studied to retrieve relevant substructures from graphs for a given set of keywords. However, existing well-studied approaches aim at finding compact trees/subgraphs containing the keywords, and ignore a critical measure, density, to represent how strongly and stably the keyword nodes are connected in the substructure. In this paper, given a set of keywords $Q = \lbrace w_1, w_2, \ldots, w_l\rbrace$ Q = { w 1 , w 2 ,... , w l } , we study the problem of finding a cohesive subgraph containing $Q$ Q with high density and compactness from a graph $G$ G . We model the cohesive subgraph based on a carefully chosen $k$ k -truss model, and formulate the problem of finding cohesive subgraphs for keyword queries as minimal dense truss search problem, i.e., finding minimal subgraph that maximizes the trussness covering $Q$ Q . However, unlike $k$ k -truss based community search that can be efficiently done based on the local search from a given set of nodes, minimal dense truss search for keyword queries is a nontrivial task as the subset of keyword nodes to be included in the retrieved substructure is previously unknown. To tackle this problem, we first design a novel hybrid KT-Index to keep the keyword and truss information compacly, and then propose an efficient algorithm that carries the search on KT-Index directly to find the dense truss with the maximum trussness $G_{den}$ G d e n without repeated accesses to the original graph. Then, we develop a novel refinement approach to extract minimal dense truss from the dense truss $G_{den}$ G d e n , by checking each node at most once based on the anti-monotonicity property derived from $k$ k -truss, together with several optimization strategies including batch based deletion, early-stop based deletion, and local exploration. Moreover, we also extend the proposed method to deal with the top- $r$ r search. Extensive experimental studies on real-world networks validated the effectiveness and efficiency of our approaches. [ABSTRACT FROM AUTHOR]

Supervised cross-modal hashing has attracted much attention. However, there are still some challenges, e.g., how to effectively embed the label information into binary codes, how to avoid using a large similarity matrix and make a model scalable to large-scale datasets, how to efficiently solve the binary optimization problem. To address these challenges, in this paper, we present a novel supervised cross-modal hashing method, i.e., scalaBle Asymmetric discreTe Cross-modal Hashing, BATCH for short. It leverages collective matrix factorization to learn a common latent space for the labels and different modalities, and embeds the labels into binary codes by minimizing a distance-distance difference problem. Furthermore, it builds a connection between the common latent space and the hash codes by an asymmetric strategy. In the light of this, it can perform cross-modal retrieval and embed more similarity information into the binary codes. In addition, it introduces a quantization minimization term and orthogonal constraints into the optimization problem, and generates the binary codes discretely. Therefore, the quantization error and redundancy may be much reduced. Moreover, it is a two-step method, making the optimization simple and scalable to large-scale datasets. Extensive experimental results on three benchmark datasets demonstrate that BATCH outperforms some state-of-the-art cross-modal hashing methods in terms of accuracy and efficiency. [ABSTRACT FROM AUTHOR]

Coupled Matrix Tensor Factorization (CMTF) facilitates the integration and analysis of multiple data sources and helps discover meaningful information. Nonnegative CMTF (N-CMTF) has been employed in many applications for identifying latent patterns, prediction, and recommendation. However, due to the added complexity with coupling between tensor and matrix data, existing N-CMTF algorithms exhibit poor computation efficiency. In this paper, a computationally efficient N-CMTF factorization algorithm is presented based on the column-wise element selection, preventing frequent gradient updates. Theoretical and empirical analyses show that the proposed N-CMTF factorization algorithm is not only more accurate but also more computationally efficient than existing algorithms in approximating the tensor as well as in identifying the underlying nature of factors. [ABSTRACT FROM AUTHOR]

With the increasing of the data size and the development of multi-core computers, asynchronous parallel stochastic optimization algorithms such as KroMagnon have gained significant attention. In this paper, we propose a new Sparse approximation and asynchronous parallel Stochastic Variance Reduced Gradient (SSVRG) method for sparse and high-dimensional machine learning problems. Unlike standard SVRG and its asynchronous parallel variant, KroMagnon, the snapshot point of SSVRG is set to the average of all the iterates in the previous epoch, which allows it to take much larger learning rates and also makes it more robust to the choice of learning rates. In particular, we use the sparse approximation of the popular SVRG estimator to perform completely sparse updates at all iterations. Therefore, SSVRG has a much lower per-iteration computational cost than its dense counterpart, SVRG++, and is very friendly to asynchronous parallel implementation. Moreover, we provide the convergence guarantees of SSVRG for both strongly convex and non-strongly convex problems, while existing asynchronous algorithms (e.g., KroMagnon and ASAGA) only have convergence guarantees for strongly convex problems. Finally, we extend SSVRG to non-smooth and asynchronous parallel settings. Numerical experimental results demonstrate that SSVRG converges significantly faster than the state-of-the-art asynchronous parallel methods, e.g., KroMagnon, and is usually more than three orders of magnitude faster than SVRG++. [ABSTRACT FROM AUTHOR]

This paper revisits the classical problem of multiple query optimization in federated RDF systems. We propose a heuristic query rewriting-based approach to optimize the evaluation of multiple queries. This approach can take advantage of SPARQL 1.1 to share the common computation of multiple queries while considering the cost of both query evaluation and data shipment. Although we prove that finding the optimal rewriting for multiple queries is NP-complete, we propose a heuristic rewriting algorithm with a bounded approximation ratio. Furthermore, we propose an efficient method to use the interconnection topology between RDF sources to filter out irrelevant sources, and utilize some characteristics of SPARQL 1.1 to optimize multiple joins of intermediate matches. The extensive experimental studies show that the proposed techniques are effective, efficient and scalable. [ABSTRACT FROM AUTHOR]

Transfer covariance function, which can model domain similarity and adaptively control the knowledge transfer across domains, is widely used in transfer learning. In this paper, we concentrate on Gaussian process (GP) models using a transfer covariance function for regression problems in a black-box learning scenario. Precisely, we investigate a family of rather general transfer covariance functions, ${T}_{*}$ T * , that can model the heterogeneous sub-similarities of domains through multiple kernel learning. A necessary and sufficient condition to obtain valid GPs using ${T}_{*}$ T * ($GP_{T_{*}}$ G P T * ) for any data is given. This condition becomes specially handy for practical applications as (i) it enables semantic interpretations of the sub-similarities and (ii) it can readily be used for model learning. In particular, we propose a computationally inexpensive model learning rule that can explicitly capture different sub-similarities of domains. We propose two instantiations of $GP_{T_{*}}$ G P T * , one with a set of predefined constant base kernels and one with a set of learnable parametric base kernels. Extensive experiments on 36 synthetic transfer tasks and 12 real-world transfer tasks demonstrate the effectiveness of $GP_{T_{*}}$ G P T * on the sub-similarity capture and the transfer performance. [ABSTRACT FROM AUTHOR]

Finding top- $k$ k frequent items has been a hot issue in databases. Finding top- $k$ k persistent items is a new issue, and has attracted increasing attention in recent years. In practice, users often want to know which items are significant, i.e., not only frequent but also persistent. No prior art can address both of the above two issues at the same time. Also, for high-speed data streams, prior art cannot achieve high accuracy when the memory is tight. In this paper, we define a new issue, named finding significant items, and propose a novel algorithm namely LTC to address this issue. It includes two key techniques, Long-tail Restoring and CLOCK, as well as three optimizations. In addition, LTC is extended to support finding significant items with thresholds. We theoretically derive the correct rate and error bound, and conduct extensive experiments on three real datasets to test the performance of LTC. Our experimental results show that LTC can achieve $10^5$ 10 5 times higher accuracy in terms of average relative error than other related algorithms. Lastly, LTC is applied to a DDoS detection task and it shows that finding significant items is more powerful than finding frequent items. [ABSTRACT FROM AUTHOR]

Studies show that a person is willing to join a social group activity if the activity is interesting, and if some close friends also join the activity as companions. The literature has demonstrated that the interests of a person and the social tightness among friends can be effectively derived and mined from social networking websites. However, even with the above two kinds of information widely available, social group activities still need to be coordinated manually, and the process is tedious and time-consuming for users, especially for a large social group activity, due to complications of social connectivity and the diversity of possible interests among friends. To address the above important need, this paper proposes to automatically select and recommend potential attendees of a social group activity, which could be very useful for social networking websites as a value-added service. We first formulate a new problem, named Willingness mAximization for Social grOup (WASO). This paper points out that the solution obtained by a greedy algorithm is likely to be trapped in a local optimal solution. Thus, we design a new randomized algorithm to effectively and efficiently solve the problem. Given the available computational budgets, the proposed algorithm is able to optimally allocate the resources and find a solution with an approximation ratio. We implement the proposed algorithm in Facebook, and the user study demonstrates that social groups obtained by the proposed algorithm significantly outperform the solutions manually configured by users. [ABSTRACT FROM PUBLISHER]

Driving is a complex activity that requires multi-level skilled operations (e.g., acceleration, braking, and turning). Analyzing driving behaviors can help us assess driver performances, improve traffic safety, and, ultimately, promote the development of intelligent and resilient transportation systems. While some efforts have been made for analyzing driving behaviors, existing methods can be improved via representation learning by jointly exploring the peer and temporal dependencies of driving behaviors. To that end, in this paper, we develop a Peer and Temporal-Aware Representation Learning based framework (PTARL) for driving behavior analysis with GPS trajectory data. Specifically, we first detect the driving operations and states of each driver from their GPS traces. Then, we derive a sequence of multi-view driving state transition graphs from the driving state sequences, in order to characterize a driver's driving behaviors that vary over time. In addition, we develop a peer and temporal-aware representation learning method to learn a sequence of time-varying yet relational vectorized representations from the driving state transition graphs. The proposed method can simultaneously model both the graph-graph peer dependency and the current-past temporal dependency in a unified optimization framework. Also, we provide two effective solutions for the optimization problem: (i) a joint optimization solution of representation learning and prediction; and (ii) a step-by-step solution of representation learning and prediction. Besides, we explore two strategies to fuse the learned representations from multi-view transition graphs: (i) simple alignment and (ii) collective fusion. Moreover, we apply the developed framework to the two applications of quantitative transportation safety: (i) scoring of driving performances, and (ii) detection of dangerous regions. Finally, we present extensive experimental results with big trajectory data to demonstrate the enhanced performances of the proposed method for quantitative transportation safety. [ABSTRACT FROM AUTHOR]

Recently, reconciling social networks, identifying the accounts belonging to the same individual across social networks, receives significant attention from both academic and industry. Most of the existing studies have limitations in the following three aspects: multiplicity, comprehensiveness and robustness. To address these limitations, we rethink this problem and, for the first time, robustly and comprehensively reconcile multiple social networks. In this paper, we propose two frameworks, MASTER and MASTER+, i.e., across Multiple social networks, integrate Attribute and STructure Embedding for Reconciliation. In MASTER, we first design a novel Constrained Dual Embedding model, simultaneously embedding and reconciling multiple social networks, to formulate this problem into a unified optimization. To address this optimization, we then design an effective NS-Alternating algorithm and prove it converges to KKT points. To further speed up MASTER, we propose a scalable framework, namely MASTER+. The core idea is to group accounts into clusters and then perform MASTER in each cluster in parallel. Specifically, we design an efficient Augmented Pre-Embedding model and Balance-aware Fuzzy Clustering algorithm for the high efficiency and the high accuracy. Extensive experiments demonstrate that both MASTER and MASTER+ outperform the state-of-the-art approaches. Moreover, MASTER+ inherits the effectiveness of MASTER and enjoys higher efficiency. [ABSTRACT FROM AUTHOR]

The number of “hits” has been widely regarded as the lifeblood of many web systems, e.g., e-commerce systems, advertising systems and multimedia consumption systems. However, users would not hit an item if they cannot see it, or they are not interested in the item. Recommender system plays a critical role of discovering interesting items from near-infinite inventory and exhibiting them to potential users. Yet, two issues are crippling the recommender systems. One is “how to handle new users”, and the other is “how to surprise users”. The former is well-known as cold-start recommendation. In this paper, we show that the latter can be investigated as long-tail recommendation. We also exploit the benefits of jointly challenging both cold-start and long-tail recommendation, and propose a novel approach which can simultaneously handle both of them in a unified objective. For the cold-start problem, we learn from side information, e.g., user attributes, user social relationships, etc. Then, we transfer the learned knowledge to new users. For the long-tail recommendation, we decompose the overall interesting items into two parts: a low-rank part for short-head items and a sparse part for long-tail items. The two parts are independently revealed in the training stage, and transfered into the final recommendation for new users. Furthermore, we effectively formulate the two problems into a unified objective and present an iterative optimization algorithm. A fast extension of the method is proposed to reduce the complexity, and extensive theoretical analysis are provided to proof the bounds of our approach. At last, experiments of social recommendation on various real-world datasets, e.g., images, blogs, videos and musics, verify the superiority of our approach compared with the state-of-the-art work. [ABSTRACT FROM AUTHOR]

Semi-supervised learning models for multiview data are important in image classification tasks, since heterogeneous features are easy to obtain and semi-supervised schemes are economical and effective. To model the view importance, conventional graph-based multiview learning models learn a linear combination of views while assuming a priori weights distribution. In this paper, we present a novel structural regularized semi-supervised model for multiview data, termed Adaptive MUltiview SEmi-supervised model (AMUSE). Our new model learns weights from a priori graph structure, which is more reasonable than weight regularization. Theoretical analysis reveals the significant difference between AMUSE and the prior arts. An efficient optimization algorithm is provided to solve the new model. Experimental results on six real-world data sets demonstrate the effectiveness of the structural regularized weights learning scheme. [ABSTRACT FROM AUTHOR]

Aligning users across different social networks has become increasingly studied as an important task to social network analysis. In this paper, we propose a novel representation learning method that mainly exploits social structures for the network alignment. In particular, the proposed network embedding framework models the follower-ship and followee-ship of each user explicitly as input and output context vectors, while preserving the proximity of users with “similar” followers and followees in the embedded space. We incorporate both known and predicted user anchors across the networks as constraints to facilitate the transfer of context information to achieve accurate user alignment. Both network embedding and user alignment are inferred under a unified optimization framework with negative sampling adopted to ensure scalability. Also, variants of the proposed framework, including the incorporation of higher-order structural features, are also explored for further boosting the alignment accuracy. Extensive experiments on large-scale social and academia network datasets demonstrate the efficacy of our proposed model compared with state-of-the-art methods. [ABSTRACT FROM AUTHOR]

The retrieval function is one of the most important components of an Information Retrieval (IR) system, because it determines to what extent some information is relevant to a user query. Most retrieval functions have “free parameters” whose value must be set before retrieval, significantly affecting the effectiveness of an IR system. Choosing the optimum values for such parameters is therefore of paramount importance. However, the optimum can only be found after a computationally expensive process, especially when the generalization error is estimated via cross-validation. In this paper, we propose to determine free parameter values by solving an optimization problem aimed at maximizing a measure of retrieval effectiveness. We employ the black-box optimization paradigm, since the analytical expression of the measure of effectiveness with respect to the free parameters is unknown. We consider different methods for solving the black-box optimization problem: a simple grid-search over the whole domain, and more sophisticated techniques such as line search and surrogate model based algorithms. Experimental results on several test collections not only provide useful insight about effectiveness, but also about efficiency: they indicate that with appropriate optimization techniques, the computational cost of parameter optimization can be greatly reduced without compromising retrieval effectiveness, even when taking generalization into account. [ABSTRACT FROM AUTHOR]

Networks are prevalent in many high impact domains. Moreover, cross-domain interactions are frequently observed in many applications, which naturally form the dependencies between different networks. Such kind of highly coupled network systems are referred to as multi-layered networks, and have been used to characterize various complex systems, including critical infrastructure networks, cyber-physical systems, collaboration platforms, biological systems, and many more. Different from single-layered networks where the functionality of their nodes is mainly affected by within-layer connections, multi-layered networks are more vulnerable to disturbance as the impact can be amplified through cross-layer dependencies, leading to the cascade failure to the entire system. To manipulate the connectivity in multi-layered networks, some recent methods have been proposed based on two-layered networks with specific types of connectivity measures. In this paper, we address the above challenges in multiple dimensions. First, we propose a family of connectivity measures (SubLine) that unifies a wide range of classic network connectivity measures. Third, we reveal that the connectivity measures in the SubLine family enjoy diminishing returns property, which guarantees a near-optimal solution with linear complexity for the connectivity optimization problem. Finally, we evaluate our proposed algorithm on real data sets to demonstrate its effectiveness and efficiency. [ABSTRACT FROM PUBLISHER]

Pattern mining (PM) refers to the process of discovering patterns of interest to users from data. However, most studies have considered only one pattern, such as frequent pattern or high-utility pattern. With the continuous requirement of businesses in various industries, the single-objective PM methods are difficult to meet the increasingly diverse needs of users. In this paper, a multi-objective problem model for high quality pattern mining (HQPM) is proposed, where the objectives are support, occupancy, and utility. In order to solve the proposed three-objective problem efficiently, an improved multi-objective evolutionary algorithm for HQPM (MOEA-PM) is proposed. Two kinds of population initialization strategies are designed, which is used to ensure the population is effectively distributed in the feasible solution space. By taking the properties of the model into consideration, an auxiliary tool is proposed to accelerate the convergence of the algorithm. Experimental results on real-world datasets show that the proposed three-objective problem model with the MOEA-PM algorithm can discover patterns that are both frequently occurring and has a high utility in the transaction datasets, while at the same time being relatively complete. Compared with the state-of-the-art MOEA-based HQPM algorithms, MOEA-PM has better performance in terms of efficiency, quality, and convergence speed. [ABSTRACT FROM AUTHOR]

Partial multi-view clustering has attracted various attentions from diverse fields. Most existing methods adopt separate steps to obtain unified representations and extract clustering indicators. This separate manner prevents two learning processes to negotiate to achieve optimal performance. In this paper, we propose the Joint Representation Learning and Clustering (JRLC) framework to address this issue. The JRLC framework employs representation matrices to extract view-specific clustering information directly from the presence of partial similarity matrices, and rotates them to learn a common probability label matrix simultaneously, which connects representation learning and clustering seamlessly to achieve better clustering performance. Under the guidance of JRLC framework, several new incomplete multi-view clustering methods can be developed by extending existing single-view graph-based representation learning methods. For illustration, within the framework, we propose two specific methods, JRLC with spectral embedding (JRLC-SE) and JRLC via integrating nonnegative embedding and spectral embedding (JRLC-NS). Two iterative algorithms with guaranteed convergence are designed to solve the resultant optimization problems of JRLC-SE and JRLC-NS. Experimental results on various datasets and news topic clustering application demonstrate the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Dynamic ridesharing refers to services that arrange one-time shared rides on short notice. It underpins various real-world intelligent transportation applications such as car-pooling, food delivery and last-mile logistics. A core operation in dynamic ridesharing is the “insertion operator”. Given a worker and a feasible route which contains a sequence of origin-destination pairs from previous requests, the insertion operator inserts a new origin-destination pair from a newly arrived request into the current route such that certain objective is optimized. Common optimization objectives include minimizing the maximum/sum flow time of all requests and minimizing the total travel time of the worker. Despite its frequent usage, the insertion operator has a time complexity of $O(n^3)$ O (n 3) , where $n$ n is the number of all requests assigned to the worker. The cubic running time of insertion fundamentally limits the efficiency of urban-scale dynamic ridesharing based applications. In this paper, we propose a novel partition framework and a dynamic programming based insertion with a time complexity of $O(n^2)$ O (n 2) . We further improve the time efficiency of the insertion operator to $O(n)$ O (n) harnessing efficient index structures, such as fenwick tree. Evaluations on two real-world large-scale datasets show that our methods can accelerate insertion by 1.5 to 998.1 times. [ABSTRACT FROM AUTHOR]

In this paper, a new method is proposed for creating an optimized ensemble classifier. The proposed method mitigates the issue of class imbalances by partitioning the input data into its various data classes. The partitions are then clustered incrementally to generate a pool of class pure data clusters. The generated data clusters are then balanced by adding samples from all classes which are closest to the cluster centroid. In this manner all generated data clusters are balanced and classifiers trained on such a data cluster are unbiased as well. This creates a diverse input space for training of base classifiers. The pool of clusters is then utilized to train a set of diverse base classifiers to generate the base classifier pool. The pool of classifiers is then treated as a combinatorial problem of optimization and an evolutionary algorithm is incorporated. The proposed approach generates an optimized ensemble classifier that can not only achieve the highest classification accuracy but also has a lower component size as well. The proposed approach is tested on 31 benchmark datasets from UCI machine learning repository and results are compared with existing state-of-the-art ensemble classifiers as well. [ABSTRACT FROM AUTHOR]

Multi-view spectral clustering can effectively reveal the intrinsic clustering structure among data by performing clustering on the learned optimal embedding across views. Though demonstrating promising performance in various applications, most of existing methods usually linearly combine a group of pre-specified first-order Laplacian matrices to construct the optimal Laplacian matrix, which may result in limited representation capability and insufficient information exploitation. Also, storing and implementing complex operations on the $n\times n$ n × n Laplacian matrices incur intensive storage and computation complexity. To address these issues, this paper first proposes a multi-view spectral clustering algorithm that learns a high-order optimal neighborhood Laplacian matrix, and then extends it to the late fusion version for accurate and efficient multi-view clustering. Specifically, our proposed algorithm generates the optimal Laplacian matrix by searching the neighborhood of the linear combination of both the first-order and high-order base Laplacian matrices simultaneously. By this way, the representative capacity of the learned optimal Laplacian matrix is enhanced, which is helpful to better utilize the hidden high-order connection information among data, leading to improved clustering performance. We design an efficient algorithm with proved convergence to solve the resultant optimization problem. Extensive experimental results on nine datasets demonstrate the superiority of our algorithm against state-of-the-art methods, which verifies the effectiveness and advantages of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The implicit feedback based collaborative filtering (CF) has attracted much attention in recent years, mainly because users implicitly express their preferences in many real-world scenarios. The current mainstream pairwise methods optimize the Area Under the Curve (AUC) and are empirically proved to be helpful to exploit binary relevance data, but lead to either not address the ranking problem, or not specifically focus on top- $k$ k recommendation. Although there exists the listwise method maximizes the Mean Reciprocal Rank (MRR), it has low efficiency and is not particularly adequate for general implicit feedback situations. To that end, in this paper, we propose a new framework, namely Collaborative List-and-Pairwise Filtering (CLAPF), which aims to introduce pairwise thinking into listwise methods. Specifically, we smooth another well-known rank-biased measure called Mean Average Precision (MAP), and respectively combine two rank-biased metrics (MAP, MRR) with the pairwise objective function to capture the performance of top- $k$ k recommendation. Furthermore, the sampling scheme for CLAPF is discussed to accelerate the convergence speed. Our CLAPF framework is a new hybrid model that provides an idea of utilizing rank-biased measures in a pairwise way on implicit feedback. Empirical studies demonstrated CLAPF outperforms state-of-the-art approaches on real-world datasets. [ABSTRACT FROM AUTHOR]

Machine learning can provide deep insights into data, allowing machines to make high-quality predictions and having been widely used in real-world applications, such as text mining, visual classification, and recommender systems. However, most sophisticated machine learning approaches suffer from huge time costs when operating on large-scale data. This issue calls for the need of Large-scale Machine Learning (LML), which aims to learn patterns from big data with comparable performance efficiently. In this paper, we offer a systematic survey on existing LML methods to provide a blueprint for the future developments of this area. We first divide these LML methods according to the ways of improving the scalability: 1) model simplification on computational complexities, 2) optimization approximation on computational efficiency, and 3) computation parallelism on computational capabilities. Then we categorize the methods in each perspective according to their targeted scenarios and introduce representative methods in line with intrinsic strategies. Lastly, we analyze their limitations and discuss potential directions as well as open issues that are promising to address in the future. [ABSTRACT FROM AUTHOR]

Multiple kernel clustering (MKC) algorithm aims to group data into different categories by optimally integrating information from a group of pre-specified kernels. Though demonstrating superiorities in various applications, we observe that existing MKC algorithms usually do not sufficiently consider the local density around individual data samples and excessively limit the representation capacity of the learned optimal kernel, leading to unsatisfying performance. In this paper, we propose an algorithm, called optimal neighborhood MKC with adaptive local kernels (ON-ALK), to address the two issues. In specific, we construct adaptive local kernels to sufficiently consider the local density around individual data samples, where different numbers of neighbors are discriminatingly selected on each sample. Further, the proposed ON-ALK algorithm boosts the representation of the learned optimal kernel via relaxing it into the neighborhood area of weighted combination of the pre-specified kernels. To solve the resultant optimization problem, a three-step iterative algorithm is designed and theoretically proven to be convergent. After that, we also study the generalization bound of the proposed algorithm. Extensive experiments have been conducted to evaluate the clustering performance. As indicated, the algorithm significantly outperforms state-of-the-art methods in recent literatures on six challenging benchmark datasets, verifying its advantages and effectiveness. [ABSTRACT FROM AUTHOR]

Networks are prevalent and often collected from multiple sources in many high-impact domains, which facilitate many emerging applications that require the connections across multiple networks. Network alignment (i.e., to find the node correspondence between different networks) has become the very first step in many applications and thus has been studied in decades. Although some existing works can use the attribute information as part of the alignment process, they still have certain limitations. For example, some existing network alignment methods can use node attribute similarities as part of the prior alignment information, whereas most of them solely explore the topology consistency without the consistency among attributes of the underlying networks. On the other hand, traditional graph matching methods encode both the node and edge attributes (and possibly the topology) into an affinity matrix and formulate it as a constrained nonconvex quadratic maximization problem. However, these methods cannot scale well to the large-scale networks. In this paper, we propose a family of network alignment algorithms (FINAL) to efficiently align the attributed networks. The key idea is to leverage the node/edge attribute information to guide the (topology-based) alignment process. We formulate this problem as a convex quadratic optimization problem, and develop effective and efficient algorithms to solve it. Moreover, we derive FINAL On-Query, an online variant of FINAL that can find similar nodes for the query nodes across networks. We perform extensive evaluations on real networks to substantiate the superiority of our proposed approaches. [ABSTRACT FROM AUTHOR]

Dual Coordinate Descent (DCD) is one of the most popular optimization methods. The parallelization of DCD is difficult, as DCD is sequential in nature. As such, simultaneously running multiple DCD threads on batches of data elements causes result inaccuracy and slow convergence, due to the concurrent updates of multiple coordinates. Some parallelization methods adopt separable approximate functions that depend on the degree of parallelism. Such dependencies result in both poor scalability and slow-convergence. To address these challenges, in this paper we present a new parallel primal-dual algorithm for DCD, called PPD. In PPD, the block data distribution is utilized to obtain a new approximate function that is independent from the parallelism. Moreover, PPD is designed with a novel primal-dual acceleration scheme to approach the optimal solution closely and quickly. We demonstrate the advantages of PPD in terms of scalability and efficiency through experiments. [ABSTRACT FROM AUTHOR]

Low rank matrix factorisation is often used in recommender systems as a way of extracting latent features. When dealing with large and sparse datasets, traditional recommendation algorithms face the problem of acquiring large, unrestrained, fluctuating values over predictions. Imposing bounding constraints has been proven an effective solution. However, existing bounding algorithms can only deal with one pair of fixed bounds, and are very time-consuming when applied on large-scale datasets. In this paper, we propose a novel algorithm named Magnitude Bounded Matrix Factorisation (MBMF), which allows different bounds for individual users/items and performs very quickly on large scale datasets. The key idea of our algorithm is to construct a model by constraining the magnitudes of each individual user/item feature vector. By converting coordinate system with radii set as the corresponding magnitudes, MBMF allows the above constrained optimisation problem to become an unconstrained one, which can be solved by unconstrained optimisation algorithms such as the stochastic gradient descent. We also explore an acceleration approach and the choice of magnitudes are given in detail as well. Experiments on synthetic and real datasets demonstrate that in most cases the proposed MBMF is superior over all existing algorithms in terms of accuracy and time complexity. [ABSTRACT FROM AUTHOR]

Link prediction and network alignment are two fundamental and interleaved tasks in network analysis. In this paper, we propose a novel cross-network embedding model under the Skip-gram framework, which alternately performs link prediction and network alignment by joint optimization. Vertex sequences, obtained via a biased random walk based on empirical mixture distributions, are used to train a Skip-gram based node embedding model. On one hand, based on the similarity in embedding space, network alignment can be effectively performed either with the initial ground truth alignments as seeds or from scratch. On the other hand, the proposed link prediction model involves training a supervised classifier by sampling a set of positive and negative edges. We also modify and incorporate the Collective Link Fusion (CLF) method under a Skip-gram framework and show that the new method can achieve better results in both tasks. Extensive experimental results show the state-of-the-art performance of our methods. [ABSTRACT FROM AUTHOR]

Due to the exponential growth of multimedia data, multi-modal hashing as a promising technique to make cross-view retrieval scalable is attracting more and more attention. However, most of the existing multi-modal hashing methods either divide the learning process unnaturally into two separate stages or treat the discrete optimization problem simplistically as a continuous one, which leads to suboptimal results. Recently, a few discrete multi-modal hashing methods that try to address such issues have emerged, but they still ignore several important discrete constraints (such as the balance and decorrelation of hash bits). In this paper, we overcome those limitations by proposing a novel method named “Enhanced Discrete Multi-modal Hashing (EDMH)” which learns binary codes and hashing functions simultaneously from the pairwise similarity matrix of data, under the aforementioned discrete constraints. Although the model of EDMH looks a lot more complex than the other models for multi-modal hashing, we are actually able to develop a fast iterative learning algorithm for it, since the subproblems of its optimization all have closed-form solutions after introducing a couple of auxiliary variables. Our experimental results on three real-world datasets have revealed the usefulness of those previously ignored discrete constraints and demonstrated that EDMH not only performs much better than state-of-the-art competitors according to several retrieval metrics but also runs much faster than most of them. [ABSTRACT FROM AUTHOR]

Due to their high retrieval efficiency and low storage cost, cross-modal hashing methods have attracted considerable attention. Generally, compared with shallow cross-modal hashing methods, deep cross-modal hashing methods can achieve a more satisfactory performance by integrating feature learning and hash codes optimizing into a same framework. However, most existing deep cross-modal hashing methods either cannot learn a unified hash code for the two correlated data-points of different modalities in a database instance or cannot guide the learning of unified hash codes by the feedback of hashing function learning procedure, to enhance the retrieval accuracy. To address the issues above, in this paper, we propose a novel end-to-end Deep Cross-Modal Hashing with Hashing Functions and Unified Hash Codes Jointly Learning (DCHUC). Specifically, by an iterative optimization algorithm, DCHUC jointly learns unified hash codes for image-text pairs in a database and a pair of hash functions for unseen query image-text pairs. With the iterative optimization algorithm, the learned unified hash codes can be used to guide the hashing function learning procedure; Meanwhile, the learned hashing functions can feedback to guide the unified hash codes optimizing procedure. Extensive experiments on three public datasets demonstrate that the proposed method outperforms the state-of-the-art cross-modal hashing methods. [ABSTRACT FROM AUTHOR]

Community detection is one of the fundamental tasks in graph mining, which aims to identify group assignment of nodes in a complex network. Recently, network embedding techniques have demonstrated their strong power in advancing the community detection task and achieve better performance than various traditional methods. Despite their empirical success, most of the existing algorithms directly leverage the observed coarse network structure for community detection. Therefore, they often lead to suboptimal performance as the observed connections fail to capture the essential tie strength information among nodes precisely and account for the impact of noisy links. In this paper, an optimal network structure for community detection is introduced to characterize the fine-grained tie strength information between connected nodes and alleviate the adverse effects of noisy links. To obtain an expressive node representation for community detection, we learn the optimal network structure and network embeddings in a joint framework, instead of using a two-stage approach to derive the node embeddings from the coarse network topology. In particular, we formulate the joint framework as an optimization problem and an alternating optimization algorithm is exploited to solve the proposed optimization problem. Additionally, theoretical analyses regarding the computational complexity and the convergence of the optimization algorithm are also provided. Extensive experiments on both synthetic and real-world networks demonstrate the effectiveness and superiority of the proposed framework. [ABSTRACT FROM AUTHOR]

Traditional recommender systems (RS) only consider homogeneous data and cannot fully model heterogeneous information of complex objects and relations. Recent advances in the study of Heterogeneous Information Network (HIN) have shed some light on how to leverage heterogeneous information in RS. However, existing HIN-based recommendation models assume HIN is invariable and merely use HIN as a data source for assisting recommendation, which limits their performance. In this paper, we propose a multi-task learning framework, called MTRec, for recommendation over HIN. MTRec relies on self-attention mechanism to learn the semantics of meta-paths in HIN and jointly optimizes the tasks of both recommendation and link prediction. Using a Bayesian task weight learner, MTRec is able to achieve the balance of two tasks during optimization automatically. Moreover, MTRec provides good interpretabilities of recommendation through a “translation” mechanism which is used to model the three-way interactions among users, items and the meta-paths connecting them. Experimental results demonstrate the superiority of MTRec over state-of-the-art HIN-based recommendation models, and the case studies we provide illustrate that MTRec enhances the explainability of RS. [ABSTRACT FROM AUTHOR]

To aggregate useful information among diversified sources, a hotspot research topic called truth discovery has emerged in recent years. Existing truth discovery methods attempt to infer the true attribute values for the entities by identifying and trusting reliable data sources. That is, the values provided by reliable sources are more likely to be the true values. However, all these methods neglect the relations among different entities, which play important roles in truth discovery task. When reliable data sources cannot provide sufficient information of entities, the true attribute values of these entities can still be inferred by propagating trustworthy information from related entities. Motivated by this, in this paper, we introduce the constrained truth discovery problem. We incorporate denial constraints, a universally quantified first-order logic formalism which can express a large number of effective and widely existing relations among entities, into the process of truth discovery. We formulate it as a constrained optimization problem and analyze its hardness. To address the problem, we propose algorithms to partition the entities into disjoint groups, and generate arithmetic constraints for each disjoint group separately. Then, the true attribute values of the entities in each disjoint group are derived by minimizing the objective function under the corresponding arithmetic constraints. Experimental results on both real-world and synthetic datasets demonstrate that the proposed approach achieves good performance even with very few constraints and reliable sources. [ABSTRACT FROM AUTHOR]

The low-rank matrix completion problem is fundamental in both machine learning and computer vision fields with many important applications, such as recommendation system, motion capture, face recognition, and image inpainting. In order to avoid solving the rank minimization problem which is NP-hard, several surrogate functions of the rank have been proposed in the literature. However, the matrix restored from the optimization problem based on the existing surrogate functions seriously deviates from the original one. In this paper, we first design a new non-convex Schatten capped $p$ p norm which generalizes several existing non-convex matrix norms and balances between the rank and the nuclear norm of the matrix. Then, a matrix completion method based on the Schatten capped $p$ p norm is proposed by exploiting the framework of the alternating direction method of multipliers. Meanwhile, the Schatten capped $p$ p norm regularized least squares subproblem is analyzed in detail and is solved explicitly. Finally, we evaluate the performance of the proposed matrix completion method based on extensive experiments in the field of image inpainting. All the experimental results demonstrate that the proposed method can indeed improve the accuracy of matrix completion compared with the existing methods. [ABSTRACT FROM AUTHOR]

Recently, network lasso has dawn much attention due to its remarkable performance on simultaneous clustering and optimization. However, it usually suffers from the imperfect data (noise, missing values, etc.), and yields sub-optimal solutions. The reason is that it finds the similar instances according to their features directly, which is usually impacted by the imperfect data, and thus returns sub-optimal results. In this paper, we propose triangle lasso to avoid its disadvantage for graph datasets. In a graph dataset, each instance is represented by a vertex. If two instances have many common adjacent vertices, they tend to become similar. Although some instances are profiled by the imperfect data, it is still able to find the similar counterparts. Furthermore, we develop an efficient algorithm based on Alternating Direction Method of Multipliers (ADMM) to obtain a moderately accurate solution. In addition, we present a dual method to obtain the accurate solution with the low additional time consumption. We demonstrate through extensive numerical experiments that triangle lasso is robust to the imperfect data. It usually yields a better performance than the state-of-the-art method when performing data analysis tasks in practical scenarios. [ABSTRACT FROM AUTHOR]

To improve the classification performance of support vector machines (SVMs) on imbalanced datasets, cost-sensitive learning methods have been proposed, e.g., Different Error Costs (DEC) and Fuzzy SVM for Class Imbalance Learning (FSVM-CIL). They relocate the hyperplane by adjusting the costs associated with misclassifying samples. However, the error costs are determined either empirically or by performing an exhaustive search in the parameter space. Both strategies can not guarantee effectiveness and efficiency simultaneously. In this paper, we propose ATEC, a solution that can efficiently find a preferable hyperplane by automatically tuning the error cost for between-class samples. ATEC distinguishes itself from all existing parameter tuning strategies by two main features: (1) it can evaluate how effective an error cost is in terms of classification accuracy; and (2) it changes the error cost in the right direction if it is not effective. Extensive experiments show that compared with the state-of-art methods, SVMs that are equipped with ATEC can not only obtain comparable improvements in terms of F1 score of minority class, area under the precision-recall curve (AUC-PR) and area under the ROC curve (AUC-ROC) scores, but also outperform the grid-search parameter tuning strategy by two orders of magnitude in terms of the training time when a high F1 score is required. [ABSTRACT FROM AUTHOR]

Hashing methods have been extensively applied to efficient multimedia data indexing and retrieval on account of the explosion of multimedia data. Cross-modal hashing usually learns binary codes by mapping multi-modal data into a common Hamming space. Most supervised methods utilize relation information like class labels as pairwise similarities of cross-modal data pair to narrow intra-modal and inter-modal gap. In this paper, we propose a novel supervised cross-modal hashing method dubbed Subspace Relation Learning for Cross-modal Hashing (SRLCH), which exploits relation information of labels in semantic space to make similar data from different modalities closer in the low-dimension Hamming subspace. SRLCH preserves the modality relationships, the discrete constraints and nonlinear structures, while admitting a closed-form binary codes solution, which effectively enhances the training efficiency. An iterative alternative optimization algorithm is developed to simultaneously learn both hash functions and unified binary codes. With these binary codes and hash functions, we can index multimedia data and search them in an efficient way. Evaluations in two cross-modal retrieval tasks on several widely-used datasets show that the proposed SRLCH outperforms most cross-modal hashing methods. Theoretical analysis also illustrates reasons for our method’s promotion in subspace relation learning. [ABSTRACT FROM AUTHOR]

Given a geo-textual dataset $\mathbb {O}$ O , a set $\varphi$ φ of keywords, a query object $q \in \mathbb {O}$ q ∈ O , and an integer $k$ k , a reverse top- $k$ k keyword-based location query returns the influence zone $\mathcal {R}$ R of $q$ q such that $q$ q belongs to the result of a top- $k$ k spatial keyword query with query keywords $\varphi$ φ and any location in $\mathcal {R}$ R as arguments. For a query object $q$ q , the influence zone of $q$ q varies for different keywords $\varphi$ φ . Users may be interested in identifying the maximum influence zone of the query object. To this end, in this paper, we study the problem called MaxiZone that finds the keyword set maximizing the influence zone of a specified query object. The MaxiZone problem has many real-life applications, e.g., a business owner would like to identify the maximum influence zone so as to attract as many customers as possible. A straightforward way to tackle the MaxiZone problem is to compute the influence zone for every candidate keyword set. Obviously, this is infeasible if there are a large number of candidate keyword sets. We propose a more efficient index-centric algorithm together with a series of optimizations as well as a sampling-based algorithm, to facilitate the query processing. Moreover, we extend the proposed algorithms to address a variant of MaxiZone problem called $\tau$ τ -MaxiZone problem, which finds top- $\tau$ τ keyword sets having the maximum influence zones. Extensive empirical study using real-world datasets demonstrates the effectiveness and efficiency of our proposed algorithms. [ABSTRACT FROM AUTHOR]