GraphSL: An Open-Source Library for Graph Source Localization Approaches and Benchmark Datasets

Junxiang Wang, Liang ZhaoJ. Open Source Softw 2024 · DOI · DBLP

TL;DR

GraphSL is a new open-source Python library designed to standardize the "inverse problem" of graph learning: identifying the original source of information (like a rumor or a virus) based on its current spread. By unifying state-of-the-art Graph Neural Network (GNN) methods with classic heuristics and standardized benchmark datasets, it provides a much-needed foundation for researchers tackling network security and epidemic modeling.

The Challenge of Source Localization

In network science, graph diffusion is a well-understood "forward" problem: if you start a rumor at a specific node, how will it spread through the network over time? However, the inverse problem—graph source localization—is significantly more complex. Given a snapshot of a network where several nodes are already "infected," the goal is to accurately identify "Patient Zero."

Comparison between the forward diffusion problem and the inverse source localization problem.

This capability is critical for real-world applications such as halting the spread of misinformation, tracking computer viruses, or identifying the root cause of a power grid failure. Until now, the field lacked a unified framework. Existing tools were often limited to specific diffusion models, lacked modern deep learning approaches, or failed to provide standardized benchmarks, making it difficult for researchers to compare new algorithms against established baselines.

The GraphSL Framework

GraphSL (Graph Source Localization) bridges this gap by implementing six major algorithms categorized into two distinct philosophies: Prescribed (heuristic-based) and GNN-based (learning-based) methods.

The hierarchical structure of the GraphSL library, categorizing methods into prescribed and GNN-based approaches.

1. Prescribed Methods (Heuristic-based)

These methods rely on hand-crafted rules and topological properties:

  • LPSI: Assumes sources are likely surrounded by a high proportion of infected nodes.
  • NetSleuth: Uses the Minimum Description Length principle to find the most "efficient" explanation for the observed spread.
  • OJC (Jordan Center): Identifies a set of nodes that cover all infected nodes within a minimum radius.

2. GNN-based Methods (Learning-based)

These methods leverage deep learning to capture complex topological patterns that heuristics might miss:

  • GCNSI: Combines LPSI with Graph Convolutional Networks to learn better source representations.
  • IVGD: An "invertible" approach that treats diffusion as a reversible process to back-calculate the source.
  • SLVAE: Uses Variational Autoencoders to approximate the source distribution based on prior knowledge of the network.

Standardized Benchmarking

To ensure robust evaluation, GraphSL includes six diverse benchmark datasets across different scales and topologies:

  • Social/Biological Networks: Karate Club (34 nodes), Dolphins (62 nodes), and Jazz Musicians (198 nodes).
  • Citation/Scientific Networks: Network Science (1,589 nodes) and Cora-ML (2,810 nodes).
  • Infrastructure: Power Grid (4,941 nodes).

The library is built to be "plug-and-play," returning a standardized Metric object for every test, which includes accuracy, precision, recall, F-score, and AUC. It also includes a diffusion_generation function, allowing users to simulate spreads using standard models like Independent Cascade (IC) or Linear Threshold (LT).

Key Insights and Impact

The primary contribution of GraphSL is the standardization of the evaluation pipeline. By providing a common API, the library allows researchers to focus on model architecture rather than data preprocessing or metric implementation. Unlike previous tools, GraphSL does not assume a specific diffusion model, making it more robust for simulating real-world scenarios where the exact "rules" of the spread might be unknown.

Limitations and Future Work

While GraphSL provides a robust starting point, challenges remain in scalability and dynamic networks. Real-world social networks involve millions of nodes, whereas current benchmarks peak at approximately 5,000. Additionally, the library currently focuses on static graph snapshots; future iterations will need to address networks where connections evolve over time. The long-term value of GraphSL depends on community adoption and the contribution of novel GNN architectures to the repository.

Summary updated

BibTeX
@article{wang2024graphsl,
  author = {Junxiang Wang and Liang Zhao},
  title = {{GraphSL: An Open-Source Library for Graph Source Localization Approaches and Benchmark Datasets}},
  journal = {J. Open Source Softw.},
  year = {2024},
  doi = {10.21105/joss.06796},
}
Figure