<figure><img src="image_1.png" /></figure>

HAL
open science

# Isolation Forest Meets Link Prediction: A Novel Framework for Backbone Extraction

Ali Yassin, Hocine Cherifi, Hamida Seba, Olivier Togni

► To cite this version:

Ali Yassin, Hocine Cherifi, Hamida Seba, Olivier Togni. Isolation Forest Meets Link Prediction: A Novel Framework for Backbone Extraction. International Conference on Complex Networks, May 2025, Fortaleza, Brazil. hal-05291560

HAL Id: hal-05291560

https://hal.science/hal-05291560v1

Submitted on 1 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Isolation Forest Meets Link Prediction: A Novel Framework for Backbone Extraction

Ali Yassin¹,³, Hocine Cherifi², Hamida Seba³, and Olivier Togni¹

¹ Laboratoire d'Informatique de Bourgogne, Université de Bourgogne, Dijon, France

² ICB UMR 6303 CNRS, Université de Bourgogne, Dijon, France

³ Univ Lyon, UCBL, CNRS, INSA Lyon, LIRIS, UMR5205, F-69622 Villeurbanne, France

## Abstract

Complex networks appear across various disciplines, including social sciences, biology, finance, and transportation. Their complexity often obscures critical structural and functional relationships, making analysis difficult. Backbone extraction simplifies networks by preserving key connections while reducing complexity. Traditional backbone extraction methods apply fixed thresholds on computed scores, making them highly sensitive to parameter choices. In a previous work we introduced similarity-based and embedding-based link prediction techniques for backbone extraction [1]. However, these methods depend on predefined thresholds. They preserve either the top or bottom fraction of scores and discard the remaining fraction, which may contain structurally significant interactions. To overcome these limitations, this study presents a novel backbone extraction framework integrating link prediction with anomaly detection.

The upper panel in Figure 1 illustrates the backbone extraction process. Each edge of the processed network is temporarily removed, and its existence probability is estimated using a link prediction based similarity metric. The edge is then reinserted to maintain the network structure. The computed scores undergo log transformation and normalization to reduce skewness and ensure consistency in scale. Finally, the Isolation Forest algorithm analyzes the scores and identifies anomalous edges [2]. These identified edges form the network backbone.

To illustrate the proposed framework, we apply it to the Zachary's Karate Club network using two well-known similarity-based link prediction methods: Preferential Attachment and Local Path Index. The Preferential Attachment backbone retains 17 nodes (50% of the original network) and 12 edges (15.4% of total edges), while the Local Path backbone preserves a slightly larger subset, with 20 nodes (58.8% of the original network) and 20 edges (25.6% of total edges). In Figure 1, edge colors represent Preferential Attachment normalized scores, where yellow edges correspond to high scores and blue edges correspond to low scores. The figure clearly shows that the backbone edges are located at the extremes, retaining only the highest and lowest scoring edges. This dual retention strategy ensures that both central and peripheral interactions are included, leading to a more representative and interpretable backbone extraction. We validate these observations by examining the distribution of normalized scores, confirming that the extracted backbone consists of edges with extreme scores while discarding intermediate-score edges. Furthermore, the choice of similarity function influences the interpretation of the extracted backbone: Preferential Attachment highlights the social hierarchy, while Local Path Index emphasizes redundant short paths and localized connectivity.

Next, we evaluate the proposed method against widely used backbone extraction techniques, including the Disparity Filter and High Salience Skeleton [3]. The experiment is conducted on two networks: Global Airports and Les Misérables. Several evaluation metrics are employed to assess the effectiveness of each method, including edge retention, node retention, reachability, transitivity, and clustering coefficient deviations. These metrics provide a comprehensive evaluation of how well each approach preserves key network properties. The results, summarized in the table of Figure 1, indicate that no single method is universally superior. However, the Local Path Index backbone balances global reachability and local clustering. In contrast, the High Salience Skeleton excels at retaining the original nodes.

Lastly, we assess the ability of the proposed framework to preserve the original edge weight and node degree distributions in the networks from the previous experiment. Results show that the Local Path backbone closely matches the original degree distribution in both networks. In contrast, the Preferential
Attachment and High Salience Skeleton backbones align more closely with the original weight distribution in the Les Misérables and Global Airports networks, respectively.

The proposed framework offers a scalable, threshold-free approach to dynamic backbone extraction across diverse networks. Its flexibility in selecting similarity functions enables tailored interpretations, making it a versatile tool for network analysis. Future research could explore learning-based link prediction methods to further enhance adaptability.

<figure><img src="image_3.png" /><figcaption>Figure 1: The upper panel illustrates the backbone extraction framework in the Zachary's Karate Club network. The framework integrates link prediction and anomaly detection. Edges are scored, transformed, and analyzed using the Isolation Forest algorithm to identify structurally significant links. The lower left panel presents a table summarizing the topological properties of the extracted backbones using Preferential Attachment (PA), Local Path Index (LP), High Salience Skeleton (HSS), and Disparity Filter (DF) for the Global Airports and Les Misérables networks. The lower right panel displays the cumulative distributions of edge weights and node degrees for the Global Airports original network and the extracted backbones, with the Kolmogorov-Smirnov (KS) statistic shown in the legend.</figcaption></figure>

## References

[1] Ali Yassin, Hocine Cherifi, Hamida Seba, and Olivier Togni. Network backbone extraction using link prediction. In *2024 IEEE Workshop on Complexity in Engineering (COMPENG)*, pages 1–6, 2024.

[2] Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation forest. In *2008 Eighth IEEE International Conference on Data Mining*, pages 413–422. IEEE, 2008.

[3] Ali Yassin, Abbas Haidar, Hocine Cherifi, Hamida Seba, and Olivier Togni. An evaluation tool for backbone extraction techniques in weighted complex networks. *Scientific Reports*, 2023.