Database Systems for Advanced Applications

Table of Contents

1. Frontmatter

2. Network Embedding

   1. Frontmatter

   2. Enhancing Network Embedding with Auxiliary Information: An Explicit Matrix Factorization Perspective

      Junliang Guo, Linli Xu, Xunpeng Huang, Enhong Chen

      Abstract

      Recent advances in the field of network embedding have shown the low-dimensional network representation is playing a critical role in network analysis. However, most of the existing principles of network embedding do not incorporate auxiliary information such as content and labels of nodes flexibly. In this paper, we take a matrix factorization perspective of network embedding, and incorporate structure, content and label information of the network simultaneously. For structure, we validate that the matrix we construct preserves high-order proximities of the network. Label information can be further integrated into the matrix via the process of random walk sampling to enhance the quality of embedding in an unsupervised manner, i.e., without leveraging downstream classifiers. In addition, we generalize the Skip-Gram Negative Sampling model to integrate the content of the network in a matrix factorization framework. As a consequence, network embedding can be learned in a unified framework integrating network structure and node content as well as label information simultaneously. We demonstrate the efficacy of the proposed model with the tasks of semi-supervised node classification and link prediction on a variety of real-world benchmark network datasets.

   3. Attributed Network Embedding with Micro-meso Structure

      Juan-Hui Li, Chang-Dong Wang, Ling Huang, Dong Huang, Jian-Huang Lai, Pei Chen

      Abstract

      Recently, network embedding has received a large amount of attention in network analysis. Although some network embedding methods have been developed from different perspectives, on one hand, most of the existing methods only focus on leveraging the plain network structure, ignoring the abundant attribute information of nodes. On the other hand, for some methods integrating the attribute information, only the lower-order proximities (e.g. microscopic proximity structure) are taken into account, which may suffer if there exists the sparsity issue and the attribute information is noisy. To overcome this problem, the attribute information and mesoscopic community structure are utilized. In this paper, we propose a novel network embedding method termed Attributed Network Embedding with Micro-Meso structure (ANEM), which is capable of preserving both the attribute information and the structural information including the microscopic proximity structure and mesoscopic community structure. In particular, both the microscopic proximity structure and node attributes are factorized by Nonnegative Matrix Factorization (NMF), from which the low-dimensional node representations can be obtained. For the mesoscopic community structure, a community membership strength matrix is inferred by a generative model from the linkage structure, which is then factorized by NMF to obtain the low-dimensional node representations. The three components are jointly correlated by the low-dimensional node representations, from which an objective function can be defined. An efficient alternating optimization scheme is proposed to solve the optimization problem. Extensive experiments have been conducted to confirm the superior performance of the proposed model over the state-of-the-art network embedding methods.

   4. An Efficient Exact Nearest Neighbor Search by Compounded Embedding

      Mingjie Li, Ying Zhang, Yifang Sun, Wei Wang, Ivor W. Tsang, Xuemin Lin

      Abstract

      Nearest neighbor search (NNS) in high dimensional space is a fundamental and essential operation in applications from many domains, such as machine learning, databases, multimedia and computer vision. In this paper, we first propose a novel and effective distance lower bound computation technique for Euclidean distance by using the combination of linear and non-linear embedding methods. As such, each point in a high dimensional space can be embedded into a low dimensional space such that the distance between two embedded points lower bounds their distance in the original space. Following the filter-and-verify paradigm, we develop an efficient exact NNS algorithm by pruning candidates using the new lower bounding technique and hence reducing the cost of expensive distance computation in high dimensional space. Our comprehensive experiments on 10 real-life and diverse datasets, including image, video, audio and text data, demonstrate that our new algorithm can significantly outperform the state-of-the-art exact NNS techniques.

   5. BASSI: Balance and Status Combined Signed Network Embedding

      Yiqi Chen, Tieyun Qian, Ming Zhong, Xuhui Li

      Abstract

      Signed social networks have both positive and negative links which convey rich information such as trust or distrust, like or dislike. However, existing network embedding methods mostly focus on unsigned networks and ignore the negative interactions between users. In this paper, we investigate the problem of learning representations for signed networks and present a novel deep network structure to incorporate both the balance and status theory in signed networks. With the proposed framework, we can simultaneously learn the node embedding encoding the status of a node and the edge embedding denoting the sign of an edge. Furthermore, the learnt node and edge embeddings can be directly applied to the sign prediction and node ranking tasks. Experiments on real-world social networks demonstrate that our model significantly outperforms the state-of-the-art baselines.

3. Recommendation

   1. Frontmatter

   2. Geographical Relevance Model for Long Tail Point-of-Interest Recommendation

      Wei Liu, Zhi-Jie Wang, Bin Yao, Mengdie Nie, Jing Wang, Rui Mao, Jian Yin

      Abstract

      Point-of-Interest (POI) recommendation plays a key role in people’s daily life, and has been widely studied in recent years, due to its increasingly applications (e.g., recommending new restaurants for users). One of important phenomena in the POI recommendation community is the data sparsity, which makes deep impact on the quality of recommendation. Existing works have proposed various models to alleviate the bottleneck of the data sparsity, and most of these works addressed this issue from the user perspective. To the best of our knowledge, few attention has been made to address this issue from the POI perspective. In this paper, we observe that the “long tail” POIs, which have few check-ins and have less opportunity to be exposed, take up a great proportion among all the POIs. It is interesting and meaningful to investigate the long tail POI recommendation from the POI perspective. To this end, this paper proposes a new model, named GRM (geographical relevance model), that expands POI profiles via relevant POIs and employs the geographical information, addressing the limitations of existing models. Experimental results based on two public datasets demonstrate that our model is effective and competitive. It outperforms state-of-the-art models for the long tail POI recommendation problem.

   3. Exploiting Context Graph Attention for POI Recommendation in Location-Based Social Networks

      Siyuan Zhang, Hong Cheng

      Abstract

      The prevalence of mobile devices and the increasing popularity of location-based social networks (LBSNs) generate a large volume of user mobility data. As a result, POI recommendation systems, which play a vital role in connecting users and POIs, have received extensive attention from both research and industry communities in the past few years. The challenges of POI recommendation come from the very sparse user check-in records with only positive feedback and how to integrate heterogeneous information of users and POIs. The state-of-the-art methods usually exploit the social influence from friends and geographical influence from neighboring POIs for recommendation. However, there are two drawbacks that hinder their performance. First, they cannot model the different degree of influence from different friends to a user. Second, they ignore the user check-ins as context information for preference modeling in the collaborative filtering framework.

      To address the limitations of existing methods, we propose a Context Graph Attention (CGA) model, which can integrate context information encoded in different context graphs with the attention mechanism for POI recommendation. CGA first uses two context-aware attention networks to learn the influence weights of different friends and neighboring POIs respectively. At the same time, it applies a dual attention network, which considers the mutual influence of context POIs for a user and the context users for a POI, to learn the influence weights of different context vertices in the user-POI context graph. A multi-layer perceptron integrates the context vectors of users and POIs for estimating the visiting probability of a user to a POI. To the best of our knowledge, this is the first work that applies the attention mechanism for POI recommendation. Extensive experiments on two public check-in data sets show that CGA can outperform the state-of-the-art methods as well as other attentive collaborative filtering methods substantially.

   4. Restricted Boltzmann Machine Based Active Learning for Sparse Recommendation

      Weiqing Wang, Hongzhi Yin, Zi Huang, Xiaoshuai Sun, Nguyen Quoc Viet Hung

      Abstract

      In recommender systems, users’ preferences are expressed as ratings (either explicit or implicit) for items. In general, more ratings associated with users or items are elicited, more effective the recommendations are. However, almost all user rating datasets are sparse in the real-world applications. To acquire more ratings, the active learning based methods have been used to selectively choose the items (called interview items) to ask users for rating, inspired by that the usefulness of each rating may vary significantly, i.e., different ratings may bring a different amount of information about the user’s tastes. Nevertheless, existing active learning based methods, including both static methods and decision-tree based methods, encounter the following limitations. First, the interview item set is predefined in the static methods, and they do not consider the user’s responses when asking the next question in the interview process. Second, the interview item set in the decision tree based methods is very small (i.e., usually less than 50 items), which leads to that the interview items cannot fully reflect or capture the diverse user interests, and most items do not have the opportunity to obtain additional ratings. Moreover, these decision tree based methods tend to choose popular items as the interview items instead of items with sparse ratings (i.e., sparse items), resulting in “Harry Potter Effect” (http://bickson.blogspot.com.au/2012/09/harry-potter-effect-on-recommendations.html). To address these limitations, we propose a new active learning framework based on RBM (Restricted Boltzmann Machines) to add ratings for sparse recommendation in this paper. The superiority of this method is demonstrated on two publicly available real-life datasets.

   5. Discrete Binary Hashing Towards Efficient Fashion Recommendation

      Luyao Liu, Xingzhong Du, Lei Zhu, Fumin Shen, Zi Huang

      Abstract

      How to match clothing well is always a troublesome problem in our daily life, especially when we are shopping online to select a pair of matched pieces of clothing from tens of thousands available selections. To help common customers overcome selection difficulties, recent studies in the recommender system area have started to infer the fashion matching results automatically. The conventional fashion recommendation is normally achieved by considering visual similarity of clothing items or/and item co-purchase history from existing shopping transactions. Due to the high complexity of visual features and the lack of historical item purchase records, most of the existing work is unlikely to make an efficient and accurate recommendation. To address the problem, in this paper we propose a new model called Discrete Supervised Fashion Coordinates Hashing (DSFCH). Its main objective is to learn meaningful yet compact high level features of clothing items, which are represented as binary hash codes. In detail, this learning process is supervised by a clothing matching matrix, which is initially constructed based on limited known matching pairs and subsequently on the self-augmented ones. The proposed model jointly learns the intrinsic matching patterns from the matching matrix and the binary representations from the clothing items’ images, where the visual feature of each clothing item is discretized into a fixed-length binary vector. The binary representation learning significantly reduces the memory cost and accelerates the recommendation speed. The experiments compared with several state-of-the-art approaches have evidenced the superior performance of the proposed approach on efficient fashion recommendation.

   6. Learning Dual Preferences with Non-negative Matrix Tri-Factorization for Top-N Recommender System

      Xiangsheng Li, Yanghui Rao, Haoran Xie, Yufu Chen, Raymond Y. K. Lau, Fu Lee Wang, Jian Yin

      Abstract

      In recommender systems, personal characteristic is possessed by not only users but also displaying products. Users have their personal rating patterns while products have different characteristics that attract users. This information can be explicitly exploited from the review text. However, most existing methods only model the review text as a topic preference of products, without considering the perspectives of users and products simultaneously. In this paper, we propose a user-product topic model to capture both user preferences and attractive characteristics of products. Different from conventional collaborative filtering in conjunction with topic models, we use non-negative matrix tri-factorization to jointly reveal the characteristic of users and products. Experiments on two real-world data sets validate the effectiveness of our method in Top-N recommendations.

   7. Low-Rank and Sparse Cross-Domain Recommendation Algorithm

      Zhi-Lin Zhao, Ling Huang, Chang-Dong Wang, Dong Huang

      Abstract

      In this paper, we propose a novel Cross-Domain Collaborative Filtering (CDCF) algorithm termed Low-rank and Sparse Cross-Domain (LSCD) recommendation algorithm. Different from most of the CDCF algorithms which tri-factorize the rating matrix of each domain into three low dimensional matrices, LSCD extracts a user and an item latent feature matrix for each domain respectively. Besides, in order to improve the performance of recommendations among correlated domains by transferring knowledge and uncorrelated domains by differentiating features in different domains, the features of users are separated into shared and domain-specific parts adaptively. Specifically, a low-rank matrix is used to capture the shared feature subspace of users and a sparse matrix is used to characterize the discriminative features in each specific domain. Extensive experiments on two real-world datasets have been conducted to confirm that the proposed algorithm transfers knowledge in a better way to improve the quality of recommendation and outperforms the state-of-the-art recommendation algorithms.

   8. Cross-Domain Recommendation for Cold-Start Users via Neighborhood Based Feature Mapping

      Xinghua Wang, Zhaohui Peng, Senzhang Wang, Philip S. Yu, Wenjing Fu, Xiaoguang Hong

      Abstract

      Traditional Collaborative Filtering (CF) models mainly focus on predicting a user’s preference to the items in a single domain such as the movie domain or the music domain. A major challenge for such models is the data sparsity problem, and especially, CF cannot make accurate predictions for the cold-start users who have no ratings at all. Although Cross-Domain Collaborative Filtering (CDCF) is proposed for effectively transferring users’ rating preference across different domains, it is still difficult for existing CDCF models to tackle the cold-start users in the target domain due to the extreme data sparsity. In this paper, we propose a Cross-Domain Latent Feature Mapping (CDLFM) model for cold-start users in the target domain. Firstly, the user rating behavior is taken into consideration in the matrix factorization for alleviating the data sparsity. Secondly, neighborhood based latent feature mapping is proposed to transfer the latent features of a cold-start user from the auxiliary domain to the target domain. Extensive experiments on two real datasets extracted from Amazon transaction data demonstrate the superiority of our proposed model against other state-of-the-art methods.