# Edge Ranking of Graphs in Transportation Networks using a Graph Neural Network (GNN)

arXiv: https://arxiv.org/abs/2303.17485 · HTML: https://mlsanity.com/paper/2303.17485/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 78 references that are in the map.
- First posted on arXiv 25 Mar 2023.

## Builds on (most cited first, 20 of 20)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [PageRank beyond the Web](https://mlsanity.com/paper/1407.5107/) (2014)
- [Estimating Node Importance in Knowledge Graphs Using Graph Neural Networks](https://mlsanity.com/paper/1905.08865/) (2019)
- [Learning to Identify High Betweenness Centrality Nodes from Scratch: A Novel Graph Neural Network Approach](https://mlsanity.com/paper/1905.10418/) (2019)
- [Joint Demand Prediction for Multimodal Systems: A Multi-task Multi-relational Spatiotemporal Graph Neural Network Approach](https://mlsanity.com/paper/2112.08078/) (2021)
- [KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation](https://mlsanity.com/paper/1604.08553/) (2016)
- [Searching for superspreaders of information in real-world social media](https://mlsanity.com/paper/1405.1790/) (2014)
- [Approximating Network Centrality Measures Using Node Embedding and Machine Learning](https://mlsanity.com/paper/2006.16392/) (2020)
- [Statistical physics of vaccination](https://mlsanity.com/paper/1608.09010/) (2016)
- [Scalable Betweenness Centrality Maximization via Sampling](https://mlsanity.com/paper/1609.00790/) (2016)
- [Centrality-based identification of important edges in complex networks](https://mlsanity.com/paper/1908.10667/) (2019)
- [Accurately Modeling Biased Random Walks on Weighted Graphs Using textitNode2vec+](https://mlsanity.com/paper/2109.08031/) (2021)

## Abstract (arXiv)

Many networks, such as transportation, power, and water distribution, can be represented as graphs. Crucial challenge in graph representations is identifying the importance of graph edges and their influence on overall network efficiency and information flow performance. For example, important edges in a transportation network are those roads that, when affected, will significantly alter the network's overall efficiency. Commonly used approach to finding such important edges is ``edge betweenness centrality'' (EBC), an edge ranking measure to determine the influential edges of the graph based on connectivity and information spread. Computing the EBC utilizing the common Brandes algorithm involves calculating the shortest paths for every node pair, which can be computationally expensive and restrictive, especially for large graphs. Changes in the graph parameters, e.g., in the edge weight or the addition and deletion of nodes or edges, require the recalculation of the EBC. As the main contribution, we propose an approximate method to estimate the EBC using a Graph Neural Network (GNN), a deep learning-based approach. We show that it is computationally efficient compared to the conventional method, especially for large graphs. The proposed method of GNN-based edge ranking is evaluated on several synthetic graphs and a real-world transportation data set. We show that this framework can estimate the approximate edge ranking much faster compared to the conventional method. This approach is inductive, i.e., training and testing are performed on different sets of graphs with varying numbers of nodes and edges. The proposed method is especially suitable for applications on large-scale networks when edge information is desired, for example, in urban infrastructure improvement projects, power, and water network resilience analyses, and optimizing resource allocations in engineering networks.