Geodesic Graph Neural Network for Efficient Graph Representation Learning
Authors: Lecheng Kong
Yixin Chen
Muhan Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Learning
Geodesic
Graph Neural Network
GNN
Fast Inference

Abstract: Graph Neural Networks (GNNs) have recently been applied to graph learning tasks and achieved state-of-the-art (SOTA) results. However, many competitive methods run GNNs multiple times with subgraph extraction and customized labeling to capture information that is hard for normal GNNs to learn. Such operations are time-consuming and do not scale to large graphs. In this paper, we propose an efficient GNN framework called Geodesic GNN (GDGNN) that requires only one GNN run and injects conditional relationships between nodes into the model without labeling. This strategy effectively reduces the runtime of subgraph methods. Specifically, we view the shortest paths between two nodes as the spatial graph context of the neighborhood around them. The GNN embeddings of nodes on the shortest paths are used to generate geodesic representations. Conditioned on the geodesic representations, GDGNN can generate node, link, and graph representations that carry much richer structural information than plain GNNs. We theoretically prove that GDGNN is more powerful than plain GNNs. We present experimental results to show that GDGNN achieves highly competitive performance with SOTA GNN models on various graph learning tasks while taking significantly less time.

Geodesic Graph Neural Network for Efficient Graph Representation Learning
Lecheng Kong
Yixin Chen
Washington University in St. Louis jerry. kong@wistl.
Washington University in St. Louis ychen25@xustl.com edu
Muhan Zhang Peking University
muhan@pku. edu. cn
Abstract
Graph Neural Networks (GNNs) have recently been applied graph learning tasks and achieved state-of-the-an the-art (SOTA) results. However, many competitive methods run GNNs multiple times with subgraph extraction and customized labeling capture information that is hard for normal GNNs to learn. Such operations are time- consuming and do not scale to large graphs. In this paper, we propose an efficient GNN framework called Geodesic GNN (GDGNN) that requires only one GNN run and injects conditional relationships between nodes into the model without labeling. This strategy effectively reduces the runtime of subgraph methods. Specifically, we view the shortest paths between two nodes as the spatial graph context the neighborhood around them. The GNN embeddings of nodes on the shortest paths are used to generate geodesic representations. Conditioned on the geodesic representations, GDGNN can generate node, link, and graph representations that carry much richer structural information than plain GNNs. We theoretically prove that GDGNN is more powerful than plain GNNs. We present experimental results to show that GDGNN achieves highly competitive performance with SOTA GNN models various graph learning tasks while taking significantly less time.
Introduction
Graph Neural Network (GNN) is type of neural network that learns from relational data. With the emergence of sarge-scale network data, it can be applied to solve many real-world problems, including recommender systems 44], protein structure modeling [15], and knowledge graph completion (2]. The growing and versatile nature of graph data pose great challenges to GNN algorithms both in their performance and their efficiency.
GNNs use message passing to propagate features between connected nodes in the graph, and the nodes aggregate their received messages generate representations that encode the graph structure and feature information around them. These representations can be combined to form multi-node structural representations. Because GNNs are efficient and have great generalizability. they are widely employed in node-level, edge-level, and graph-level tasks. part the power of GNNs comes from the fact that they resemble the process of the I-dimensional Weisfeiler-Lehman (1-WL) algorithm [22. The algorithm encodes subtrees rooted from each node through an iterative node coloring process, and if two nodes have the same color, they have the same rooted subtree and should have very similar surrounding graph structures. However, as pointed out by Xu et al. [45). GNN's 's expressive power is also upper-bounde bounde- by the 1-WL test. Specifically, GNN is not able to differentiate nodes that have exactly the same subtrees but have different substructures. For example, consider the graph
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

in Figure I with two connected components, because all nodes have the same number of degrees, they will have exactly the same rooted subtrees. Nevertheless, the nodes in the left component are clearly different from the nodes in the right component, because the left component is a 3-cycle and the right one a 4-cycle. Such cases can not be discriminated by GNNs or the 1-WI. test. We refer to this type of GNN as plain GNN or basic GNN.
On the other hand, even when a carefully- desiine GNN can dif- ferentiate all node substructures in graph, Zhang el al. [ show that the learned node representation still cannot effectively perform structural learning tasks involving multiple nodes, including link predictions and subgraph predictions, because the nodes are not able to learn the relative structural information. We will discuss this in more detail in Section 3.1
An example where plain GNN fails to distinguish nodes in the graph.
Figure 1:
These limitations motivate recent research that pushes the limit of GNN's expressiveness. One branch is to use higher-order GNNs that mimic nigher-dimensional Weisfeiler-Lehman tests [23 26]. They extend node-wise message passing node-tuple-wist and obtain more expressive representations. Another branch is to use labeling methods. By extracting subgraphs around the nodes of interest, they design a set of subgraph- customized labels as additional node features. The labels can be used to distinguish between the nodes of interest and other nodes. The resulting node representations can encode substructures that plain GNNs cannot, like cycles.
However, the major drawback of these methods is that compared to plain GNNs, their efficiency is significantly compromised. Higher-order GNNs update embeddings over tuples and incur least cubic complexity [52 233. Labeling tricks usually require subgraph extraction on a large graph and running GNNs on mini-batches of subgraphs. Because the subgraphs overlap with each other, the aggregated size of the subgraphs is possibly hundreds of times the large graph. Nowadays GNNs are massive, the increased graph computation cost makes labeling methods inapplicable real-world problems with millions of nodes.
We observe that great portion of the labeling methods relies on geodesics, namely the shortest paths, between nodes. For node representation, Distance-Fnccding (DH) (25) labels the target nodes' surrounding nodes with their shortest path distance the target nodes and achieves higher than 1-WL test expressiveness. Current tfate-of-the-arr methods for link prediction, such as SEAL [50]. leverage the labeling tricks in order capture the shortest path distance along with the number of shortest paths between the two nodes of the link. Inspired by this, we propose our graph representation learning framework, Geodesic GNN (GDGNN), where we run GNN only once and inject higher expressiveness into the model using shortest paths information by geodesic pooling layer. Our framework can obtain higher than 1-WL power without multiple runs of plain GNNs, which largely improves the efficiency of more expressive methods.
Specifically, our GDGNN model learns function that maps the learning target to geodesic- augmented target representation (the target can be a node, edge, graph, etc). The model consists of two units, GNN unit, and geodesic pooling unit. The two units are connected perform end-to-end training. We first apply the GNN to the graph to obtain embeddings of all nodes. Then, for each target, we find the task-specific geodesics and extract the corresponding GNN representations of nodes on the geodesics. The task-specific geodesics have three levels. For node-level tasks, we extract the geodesics between the target node and all of its neighbors. For edge-level tasks, we extract the geodesics between the two target nodes of the edge. For graph-level tasks, we get the geodesic- auggeeted node representation for each node as in node-level tasks and readout all node representations as the graph representation. Finally, using the geodesic pooling unit, we combine the geodesic representation and target representation to form the final geodesic augmented target representation. Figure 2 summarizes the GDGNN framework.
All task task-specific geodesics are formed by one or multiple pair-wise geodesics between two nodes. We propose two methods to extract the pair-wise geodesic information, horizontal and vertical. The horizontal geodesic obtained by directly extracting one shortest path between the two nodes. The vertical geodesic is obtained by extracting all direct neighbors of the two nodes that are on any of their shortest paths. They focus on depth and breadth respectively. Horizontal geodesic is good at capturing long- digg-ait information not covered by the GNN. Vertical geodesic is provably more powerful than plain GNN, Moreover, by incorporating the information of the subgraph induced by
They
2

---

GNN
Naaiiple pair véle grededis are combiiee
intornation mnttiple rodes comsiteed
Tanbeddllgs oxderde sor graerate
Paaeoedee Goodaai Hegrosesiiiin
Task Task-Specilic Geodesis Pooling F Func
Targetgrahh
GNN prux graph conbeddingss
Vertical Geodesi
Representation
Representation
Graph Repeescntation
Figure 2: The overall pipeline of GDGNN. GNN applied once to generate node embeddings. We then use horizontal vertical geodesic to extract pair-wise geodesic representation. One more such representations are collected to generate task-specific representation.
the vertical geodesic nodes, we can use GDGNN to distinguish some distance-regulae graphs, type of graph that many current most powerful GNNs cannot distinguish.
During inference, the GNN unit applied only once to the graph, after which we feed nodes and geodesic information to the efficient geodesic pooling unit. This limits the number of GNN runs from the query number (or the number of nodes for graph-level tasks) to a constant of one and remarkably reduces the computation cost, Compared to labeling methods, GDGNN only requires one GNN run and is much more efficient. Compared to plain GNN methods, GDGNN uses geodesic information and thus is more powerful. We conducted experiments tasks across datasets with different scales and show that GDGNN is able to significantly improve the performance of basic GNNs and achieves very competitive results compared to state-of state-of-the-arr methods. We also demonstrate GDGNN's runtime superiority over other more- more-cxpressive GNNs.
node-level, edge-level, and graph-level
2 Preliminaries
graph can denoted by G (V,E, R)) where = {UI, vn is the node set, & S {(u;, r, my (2)) U V,r RJ is the edge set and R is the set of edge types in the graph. When (R] = 1, the graph can be referred to as a homogeneous graph. When [R] > 1, the graph can be heterogeneous graph. Knowledge graphs are usually heterogeneous graphs. The nodes can be associated with features X' = (x.IVe E V}. For simplicity, we use homogeneous graphs to illustrate ideas and methods.
referred to
We follow the definition of message passing GNNs in 45 with AGGREGATE and COMBINE functions. Such GNNs iteratively update the node embeddings by receiving and combining the neighbor nodes' embeddings. The k-th layer of a GNN can be expressed as:
(k) AGGREGATE ()) (f(()-))) h COMBINE (m (K) ((t)), (h-1)))
(1)
where h0 the node representation after & iterations. h: T.. .V(v) the set of direct neighbors of m., is the message embedding. Different GNNs vary mainly by the design choice of the AGGREGATE, and COMBINE functions. In this paper, we use h, to represent the final node representation of from the plain GNN. In this paper, we use bold letters to represent vectors, capital letters represent sets, and A (v) to refer to nodes within the k-hop neighborhood of v.
3 Geodesic Graph Neural Network
Geodesic is conventionally defined as the shortest path between two nodes and indeed in homogeneous graphs, it encodes only the distance. However, we found that when combined with GNNs and node representations, geodesics express information much richer than the shortest path distance alone. In this section, we first discuss the intuition behind GDGNN and its effectiveness. Then, we describe the GDGNN framework and how its GNN unit and geodesic pooling unit are combined to make predictions, Finally, we provide theoretical results of the better expressiveness of GDGNN.

---

(a)
(b)
(c)
(d)
Figure 3: (a) A circular graph where plain GNN cannot distinguish link AB and AC. (b) and (c) are the GNN computation graphs of A if B and C, respectively, are labeled. (d) is an example where geodesic representation can distinguish links AB and AC, but distance fails to do so.
3.1 Intuition and Overview
The key weakness of directly using plain GNNs is that the embeddings are generated without conditional information. For node-level tasks, as pointed out in [49]. a plain GNN is unaware of the position of the target node in the rooted subtree, and hence the target node is oblivious of the conditional information about itself. For edge-level tasks, Zhang er al. [54) shows that despite GNN, without node labeling, the embedding of one node in the edge is not able to preserve the conditional information of the other node. Concretely, take link prediction as an example, in Figure 3a we have two target links AB and AC Since AB is already connected by a link and AC is not, they should be represented differently. On the other hand, All nodes in the graph are symmetric and should be assigned the same embeddings using any GNN. Hence, if we simply concatenate the node representations of AB and AC, they will have the same link representations, and cannot differentiated by any downstream learner. To overcome this problem, previous methods rely on labeling tricks to augment the computation graphs with conditional information. When node and C are labeled respectively in two separate subgraphs, the resulting computation graphs of A different shown in Figure and 3c
Notice that, for the labeling methods to take effect, subgraph extraction is necessary. However, relabeling the graph and applying a GNN to every target to predict is extremely costly. Hence, we wonder whether we can also incorporate conditional information between nodes without customized labeling. Observe that in the example, the computation graph captures the number of layers before node A first receives a message from a labeled node, which is essentially the shortest path distance d between A and the other node. This implies that even when we only have node representations from a plain GNN, by adding the distance information (which and 3 for AB and AC respectively) independent of the computation graph, we can still distinguish the links.
While the previous example demonstrates the effectiveness of a simple shortest path distance metric. we notice that distance alone is not always sufficient. For example. in Figure 33d node B and node C are symmetric and hence should be assigned the same node embedding when the graph is not labeled. However, links AB and AC are apparently different as connecting AB connects to another group of nodes whereas V/ connecting AC does not connect any other node. If we only use the shortest path distance between AB and AC to assist the prediction, we still cannot differentiate them. However, if we inject the entire geodesic expressed by the corresponding node embeddings along the shortest path to the model, we are able to tell AB and AC apart due to Uj and 12 's different embeddings.
Consider naive GNN that outputs all node embeddings as one. Taking the shortest path can be seen as extracting a one-valued vector with a length of the shortest distance between the two nodes. In the neural setting, a general GNN can model the naive GNN and the nodes on the same shortest path can have different representations besides one by encoding their own neighborhood. The extension of the shortest path to the neural setting grants stronger expressive power the geodesics. The geodesic generation and the GNN are decoupled, because the selection of geodesic nodes is independent of the node representations, while the node representations in subgraph GNNs are tied to subgraph. Dwelling on this decoupling and conditioning philosophy, GDGNN can run the GNN only once to generate generic node embeddings and then use geodesic information to inject conditional information into the model in a much more efficient way.

---

3.2 Pair-wise Geodesic Representation
GDGNN has different ways to leverage geodesic information for different levels of tasks, but they all have the same basic component, pair-wise geodesic representation. It consists of structural information of nodes on the shortest paths of the pair. Directly extracting all such nodes is time- consuming and sometimes not effective, hence we present two primary ways to learn the geodesic representation, horizontal and vertical.
3.2.1 Horizontal Geodesic Representation
Horizontal Geodesic Representation is designed to directly capture the distinctiveness described in the previous example shown Figure 3d first finds the shortest path between two nodes as the geodesic. If there multiple paths between them, we randomly choose one. The nodes the shortest path denoted by p(H)
[u,e) {u, n1, f22, mg-1, v) with length of d. Using p(H) we can construct the geodesic representation ((u,v) by a geodesic pooling layer.
(u,v)
(H) = Rdd (fhw, Ve E P(()))
(u,F)
To prevent extremely long geodesics which may cause overfitting, we limit the maximum length to manageable constant dmaz- Any pair with a distance larger than dmaz will have an infinite distance and zero geodesic representation.
Because of the high computation cost of GNNs, the number of GNN layers is usually very small. Using horizontal geodesics, we are able to connect nodes that are far away and do not coexist in GNN's s limited-height computation graph.
3.2.2 Vertical Geodesics Representation
Horizontal geodesics seems like an intuitive choice to directly connect the pair of nodes by sequence of adjacent nodes. However, a natural question to ask whether a single path is enough to represent the conditional information between the pair. An example where horizontal geodesic falls short can be found in Appendix G Realizing this limitation, we propose the vertical geodesic representation that includes all geodesic information in efficient way.
For pair of nodes and v, vertical geodesic extracts the direct neighbors of them that are on any of their shortest paths. Specifically, let the distance between and be d(u, v), we have the nodes on their shortest paths to be W W(,,)) {w d(u, w) + d(w, v) = d(u, v), Vu V}. The geodesics can be represented as,
(u,e) = p(V) (u,o), U P(
(a,e),. where (u,v), = W (W()), {u,
(3)
Here P.V) (u,,) represents the nodes in the geodesic that are also the direct neighbors of i. For some tasks, we only consider one p(V) (a.)), as the geodesics instead of both. We use pooling layer to generate vertical geodesic
RR() (( Vu E P(Y)) F).
g (u.0)
(4)
While the vertical geodesic does not explicitly encode long shortest path, it can still capture short shortest path information due to pooling the embeddings of the nodes in it. Compared with the horizontal geodesic that takes random shortest path, the vertical geodesic focuses more breadth by incorporating all direct neighbors on any shortest paths.
Unlike nodes in horizontal geodesic, nodes in vertical geodesic induce more complex subgraph.
Consider only p(()) (a.").v (we will use P. here for simplicity) and the subgraph G. induced by nodes in P.. We can have pooling function that encodes the graph structure G..
(5) The pooling layer can be small plain GNN itself, and the initial embedding of G, can take the pooled node embeddings from the main GNN. However, to keep our method efficient, only add
g (v) R
gd ((hig Vu P.).Gu).
5

---

the degree of nodes in the subgraph to the node embeddings. And the vertical geodesic representation becomes,
g: vV = ( @ degs. (w), Vw E Po)).
(6) where + means concatenation. Note that node's s degree in the subgraph is different from that in the main graph. This can be seen as a 1-layer GNN applied onto Gg with identical initial node embeddings. Even with this simple pooling design, the vertical geodesic is able to help distinguish some distance regular graphs, which we cover in section 3.4
Because vertical geodesics do not encode distance directly, we concatenate distance to vertical geodesics an additional feature. Like in horizontal geodesics, when d(u, v) is greater than dmmazs we do not generate the geodesic representation for the pair and set their distance to infinity.
3.3 Task specific geodesic representation
Task-specific geodesic representation is collection of pair-wise geodesic representations, Here, focus on three levels of tasks, node-level, edge-level, and graph-level.
For node-level tasks, the goal is to generate a representation =(") for a target node v. We first find e's k-hop neighbor nodes S, v (v). Then for each node s; in S.. we find the pair-wise geodesic, Iv.s.. Note that in node level tasks, vertical geodesic only contains the geodesic nodes close to s,, P(V)
(e..s).e, This enables fast geodesic extraction, and Theorem shows that with only one side the vertical geodesics, GDGNN can already distinguish almost all pairs of regular graphs. The geodesic representations of the neighborhood combined by pooling layer,
= R (g(o.)))) 81 E S.).
While the GNN node embeddings of the neighborhood are not conditioned on v, by adding the geodesic information to every neighbor, we inject the conditional information of v into its neighbors. Then the collective information of the neighbors helps distinguish v.
For edge-level tasks, the goal to generate an edge embedding 2((e) for nodes u and v. Here, we (u,,v)
directly use the pair-wise geodesic for the two nodes, ((,,)) = I(,,)) As pointed out by previous works (58] 53], the advantage of this setup is that, when the downstream task is to rank one link against N other links with one same node v, we only need to compute the distance vector from once and find the geodesic nodes efficiently.
(e)
For graph-level tasks, we need to generate graph embedding 200) for -=V pooling layer to summarize the geodesic-augmmented representation of every node in the graph,
(V,E), We use another
(g) =( (z V).
(8)
GDGNN can also be easily generalized to other levels of tasks such subgraph-level.
3.4 Expressive Power of GDGNN
Distinguishing power on graph-level tasks is often used to characterize the expressiveness of a GNN model. For GNN models to be more expressive than the 1-WL test, we can test whether they are able to distinguish regular graphs. In the following theorem, we show that given an injective R(a), the graph embedding za generated based on vertical geodesics can distinguish most regular graphs.
Let the graph pooling layer R(9) be injective given input from a countable space. Consider all pairs of n-sized r-regular graphs, where 3 S < 22g n, is the number of nodes in the graph. For any small constant 6 > 0, there exists a GDGNN using vertical geodesic log
Theorem 1.
representations with dmax = [[2 + c) log( which distinguishes almost all (1 o(1)) such pairs of graphs.
We include the proof of Theorem in Appendix A This theorem implies that GDGNN with vertical geodesics is more expressive than basic GNNs (and 1-WL) and can discriminate almost all r-regular graphs. Moreover, GDGNN only needs to search small neighborhood for geodesics to achieve higher expressiveness. This guarantees the good efficiency and performance of GDGNN.

---

X5
X9
X4
XO
Figure 4: An example of two graphs where GDGNN with vertical geodesics and subgraph degrees can distinguish, while distance encoding cannot.
Moreover, when the vertical geodesic pooling layer encodes the subgraph induced by the geodesic nodes (using Equation geodesic pooling), GDGNN can distinguish some distance regular graphs. Figure shows two distance regular graphs, the Shrikhande graph, and the 4x4 rook's 's graph. They have the same intersection array and number of nodes. As proved by Li et al. [25), distance encoding is not able to distinguish this pair of graphs, because nodes in the two graphs will be assigned the same embedding. However, vertical geodesic can discriminate them. Suppose the black nodes are the target nodes, the brown nodes are one distance away from the black nodes and the light blue nodes are two distances away from the black nodes. Consider the light blue nodes in both graphs, they each have a pair of brown common neighbors with a black node. The brown pair is the vertical geodesics of one light blue node. If we count the number of edges in the subgraph formed by each brown pair, we will see that four out of nine pairs form a one-edge graph (in red) in the Shrikhande graph, while zero out of nine pairs form a one-edge graph in the 4x4 rook's graph. Since Equation 6 directly captures this and will give four light blue nodes in the Shrikhande graph different pair-wise geodesics with respect to the black node, an injective graph pooling layer will yield different node representations for the two black nodes, and in turn, discriminates the two graphs.
Complexity. The main computation advantage of GDGNN comes from the fact that, for GDGNN, the number of GNN runs stays at constant of 1, while subgraph- -based methods incur GNN runs which increase linearly with respect to the number of queries. Hence, GDGNN maintains the good efficiency of basic GNN methods, while injecting the high-expressivensss of subgraph methods into the model. A detailed complexity analysis on different tasks can be found in Appendix B
Limitations. While a simple geodesic pooling layer satisfies the theoretical expressiveness, if we indeed use GNN or other more complex layer for pooling suggested in Section 3.2.2 the pooling will dominate the good amortized complexity of GDGNN. We see this as a possible future direction more complex pooling layer to further improve expressiveness while maintaining efficiency. Like subgraph GNNs, the geodesic extraction process also includes a cutoff distance dmaz which potentially limits the expressive power of GDGNN. Meanwhile, compare GDGNN with different cutoff distances in Appendix [F] and show that a relatively small dmaa suffices to represent the graph structure indicated in Theorem I
where
4 Related Works
GNNs beyond 1-WL test. Designing GNNs with stronger representation power is fundamental task in GNN research. Xu al. [45] first proved that the expressiveness of basic GNNs, such as GCN 20), GrEphSAGE [17], and GAT 440, is upper-bounded by the 1-WL test. Following works conducted extensive research to break this limit. They can be sorted into several directions: (1) Earlier works proposed higher-order GNNs that are as expressive as the k- W- algorithm, such as k-GNN 23 RingGNN(6), and PPGN[26]. These methods require message passing on node tuples that grow exponentially with respect to k. The increased computation cost makes them not scalable to large graphs. (2) Another type of methods, like GSN [5] and MotifNet (27] incorporates isomorphism counting on certain graph substructures like cycles, triangles, and cliques, similar to earlier kemnl-- based methods [6) 12]. They essentially augment the models with features undetectable by GNNs. However, properly-desige substructure usually requires expert knowledge which is not available for all data. (3) Some other works use identity or random node labeling within the plain GNN framework. ID-GNN 49 extracts a subgraph around the target node and performs heterogeneous message passing. DE-GNN 25 also requires subgraph extraction but labels nodes in the subgraph with distance to the targets. They both have stronger expressiveness than basic GNNs. Abboud et al.
7

---

[ shows that GNNs possess universality with random node feature initialization (RNI). Nevertheless, RNI also induces huge sample space, and GNNs adopting RNI is very hard to train. (4) Some recent augment
works propose to use additional subgraph structures to augment the node embeddings. GraphSNN
4 incorporates properties of overlapping subgraphs between adjacent nodes to more expressive than 1-WL. Nested-GNN [52] applies GNN to ego-subgraphs of every node and proves that it is able to discriminate regular graphs. Sharing the same idea of Nested-GNN, GNN-AK[55] uses a different subgraph pooling strategy and uses subgraph dropping to improve the model scalability. (5) Another approach learns from both positional and structural representation. Dwivedi et al. [EI proposes to learn from positional node embeddings unrecognized by the GNN and iteratively update them during message passing. Zhu et al. (57) computes node proximity matrix to learn positional of nodes. They can be combined with GDGNN to adapt to position sensitive
position-sensitive tasks.
Link prediction using GNNs. Earlier works 21 20 39] applied basic GNNs to link prediction
using an auto-encodes framework, where the GNN serves as the encoder of the nodes, and edges are decoded by their nodes' encoding vectors. Another line of works, including SEAL 50) IGMC [5]], and GraIL [36], use GNNs encode a labelled subgraph to form the link representation. Later work 34 54] reveals that a good poode-leee/grraph-eeee representation does not necessarily lead to good edge-level representation. Zhang et al. [54] systematically show that the labeling trick bridges the gap between node-level and edge-level GNN expressiveness. Sharing the spirits of labeling trick, NBFNet [58] extends the generalized Bellman- Ford algorithm to the neural setting and can encode many traditional path-based methods. NBFNett has better scalability when there are multiple links sharing the same node. Some other works also propose to use path information between links to enhance the prediction like horizontal geodesic. Jagvaral et al. 19] uses CNN and BiLSTM to summarize the path information, however, their model requires fixed node embedding, while horizontal geodesic is based on graph structure generated from GNN and hence is inductive. Wang et al. 42 learns relational path information by training set of embeddings for all different types of relational paths, while horizontal GDGNN uses GNN to capture the graph structure and pool node embeddings along the geodesic without training relational-pati path-speecffic embeddings.
5 Experimental Results
5.1 Link Prediction
Datasets. We use several types of datasets for link prediction. (1) Knowledge Graph (KG) inductive link prediction datasets. Inductive link prediction means that the model is trained on training graph while tested on a different graph. This requires the model to generalize to unseen entities, which is property preserved by limited number of models. We follow the standard inductive split of WNI8RR (1) and FB15K237 (38) as in Teru et al. [36]. We rank each positive link against 50 randomly sampled negative links with the same head/tail as the positive link and report the Hit@ 10 ratio. (2) OGB large-scale link prediction dataset [8]. including OGBL-COLLAB and OGBL-PPA.
We use the official data split. We rank each positive link against set of provided negative links in the dataset and report the Hit@ 50 ratio for the OGBL-COLLAB dataset and the Hit@ 100 ratio for the OGBL-PPA dataset. (4) Transductive KG results are included in Appendix C (3) Results of citation datasets and comparison to other distance-based methods can be found in Appendix D These datasets vary by graph size and demonstrate GDGNN's capability across scales.
Baselines. We compare GDGNN with Rules Mining methods, DRUM [1 and NeuralLP [47]. and GNN-based methods, NBFNet (58) and Grall (36) for the KG tasks. Some other works like incorporate text data in the KG to achieve better performance. As we believe models that employ textual information is beyond the context of graph structural learning, we exclude them in our comparison. For the OGB dataset, we compare GDGNNS with other methods achieving top places on the OGB link prediction leaderboard, including Deep Walk (29) Resource Allocation (RA) (56). SEAL, Deeper GCN (24).
41 g
Implementation Details For link prediction, we use GCN (RGCN for KG) the basic GNN. For the KG datasets, we search the number of GNN layers in {2, 3, 4, 5} and use 64 as hidden dimensions, and the max search distance for geodesic, dmaax is the same the number of GNN layers. For the OGB datasets, we search the number of GNN layers in (2, 3, 4} and use 100 as the hidden dimension.
'The code and data of GDGNN can be found http://ggthbbccom/woooodutteele
8

---

Table I: Link prediction results (%) on KG.
Table 2: Link prediction results (%) on OGB.
FB15K-237
WNI8RR
Method
OGBL-COLLAB
OGBL-PPA
Method
v1
v2
v3
v4
v1
v2
v3
v4
GCN
44.75 1 1.45
18.67 1: 1.32
DRUM
52.9
58.7
52.9
55.9
74.4
68.9
46.2
67.1
DEEP WALK
50.37 1 0.34
28.88 - 1.63
N
52.9
58.7
52.9
55.9
74.4
68.9
RA
49,33 = 0.00
GralL
64.2
81.2
82.8
89.3
82.5
78.7
G8.4
73.4
DeeperGEN
0.473
NBFNet
83.4
94.9
95.1
96.0
94.8
90.5
89.3
89.0
SEAL.
54.37 0.49
48.80
GDGNN- Vert
85.4
95.6
97.9
97.8
93.1
88,9
88.1
85.6
GDGNN- Vert
+4.4400.65
45.92 2.14
GDGNN-Hor
82.1
95.8
94.0
97.7
94,9
87.8
89.5
88.5
GDGNN-Hor
34.52 + 0.72
28.79 3.80
Table 3: Link prediction running time results.
Table 4: Graph classification running time results.
Method
OGBL-COLLAB OGBL-PPA
Method
OGBG-MOLHIV OGBG-MOLPCBA
GCN
27 sec
min
GIN
20 sec
min 12 min
SEAL
90 sec
2 hr 20 min
GIN-AK Nested-GIN
70 sec
NBFNet
OOM
OOM
149 sec
16 min
GDGNN- Vert
sec
min
GDGNN- Vert
25 sec
2.5 min
We train 50 epochs with a batch size of 64 for the KG datasets, and we train 25 epochs with a batch
size of 2048 for the OGB datasets. For OGBL-COLLAB dataset, we use homogeneous labels (1 labels) for all nodes. We record the test score using the model with the best set of hyperparameters on validation set. The experiment is repeated 5 times and we take the average.
Results and discussion. We achieved SOTA performance on the inductive datasets. GDGNN is able to significantly improve over rule-mining methods and GralL. We also outperform NBFNet on most of the datasets. On the OGBL-COLLAB dataset (Table GDGNN achieved SOTA performance. On the OGBL-PPA dataset, vertical GDGNN can obtain very competitive result. Horizontal GDGNN does not perform well possibly because single path has limited distinguishing power in graph with high density. On both OGB datasets, GDGNN improves greatly over its basic GNN, GCN, Moreover, shown in Table GDGNN has running-time superiority over methods achieving comparable performance and has a memory advantage to handle large graphs where NBFNet cannot when links do not share common nodes. To make fair rumning time comparison, run all models on 32 CPUs and Nvidia GeForce 1080Ti GPU. We also include ablation studies on all components of GDGNN in Appendix [
5.2 Graph Classification
Datasets. We use two types of datasets for graph classification. (1) TU datasets contain DI MUTAG[9, PRO (37] The evaluation metric is Accuracy (%). We follow the evaluation protocol in (52) where we use 10-fold cross-validation to compute the score. (2) OGB datasets including OGBG-MOLHIV and OGBG- MOLGGG-MOPCBBAA The task of the OGBG-MMOLHIV dataset is to predict whether molecule inhibits the HIV virus. We use Area Under ROC Curve (AUC) to evaluate the OGBG-MOLHIV dataset. OGBG-MOLPCBA dataset has 128 classification tasks. We follow the evaluation protocol provided by the OGB team and use Average Precision (AP) averaged across all classes to evaluate the dataset. (3) Synthetic datasets, including Ε and 28) These datasets contain graphs that can be only distinguished by models with > 1-WL expressiveness. We report accuracy for these datasets.
Baselines. For the TU dataset, we compare GDGNN with another plug-and-play GNN framework, Nested-GNN[52). Both GDGNN and Nested-GNN use GIN and GCN as their basic GNNs. For the OGB dataset, we use GIN as the basic GNN, we compare GDGNN with methods achieving top places on the OGB leaderboard, including G5), GIN-AK (55). LSPE [4], Nested GNN [52]. Directional GSN (DGSN) B. PF-GNN 13).
Implementation details. We use vertical geodesic in the graph-level tasks because of its theoretical advantage over horizontal GDGNN. For TU datasets, we search the GNN layers and dmai in (,,3,4). We train on the TU dataset for 100 epochs with a batch size of 64. For OGB datasets, we search the number of GNN layers in (2,3,4,5), ), and train for 100 epochs with batch size of 256. We adopt the virtual node technique
16 to increase the connectivity of graphs for the OGBG-MOLPCBA dataset. For synthetic datasets, we search the number of GNN layers in (2,3,4), and train for 50 epochs with batch size of 16. For the synthetic datasets, we report GDGNN's performance with different numbers of layers| (2.3.4). We train the models for 100 epochs with batch size of 8.

---

Table S: Graph classification results (%) on TU.
Table 6: Graph classification results (%) on OGB.
D&D
MUTAG
PROTEINS
PTC PR
Method
OGBG-MOLHIV
OGBG-MOLPCBA
Avg. Wnodes
284.32
17.93
39.06
14.29
GIN
75.58 + 1.40
27.03 0.23
GCN
71.622
73.4 +: 10.8
71.7 4.7
56.4 = 7.1
LSPE
28.40 0.20
GIN
71.6 3.0
74.0 8.8
7.2
57.0
5.5
Nested-GIN
78.34 + 1886
28.32 = 0.41
Nested-GCh,
3.8
82.9
+ 11.1
73.3 4.00
57.3
7.7
DGSN
80.39 0.90
Nested-GIN
77.8 3.9
8.2
7.1
51.1 7.7
GIN-AK
78.22
0.75
29.30 0.44
PF-GNN
80.15 1 0.08
GDGCN
7..6=4.0
88.4
6.6
4.4
60.3 = 4.5
GDGIN
3.6
89.4 7.1
57.9 2..
3.4
GDGIN
79.07 + 1.20
28.59 0.63
Results and discussions. On the TU datasets 5) GDGNNS consistently outperform the basic GNNs. Compared to Nested-GNN, GDGNN is able to bring a larger performance increase. This shows GDGNN's enhancing power. On the OGB datasets (Table (6. we can see that GDGNN's performance is lower than PF-GNN and Directional GSN (so are GIN-AK and Nested-GNN). This might indicate that pairwise conditional information is less effective for graph tasks than for link tasks.
Nevertheless, GDGNN still outperforms the basic GIN a lot, and as
Table 7: Synthetic Results.
GDGNN is a general framework that can be applied any basic GNN, the performance can be further improved. We notice that GDGNN outper- forms LSPE on the MOL-MOL dataset, which might indicate that
EXP
CSL
GIN
50.0
10.0
the pair-wise relation encoded by GDGNN is sufficient in representing the positional information of node. On the synthetic data, we achieve comparable results to the universal PF-GNN, which verifies our theory.
RNI
99.7
16.0
PF-GNN
100.0
100.0
2-GDGNN
50.0
30.0
3-GDGNN
100.0
60.0
We include ablation studies of graph-level geodesics in Appendix
4-GDGNN
100.0
100.0
5.3 Node Classification
Datasets. We use airport datasets, Brazil-Airport, Europe-Airport and USA-Airport for our node classification experiments. The task is to predict passenger flow level from the flight traffic network, where graph structure matters and expressive GNNs are useful. Following the setting in Li et al. (25), we split the dataset with train/test/valid ratio of 8:1:1 and run experiments with independent random initialization 20 times and report the average accuracy and 95% confidence range.
Baselines.
For GNN baselines, we compare to 1-WL. GNNs, including that also relies on distance information.
GCN and GIN, and DE-GNN (25
We further compare to Struc2vec 330]
Table 8: Node classification results (%).
PhUSION[57 that encodes graph structures without GNN. DE-GNN and PhUSION have several variants and we take their best results ver-
Method
Bra.-Airports
Aur.oAispots
USA-Airporss
GCN
64.55 4 4.18
52.07 i 2.79
56.58 +: 1.11
here. Like in graph classification, tical geodesics because of its good theoretical properties. We search the GNN layers and dmaz in (2,3,4). We train on all datasets for 200 epochs with batch size of 32.
GIN
72.83 0.43:33.0 3.57
53.84 - 3.94
57.43 2.13
PhUSION
72.37
0.00
56.02
1 0.00
63.49 1: 0.00
Struc2vec
70.88 0668:-00 4.26
57.94 4.01
61.92 : 2.61
DE-GNN
75.37
3.37223.22 3.25
58.41 = 3.20
64.16 = 1.70
GDGIN
78.61 2.20
53.97 # 3.50
64.36 + 1.62
Results and discussions. From Table 3 we can see that GDGNN achieves very competitive results compared to DE-GNN, and significantly improves the performance of basic GIN on two datasets, which experimentally verifies our claim that nove-level geodesic is more expressive than plain GNNs. For GDGNN, because the GNN is applied to the graph only once in the entire node classification process, it can maintain a good efficiency comparable to that of the basic GNNs.
6 Conclusions
In this paper, propose general GNN framework that incorporates geodesic information to generate node, link, and graph representations. Our framework is more powerful than basic GNNs both practically and theoretically and is more efficient than current expresxxee GNNs as demonstrated by the running-time time experiments. Our framework has the potential to make GNNs encoding conditional information really applicable to large-scale real-world graphs.
Acknowledgement. I.K and YC are supported by NSF grant CBE-2225809, MZ. supported by NSF China (No. NN.662260033 and CCF-Baidu Open Fund 1N0.2221PP15002000
10

---

References
[1] Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.01179 2020.
[2] Siddhant Arora. A survey on graph neural networks for knowledge graph completion. arXiv preprint arXiv:2007. 12374, 2020.
[3] Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference Machine Learning, pages 748-758. PMLR, 2021.
[4] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-re nulti-relationa data. Advances in neural information processing systems, 26, 2013.
[5] Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
[6] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019.
[7] Tim R Davidson, Luca Falorsi, Nicola De Cao, Thomas Kipf, and Jakub M Tomezak. Hyper- spherical variational auto-encoders. arXiv preprini arXiv: 180440004400 2018.
[8] Daniel Daza, Michael Cochez, and Paul Groth. Inductive entity representations from text via link prediction. Proceedings of the Web Conference 2021, pages
2021.
[9] Asim Kumar Debnath, Rosa I. Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):76-799, 1991.
[10] Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Thirty-second AAAI conference on artificial intelligence, 2018.
[11] Paul D. Dobson and Andrew J. Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of Molecular Biology, 330(4):771-783, 2003.
[12] Simon Du, Kangeheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in neural information processing systems, 32, 2019.
[13] Mohammed Haroon Dupty, Yanfei Dong, and Wee Sun Lee. Pf-gnn: Differentiable particle filtering based approximation of universal graph representations. In International Conference on Learning Representations, 2021.
[14] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. arXiv preprint arXiv:2110.07875. 2021.
[15] Wenhao Gao, Sai Pooja Mahajan, Jeremias Sulam, and Jeffrey J Gray. Deep learning in protein structural modeling and design. Patterns, 109):000142, 2020.
[16] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. International conference on machine learning, pages 1263-1272. PMLR, 2017.
[17] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 3/ International Conference on Neural Information Processing Systems, pages 1025-1035, 2017.

---

[18] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 18-2133, 2020.
[19] Batselem Jagvaral, Wan-Kon Lee, Jae-Seung Roh, Min-Sung Kim, and Young- Young-Tack Park. Path-based reasoning approach for knowledge graph completion using enn- ann-iilsmm with attention mechanism. Expert Systems with Applications, 142:1 12960, 2020.
[20] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. XrViv preprint arXiv: 2016.
[21] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv: 1,003008 2016.
[22] AA Leman and Boris Weisfeiler. A reduction of a graph to a canonical form and an algebra arising during this reduction. Tauuchnu-Tcchnicceskkaya Informatsiya, 2(9):12-16, 1968.
[23] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In International conference on machine learning, pages 3835-3845. PMLR, 2019.
[24] Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint arXiv:2006.07739, 2020.
[25] Pan Li, Yanbang Wang. Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Neural Information Processing Systems (NeurIPS), 2020.
[26] Haggai Maron, Heli Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
[27] Federico Monti, Karl Otness, and Michael M Bronstein. Motifnet: a motif-based graph convolutional network for directed graphs. In 2018 IEEE Data Science Workshop (DSW), pages 225-228. IEEE, 2018
[28] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pages 4663-4673. PMLR, 2019.
[29] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. CoRR,
2014.
[30] Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. strue2vec: Learning node representations from structural identity. Proceedings of the 23rd ACM SIGKDD international conference knowledge discovery and data mining, pages 385-394, 2017.
[31] Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. DRUM: end-to-end differentiable rule mining on knowledge graphs. CORR, abs/1911.00005, 2019.
[32] Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks, 2017.
[33] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008
[34] Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations, In International Conference on Learning Representations, 2019.
[35] Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph em- bedding by relational rotation in complex space. In International Conference Learning Representations, 2019.
[36] Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning, In International Conference on Machine Learning, pages 9448-9457 PMLR, 2020.
12

---

[37] Hannu Toivonen, Ashwin Srinivasan, Ross King, Stefan Kramer, and Christoph Helma. Sta- tistical evaluation of the predictive toxicology challenge 2000-2001. Bioinformatics (Oxford. England), 19:1 111-1833 08 2003.
[38] Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd workshop on continuous vector space models and their compositionality, pages 57-66, 2015.
[39] Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition- based multi-relational graph convolutional networks. In International Conference on Learning Represen- tations, 2019.
[40] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[41] Bo Wang, Tao Shen, Guodong Long, Tianyi Zhou, Ying Wang, and Yi Chang. Structure- augmented text representation learning for efficient knowledge graph completion. In Proceedings of the Web Conference 2021, pages 1737-1748, 2021.
[42] Hongwei Wang, Hongyu Ren, and Jure Leskovec. Relational message passing for knowledge graph completion. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1697-1707, 2021.
[43] Asiri Wijesinghe and Qing Wang. A new perspective on" how graph neural networks go beyond weisfeiler-lehman?.. In International Conference on Learning Representations, 2021.
[44] Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recom- mender systems: survey, ACM Computing Surveys (CSUR), 2020.
[45] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2018
[46] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. Proceedings of the 21th ACM SIGKDD international conference knowledge discovery and data mining, pages 1365-1374, 2015.
[47] Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. In NIPS, 2017.
[48] Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In Interna- tional conference on machine learning, pages 7134-7143. PMLR, 2019.
[49] Jiaxuan You, Jonathan Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. CoRR, abs/2101.10322 2021.
[50] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in Neural Information Processing Systems, 31:5165-5175, 2018.
[51] Muhan Zhang and Yixin Chen. Inductive matrix completion based on graph neural networks. In International Conference on Learning Representations, 2020.
[52] Muhan Zhang and Pan Li. Nested graph neural networks. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[53] Yongqi Zhang and Quanming Yao. Knowledge graph reasoning with relational digraph. In Proceedings of the ACM Web Conference 2022, pages 912-924, 2022.
[54] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: theory of using graph neural networks for multi-node representation learning, Advances in Neural Information Processing Systems, 34, 2021.
[55] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. arXiv preprint arXiv:2 2021.
13

---

[56] Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B, 71()))6233 630, 2009.
[57] Jing Zhu, Xingyu Lu, Mark Heimann, and Danai Koutra. Node proximity is all you need: Unified structural and positional node and graph embedding. CoRR, 0ass/202.115822 2021.
[58] Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman- ford networks: A general graph neural network framework for link prediction. arXiv preprint arXiv:2106.06935, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We faithfully summarize the paper in the abstract. (b) Did you describe the limitations of your work? [Yes] As described in the Section 5 and Appendix C
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work only involves existing datasets and solves general graph learning problem without negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Assumption is described in the Theorem [
(b) Did you include complete proofs of all theoretical results? [Yes] In Appendix A
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters how they were chosen)? [Yes] As described in the implementation details of Section [5]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] As shown in the experiment result tables.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] In the discussion of Section 5
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] The datasets and model source code repositories are all cited.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No] The datasets and source code are open source information allowed for research use.
(c) Did you discuss whether the data you are using/curating contains personally identifiable
information offensive content? [No] The data using is known to be de- identified.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "yRm26goX47-", "reviewer": "Reviewer_CvY7", "summary": "The paper deals with supervised learning on graph structured data for which the most common framework of GNN is limited in expressivity by 1-WL test in terms of its identifying capacity of graphs. More expressive GNN models operate on either higher order tuples of nodes or involve preprocessing of substructures, both of which involve more computation which is not scalable to large graphs. In this paper, the authors propose using the geodesic information between pairs of nodes which includes full shortest-path information. The method includes horizontal geodesic (set of nodes in shortest path) and vertical geodesic (1-hop neighbors which occur in any shortest path). Experimental results on Link Prediction and graph prediction datasets are shown as empirical evidence for the proposed approach.", "questions": "Please address the weaknesses mentioned above.\n", "limitations": "I did not find limitations of the approach being discussed in the paper. There is no potential negative societal impact.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n1. The paper addresses an important problem of finding efficient ways of improving the expressivity of the GNNs.\n1. **Novelty**: Although the use of shortest path information or distance encodings is shown by some recent works for improving expressivity of GNNs, I find there is good enough novelty in exploring this approach further by incorporating full geodesic information. I find the “vertical” and “horizontal” geodesics proposed to be interesting ways of incorporating the geodesic information explicitly. \n1. The geodesic method can distinguish graphs which go beyond distinguishing capacity of mere distance encodings.\n1. Experimental results on Link prediction datasets seem to be good.\n1. Paper is well written and the presentation is clear. I especially appreciate the intuitive explanations with example graphs to show how “vertical” and “horizontal” geodesics are helpful. However, more annotations in Figure 4 would be helpful.\n\n### Weaknesses:\n1. **Permutation invariance**: The method belongs to randomization based techniques to improve expressive power of GNNs since one random shortest path is chosen in computing horizontal geodesic and hence cannot guarantee permutation invariance. This in itself is not a weakness, however, it needs to be acknowledged and the paper needs to be clearly positioned accordingly. \nAt least some experiments should show comparison with randomization based expressive GNNs like RNI (Abboud  et al. (2020)) and PF-GNN (Dupty et al. (2021))\n1. Since the aim of the paper is primarily to go beyond 1-WL GNNs, then it should present experiments where GD-GNN is able to identify graphs not identifiable by 1-WL GNNs like on Circular skip link, Strongly regular graphs etc.. Most papers on the topic of expressive GNNs do exactly this. Such experiments are missing. It would be helpful to see the comparison with higher-order K-GNNs, PPGNN (Maron et al.(2019)), RNI, PF-GNN in order to assess where GD-GNN stands in comparison with other more expressive models.\n1. It is not clear how exactly the geodesics are generated efficiently. For ex, how to find vertical geodesics of a pair of nodes. Naively, you would need to  find all shortest paths between nodes and take subset of 1-hop neighbors. Naive way of generating geodesic would take not less than O(n^3) time which is all pairs shortest path. Is  there an efficient way of computing geodesics of all nodes at once? \n1. I don’t understand “decoupling” and its usefulness as it is said in line 155-158. What do you mean running GNNs only once? Why can’t we preprocess geodesic information and then use it along with GNN message passing. For ex, preprocess horizontal geodesic, run GNN message passing and pool embeddings from geodesic subset of nodes and repeat this iteratively. Comparing both GNN and geodesic computation, I see that GNN is more efficient than computing geodesics and don’t understand why run GNN only once. Also, do vertical and horizontal geodesics have any learnable parameters?\n1. Results on link prediction are impressive. However, the results on graph prediction are not and the baselines used are dated. Since, the motivation of the  paper is to build more expressive GNN, other more expressive models like K-GNN, RNI, PF-GNN should be shown. If the performance is not at par, it is not an issue, however, it should be acknowledged.\n1. One of the claim is runtime efficiency compared to other expressive models. However, in worst case, I believe the runtime of GD-GNN is also not less than O(n^3), since the subgraph around a node can be O(n) size. This is same as 3-WL time complexity. Please clarify the worst case runtime in terms of number of nodes n.  Also, in runtime experiments, are you also taking the geodesic computation into account?\n1. Ablation study can be expanded. You can test vertical geodesic by instead taking all neighbors of pair of nodes and not just neighbors which are part of shortest paths. This would show if vertical geodesic is important. For horizontal geodesic, you can test does full shortest path is needed or few hop nodes in the shortest path are good enough. You can vary number of hops for ablation.\n1. In Section 3.3, the paper first discusses all node, link and graph prediction tasks but doesn’t show experiments on node prediction. \n1. For link prediction tasks, I think it would be better to compare with other methods like Position-aware GNNs (You et al.(2019)) which also in a way tries to capture shortest path information.\n\n**Overall**, I find the idea and theme of the paper novel and significant. However, in the present form there are many issues as identified in the weaknesses which makes the paper somewhat in borderline.\n\n### References:\n1. Abboud  et al. (2020). \"The surprising power of graph neural networks with random node initialization.\" arXiv preprint arXiv:2010.01179\n1. Dupty et al. (2021) \"PF-GNN: Differentiable particle filtering based approximation of universal graph representations.\" International Conference on Learning Representations.\n1. You et al.(2019) . \"Position-aware graph neural networks.\" International conference on machine learning. PMLR\n\n\n########################\n\nUpdate:\nI Thank the authors for the response and additional experiments. Based on the revision, I'm updating the rating and would be happy to see the paper at the conference.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "y3Fh0RXYDrZ", "reviewer": "Reviewer_SHs4", "summary": "This paper proposes a novel mechanism to efficiently improve learned graph representations. It proposes an independent second layer built upon base GNN representations that can improve the performance and expressivity of the base GNN. This mechanism is the Geodesic pooling layer. The horizontal version works by pooling the node representations along the shortest path between a pair of nodes. The vertical version works by pooling the nearest neighbors to the target node along any shortest path between the nodes of interest. \n\nThe paper then proposes different techniques for using these geodesics for node-level, edge-level, and graph-level tasks. \n\nFor experimentation, they do experimental testing across different domains. They test on link prediction tasks for knowledge graphs and link prediction on OGB datasets. They also test on graph classification using TU and OGB datasets. Node classification tasks are not experimentally tested.\n\nThe results show very good results on edge level and graph level tasks.\n\nThere is also a bit of theoretical analysis showing that the model can distinguish certain types of graphs (r-regular) with a high and controllable likelihood. In addition there are good synthetic examples where existing works would fail to distinguish certain graphs or edges. ", "questions": "1) For node level tasks, how is the geodesic approach any different to sampling neighbors of a node and running a GNN? (maybe with included feature indicating node of interest). Does not seem like this approach would confer any advantage or difference in this realm.\n\n2) Since you use a max distance cutoff, how often do the graphs have links that are beyond the max distance? Does the model still predict these links in practice or does the model learn to never predict links between \"disconnected\" nodes?\n\n3) How would the presence of node features affect or limit the analysis?", "limitations": "Limitations/questions surround the node level tasks, analysis under the presence of node features. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality:\n\n++ Work is original. Ideas are novel. \n\n-- Should be comparison to how this differs from path based reasoning methods (many exist for KG completion)\n\nQuality:\n\n++ The work is a complete work and is of generally high quality. The ideas are well motivated. \n\n++ This approach seems very well attuned to link level tasks and would certainly be of interest to people working with these tasks (e.g. Knowledge Graph Completion). It also seems like it is better than the baselines in graph completion.\n\n-- Does not seem like there would be any advantage to using this on node-level tasks as there is basically no difference to existing GNNs. It is essentially sampling neighbors of a node and then applying another GNN on top of that. \n\n-- Also, no testing of node level tasks\n\n-- The KG completion task should not necessarily be considered state of the art. I think the baselines are fair for comparison, but there are other methods that take advantage of the textual data available via language modeling for better inductive knowledge graph completion. I think the authors should mention that they exclude text based inductive models for KG completion. Or they could add these baselines and see how they compare?\n\nIncluding:\n\nWang, Bo et al. “Structure-Augmented Text Representation Learning for Efficient Knowledge Graph Completion.” Proceedings of the Web Conference 2021 (2021): n. pag.\n\nDaza, Daniel et al. “Inductive Entity Representations from Text via Link Prediction.” Proceedings of the Web Conference 2021 (2021): n. pag.\n\n-- The theoretical analysis is limited to to r-regular graphs with no node features. This is not a common occurance, but does slightly support the idea that there may be an advantage over standard GNNs. However, in general, this work does not deal well with how node features affect the analysis. Authors state \"For simplicity, we use homogeneous graphs to illustrate our ideas and methods\" but the analysis likely does not hold up as well for non homogenous graphs. \n\n-- Small note: GNNs often use only a few layers because there is no performance advantage (e.g. over smoothing), not because of computational cost. (line 174)\n\n+- Small note: The horizontal geodesic seems like a good idea for connecting far nodes, however, there is still a max depth. \n\nClarity:\n\n++ The writing is generally precise and clear. \n\n-- The use of the v1 and v3 splits  for inductive kg completion is slightly cherry picked (the full table is in the appendix)\n\nGrammar/Spelling:\n\nFigure 4: distingshui -> distinguish\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "N9cPu3nJHn8", "reviewer": "Reviewer_wYEs", "summary": "Among existing graph neural networks (GNNs), standard GNNs are efficient but cannot distinguish structures beyond 1-WL test, while subgraph extraction or customized labeling methods are powerful but require much more computation. This paper proposes a new graph neural network (GNN) architecture, which seeks for a new sweet point between efficiency and effectiveness. The idea is to first compute node representations with a standard GNN, and then readout augmented node/edge/graph-level representations via geodesics. The authors propose two variants for Geodesic GNN, namely horizontal and vertial geodesics. Experiments on both link prediction and graph classification tasks show that geodesic GNNs achieve results on par with SotA models, while only take time similar to standard GNNs.\n\nThe contributions of this paper include:\n\n1. Propose geodesic GNNs that are both effcient and effective.\n2. Theoretically prove geodesic GNNs are more powerful than 1-WL test.\n3. Empirically show that geodesic GNNs achieve good results in both performance and time.", "questions": "- Line 55: Why are higher-order GNNs at least cubic complexity? Could you provide a reference to that?\n- Line 125: Taking link prediction as an example\n- Line 151: Why is the shortest path viewed as a chain of nodes with embeddings one? What are the embeddings discussed here?\n- Line 179: You may provide a motivating example here.\n- Line 198: If the pooling layer is a small plain GNN, is geodesic GNNs as slow as SEAL?\n- Line 214: Why are geodesic nodes close to $v$ ignored here?\n- Line 220-224: To my understanding, this property has been discussed in NBFNet[1] and RED-GNN[2] before. It’s better to cite them to provide a fair context.\n- Line 297-299: If I understand correctly, the main advantage of GD-GNN over NBFNet is that it avoids the cost of GNNs in subgraph extraction, but GD-GNN still needs to perform subgraph extraction for each query. Why is GD-GNN efficient in any scenario? Is it over-claiming?\n- Appendix B: The time complexity analysis is too optimistic. The authors seem to use the average degree of a node in the full graph / in a local subgraph interchangeably, and assume they are small constants. This may not be true. For example, for a scale-free graph, the average degree may be a constant, but the average degree in a local subgraph may not! This is because every node is likely to be connected to nodes with large degrees, and therefore a lot of subgraphs contain nodes with large degrees. I suggest including the complexity of standard GNNs, SEAL, NBFNet for a fair context.\n- Table 3: Why does NBFNet cause OOM? Could you give an explanation?\n\n[1] Zhaocheng Zhu et al. Neural bellman-ford networks: A general graph neural network framework for link prediction. NeurIPS 2021.\n\n[2] Yongqi Zhang, and Quanming Yao. Knowledge graph reasoning with relational digraph. WWW 2022.", "limitations": "The authors don’t discuss the limitations and societal impacts in the paper. I would suggest the authors adding one paragraph to discuss that. For example, some limitations could be that GD-GNN can only be applied with simple geodesic readout, otherwise it may still have time complexity issues.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n- The idea of using geodesics for readout seems novel to the community. It fills an important gap in GNNs beyond 1-WL test.\n- The proposed geodesic GNNs are more powerful in theory, and trades off efficiency and effectiveness better in experiments.\n- Geodesic GNNs are general and have the potential to be applied to most standard GNNs.\n- The paper is well written and easy to follow.\n\nWeakness\n\n- Although the authors propose node-level representations for geodesic GNNs, there is no experiments on node classification tasks to verify its efficiency and effectiveness.\n- The authors are ambiguous about the time complexity of geodesic GNNs. In general, the complexity of geodesic GNNs should between standard GNNs and subgraph extraction. The condition for “GD-GNN maintains the good efficiency of basic GNN models” is that the geodesic readout can be amortized by the cost of the GNN. This is only true for some simple geodesic readout functions, like the two proposed in the paper. The authors should make this more explicit to the readers. Also the time complexity in Appendix B is too optimistic.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept