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.
Tasks	Network Embedding
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.
Tasks	Network Embedding
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.
Tasks	Network Embedding
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.
Tasks	Continuous Control
Published	2020-03-16
URL	https://arxiv.org/abs/2003.06959v1
PDF	https://arxiv.org/pdf/2003.06959v1.pdf
PWC	https://paperswithcode.com/paper/particle-based-adaptive-discretization-for
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.
Tasks
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.
Tasks
Published	2020-02-27
URL	https://arxiv.org/abs/2002.12445v1
PDF	https://arxiv.org/pdf/2002.12445v1.pdf
PWC	https://paperswithcode.com/paper/multi-tier-automated-planning-for-adaptive
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
PWC	https://paperswithcode.com/paper/sample-based-distributional-policy-gradient
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.
Tasks
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).
Tasks
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.
Tasks
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
Tasks	Feature Selection
Published	2020-02-11
URL	https://arxiv.org/abs/2002.04319v1
PDF	https://arxiv.org/pdf/2002.04319v1.pdf
PWC	https://paperswithcode.com/paper/neural-rule-ensembles-encoding-sparse-feature
Repo
Framework