Efficient Estimation of Shortest-Path Distance Distributions to Samples in Graphs
This addresses bias and fairness issues in graph machine learning for researchers and practitioners working with large graph datasets, though it is incremental as it builds on prior work on distance-based indicators.
The paper tackles the problem of evaluating how graph sampling methods affect the distribution of shortest-path distances to sampled nodes without performing actual sampling, presenting an efficient framework that is faster than empirical methods and remains accurate for comparison-based tasks.
As large graph datasets become increasingly common across many fields, sampling is often needed to reduce the graphs into manageable sizes. This procedure raises critical questions about representativeness as no sample can capture the properties of the original graph perfectly, and different parts of the graph are not evenly affected by the loss. Recent work has shown that the distances from the non-sampled nodes to the sampled nodes can be a quantitative indicator of bias and fairness in graph machine learning. However, to our knowledge, there is no method for evaluating how a sampling method affects the distribution of shortest-path distances without actually performing the sampling and shortest-path calculation. In this paper, we present an accurate and efficient framework for estimating the distribution of shortest-path distances to the sample, applicable to a wide range of sampling methods and graph structures. Our framework is faster than empirical methods and only requires the specification of degree distributions. We also extend our framework to handle graphs with community structures. While this introduces a decrease in accuracy, we demonstrate that our framework remains highly accurate on downstream comparison-based tasks. Code is publicly available at https://github.com/az1326/shortest_paths.