April 2, 2020

2877 words 14 mins read

# Paper Group ANR 184

Empirical Comparison of Graph Embeddings for Trust-Based Collaborative Filtering. Temporal Network Representation Learning via Historical Neighborhoods Aggregation. RNE: A Scalable Network Embedding for Billion-scale Recommendation. DeBayes: a Bayesian method for debiasing network embeddings. A Node Embedding Framework for Integration of Similarity …

#### Empirical Comparison of Graph Embeddings for Trust-Based Collaborative Filtering

Title Empirical Comparison of Graph Embeddings for Trust-Based Collaborative Filtering
Authors Tomislav Duricic, Hussain Hussain, Emanuel Lacic, Dominik Kowald, Denis Helic, Elisabeth Lex
Abstract In this work, we study the utility of graph embeddings to generate latent user representations for trust-based collaborative filtering. In a cold-start setting, on three publicly available datasets, we evaluate approaches from four method families: (i) factorization-based, (ii) random walk-based, (iii) deep learning-based, and (iv) the Large-scale Information Network Embedding (LINE) approach. We find that across the four families, random-walk-based approaches consistently achieve the best accuracy. Besides, they result in highly novel and diverse recommendations. Furthermore, our results show that the use of graph embeddings in trust-based collaborative filtering significantly improves user coverage.
Published 2020-03-30
URL https://arxiv.org/abs/2003.13345v1
PDF https://arxiv.org/pdf/2003.13345v1.pdf
PWC https://paperswithcode.com/paper/empirical-comparison-of-graph-embeddings-for
Repo
Framework

#### Temporal Network Representation Learning via Historical Neighborhoods Aggregation

Title Temporal Network Representation Learning via Historical Neighborhoods Aggregation
Authors Shixun Huang, Zhifeng Bao, Guoliang Li, Yanghao Zhou, J. Shane Culpepper
Abstract Network embedding is an effective method to learn low-dimensional representations of nodes, which can be applied to various real-life applications such as visualization, node classification, and link prediction. Although significant progress has been made on this problem in recent years, several important challenges remain, such as how to properly capture temporal information in evolving networks. In practice, most networks are continually evolving. Some networks only add new edges or nodes such as authorship networks, while others support removal of nodes or edges such as internet data routing. If patterns exist in the changes of the network structure, we can better understand the relationships between nodes and the evolution of the network, which can be further leveraged to learn node representations with more meaningful information. In this paper, we propose the Embedding via Historical Neighborhoods Aggregation (EHNA) algorithm. More specifically, we first propose a temporal random walk that can identify relevant nodes in historical neighborhoods which have impact on edge formations. Then we apply a deep learning model which uses a custom attention mechanism to induce node embeddings that directly capture temporal information in the underlying feature representation. We perform extensive experiments on a range of real-world datasets, and the results demonstrate the effectiveness of our new approach in the network reconstruction task and the link prediction task.
Tasks Link Prediction, Network Embedding, Node Classification, Representation Learning
Published 2020-03-30
URL https://arxiv.org/abs/2003.13212v1
PDF https://arxiv.org/pdf/2003.13212v1.pdf
PWC https://paperswithcode.com/paper/temporal-network-representation-learning-via
Repo
Framework

#### RNE: A Scalable Network Embedding for Billion-scale Recommendation

Title RNE: A Scalable Network Embedding for Billion-scale Recommendation
Authors Jianbin Lin, Daixin Wang, Lu Guan, Yin Zhao, Binqiang Zhao, Jun Zhou, Xiaolong Li, Yuan Qi
Abstract Nowadays designing a real recommendation system has been a critical problem for both academic and industry. However, due to the huge number of users and items, the diversity and dynamic property of the user interest, how to design a scalable recommendation system, which is able to efficiently produce effective and diverse recommendation results on billion-scale scenarios, is still a challenging and open problem for existing methods. In this paper, given the user-item interaction graph, we propose RNE, a data-efficient Recommendation-based Network Embedding method, to give personalized and diverse items to users. Specifically, we propose a diversity- and dynamics-aware neighbor sampling method for network embedding. On the one hand, the method is able to preserve the local structure between the users and items while modeling the diversity and dynamic property of the user interest to boost the recommendation quality. On the other hand the sampling method can reduce the complexity of the whole method theoretically to make it possible for billion-scale recommendation. We also implement the designed algorithm in a distributed way to further improves its scalability. Experimentally, we deploy RNE on a recommendation scenario of Taobao, the largest E-commerce platform in China, and train it on a billion-scale user-item graph. As is shown on several online metrics on A/B testing, RNE is able to achieve both high-quality and diverse results compared with CF-based methods. We also conduct the offline experiments on Pinterest dataset comparing with several state-of-the-art recommendation methods and network embedding methods. The results demonstrate that our method is able to produce a good result while runs much faster than the baseline methods.
Published 2020-03-10
URL https://arxiv.org/abs/2003.07158v1
PDF https://arxiv.org/pdf/2003.07158v1.pdf
PWC https://paperswithcode.com/paper/rne-a-scalable-network-embedding-for-billion
Repo
Framework

#### DeBayes: a Bayesian method for debiasing network embeddings

Title DeBayes: a Bayesian method for debiasing network embeddings
Authors Maarten Buyl, Tijl De Bie
Abstract As machine learning algorithms are increasingly deployed for high-impact automated decision making, ethical and increasingly also legal standards demand that they treat all individuals fairly, without discrimination based on their age, gender, race or other sensitive traits. In recent years much progress has been made on ensuring fairness and reducing bias in standard machine learning settings. Yet, for network embedding, with applications in vulnerable domains ranging from social network analysis to recommender systems, current options remain limited both in number and performance. We thus propose DeBayes: a conceptually elegant Bayesian method that is capable of learning debiased embeddings by using a biased prior. Our experiments show that these representations can then be used to perform link prediction that is significantly more fair in terms of popular metrics such as demographic parity and equalized opportunity.
Tasks Decision Making, Link Prediction, Network Embedding, Recommendation Systems
Published 2020-02-26
URL https://arxiv.org/abs/2002.11442v2
PDF https://arxiv.org/pdf/2002.11442v2.pdf
PWC https://paperswithcode.com/paper/debayes-a-bayesian-method-for-debiasing
Repo
Framework

#### A Node Embedding Framework for Integration of Similarity-based Drug Combination Prediction

Title A Node Embedding Framework for Integration of Similarity-based Drug Combination Prediction
Authors Liang Yu, Mingfei Xia, Lin Gao
Abstract Motivation: Drug combination is a sensible strategy for disease treatment by improving the efficacy and reducing concomitant side effects. Due to the large number of possible combinations among candidate compounds, exhaustive screening is prohibitive. Currently, a plenty of studies have focused on predicting potential drug combinations. However, these methods are not entirely satisfactory in performance and scalability. Results: In this paper, we proposed a Network Embedding framework in Multiplex Networks (NEMN) to predict synthetic drug combinations. Based on a multiplex drug similarity network, we offered alternative methods to integrate useful information from different aspects and to decide quantitative importance of each network. To explain the feasibility of NEMN, we applied our framework to the data of drug-drug interactions, on which it showed better performance in terms of AUPR and ROC. For Drug combination prediction, we found seven novel drug combinations which have been validated by external sources among the top-ranked predictions of our model.
Published 2020-02-25
URL https://arxiv.org/abs/2002.10625v1
PDF https://arxiv.org/pdf/2002.10625v1.pdf
PWC https://paperswithcode.com/paper/a-node-embedding-framework-for-integration-of
Repo
Framework

#### FONDUE: A Framework for Node Disambiguation Using Network Embeddings

Title FONDUE: A Framework for Node Disambiguation Using Network Embeddings
Authors Ahmad Mel, Bo Kang, Jefrey Lijffijt, Tijl De Bie
Abstract Real-world data often presents itself in the form of a network. Examples include social networks, citation networks, biological networks, and knowledge graphs. In their simplest form, networks represent real-life entities (e.g. people, papers, proteins, concepts) as nodes, and describe them in terms of their relations with other entities by means of edges between these nodes. This can be valuable for a range of purposes from the study of information diffusion to bibliographic analysis, bioinformatics research, and question-answering. The quality of networks is often problematic though, affecting downstream tasks. This paper focuses on the common problem where a node in the network in fact corresponds to multiple real-life entities. In particular, we introduce FONDUE, an algorithm based on network embedding for node disambiguation. Given a network, FONDUE identifies nodes that correspond to multiple entities, for subsequent splitting. Extensive experiments on twelve benchmark datasets demonstrate that FONDUE is substantially and uniformly more accurate for ambiguous node identification compared to the existing state-of-the-art, at a comparable computational cost, while less optimal for determining the best way to split ambiguous nodes.
Tasks Knowledge Graphs, Network Embedding, Question Answering
Published 2020-02-24
URL https://arxiv.org/abs/2002.10127v1
PDF https://arxiv.org/pdf/2002.10127v1.pdf
PWC https://paperswithcode.com/paper/fondue-a-framework-for-node-disambiguation
Repo
Framework

#### ConQUR: Mitigating Delusional Bias in Deep Q-learning

Title ConQUR: Mitigating Delusional Bias in Deep Q-learning
Authors Andy Su, Jayden Ooi, Tyler Lu, Dale Schuurmans, Craig Boutilier
Abstract Delusional bias is a fundamental source of error in approximate Q-learning. To date, the only techniques that explicitly address delusion require comprehensive search using tabular value estimates. In this paper, we develop efficient methods to mitigate delusional bias by training Q-approximators with labels that are “consistent” with the underlying greedy policy class. We introduce a simple penalization scheme that encourages Q-labels used across training batches to remain (jointly) consistent with the expressible policy class. We also propose a search framework that allows multiple Q-approximators to be generated and tracked, thus mitigating the effect of premature (implicit) policy commitments. Experimental results demonstrate that these methods can improve the performance of Q-learning in a variety of Atari games, sometimes dramatically.
Tasks Atari Games, Q-Learning
Published 2020-02-27
URL https://arxiv.org/abs/2002.12399v1
PDF https://arxiv.org/pdf/2002.12399v1.pdf
PWC https://paperswithcode.com/paper/conqur-mitigating-delusional-bias-in-deep-q-1
Repo
Framework

#### Particle-Based Adaptive Discretization for Continuous Control using Deep Reinforcement Learning

Title Particle-Based Adaptive Discretization for Continuous Control using Deep Reinforcement Learning
Authors Pei Xu, Ioannis Karamouzas
Abstract Learning controls in high-dimensional continuous action spaces, such as controlling the movements of highly articulated agents and robots, has long been a standing challenge to model-free deep reinforcement learning (DRL). In this paper we propose a general, yet simple, framework for improving the action exploration of policy gradient DRL algorithms. Our approach adapts ideas from the particle filtering literature to dynamically discretize the continuous action space and track policies represented as a mixture of Gaussians. We demonstrate the applicability of our approach on state-of-the-art DRL baselines in challenging high-dimensional motor tasks involving articulated agents. We show that our adaptive particle-based discretization leads to improved final performance and speed of convergence as compared to uniform discretization schemes and to corresponding implementations in continuous action spaces, highlighting the importance of exploration. In addition, the resulting policies are more stable, exhibiting less variance across different training trials.
Published 2020-03-16
URL https://arxiv.org/abs/2003.06959v1
PDF https://arxiv.org/pdf/2003.06959v1.pdf
Repo
Framework

#### A Deterministic Streaming Sketch for Ridge Regression

Title A Deterministic Streaming Sketch for Ridge Regression
Authors Benwei Shi, Jeff M. Phillips
Abstract We provide a deterministic space-efficient algorithm for estimating ridge regression. For $n$ data points with $d$ features and a large enough regularization parameter, we provide a solution within $\varepsilon$ L$_2$ error using only $O(d/\varepsilon)$ space. This is the first $o(d^2)$ space algorithm for this classic problem. The algorithm sketches the covariance matrix by variants of Frequent Directions, which implies it can operate in insertion-only streams and a variety of distributed data settings. In comparisons to randomized sketching algorithms on synthetic and real-world datasets, our algorithm has less empirical error using less space and similar time.
Published 2020-02-05
URL https://arxiv.org/abs/2002.02013v1
PDF https://arxiv.org/pdf/2002.02013v1.pdf
PWC https://paperswithcode.com/paper/a-deterministic-streaming-sketch-for-ridge
Repo
Framework

#### Multi-tier Automated Planning for Adaptive Behavior (Extended Version)

Title Multi-tier Automated Planning for Adaptive Behavior (Extended Version)
Authors Daniel Ciolek, Nicolás D’Ippolito, Alberto Pozanco, Sebastian Sardina
Abstract A planning domain, as any model, is never complete and inevitably makes assumptions on the environment’s dynamic. By allowing the specification of just one domain model, the knowledge engineer is only able to make one set of assumptions, and to specify a single objective-goal. Borrowing from work in Software Engineering, we propose a multi-tier framework for planning that allows the specification of different sets of assumptions, and of different corresponding objectives. The framework aims to support the synthesis of adaptive behavior so as to mitigate the intrinsic risk in any planning modeling task. After defining the multi-tier planning task and its solution concept, we show how to solve problem instances by a succinct compilation to a form of non-deterministic planning. In doing so, our technique justifies the applicability of planning with both fair and unfair actions, and the need for more efforts in developing planning systems supporting dual fairness assumptions.
Published 2020-02-27
URL https://arxiv.org/abs/2002.12445v1
PDF https://arxiv.org/pdf/2002.12445v1.pdf
Repo
Framework

#### Sample-based Distributional Policy Gradient

Title Sample-based Distributional Policy Gradient
Authors Rahul Singh, Keuntaek Lee, Yongxin Chen
Abstract Distributional reinforcement learning (DRL) is a recent reinforcement learning framework whose success has been supported by various empirical studies. It relies on the key idea of replacing the expected return with the return distribution, which captures the intrinsic randomness of the long term rewards. Most of the existing literature on DRL focuses on problems with discrete action space and value based methods. In this work, motivated by applications in robotics with continuous action space control settings, we propose sample-based distributional policy gradient (SDPG) algorithm. It models the return distribution using samples via a reparameterization technique widely used in generative modeling and inference. We compare SDPG with the state-of-art policy gradient method in DRL, distributed distributional deterministic policy gradients (D4PG), which has demonstrated state-of-art performance. We apply SDPG and D4PG to multiple OpenAI Gym environments and observe that our algorithm shows better sample efficiency as well as higher reward for most tasks.
Tasks Distributional Reinforcement Learning
Published 2020-01-08
URL https://arxiv.org/abs/2001.02652v1
PDF https://arxiv.org/pdf/2001.02652v1.pdf
Repo
Framework

#### Unsupervised Bilingual Lexicon Induction Across Writing Systems

Title Unsupervised Bilingual Lexicon Induction Across Writing Systems
Authors Parker Riley, Daniel Gildea
Abstract Recent embedding-based methods in unsupervised bilingual lexicon induction have shown good results, but generally have not leveraged orthographic (spelling) information, which can be helpful for pairs of related languages. This work augments a state-of-the-art method with orthographic features, and extends prior work in this space by proposing methods that can learn and utilize orthographic correspondences even between languages with different scripts. We demonstrate this by experimenting on three language pairs with different scripts and varying degrees of lexical similarity.
Published 2020-01-31
URL https://arxiv.org/abs/2002.00037v1
PDF https://arxiv.org/pdf/2002.00037v1.pdf
PWC https://paperswithcode.com/paper/unsupervised-bilingual-lexicon-induction
Repo
Framework

#### selp: A Single-Shot Epistemic Logic Program Solver

Title selp: A Single-Shot Epistemic Logic Program Solver
Authors Manuel Bichler, Michael Morak, Stefan Woltran
Abstract Epistemic Logic Programs (ELPs) are an extension of Answer Set Programming (ASP) with epistemic operators that allow for a form of meta-reasoning, that is, reasoning over multiple possible worlds. Existing ELP solving approaches generally rely on making multiple calls to an ASP solver in order to evaluate the ELP. However, in this paper, we show that there also exists a direct translation from ELPs into non-ground ASP with bounded arity. The resulting ASP program can thus be solved in a single shot. We then implement this encoding method, using recently proposed techniques to handle large, non-ground ASP rules, into the prototype ELP solving system “selp”, which we present in this paper. This solver exhibits competitive performance on a set of ELP benchmark instances. Under consideration in Theory and Practice of Logic Programming (TPLP).
Published 2020-01-04
URL https://arxiv.org/abs/2001.01089v1
PDF https://arxiv.org/pdf/2001.01089v1.pdf
PWC https://paperswithcode.com/paper/selp-a-single-shot-epistemic-logic-program
Repo
Framework

#### Topology Distance: A Topology-Based Approach For Evaluating Generative Adversarial Networks

Title Topology Distance: A Topology-Based Approach For Evaluating Generative Adversarial Networks
Authors Danijela Horak, Simiao Yu, Gholamreza Salimi-Khorshidi
Abstract Automatic evaluation of the goodness of Generative Adversarial Networks (GANs) has been a challenge for the field of machine learning. In this work, we propose a distance complementary to existing measures: Topology Distance (TD), the main idea behind which is to compare the geometric and topological features of the latent manifold of real data with those of generated data. More specifically, we build Vietoris-Rips complex on image features, and define TD based on the differences in persistent-homology groups of the two manifolds. We compare TD with the most commonly used and relevant measures in the field, including Inception Score (IS), Frechet Inception Distance (FID), Kernel Inception Distance (KID) and Geometry Score (GS), in a range of experiments on various datasets. We demonstrate the unique advantage and superiority of our proposed approach over the aforementioned metrics. A combination of our empirical results and the theoretical argument we propose in favour of TD, strongly supports the claim that TD is a powerful candidate metric that researchers can employ when aiming to automatically evaluate the goodness of GANs’ learning.
Published 2020-02-27
URL https://arxiv.org/abs/2002.12054v1
PDF https://arxiv.org/pdf/2002.12054v1.pdf
PWC https://paperswithcode.com/paper/topology-distance-a-topology-based-approach
Repo
Framework

#### Neural Rule Ensembles: Encoding Sparse Feature Interactions into Neural Networks

Title Neural Rule Ensembles: Encoding Sparse Feature Interactions into Neural Networks
Authors Gitesh Dawer, Yangzi Guo, Sida Liu, Adrian Barbu
Abstract Artificial Neural Networks form the basis of very powerful learning methods. It has been observed that a naive application of fully connected neural networks to data with many irrelevant variables often leads to overfitting. In an attempt to circumvent this issue, a prior knowledge pertaining to what features are relevant and their possible feature interactions can be encoded into these networks. In this work, we use decision trees to capture such relevant features and their interactions and define a mapping to encode extracted relationships into a neural network. This addresses the initialization related concern of fully connected neural networks. At the same time through feature selection it enables learning of compact representations compared to state of the art tree-based approaches. Empirical evaluations and simulation studies show the superiority of such an approach over fully connected neural networks and tree-based approaches