Graph DNA: Deep Neighborhood Aware Graph Encoding for Collaborative Filtering

Liwei Wu, Hsiang-Fu Yu, Nikhil Rao, James Sharpnack, Cho-Jui Hsieh

Introduction

Collaborative Filtering (CF) remains a cornerstone of modern recommendation systems, predicting user preferences based on historical interactions. To combat data sparsity, researchers frequently integrate "side information" such as social networks or item knowledge graphs. However, a significant bottleneck persists: most algorithms only leverage immediate (1 or 2-hop) neighbors. While "deep" neighborhoods—the preferences of a "friend of a friend of a friend"—contain valuable signals, the exponential growth of neighbors with each hop leads to a "neighborhood explosion," making storage and processing computationally prohibitive.

Methods: Deep Neighborhood Aware Encoding

The authors propose Graph DNA (Deep Neighborhood Aware) encoding to efficiently capture these deep structural signals. The core innovation utilizes Bloom filters—probabilistic, space-efficient data structures—to represent a node's neighborhood in logarithmic space relative to the total number of nodes ($O(\log n)$).

The encoding process follows a simple, deterministic propagation scheme:

  1. Initialization: Each node is assigned a Bloom filter (a bit array) initially containing only its own identifier.
  2. Propagation: Nodes iteratively perform a bitwise OR (union) operation with the Bloom filters of their immediate neighbors.
  3. Encoding: After $d$ iterations, the resulting bit array effectively encodes the node's entire $d$-hop neighborhood.
Iterative propagation of Bloom filters to encode multi-hop neighborhood information.

This "DNA" bit array can then be integrated into various models. In Graph Regularized Matrix Factorization (GRMF), the bits function as "pseudo-nodes" in a bipartite graph. In Graph Convolutional Networks (GCNs), they serve as high-quality, low-dimensional input features. Notably, Graph DNA requires no training; it is a linear-time process that is significantly faster than traditional embedding methods like Node2Vec.

Key Results and Performance

The efficacy of Graph DNA was evaluated on synthetic data and large-scale real-world datasets, including Douban (129k users) and Flixster (147k users).

Performance comparison of Graph DNA against standard Matrix Factorization and higher-order graph regularized methods.

Key findings include:

  • Substantial Performance Gains: On the Flixster dataset, Graph DNA with 3-hop information (DNA-3) achieved a Relative Graph Gain (RGG) exceeding 1000% compared to standard first-order graph regularization in certain Matrix Factorization settings.
  • Computational Efficiency: The encoding process is remarkably fast. For instance, generating features for a 3,000-node graph took only 7.5 seconds, compared to over 15 minutes for Node2Vec.
  • Superiority over GCNs: When used as input features for Graph Convolutional Matrix Completion (GC-MC), Graph DNA outperformed state-of-the-art GCN methods. This suggests that direct encoding of higher-order structures can be more effective than relying on GCN layers to learn them implicitly.

Discussion and Insights

A surprising insight from the study is that Graph DNA often outperforms exact higher-order graph information. The authors hypothesize that the controlled false-positive rate inherent in Bloom filters acts as a form of implicit regularization. This prevents the model from overfitting to "hub" nodes—highly connected users who might otherwise dominate the signal. Furthermore, the number of shared bits between two nodes' DNA serves as a strong proxy for their shortest path distance, capturing structural similarity without expensive path-finding computations.

While highly effective, the method faces a "saturation" limit: if a Bloom filter becomes too full, its discriminative power decreases. The authors employ a threshold parameter ($\theta$) to halt propagation in such cases, though this requires manual tuning. Future research may focus on adapting Graph DNA for dynamic graphs, allowing real-time updates as new users and links are added to the system.

Summary updated

Abstract

In this paper, we consider recommender systems with side information in the form of graphs. Existing collaborative filtering algorithms mainly utilize only immediate neighborhood information and have a hard time taking advantage of deeper neighborhoods beyond 1-2 hops. The main caveat of exploiting deeper graph information is the rapidly growing time and space complexity when incorporating information from these neighborhoods. In this paper, we propose using Graph DNA, a novel Deep Neighborhood Aware graph encoding algorithm, for exploiting deeper neighborhood information. DNA encoding computes approximate deep neighborhood information in linear time using Bloom filters, a space-efficient probabilistic data structure and results in a per-node encoding that is logarithmic in the number of nodes in the graph. It can be used in conjunction with both feature-based and graph-regularization-based collaborative filtering algorithms. Graph DNA has the advantages of being memory and time efficient and providing additional regularization when compared to directly using higher order graph information. We conduct experiments on real-world datasets, showing graph DNA can be easily used with 4 popular collaborative filtering algorithms and consistently leads to a performance boost with little computational and memory overhead.
BibTeX
@inproceedings{wu2020graph,
  author = {Liwei Wu and Hsiang-Fu Yu and Nikhil Rao and James Sharpnack and Cho-Jui Hsieh},
  title = {{Graph DNA: Deep Neighborhood Aware Graph Encoding for Collaborative Filtering}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
}
Figure