Multi-Relational Graph Neural Network for Out-of-Domain Link Prediction

Asma Sattar, Georgios Deligiorgis, Marco Trincavelli, Davide Bacciu

TL;DR

This paper introduces GOOD (Graph neural network for Out-Of-Domain), a novel architecture designed to predict relationships in a graph that were never seen during training. By using a unique "coefficient disentanglement" loss, the model learns to represent nodes in a way that captures the underlying "recipe" of different relationship types, allowing it to generalize to entirely new domains.

What Problem Does This Paper Address?

Standard Graph Neural Networks (GNNs) excel at in-domain link prediction—for example, if you know who is friends with whom in New York, a GNN can predict missing friendships in New York. However, they struggle with out-of-domain (OOD) scenarios: can you predict "bought-together" relationships in a new country (Domain E) using only data from four other countries (Domains A-D)?

Most existing multi-relational models treat different relationship types in isolation or assume the target relationship type is already present in the training data. The authors identify a gap in handling Multi-Input Single-Output (MISO) tasks, where the goal is to leverage multiple known contexts to predict an unseen, unknown context. This is particularly vital in retail and recommendation systems where data for a specific market or relationship type might be extremely sparse.

Methods

The authors propose the GOOD model, which consists of two primary components:

  1. GNNRel (The Specialists): This layer constructs independent representations for each relationship type (context). It uses Graph Convolutional Networks (GCNs) and handles dynamic graphs by processing time-stamped snapshots with residual (skip) connections to maintain historical state.
  2. MixAGG (The Integrator): This component aggregates the specialized embeddings into a single vector using mixing coefficients ($q$).
  3. Coefficient Disentangler (CD): This is the core innovation. Inspired by "Blind Source Separation," the model includes a secondary task: it must be able to reconstruct the original mixing proportions from the final aggregated embedding.

The model is trained with a multi-objective loss:

  • Link Prediction Loss ($L_{link}$): Standard binary cross-entropy to predict if an edge exists.
  • Disentanglement Loss ($L_Q$): A Mean Squared Log Error (MSLE) that penalizes the model if it cannot "guess" which contexts contributed to the final embedding. This acts as a powerful regularizer, forcing the model to create more robust and generalizable features.

Datasets

The researchers evaluated their model on five benchmarks across two retail domains:

  • ST1, ST2, ST3 (Seasonal Transactions): Internal datasets from H&M Group featuring online transactions across multiple markets and seasons. These include 4 product types and 24 edge types (representing different contexts and seasons).
  • CS1, CS2 (Customer Segmentation): Publicly available datasets containing transactions from 37 countries, grouped geographically to create OOD challenges. These feature 16 different types of edges.

Key Insights and Ideas

  • The "Good Representation" Hypothesis: The authors argue that a representation is truly "good" if you can disentangle the mixing proportions of the various inputs that produced it. This prevents the model from "smearing" information together and forces it to preserve the unique characteristics of each relationship type.
  • MISO > SISO: Surprisingly, the experiments showed that the Multi-Input (OOD) model often outperformed a Single-Input In-Domain model. This suggests that seeing a variety of different relationship types helps the model learn more fundamental node features than seeing a lot of data from just one relationship type.
  • Regularization via Reconstruction: By forcing the model to remember "how much of Context A" and "how much of Context B" went into a node's embedding, the model learns a more structured latent space that transfers better to unseen Context C.

Key Results

The GOOD model consistently outperformed state-of-the-art baselines (like RGCN, MSGCN, and MMGCN) in OOD link prediction:

  • Accuracy & ROC-AUC: GOOD achieved the highest ROC-AUC across almost all datasets (e.g., 0.6340 on ST1 and 0.6990 on CS2).
  • Generalization: While models like MMGCN failed to generalize to OOD tasks (often performing near random), GOOD maintained high performance, proving that the disentanglement mechanism is critical for cross-domain transfer.
  • Ablation Study: Removing the Coefficient Disentangler (the "GOOD-coefficient-ablated" version) led to a significant drop in performance, confirming that the disentanglement task is the primary driver of its OOD success.

Limitations and Future Work

  • Scalability: The current approach processes each relation independently before aggregating. For graphs with hundreds or thousands of relation types, this could become computationally expensive. The authors suggest exploring meta-path based approaches to improve scalability.
  • Attention Mechanisms: While the current model uses a disentangler to handle mixing, the authors plan to investigate attention-based integration to allow the model to automatically weigh which source domains are most relevant to the target domain.
  • Broader Applications: While tested on retail data, the authors note the potential for this architecture in fields like drug-protein interaction networks, where predicting new types of therapeutic effects is a major challenge.

Summary updated

Abstract

Dynamic multi-relational graphs are an expressive relational representation for data enclosing entities and relations of different types, and where relationships are allowed to vary in time. Addressing predictive tasks over such data requires the ability to find structure embeddings that capture the diversity of the relationships involved, as well as their dynamic evolution. In this work, we establish a novel class of challenging tasks for dynamic multi-relational graphs involving out-of-domain link prediction, where the relationship being predicted is not available in the input graph. We then introduce a novel Graph Neural Network model, named GOOD, designed specifically to tackle the out-of-domain generalization problem. GOOD introduces a novel design concept for multi-relation embedding aggregation, based on the idea that good representations are such when it is possible to disentangle the mixing proportions of the different relational embeddings that have produced it. We also propose five benchmarks based on two retail domains, where we show that GOOD can effectively generalize predictions out of known relationship types and achieve state-of-the-art results. Most importantly, we provide insights into problems where out-of-domain prediction might be preferred to an in-domain formulation, that is, where the relationship to be predicted has very few positive examples.
BibTeX
@inproceedings{sattar2024multi,
  author = {Asma Sattar and Georgios Deligiorgis and Marco Trincavelli and Davide Bacciu},
  title = {{Multi-Relational Graph Neural Network for Out-of-Domain Link Prediction}},
  booktitle = {IJCNN},
  year = {2024},
  doi = {10.1109/ijcnn60899.2024.10650198},
}

Loading related content...

Figure