Graph DNA: Deep Neighborhood Aware Graph Encoding for Collaborative\n Filtering

2019/05/29 by Liwei Wu, Hsiang-Fu Yu, Wu, Liwei +9
Computer Science · Mathematics · Social Sciences · #Advanced Graph Neural Networks #Algorithm #Artificial Intelligence (cs.AI) #Artificial intelligence #Bloom filter #Caching and Content Delivery #Collaborative filtering #Computer science #Encoding (memory) #FOS: Computer and information sciences #Graph #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine learning #Privacy, Security, and Data Protection #Probabilistic logic #Recommender Systems and Techniques #Recommender system #Theoretical computer science #cs.AI #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1905.12217

under review

arxiv created 2019/05/29 · openalex publication_date 2019/05/29 · arxiv updated 2019/05/30 · openalex created_date 2022/07/29 · openalex updated_date 2026/08/05

Abstract

In this paper, we consider recommender systems with side information in the\nform of graphs. Existing collaborative filtering algorithms mainly utilize only\nimmediate neighborhood information and have a hard time taking advantage of\ndeeper neighborhoods beyond 1-2 hops. The main caveat of exploiting deeper\ngraph information is the rapidly growing time and space complexity when\nincorporating information from these neighborhoods. In this paper, we propose\nusing Graph DNA, a novel Deep Neighborhood Aware graph encoding algorithm, for\nexploiting deeper neighborhood information. DNA encoding computes approximate\ndeep neighborhood information in linear time using Bloom filters, a\nspace-efficient probabilistic data structure and results in a per-node encoding\nthat is logarithmic in the number of nodes in the graph. It can be used in\nconjunction with both feature-based and graph-regularization-based\ncollaborative filtering algorithms. Graph DNA has the advantages of being\nmemory and time efficient and providing additional regularization when compared\nto directly using higher order graph information. We conduct experiments on\nreal-world datasets, showing graph DNA can be easily used with 4 popular\ncollaborative filtering algorithms and consistently leads to a performance\nboost with little computational and memory overhead.\n

Citations

• PU Learning for Matrix Completion
• Network Applications of Bloom Filters: A Survey
• Matrix Factorization Techniques for Recommender Systems
• Scalable Bloom Filters
• Empirical Analysis of Predictive Algorithms for Collaborative Filtering
• Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding
• Space/time trade-offs in hash coding with allowable errors
• BPR: Bayesian Personalized Ranking from Implicit Feedback
• Semi-Supervised Classification with Graph Convolutional Networks
• Graph Convolutional Matrix Completion
• Inductive Representation Learning on Large Graphs

Related

• How Powerful is Graph Convolution for Recommendation?
• Improving Collaborative Filtering Recommendation via Graph Learning
• A Topology-aware Analysis of Graph Collaborative Filtering
• On Manipulating Signals of User-Item Graph: A Jacobi Polynomial-based Graph Collaborative Filtering
• How Powerful is Graph Filtering for Recommendation