PaperlayerView exact revision on arXiv

Source-linked AI summary

Reinforced Neighborhood Selection Guided Multi-Relational Graph Neural Networks

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

arXiv:2104.07886v2cs.LGcs.SI

TL;DR

Existing GNNs oversimplify heterogeneous, multi-relational graphs, motivating a model that preserves relation-specific structure while selecting informative neighbors. RioGNN combines task-driven multi-relational graph construction, label-aware similarity, relation-aware reinforcement learning, and recursive threshold optimization, and reports improvements in effectiveness, efficiency, and explainability across real-world tasks.

  • Problem

    Existing GNNs often oversimplify heterogeneous nodes and multi-relational edges, while practical graphs contain diverse relations and potentially misleading neighbors.

  • Method

    RioGNN constructs task-driven multi-relational graphs and uses label-aware similarity, reinforced relation-aware neighbor selection, and recursive scalable reinforcement learning to optimize filtering thresholds.

  • Results

    RioGNN significantly improves downstream tasks over state-of-the-art GNNs and dedicated heterogeneous models by 0.70%–32.78%, while RSRL improves learning time by up to 4.52x and node classification by 4.90%.

  • Takeaways & Limitations

    The framework supports more discriminative node embeddings and explains relation importance through learned filtering thresholds across fraud detection, diabetes detection, classification, and clustering tasks.

  • Takeaways & Limitations

    The authors identify manual relation definition as a remaining limitation and propose multi-agent reinforcement learning to adaptively identify meaningful relations for each node.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have been widely used for the representation learning of various structured graph data. While promising, most existing GNNs oversimplified the complexity and diversity of the edges in the graph, and thus inefficient to cope with ubiquitous heterogeneous graphs, which are typically in the form of multi-relational graph representations. In this paper, 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.

1 INTRODUCTION

Existing GNNs often simplify heterogeneous nodes and multi-relational edges, limiting their suitability for practical tasks. RioGNN addresses this with relation-aware neighborhood selection, recursive reinforcement learning, and multi-relational representations.

  • Motivation and framework: Existing homogeneous GNNs simplify node and edge diversity, while heterogeneous models often require complex architectures and strong domain knowledge.Examples include GraphSAGE, GCN, GAT, and GIN, alongside more specialized heterogeneous models such as HetGNN, RSHN, HGT, and MAGNN.
  • Motivation and framework: RioGNN extends GNNs to multi-relational graphs while preserving relation-dependent representations for diverse practical tasks.The framework uses task-driven graph construction and explicitly differentiates edge types without requiring entity-associated meta-structures.
  • Method: RioGNN combines label-aware neural similarity with reinforced relation-aware neighbor selection before aggregating information across relations.The similarity measure uses supervised signals and node features to identify similar neighbors and reduce embedding over-assimilation.
  • Experiments and contributions: 0.70%–32.78% improvement across downstream tasks and up to 4.52x faster learning demonstrate RioGNN’s reported effectiveness and efficiency over comparative GNNs.The experiments cover fraud detection and diabetes detection on Yelp, Amazon, and MIMIC-III, including node classification and clustering.
  • Experiments and contributions: The paper contributes a recursive, scalable reinforcement-learning framework and an explainability analysis based on the importance of individual relations.The framework learns filtering thresholds with estimable depth and width for different graph scales or tasks.

2 BACKGROUND AND OVERVIEW

The paper formulates multi-relational graphs and GNN aggregation around relation-specific edges, node features, and labels. It frames RioGNN around filtering misleading neighbors, selecting suitable neighbors across relations, and efficiently optimizing filtering thresholds.

  • 2.1 Problem Definition: A multi-relational graph contains feature-bearing nodes, relation-specific edges, and labels, with an edge potentially associated with multiple relations.The graph directly represents task elements as nodes and uses relationships between differently labeled elements as multiple connections.
  • 2.1 Problem Definition: The multi-relational formulation models practical tasks such as spam-review detection and disease diagnosis by connecting task elements through distinct relation types.Examples include reviews connected through shared product, user, rating, or temporal characteristics, and patients connected through similar symptoms.
  • 2.1 Problem Definition: Multi-relational GNNs separate intra-relation aggregation from inter-relation aggregation before combining node and neighborhood information.Neighbor embeddings are aggregated within each relation, then the relation-level embeddings are combined with the central node representation.
  • 2.2 Problem Scope and Challenges: The framework must filter misleading neighbors because adversarial, camouflaged, or imprecisely selected features can cause a central node’s embedding to assimilate noisy neighbors.The paper identifies similarity measurement as necessary before applying neighborhood information in a GNN.
  • 2.2 Problem Scope and Challenges: Different relations require adaptive neighbor selection because labeling all similar neighbors is expensive and a shared filtering threshold is unsuitable for many noisy relations.The paper also identifies continuous threshold optimization as a challenge for large-scale graphs and notes limitations of the preliminary Bernoulli bandit approach.

3 METHODOLOGY

RioGNN combines label-aware similarity, adaptive relation-specific neighbor filtering, and recursive reinforcement learning to construct efficient multi-relational graph representations.

  • Architecture: RioGNN’s architecture comprises label-aware similarity measurement, similarity-aware neighbor selection, and relation-aware neighbor aggregation.These modules form the model’s main processing pipeline.
  • Label-aware Neural Similarity Measure: An FCN uses supervised node-label predictions and l1-distance to measure similarity between neighboring nodes at each layer.The similarity measure uses intermediate node embeddings as input and is trained with cross-entropy loss.
  • Label-aware Neural Similarity Measure: The label-aware similarity measure reduces computation from O(kd) to O(d) by comparing FCN predictions instead of combined k-neighbor embeddings.This design considers each node’s own feature when producing the prediction used for similarity.
  • Top-p Sampling: Top-p sampling ranks neighbors by similarity within each relation and retains a relation- and layer-specific fraction before aggregation.The filtering threshold p^l_r determines the retained proportion, while discarded neighbors do not participate in that layer’s aggregation.
  • RSRL Framework: The recursive framework addresses local-optimality and convergence-cost issues associated with manually specified or fixed threshold-adjustment strategies.Earlier strategies could require more convergence epochs, increasing computation and reducing accuracy on larger datasets.
  • RSRL Framework: RSRL models threshold selection as an L-layer reinforcement-learning forest whose recursive search adapts filtering strategies to different relations.The framework recursively searches actions until accuracy requirements are met and reduces action-search time from O(k_r) to O(αlog_αk_r).

4 EXPERIMENTAL SETUP

The experiments evaluate RioGNN across fraud, disease, clustering, and inductive-learning settings using task-specific multi-relational graphs and controlled training procedures.

  • Implementation: Experiments use mini-batch training and under-sampling to improve training efficiency and avoid overfitting.Negative instances are randomly sampled at the same count as positive instances within each mini-batch.
  • Experimental tasks: Experiments cover spam review, fraudulent user, and diabetes diagnosis classification tasks across Yelp, Amazon, and MIMIC-III.The setup also includes clustering and inductive-learning evaluations.
  • Graph construction: The constructed graphs encode task-specific relations, including shared users, products, ratings, diagnoses, procedures, and microbiology codes.Yelp uses R-U-R, R-T-R, and R-S-R; Amazon uses U-P-U, U-S-V, and U-V-U; MIMIC-III uses V-A-V, V-D-V, V-P-V, and V-M-V.
  • Dataset statistics: The datasets differ substantially in class balance, relation counts, edge distributions, and relation-matrix density.Yelp and Amazon contain 14.5% and 9.5% fraud nodes, while MIMIC-III has a more balanced ratio and denser relation matrices.

4.3 Baselines and Variations

The study compares RioGNN with traditional, heterogeneous, multi-relational, and reinforcement-learning-guided GNN baselines, then evaluates variants of its core modules and reinforcement-learning choices.

  • Baselines: Baselines span homogeneous, heterogeneous, multi-relational, and reinforcement-learning-guided GNN models.GCN, GAT, GraphSAGE, and GeniePath use merged homogeneous graphs; GraphNAS_H and Policy-GNN_H use raw heterogeneous graphs; other models use multi-relational graphs.
  • Model variations: RioGNN variants isolate the effects of label-aware similarity, similarity-aware neighbor selection, and relation-aware aggregation.Table 3 summarizes the main functions of the variants.
  • Model variations: RioGNN 2l uses Actor-Critic reinforcement learning to recursively select relation filter thresholds while using a two-layer label-aware similarity measure.The thresholds act as relation weights during cross-relation aggregation.
  • Model variations: BIO-GNN and ROO-GNN vary the reinforcement-learning algorithm used for recursive relation-threshold selection.BIO-GNN uses BMAB, whereas ROO-GNN uses Actor-Critic with the same general filtering-threshold aggregation design.
  • Reinforcement-learning variations: The framework is tested with discrete and continuous action spaces using algorithms including Actor-Critic, DDPG, and SAC.Discrete actions represent discrete filtering thresholds, while continuous actions represent continuous filtering thresholds.

4.4 Model Training

Model training uses shared hyperparameters and fixed default settings across experiments, with dataset-specific batch sizes.

  • Shared settings: All models use embedding size 64, learning rate 0.01, similarity-loss weight λ1 = 2, and L2 regularization weight λ2 = 0.001.Batch sizes are 1024 for Yelp and 256 for Amazon and MIMIC-III.
  • Default configuration: Unless otherwise specified, experiments use a 40% training ratio, 1:1 under-sampling ratio, three deep switches, and depth-first/breadth-first weight α = 10.The default similarity perception setting is single-layer.

4.5 Evaluation Metrics

Evaluation uses classification metrics AUC and Recall, clustering metrics NMI and ARI, and F1 for inductive learning.

  • Classification metrics: AUC and Recall measure overall classifier performance, with AUC reducing the influence of imbalanced classes through probability ranking.Recall is defined using true-positive and false-negative counts.
  • Clustering metrics: NMI and ARI serve as performance indicators for clustering tasks.The metric definitions use class-cluster contingency counts and cluster or class totals.
  • Inductive-learning metrics: Inductive-learning experiments add F1 to AUC and Recall for evaluation.F1 uses precision, true positives, and false positives.

5.1 Overall Evaluation of Fraud Detection Task

RioGNN improves fraud detection by constructing multi-relational graphs and selecting relation-specific neighbors through similarity-aware reinforcement learning. Experiments show gains in classification, clustering, threshold optimization, and multi-layer similarity analysis, with performance and efficiency shaped by dataset structure.

  • Single-relations vs. Multi-relations: RioGNN and related neighbor-sampling models significantly outperform other baselines by 8.60%-32.78% on Yelp and Amazon fraud detection.The results attribute this advantage to sampling neighbors according to node features before aggregation, reducing interference from impure neighbors.
  • Single-relations vs. Multi-relations: Multi-relational graphs improve AUC by 0.33%-1.71% over heterogeneous graphs on Yelp and Amazon.GraphNAS and Policy-GNN do not show significant AUC or Recall advantages because they do not adaptively sample different relations.
  • RioGNN Variants in Classification: Automatic strategy optimization improves classification accuracy by 4.65% on Yelp and 0.89% on Amazon.The recursive framework converges all relations by 110 epochs, compared with 390 epochs for the non-recursive ROO-GNN variant.
  • RioGNN Variants in Clustering: RioGNN improves clustering over RIO-GNN2l and BIO-GNN by at least 9.04% NMI and 10.33% ARI on Yelp, and 2.39% NMI and 1.87% ARI on Amazon.On Amazon, RioGNN also exceeds ROO-GNN by 3.45% NMI and 2.31% ARI, whereas ROO-GNN performs best on Yelp.
  • Explainable RSRL Training Process: RioGNN reaches different relation-specific filtering thresholds, converging to [0.99, 0.093, 0.787] on Yelp and [0.071, 0.0712, 0.9997] on Amazon.The framework independently searches thresholds for each relation using relation similarities as rewards, producing a Nash-equilibrium sampling scheme.
  • Multi-layer Analysis: Multi-layer similarity scores improve by 14.00 for R-U-R, 5.33 for R-T-R, and 7.66 for R-S-R, although AUC gains remain limited on these datasets.The paper attributes the limited AUC gain to sufficient one-hop information and suggests multi-layer joining for datasets with insufficient one-hop embeddings.

5.2 Overall Evaluation of Diagnosis of Diabetes Mellitus Task

On MIMIC-III diabetes diagnosis, RioGNN generally outperforms single-relation, heterogeneous, and internal variant baselines, while its recursive reinforcement framework stabilizes relation-specific filtering.

  • Accuracy Analysis: RioGNN exceeds single-relation GCN, GAT, and GraphSAGE by 13.32%-18.30% and heterogeneous GCT, HSGNN, and HAN by at least 8.77% on MIMIC-III.The comparison is reported for diabetes diagnosis accuracy.
  • Accuracy Analysis: RioGNN accuracy steadily increases as the training ratio rises from 5% to 40%, whereas some baselines do not improve with additional supervised signals.The authors associate this behavior with learning more node features during recursive reinforcement learning.
  • Clustering Analysis: RioGNN improves clustering over BIO-GNN and ROO-GNN by at least 0.29% in NMI and 1.76% in ARI on diabetes diagnosis.The result supports the RSRL framework’s accuracy benefit on dense datasets.
  • RSRL Framework: RioGNN outperforms CARE-GNN in almost every MIMIC-III training epoch, indicating a positive effect of the RSRL framework on classification results.The framework filters suspected nodes through a reinforcement learning tree.
  • Filter Thresholds: RioGNN converges to stable relation-specific thresholds within 100 epochs, with thresholds [0.88, 0.96, 0.32, 0.26] across four relations.BIO-GNN’s corresponding thresholds are [0.35, 0.37, 0.36, 0.37], showing different filtering strengths across relations.

5.3 Versatility Analysis of RSRL Framework

The RSRL framework adapts reinforcement-learning algorithms, action spaces, and tree dimensions to task and dataset characteristics, with continuous actions performing best on two datasets.

  • Algorithms and Action Space for Different Task Scenarios: RSRL flexibly matches reinforcement-learning algorithms and action-space types to datasets while adaptively estimating each relation’s tree depth and width.This design targets datasets with different sizes and types.
  • Algorithms and Action Space for Different Task Scenarios: PD3 with continuous actions and two Q-value-updating networks achieves the best results on Yelp and MIMIC-III, while discrete actions perform best on Amazon.The comparison records the best AUC within 500 epochs.
  • Depth and Width for Different Task Scenarios: The adaptive parameter α controls each relation layer’s action-space size and the overall relation-tree depth, affecting both AUC and convergence epochs.The experiments compare these effects across three datasets.

5.4 Inductive Learning Analysis

Under inductive learning, RioGNN retains advantages over GAT and GraphSAGE and remains comparatively stable across its variants and challenging task settings.

  • Inductive Learning Analysis: RioGNN improves AUC, Recall, and F1 over GAT and GraphSAGE by 17.34%-28.53%, 2.64%-23.30%, and 13.29%-20.90%, respectively.The results cover Yelp, Amazon, and MIMIC-III under inductive learning.
  • Inductive Learning Analysis: RioGNN maintains relatively stable evaluation metrics across variants and surpasses ROO-GNN on Yelp AUC and Recall under inductive learning.This contrasts with ROO-GNN’s slight transductive-learning advantage on Yelp.

5.5 Hyper-parameter Sensitivity

Hyper-parameter experiments show that balanced sampling avoids the overfitting observed with a 1:0.2 ratio, while the study also varies backtracking and deep-switching settings across three datasets.

  • Parameter Sensitivity: A 1:1 sampling ratio yields higher AUC and Recall than 1:0.5 and 1:2 across Yelp, Amazon, and MIMIC-III.A 1:0.2 ratio causes overfitting in all three datasets.
  • Parameter Sensitivity: Figure 12 evaluates under-sampling ratio, backtracking, and deep switching number as sensitivity factors across Yelp, Amazon, and MIMIC-III.The caption identifies the three parameter dimensions and datasets.

6 RELATED WORK

Prior work spans homogeneous, heterogeneous, multi-graph, reinforcement-learning, and RL-guided GNNs, but these approaches differ in how they model graph structure and adapt to tasks.

  • 6 RELATED WORK: Semi-supervised GNN research includes homogeneous, heterogeneous, and multiple-graph learning models.Homogeneous methods omit node or edge types, whereas heterogeneous methods incorporate them during neighborhood aggregation.
  • 6 RELATED WORK: Homogeneous GNNs use convolution, neighbor sampling, or attention to generate node embeddings without modeling node or edge types.Examples include GCN, Graph-SAGE, and GAT.
  • 6 RELATED WORK: Heterogeneous GNNs model diverse node or edge types through meta-paths, meta-graphs, relation-aware aggregation, or type-dependent neural parameters.Representative methods include GAS, HAN, MAGNN, R-GCN, SemiGNN, FdGars, and GraphConsis.
  • 6 RELATED WORK: Reinforcement-learning methods include value-based, policy-based, and Actor-Critic algorithms, each associated with different action-space, convergence, or adaptability limitations.The surveyed literature notes that frameworks supporting only one reinforcement-learning algorithm may be less adaptable across task types.
  • 6 RELATED WORK: RL-guided GNN studies use graph representations to improve reinforcement learning or use reinforcement learning to optimize graph representation processes such as reasoning paths and meta-path selection.RioGNN differs from RL-HGNN by focusing on reinforced neighborhood selection rather than primarily revealing meaningful meta-paths.

7 CONCLUSION AND FUTURE WORK

RioGNN combines label-aware similarity, relation-aware reinforcement learning, and recursive scalability to select neighborhoods in multi-relational graphs. Experiments report consistent superiority across three benchmark datasets, while future work targets automated relation identification and broader graph tasks.

  • 7 CONCLUSION AND FUTURE WORK: RioGNN significantly, consistently, and steadily outperforms state-of-the-art alternatives across three real-world benchmark datasets.The evaluation targets effectiveness, efficiency, and explainability in spam review detection and disease diagnosis tasks.
  • 7 CONCLUSION AND FUTURE WORK: RioGNN uses label-aware neural similarity, reinforced relation-aware neighbor selectors, and a recursive scalable framework with estimable depth and width.These components support adaptive neighborhood aggregation for multi-relational graphs.
  • 7 CONCLUSION AND FUTURE WORK: Future work aims to use multi-agent reinforcement learning to identify meaningful relations for each node instead of manually defining relations.The stated goal is automated representation learning on heterogeneous data.
  • 7 CONCLUSION AND FUTURE WORK: The authors also plan to extend RioGNN to additional graph-analysis applications, including personalized recommendation and social-network analysis.
Loading 2104.07886v2…