Three papers accepted in ACM WSDM 2022

1
Title: Directed Network Embedding with Virtual Negative Edges
Author: Hyunsik Yoo, Yeon-Chang Lee, Kijung Shin, Sang-Wook Kim
Abstract
The directed network embedding problem is to represent the nodes in a given directed network as embeddings (i.e., low-dimensional vectors) that preserve the asymmetric relationships between nodes. While a number of approaches have been developed for this problem, we point out that existing approaches commonly face difficulties in accurately preserving asymmetric proximities between nodes in a sparse network containing a large number of low out- and in-degree nodes. In this paper, we focus on addressing this intrinsic difficulty caused by the lack of information. We first introduce the concept of virtual negative edges (VNEs), which represent latent negative relationships between nodes. Based on the concept, we propose a novel DIrected NE approach with VIrtual Negative Edges, named as DIVINE. DIVINE carefully decides the number and locations of VNEs to be added to the input network. Once VNEs are added, DIVINE learns embeddings by exploiting both the signs and directions of edges. Our experiments on four real-world directed networks demonstrate that adding VNEs alleviates the lack of information about low-degree nodes, thereby enabling DIVINE to yield high-quality embeddings that accurately capture asymmetric proximities between nodes. Specifically, the embeddings obtained by DIVINE lead to up to 10.16% more accurate link prediction, compared to those obtained by state-of-the-art competitors. 2
Title: Linear, or Non-Linear, That is the Question!
Author: Taeyong Kong, Taeri Kim, Jinsung Jeon, Jeongwhan Choi, Yeon-Chang Lee, Noseong Park, Sang-Wook Kim
Abstract
There were fierce debates on whether the non-linear embedding propagation of GCNs is appropriate to GCN-based recommender systems. It was recently found that the linear embedding propagation shows better accuracy than the non-linear embedding propagation. Since this phenomenon was discovered especially in recommender systems, it is required that we carefully analyze the linearity and non-linearity issue. In this work, therefore, we revisit the issues of i) which of the linear or non-linear propagation is better and ii) which factors of users/items decide the linearity/non-linearity of the embedding propagation. We propose a novel Hybrid Method of Linear and non-linEar collaborative filTering method (HMLET, pronounced as Hamlet). In our design, there exist both linear and non-linear propagation steps, when processing each user or item node, and our gating module chooses one of them, which results in a hybrid model of the linear and non-linear GCN-based collaborative filtering (CF). The proposed model yields the best accuracy in three public benchmark datasets. Moreover, we classify users/items into the following three classes depending on our gating modules’ selections: Full-Non-Linearity (FNL), Partial-Non-Linearity (PNL), and Full-Linearity (FL). We found that there exist strong correlations between nodes’ centrality and their class membership, i.e., important user/item nodes exhibit more preferences towards the non-linearity during the propagation steps. To our knowledge, we are the first who design a hybrid method and report the correlation between the graph centrality and the linearity/non-linearity of nodes. All HMLET codes and datasets are available at: this https URL. 3
Title: Reinforcement Learning over Sentiment-Augmented Knowledge Graphs towards Accurate and Explainable Recommendation
Author: Sung-Jun Park, Dong-Kyu Chae, Hong-Kyun Bae, Sumin Park, Sang-Wook Kim
Abstract
Explainable recommendation has gained great attention in recent years. A lot of work in this research line has chosen to use the knowledge graphs (KG) where relations between entities can serve as explanations. However, existing studies have not considered sentiment on relations in KG, although there can be various types of sentiment on relations worth considering (e.g., a user’s satisfaction on an item). In this paper, we propose a novel recommendation framework based on KG integrated with sentiment analysis for more accurate recommendation as well as more convincing explanations. To this end, we first construct a Sentiment-Aware Knowledge Graph (namely, SAKG) by analyzing reviews and ratings on items given by users. Then, we perform item recommendation and reasoning over SAKG through our proposed Sentiment-Aware Policy Learning (namely, SAPL) based on a reinforcement learning strategy. To enhance the explainability for end-users, we further developed an interactive user interface presenting textual explanations as well as a collection of reviews related with the discovered sentiment. Experimental results on three real-world datasets verified clear improvements on both the accuracy of recommendation and the quality of explanations.