GIR Framework: Learning Graph Positional Embeddings with Anchor Indication and Path Encoding
Authors: Yuheng Lu
Jinpeng Chen
Chuxiong Sun
Jie Hu
Venue: ICLR 2022 Submitted (2022)
Keywords: Graph neural networks
Anchor based GNN
Node representation learning

Abstract: The majority of existing graph neural networks (GNNs) following the message passing neural network (MPNN) pattern have limited power in capturing position information for a given node. To solve such problems, recent works exploit positioning nodes with selected anchors, mostly in a process that first explicitly assign distances information and then perform message passing encoding. However, this two-stage strategy may ignore potentially useful interaction between intermediate results of the distance computing and encoding stages. In this work, we propose a novel framework which follows the anchor-based idea and aims at conveying distance information implicitly along the MPNN message passing steps for encoding position information, node attributes, and graph structure in a more flexible way. Specifically, we first leverage a simple anchor indication strategy to enable the position-aware ability for well-designed MPNNs. Then, following this strategy, we propose the Graph Inference Representation (GIR) model, which acts as a generalization of MPNNs with a more specific propagation path design for position-aware scenarios.  Meanwhile, we theoretically and empirically explore the ability of the proposed framework to get position-aware embeddings, and experimental results show that our proposed method generally outperforms previous position-aware GNN methods.

Under review as a conference paper at ICLR 2022
GIR FRAMEWORK: LEARNING GRAPH POSITIONAL EMBEDDINGS WITH ANCHOR INDICATION AND PATH ENCODING
Anonymous authors Paper under double-blind review
ABSTRACT
The majority existing graph neural networks (GNNs) following the message passing neural network (MPNN) pattern have limited power in capturing position information for a given node. To solve such problems, recent works exploit po- sitioning nodes with selected anchors or the message passing destination, mostly in a process that first explicitly assign distances information and then perform message passing encoding. However, those existing two-stage models ignore po- tentially useful interaction between intermediate results of the distance computing and encoding stages to some extent, due the model architecture designs. In this work, we propose novel framework which follows the anchor-based idea and aims at conveying distance information implicitly along the MPNN message pass- ing steps for encoding position information, node attributes, and graph structure in more flexible way. Specifically, we first leverage a simple anchor indication strategy to enable the ansition-awars ability for well-designed MPNNs. Then, fol- lowing this strategy, we propose the Graph Inference Representation (GIR) model, which acts generalization of MPNNs with more specific propagation path design for position-aware scenarios. Meanwhile, we theoretically and empirically explore the ability of the proposed framework get position-ave awaree embeddings, and experimental results show that our proposed method generally outperforms previous position-awee aware GNN methods.
INTRODUCTION
Graph, as an important data structure, is a powerful tool to represent ubiquitous relationships in the real world. Learning vector representations for graph data, benefits many downstream tasks the graph such as node classification (Kipf & Welling 2017) and link prediction (Zhang Chen, 2018). Many graph representation learning methods have been proposed recently, among those, Graph Neural Networks (GNNs), inheriting the merits of neural networks, have shown superior performance and become much popular choice.
Existing GNN models mainly follow the message passing neural network (MPNN) (Gilmer et al., 2017) pattern, which stacks message passing layers that aggregate information from neighborhoods and then update representations for each node. Typical MPNNs are limited by J-Weisfeiler- test (Xu et al., 2019), and lack of ability to capture the position information within the graph (You) et 2019), without distinguishable node/edge attributes, nodes in different part of the graph with topologically equivalent neighborhood structures even with different substructures may be em- bedded into the identical representation by typical MPNNs alone (You et al.) 2019: Li et al., 2020), as shown in figure T (b). A₁ and B2 cannot be distinguished with MPNNs and no distinguishable attributes (when ignoring colored anchor nodes).
Researchers have developed methods to alleviate this issue. Some earlier works adopt one-hot en- codings as extended node attributes (Kipf & Welling 2017). More recent methods utilize graph distance information to get position-aware embeddings. Anchor-based GNNs (You et al. 2019 Liu et al. 2019) select anchor nodes as positioning bases, and use position information related to anchors to break the structural symmetry (Figure (c)). Distance encoding (Li et al., 2020) utilizes distance information to push typical MPNNs beyond the "Weisfeiler-Lehmaal test limitation (Figure

---

Under review as a conference paper at ICLR 2022
(a) Input
(b) MPNN
PGNN/AGNN
Distance Encoding
Model
Figure I: Comparison of position-aware GNN methods. (a) (Modified from Li al. 2020 Exam- ple unattributed input graph, nodes start with the same letter (A, B or C) are structurally ly equivalent. Nodes in doubled circle (A₃ and B1) selected for demonstrating different position-aware GNN methods; the colored node (C1) will be chosen as an anchor for anchor- machor-bsedd GNNs. (b-e) Different position aware GNN methods: MPNN (with anchor labeling); PGNN/AGNN; Distance Encoding; GIR model.
Those existing position-awar GNN methods mainly explicitly pre-compute the distance between node pairs, utilizing them as node attributes or controlling of message passing steps, and then per- form message passing encoding. Due to the design choices for what and how to utilize distance information, those existing methods consider graph structure and attributes information encoded by GNN propagation and position information in relatively separate manner, potentially useful inter- action between intermediate results of the distance computing and encoding stages may be ignored.
In this paper, we follow the anchor-based GNN strategy and aim performing more flexible inter- action with graph structure, positioning and attribute information. With limited fixed anchor posi- tioning base selected, abundant position information could be assigned, boosting the performance of MPNNs in the position aware scenarios in a trackable way. Besides the explicit assigning strategy, here we mainly focus on conveying position information implicitly, order to retain the potential possibility for more flexible usage of the graph data, some information beyond pre-performed graph algorithms (e.g. shortest path distance algorithm) may potentially useful to be captured. Our motivation comes from the structural similarity between GNN message passing and distance relax- ation process of the Bellman-Ford shortest path algorithm (Bellman 1958), we show that with simple indication of anchors and appropriate design for message passing functions, MPNNs can keep track of the shortest paths from anchors. Further, inspired by a relaxation order improved variant of Bellman-Ford algorithm (Moore) 1959), propose generalized MPNN architecture, termed Graph Inference Representation (GIR), as a more specialized model for the position-aware scenario. The GIR model propagates messages from anchors along paths each node, and outputs of the k-th layer encode k-step representations related to anchors. On an unweighted graph with no distinguishable node attributes, the proposed strategies provide natural ways help break the structural symmetry as the previous anchor based GNNs could (Figure (b&e)).
Our contributions are summarized follows:
1. We propose general anchor labeling strategy, enabling MPNNs for mimicking the Bellman-Fore algorithm and getting position-awee awwar embeddings implicitly under anchor- based GNN pattern and discuss theoretical implications and experimental realizations.
2. We propose the Graph Inference Representation (GIR) model that contains more special- ized structure for learning position-awand embeddings.
3. Empirically, evaluate the performance of proposed methods for tasks in position-awee datasets, experimental results show that our position-awarr awware GIRs achieve generally higher performance.
2

---

Under review as a conference paper at ICLR 2022
The rest of the paper is organized as follows. Section reviews related works. Section introduces notations and definitions, theoretical implications are discussed. Section details the proposed GIR framework. Section SectionSSpresse presents the experiment and gives a discussion of the results. Finally, section presents our conclusion.
RELATED WORKS
Our work follows the anchor-based GNN pattern from the position-aware GNN literature, with the design inspired by the Bellman-Ford algorithm.
2.1 POSITION-AWARY GNNS
Position-aware GNNs leverage distance information in the message propagating encoding process. Distance Encoding (Li et al., 2020) follows the MPNN propagation design and extends it with pre- assigned graph distance from the propagation target to each node (Figure I (d)). For each message propagation step on a target node v, only distance from u are utilized, potentially useful distance from other nodes not considered.
Anchor-based GNNs use selected anchor nodes as a positioning base, existing methods mainly fol- low the two-stage pattern: select anchor nodes first, and then encode the information related to anchors. Position-aware GNN (PGNN) (You et al. 2019) selects anchor node sets randomly before running every forward of the model get low distortion embedding capturing global position information, a PGNN layer directly propagates message from the selected anchor node set to each target node, weighted by the pairwise distance. The random anchor selecting strategy of PGNNs leads to unstable limitation, some more recent work uses fixed anchor nodes instead to overcome this issue. AGNN (Liu al. 2019) pre-selects fixed anchors by minimum point cover nodes al- gorithm; GraphReach (Nishad et al. 2020) follows the fix anchor setting and adopts random walk reachability estimations instead of the shortest path distance. Those methods adopt the strategy that ignores graph structure when performing message propagation.
Our GIR framework follows the anchor-based GNN pattern and differs from previous works in the position information encoding and utilizing strategy (depicted in figure D GIRs are capable of encoding position information implicitly. taken intermediate results in computing shortest path distance into consideration, and under specific settings, corresponding distances related to anchors and the graph structure are utilized together.
2.2 BELLMAN-FORD ALGORITIM
The Bellman-Fort algorithm (Bellman 1958) computes the shortest path distance from a single source node to each node in weighted digraph. For graph g (V, E), source node 8, the algorithm performs V relaxation iterations, maintaining the shortest path from a with at most i edges in the i-th iteration. A relaxation step iterate over all edges, correct distance to better ones. The relaxation of distance on i-th iteration and edge (u, v) with weight w is defined as,
dist min (distt dist + w)
where dist is initialized as,
dist.
V s otherwise
(2)
A variant of Bellman-Forde algorithm (Moore 1959 notices that if the distance value of node has not been changed since its last relaxed, edges out e are no need to perform relaxation.
Learning graph algorithm including the Bellman-Ford algorithm with MPNN has been experimented in Velikovi et al. (2020), they show the effectiveness of adopting max-pooling as aggregator, and propose to learn with intermediate results of graph algorithms. Our work goes further toward the implication from the Bellman- Ford algorithm. and proposes a more specialized message passing strategy beyond typical MPNN for this. In addition, experiment setting of Velikovi et al. (2020) focus on a single specific source node, and in the experiment on synthetic datasets, we generalize this to adapt the anchor-based GNN settings.
3

---

Under review as a conference paper at ICLR 2022
Table 1: Notations
Notation
Description
g
the input graph
E,E
the node/edge set of G the i-th node in G the node attribuies/repreeenaatioss of G
V;
X, Z
24, 24
the attrbutefrepresentation 0
W
the edge weights of G
(w))
in-neighborhhods of node v in G
&
the anchor node set successors of any node in source node set 8 C V concat vector a and b
Successors({,S)
[a|
3 PRELIMINARIES
3.1 NOTATIONS
A graph can be represented as G = (V, where = {VI,... " J is the node set and & {(us, By) Pt, V/ E V) the edge set. Nodes are augmented with the feature matrix X, which is either imput attributes if available or placeholders. Edges may augmented with the optional weights W. in-neigbborhoods of node are represented as N(v).. Notations are summarized in table
3.2 POSITION-AWAND EMBEDDINGS
One goal of the anchor-based GNN model is to utilize anchors as bases to encode position-aware information for each node. To capture this intuition, PGNNs YYou et al. 2019) view embeddings as position-aware if the shortest path distance between node pairs could he reconstructed from their embeddings. which hard for models with fixed anchors satisfy. Here we define position-award embeddings related to anchors (Definition D. Considering that the shorest path distance to node set has different definitions, such the shorest path distance to anchor nodes to any node in the anchor node set, or whether to focus on shorest path with limited hop. Here in the definition [ we focus on limited hop shorest path distance (for alignment with MPNN) to any node in specific node sets, for retaining high generality, and the union of those node sets need to be the anchor node set, for consisting with the position-ave aware embeddings related to anchors definition.
_
Definition (Position-aware Embeddings). For a C. P(AA), Upr A, where P(A) the power set of node set A, the node embedding Z {2 f(w))lV,, V.. where f is graph encoder that maps a node to its embedding, is k-hop of --pssition-awatt if there exists functioos (gx (-)VV' of dep (vs, A!), where (v, A!) is the k-hop shortest path distance between node o and any node in the node set &! the graph G. If all elements in a are singleton, brakets of sets inner a could be omitted.
such that gad (2,)
As examples for definition 1. could reconstruct k-hopp shorest path distance from any node in the anchor set from k-hop { { poot-ptoiioonawarree embeddings, and k-hop shorest path distances from all anchor nodes from k-hop À- a-position-aware embeddings, these two settings will be discussed most commonly in following sections.
3.3 INDICATABILITY
Here discuss the thcoretical implicitly of our GIR framework design. We begin with our mo- tivation of mimicking the Bellman- FFrd algorithm with MPNNs, the concept indicatability is introduced an effective tool for the design of the GIR framework.
A natural idea for an MPNN to mimic the Bellman-Ford algorithm is to perform neural relaxation functions and enable the capability of keeping track of the intermediate limited hop shortest path distances. The motivation of mimicking the Bellman-Forr algorithm and getting position-awee awaree embeddings implies the capability for reconstructing k-hop shortest path distance from k-th layer.
4

---

Under review as a conference paper at ICLR 2022
To capture this intuition, introduce the concept of indicatability that implies the existence and constructibility of functions that reconstruct specific information related to a node set from a vector representation.
Definition 2 (Indicatability). For A C A., the function set I is Al-indicatable over function if there exists a constructable function Ta such that for all 0z E A, (2,) = [(v,, A').
The indicatability (Definition 2 is defined over pre-defined function ʃ that maps a node v; and a node set A' to a real value (e.g. the multi-souce shortest path distance function), which could be mimicked by a neural network module that takes 2,, the embedding of vs as input and could generate outputs include f(z,, A'), as the target neural network module is capable for mimicking over A', we say that is A' a'-indicatablee over f. Moreover, the k-hop ee---ptiioonavee aware definition (Definition I can be restated as the existence of f-dist with A' -indicatability over k-hop limited multi-souce shorest path distance function, for A' E ot.
3.4 NEURAL BELLMAN-FORD WITH MPNNS
Here show that well-designed and parameterized MPNNN is capable for representing the process of updating the existence of A' -i-idiccatable f-dist k-1 for z to A' A'-indicatable f-dist. over Zk in the k-th layer, the mentioned corresponding functions are directly implemented or implicitly mimicked by well-learned parameterized multi-layer perceptrons (MIP), and the effectiveness is guaranteed by the inductive proof of the Bellman-Ford algorithm and the universal approximation theorem (Hornik 1991).
Firstly, a well-learned MLP is expected to reconstruct (k-1)-hop limited shortest path distances from the inputs of k-th layer, with the existence of A -indicatteele f-dist which can be written as,
[dist 1,,, f-dist k- ( (=(-1)
then, considering the aggregate and update pattern of MPNNs, we expect an MPNN layer performed on node to mimic a relaxation iteration on u. Deriving from the Bellman-Fort relaxation function (Equation D. the expected function for an MPNN layer to mimic could be,
I min( (min([dist -diisth-11_... 1,,, [dist '), + VV= E
(4)
or equivalently.
[ min([dist "1 min( ((distt) J, + We=(m.e) E (())))))
(5)
where the binary min function is expected to be mimicked by well-learned ML.s before pooling in the aggregator or the update function, while the min function over the set is expected to be mimicked by a well-learned parameterized sequential encoder like Recurrent Neural Networks (RNNs) or more commonly used max-pooling. A simple ordering of {dist IVA' E A} as part of output Z would maintain the existence of A' -indicatable f-dist".
There remains an issue of initialization. For the first layer, there is no natural existence of A'- indicatable f-dist as in the Bellman-Food algorithm, the distance value of source nodes is initialized as O, while others co. We would expect the updated distance value used in the min functions to be an enough large value, but not a natural way to explicitly assign it as node attributes, and instead adopt simple anchor indication strategy, f-ind (z:) indicates whether the node v is in A'. And the expected function for the first MPNN layer to mimic, corresponding with equation 4 and would be,
the f-ind with A' o'-indicatability, where
[ min (W= EN()) A findgg((x))))
(6)
3.5 PROBLEM DEFINITION
The GIR framework is designed for node representation learning tasks, paying special attention to the capacity for getting position-aware embeddings. As general encode for node representation learning, GIR takes graph G = (V,E) with node attributes and optional edge weights W as inputs, and embed nodes into d d-dimensional vectors, represented as Z E R <d The node repre- sentations are normally used in downstream tasks like node classification and link prediction.
5

---

Under review as a conference paper at ICLR 2022
(a) Input Graph
(b) Message Propagating Paths
Figure 2: (a) Example input graph, colored nodes are chosen anchors. (b) Message propagating edges for each layer in a 2-layer GIR model, Colored nodes highlight propagating source nodes.
4 METHODOLOGY
Here we proposed the GIR framework, acting extension of MPNNs to get position-aware embeddings. The GIR framework based on the f-ind idea (Section 3.4 and a further specialization on the propagation paths, which will introduce first, the overall design of the GIR framework will be elaborated then, finally, we take a discussion about using GIR as general graph encoder.
4.1 GIR MODEL: MORE SPECIFIC PROPAGATION PATHS
Motivated by the relaxation order improved variant of the Bellman-Ford algorithm (Moore 1959). consider designing an MPNN architecture with more specific propagation paths. As the condition of whether to relax is dependent not only on the graph structure, we loose this condition to whether node is reached by the breadth-first search from the source nodes. Under these considerations, we propose the Graph Inference Representation (GIR) model, which acts as a generalization of MPNNs, propagating messages from anchors along breath first search paths (Figure 2 The GIR model would be degraded to an MPNN or a non-graph encoder if selecting all nodes or no node for the anchor set.
There is a general consideration in MPNNs that how to deal with nodes without in-edge in the propagation step. and common workaround is adding self-loop the input graph. the GIR model, this becomes a more important issue as we additionally introduced this situation for nodes with the important role (anchor nodes that without other anchor nodes as neighborhood), We take zero vector as message if no in-neigbborhood exists. In fact, considering a graph with only the same placeholders as node attributes and no node has zero in-degree, whatever the structure of propagation tree is, all nodes are embedded identically. Adopting zero vector as dummy message is a simple but effective strategy for guaranteeing the existence of f-ind with {A) J-indicatability, thus k-layer GIR with an anchor set & is k-hop 11o)-postiion-a
4.2 THE GIR FRAMEWORK
Having discussed the design choices for MPNNs and the propagating path variated GIR model, here we summarize the working process of the whole proposed framework for getting position-aware embeddings (Algorithm) building blocks are elaborated follows.
Anchor Selection (Algorithm D line 1) The intuition behind anchor-based GNNs is that some nodes perform a more important role in the graph for the specific task (Liu et 2019 Xu al., 2020). Specifing influential anchor node set is highly data depent task, and it IS a important research topic in the network analysis. We adopt degree centrality, the conceptually simplest choice, as a starting point. Also, the high interaction of degree centrality suggests an effective coverage through k-step message passing, and we heuristically believe it to be a promising choice for acting as positioning base. Concretely,
adopt degree centrality based GA-MPCA algorithm used in AGNN (Liu et al. 2019) as default choice. For data or tasks with more heuristic, other choices may be adopted. For example, for web page networks, PageRank (Page al. 1999) may be more capable choice, and for networks constructed by snowball sampling (Goodman 1961). seed nodes may be directly marked as anchor.

---

Under review as a conference paper at ICLR 2022
Algorithm The GIR framework.
Input: Graph 9 = EV;E); Node input attributes {ae, Ve E V); Edge weights W (optional)
Parameter: Number of layers L; Anchor selection function Select Anchor indicatabil- Message functions M; Neighborhood aggregator functions AGGR; Node update functions U.
ity mark function Indicatable
Output: A-position-awar embedding {Zu, Yu e V)
1: A f PedeectAnchordy
2: h. f [Tg |
3: BFS < A
4: for I
do 5: for in V do
6:
sre + node set with lower bound M(e) n BFS and upper bound ((v))
7:
m, t AGGGR (h ,hh W (e=(w)))
8:
hr - ('i,1, ,m,)
9: end for
BFS Successors(
11: end for
z = h
13: return
Anchor Indication (Algorithm line 2) Assigning extend node attributes for guaranteeing the existence of fiidd with A' -iindicatability for all A' E sf for a desired o ppossition-awaa capability. Here we introduce two simple strategies as the realization of f-inds, and note that those are optional for using the GIR model (Section 4.1) if only { p-soopotttto-aaaaa aware capability is expected.
Anchor Labeling: pellj-oosttoo--wwaee Assigning one for anchor nodes as an extended attribute, and zero for others. It guarantees the existence of f-ind with A-indicatability, by checking whether the extended attribute is one.
Assigning one-hot labeling for anchors as ex- tend attribute and zeros for others. For all anchor node a E A. the existence of f-ind with (n)-indicatability is guaranteed by indexing the ID of a in the extended attributes. This strategy is similar to the node one-hot labeling trick but introducing much fewer input di- mensions. Note that the anchor ID labeling is not capable of inductive settings, for it is sensible to the order of anchor nodes.
Anehor ID Labeling: (A- (A-position-awarc
Message Propagation (Algorithm line 3-12) For the propagation paths, the GIR model (Sec- tion (..1) gives limitation for determining neighborhoods in the MPNN message- passing steps (tracked as BFS in algorithm [T, and we take this limitation as lower bound in the whole frame- work. The message functions M preferred be parameterized encoder tations and optional edge weight, and the update functions M are preferred to be parameterized encoder over node message and representations, encoders. Max-pooling is the most preferred choice for the aggregator AGGR.
node represen-
commonly choose MLP as the parameterized
4.3 GIR AS GENERAL GRAPH ENCODER
Although the starting point of GIR is to learn embeddings that are aware of position information measured by shorest path distance, design choices of GIR encourage be general graph encoder with potential to be used for wider range of areas, here we discuss some related considerations.
Firstly, when using GIR model with a subset of nodes as anchor, information loss of graph structure would be occured. We suggest to apply GIR model on multiple anchor set and concatenate for out- puts (named GIR-MIX), a mixture of GIR model and MPNN (GIR with all nodes as anchor) would be helpful for more general cases, Moreover, the mixture of models with A s/, ... ..,,, -posiiion aware capability would (Ng A) -----poition-awwe aware. Then for the issue of inductive setting, consid- ering the components of GIR framework, common anchor selection methods with general strategy are inductive, and the message passing is also inductive. And for the indication labeling strategy, only anchor labeling (which implies (A) --ositioon-aware is inductive, order aware strategies like

---

Under review as a conference paper at ICLR 2022
Table 2: Results on synthetic datasets. Bold font highlights the best results.
{ weeigtet
{A]-unweighhte
A-weighted
A-unwwighted
mean
last
mean
last
mean
last
mean
last
MPNN
3.4
3.6
0.7
4.0
4.0
0.5
0.5
MPNN anchor labeling
0.1
0.1
0.0
0.0
3.5
3.5
0.5
0.5
GIR
0.2
0.2
0.0
3.5
3.5
0.5
0.5
w/ mean aggregator
0.9
1.1
0.1
0.0
3.6
3.6
0.4
0.5
MPNN anchor ID labeling
2.7
3.0
GIR + anchor ID laheling
2.5
2.7
0.1
0.1
w/ mean aggregator
2.9
3.1
0.1
0.1
GIR-MIX
2.3
2.4
0.1
0.1
anchor ID labeling will be failed in inductive settings. If more position aware capability needed, particularly, GIR-MIX provide inductive ability with pairwise tasks, which is same as in PGNN.
The time complexity of our default anchor selecting method O([V)2) (Liu et al. 2019)), and ((E)) for commonly used adjacency list representation of graph. For the message propagation, we compute the total propagation edges, including message from self-loop. For K layer vanilla MPNN, the time complexity is [ K| VV))), and for K layer GIR model, let D represents the maximum of node out-degrees, we take the upper bound with that leads to O(A|D + K(V)), and it is strictly lower than or in the worst equal to MPNN.
EXPERIMENTS
In this section, we first take experiments on synthetic dataset to validate the effectiveness of the GIR framework for getting position-awee -aware embeddings, then we demonstrate the performance of GIRs real world datasets used in position-aware GNN literature.
Datasets & Experimental Setup Based on our position- definition (Definition D we con- struet four synthetic datasets, with {A (A- posttoootionn information need weighted/unweighted
graphs, and following Velikovi et al. (2020), limited hop shortest path distances are predicted on each layer. We also take real-world datasets from previous position-and aware GNN literature (You et al. [2019] [i al.) (2020). Those datasets with too few scales or in an inductive setting are filtered out. The graphs in these datasets are unattributed, the graph structure makes the major contribution to the tasks, and previous works have demonstrated the effectiveness of position information in those tasks, here we set node input attributes ones as placeholders for a more fair comparison. More details of the datasets and eperimental setup are in Appendix A.I
We choose baselines from MPNNs and anchor-based methods literature. The MPNN baseline uses a linear transformation for message and update functions, which keep the same as in proposed models in the GIR framework. We take PGNN, AGNN and Distance Encoding (DE) as position aware GNN basclines, among those, PGNN and AGNN anchor based methods, and the AGNN with fixed anchor is most related to our experiment setting. We take experiments for the GIR frame- work variants over: (1) MPNN GIR message passing; (2) anchor labeling [[8])-oosiiion-waar)) or anchor ID labeling (A-position-awarr) anchorindication strategies; (3) max-pooling and mean aggregator; (4) GIR-MIX over all anchor node (A- (a-pos)tion-aware). Explicily assigning distances and optional intermediate-hop distances in the anchor based setting are also experimented, and for synthetic datasets, those methods with explicit distance assigning are not evaluated.
Results and analysis For synthetic datasets, report the mean absolute error (MAE) for mean outputs every layer (mean) and on the last layer (last) in table ? Considering that the aver- age label value for these datasets (Table 4 in Appendix), the performance of the GIR framework with corresponding position-aware capability is quite promising. Models using mean aggregator generally inferior to the corresponding max- max-pooling models, which supports max-pooling to be a preferred aggregator. Variants using GIR propagation get outperformed results in A --sosiiinn- aware datasets but inferior in (A)-position-awar datasets. We owe the outperformed results the
8

---

Under review as a conference paper at ICLR 2022
Table 3: Results the position-aware real-world datasets, measured in test ROC AUC (in %) for link prediction (-Ip) and node pair classification (-npc) task, and in test accuracy (in %) for
node classification (-nc) task. highlights the improvement over the strong baseline DE, Bold font highlights top-3 results, highlights the best results.
email-npe
europe-ne
usa-nc
ce-link
ns-link
pb-link
PGNN
53.3
54.2
58.8
79.4
94.9
88.6
AGNN
89.6
52.4
61.4
84.9
89.7
93.4
DE
87.5
58.4
64.2
90.0
99.4
95.0
MPNN
50.0
25.4
25.2
50.0
50.0
50.0
w/ final distances
99,74
50.0
72.4*
91.5*
90.1
95,1
w/ all distances
99.8**
61.0* "
71.5*
87.7
88.2
95,4**
MPNN anchor labeling
51.0
26.4
25.4
52.7
79.3
65.2
GIR
50.1
25.3
26.7
55.3
81.1
63.4
MPNN anchor ID labeling
99.8**
52.2
66.0*
89.6
85.9
95.3*
final distances
99.8*
50.6
72.5*
91.3*
90.0
95.2
GIR + anchor ID labeling
99.8**
56.7
67.6*
89.9
89.9
95.1
w/ final distances
99.7*
53.3
76.0
91.3*
91.2
95.3*
more specific propagation paths in GIR models, thus more easily to learn the expected functions in the relatively complicated cases, while in the {A jo.-pposttion-waare datasets, both { paae--oottton-awarre models archives nearly perfect results, and the higher capacity of MPNN leads to slight superiority.
Results of experiments on real-woria datasets are reported in table where the DE record the best performance of DE variants reported in the original paper (Li et al. 2020) for datasets except Email. We only keep part of the results for highlighting some key aspects, full results and more analysis are in Appendix A.3 Results show that with the same input feature, the MPNN baseline fails to distin- guish different nodes. Explicitly assigning anchor based distances on MPNN improve performance by a large margin, and generally outperform or compete position-aware baselines, this demonstrates the effectiveness of the more flexible distance information interaction. Note that although accessing distance information to all anchor nodes, using this strategy alone is not A-position-ane aware, with no correspondence with anchor node ids. Anchor ID labeling provide slight improvement to this, and the GIR propagation strategy push the improvement further. And without explicit distance modeling ability, MPNNs with anchor labeling and vanilla GIRs
signing, with (A [A))-ositionnawaal generally get higher results, yet inferior to models with more powerful position-award capability, and variants with GIR propagation perform generally better, these results suggest the effectiveness of the anchor indication and the further GIR propagation strategy.
In Europe-nc, the substantial improvement is got with all distance assigning, that suggests the ef- fectiveness of intermediate limited hop distance information on the dataset, and in this case, GIR with anchor ID labeling outperforms those explicit final distance assigning variants, this suggest the potential advantage of the implicit learning strategy, as the information need by applying discrete graph algorithm may not clear in real-world scenarios. We ascribe the performence drop for as- signing intermediate distance on other datasets to the information redundant. Moreover, we note that GIR framework performs inferior Ns-link, and we ascribe it to the sparsity of NS dataset, unreachable nodes from anchors on the input graph will be not benefited from the GIR framework, and previous position- awarre methods with special propagation strategy get relatively higher results.
6 CONCLUSION AND FUTURE WORK
We propose the GIR (Graph Inference Representation) framework, following the anchor- based GNN pattern and aims at conveying distance information implicitly along the MPNN message-passing steps. Theoretical implications and experimental results show the effectiveness of proposed strate- gies, and considerations for more general usages of GIR framework are discussed. Our empirical evaluations are taken the synthetic datasets and relatively small scale real-world position-awen datasets used in the previous position-aware GNN literature, we leave the potential usage of GIR on larger scale scenarios for future work.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Robert Ackland et al. Mapping the us political blogosphere: Are conservative bloggers more promi- nent? In BlogTalk Downunder 2005 Conference, Sydney, 2005.
R. Bellman. On routing problem. Quarterly of Applied Mathematics, 16:87-90, 1958.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pp- 1263-1272. PMLR, 2017.
L. A. Goodman. Snowball sampling. Annals of Mathematicall Statistics, 32(1):148-170, 1961.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4 (2):251-257, 1991.
M. Kaiser. Nonoptimal component placement, but short processing paths, due to long-distance projections in neural systems. PLOS Computational Biology, 2006.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In International Conference on Learning Representations (ICLR). 2017.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):2-es, 2007.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33, 2020.
Chao Liu, Xinchuan Li, Dongyang Zhao, Shaolong Guo. Xiaojun Kang, Lijun Dong, and Hong Yao.
A-gmn: Anchors-aware graph neural networks for node embedding. International Conference Heterogeneous Networking for Quality, Reliability, Security and Robustesss pp. 141-153. Springer, 2019.
E. F. Moore. The shortest path through maze. In Proc. of the International Symposium the Theory of Switching, 1959.
Mark EJ Newman. Finding community structure in networks using the eigenvectors of matrices. Physical review E, 74(3)0036104, 2006.
Sunil Nishad, Shubhangi Agarwal, Arnab Bhattacharya, and Sayan Ranu. GraphReach: Position-
Aware Graph Neural Networks using Reachability Estimations. arXiv:2008. 09657 [cs, stat), September 2020. http::t///aaxkt
org a200 09657
arXiv: 2008.09657.
Lawrence Page. Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, 1999.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Petar Velikovi, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In International Conference on Learning Representations, 2020. URL
htttps://openreviees nwt...ee/foot fow.
Minjie Wang. Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song. Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint arXiv: 10X9vv9999.013111 2019.
Chunyan Xu, Zhen Cui, Xiaobin Hong, Tong Zhang, Jian Yang, and Wei Liu. Graph inference learn- ing for semi-supervised classification. In International Conference on Learning Representations, 2020. URL htl.ttts:: htttps://operrvv...e wwt.://wwweeeeeee..........t.ete www.:eee/ffoummmmmrmmmmmmm 1 evhhEkvH
10

---

Under review as a conference paper at ICLR 2022
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https:
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In International Conference on Machine Learning, pp. 7134-7143, PMLR, 2019.
M Zhang and Y Chen. Link prediction based on graph neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 5171-5181, 2018.

---

Under review as a conference paper at ICLR 2022
Table 4: Details of synthetic position-aware datasets.
Dataset
[
[
avg. [8]
weighted
position-aware setting
avg. label
[A]
layers
dist
200
100, 200
907.2
(A) ) position-aaaaa
8.1
dist-u
200
100, 200
907.2
X
(A) position aware
1.6
dist-a
2000
20000
/
A- a-position-aware
17.9
20
4
dist-au
2000
20000
X
A p-posiiion-aware
3.3
20
4
Table 5: Details of position-aware real-world datasets.
Dataset
[V]
[
A
Cite
Email
1005
25571
50
Leskovec et al.
2007
Europe
5995
20
Ackland et al.
2005
USA
1190
13599
50
Ackland ct al.
2005
C.ole
297
2148
20
Kaiser 2006
NS
1461
2742
50
Newman (2006)
PB
1222
16714
50
Ackland al.
2005
A EXPERIMENT DETAILS
A.1 DATASETS & EXPERIMENTAL SETUP
We first detail the construction of synthetic datasets. For (A) (aJ-position-awnn setting, we generate 160 graphs with 100 nodes each for training, 20/20 graphs with 200 nodes each as valid/test set, and for A A--position-wwart setting, as anchor ID labeling strategy is not inductive, we generate one graph with 2000 nodes, train/valid/test sets are randomly split by 6:2:2. In the weighted setting, we assign edge weights uniformly sampled integer from 2 to 10, and in the unweighted setting, the distance between every connected node pair would be Details of those synthetic datasets are listed in table 4
For real-world datasets, following Li et al. 2020), we split train/valid/test sets by 8:1:1. Details of those real-world datasets are listed in table
For each dataset, we report the test set performance at the best model with the valid set, and the final results are reported over 20 runs with different random seeds generated synthetic data samples or on the randomly split dataset for real-world datasets to keep consistent with DE baseline.
A.2 IMPLEMENTATION DETAILS
Our implementation is based on Deep Graph Library (DGL) (Wang et al., 2019). with Py- Torch (Paszke et al., 2017) backend. For synthetic datasets, we use Adam optimizer for training, hyperparameters are set heuristically, listed in table[4 For real-world datasets, we mainly follow the hyperparameters settings in Li et al. (2020), with learning rate tuning in le-3 and lc-4; hidden size set to 100; dropout set to 0.2; using 3 layer models for all datasets; the number of anchors are set heuristically according to the scale of each dataset and is also restricted by the GA-MPCA anchor selecting algorithm, listed in 5
A.3 MORE RESULTS AND ANALYSIS
We note the full experiment results real-world datasets (Table 6) and take some complementary analysis here.
We first note some key aspects for highlighting the improvements GIR framework in table 7 We note the improvement of using explicit distance assigning on MPNN in (Table 1-2), which highlights the effectiveness of distance information. Table 7 3-4 lists the improvements of the GIR framework with different position-awee aware settings, settings with explicit distance assigning not considered here for more clear comparison. The improvements GIR propagation strategy highlighted in table 7 5-6, the comparisons taken on MPNN with same position-aware
12

---

Under review as a conference paper at ICLR 2022
Table 6: Full results the position-aware real-world datasets, measured in test ROC AUC (in %) for link prediction (-Ip) and node pair classification (-npc) task, and in test accuracy (in %) for
node classification (-nc) task. highlights the improvement over the strong baseline DE, Bold font highlights top-5 results, highlights the best results.
email-npe
europe-ne
usa-ne
ce-link
ns-link
pb-link
PGNN
$3.3
$4.2
58.8
79.4
94.9
88.6
AGNN
89.6*
61.4
84.9
89.7
93.4
DE
87.5
58.4
64.2
90.0
99.4*
95.0
MPNN
50.0
25.4
25.2
50.0
50.0
50.0
w/ final distances
99,74
50.0
72.4
91.5*
90.1
95.1
6
w/ all distances
99.8*
61.0*
71.5*
87.7
88.2
95.4*
MPNN anchor labeling
51.0
26.4
25.4
52.7
79.3
65.2
w/ aggregator
72.6
$2.7
52.6
84.8
79.5
92.3
final distances
99.74
72.2
91.6
90.0
95.1
10
w/ all distances
99.84
61.0*
70.5
87.6
87.9
95.5
11
GIR
50.1
25.3
26.7
55.3
81.1
63.4
12
w/ aggregator
50.3
27.9
32.4
55.9
80.3
60.4
final distances
99.74
74.7
91.3*
91.2
95.3*
14
w/ all distances
99.84
59.94
74.1*
87.9
90.0
95.5
15
MPNN + anchor ID labeling
99.8*
52.2
66.0*
89.6
85.9
95.3
16
w/ mean aggregator
99.6*
51,4
66.1
89.0
67.0
94.7
17
w/ final distances
99.8*
50.6
72.5*
91.3*
90.0
95.2
w/ all distances
99.8*
62.1
70.2*
87.8
88.2
95.5
19
GIR anchor ID labeling
99.8
56.7
67.6*
89.9
89.9
95.1
20
w/ mean aggregator
99.94
51.2
66.3*
89.9
89.6
95.3
w/ final distances
99.74
76.0
91.3*
91.2
95.3
22
w/ all distances
99.84
59.2
74.7A
88.1
90.0
95.5
23
MPNN node onc-hot labeling
100,0*
48.5
61.3
87.9
91.8
93.7
GIR node one-hot hot labeling
100.0*
59.5
68.6
88.4
86.6
94.1
GIR-MIX
65.6
27.9
35.4
81.3
86.3
84.6
Table Highlights for key aspects of the results on real-world datasets (Table Average improve- ment of the aspects every datasets noted (in %), references of comparisons noted with the line number in table
variants
references
email -mpe
europe -ne
usa -ne
ce
ns -link
pb -link
-link
MPNN final distances
5-44
99.4
187.3
83.0
80.2
90.2
2 MPNN w/ all distances
6-+4
99.6
140.2
183.7
75.4
76.4
90.8
(A) -positionnaware A- --ositioonawwae
7-14,11-4
1.1
1.7
3.3
8.0
60.4
28.6
15-44,19-4
99.6
114.4
165.1
79.5
75.8
90.4
GIR (w/o distance assigning)
11-+7,19->15
-0.9
2.2
3.8
2.6
3.5
-1.5
GIR (w/ distance assigning)
13-99,14+10,
-0.0
0.7
5.0
0.0
1.8
0.0
21-+17222+18
7 w/ final distances
17->15.21-x19
-0.0
-4.5
11.1
1.7
3.1
0.0
w/ all distances
18-+15,22-19
0.0
11.7
8.4
-2.0
1.4
0.3
A position aware
17-45,18-66
1.7
0.0
0.8
over distance assigning
21-45,22-46
setting, settings of using explicit distance assigningare considered separately. The implicit encoding strategy, while has the capability of learning distances, due to the hardness learning, assigning distance information explicitly would still be helpful. We note the improvement of explicit distance assigning over A d-position-awe aware GIRs table / 7-8. And the results show that the strategies for A-position-aware GIR would still be helpful with distance assigned (Table 9).
13

---

Under review as a conference paper at ICLR 2022
For the choice of aggregator, we take max-pooling the default following starting point of mimicking Bellman-Fool Ford algorithm, and the experiments on synthetic datasets support this, but it is not absolute for real-world cases the information need may not clear. Results show that the mean aggregator (Table 6 1,,2,16,00 gets improvement on those {A] jo--position-aware models aapNN+anchor labeling and GIR), and for A-position-aware models with anchor IDD labeling, the need for more accurate distance information suggests the max-pooling aggregator.
The node one-hot labeling (Table 23-24) provide a Y-position-aware capability MPNN, besides the efficiency issue, results show a performance decline compared with using anchor ID labeling, this demonstrates the effectiveness of the important node selection strategy. Moreover, the GIR propagation with node one-hot labeling combine the merits of both, and gets a relatively promising result.
For GIR-MIX (Table 6 25), with A-p A--psstiio-awaree performs only superior to (A) -eep-potiion-awaal models, and largely inferior models with anchor ID labeling, we ascribe the extremely limited propagation path, though effective in the synthetic datasets, GIR-MIX for every single nodes may not be an effective general graph encoder.
14


Reviews:
[{"review_id": "ci79E39KNj", "reviewer": "Reviewer_YkUE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strengths:\n\n1. The idea of mimicking Bellman-Ford algorithm sounds interesting and novel to the reviewer.\n\nWeaknesses:\n\n1. The presentation of the paper could be improved. The notation is a bit overwhelming, especially in Sec 3.3.  What's the difference of $\\mathbb{B}$ and $\\mathbb{N}$? What does $\\mathbf{f}_{\\mathbb{N}} (z) = f(z, N)$ mean? In addition, I suggest the authors to try to avoid using too many abbreviations in the experiment section as it's really hard to follow, e.g, Table 2, 4 (dist-u,a,au, -AA -A -M -O, etc.). Even the algorithm detail is not super clear to me. What does line 6 mean?\n\n2. The experiments between MPNN and GIR in Table 2 is not consistent. I'm wondering why. It occurs to me that GIR has no significant benefts over MPNN.\n\n3. The empirical study seems not sufficient. There's no large-scale experiments. \n\nQuestions:\n\n1. Though the selection of anchors seem deterministic. I'm wondering what's the variance of selecting different anchors? Or what's the selecting of selecting 1 more or 1 less achors?\n\nPost rebuttal\n\nI thank the authors for the updates. The notation system looks better in the revised version, though I believe it is possible to deliver this paper in a clearer way. As for the empirical performance, I'm not convinced by the authors that MPNN-A is also a GIR framework (it's basically adding one hot labels to label nodes). Summarizing above, I believe this submission could be more impactful after careful revising. I will retain my original rating as borderline reject. ", "summary_of_the_paper": "This paper proposes the Graph Inference Representation (GIR) model, which first applies an anchor indication strategy and a forward process that mimics Bellman-Ford algorithm. The authors theoretically show that the proposed pipeline should be able to capture positional embeddings implicitly, and empirically show that the proposed pipeline can achieve superior performance on simulated and real-world datasets.", "summary_of_the_review": "interesting idea, but the presentation is hard to follow and the empirical results do not seem very significant", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Upbya72-K8", "reviewer": "Reviewer_Z48B", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "As the authors mentioned, the MPNN framework has inherent limitations, especially in position-aware embeddings.\n\nSo this work can bring some value to the GNNs community.\n\nI have a question about GIR framework.\n\nIn Anchor Selection, it is determined in a heuristic way, degree centrality. \n\nBecause anchors are important components in the GIR framework, I believe there should be various attempts to choose the measure of importance for anchors.\n\nIn addition to degree centrality, Eigenvector Centrality, Katz Centrality, PageRank, Betweenness Centrality, Closeness Centrality, Harmony Centrality, and Clustering coefficient can be candidates for anchor selection. \n\nEven some might be suited for effective coverage. \n\nOr, additional trainable neural networks can be used. Could you explain how did you choose the measure and provide evidence as well?", "summary_of_the_paper": "In this paper, the authors propose the anchor-based framework for position encoding. \n\nIt is well known that the message-passing framework inherently has a limitation to encode graph structure and sometimes fails to discriminate isomorphic subgraphs.\n\nGraph Inference Representation exploits the distance relaxation process of the Bellman-Ford shortest path algorithm.\n\nThe authors show that the MPNN framework can keep track of the shortest paths using anchors.\n\nTo this end, the authors introduce the anchor labeling strategy for MPNNs mimicking the Bellman-Ford algorithm.\n\nIt has a more specialized structure and outperforms baseline models.", "summary_of_the_review": "I would recommend this paper be accepted if other issues do not arise.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IeC4uNsjmYr", "reviewer": "Reviewer_C6uM", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Pros:**\n\n- The idea of capturing positional information in the node embedding in an implicit way by constraining the propagation path in a way similar to BFS is interesting and could lead to powerful results.\n- I appreciate the formalisation of positional-aware embeddings and the alignment between the proposed method and the BFS algorithm.\n\n**Cons:**\n\n- While the empirical results show some improvements in certain scenarios, it is not clear from the paper why or when the implicit positional encoding is superior to explicitly encoding of the shortest path. When the interactions between intermediate positional encoding (mentioned in the abstract) are useful, and why is it better to learn them instead of specifying them for each layer? A clear discussion in this regard would be useful to emphasize and clarify the theoretical contribution of this paper.\n- Even if I find this idea as having big potential, I found the paper very hard to follow. The distinction between A-position-aware and {A}-position-aware is not clearly explained in the text even if it is a central element in the paper, as most of the experimental section refer to these two setups.\n- The experiments presented in Table 5 are not enough explained in the text. What is the intuition for the difference in performance between GIR, GIR-A, GIR-O, and why is the ranking different from one dataset to another. What additional information brings each one of them? Moreover, I found the way the experiments are presented (too many abbreviations) difficult to follow.\n- As the authors mentioned, the number of anchors and the way you pick them to influence the amount of structure captured by the algorithm, ranging from complete lack of structure to a normal message passing algorithm. Very few anchors or a bad way to choose them could lead to a great loss of information in terms of structure, eventually leading to poor results. An ablation study on how the results changed depending on this choice, or at least some intuition on what properties the SelectAnchor method should fulfil, would be useful.\n\nMinors: The definitions for the concepts introduced are confusing, and some notations are not consistent along the paper. N is well-known for the set of natural numbers, so I recommend picking a different letter in definition 2. On page 7, there is a typo: I think it should be PGNN-F instead of PGNN-E; On page 7, Datasets paragraph, it should be Definition 1 instead of Definition 2; Same on the last paragraph before section 3.4; Multiple inconsistent usages of normal vs mathbb letters to denote sets (e.g. in Definition 2).", "summary_of_the_paper": "The paper proposes a GNN method (GIR) that incorporates the paths produced by the BFS algorithm in the message passing algorithm, such that it enables the method to mimic the shortest path algorithm. This way, the method is able to learn positional embeddings implicitly. The experiments are conducted both on synthetic and real-world datasets.", "summary_of_the_review": "Overall, I agree that the method could be useful and could improve the GNN methods in situations when the positional encoding is important. However, the current form of the paper lack clarity and I consider that many aspects of the method/experiments should be better present in order to be clearly delivered to the community.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EIWJkjD72Y5", "reviewer": "Reviewer_jwSq", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strength:\nThis paper explores how to implicit learn graph position embeddings with anchor indication, and then propose a new strategy for message propagation under MPNN, which is clearly distinguished from other position-aware GNNs.\n\nWeaknesses:\n\n• The proposed framework (GIR) has limited theoretical contributions and  application scenarios, i.e., incapable of inductive settings, only tested on small-scale dataset. The empirical results lack the support for the key claim that the combined procedure of distance computing and encoding is more beneficial than the separated two-stage way.\n\n• The authors only differentiate GIR with other position-aware GNNs, but do not present the connection and difference between previous works [1] (first propose max-pooling of MPNN to mimic Bellman-Ford Alg).\n\n• The authors do not include the complexity discussion of the proposed method, especially regarding the part of labelling indication and \nmodified message passing and the cost comparison between implicit and explicit encodings. The introduction of relaxation process also raises the concern for the proposed method working on large-scale datasets. \n\n• The notation system used in this paper appears to be very confusing. Several symbols are not properly defined, such as $f_p$, $g_a$ in Def 1. \n\n[1] Veličković, Petar, et al. \"Neural execution of graph algorithms.\" arXiv preprint\narXiv:1910.10593 (2019).\n\n\nTypos:\nIn Def 1, $\\mathbb{N} \\in \\mathbb{B}$ should be $\\mathbb{N} \\subset \\mathbb{B}$?\nIn Def 2, $f_{\\mathbb{N}}(z) = f(z, N)$ should be $f_{\\mathbb{N}}(z) = f(z, \\mathbb{N})$?\nReference for position-aware embeddings should be Def 1 instead of Def 2?", "summary_of_the_paper": "This paper proposes a new type of anchor-based GNN by implicitly exploiting node positioning within customized message passing steps of MPNN. The framework consists of an anchor labeling strategy and a specified propagation path with the utilization of Bellman-Ford algorithm, to enable its positional awareness. The empirical results on small synthetic and real datasets show the effectiveness of implicit positional encoding, and achieve comparable results against other anchor-based models.", "summary_of_the_review": "This paper presents an implicit way to learn graph positional embedding. However, the manuscript is not yet ready to be published. It does not provide a clear empirical investigation or a solid theoretical examination for how the implicit positional encoding is better than the explicit way. The content, organization and experiments also need to be further polished and enhanced.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to encode positions of nodes in graphs by anchor-based GNN with customized message passing steps. All reviewers raised significant concerns on this paper, including novelty of the message passing steps, experiments, writing and clarity, etc. The authors have actively responded to reviewer comments, but many of the concerns are still not addressed. Thus, the paper needs some work in order to be competitive.
Decision: Reject