Rel-MOSS: Towards Imbalanced Relational Deep Learning on Relational Databases

This paper introduces Rel-MOSS, a novel relation-centric deep learning framework that addresses the critical issue of class imbalance in relational databases by employing a relation-wise gating controller and a relation-guided minority synthesizer to enhance the representation and over-sampling of minority entities, thereby significantly outperforming existing methods in entity classification tasks.

The Gist

Imagine you are a detective trying to solve a crime in a massive city. The city is your Relational Database (RDB)—a giant collection of interconnected records (like people, products, and reviews) that talk to each other.

Your job is to find the criminals (the "minority" class, like fake accounts or fraudulent transactions). The problem? The city is 99% made up of law-abiding citizens (the "majority" class).

The Problem: The "Loud Crowd" Effect

In the past, detectives (AI models) used a method called Relational Deep Learning. They would ask a suspect, "Who are your friends?" and listen to the answers to decide if the suspect was guilty.

But here's the catch: Because there are so many law-abiding citizens, their voices are louder and more numerous.

• If a criminal has 5 friends, and 4 of them are honest citizens, the detective hears mostly "He's innocent!"
• The AI gets overwhelmed by the "loud crowd" of normal data. It stops listening to the subtle clues that scream "Criminal!" and ends up labeling everyone as innocent.
• Result: The model fails completely. It misses the bad guys because it's too busy listening to the good guys.

The Solution: Rel-MOSS

The authors of this paper built a new detective tool called Rel-MOSS. Think of it as a super-smart detective who knows exactly how to handle a noisy crowd. It has two special gadgets:

1. The "Volume Knob" (Rel-Gate)

Imagine the detective has a special pair of headphones with a volume knob for every type of relationship.

• Normally, the AI listens to all friends equally.
• Rel-Gate looks at each friend and asks: "Is this friend likely to be part of the criminal gang?"
• If a friend is a "law-abiding citizen" (majority), Rel-Gate turns their volume down.
• If a friend is suspicious or part of a small, tight-knit criminal group (minority), Rel-Gate turns their volume up.
• The Result: The detective can finally hear the quiet, critical whispers of the minority group without being drowned out by the shouting majority.

2. The "Clay Sculptor" (Rel-Syn)

Even with better hearing, the detective still doesn't have enough examples of criminals to learn from. They need more practice cases.

• Old methods tried to make fake criminals by just mixing the features of two real criminals (like mixing two colors of paint). But in a relational database, this is dangerous. If you just mix the "paint," you might create a fake criminal who has a weird, impossible social network (e.g., a criminal who is friends with 500 people, which real criminals never do). This breaks the rules of the city.
• Rel-Syn is a Clay Sculptor. Instead of just mixing paint, it looks at the structure of the criminal's life. It asks: "What does a typical criminal's social circle look like? How many friends do they have? What kind of people are they?"
• It creates new, fake criminals that perfectly mimic the structure of real ones. These aren't just random copies; they are faithful replicas that fit perfectly into the city's social network.
• The Result: The detective now has a huge, realistic training set of criminals to study, making them much better at spotting the real ones.

Why This Matters

In the real world, this is like finding fraudulent credit cards, fake social media accounts, or failed medical trials. These are rare events hidden in a sea of normal data.

• Without Rel-MOSS: The AI ignores the rare events because they are too quiet.
• With Rel-MOSS: The AI turns up the volume on the rare events and creates realistic practice scenarios, allowing it to catch the bad guys with much higher accuracy.

The Bottom Line

The paper shows that by tuning the volume of different relationships and sculpting realistic fake examples that respect the complex web of connections, we can finally teach AI to see the "needles in the haystack" that it was previously ignoring. It's a game-changer for making AI fair and effective in the real world.

Technical Summary

Here is a detailed technical summary of the paper "Rel-MOSS: Towards Imbalanced Relational Deep Learning on Relational Databases."

1. Problem Statement

The paper addresses a critical gap in Relational Deep Learning (RDL): the class imbalance problem in relational database (RDB) entity classification.

• Context: RDL treats RDBs as heterogeneous entity graphs to enable end-to-end learning. However, existing RDL methods (e.g., RelGNN, HGT) assume balanced data or ignore imbalance.
• The Challenge: In real-world RDBs (e.g., fraud detection, churn prediction), minority classes (e.g., fraudulent users) are vastly outnumbered by majority classes.
• Specific Issues in RDBs:
  1. Minority Information Collapse: Standard Graph Neural Networks (GNNs) aggregate messages indiscriminately. In imbalanced RDBs, the sheer volume and strong connection strength of majority neighbors drown out minority signals, causing minority and majority entity representations to become indistinguishable.
  2. Relational Inconsistency in Synthesis: Existing oversampling methods (like GraphSMOTE) designed for homogeneous graphs fail in heterogeneous RDBs. They often ignore the complex structural roles of entities, generating synthetic samples that violate relational consistency (e.g., a synthetic "fraud user" might have a neighborhood structure typical of a "benign user").

2. Methodology: Rel-MOSS

The authors propose Rel-MOSS (Relation-centric Minority Synthetic Over-sampling GNN), a framework specifically designed for heterogeneous entity graphs derived from RDBs. It consists of two core modules:

A. Modality-Specific Feature Encoder

Since RDB entities have diverse feature types (numeric, categorical, timestamp, text), the model first uses dedicated encoders ($E_k$) for each modality to convert raw features into unified vector representations, followed by a projection MLP to standardize dimensions.

B. Rel-Gate: Relation-wise Gating Controller

To address Minority Information Collapse, Rel-Gate modulates the message-passing process.

• Mechanism: Instead of treating all relation types equally, Rel-Gate estimates the likelihood that the neighborhood information from a specific relation type $r$ leans toward the minority class.
• Implementation: It uses a learnable relation embedding ($R_r$) and a cross-attention mechanism (Query, Key, Value) to compute a gating factor $\Psi_{e,r}$.
• Effect: If a relation type provides strong minority-discriminative signals, the gate amplifies it; if it is dominated by majority noise, the gate suppresses it. This ensures minority signals are preserved during aggregation.

C. Rel-Syn: Relation-guided Minority Synthesizer

To address Relational Inconsistency, Rel-Syn performs oversampling while preserving the structural integrity of the graph.

• Relational Signatures: Instead of just interpolating in the embedding space, Rel-Syn defines a "relational signature" ($S_e$) for each entity. This signature captures structural statistics, such as:
  • Histograms of 1-hop and 2-hop neighbor entity types.
  • Fan-in and fan-out distributions of relation types.
• Synthesis Process:
  1. Identify the closest minority neighbor $e^*$ based on a distance metric combining both the gated representation ($X_e$) and the relational signature ($S_e$): $D(e, e') = \|X_e - X_{e'}\|^2 + \omega \|S_e - S_{e'}\|^2$.
  2. Perform linear interpolation (Mixup) on both the representation and the signature: $X_{syn} = \lambda X_e + (1-\lambda)X_{e^*}$ and $S_{syn} = \lambda S_e + (1-\lambda)S_{e^*}$.
• Result: The synthetic samples maintain the structural role of true minority entities, preventing distribution shifts.

D. Optimization Objective

The model is trained with a composite loss function:

1. Classification Loss (BCE): Binary Cross-Entropy for both original and synthetic samples.
2. Signature Reconstruction Loss (MSE): Mean Squared Error to ensure the synthesized samples can be reconstructed back to their relational signatures, enforcing structural consistency.

3. Key Contributions

1. First Investigation of Imbalance in RDBs: The paper is the first to formally identify and address the class imbalance problem specifically within the context of Relational Deep Learning on heterogeneous entity graphs.
2. Rel-Gate Mechanism: A novel gating controller that adaptively modulates message passing per relation type to prevent minority signal collapse.
3. Rel-Syn Mechanism: A relation-guided oversampling technique that integrates structural signatures to generate faithful synthetic minority samples, ensuring relational consistency.
4. Comprehensive Evaluation: Extensive experiments on 12 diverse RDB datasets (RelBench) covering e-commerce, social media, and healthcare.

4. Experimental Results

The authors evaluated Rel-MOSS against standard RDL baselines (RDL, HGT, RelGNN) and classic imbalance handling methods (SMOTE, GraphSMOTE, Focal Loss, GraphSHA).

• Performance Gains: Rel-MOSS achieved state-of-the-art performance across 12 datasets.
  • Balanced Accuracy (B-Acc): Average improvement of 2.46% over SOTA RDL methods.
  • G-Mean: Average improvement of 4.00% over SOTA RDL methods.
  • In highly imbalanced datasets (e.g., f1-driver-top3), Rel-MOSS improved G-Mean by nearly 8% compared to the best baseline.
• Ablation Studies:
  • Removing Rel-Syn caused a catastrophic drop in performance (often reverting to random guessing on severe imbalance), proving that faithful synthesis is the fundamental determinant.
  • Removing Rel-Gate caused a moderate but consistent performance drop, confirming its role in enhancing representational distinctiveness.
• Qualitative Analysis:
  • t-SNE Visualization: Showed that Rel-MOSS generates synthetic samples that align with the true minority manifold, whereas GraphSMOTE produced samples that diverged significantly.
  • Distance Metrics: Rel-Gate significantly increased the Euclidean and Manhattan distances between minority and majority representation centroids, proving better class separability.
• Efficiency: The additional computational cost is minimal (linearithmic relative to memory bank size), with runtime comparable to standard RDL pipelines.

5. Significance

• Practical Impact: Rel-MOSS enables the deployment of RDL models in critical real-world scenarios (fraud detection, medical trial prediction, customer churn) where data is inherently imbalanced. Without such methods, models often fail to detect rare but critical events.
• Theoretical Advancement: It bridges the gap between graph data mining and relational database theory by proposing methods that respect the unique heterogeneity and structural complexity of RDBs.
• Ethical AI: By effectively handling class imbalance, the method mitigates algorithmic bias, ensuring that minority entities (e.g., fraudulent accounts or rare diseases) are not systematically under-represented or ignored by AI systems.