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

Asma Sattar, Georgios Deligiorgis, Marco Trincavelli, Davide Bacciu

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.

Standard Graph Neural Networks (GNNs) excel at in-domain link prediction—for example, if a model is trained on friendship data in one city, it can effectively predict missing friendships within that same city. However, they struggle with out-of-domain (OOD) scenarios where the target relationship type was never seen during training.

Illustration of the Out-of-Domain Link Prediction task, where known contexts (c1-c4) are used to predict links in an unknown context (c5).

Most existing multi-relational models treat different relationship types in isolation or assume the target relationship type is already present in the training data. This paper identifies 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.

The GOOD Model Architecture

The authors propose the GOOD (Graph neural network for Out-Of-Domain) model, which is designed to capture the underlying "recipe" of different relationship types to allow for generalization to entirely new domains.

The GOOD model architecture, featuring GNNRel specialists, MixAGG integration, and the core Coefficient Disentangler component.

The architecture consists of three 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 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 combining standard link prediction (binary cross-entropy) and a Disentanglement Loss ($L_Q$). This acts as a powerful regularizer, forcing the model to create more robust and generalizable features by preserving the unique characteristics of each relationship type.

Experimental Evaluation

The researchers evaluated GOOD on five benchmarks across two retail domains:

  • Seasonal Transactions (ST1, ST2, ST3): Internal datasets from H&M Group featuring online transactions across multiple markets and seasons, including 24 edge types.
  • Customer Segmentation (CS1, CS2): Publicly available datasets containing transactions from 37 countries, grouped geographically to create OOD challenges.

Key Results

The GOOD model consistently outperformed state-of-the-art baselines (like RGCN, MSGCN, and MMGCN) in OOD link prediction. It achieved the highest ROC-AUC across almost all datasets, such as 0.6340 on ST1 and 0.6990 on CS2.

One of the most surprising insights was that the Multi-Input (OOD) model often outperformed Single-Input In-Domain (SISO) models. This suggests that seeing a variety of different relationship types helps the model learn more fundamental node features than seeing a large volume of data from just one relationship type. Ablation studies confirmed that removing the Coefficient Disentangler led to a significant drop in performance, proving its criticality for cross-domain transfer.

Conclusion

GOOD introduces a novel design concept for multi-relation embedding aggregation based on disentanglement. By forcing the model to remember the mixing proportions of its inputs, it learns a structured latent space that transfers effectively to unseen contexts. While currently tested on retail data, this architecture holds potential for other 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},
}
Figure