（GraphGeo）Connecting the Hosts: Street-Level IP Geolocation with GraphNeural Networks

ABSTRACT

确定IP地址的地理位置对于从目标广告到防止欺诈的一系列位置感知应用程序（location-aware applications ）非常重要。大多数传统的基于测量（traditional measurement-based）和最近基于学习的方法（learning-based methods）要么关注的是拓扑的有效利用（efficient employment of topology），要么是利用数据挖掘（data mining）在公开的资源中寻找目标IP的线索。基于现有工作的局限性，我们提出了一个名为GraphGeo的新框架，该框架通过图神经网络的应用，为街道级IP地理定位（street-level IP geolocation）提供了一个完整的处理方法。它将IP主机知识（IP hosts knowledge）和邻域关系（kinds of neighborhood relationships）集成到图中，以推断空间拓扑（rspatial topology ），用于进行高质量的地理位置预测。我们明确地考虑和缓解了（explicitly consider and alleviate）在复杂的网络环境中普遍存在的网络抖动和拥塞（network jitter and congestion）所造成的不确定性的负面影响。对三个大型真实世界数据集的广泛评估表明，与最先进的方法相比，GraphGeo显著地减少了地理位置错误。此外，拟议的框架已作为在线服务（online service）在网络平台（online service）上部署了6个月。

CCS CONCEPTS

网络（Networks）→基于位置的服务（Location based services）；计算方法（Computing methodologies）→空间和物理推理（Spatial and physical reasoning）。

KEYWORDS

IP地理定位（IP Geolocation），网络拓扑（Network Topology），图神经网络（Graph Neural Networks），不确定性推理（Uncertain Inference），普适计算（Ubiquitous Computing）

1 INTRODUCTION

IP地址（IP address）是分配给连接到互联网的每个主机的唯一标识符（a unique identifier），它作为个人可识别信息（personally identifiable information）和虚拟位置寻址（virtual location addressing）。IP定位（IP geolocation）指的是将一个真实世界的地理位置分配给给定的IP地址，这个地理位置通常由（经度、纬度）元组表示。这是人们关注用户访问特定服务的许多应用程序的问题，从有针对性的营销到防止欺诈。通过对用户的精确地理定位，平台还可以提供各种个性化的服务——例如，在线定向广告可以在用户的邻近范围内（within user’s proximity）推荐餐馆。无处不在的基于位置的服务长期以来一直被认为是互联网面临的一个重要挑战。

虽然IP地理定位有了充分的研究和影响，但它仍然是一个具有挑战性的问题，因为它很难收集到可用的和可靠的信息（since it is hard to collect available and reliable information.）。早期旨在地理定位IP地址（geolocate IP addresses）的工作直接利用在公共数据库中记录的线索，如WHOIS和域名系统（DNS）[26,27]。这些工作维护了公共记录和地理位置[27]之间基于规则的映射关系，由于公共资源已经过时，因此比较粗糙且不可靠。

[26] David Moore, Ram Periakaruppan, Jim Donohoe, and Kimberly Claffy. 2000. Where in the world is netgeo.caida.org?. In INET.   

[27] Venkata N. Padmanabhan and Lakshminarayanan Subramanian. 2001. An investigation of geographic mapping techniques for internet hosts. In SIGCOMM. 173–185. 

还有其他研究结果利用多个可控主机（several controllable hosts ）探测的网络测量（exploiting network measurements probed），如ping值和跟踪列表（traceroute list）[17,33]。这些方法主要将以几个圆为中心的圆的交点作为位置边界(cf。图1(a))。

[17] Ethan Katz-Bassett, John P John, Arvind Krishnamurthy, David Wetherall, Thomas Anderson, and Yatin Chawathe. 2006. Towards IP geolocation using delay and topology measurements. In SIGCOMM. 71–84.  

[33] Yong Wang, Daniel Burgener, Marcel Flores, Aleksandar Kuzmanovic, and Cheng Huang. 2011. Towards Street-Level Client-Independent IP Geolocation.. In NSDI. USENIX.    

图1：两种主流地理定位方法的核心思想（左）和我们提出的GraphGeo（右）。

经过几十年的发展，目前存在着各种基于机器学习和神经网络的IP地理定位模型。有些人将度量视为特征（measurements as features），以确定包含目标IP的区域（a region containing the target IP）作为分类任务[6]，或预测其经度和纬度（longitude and latitude）作为回归任务[15]。利用基于学习的模型（learning-based models），他们可以通过集成和分析多源数据来发现更有益的地理定位线索。它可以很容易地将特征转换为高维空间进行进一步分析，学习常识，并在大规模数据集训练后进行地理定位预测。

[6] Brian Eriksson, Paul Barford, Joel Sommers, and Robert Nowak. 2010. A learning-based approach for IP geolocation. In PAM. 171–180. 

[15] Hao Jiang, Yaoqing Liu, and Jeanna N Matthews. 2016. IP geolocation estimation using neural networks with stable landmarks. In INFOCOM WKSHPS. 170–175.   

现有的IP地理定位工作的关键思想如图1(a)和(b)，所示尽管结果令人鼓舞，但他们也有一定的缺点。一方面，传统的基于测量的方法的实际部署（practical deployments ）受到困难的物理距离估计（physical distance estimations） 和未知的空间拓扑关系（unknown spatial topological relationships）的影响。另一方面，基于学习的方法通常将IP知识（IP knowledge）和度量（measurements）独立地视为表格数据（tabular data），并将其输入到学习模型中，如神经网络作为行向量。然而，这种范式忽略了与IP主机的地理定位密切相关的结构化信息。（structured information which is strongly related to geolocations of IP hosts. ）此外，各自的工作没有很好地考虑网络拥塞、抖动、拓扑约束（network congestion, jitter, topology constraints）等引起的测量不确定性（uncertainty of measurements），使得它们的模型在现实IP地理定位中不够稳健。

[21] Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR.   

近年来，图神经网络（GNN）[21]在一系列的应用中蓬勃发展。为了解决以前工作的局限性，我们做了一项开创性的努力，利用图结构来连接独立的IP主机（independent IP hosts），并将网络拓扑合并到它们的街道级IP地理定位特性（for street-level IP geolocation）中（incorporate network topology into their features）。有三个主要的挑战： (1)一个图包含哪些IP主机？(2)如何建立合适的图形结构？(3)由于网络测量总有噪声和不确定性，因此如何稳健地聚合节点特征？为了解决这些问题，我们提出了一个名为GraphGeo的基于图的框架，它为街道级IP地理定位提供了一个完整的系统。GraphGeo首先采用一种基于规则的方法（a rule-based approach），结合路由器信息（routers information）——受测量误差的影响较小（less influenced by measurement errors）——来确定哪些IP主机属于图（to determine which graph IP hosts belong to）。然后，从拓扑和语义的角度（topological and semantic perspectives）建立IP主机之间的邻域关系（neighborhoods relationship），形成加权图（weighted graph）并将其连接起来。最后，目标IP（target IP）用一个具有不确定性感知的GNN（uncertainty-aware GNN）来聚合其邻居的知识（aggregates knowledge of its neighbors），以获得准确和稳定的输出。

我们的GraphGeo从一个新的角度解决了街道级IP地理定位问题，它根据结构化信息（structured information）结合了目标IP的知识（knowledge of target IPs ）和地标拓扑（topologies of landmarks），同时联合利用了网络规则和数据驱动的模型（networking rules and data-driven models.）。综上所述，这项工作的主要贡献有四个方面：

•我们提出了一个新的框架GraphGeo，它为将图神经网络应用于街头IP地理定位问题提供了一个完整的管道。它包含了IP主机的特征（IP host features ）和邻域关系的类型（kinds of neighborhoods relationships），允许我们提取具有图结构的公共知识和拓扑（extract the common knowledge and topology with graph structure），而不是学习线性特征交互或独立处理每个IP主机。

•我们通过提出一个具有类型感知能力的GNN（uncertainty-aware GNN）来确定目标IP地址（target IP address）。通过在概率空间（probabilistic space）中进行连续、灵活的推理，关注了复杂网络环境中普遍存在的网络拥塞和抖动所引起的不确定性和噪声。

•对三个真实数据集上的广泛实验评估证明了我们的框架的优越性，它不仅显著提高了街道级IP地理定位的准确性，而且还提供了模型行为的解释（interpretations of the model behaviors）。

•我们的框架已经成功部署在Aiwen Tech（https://en.ipplus360.com/ home/）的网络平台上生产超过6个月，该平台提供在线API请求和离线地理定位数据库服务。迄今为止，它已经为2700多家公司和客户提供了服务。

2 RELATED WORK

2.1 IP Geolocation

许多研究已经解决了IP地理定位预测的问题。现有的工作大致可以分为两类：基于数据挖掘的方法和基于测量的方法。

Data mining-based methods

基于数据挖掘的方法（Data mining-based methods）依赖于在公开的资源中挖掘位置线索来对目标IP（target IP）进行地理定位。其中一些数据分析了来自与IP相关的数据库，如WHOIS数据库和DNS的数据。

例如，Moore等人[26]提出了NetGeo，其中包括一组Perl脚本(Perl scripts)，用于地址解析(address parsing)和启发式分析(heuristic analysis)WHOIS记录，以进行IP地理位置预测。[27]等人将目标主机的DNS名称（DNS names of target hosts）和边界网关协议（BGP)表中的前缀信息（prefix information）合并来推断地理位置。赫芬克等人[14]收集宿主域内（host domain）的地理提示（geographic hints），并将这些字符串（例如，机场代码）与地球物理位置(geophysical locations)联系起来。其他（主体）作品主要从网页和社交媒体平台的语义或多媒体信息(semantic or multimedia information )中提取地理定位线索。Liu等人的[25]利用来自社交网络的签到记录(check-in records)来学习IP、用户(user)和地理位置（geolocation）之间的映射模型(mapping model)。Wang等人[34]从网页中提取指示线索（location-indicating clues）的位置，并根据这些线索定位网络服务器（web servers）。Li等人[35]和Wang等人[23]定期监控（periodically monitor ）托管实时网络摄像头（hosting live webcams）的网站，并使用自然语言处理技术提取IP地理定位。

[26] David Moore, Ram Periakaruppan, Jim Donohoe, and Kimberly Claffy. 2000. Where in the world is netgeo.caida.org?. In INET. 

[27] Venkata N. Padmanabhan and Lakshminarayanan Subramanian. 2001. An investigation of geographic mapping techniques for internet hosts. In SIGCOMM. 173–185. 

[14] Bradley Huffaker, Marina Fomenkov, and KC Claffy. 2014. DRoP: DNS-based router positioning. Comput. Commun. Rev. (2014), 5–13. 

[25] Hao Liu, Yaoxue Zhang, Yuezhi Zhou, Di Zhang, Xiaoming Fu, and KK Ramakrishnan. 2014. Mining checkins from location-sharing services for client-independent ip geolocation. In INFOCOM. 619–627.   

[34] Yucheng Wang, Hongsong Zhu, Jinfa Wang, Jie Liu, Yong Wang, and Limin Sun. 2020. XLBoost-Geo: An IP Geolocation System Based on Extreme Landmark Boosting. arXiv:2010.13396.

[23] Qiang Li, Zhihao Wang, Dawei Tan, Jinke Song, Haining Wang, Limin Sun, and Jiqiang Liu. 2021. GeoCAM: An IP-Based Geolocation Service Through Fine-Grained and Stable Webcam Landmarks. IEEE/ACM Trans. Networking (2021), 1798–1812. 

[35] Zhihao Wang, Qiang Li, Jinke Song, Haining Wang, and Limin Sun. 2020. Towards IP-based geolocation via fine-grained and stable webcam landmarks. In WWW. 1422–1432.

尽管现有的数据挖掘方法的性能很好，但由于网络数据采集的被动方式（passive way），现有的数据挖掘方法通常受到信息不可靠和不完整（unreliable and incomplete information）的限制，容易导致不准确的地理定位结果。

Measurement-based methods

基于测量的方法（Measurement-based methods ）利用探测主机和目标IPs（probing hosts and target IPs）之间的网络延迟和拓扑结构（network latency and topology）来估计它们的距离并推断目标的地理位置。

这一想法是基于网络延迟（network latency）和地理距离（geographical distance）之间存在相关性（existent correlation）的假设，这已经在[41]中得到了证明。Wang等人[33]设计了一个分层系统（hierarchical system），通过延迟测量（latency measurement）从大的粗粒度尺度（large, coarse-grained scale）开始，然后升级该尺度中外部信息（external information）的使用，以确定目标IP。同样，Jiang等人[15]首先基于延迟相似度（delay similarity ）确定一个大的区域，然后通过神经网络利用局部地标信息（local landmarks information）来预测地理位置。此外，也有研究旨在产生更准确的延迟-距离关系（latency-distance relationships）。例如，Laki等人，[22]一起处理所有的地标点（landmark points），并推导出一个共同的概率延迟-距离模型（probabilistic delay-distance model）。希尔曼等人[12,13]考虑了不同的层网络级别（Tier network levels），并引入了一个对数曲线（logarithmic curve）来描述延迟-距离关系（delay-distance relationships）。

[41] Artur Ziviani, Serge Fdida, José F De Rezende, and Otto Carlos MB Duarte. 2005. Improving the accuracy of measurement-based geographic location of Internet hosts. Comput. Networks (2005), 503–523. 

[33] Yong Wang, Daniel Burgener, Marcel Flores, Aleksandar Kuzmanovic, and Cheng Huang. 2011. Towards Street-Level Client-Independent IP Geolocation.. In NSDI. USENIX.