Learning from data with missing values is a common challenge in real-world applications. Existing approaches for handling data incompleteness often involve imputation, which can introduce errors that propagate into downstream tasks or impose assumptions that limit the support for heterogeneous feature types. To address these issues, we propose Missing Feature Attention Network ( MFAN ), an end-to-end label prediction model that directly consumes incomplete data without requiring imputation. MFAN flexibly accommodates both continuous and categorical features through learnable embeddings, and leverages a transformer encoder with self-attention to capture the correlation among features as well as the correlation between features and missingness . This attention-based mechanism allows missing features to benefit from relationships learned among observed features, leading to enhanced hidden representations and robust prediction performance. Additionally, we introduce auxiliary self-supervised pre-training tasks that further guide the attention mechanism in modeling missingness. Experimental results on eight regression and seven classification datasets demonstrate MFAN ’s superiority over state-of-the-art end-to-end methods and imputation-based approaches. Comprehensive ablation studies confirm the effectiveness of each MFAN component, underscoring the importance of explicitly modeling correlations among observed and missing features.

Incremental data drifting is a common problem when employing a machine-learning model in industrial applications. The underlying data distribution evolves gradually, e.g., users change their buying preferences on an E-commerce website over time. The problem needs to be addressed to obtain high performance. Right now, studies regarding incremental data drifting suffer from several issues. For one thing, there is a lack of clear-defined incremental drift datasets for examination. Existing efforts use either collected real datasets or synthetic datasets that show two obvious limitations. One is in particular when and of which type of drifts the distribution undergoes is unknown, and the other is that a simple synthesized dataset cannot reflect the complex representation we would normally face in the real world. For another, there lacks a well-defined protocol to evaluate a learner’s knowledge transfer capability on an incremental drift dataset. To provide a holistic discussion on these issues, we create approaches to generate datasets with specific drift types, and define a novel protocol for evaluation. Besides, we investigate recent advances in the transfer learning field, including Domain Adaptation and Lifelong Learning, and examine how they perform in the presence of incremental data drifting. The results unfold the relationships among drift types, knowledge preservation, and learning approaches.

Customs officials across the world encounter huge volumes of transactions. Associated with customs transactions is customs fraud-the intentional manipulation of goods declarations to avoid taxes and duties. Due to limited manpower, the customs offices can only manually inspect a small number of declarations, necessitating the automation of customs fraud detection by machine learning techniques. The limited availability of manually inspected ground truth data makes it essential for the ML approach to generalize well on unseen data. However, current customs fraud detection models are not well suited or designed for this setting. In this work, we propose GraphFC (Graph Neural networks for Customs Fraud), a model-agnostic, domain-specific, graph neural network based customs fraud detection model that is designed to work in a real-world setting with limited ground truth data. Extensive experimentation using real customs data from two countries demonstrates that GraphFC generalizes well over unseen data and outperforms various baselines and other models by a large margin.

Deep learning shows superiority in learning feature representations that offer promising performance in various application domains. Recent advances have shown that privacy attributes of users and patients (e.g., identity, gender, and race) can be accurately inferred from image data. To avoid the risk of privacy leaking, data owners can resort to releasing the embeddings rather than the original images. In this article, we aim at learning to generate privacy-preserving embeddings from image data. The obtained embeddings are required to maintain the data utility (e.g., keeping the performance of the main task, such as disease prediction) and to simultaneously prevent the private attributes of data instances from being accurately inferred. We also want the hard embeddings to be successfully used to reconstruct the original images. We propose a hybrid method based on multi-task learning to reach the goal. The key idea is twofold. One is to learn the feature encoder that can benefit the main task and fool the sensitive task at the same time via iterative training and feature disentanglement. The other is to incorporate the learning of adversarial examples to mislead the sensitive attribute classification’s performance. Experiments conducted on Multi-Attribute Facial Landmark (MAFL) and NIH Chest X-ray datasets exhibit the effectiveness of our hybrid method. A set of advanced studies also shows the usefulness of each model component, the difficulty in data reconstruction, and the performance impact of task correlation.

Nowadays, numerous AI systems employ deep neural network models with excessive number of parameters to obtain superior performance on real-world applications. Such systems relies on high-performance GPUs to achieve real-time inference, especially for the ones that involve convolutional operations. This prohibits the practical deployment on resourcescarce edge devices. To reduce model size and inference time, model pruning for deep neural network models has been an active thread of research in the recent years. Among a significant amount of literature towards different model pruning strategies, ℓ1regularization is commonly considered as a simple solution for sparse models. However, a fundamental issue is seldom addressed: "why ℓ1regularization can be effective for model pruning". In this work, we provide a theoretical explanation showing that, for a specific type of neural network models with ℓ1regularization, tasks of higher accuracy result in higher pruning ratio. Hence, network pruning could be exceptionally effective on high accuracy tasks. Based on the theoretical analysis, we demonstrate the effectiveness of ℓ1regularization learning on two iconic computer vision tasks: (a) face detection and (b) image segmentation. The experiment results show that, with suitable ℓ1-regularized optimizations, even for a compact model like MobileNetV2, the model size can be reduced by an order of magnitude without significant losses on the accuracy. Furthermore, we show that with proper implementation of sparse convolution, the obtained sparse neural network models can achieve multiple times speed-ups not only in FLOPs, but also in actual inference time.

Machine learning has been a rising technique in signatureless malware detection and is popular in the anti-virus industry. Despite the powerful ability of machine learning, it is known to be vulnerable to attack by injecting specially crafted input noise (adversarial example). In this paper, we develop a systematic attack method that is effective, general and also efficient which automatically generates functional malware. Experiment results showed that such adversarial malware could deceive commercial anti-virus and completely defeat learning-based malware detector provided by a well-known anti-virus vendor. We further examine the effectiveness of our approach on multiple anti-virus engines on VirusTotal and investigate the transferability of our proposed method between different features and classification algorithms. Finally, we show how our attack could resist JavaScript de-obfuscation techniques.

Demographic information is important for various commercial and academic proposes, but in reality, few of these data are accessible for analysis and research. To solve this problem, several studies predict demographic attributes from users’ behavioral data. However, previous works suffer from different kinds of disadvantages. Handling data sparseness and defining useful features remain especially challenge tasks. In this article, we propose a novel Deep Energy Factorization Model to address these two drawbacks. The model is a designed network that performs multi-label classification and feature representation. Experiments are conducted on four datasets with four evaluation metrics. The empirical results show that our Deep Energy Factorization Model significantly outperforms state-of-the-art models.

The railway is an indispensable means of transportation for people living in urban areas in Japan. However, unexpected accidents or disasters disturb the train operation. People usually check the operation status of trains on the official websites or Twitter of each railway company. However, it is still unclear whether such information is provided in realtime, when it is updated and which station is severely affected. Therefore, we tackle a real-world application of transportation big data using 8 months' data collected by smart cards for public transportation in Keikyu Line operating in Tokyo and Kanagawa Prefectures. We propose a method to detect the anomaly state by using the number of train users every 10 minutes in major 9 stations in Keikyu Line. In the method, outlier detections by interquartile range, interval estimation and Hotelling's theory are utilized to detect anomaly points. As the results, our proposal detects anomaly state better than the official announcement by Twitter on some points in terms of realtimeness, update frequency and geographic detail.

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

Excellent recommendation system facilitates users retrieving contents they like and, what»s much more important - the contents they might like but they are not aware of yet. It will further increase the satisfaction of users and increase the retention rate and conversion rate indirectly. While the public's now listening to all kinds of music, recommendation algorithms still struggle in key areas. Without enough historical data, how would an algorithm know if listeners will like a new song or a new artist? And, how would it know what songs to recommend brand new users? In WSDM Cup 2018, the first task is to solve the abovementioned challenges to build a better music recommendation system. The 2nd task in the Cup focuses on churn prediction. For a subscription business, accurately predicting churn is critical to long-term success. Even slight variations in churn can drastically affect profits. In this task, participants are asked to build an algorithm that predicts whether a user will churn after their subscription expires. The competition data and award are provided by KKBOX, a leading music streaming service in Taiwan.

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

Recommender systems have been studied for decades with numerous promising models been proposed. Among them, Collaborative Filtering (CF) models are arguably the most successful one due to its high accuracy in recommendation and elimination of privacy-concerned personal meta-data from training. This paper extends the usage of CF-based model to the task of course recommendation. We point out several challenges in applying the existing CF-models to build a course recommendation engine, including the lack of rating and meta-data, the imbalance of course registration distribution, and the demand of course dependency modeling. We then propose several ideas to address these challenges. Eventually, we combine a two-stage CF model regularized by course dependency with a graph-based recommender based on course-transition network, to achieve AUC as high as 0.97 with a real-world dataset.

Location tracking of passive RFID tags is useful for its ultra-low cost, but is very challenging for its passive nature. A passive RFID tag relies on no internal power source and draws power from the field created by the reader to power the microchip's circuits. This has made passive RFID tags highly sensitive to surrounding materials, as well as any disturbance. Therefore, conventional machine learning models may not perform well. In this paper, we propose an ensemble-based machine learning model, together with novel feature engineering techniques, for location tracking of passive RFID, which can work seamlessly with any supervised learning methods. The reader-based sub-models training method used in our model significantly reduces the training time by splitting our model into smaller sub-models and training them in parallel, which is desirable in real-world application.

PageRank has been the signature unsupervised ranking model for ranking node importance in a graph. One potential drawback of PageRank is that its computation depends only on input graph structures, not considering external information such as the attributes of nodes. This work proposes AttriRank, an unsupervised ranking model that considers not only graph structure but also the attributes of nodes. AttriRank is unsupervised and domain-independent, which is different from most of the existing works requiring either ground-truth labels or specific domain knowledge. Combining two reasonable assumptions about PageRank and node attributes, AttriRank transfers extra node information into a Markov chain model to obtain the ranking. We further develop approximation for AttriRank and reduce its complexity to be linear to the number of nodes or links in the graph, which makes it feasible for large network data. The experiments show that AttriRank outperforms competing models in diverse graph ranking applications.

Inspired by recent progress in parallel and distributed optimization, we propose parallel least-squares policy iteration (parallel LSPI) in this paper. LSPI is a policy iteration method to find an optimal policy for MDPs. As solving MDPs with large state space is challenging and time demanding, we propose a parallel variant of LSPI which is capable of leveraging multiple computational resources. Preliminary analysis of our proposed method shows that the sample complexity improved from O(1/√n) towards O(1/√Mn) for each worker, where n is the number of samples and M is the number of workers. Experiments show the advantages of parallel LSPI comparing to the standard non-parallel one.

This paper presents two strategies to speed up the alternating direction method of multipliers (ADMM) for distributed data. In the first method, inspired by stochastic gradient descent, each machine uses only a subset of its data at the first few iterations, speeding up those iterations. A key result is in proving that despite this approximation, our method enjoys the same convergence rate in terms of the number of iterations as the standard ADMM, and hence is faster overall. The second method also follows the idea of sampling a subset of the data to update the model before the communication of each round. It converts an objective to the approximated dual form and performs ADMM on the dual. The method turns out to be a distributed variant of the recently proposed SDCA-ADMM. Yet, compared to the straightforward distributed implementation of SDCA-ADMM, the proposed method enjoys less frequent communication between machines, better memory usage, and lighter computational demand. Experiments demonstrate the effectiveness of our two strategies.

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

Datasets gathered from sensor networks often suffer from a significant fraction of missing data, due to issues such as communication and sensor interference, power depletion, and hardware failure. Many standard data analysis tools such as classification engines, time-sequence pattern analysis modules, and statistical tools are ill-equipped to deal with missing values - hence, there is a vital need for highly-accurate techniques for imputing missing readings prior to analysis. This paper presents novel imputation methods that take a "recommendation systems" view of the problem: the sensors and their readings at each time step are viewed as products and user product ratings, with the goal of estimating the missing ratings. Sensor readings differ from product ratings, however, in that the former exhibit high correlation in both time and space. To incorporate this property, we modify the widely successful matrix factorization approach for recommendation systems to model inter-sensor and intra-sensor correlations and learn latent relationships among these dimensions. We evaluate the approach using two sensor network datasets, one indoor and one outdoor, and two imputation scenarios, corresponding to intermittent readings and failed sensors. Next, we consider sensor networks with multiple sensor types at each node. We present two techniques for extending our model to account for possible correlations among sensor types (e.g., temperature and humidity) with promising results. Finally, we study how the imputed values affect the result of data analysis. We consider a popular data analysis task - building regression-based prediction models - and show that, compared to prior approaches for imputation, our method leads to a much higher quality prediction model.

This paper proposes to study a novel problem, discovering a Smallest Unique Subgraph (SUS) for any node of interest specified by user in a heterogeneous social network. The rationale of the SUS problem lies in how a person is different from any others in a social network, and how to represent the identity of a person using her surrounding relational structure in a social network. To deal with the proposed SUS problem, we develop an Ego-Graph Heuristic (EGH) method to efficiently solve the SUS problem in an approximated manner. EGH intelligently examine whether one graph is not isomorphic to the other, instead of using the conventional subgraph isomorphism test. We also prove SUS is a NP-complete problem through doing a reduction from Minimum Vertex Cover (MVC) in a homogeneous tree structure. Experimental results conducted on a real-world movie heterogeneous social network data show both the promising efficiency and compactness of our method.

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

This paper emphasizes optimizing ranking measures in a recommendation problem. Since ranking measures are non-differentiable, previous works have been proposed to deal with this problem via approximations or lower/upper bounding of the loss. However, such mismatch between ranking measures and approximations/bounds can lead to non-optimal ranking results. To solve this problem, we propose to model the gradient of non-differentiable ranking measure based on the idea of virtual gradient, which is called lambda in learning to rank. In addition, noticing the difference between learning to rank and recommendation models, we prove that under certain circumstance the existence of popular items can lead to unlimited norm growing of the latent factors in a matrix factorization model. We further create a novel regularization term to remedy such concern. Finally, we demonstrate that our model, LambdaMF, outperforms several state-of-the-art methods. We further show in experiments that in all cases our model achieves global optimum of normalized discount cumulative gain during training. Detailed implementation and supplementary material can be found at (http://www.csie.ntu.edu.tw/~b00902055/).

This paper tries to answer two questions. First, how to infer real-time air quality of any arbitrary location given environmental data and historical air quality data from very sparse monitoring locations. Second, if one needs to establish few new monitoring stations to improve the inference quality, how to determine the best locations for such purpose? The problems are challenging since for most of the locations (>99%) in a city we do not have any air quality data to train a model from. We design a semi-supervised inference model utilizing existing monitoring data together with heterogeneous city dynamics, including meteorology, human mobility, structure of road networks, and point of interests (POIs). We also propose an entropy-minimization model to suggest the best locations to establish new monitoring stations. We evaluate the proposed approach using Beijing air quality data, resulting in clear advantages over a series of state-of-the-art and commonly used methods.

Considering nowadays companies providing similar products or services compete with each other for resources and customers, this work proposes a learning-based framework to tackle the multi-round competitive influence maximization problem on a social network. We propose a data-driven model leveraging the concept of meta-learning to maximize the expected influence in the long run. Our model considers not only the network information but also the opponent's strategy while making a decision. It maximizes the total influence in the end of the process instead of myopically pursuing short term gain. We propose solutions for scenarios when the opponent's strategy is known or unknown and available or unavailable for training. We also show how an effective framework can be trained without manually labeled data, and conduct several experiments to verify the effectiveness of the whole process.

This work tries to bring a marriage between two areas of computer science, social network analysis and machine learning, by exploiting ranking-based learning models for preference prediction on social networks. In the field of social network analysis, the diffusion of information on social networks has been studied for decades. This paper proposes the study of diffusion of preference on social networks. In general, there are two types of approaches proposed to predict the diffusion of information on a network, model-driven and data-driven approaches. The former assumes an underlying mechanism for diffusion while the latter tries to learn a more flexible model with the given data. This paper first proposes a simple modification on the existing model-driven binary diffusion approaches for preference list diffusion, and then addresses some concerns by proposing a rank-learning based data-driven approach. To evaluate the approaches, we propose two scenarios which data can be obtained from publicly available sources, namely predicting the preference propagation about the citation behavior and the microblogging behavior. The experiments show that the proposed ranking-based data-driven method outperforms all the other competitors significantly in both evaluation scenarios.

One of the main purposes of a computer-aided diagnosis (CAD) system is to reduce the workload of the radiologists in identifying potential diseases. However, such system can become unreliable and useless if it produces even only a small amount of false negatives, since a misclassification of any unhealthy patient as healthy can result in the delay of treatment, which can lead to fatal outcomes. Designing a CAD system that is capable of reducing the workload of radiologists and meanwhile avoiding any false negative is a very challenging problem. To tackle this problem, we propose a two-stage framework and a novel evaluation criterion, namely optimal specificity under perfect sensitivity (OSPS). We argue that for medical data classification, this criterion is more suitable than other conventional measures such as accuracy, f-score, or area-under-ROC curve. We further propose two learning strategies to improve OSPS. The first aims particularly at multi-instance learning tasks via disregarding the misclassified negative instances of positive patients. The second tries to improve OSPS by embedding more restricted constraints for negatives.

This paper considers the design of a reinforcement learning (RL) agent that can strike a balance between return and risk. First, we discuss several favorable properties of an RL risk model, and then propose a definition of risk based on expected negative rewards. We also design a Q-decomposition-based framework that allows a reinforcement learning agent to control the balance between risk and profit. The results of experiments on both artificial and real-world stock datasets demonstrate that the proposed risk model satisfies the beneficial properties of an RL-based risk learning model, and also significantly outperforms other approaches in terms of avoiding risks.

Multi-label classification (MLC) is a type of structured output prediction problems where a given instance can be associated to more than one labels at a time. From the probabilistic point of view, a model predicts a set of labels y given an input vector v by learning a conditional distribution p(y|v). This paper presents a powerful model called a Neural Conditional Energy Model (NCEM) to solve MLC. The model can be viewed as a hybrid deterministic-stochastic network of which we use a deterministic neural network to transform the input data, before contributing to the energy landscape of v, y, and a single stochastic hidden layer h. Non-linear transformation given by the neural network makes our model more expressive and more capable of capturing complex relations between input and output, and using deterministic neurons facilitates exact inference. We present an efficient learning algorithm that is simple to implement. We conduct extensive experiments on 15 real-world datasets from wide variety of domains with various evaluation metrics to confirm that NCEM is significantly superior to current state-of-the-art models most of the time based on pair-wise t-test at 5% significance level. The MATLAB source code to replicate our experiments are available at https://github.com/Kublai-Jing/NCEM.

Data Sparsity incurs serious concern in collaborative filtering (CF). This issue is especially critical for newly launched CF applications where observed ratings are too scarce to learn a good model to predict missing values. There could be, however, information from other related domains which are with relatively denser data that can be utilized. This paper proposes a transfer-learning based approach that exploits probabilistic matrix factorization model trained with variational expectation-maximization (VIM) to resolve data sparsity by using information from multiple auxiliary domains. We conduct experiments on several data combination and report significant improvements over state-of-the-art transfer-based models for collaborative filtering. The results also show that our framework is the only solution that can achieve acceptable performance when each user has only one single rating. The code of our model is available at https://github.com/Kublai-Jing/TIC https://github.com/Kublai-Jing/TIC.

Given two homogeneous rating matrices with some overlapped users/items whose mappings are unknown, this paper aims at answering two questions. First, can we identify the unknown mapping between the users and/or items? Second, can we further utilize the identified mappings to improve the quality of recommendation in either domain? Our solution integrates a latent space matching procedure and a refining process based on the optimization of prediction to identify the matching. Then, we further design a transfer-based method to improve the recommendation performance. Using both synthetic and real data, we have done extensive experiments given different real life scenarios to verify the effectiveness of our models. The code and other materials are available at http://www.csie.ntu.edu.tw/~r00922051/matching/

Location-based services allow users to perform geospatial recording actions, which facilitates the mining of the moving activities of human beings. This article proposes to recommend time-sensitive trip routes consisting of a sequence of locations with associated timestamps based on knowledge extracted from large-scale timestamped location sequence data (e.g., check-ins and GPS traces). We argue that a good route should consider (a) the popularity of places, (b) the visiting order of places, (c) the proper visiting time of each place, and (d) the proper transit time from one place to another. By devising a statistical model, we integrate these four factors into a route goodness function that aims to measure the quality of a route. Equipped with the route goodness, we recommend time-sensitive routes for two scenarios. The first is about constructing the route based on the user-specified source location with the starting time. The second is about composing the route between the specified source location and the destination location given a starting time. To handle these queries, we propose a search method, Guidance Search , which consists of a novel heuristic satisfaction function that guides the search toward the destination location and a backward checking mechanism to boost the effectiveness of the constructed route. Experiments on the Gowalla check-in datasets demonstrate the effectiveness of our model on detecting real routes and performing cloze test of routes, comparing with other baseline methods. We also develop a system TripRouter as a real-time demo platform.

Label powerset (LP) method is one category of multi-label learning algorithm. This paper presents a basis expansions model for multi-label classification, where a basis function is an LP classifier trained on a random k-labelset. The expansion coefficients are learned to minimize the global error between the prediction and the ground truth. We derive an analytic solution to learn the coefficients efficiently. We further extend this model to handle the cost-sensitive multi-label classification problem, and apply it in social tagging to handle the issue of the noisy training set by treating the tag counts as the misclassification costs. We have conducted experiments on several benchmark datasets and compared our method with other state-of-the-art multi-label learning methods. Experimental results on both multi-label classification and cost-sensitive social tagging demonstrate that our method has better performance than other methods.

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

Online social networks are mainly characterized by large-scale and heterogeneous semantic relationships. Unfortunately, for online social network services such as Facebook or Twitter, it is very difficult to obtain the fully observed network without privilege to access the data internally. To address the above needs, social network sampling is a means that aims at identifying a representative sub graph that preserves certain properties of the network, given the information of any instance in the network is unknown before being sampled. This study tackles heterogeneous network sampling by considering the conditional dependency of node types and link types, where we design a property, Relational Profile, to account such characterization. We further propose a sampling method to preserve this property. Lastly, we propose to evaluate our model from three different angles. First, we show that the proposed sampling method can more faithfully preserve the Relational Profile. Second, we evaluate the usefulness of the Relational Profile showing such information is beneficial for link prediction tasks. Finally, we evaluate whether the networks sampled by our method can be used to train more accurate prediction models comparing to networks produced by other methods.

The concern of privacy has become an important issue for online social networks. In services such as Foursquare.com, whether a person likes an article is considered private and therefore not disclosed; only the aggregative statistics of articles (i.e., how many people like this article) is revealed. This paper tries to answer a question: can we predict the opinion holder in a heterogeneous social network without any labeled data? This question can be generalized to a link prediction with aggregative statistics problem. This paper devises a novel unsupervised framework to solve this problem, including two main components: (1) a three-layer factor graph model and three types of potential functions; (2) a ranked-margin learning and inference algorithm. Finally, we evaluate our method on four diverse prediction scenarios using four datasets: preference (Foursquare), repost (Twitter), response (Plurk), and citation (DBLP). We further exploit nine unsupervised models to solve this problem as baselines. Our approach not only wins out in all scenarios, but on the average achieves 9.90% AUC and 12.59% NDCG improvement over the best competitors. The resources are available at http://www.csie.ntu.edu.tw/~d97944007/aggregative/

Linear Classification has achieved complexity linear to the data size. However, in many applications, data contain large amount of samples that does not help improve the quality of model, but still cost much I/O and memory to process. In this paper, we show how a Block Coordinate Descent method based on Nearest-Neighbor Index can significantly reduce such cost when learning a dual-sparse model. In particular, we employ truncated loss function to induce a series of convex programs with superior dual sparsity, and solve each dual using Indexed Block Coordinate Descent, which makes use of Approximate Nearest Neighbor (ANN) search to select active dual variables without I/O cost on irrelevant samples. We prove that, despite the bias and weak guarantee from ANN query, the proposed algorithm has global convergence to the solution defined on entire dataset, with sublinear complexity each iteration. Experiments in both sufficient and limited memory conditions show that the proposed approach learns many times faster than other state-of-the-art solvers without sacrificing accuracy.

Issues about information diffusion on social networks has been studied for decades. To simplify the analysis, most models consider the propagated information or media as single real values. Representing media as single values however would not suitable for certain situations such as the voter preference toward the candidates in an election. In such case, the representation would better be lists instead of single values as people sometimes can alter others’ preference through toward objects social inference. This paper studies the diffusion of preference on social networks, which is a novel problem to solve in this direction. First, we propose a preference propagation model that can handle the diffusion of vector-type information instead of only binary or numerical values. Furthermore, we theoretically prove the convergence of diffusion with the proposed model, and that a consensus among strongly connected nodes can eventually be reached with certain conditions. We further extract relevant information from a publicly available bibliography datasets to evaluate the proposed models, while such data can further serve as a benchmark for evaluating future models of the same purpose. Lastly, we exploit the extracted data to demonstrate the usefulness of our model and compare it with other well-known diffusion strategies such as independent cascade, linear threshold, and diffusion rank. We find that our model consistently outperforms other models.

The concept of random walk (RW) has been widely applied in the design of recommendation systems. RW-based approaches are effective in handling locality problem and taking extra information, such as the relationships between items or users, into consideration. However, the traditional RW-based approach has a serious limitation in handling bidirectional opinions. The propagation of positive and negative information simultaneously in a graph is nontrivial using random walk. To address the problem, this article presents a novel and efficient RW-based model that can handle both positive and negative comments with the guarantee of convergence. Furthermore, we argue that a good recommendation system should provide users not only a list of recommended items but also reasonable explanations for the decisions. Therefore, we propose a technique that generates explanations by backtracking the influential paths and subgraphs. The results of experiments on the MovieLens and Netflix datasets show that our model significantly outperforms state-of-the-art RW-based algorithms, and is capable of improving the overall performance in the ensemble with other models.

Graph mining is a popular technique for discovering the hidden structures or important instances in a graph, but the computational efficiency is usually a cause for concern when dealing with large-scale graphs containing billions of entities. Cloud computing is widely regarded as a feasible solution to the problem. In this work, we present an open source graph mining library called the MapReduce Graph Mining Framework (MGMF) to be a robust and efficient MapReduce-based graph mining tool. We start from dividing graph mining algorithms into four categories and designing a MapReduce framework for algorithms in each category. The experimental results show that MGMF is 3 to 20 times more efficient than PEGASUS, a state-of-the-art library for graph mining on MapReduce. Moreover, it provides better coverage of different graph mining algorithms. We also validate our framework on billion-scaled networks to demonstrate that it is scalable to the number of machines. Fur-thermore, we test and compare the feasibility between single ma-chine and the cloud computing technique. The effects of different file input formats for MapReduce are investigated as well. Our implemented open-source library can be downloaded from http://mslab.csie.ntu.edu.tw/~noahsark/MGMF/.

With the popularity of online social network services, influence maximization on social networks has drawn much attention in recent years. Most of these studies approximate a greedy based sub-optimal solution by proving the submodular nature of the utility function. Instead of using the analytical techniques, we are interested in solving the diffusion competition and influence maximization problem by a data-driven approach. We propose Information Propagation Game (IPG), a framework that can collect a large number of seed picking strategies for analysis. Through the IPG framework, human players are not only having fun but also helping contributing the seed picking strategies. Preliminary experiment suggests that centrality based heuristics are too simple for seed selection in a multiple player environment.

This paper demonstrates a system that exploits graph mining, social network analysis, and agent-based crowd simulation techniques to investigate the evacuation dynamics during fire emergency. We create a novel evacuation planning system, EvaPlanner, to deal with three tasks. First, the system identifies the preferable locations to establish the exits to facilitate efficient evacuation from the dangerous areas. Second, it determines the most effective positions to place the emergency signs such that panic crowd can quickly find the exits. Third, it faithfully simulates the evacuation dynamics of crowd considering not only the individual movement kinetics but also the social connections between people. EvaPlanner provides a flexible experimental platform for investigating the evacuation dynamics under a variety of settings, and can further be utilized for animation and movie production. In addition, it can serve as a tool to assist architects address the safety concern during the planning phase. The demo system can be found in the link: http://mslab.csie.ntu.edu.tw/evaplanner/

To model time-dependent user intent for Web search, this paper proposes a novel method using machine learning techniques to exploit temporal features for effective time-sensitive search result re-ranking. We propose models to incorporate users' click through information for queries that are seen in the training data, and then further extend the model to deal with unseen queries considering the relationship between queries. Experiment shows significant improvement on search result ranking over original search outputs.

Micro-blogging is a type of social networking service that has become ubiquitous in Web 2.0 era. Micro-blogs allows bloggers to exchange information, discuss ideas, and share experiences with friends or even strangers with similar interests. In this paper, we try to identify ways to measure how information is propagated in micro-blogs. More specifically, we consider the following issues. (1) How to quantify a person's capability to disseminate ideas via a micro-blog. (2) How to measure the extent of propagation of a concept in a micro-blog. (3) How to demonstrate and visualize information propagation in a micro-blog. We propose methods to effectively measure each user's ability to disseminate information via micro-blogs. The design of the measure considers three factors: (a) the number of people influenced, (b) the speed of propagation, and (c) the geographic distance of the propagation. We also provide an online demonstration micro-blog system that allows the users to explore the information propagation. The system shows the propagation paths and social graphs, influence scores, timelines, and geographical information among people for the user-given terms.

In online social networking services, there are a range of scenarios in which users want to search a particular person given the targeted person one's name. The challenge of such people search is namesake, which means that there are many people possess the same names in the social network. In this paper, we propose to leverage the query contexts to tackle such problems. For example, given the information of one's graduation year and city, the last names of some individuals, one may wish to find classmates from his/her high school. We formulate such problem as the context-based people search. Given a social network in which each node is associated with a set of labels and given a query set of labels consisting of a targeted name label and other context labels, our goal is to return a ranking list of persons who possess the targeted name label and connects to other context labels with minimum communication costs through an effective subgraph in the social network. We consider the interactions among query labels to propose a grouping-based method to solve the context-based people search. Our method consists of three major parts. First, we model those nodes with query labels into a group graph which is able to reduce the search space to enhance the time efficiency. Second, we identify three different kinds of connectors which connecting different groups, and exploit connectors to find the corresponding detailed graph topology from the group graph. Third, we propose a Connector-Steiner Tree algorithm to retrieve a resulting ranked list of individuals who possess the targeted label. Experimental results on the DBLP bibliography data show that our grouping-based method can reach the good quality of returned persons as a greedy search algorithm at a considerable outperformance on the time efficiency.

This work combines the central ideas from two different areas, crowd simulation and social network analysis, to tackle some existing problems in both areas from a new angle. We present a novel spatio-temporal social crowd simulation framework, Social Flocks, to revisit three essential research problems, (a) generation of social networks, (b) community detection in social networks, (c) modeling collective social behaviors in crowd simulation. Our framework produces social networks that satisfy the properties of high clustering coefficient, low average path length, and power-law degree distribution. It can also be exploited as a novel dynamic model for community detection. Finally our framework can be used to produce real-life collective social behaviors over crowds, including community-guided flocking, leader following, and spatio-social information propagation. Social Flocks can serve as visualization of simulated crowds for domain experts to explore the dynamic effects of the spatial, temporal, and social factors on social networks. In addition, it provides an experimental platform of collective social behaviors for social gaming and movie animations. Social Flocks demo is at http://mslab.csie.ntu.edu.tw/socialflocks/ .

Social networking services possess two features: (1) capturing the social relationships among people, represented by the social network, and (2) allowing users to express their preferences on different kinds of items (e.g. photo, celebrity, pages) through endorsing buttons, represented by a kind of endorsement bipartite graph. In this work, using such information, we propose a novel recommendation method, which leverages the viral marketing in the social network and the wisdom of crowds from endorsement network. Our recommendation consists of two parts. First, given some query terms describing user's preference, we find a set of targeted influencers who have the maximum activation probability on those nodes related to the query terms in the social network. Second, based on the derived targeted influencers as key experts, we recommend items via the endorsement network. We conduct the experiments on DBLP co-authorship social network with author-reference data as the endorsement network. The results show our method can achieve effective recommendations.

It is widely recognized that stakeholder information can provide important knowledge about stock investments, and an increasing number of countries require that such information is publicly available. In this paper, we present a novel way to exploit stakeholder information by using it to construct stake-based social networks, namely, StakeNet. We also provide a visualization tool that displays socio-centric and ego-centric views of the networks. In addition, we analyze stakeholders' static and dynamic behavior patterns in StakeNet, and demonstrate that most of StakeNet's properties are similar to those of a typical social network, except that the in-degree distribution does not follow a power law distribution. Finally, we demonstrate two applications of StakeNet by exploiting it to identify important companies and to group companies together. The experiments show that our results are highly consistent with the outcomes generated by human experts. Source code, dataset, and resources are available at http://www.csie.ntu.edu.tw/~d97944007/stakenet/.

The vertex-betweenness centrality index is an essential measurement for analyzing social networks, but the computation time is excessive. At present, the fastest algorithm, proposed by Brandes in 2001, requires O(|V| |E|) time, which is computationally intractable for real-world social networks that usually contain millions of nodes and edges. In this paper, we propose a fast and accurate algorithm for estimating vertex-betweenness centrality values for social networks. It only requires O(b2|V|) time, where b is the average degree in the network. Significantly, we demonstrate that the local dynamic information about the vertices is highly relevant to the global betweenness values. The experiment results show that the vertex-betweenness values estimated by the proposed model are close to the real values and their rank is fairly accurate. Furthermore, using data from online role-playing games, we present a new type of dynamic social network constructed from in-game chatting activity. Besides using such online game networks to evaluate our betweenness estimation model, we report several interesting findings derived from conducting static and dynamic social network analysis on game networks.

In an organization, based on the positions of employees there is usually an existing hierarchy among them. However, in real-life cases, people's interactions tend to form a certain communication structure due to some external forces or personal factors. In this paper, we aim at discovering the potential communication structure, in which nodes are typed labels (e.g. job-titles) and edges stand for tight interactions between typed labels in an organizational social network. To tackle this problem, we propose to exploit the concept of information asymmetry to model the core-periphery property in the communication structure. The proximity asymmetry is defined to realize the information asymmetry. We also devise two random-walk methods to calculate the proximity asymmetry between typed labels. The experiments conducted on the Enron email dataset shows that the proposed method outperforms some heuristic ones.

Micro-blogging services provide platforms for users to share their feelings and ideas on the go. Desiging to produce information stream in almost Micro-blogging services, although are capable of recording rich and diverse senses, still suffer from a drawback of not being able to provide deeper and summarized views. In this paper, we present a novel framework, Pusic, to musicalize micro-blogging messages for terms or users. Pusic can be used to (1) summarize users' messages into certain expression of emotions, (2) explore the emotions and senses and transform them into music, and (3) serve as a presentation of crowd net art. We generate the music from two aspects: emotion and harmony. The former is tackled by emotion detection from messages while the latter is estabilished by rule-based harmonic heuristics according to the detected emotions. Pusic has been announced online for people's experience and further investigation.

Social network is a powerful data structure that allows the depiction of relationship information between entities. However, real-world social networks are sometimes too complex for human to pursue further analysis. In this work, an unsupervised mechanism is proposed for egocentric information abstraction in heterogeneous social networks. To achieve this goal, we propose a vector space representation for heterogeneous social networks to identify linear combination of relations as features and compute statistical dependencies as feature values. Then we design several abstraction criteria to distill representative and important information to construct the abstracted graphs for visualization. The evaluations conducted on a real world movie dataset and an artificial crime dataset demonstrate that the abstractions can indeed retain important information and facilitate more accurate and efficient human analysis.

An important problem in the area of homeland security is to identify suspicious entities in large datasets. Although there are methods from knowledge discovery and data mining (KDD) focusing on finding anomalies in numerical datasets, there has been little work aimed at discovering suspicious instances in large and complex semantic graphs whose nodes are richly connected with many different types of links. In this paper, we describe a novel, domain independent and unsupervised framework to identify such instances. Besides discovering suspicious instances, we believe that to complete the process, a system has to convince the users by providing understandable explanations for its findings. Therefore, in the second part of the paper we describe several explanation mechanisms to automatically generate human understandable explanations for the discovered results. To evaluate our discovery and explanation systems, we perform experiments on several different semantic graphs. The results show that our discovery system outperforms the state-of-the-art unsupervised network algorithms used to analyze the 9/11 terrorist network by a large margin. Additionally, the human study we conducted demonstrates that our explanation system, which provides natural language explanations for its findings, allowed human subjects to perform complex data analysis in a much more efficient and accurate manner.

A significant portion of knowledge discovery and data mining research focuses on finding patterns of interest in data. Once a pattern is found, it can be used to recognize satisfying instances. The new area of link discovery requires a complementary approach, since patterns of interest might not yet be known or might have too few examples to be learnable. We present an unsupervised link discovery method aimed at discovering unusual, interestingly linked entities in multi-relational datasets. Various notions of rarity are introduced to measure the "interestingness" of sets of paths and entities. These measurements have been implemented and applied to a real-world bibliographic dataset where they give very promising results.

With the rapid growth of the World Wide Web, more and more people rely on the online services to acquire and integrate information. However, it is time consuming to find the online services that are perfectly suited for a given task. First, the users might not have enough information to fill in the required input fields for querying an online service. Second, the online service might generate only partial information. Third, the user might only find the inverse version of the desired service. We propose a framework to develop flexible Web agents that handle these imperfect situations. In this framework we exploit a search engine as a general information discovery tool to assist finding and pruning information. To demonstrate this framework, we implemented two Web agents: the Internet inverse geocoder and the address lookup module.