GCN-Geo: A Graph Convolution Network-based Fine-grained IP Geolocation System

Shichang Ding, Xiangyang Luo, Jinwei Wang, Neal Naixue Xiong

TL;DR

This paper introduces GNN-Geo, a novel framework that leverages Graph Neural Networks (GNNs) to improve the accuracy and generalization of fine-grained IP geolocation. By treating network topology as a graph, GNN-Geo captures complex relationships that traditional methods miss, significantly outperforming existing state-of-the-art approaches.

What Problem Does This Paper Address?

Accurately pinpointing the geographic location of an IP address, especially at a fine-grained level (e.g., street-level), is crucial for various applications like localized advertising, content restriction, and cybercrime investigation. Existing methods fall into two main categories: rule-based and learning-based. Rule-based methods rely on hypothetical delay-distance relationships, which often fail to generalize across diverse network environments. While learning-based methods, like Multi-Layer Perceptrons (MLPs), offer better generalization, they struggle with the inherently graph-structured nature of computer networks. MLPs treat IP addresses as isolated entities, ignoring valuable information about network connections and topology, thus limiting their accuracy. This paper aims to bridge this gap by applying Graph Neural Networks (GNNs), which are specifically designed to handle graph-structured data, to the problem of fine-grained IP geolocation.

Methods

The core of GNN-Geo is its formulation of IP geolocation as an attributed graph node regression problem. The framework comprises four key components:

  • Preprocessor: This module takes raw network measurement data (primarily traceroute information) and transforms it into a graph representation. This involves identifying IP addresses as nodes and the links between them as edges, along with extracting attributes for both nodes (e.g., delay, IP address) and edges (e.g., edge delay).
  • Encoder: The encoder converts the initial node and edge attributes into low-dimensional embeddings, preparing them for the message-passing layers.
  • Message Passing (MP) Layers: This is where the GNN's power lies. Multiple MP layers iteratively refine node embeddings by aggregating information from neighboring nodes and edges. This process allows GNN-Geo to learn complex relationships and capture network topology, which is crucial for accurate geolocation. The paper specifically uses a Message Passing Neural Network (MPNN) as the base GNN model.
  • Decoder: The decoder takes the refined node embeddings and maps them to predicted latitude and longitude coordinates. To address convergence issues inherent in predicting coordinates across the entire globe, the authors propose an improved decoder that incorporates prior knowledge by scaling the output to a limited range (based on coarse-grained location estimates) and using batch normalization and sigmoid activation functions.

Datasets

The authors evaluated GNN-Geo on 8 real-world IPv4/IPv6 networks across North America, Asia, and Europe. These include:

  • New York State (NYS)
  • Hong Kong (HK)
  • Shanghai
  • Beijing
  • Tokyo
  • Tokyo (IPv6)
  • Berlin (IPv6)
  • Munich (IPv6)

Landmark data was collected using established methods for IPv4 and a novel approach for IPv6. In total, over 350,000 IPv4/IPv6 landmarks were used, with 11,654 being measurable fine-grained landmarks. The experiments utilized various training-validation-testing ratios (70%, 50%, 30%, and 10% for training) to assess generalization.

Key Insights and Ideas

  • Network Topology is Key: The paper strongly advocates that ignoring network connectivity and topology, as MLPs do, is a significant limitation for IP geolocation. GNNs, by their nature, excel at capturing these graph-based relationships.
  • Rule-based vs. Learning-based Trade-offs: While rule-based methods like SLG can achieve very high accuracy for specific cases (e.g., when delay directly correlates with distance), they falter significantly when these assumptions are violated. GNN-Geo, by learning from data, offers a more robust and generalized solution.
  • Decoder Design Matters: A standard GNN decoder (predicting raw latitude/longitude) is ill-suited for IP geolocation due to the vast output space and convergence difficulties. Incorporating coarse-grained location priors and activation functions like sigmoid is crucial for practical performance.
  • Edge Features are Important: The paper highlights that edge attributes (like link delay) are vital for IP geolocation, and MPNNs are well-suited to leverage these features, outperforming GCN and GAT in this context.

Key Results

GNN-Geo consistently outperformed state-of-the-art rule-based (SLG, Corr-SLG) and learning-based (MLP-Geo) baselines across all 8 tested networks.

  • Accuracy Improvement: On average, GNN-Geo achieved a 22.51% reduction in average error distance and a 21.05% reduction in median error distance compared to the best baselines when using a 70% training dataset.
  • Generalization: GNN-Geo demonstrated superior generalization capabilities, maintaining strong performance across diverse network environments where baselines varied significantly.
  • Decoder Impact: The proposed rule-informed decoder significantly improved performance, reducing average error distances from over 1,000 km (with vanilla MLP decoders) to under 30 km.
  • Training Data Sensitivity: While GNN-Geo generally performs well, its performance can be more affected by extremely sparse training data (e.g., 10% training ratio) compared to rule-based methods, suggesting a higher risk of overfitting.

Limitations and Future Work

  • Explainability: A common limitation of deep learning methods, GNN-Geo's results are less interpretable than rule-based methods, making it harder to diagnose why specific geolocation errors occur.
  • Computational Cost: GNN-Geo requires more computational resources for training compared to simpler methods.
  • Landmark Dependency: Like most measurement-based methods, GNN-Geo's performance is influenced by the availability and distribution of landmarks. Improving performance with fewer landmarks is a key area for future work.
  • Future Directions: The authors suggest exploring attention mechanisms, further investigating different GNN architectures, reducing training costs, and injecting more explainability into the framework.

Summary updated

Abstract

Rule-based fine-grained IP geolocation methods are hard to generalize in computer networks which do not follow hypothetical rules. Recently, deep learning methods, like multi-layer perceptron (MLP), are tried to increase generalization capabilities. However, MLP is not so suitable for graph-structured data like networks. MLP treats IP addresses as isolated instances and ignores the connection information, which limits geolocation accuracy. In this work, we research how to increase the generalization capability with an emerging graph deep learning method -- Graph Neural Network (GNN). First, IP geolocation is re-formulated as an attributed graph node regression problem. Then, we propose a GNN-based IP geolocation framework named GNN-Geo. GNN-Geo consists of a preprocessor, an encoder, messaging passing (MP) layers and a decoder. The preprocessor and encoder transform measurement data into the initial node embeddings. MP layers refine the initial node embeddings by modeling the connection information. The decoder maps the refined embeddings to nodes' locations and relieves the convergence problem by considering prior knowledge. The experiments in 8 real-world IPv4/IPv6 networks in North America, Europe and Asia show the proposed GNN-Geo clearly outperforms the state-of-art rule-based and learning-based baselines. This work verifies the great potential of GNN for fine-grained IP geolocation.
BibTeX
@article{ding2021gcn,
  author = {Shichang Ding and Xiangyang Luo and Jinwei Wang and Neal Naixue Xiong},
  title = {{GCN-Geo: A Graph Convolution Network-based Fine-grained IP Geolocation System}},
  journal = {IEEE Trans. Network Science \& Engineering},
  year = {2021},
  doi = {10.48550/arxiv.2112.10767},
}
Figure