BLADE: Biased neighborhood sampling based graph neural network for directed graphs

Directed graphs are ubiquitous and have applications across multiple domains including citation, website, social, and traffic networks. Yet, the majority of research involving graph neural networks (GNNs) focus on undirected graphs. In this paper, we deal with the problem of node recommendation in non-attributed directed graphs. Specifically, given a directed graph and query node as input, the goal is to recommend top-𝑘 nodes that have a high likelihood of a link with the query node. Here we propose BLADE, a novel GNN to model directed graphs. In order to jointly capture link likelihood and link direction, we employ an asymmetric loss function and learn dual embeddings for each node, by appropriately aggregating features from its neighborhood. In order to achieve optimal performance on both low and high-degree nodes, we employ a biased neighborhood sampling scheme that generates locally varying neighborhoods which differ based on a node’s connectivity structure. Extensive experimentation on several open-source and proprietary directed graphs show that BLADE outperforms state-of-the-art baselines by 6-230% in terms of HitRate and MRR for the node recommendation task and 10.5% in terms of AUC for the link direction prediction task. We perform ablation studies to accentuate the importance of biased neighborhood sampling employed in generating higher quality recommendations for both low-degree and high-degree query nodes. Further, BLADE delivers significant improvement in revenue and sales as measured through an A/B experiment.