Reinforced Neighborhood Selection Guided Multi-Relational Graph Neural Networks

Hao Peng, Ruitong Zhang, Yingtong Dou, Renyu Yang, Jingyi Zhang, Philip S. Yu

TL;DR

Real-world graphs are messy, containing multiple types of relationships and noisy or actively deceptive nodes (like camouflaged fraudsters). This paper introduces RioGNN, a Graph Neural Network that uses a novel recursive reinforcement learning framework to dynamically figure out exactly how many neighbors to trust—and which ones to ignore—across different types of relationships. It achieves state-of-the-art accuracy and massive speedups on complex tasks like fraud detection and medical diagnosis.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) learn by aggregating information from a node's neighbors. But in the real world, graphs are heterogeneous—nodes and edges come in many different types. For example, in an e-commerce graph, two reviews might be connected because they share the same author, target the same product, or were posted in the same month.

Existing GNNs struggle with two main issues in these environments:

  1. Misbehaved Nodes: Fraudsters actively camouflage their features to look like normal users. If a GNN blindly aggregates data from all neighbors, the central node's embedding gets poisoned by these bad actors.
  2. Threshold Tuning: To fix the poisoning issue, you can filter out dissimilar neighbors. But different relationships have different levels of trustworthiness. Manually tuning the exact filtering threshold (e.g., "keep the top 10% of neighbors for relation A, but the top 80% for relation B") is practically impossible, especially as graphs scale.

Methods

The authors propose RioGNN (Reinforced, recursive and flexible neighborhood selection guided multi-relational GNN), which tackles these challenges through three main innovations:

  • Label-Aware Neural Similarity Measure: Instead of relying on raw features (which fraudsters easily fake), RioGNN uses a lightweight neural network to predict node labels and calculates the distance between these predictions. This acts as a robust similarity score to identify truly relevant neighbors.
  • Recursive and Scalable Reinforcement Learning (RSRL): This is the paper's core technical leap. To find the optimal filtering threshold for each relation, RioGNN uses an RL agent. Instead of searching a massive, flat action space (which is slow and inaccurate), RSRL uses a recursive tree structure. It first searches a coarse range (e.g., 0.0 to 1.0 in steps of 0.1). If it finds 0.8 is best, it "zooms in" and searches between 0.75 and 0.85, and so on. This allows the model to quickly pinpoint highly precise thresholds.
  • Relation-Aware Aggregation: Once the optimal filtering thresholds are found, RioGNN directly uses these threshold values as weights to combine the information from different relations, saving the computational cost of training separate attention weights.

Datasets

The authors evaluated RioGNN on three real-world datasets across two distinct domains:

  • Yelp: Spam review detection (45k nodes). Relations include reviews by the same user, same star rating, etc.
  • Amazon: Fraudulent user detection (11.9k nodes). Relations include users reviewing the same product, similar text, etc.
  • MIMIC-III: A massive medical database used here for diabetes diagnosis (28.5k patient visits). Relations include visits with the same diagnoses, procedures, or microbiology codes.

Key Insights and Ideas

  • Nash Equilibrium of Trust: The RL agents naturally settle on vastly different filtering thresholds for different relations. For example, on Yelp, the model learned to keep 99% of neighbors connected by the "same user" relation, but only 9.3% of neighbors connected by the "same month" relation. The agents find a Nash equilibrium that perfectly balances the signal-to-noise ratio across the graph.
  • Explainability as a Byproduct: Because RioGNN outputs explicit filtering thresholds, the model is highly explainable. A human operator can look at the final thresholds and immediately understand which relationships the model found predictive and which were mostly noise.
  • Recursive RL is a Game-Changer: By structuring the RL action space as a zooming-in tree, the authors solved the classic RL trade-off between precision and convergence time. You don't have to choose between a fast, inaccurate model and a slow, precise one.

Key Results

  • Accuracy: RioGNN significantly outperformed state-of-the-art GNNs and dedicated heterogeneous models, boosting AUC by 0.70% to 32.78% across the datasets.
  • Beating its Predecessor: It beat CARE-GNN (the authors' previous state-of-the-art fraud detection model) by 5.90% on Yelp and 10.41% on Amazon.
  • Speedup: The recursive RSRL framework sped up training time by up to 4.52x compared to a standard, non-recursive RL approach, while simultaneously improving node classification accuracy by up to 4.90%.

Limitations and Future Work

  • Manual Relation Engineering: Currently, RioGNN requires humans to manually define the relations used to build the multi-relational graph (e.g., deciding that "reviews posted in the same month" should be an edge type).
  • Future Work: The authors plan to use multi-agent reinforcement learning to automatically discover and identify meaningful relations from raw heterogeneous data, removing the need for manual feature engineering. They also plan to extend the architecture to recommender systems and social network analysis.

Summary updated

Abstract

Graph Neural Networks (GNNs) have been widely used for the representation learning of various structured graph data, typically through message passing among nodes by aggregating their neighborhood information via different operations. While promising, most existing GNNs oversimplify the complexity and diversity of the edges in the graph and thus are inefficient to cope with ubiquitous heterogeneous graphs, which are typically in the form of multi-relational graph representations. In this article, we propose RioGNN, a novel Reinforced, recursive, and flexible neighborhood selection guided multi-relational Graph Neural Network architecture, to navigate complexity of neural network structures whilst maintaining relation-dependent representations. We first construct a multi-relational graph, according to the practical task, to reflect the heterogeneity of nodes, edges, attributes, and labels. To avoid the embedding over-assimilation among different types of nodes, we employ a label-aware neural similarity measure to ascertain the most similar neighbors based on node attributes. A reinforced relation-aware neighbor selection mechanism is developed to choose the most similar neighbors of a targeting node within a relation before aggregating all neighborhood information from different relations to obtain the eventual node embedding. Particularly, to improve the efficiency of neighbor selecting, we propose a new recursive and scalable reinforcement learning framework with estimable depth and width for different scales of multi-relational graphs. RioGNN can learn more discriminative node embedding with enhanced explainability due to the recognition of individual importance of each relation via the filtering threshold mechanism. Comprehensive experiments on real-world graph data and practical tasks demonstrate the advancements of effectiveness, efficiency, and the model explainability, as opposed to other comparative GNN models.
BibTeX
@article{peng2022reinforced,
  author = {Hao Peng and Ruitong Zhang and Yingtong Dou and Renyu Yang and Jingyi Zhang and Philip S. Yu},
  title = {{Reinforced Neighborhood Selection Guided Multi-Relational Graph Neural Networks}},
  journal = {ACM Trans. Information Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=_EQSMVsMtj_},
}
Figure