Accurate and Stable AS Relationship Inference via Trusted Seeds and Semi-Supervised Learning

Autonomous System (AS) relationship inference is critical for understanding Internet topology and detecting routing anomalies, yet existing methods suffer from accuracy and stability issues. Current algorithms struggle with peer-to-peer (p2p) relationship inference due to insufficient visibility in BGP feeds and lack of robust heuristics, while exhibiting instability under changing vantage point (VP) deployments.We present Apollo, an accurate and stable AS relationship inference method using trusted seeds and semi-supervised learning. We first extract trusted AS relationships by using export policies in Internet Routing Registry (IRR) databases. We then apply the valley-free principle to infer relationships along AS paths using these trusted seeds. For remaining unlabeled links, we employ probabilistic label generation and ensemble learning to achieve balanced training and accurate inference. Our evaluations of BGP data from 2022 to 2024 show that, compared to current methods, Apollo reduces the overall error rates by 2.52×-3.85× and p2p relationship error rates by up to 11.25×. Apollo maintains superior stability with zero relationship transitions in two of the three categories under varying VP deployments. Applied to route leak detection, Apollo uncovers 2.10×-2.64× more historical route leak incidents than prior methods.