Year: 2021

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 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 potentially useful interaction between intermediate results of the distance computing and encoding stages to some extent, due to the model architecture designs. 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.

heading: 1 INTRODUCTION
text: 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 on 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 a 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 1-Weisfeiler-Lehman test (Xu et al., 2019), and lack of ability to capture the position information within the graph (You et al., 2019), without distinguishable node/edge attributes, nodes in a different part of the graph with topologically equivalent neighborhood structures or even with different substructures may be embedded into the identical representation by typical MPNNs alone (You et al., 2019; Li et al., 2020), as shown in figure 1 (b), A1 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 encodings 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 1 (c)). Distance encoding (Li et al., 2020) utilizes distance information to push typical MPNNs beyond the 1-Weisfeiler-Lehman test limitation (Figure 1 d).
Those existing position-aware GNN methods mainly explicitly pre-compute the distance between node pairs, utilizing them as node attributes or controlling of message passing steps, and then perform 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 a relatively separate manner, potentially useful interaction 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 at performing a more flexible interaction with graph structure, positioning and attribute information. With limited fixed anchor positioning 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, in order to retain the potential possibility for more flexible usage of the graph data, as 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 relaxation process of the Bellman-Ford shortest path algorithm (Bellman, 1958), we show that with a 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), we propose a 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 to 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 to help break the structural symmetry as the previous anchor-based GNNs could (Figure 1 (b&e)).
Our contributions are summarized as follows:
1. We propose a general anchor labeling strategy, enabling MPNNs for mimicking the Bellman-Ford algorithm and getting position-aware embeddings implicitly under anchorbased GNN pattern and discuss theoretical implications and experimental realizations.
2. We propose the Graph Inference Representation (GIR) model that contains more specialized structure for learning position-aware embeddings.
3. Empirically, we evaluate the performance of proposed methods for tasks in position-aware datasets, experimental results show that our position-aware GIRs achieve generally higher performance.
The rest of the paper is organized as follows. Section 2 reviews related works. Section 3 introduces notations and definitions, theoretical implications are discussed. Section 4 details the proposed GIR framework. Section 5 presents the experiment and gives a discussion of the results. Finally, section 6 presents our conclusion.

heading: 2 RELATED WORKS
text: Our work follows the anchor-based GNN pattern from the position-aware GNN literature, with the design inspired by the Bellman-Ford algorithm.

heading: 2.1 POSITION-AWARE GNNS
text: 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 preassigned graph distance from the propagation target to each node (Figure 1, (d)). For each message propagation step on a target node v, only distance from v are utilized, potentially useful distance from other nodes are not considered.
Anchor-based GNNs use selected anchor nodes as a positioning base, existing methods mainly follow 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 to get a 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 et al., 2019) pre-selects fixed anchors by minimum point cover nodes algorithm; 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 1). 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.

heading: 2.2 BELLMAN-FORD ALGORITHM
text: The Bellman-Ford algorithm (Bellman, 1958) computes the shortest path distance from a single source node to each node in a weighted digraph. For a graph G = (V, E), source node s, the algorithm performs |V| − 1 relaxation iterations, maintaining the shortest path from s 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,
distiv = min(dist i−1 v , dist i−1 u + w) i > 0 (1)
where dist0 is initialized as,
dist0v = { 0 v = s ∞ otherwise (2)
A variant of Bellman-Ford algorithm (Moore, 1959) notices that if the distance value of node v has not been changed since its last relaxed, edges out of v 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.

heading: 3 PRELIMINARIES

heading: 3.1 NOTATIONS
text: A graph can be represented as G = (V, E), where V = {v1, · · · , vn} is the node set and E = {〈vi, vj〉|vi, vj ∈ V} is the edge set. Nodes are augmented with the feature matrix X , which is either input attributes if available or placeholders. Edges may augmented with the optional weights W . In-neighborhoods of node v are represented as N (v). Notations are summarized in table 1.

heading: 3.2 POSITION-AWARE EMBEDDINGS
text: 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 (You et al., 2019) view embeddings as position-aware if the shortest path distance between node pairs could be reconstructed from their embeddings, which is hard for models with fixed anchors to satisfy. Here we define position-aware embeddings related to anchors (Definition 1). Considering that the shorest path distance to a node set has different definitions, such as the shorest path distance to all anchor nodes or to any node in the anchor node set, or whether to focus on shorest path with limited hop. Here in the definition 1, we focus on the limited hop shorest path distance (for the alignment with MPNN) to any node in specific node sets, for retaining a high generality, and the union of those node sets need to be the anchor node set, for consisting with the position-aware embeddings related to anchors definition.
Definition 1 (Position-aware Embeddings). For A ⊆ P(A), ⋃
A = A, where P(A) is the power set of node set A, the node embedding Z = {zi = f(vi)|∀vi ∈ V}, where f is a graph encoder that maps a node to its embedding, is k-hop A -position-aware if there exists functions {gA′(·)|∀A′ ∈ A } such that gA′(zi) = dsp(vi,A′), where dsp(vi,A′) is the k-hop shortest path distance between node vi and any node in the node set A′ in the graph G. If all elements in A are singleton, brakets of sets inner A could be omitted.
As examples for definition 1, we could reconstruct k-hop shorest path distance from any node in the anchor set A from k-hop {A}-position-aware 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.

heading: 3.3 INDICATABILITY
text: Here we discuss the theoretical implicitly of our GIR framework design. We begin with our motivation of mimicking the Bellman-Ford algorithm with MPNNs, the concept of indicatability is introduced as 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-Ford algorithm and getting position-aware embeddings implies the capability for reconstructing k-hop shortest path distance from k-th layer.
To capture this intuition, we 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′ ⊆ A, the function set f is A′-indicatable over function f if there exists a constructable function fA′ such that for all vi ∈ A, fA′(zi) = f(vi,A′).
The indicatability (Definition 2) is defined over a pre-defined function f that maps a node vi 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 zi, the embedding of vi as input and could generate outputs include f(zi,A′), as the target neural network module f is capable for mimicking f over A′, we say that f is A′-indicatable over f . Moreover, the k-hop A -position-aware definition (Definition 1) can be restated as the existence of f-dist with A′-indicatability over k-hop limited multi-souce shorest path distance function, for all A′ ∈ A .

heading: 3.4 NEURAL BELLMAN-FORD WITH MPNNS
text: Here we show that a well-designed and parameterized MPNN is capable for representing the process of updating the existence of an A′-indicatable f-distk−1 for Zk−1 to A′-indicatable f-distk over Zk in the k-th layer, the mentioned corresponding functions are directly implemented or implicitly mimicked by well-learned parameterized multi-layer perceptrons (MLP), 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′-indicatable f-distk−1, which can be written as,
[distk−1A′ ]vi = f-dist k−1 A′ (z k−1 i ) (3)
then, considering the aggregate and update pattern of MPNNs, we expect an MPNN layer performed on node v to mimic a relaxation iteration on v. Deriving from the Bellman-Ford relaxation function (Equation 1), the expected function for an MPNN layer to mimic could be,
[distkA′ ]v = min({min([dist k−1 A′ ]v, [dist k−1 A′ ]u +We=〈u,v〉)|∀u ∈ N (v)}) (4)
or equivalently,
[distkA′ ]v = min([dist k−1 A′ ]v,min({[dist k−1 A′ ]u +We=〈u,v〉|∀u ∈ N (v)})) (5)
where the binary min function is expected to be mimicked by well-learned MLPs 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 {distkA′ |∀A′ ∈ A} as part of output Zk would maintain the existence of A′-indicatable f-distk.
There remains an issue of initialization. For the first layer, there is no natural existence of A′indicatable f-dist0, as in the Bellman-Ford algorithm, the distance value of source nodes is initialized as 0, while others∞. We would expect the updated distance value used in the min functions to be an enough large value, but it is not a natural way to explicitly assign it as node attributes, and we instead adopt a simple anchor indication strategy, or the f-ind with A′-indicatability, where f-indA′(xi) indicates whether the node vi is in A′. And the expected function for the first MPNN layer to mimic, corresponding with equation 4 and 5, would be,
[dist1A′ ]v = min({We=〈u,v〉|u ∈ N (v) ∧ f-indA′(xu)}) (6)

heading: 3.5 PROBLEM DEFINITION
text: The GIR framework is designed for node representation learning tasks, paying special attention to the capacity for getting position-aware embeddings. As a general encode for node representation learning, GIR takes graph G = (V, E) with node attributes X and optional edge weights W as inputs, and embed nodes into d-dimensional vectors, represented as Z ∈ R|V|×d. The node representations are normally used in downstream tasks like node classification and link prediction.

heading: 4 METHODOLOGY
text: Here we proposed the GIR framework, acting as an extension of MPNNs to get position-aware embeddings. The GIR framework is based on the f-ind idea (Section 3.4) and a further specialization on the propagation paths, which we will introduce first, the overall design of the GIR framework will be elaborated then, finally, we take a discussion about using GIR as a general graph encoder.

heading: 4.1 GIR MODEL: MORE SPECIFIC PROPAGATION PATHS
text: Motivated by the relaxation order improved variant of the Bellman-Ford algorithm (Moore, 1959), we 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 a 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 a common workaround is adding a self-loop to the input graph. In 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 a neighborhood). We take zero vector as a message if no in-neighborhood 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 the 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}-indicatability, thus a k-layer GIR with an anchor set A is k-hop {A}-position-aware.

heading: 4.2 THE GIR FRAMEWORK
text: 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 1), building blocks are elaborated as follows.
Anchor Selection (Algorithm 1, 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 al., 2019; Xu et al., 2020). Specifing influential anchor node set is a 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, we adopt degree centrality based GA-MPCA algorithm used in AGNN (Liu et al., 2019) as a default choice. For data or tasks with more heuristic, other choices may be adopted. For example, for web page networks, PageRank (Page et al., 1999) may be a more capable choice, and for networks constructed by snowball sampling (Goodman, 1961), seed nodes may be directly marked as anchor.
Algorithm 1 The GIR framework. Input: Graph G = (V, E); Node input attributes {xv,∀v ∈ V}; Edge weights W (optional) Parameter: Number of layers L; Anchor selection function SelectAnchor; Anchor indicatability mark function IndicatableMark; Message functions M ; Neighborhood aggregator functions AGGR; Node update functions U . Output: A-position-aware embedding {zv,∀v ∈ V}
1: A← SelectAnchor(G) 2: h0v ← [xv||IndicatableMark(v,A)],∀v ∈ V 3: BFS ← A 4: for l← 1 to L do 5: for v in V do 6: src← a node set with lower bound N (v) ∩BFS and upper bound N (v) 7: mv ← AGGRlu∈srcM l(hl−1u , hl−1v ,We=〈u,v〉) 8: hlv ← U l(hl−1v ,mv) 9: end for
10: BFS ← Successors(G, BFS) 11: end for 12: z ← hL 13: return z
Anchor Indication (Algorithm 1, line 2) Assigning extend node attributes for guaranteeing the existence of f-ind with A′-indicatability for all A′ ∈ A for a desired A -position-aware 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 {A}-position-aware capability is expected.
• Anchor Labeling: ({A}-position-aware) 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.
• Anchor ID Labeling: (A-position-aware) Assigning one-hot labeling for anchors as extend attribute and zeros for others. For all anchor node a ∈ A, the existence of f-ind with {a}-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 dimensions. Note that the anchor ID labeling is not capable of inductive settings, for it is sensible to the order of anchor nodes.
Message Propagation (Algorithm 1, line 3–12) For the propagation paths, the GIR model (Section 4.1) gives a limitation for determining neighborhoods in the MPNN message-passing steps (tracked as BFS in algorithm 1), and we take this limitation as lower bound in the whole framework. The message functions M are preferred to be a parameterized encoder over node representations and optional edge weight, and the update functions M are preferred to be a parameterized encoder over node message and representations, we commonly choose MLP as the parameterized encoders. Max-pooling is the most preferred choice for the aggregator AGGR.

heading: 4.3 GIR AS GENERAL GRAPH ENCODER
text: 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 it to be a 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 outputs (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 A1,A2, · · ·An-positionaware capability would be (∩ni=1Ai)-position-aware. Then for the issue of inductive setting, considering the components of GIR framework, common anchor selection methods with a general strategy are inductive, and the message passing is also inductive. And for the indication labeling strategy, only anchor labeling (which implies {A}-position-aware) is inductive, order aware strategies like
anchor ID labeling will be failed in inductive settings. If more position aware capability needed, particularly, GIR-MIX provide an inductive ability with pairwise tasks, which is same as in PGNN.
The time complexity of our default anchor selecting method is O(|V|2) (Liu et al., 2019), and O(|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 a K layer vanilla MPNN, the time complexity is O(K|E|+K|V|), and for a K layer GIR model, let D represents the maximum of node out-degrees, we take the upper bound with D that leads to O(|A|DK + K|V|), and it is strictly lower than or in the worst case equal to MPNN.

heading: 5 EXPERIMENTS
text: In this section, we first take experiments on a synthetic dataset to validate the effectiveness of the GIR framework for getting position-aware embeddings, then we demonstrate the performance of GIRs on real world datasets used in position-aware GNN literature.
Datasets & Experimental Setup Based on our position-aware definition (Definition 1), we construct four synthetic datasets, with {A}/A-position-aware information need on 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-aware GNN literature (You et al., 2019; Li et 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 to ones as placeholders for a more fair comparison. More details of the datasets and eperimental setup are in Appendix A.1.
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 our proposed models in the GIR framework. We take PGNN, AGNN and Distance Encoding (DE) as position aware GNN baselines, among those, PGNN and AGNN are anchor based methods, and the AGNN with fixed anchor is most related to our experiment setting. We take experiments for the GIR framework variants over: (1) MPNN or GIR message passing; (2) anchor labeling ({A}-position-aware) or anchor ID labeling (A-position-aware) anchorindication strategies; (3) max-pooling and mean aggregator; (4) GIR-MIX over all anchor node (A-position-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, we report the mean absolute error (MAE) for mean outputs of every layer (mean) and on the last layer (last) in table 2. Considering that the average 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 are generally inferior to the corresponding max-pooling models, which supports max-pooling to be a preferred aggregator. Variants using GIR propagation get outperformed results in A-positionaware datasets but inferior in {A}-position-aware datasets. We owe the outperformed results to the
more specific propagation paths in GIR models, thus more easily to learn the expected functions in the relatively complicated cases, while in the {A}-position-aware datasets, both {A}-position-aware models archives nearly perfect results, and the higher capacity of MPNN leads to a slight superiority.
Results of experiments on real-world datasets are reported in table 3, 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 distinguish 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-aware, as 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 assigning, with {A}-position-aware modeling ability, MPNNs with anchor labeling and vanilla GIRs generally get higher results, yet inferior to models with more powerful position-aware 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 effectiveness 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 assigning intermediate distance on other datasets to the information redundant. Moreover, we note that GIR framework performs inferior on 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-aware methods with special propagation strategy get relatively higher results.

heading: 6 CONCLUSION AND FUTURE WORK
text: 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 strategies, and considerations for more general usages of GIR framework are discussed. Our empirical evaluations are taken on the synthetic datasets and relatively small scale real-world position-aware datasets used in the previous position-aware GNN literature, we leave the potential usage of GIR on larger scale scenarios for future work.

heading: A EXPERIMENT DETAILS
text: A.1 DATASETS & EXPERIMENTAL SETUP
We first detail the construction of synthetic datasets. For {A}-position-aware 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-position-aware 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 as a uniformly sampled integer from 2 to 10, and in the unweighted setting, the distance between every connected node pair would be 1. 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 5.
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 on 5 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 PyTorch (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 1e-3 and 1e-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 table 5.
A.3 MORE RESULTS AND ANALYSIS
We note the full experiment results of real-world datasets (Table 6) and take some complementary analysis here.
We first note some key aspects for highlighting the improvements of GIR framework in table 7. We note the improvement of using explicit distance assigning on MPNN in (Table 7, 1-2), which highlights the effectiveness of distance information. Table 7, 3-4 lists the improvements of the GIR framework with different position-aware settings, settings with explicit distance assigning are not considered here for more clear comparison. The improvements of GIR propagation strategy are highlighted in table 7, 5-6, the comparisons are taken on MPNN with same position-aware
setting, settings of using explicit distance assigningare considered separately. The implicit encoding strategy, while has the capability of learning distances, due to the hardness of learning, assigning distance information explicitly would still be helpful. We note the improvement of explicit distance assigning over A-position-aware GIRs in table 7, 7-8. And the results show that the strategies for A-position-aware GIR would still be helpful with distance assigned (Table 7, 9).
For the choice of aggregator, we take max-pooling as the default following our starting point of mimicking Bellman-Ford algorithm, and the experiments on synthetic datasets support this, but it is not absolute for real-world cases as the information need may not clear. Results show that the mean aggregator (Table 6, 8,12,16,20) gets improvement on those {A}-position-aware models (MPNN+anchor labeling and GIR), and for A-position-aware models with anchor ID labeling, the need for more accurate distance information suggests the max-pooling aggregator.
The node one-hot labeling (Table 6, 23-24) provide a V-position-aware capability to 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-position-aware, performs only superior to {A}-position-aware models, and largely inferior to models with anchor ID labeling, we ascribe it to 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.

Review summaries:
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.

In this paper, the authors propose the anchor-based framework for position encoding.   It is well known that the message-passing framework inherently has a limitation to encode graph structure and sometimes fails to discriminate isomorphic subgraphs.  Graph Inference Representation exploits the distance relaxation process of the Bellman-Ford shortest path algorithm.  The authors show that the MPNN framework can keep track of the shortest paths using anchors.  To this end, the authors introduce the anchor labeling strategy for MPNNs mimicking the Bellman-Ford algorithm.  It has a more specialized structure and outperforms baseline models.

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.