Local-Global Shortest Path Algorithms on Random Graphs, Enhanced with GNNs

I have concerns about the proposed method, as it appears to be effective only on small graphs, even when computing approximate distances. This limitation raises questions about its scalability and practical applicability to larger networks

We thank the reviewer for the useful feedback.

Note that we report results on larger networks, such as in Figures 4a, where the target graphs are ER graphs with as many as 12,800 nodes and 38,400 edges, and in Figures 4b and 4c, where the target graphs are real-world networks with as many as 28,281 nodes and 92,752 edges.

We do however understand the reviewer's criticism that the networks in our experiments are not sufficiently large, and agree that numerical results on larger graphs would be more compelling. For that reason, we plan to run transferability experiments on SNAP's Amazon co-purchasing network, with around 100k nodes, and Youtube network, with around 1 million nodes. These results will be included in Section 4.3 and reported as they become available.

The lack of experiments on larger networks in the original submission was primarily due to limited computational resources. Further, our paper's contribution is primarily theoretical---more specifically an analysis of approximation factors/embedding sizes for local-global algorithms on ER graphs. The addition of GNNs in the global step is a methodological contribution inspired by the fact that, on ER graphs, which can be thought of as being the average-case as opposed to the worst-case graphs in Das Sarma et al. (2010) and Bourgain (1985), the required embedding size (and thus the required GNN depth) are lower.

The presentation could benefit from improvements in several areas. For instance, the research problem [...] lacks clear motivation. The transferability of the GNN from small graphs to large graphs is not adequately justified. The experiments are limited [...].

Thank you for bringing this up.

Motivation and contributions. We will improve the writing to address this. The main contribution of our manuscript is an analysis of local-global shortest path (SP) algorithms on ER graphs. The idea was to initiate the study of average case analysis in the same spirit as the classical works in the theoretical CS literature for NP-hard problems. Our goal is slightly different though, since the underlying problem is not NP-hard, and the average case analysis is used for understanding possible reduction in complexity. We will add a few lines along this direction in the introduction to improve clarity in our stated motivation.

Transferability justification. The reason for leveraging GNN transferability has to do with the fact that the cost of training GNNs increases with the graph size. But indeed, it seems counterintuitive to use this property in shortest path computations since, as the graph size $n$ increases, the average path length increases as $\log (n)$ while the GNN depth remains fixed. To curb this limitation, we use the same GNN but increase the number of seed sets by running the GNN inference step $\sqrt{N}/\sqrt{n}$ times, where $n$ is the size of the smaller training graph and $N$ is the size of the large target graph. This corresponds to $\sqrt{N}/\sqrt{n}$ different random seed sets, whose embeddings are then appended to form a $\sqrt{N}$-dimensional embedding per node. We will better emphasize this step in the paper.

Experimental results. In addition to the experiments on synthetic ER graphs with up to 12,800 nodes and 38,400 edges, we have also reported results on real-world social networks with as many as 28,281 nodes and 92,752 edges. We could not fit all of these results in the main body due to the page limit, but the complete set of experiments is reported in the appendices.

We acknowledge that the graph sizes in our experiments are not as large, and we thank the reviewer for pointing that out. We will make our best effort to overcome this limitation in the coming week, resource-permitting; but we respectfully point out that this paper's contribution as primarily theoretical and, as such, the main goal of the numericals is illustrating the empirical manifestation of our theoretical findings.

This doesn't answer my question on " it is unclear how the node features contribute meaningfully in this context. Providing examples or intuitive explanations would help clarify this aspect."

The reason for this request is that, unlike many other graph properties, shortest path distances depend solely on graph structures and are independent of node features. Therefore, it is unclear what kind of node features was used in the experiments where GNNs were applied for local steps. Please include a concrete example to clarify this.

In order to train the GNN, we proceed as follows. We sample a training set of ER graphs of size $n$ and generate random input signals $\mathbf{X} \in \mathbb{R}^{n \times r}$ where each column corresponds to a seed and one-hot encodes which node is a seed for a given graph. The outputs have the same dimensions as the inputs, $\mathbf{Y} \in \mathbb{R}^{n \times r}$, and correspond to the exact shortest path distances between nodes $u \in V$ and seeds $s \in S$, i.e., $[\mathbf{Y}]_{us} = d(u,s)$.

I.e., the GNN can be thought of as being trained via imitation learning of breadth-first search.

I fail to see how this approach ensures GNN transferability. Unlike other graph properties, distance information does not appear to adhere to consistent patterns, as the same node can have varying distances to different nodes.

Thanks for this point. We use the same GNN but increase the number of seed sets by running the GNN inference step $\sqrt{N}/\sqrt{n}$ times, where $n$ is the size of the smaller training graph and $N$ is the size of the large target graph. This corresponds to $\sqrt{N}/\sqrt{n}$ different random seed sets, whose embeddings are then appended to form a $\sqrt{N}$-dimensional embedding per node.

The transferability paradigm we consider assumes that the graphs and the inputs are sampled from the same random graph-and-signal model (as in, e.g., Ruiz et al., 2020; Keriven et al., 2020; Levie et al., 2021). Transferability works because as the graph size increases, we increase the number of seeds, essentially making sure that the one-hot embeddings $\mathbf{x}_n$ are close to $\mathbf{x}_N$ in $L_2$.

In other words, the induced stepfunctions $X_n(u) = \sum_{i=1}^n [\mathbf{x}_n]_i \mathbb{I}(u \in [(i-1)/n,i/n])$ and respectively $X_m$ are close in $L_2$ norm. Moreover, intuitively increasing the number of seeds as the graph size increases ensures that the distance from nodes to any seed does not explode with the graph size.

While the authors claim superior performance, there is limited comparative analysis with other shortest-path based GNN approaches [1, 2, 3]. A more detailed benchmarking against established methods could validate the claims and provide a clearer context for the contributions.

Refs.:

[1] Shouheng et al., Local Vertex Colouring Graph Neural Networks, ICML 2023.

[2] Bohang et al., Rethinking the Expressive Power of GNNs via Graph Biconnectivity, ICLR 2023.

[3] Petar et al., Neural Execution of Graph Algorithms, ICLR 2020.

Thank you for raising this concern and for pointing us to these references. These are very relevant to our paper and will be cited in the revision.

Regarding performance, we respectfully point out that we do not claim superior performance. The main contribution of our manuscript is an analysis of local-global shortest path (SP) algorithms on ER graphs. The idea was to initiate the study of average case analysis in the same spirit as the classical works in the CS literature for NP hard problems. Our goal is slightly different though, since the underlying problem is not NP-hard, and the average case analysis is used for understanding possible reduction in complexity. We will add a few lines along this direction in the introduction to improve clarity in our stated motivation.

Since our theorems show that a lower embedding size is achievable on ER graphs, we were motivated to explore the possibility of replacing the breadth-first search (BFS) in the local step---which does not have a fixed width and depth for arbitrary graphs---with a GNN---which has fixed width and depth---as an empirical contribution to reduce computational complexity. The reasoning for using a GNN in the local step of such algorithms, as opposed to using GNNs for end-to-end SP computations, has to do with results by Loukas (2020) which show that it is impossible for GNNs with fixed depth and width to learn SPs on arbitrary graphs. This is a key difference between our paper and [1]--[3], which use GNNs to do end-to-end shortest path computations, so we do not believe an empirical comparison applies. We note however that it would be possible to incorporate any (local) GNN architecture, including those in [1]--[3], in the local step of Algorithm 1. We leave this as an interesting direction for future work. Thanks once again for the suggestion.

The theoretical analysis is strong but could be expanded to cover edge cases or graph types beyond Erdős-Rényi. This would enhance the generalizability of the findings and provide deeper insights into the algorithm’s performance.

This is a good point, and we acknowledge the limitations of focusing solely on ER graphs. However, our choice was deliberate: starting with simpler models like ER graphs allows us to develop the theoretical tools and insights needed for analyzing algorithms on more complex graph structures. Even for ER graphs, our analysis is nontrivial, as it depends on results about the growth of local neighborhoods.

We agree that extending this analysis to more realistic graph models is an important next step. Specifically, we are exploring inhomogeneous random graphs, which better model social networks, and expect our local neighborhood expansion results to hold in this setting. Thank you for raising this concern.

More detailed information / empirical study on the computational complexity and memory requirements of the proposed method would be beneficial.

Thank you for bringing this up. We refer the reviewer to Figure 3c, which shows the time required to generate the distances between the seeds and all nodes (i.e., the sketches) for both the BFS- and the GNN-based approach.

Could you elaborate on the specific architectural choices made for the GNNs? How do these choices influence their performance when transferred to larger graphs? What criteria were used to evaluate the transferability of GNNs across varying graph sizes? Were there instances where transferability was not achieved

For each of the eight training graph sizes, we evaluated four GNN architectures (GCN, GraphSAGE, GAT, and GIN) across nine combinations of width and depth, as detailed in the experimental section and appendices. Using MSE to evaluate performance, we selected the GNN with the lowest MSE for node embedding calculations in the local step.

Selecting the best-performing GNN ensured high-quality node embeddings, improving shortest-path approximations in the local-global framework, as shown in Experiment 3. GNNs trained on larger graphs generally enhanced transferability by capturing more relevant structural patterns.

Transferability was not achieved when the GNN in the local step was poorly trained or lacked sufficient depth to encode meaningful embeddings. While model tuning helped identify suitable architectures, understanding the theoretical relationship between GNN design and embedding quality remains an important direction for future research.

Although inspired by Awasthi et al.'s framework, there isn’t a direct comparison of results, such as accuracy or runtime metrics.

We thank the reviewer for this feedback. We will include the following comparison of our theoretical results with Theorem 1 in Awasthi et al.:

``In the worst case analysis, Sarma et al. (2010), Matousek (1996), and Awasthi et al. (2022) showed that a $(2c-1)$-factor upper bound for all pairs and a $\frac{1}{2c-1}$-factor lower bound of shortest paths can be achieved using local-global algorithms with an embedding dimension of $\Omega(n^{1/c} \log n)$ for $c>1$. Our results require an embedding dimension of $\Omega (n^{3-2c-\log 2}\log{n})$ for a $(2c-1)$-factor upper bound and $\Omega (n^{1/(2c-1)}\log{n})$ for a $\frac{1}{2c-1}$-factor lower bound with high probability for most pairs of nodes. Thus, in random graphs, we achieve an improvement in the embedding dimension. On the downside, the results for random graphs do not provide approximate distances for all pairs of nodes. We leave this as an interesting direction for future research.''

Regarding empirical comparisons, we note that the code for GNN+ is not publicly available, which limits our ability to conduct direct experimental evaluations. Additionally, Awasthi et al.'s GNN+ framework comprises multiple GNNs, whereas the GNN-augmented algorithm we consider relies on a single GNN, so these approaches are somewhat different in their design and scope.

The proof sections are a bit difficult to follow, especially for people without a sound background in this field. A detailed table introducing all the variables introduced in the algorithms and proofs would help to understand them easily.

Thank you for the feedback. To improve clarity, we have revised the theorem statements and proofs for the lower and upper bound distortions in Section 3. Additionally, we now redefine all relevant variables at the beginning of each section to make the notation more accessible and easier to follow.

How does this method perform on large-scale networks with millions of nodes, like social or biological networks? SNAP dataset collection of Stanford University has some very large social network datasets.

Thank you for the suggestion. We acknowledge that our experiments so far have been limited to smaller networks. While trying to work with batches of 100 graphs of size 12,800 nodes, we had kernel crashes, which prevented us from scaling up further at the time. However, as suggested by the reviewer, we are currently repeating Experiment 3 on a cloud service using SNAP's Amazon co-purchasing network, with around 100k nodes, and Youtube network, with around 1 million nodes, as the test graph. These results will be included in Section 4.3 and reported as they become available.

How does the GNN-based approach handle real-world sparse networks where long-range dependencies are more challenging? Could alternative GNN architectures improve performance in such cases?

Our method is based on local neighborhood expansions, so it does not capture long-range dependencies. While such dependencies are less common in the sparse Erdős-Rényi (ER) graphs analyzed in our paper, we acknowledge this as a limitation and will highlight it in the revised version. That said, our results already hold for sparse ER graphs, which are precisely the type of graphs we focus on in this work. Furthermore, we expect the methodology developed here to extend to other graphs with local expansion properties, such as inhomogeneous random graphs and expanders. We are actively exploring these extensions.

In our experiments, we demonstrated that GNNs struggle to predict distances longer than their depth. But in the local-global framework, we hypothesize that this limitation, i.e., the existence of seed-node pairs for which the GNN distances/sketches saturate, can be advantageous in the context of Bourgain's algorithm (lower bound), as it effectively ``prunes'' poor-quality seed nodes that are far from most other nodes. This will happen when nodes $u,v$ have almost the same distance to the seed $s$, improving the lower-bound computation $\max_{s,s' \in S} |d(u,s)-d(s',v)|$.

We leave the theoretical exploration of the relationship between the performance of GNN-enhanced local-global algorithms and the GNN architecture an avenue for future research.

Thanks again to the AC and the reviewers for their efforts in reviewing our paper. As an update, additional experiments on larger graphs with up to 100k nodes are now reported in Figures 4(d)--4(f) of the manuscript. We could not scale to larger graphs due to limited computational resources. Given the primarily theoretical nature of our paper, we hope the reviewers can understand.