Using Graph Neural Networks and the Internet Graph Topology to Learn Autonomous System Relationships
Abstract
The Internet is built upon thousands of interconnected Autonomous Systems (ASes) that exchange routing information through the Border Gateway Protocol (BGP). The commercial relationships between ASes classified as peer-to-peer (P2P), customer-to-provider (C2P), or provider-to-customer (P2C), shape the paths that packets follow across the network. However, this information is rarely disclosed publicly and must be inferred from indirect sources. Accurate inference of AS relationships is essential for analyzing the Internet structure, understanding routing policies, and detecting anomalies. In this work, we propose using Graph Neural Networks (GNNs) as a novel approach to this inference task. We construct an AS-level Internet graph with 79K nodes and 438K edges from BGP Routing Information Bases (RIBs) collected via RouteViews and RIPE RIS, enriching node representations with attributes from PeeringDB and one-hot encoding. We present a GNN approach that evaluates two GNN architectures (GCN and GraphSAGE) end-to-end, with the GNN and an MLP decoder jointly trained for relationship classification. We compare against established graph embedding baselines, DeepWalk and BGP2Vec. The best model, a GCN + MLP architecture with PeeringDB attributes, achieves 0.952 accuracy and 0.950 macro-F1, surpassing BGP2Vec in macro-F1 (0.946) while requiring half the training time (10 vs 20 min), suggesting that GNNs offer a scalable and structurally motivated alternative for AS relationship inference.
