Pei-Fu Guo, Yun-Da Tsai, Chun-Chia Hsu, Kai-Xin Chen, Ya An Tsai, Kai-Wei Chang, Nanyun Peng, Mi-Yen Yeh, Shou-De Lin. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

Converting different modalities into generalized text, which then serves as input prompts for large language models (LLMs), is a common approach for aligning multimodal models, particularly when pairwise data is limited. Text-centric alignment method leverages the unique properties of text as a modality space, transforming diverse inputs into a unified textual representation, thereby enabling downstream models to effectively interpret various modal inputs. This study evaluates the quality and robustness of multimodal representations in the face of noise imperfections, dynamic input order permutations, and missing modalities, revealing that current text-centric alignment methods can compromise downstream robustness. To address this issue, we propose a new text-centric adversarial training approach that significantly enhances robustness compared to traditional robust training methods and pre-trained multimodal foundation models. Our findings underscore the potential of this approach to improve the robustness and adaptability of multimodal representations, offering a promising solution for dynamic and real-world applications.

The task of retrieving known Advanced Persistent Threat (APT) campaigns from system activity graphs, where nodes represent MITRE ATT&CK techniques and edges encode temporal or resource-level relationships, requires reasoning over structures. In operational settings, these target graphs are often noisy due to incomplete detection, technique misclassification, and benign-induced structural artifacts. To address this issue, we formulate the task as approximate subgraph matching between a known APT query graph and a noisy, partially observed technique graph. In this poster, we introduce a preliminary embedding-based retrieval method, aiming to promote it as a robust and practical framework for retrieving known APTs in real-world environments.

Ko-Wei Huang, Yi-Fu Fu, Ching-Yu Tsai, Yu-Chieh Tu, Tzu-ling Cheng, Cheng-Yu Lin, Yi-Ting Yang, Heng-Yi Liu, Keng-Te Liao, Da-Cheng Juan, Shou-De Lin. Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing. 2025.

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.

This paper reveals a data bias issue that can profoundly hinder the performance of machine learning models in malicious URL detection. We describe how such bias can be diagnosed using interpretable machine learning techniques and further argue that such biases naturally exist in the real world security data for training a classification model. To counteract these challenges, we propose a debiased training strategy that can be applied to most deep-learning based models to alleviate the negative effects of the biased features. The solution is based on the technique of adversarial training to train deep neural networks learning invariant embedding from biased data. Through extensive experimentation, we substantiate that our innovative strategy fosters superior generalization capabilities across both CNN-based and RNN-based detection models. The findings presented in this work not only expose a latent issue in the field but also provide an actionable remedy, marking a significant step forward in the pursuit of more reliable and robust malicious URL detection.

This study investigates the privacy risks associated with text embeddings, focusing on the scenario where attackers cannot access the original embedding model.Contrary to previous research requiring direct model access, we explore a more realistic threat model by developing a transfer attack method.This approach uses a surrogate model to mimic the victim model's behavior, allowing the attacker to infer sensitive information from text embeddings without direct access.Our experiments across various embedding models and a clinical dataset demonstrate that our transfer attack significantly outperforms traditional methods, revealing the potential privacy vulnerabilities in embedding technologies and emphasizing the need for enhanced security measures.

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.

Neural networks are often trained with empirical risk minimization; however, it has been shown that a shift between training and testing distributions can cause unpredictable performance degradation. On this issue, a research direction, invariant learning, has been proposed to extract causal features insensitive to the distributional changes. This work proposes EDNIL, an invariant learning framework containing a multi-head neural network to absorb data biases. We show that this framework does not require prior knowledge about environments or strong assumptions about the pre-trained model. We also reveal that the proposed algorithm has theoretical connections to recent studies discussing properties of variant and invariant features. Finally, we demonstrate that models trained with EDNIL are empirically more robust against distributional shifts.

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.

Chinese NLP applications that rely on large text often contain huge amounts of vocabulary which are sparse in corpus.We show that characters' written form, Glyphs, in ideographic languages could carry rich semantics.We present a multi-modal model, Glyph2Vec, to tackle Chinese out-of-vocabulary word embedding problem.Glyph2Vec extracts visual features from word glyphs to expand current word embedding space for out-of-vocabulary word embedding, without the need of accessing any corpus, which is useful for improving Chinese NLP systems, especially for lowresource scenarios.Experiments across different applications show the significant effectiveness of our model.

We focus on a recently deployed system built for summarizing academic articles by concept tagging. The system has shown great coverage and high accuracy of concept identification which could be contributed by the knowledge acquired from millions of publications. Provided with the interpretable concepts and knowledge encoded in a pre-trained neural model, we investigate whether the tagged concepts can be applied to a broader class of applications. We propose transforming the tagged concepts into sparse vectors as representations of academic documents. The effectiveness of the representations is analyzed theoretically by a proposed framework. We also empirically show that the representations can have advantages on academic topic discovery and paper recommendation. On these applications, we reveal that the knowledge encoded in the tagging system can be effectively utilized and can help infer additional features from data with limited information.

In recent years, deep learning has made dramatic advances in computer vision field, especially in improving the performance of object detection as well as instance semantic segmentation. Still, multi-object tracking (MOT) remains a very challenging issue. Even in state-of-the-art deep learning-based object detectors, a preferred paradigm for MOT: tracking-by-detection, can only slightly improve the tracking performance. Pixel-level information is considered more precise and useful for tracking performance improvement than using conventional information, such as foreground or background content in a bounding box. However, the performance of current state-of-the-art models for automatically annotating pixel-level information is still far from the expectation of human beings. Therefore, we shall explore how multi-object tracking and segmentation (MOTS) is affected when the information obtained after applying instance semantic segmentation is incomplete. We propose a mask-guided two-streamed augmentation learning (MGTSAL) algorithm, which can be applied to TrackR-CNN to alleviate significant drop of MOTS performance when encountering incompletely segmented information. We evaluate the proposed approach on MOTS KITTI dataset, and our approach outperforms the baseline model TrackR-CNN in all our experimental settings. The promising experimental results and ablation study validate the effectiveness of the proposed approach.

We study the problem of online linear optimization with sparsity constraints in the semi-bandit setting. It can be seen as a marriage between two well-known problems: the online linear optimization problem and the combinatorial bandit problem. For this problem, we provide an algorithm which is efficient and achieves a sublinear regret bound. Moreover, we extend our results to two generalized settings, one with delayed feedbacks and one with costs for receiving feedbacks. Finally, we conduct experiments which show the effectiveness of our methods in practice.

For multi-target multi-camera recognition tasks, tracking of objects of interest is one of the essential yet challenging issues due to the fact that the task requires re-identifying identical targets across distinct views. Multi-target multi-camera tracking (MTMCT) applications span a wide range of variety (e.g. crowd behavior analysis, anomaly individual tracking and sport player tracking), so how to make the system perform real-time tracking becomes a crucial research issue. In this paper, we propose an online hierarchical algorithm for extreme clustering based MTMCT framework. The system can automatically create a dynamic gallery with real-time fashion by collecting appearance information of multi-object tracking in single-camera view. We evaluate the effectiveness and efficiency of our framework, and compare the state-of-the-art methods on MOT16 as well as DukeMTMC for single and multiple camera tracking. The high-frame-rate performance and promising tracking results confirm our system can be used in realworld applications.

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.

Chih-Te Lai, Yi-Te Hong, Hong-You Chen, Chi-Jen Lu, Shou-De Lin. Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019.

Adversarial loss in a conditional generative adversarial network (GAN) is not designed to directly optimize evaluation metrics of a target task, and thus, may not always guide the generator in a GAN to generate data with improved metric scores. To overcome this issue, we propose a novel MetricGAN approach with an aim to optimize the generator with respect to one or multiple evaluation metrics. Moreover, based on MetricGAN, the metric scores of the generated data can also be arbitrarily specified by users. We tested the proposed MetricGAN on a speech enhancement task, which is particularly suitable to verify the proposed approach because there are multiple metrics measuring different aspects of speech signals. Moreover, these metrics are generally complex and could not be fully optimized by Lp or conventional adversarial losses.

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.

This paper proposes a low-cost, easily realizable strategy to equip a reinforcement learning (RL) agent the capability of behaving ethically. Our model allows the designers of RL agents to solely focus on the task to achieve, without having to worry about the implementation of multiple trivial ethical patterns to follow. Based on the assumption that the majority of human behavior, regardless which goals they are achieving, is ethical, our design integrates human policy with the RL policy to achieve the target objective with less chance of violating the ethical code that human beings normally obey.

This paper intends to address an issue in RL that when agents possessing varying capabilities, most resources may be acquired by stronger agents, leaving the weaker ones "starving". We introduce a simple method to train non-greedy agents in multi-agent reinforcement learning scenarios with nearly no extra cost. Our model can achieve the following goals in designing the non-greedy agent:non-homogeneous equality, only need local information, cost-effective, generalizable and configurable. We propose the idea of diminishing reward that makes the agent feel less satisfied for consecutive rewards obtained. This idea allows the agents to behave less greedy with-out the need to explicitly coding any ethical pattern nor monitor other agents' status. Given our framework, resources distributed more equally without running the risk of reaching homogeneous equality. We designed two games, Gathering Game and Hunter Prey to evaluate the quality of the model.

Lexicon relation extraction given distributional representation of words is an important topic in NLP.We observe that the state-of-theart projection-based methods cannot be generalized to handle unseen hypernyms.We propose to analyze it in the perspective of pollution, that is, the predicted hypernyms are limited to those appeared in training set.We propose a word relation autoencoder (WRAE) model to address the challenge and construct the corresponding indicator to measure the pollution.Experiments on several hypernymlike lexicon datasets show that our model outperforms the competitors significantly.

Translating video to language is very challenging due to diversified video contents originated from multiple activities and complicated integration of spatio-temporal information. There are two urgent issues associated with the video-to-language translation problem. First, how to transfer knowledge learned from a more general dataset to a specific application domain dataset? Second, how to generate stable video captioning (or description) results under different sampling rates? In this paper, we propose a novel temporal embedding method to better retain temporal representation under different video sampling rates. We present a transfer learning method that combines a stacked LSTM encoder-decoder structure and a temporal embedding learning with soft-attention (TELSA) mechanism. We evaluate the proposed approach on two public datasets, including MSR-VTT and MSVD. The promising experimental results confirm the effectiveness of the proposed approach.

We consider a generalization of mixed regression where the response is an additive combination of several mixture components. Standard mixed regression is a special case where each response is generated from exactly one component. Typical approaches to the mixture regression problem employ local search methods such as Expectation Maximization (EM) that are prone to spurious local optima. On the other hand, a number of recent theoretically-motivated \emph{Tensor-based methods} either have high sample complexity, or require the knowledge of the input distribution, which is not available in most of practical situations. In this work, we study a novel convex estimator \emph{MixLasso} for the estimation of generalized mixed regression, based on an atomic norm specifically constructed to regularize the number of mixture components. Our algorithm gives a risk bound that trades off between prediction accuracy and model sparsity without imposing stringent assumptions on the input/output distribution, and can be easily adapted to the case of non-linear functions. In our numerical experiments on mixtures of linear as well as nonlinear regressions, the proposed method yields high-quality solutions in a wider range of settings than existing approaches.

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.

Scientific studies from anthropologists, biologists, and sociologists hypothesized people who live in the geo neighborhood have more chances to contact with each other and construct the social relationships. This paper exploits a simulation-based approach to verify such hypothesis through unveiling the connection between the spatial-temporal movements of people and their social relationships. Based on the crowd simulation technique, we design an agent-based framework, social flocks, to model the geo spatial correlation of social elements. We simulate the movements of people to tackle two tasks, social network generation and network community detection. By mapping nodes in the network into agents in the simulation, we examine whether the social networks generated by our model can satisfy the network properties, such as high clustering coefficient, low average path length, and power-law degree distribution. Besides, given a social network, we simulate the social moving behaviors of agents/nodes to study the formation of communities. Experiments conducted for such two tasks verify the proposed hypotheses. Social flocks can also serve as a visualization platform for experts to explore the effects over the spatial, temporal, and social contexts. Through demonstrating how the simulation models are exploited to address social network problems, this paper encourages more studies on this direction.

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.

The latent feature model (LFM), proposed in (Griffiths \& Ghahramani, 2005), but possibly with earlier origins, is a generalization of a mixture model, where each instance is generated not from a single latent class but from a combination of latent features. Thus, each instance has an associated latent binary feature incidence vector indicating the presence or absence of a feature. Due to its combinatorial nature, inference of LFMs is considerably intractable, and accordingly, most of the attention has focused on nonparametric LFMs, with priors such as the Indian Buffet Process (IBP) on infinite binary matrices. Recent efforts to tackle this complexity either still have computational complexity that is exponential, or sample complexity that is high-order polynomial w.r.t. the number of latent features. In this paper, we address this outstanding problem of tractable estimation of LFMs via a novel atomic-norm regularization, which gives an algorithm with polynomial run-time and sample complexity without impractical assumptions on the data distribution.

We investigate an unsupervised generative approach for network embedding. A multi-task Siamese neural network structure is formulated to connect embedding vectors and our objective to preserve the global node ranking and local proximity of nodes. We provide deeper analysis to connect the proposed proximity objective to link prediction and community detection in the network. We show our model can satisfy the following design properties: scalability, asymmetry, unity and simplicity. Experiment results not only verify the above design properties but also demonstrate the superior performance in learning-to-rank, classification, regression, and link prediction tasks.

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.

In this work, we investigate the possibility of cross-website transfer learning for tackling the cold-start problem.To address the coldstart issues commonly present in a collaborative ltering (CF) system, most existing crossdomain CF models require auxiliary rating data from another domain; nevertheless, under the cross-website scenario, such data is often unobtainable.Therefore, we propose the nearest-neighbor transfer matrix factorization (NT-MF) model, where a topic model is applied to the unstructured user-generated content in the source domain, and the similarity between users in the latent topic space is utilized to guide the target-domain CF model.Specically, the latent factors of the nearestneighbors are regarded as a set of pseudo observations, which can be used to estimate the unknown parameters in the model.Improvement over previous methods, especially for the cold-start users, is demonstrated with experiments on a real-world cross-website dataset.1

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.

In past few years, several techniques have been proposed for training of linear Support Vector Machine (SVM) in limited-memory setting, where a dual block-coordinate descent (dual-BCD) method was used to balance cost spent on I/O and computation. In this paper, we consider the more general setting of regularized \emph{Empirical Risk Minimization (ERM)} when data cannot fit into memory. In particular, we generalize the existing block minimization framework based on strong duality and \emph{Augmented Lagrangian} technique to achieve global convergence for ERM with arbitrary convex loss function and regularizer. The block minimization framework is flexible in the sense that, given a solver working under sufficient memory, one can integrate it with the framework to obtain a solver globally convergent under limited-memory condition. We conduct experiments on L1-regularized classification and regression problems to corroborate our convergence theory and compare the proposed framework to algorithms adopted from online and distributed settings, which shows superiority of the proposed approach on data of size ten times larger than the memory capacity.

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.

This paper proposes a robust method to estimate the inverse covariance under noisy measurements. The method is based on the estimation of each column in the inverse covariance matrix independently via robust regression, which enables parallelization. Different from previous linear programming based methods that cannot guarantee a positive semi-definite covariance matrix, our method adjusts the learned matrix to satisfy this condition, which further facilitates the tasks of forecasting future values. Experiments on time series prediction and classification under noisy condition demonstrate the effectiveness of the approach.

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/

Video sensors are widely used in many applications such as security monitoring and home care. However, the growth of the number of sensors makes it impractical to stream all videos back to a central server for further processing, due to communication bandwidth and server storage constraints. Multi-view video summarization allows us to discard redundant data in the video streams taken by a group of sensors. All prior multi-view summarization methods, however, process video data in an off-line and centralized manner, which means that all videos are still required to be streamed back to the server before conducting the summarization. This paper proposes an on-line, distributed multi-view summarization system, which integrates the ideas of Maximal Marginal Relevance (MMR) and MS-Wave, a bandwidth-efficient distributed algorithm for finding k-nearest-neighbors and k-farthest-neighbors. Empirical studies show that our proposed system can discard redundant videos and keep important keyframes as effectively as centralized approaches, while transmitting only 1/6 to 1/3 as much data.

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/.

Label powerset (LP) method is one category of multi-label learning algorithms. It reduces the multi-label classification problem to a multi-class classification problem by treating each distinct combination of labels in the training set as a different class. This paper proposes a basis expansion model for multi-label classification, where a basis function is a LP classifier trained on a random k-labelset. The expansion coefficients are learned to minimize the global error between the prediction and the multi-label ground truth. We derive an analytic solution to learn the coefficients efficiently. We have conducted experiments using several benchmark datasets and compared our method with other state-of-the-art multi-label learning methods. The results show that our method has better or competitive performance against other methods.

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.

Audio tags correspond to keywords that people use to de scribe different aspects of a music clip, such as the genre, mood, and instrumentation. Since social tags are usually as signed by people with different levels of musical knowledge, they inevitably contain noisy information. By treating the tag counts as costs, we can model the audio tagging problem as a cost-sensitive classification problem. In addition, tag correlation is another useful information for automatic audio tagging since some tags often co-occur. By considering the co-occurrences of tags, we can model the audio tagging problem as a multi-label classification problem. To exploit the tag count and correlation information jointly, we formulate the audio tagging task as a novel cost-sensitive multi-label (CSML) learning problem. The results of audio tag annotation and retrieval experiments demonstrate that the new approach outperforms our MIREX 2009 winning method.

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/ .

This paper proposes an audiovisual presentation system, called PhotoFeel, to not only give users pleasant browsing atmosphere but also deliver a quick sense conveyed by given photo collection. While conventional photo display systems aim at improving the styles of presentation, we explore the visual and semantic feelings to create a space exhibiting the feelings from photographers. This is achieved by simulating the interactions among photos to emerge some flocking behaviors, where each photo is regarded as a simulated agent. To present the feelings of photos on the flocking, we construct two graphs by investigating the visual contents and tag semantics respectively. In addition, to enhance the diverse feelings of a photo collection, three audiovisual effects are composed to have rich presentation of feelings. Experimental results show that our PhotoFeel truly exhibits potential feelings for given photos and people comparatively favor our system.

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.

Audio tags correspond to keywords that people use to describe different aspects of a music clip. With the explosive growth of digital music available on the Web, automatic audio tagging, which can be used to annotate unknown music or retrieve desirable music, is becoming increasingly important. This can be achieved by training a binary classifier for each tag based on the labeled music data. Our method that won the MIREX 2009 audio tagging competition is one of this kind of methods. However, since social tags are usually assigned by people with different levels of musical knowledge, they inevitably contain noisy information. By treating the tag counts as costs, we can model the audio tagging problem as a cost-sensitive classification problem. In addition, tag correlation information is useful for automatic audio tagging since some tags often co-occur. By considering the co-occurrences of tags, we can model the audio tagging problem as a multi-label classification problem. To exploit the tag count and correlation information jointly, we formulate the audio tagging task as a novel cost-sensitive multi-label (CSML) learning problem and propose two solutions to solve it. The experimental results demonstrate that the new approach outperforms our MIREX 2009 winning method.

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.