Learning to Rank Critical Road Segments via Heterogeneous Graphs with Origin-Destination Flow Integration

Ming Xu, Jinrong Xiang, Zilong Xie, Xiangfu Meng · 2025

Read Learning to Rank Critical Road Segments via Heterogeneous Graphs with Origin-Destination Flow Integration by Ming Xu, Jinrong Xiang, Zilong Xie, Xiangfu Meng (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-19199.txt.

Introduction

Ming Xu and co-authors rank which road segments a city can least afford to lose, and they feed the judge the city's actual travel patterns. Earlier learning-to-rank methods judged a road by the map alone, ignoring where trips start and end and which routes they take, so long-range effects escaped them. Their 2025 paper builds a graph with three kinds of nodes: origins and destinations, routes, and the road network itself.

Attribute-guided graphs add a second view in which a road's features become nodes in their own right, linking roads that serve similar functions. A joint random walk samples both graphs, and a transformer turns the sampled walks into embeddings that carry flow, route, and function together. A listwise ranking loss then orders the segments. On three simulated networks of different sizes, the method beat the state of the art across the tests.

Catalog record

CREATORMing Xu, Jinrong Xiang, Zilong Xie, Xiangfu Meng
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE82 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-19199

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning to Rank Critical Road Segments via Heterogeneous Graphs with Origin-Destination Flow Integration Ming Xu, Jinrong Xiang, Zilong Xie, Xiangfu Meng Abstract Existing learning-to-rank methods for road networks often fail to incorporate origin–destination (OD) flows and route information, limiting their ability to model long-range spatial dependencies. To address this gap, we propose HetGL2R, a heterogeneous graph learning framework for ranking road-segment importance. HetGL2R builds a tripartite graph that unifies OD flows, routes, and network topology, and further introduces attribute-guided graphs that elevate node attributes into explicit nodes to model functional similarity. A heterogeneous joint random walk algorithm (HetGWalk) jointly samples both graph types to generate context-rich node sequences. These sequences are encoded using a Transformer to learn embeddings that capture long-range structural dependencies induced by OD flows and route configurations, as well as functional associations derived from attribute similarity. Finally, a listwise ranking strategy with a KL-divergence loss evaluates and ranks segment importance. Experiments on three SUMO-generated simulated networks of different scales show that, against state-of-the-art methods, HetGL2R achieves average improvements of approximately 7.52%, 4.40% and 3.57% in ranking performance. 1 1 1 Our code and data are available at : https://github.com/iCityLab/HetGL2R. 1 Introduction Efficient and resilient road networks are essential for ensuring smooth urban mobility and public safety. When a single road segment becomes congested or blocked, the resulting disruption often propagates along multiple routes, leading to large-scale delays or even citywide paralysis. Therefore, identifying critical road segments—those whose failure would significantly degrade overall network performance—is of great importance for traffic management and infrastructure planning ( Xu et al., 2018 ) . Figure 1 : A small simulated road network used for illustration. The network consists of 11 nodes ( v ) and 11 directed edges ( e ), with two origin–destination (OD) pairs: <v_{1} , v_{4}> with 300 vehicles traveling along a single path, and <v_{8} , v_{7}> with 500 vehicles distributed over two alternative paths. Red and blue arrows indicate the routing paths associated with the two OD pairs, respectively. Prior studies on road-network criticality were primarily based on complex network theory, in which centrality measures (e.g., early betweenness centrality ( Freeman, 1977 ) and PageRank ( Agryzkov et al., 2012 ) , and more recent methods such as IDME ( Sun et al., 2023 ) , EPC ( Ullah et al., 2024 ) , OVED-Rank ( Ullah et al., 2025 ) , LSS ( Ullah et al., 2023 ) , and GLC ( Ruan et al., 2025 ) ) were used to quantify the structural importance of nodes. These approaches are intuitive and easy to interpret but fail to incorporate the rich attribute features and dynamic traffic behaviors associated with each road segment. In reality, a segment’s criticality depends on multiple factors such as traffic volume, number of lanes, and functional hierarchy, many of which are neglected in purely topological metrics. Some studies have attempted to combine centrality measures with attribute features (e.g., study ( Agryzkov et al., 2012 ) ), but most rely on manually tuned parameters, limiting their scalability and generalization to large real-world networks. In recent years, graph neural network (GNN)–based learning methods ( Fan et al., 2020 ; Xu and Zhang, 2024 ) have attracted increasing attention in the field of node importance assessment. These models integrate node attributes with local topological information through message-passing mechanisms to learn effective node embeddings. However, due to the limited receptive field of GNNs, they struggle to capture the long-range path dependencies commonly present in traffic flows, which limits their performance in critical road segment ranking tasks. In transportation networks, the global influence of a road segment is largely shaped by origin–destination (OD) flows, which quantify the travel demand between each OD pair. The OD flows determine which paths are utilized and how traffic load is distributed, thereby shaping each segment’s functional role and criticality ( Guo et al., 2025 ; Xing et al., 2025 ; Wang et al., 2024 ) . For instance, if a segment lies on the shortest paths of multiple high-demand OD pairs, any incident or restriction there can induce congestion that propagates upstream along the affected OD paths, leading to severe network-wide delays. Conversely, a peripheral segment carrying a similar traffic volume but serving only a few OD flows would have a far more limited systemic impact if disrupted. As illustrated in Figure 1 , a simulated road network contains two OD flows, <v_{1} , v_{4}> and <v_{8} , v_{7}> . When an incident occurs at node v_{11} , congestion propagates upstream along the path of OD flow <v_{8} , v_{7}> to nodes v_{10} and v_{9} . This forces some travelers to reroute, thereby increasing the congestion risk on distant segments v_{5} and v_{6} . In contrast, segments v_{2} and v_{3} remain largely unaffected as they do not carry the affected OD flows. This example highlights that the influence among road segments is fundamentally governed by the OD flows they serve and the paths they form. Conceptually, spatial dependencies in a road network stem from functional interactions among OD flows, paths, and segments, rather than from physical connectivity. Consequently, the OD-dominated functional relationships are pivotal for evaluating node criticality. Existing graph learning approaches face two fundamental limitations in this task. First, they primarily learn structural representations from the physical topology of road networks while overlooking the functional structures shaped by OD flows. Second, their local neighborhood aggregation mechanism is constrained by network depth, resulting in limited receptive fields. As a result of these limitations, they struggle to capture long-range spatial dependencies and consequently fail to accurately model the impact patterns of local disruptions (e.g., an incident at node v_{11} )—where the scope of impact is dictated by the functional roles of segments within OD flows and paths, rather than by physical proximity. Although CRRank ( Xu et al., 2018 ) incorporates OD information to evaluate the functional importance of road segments, its reliance on manually designed aggregation rules and similarity metrics constrains its expressiveness and effectiveness, as it cannot learn complex interaction patterns in an end-to-end manner. To overcome these limitations, this paper proposes HetGL2R, a heterogeneous graph learning framework that integrates OD flow information for road-segment ranking. The key contributions of this study can be summarized as follows: 1. Methodological Innovation : HetGL2R constructs a tripartite graph (connecting OD pairs, paths, and road segments) to integrate the functional structure of the road network with its physical structure. Simultaneously, it introduces three attribute-node bipartite graphs—one each for OD pairs, paths, and segments—to explicitly model the attribute-based functional similarities. A joint random walk mechanism operates on these graphs collectively to sample context-rich node sequences, which are then processed by a Transformer encoder to learn the long-range dependencies and functional roles of segments for accurate criticality ranking. 2. Theoretical Insight : Our core insight is that spatial dependencies in traffic networks are governed by functional structure rather than physical topology. To capture this structure, we introduce a joint random walk that integrates two complementary perspectives: functional role relationships (OD-path-segment) and attribute-based functional similarities. Consequently, the model learns the underlying mechanisms of spatial dependency, thereby enabling accurate assessment of nodes’ spatial influence. 3. Practical Implication : Extensive evaluation on three simulated traffic network datasets

Read the complete text