🤖 machine learning

Inductive inference of gradient-boosted decision trees on graphs for insurance fraud detection

This paper introduces G-GBM, a novel inductive graph gradient boosting machine that effectively combines the robustness of gradient boosting with interpretable heterogeneous graph features to outperform or match state-of-the-art methods in insurance fraud detection while addressing challenges like class imbalance and dynamic data.

Original authors: Félix Vandervorst, Bruno Deprez, Wouter Verbeke, Tim Verdonck

Published 2026-05-18

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Félix Vandervorst, Bruno Deprez, Wouter Verbeke, Tim Verdonck

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are an insurance detective trying to catch a group of people who are faking car accidents or doctor visits to steal money.

The Old Way: Looking at Individuals
Traditionally, detectives looked at each person (or company) in isolation. They checked a list of facts: "How old are they? What car do they drive? Have they made many claims?" This is like trying to solve a mystery by only looking at one suspect's ID card. It works okay, but it misses the big picture. Fraudsters often work in rings, helping each other. If you only look at one person, you might miss the fact that they are connected to a known criminal.

The New Idea: The "Social Network" Map
The authors of this paper realized that to catch organized fraud, you need to see the connections. They built a giant map (a "graph") where:

Nodes are the people and companies.
Lines are the relationships (e.g., "Company A owns this car," "Person B lives at this address," "Person C is the director of Company D").

This map is messy and complex. It has different types of people and different types of connections. It also changes over time as new people join or leave.

The Problem with Current "Smart" Maps
Recently, computer scientists started using fancy "Deep Learning" (AI) to read these maps. Think of these AI models as a black box that takes the whole map, squishes it into a single, blurry summary, and guesses who is a fraudster.

The Flaw: These black boxes are hard to understand. In the insurance world, you can't just say, "The computer says they are guilty." You need to explain why to regulators and courts. Also, these AI models sometimes get confused when the map is huge or when there are very few fraud cases compared to honest people (a problem called "class imbalance").

The Solution: G-GBM (The "Path-Reading" Detective)
The authors created a new tool called G-GBM. Instead of squishing the map into a blurry summary, G-GBM acts like a detective who walks specific paths through the map.

Here is how it works, using a simple analogy:

The "Metapath" Walk: Imagine you are investigating a specific person (let's call him "Bob"). G-GBM doesn't just look at Bob. It sends out little "walkers" to trace specific routes from Bob.
- Path 1: Bob $\rightarrow$ His Car $\rightarrow$ The Car's Owner (maybe Bob's brother).
- Path 2: Bob $\rightarrow$ The Repair Shop $\rightarrow$ The Shop Owner (maybe Bob's cousin).
- Path 3: Bob $\rightarrow$ The Address $\rightarrow$ The Neighbor (who also filed a suspicious claim).
Reading the Clues: Instead of turning these paths into a blurry summary, G-GBM writes down the specific details found along each path. "Bob's brother owns a car," "The repair shop owner is Bob's cousin." It keeps these details separate and clear.
The "Tree" Decision: It feeds these specific path-details into a powerful decision-making engine (called a Gradient Boosted Tree). This engine is famous for being great at spotting patterns in messy data and handling the fact that fraud is rare. It asks: "If I see this specific combination of neighbors and connections, is this person likely to be a fraudster?"
The "Why" (Explainability): This is the superpower. Because the model didn't blur the data, it can point to the exact path that triggered the alarm.
- Example: "We flagged Bob not because of his age, but because Path 2 showed he is connected to a repair shop owner who has 50 other suspicious claims."
- This gives the insurance company a clear "audit trail" to prove their decision, which is required by law.

What the Paper Found
The authors tested this new detective tool on two real-world scenarios:

A Belgian Insurance Dataset: A massive, real-world map of companies and their directors.
A Healthcare Fraud Dataset: A map of doctors and patients.

The Results:

Better or Equal Performance: G-GBM caught fraud just as well as, or better than, the fancy "black box" AI models and the traditional methods.
Speed: It was much faster to train than the complex AI models.
Transparency: It provided clear reasons for its decisions, which the AI models could not do as easily.
Robustness: It handled the "messy" nature of the data (like missing info or weird categories) better than the AI models.

In Summary
The paper introduces a method that combines the best of two worlds: the ability of AI to see complex connections in a social network, and the clarity and speed of traditional decision trees. It doesn't just say "This is fraud"; it says "This is fraud because of these specific connections," making it a practical, trustworthy tool for fighting insurance scams.

Technical Summary: Inductive Inference of Gradient-Boosted Decision Trees on Graphs for Insurance Fraud Detection

Problem Statement

Insurance fraud detection faces a unique set of challenges that render traditional machine learning approaches suboptimal. First, fraud often involves organized networks where individuals and entities collaborate, necessitating the modeling of complex relationships rather than treating claims as independent and identically distributed (i.i.d.) events. Second, insurance data is inherently heterogeneous (involving diverse node types like companies, administrators, and policies) and dynamic (evolving over time). Third, fraud datasets suffer from extreme class imbalance, where confirmed fraud cases are rare compared to legitimate claims.

While Graph Neural Networks (GNNs) have emerged as a powerful tool for modeling relational data, they face significant hurdles in this domain:

Inductive Limitations: Many embedding methods (e.g., node2vec) are transductive and struggle to update predictions when graph structures evolve or new nodes appear.
Feature Handling: GNNs often struggle with high-cardinality categorical features common in insurance data (e.g., car brands, legal forms), as aggregating these via averaging operations is often meaningless.
Over-smoothing: Deep GNNs can suffer from over-smoothing, where node representations become indistinguishable as message-passing layers increase.
Interpretability: Regulatory requirements in the insurance industry demand transparent audit trails. GNNs often produce opaque embeddings that obscure the specific evidence (nodes/edges) driving a fraud prediction.

Consequently, gradient-boosted tree (GBM) methods on tabular data remain dominant due to their robustness to class imbalance and categorical features, but they lack the ability to natively incorporate graph structure.

Methodology: G-GBM

The authors propose G-GBM (Graph-Gradient Boosted Machine), a novel inductive framework that extends gradient-boosted decision trees to heterogeneous, dynamic graphs. The method bridges the gap between the predictive power of GBMs and the relational modeling of graphs without sacrificing interpretability.

Core Mechanism

G-GBM operates by transforming the graph structure into a set of explicit, featurized paths within a node's local neighborhood (ego-net), which are then fed into a standard gradient boosting algorithm (specifically LightGBM).

Metapath Sampling: For a target node $v$ , the algorithm samples simple paths of a fixed length $n$ within its $n$ -hop ego-net. These paths follow specific metapaths (sequences of node and edge types).
Feature Concatenation: Instead of aggregating neighbor features into a single vector (as GNNs do), G-GBM concatenates the raw node and edge features encountered along each sampled path. This preserves the granularity of high-cardinality categorical data.
Probability-Weighted Learning: Each path is assigned a weight based on the probability of a random walker traversing that path. These weights are used as case weights during the training of the decision trees.
Weighted Gini Impurity: The tree construction utilizes a weighted Gini impurity criterion. The impurity calculation incorporates the path probabilities, ensuring that paths with higher likelihoods contribute more significantly to the split decisions.
Inductive Prediction: The final fraud probability for a node is the weighted sum of the predictions from the trees trained on each metapath. This allows the model to generalize to new nodes and evolving graph structures without retraining the entire embedding space.

Interpretability

Because the model relies on explicit feature concatenations rather than opaque embeddings, it retains full compatibility with SHAP (SHapley Additive exPlanations) values. This allows investigators to trace a fraud prediction back to specific nodes, edges, and features within the graph, satisfying regulatory audit requirements.

Key Contributions

The paper outlines four primary contributions:

Theoretical: G-GBM provides an inductive framework for supervised learning on heterogeneous graphs. The authors argue it offers a formal Pareto dominance guarantee over its tabular counterpart (LightGBM), as the inclusion of graph structure can only improve or maintain performance, never degrade it.
Methodological: The method introduces a theoretically grounded bridge between random-walk path semantics and gradient boosting via probability-weighted metapath featurization and adapted Gini impurity. This addresses the open problem of applying tree-based learning to heterogeneous, dynamic graphs.
Empirical: On real-world insurance fraud data, G-GBM achieves strong predictive performance while retaining the practical advantages of GBMs (handling categorical features, missing data, and class imbalance) and providing path-level SHAP audit trails.
Reproducibility: The authors release the full implementation on GitHub and an anonymized, real-world Belgian insurance fraud graph on Kaggle, providing a rare proprietary-grade benchmark for the community.

Experimental Results

The authors evaluated G-GBM on two datasets: a proprietary Belgian insurance dataset (involving companies and administrators) and an open-source healthcare provider (HCP) fraud dataset.

Proprietary Insurance Dataset

Performance: G-GBM outperformed both the tabular LightGBM baseline and several inductive HGNN baselines (HinSAGE, HAN, HGT).
- For Company nodes, G-GBM achieved an AUC-PR of 0.77, surpassing LightGBM (0.75) and HinSAGE (0.76).
- For Administrator nodes, where head-node features were sparse, the improvement was more pronounced. G-GBM achieved an AUC-PR of 0.46, significantly outperforming LightGBM (0.38) and all GNN baselines.
Interpretability: SHAP analysis revealed that for administrators, features from the second-degree neighborhood were highly significant, a signal the baseline GBM could not capture.
Efficiency: G-GBM was slower than the pure tabular LightGBM but significantly faster to train than the HGNN baselines (e.g., HinSAGE took ~4300s vs. G-GBM's ~28s for company nodes).

Healthcare Provider (HCP) Dataset

Performance: In this dataset, where head-node features were highly predictive, G-GBM performed on par with LightGBM and HGT (AUC-ROC ~0.94).
Observation: The addition of neighborhood features did not significantly boost performance over the tabular baseline, suggesting that for this specific dataset, the fraud signal was already captured by the intrinsic node features. However, G-GBM maintained competitive performance without the over-smoothing issues observed in some GNNs.
Computational Cost: Training time for G-GBM was higher than on the insurance dataset due to the HCP graph's higher average degree, which increased the number of possible metapaths.

Significance and Claims

The paper positions G-GBM as a pragmatic and powerful solution for the insurance industry, balancing the need for high predictive accuracy with strict regulatory demands for explainability.

Regulatory Compliance: Unlike GNNs, which produce "black box" embeddings, G-GBM offers a clear audit trail. Investigators can see exactly which neighboring entities and specific features (e.g., a shared address or a specific legal form) contributed to a fraud score.
Robustness to Data Characteristics: By leveraging the strengths of gradient boosting, the method naturally handles the high-cardinality categorical variables and class imbalance typical of insurance data, which often degrade GNN performance.
Inductive Capability: The method is designed for dynamic environments where new nodes and edges are constantly added, avoiding the need for full re-embedding required by transductive methods.

The authors conclude that while G-GBM faces computational challenges in highly connected graphs due to dimension expansion, it successfully avoids the over-smoothing pitfalls of deep GNNs and provides a superior trade-off between detection power, interpretability, and training efficiency for insurance fraud detection.