Learning feature space node embeddings that encode the position of a node within the context of a graph is useful in several graph prediction tasks. Majority of the existing graph neural networks (GNN) learn node embeddings that encode their local neighborhoods but not their positions. Consequently, two nodes that are vastly distant but located in similar local neighborhoods would map to similar embeddings  . This limitation may prevent accurate performance in predictive tasks that rely on position information. In this paper,we address this gap by developing GraphReach, a position-aware , inductive GNN . GraphReach captures the global positions of nodes though reachability estimations with respect to a set of nodes called anchors. The reachability estimations compute the frequency with which a node may visit an anchor through any possible path. The anchors are strategically selected so that the reachability estimations across all  nodes are maximized. We show that this combinatorial anchor selection problem is NP-hard and  consequently, develop a greedy (1-1/e) approximation . An extensive experimental evaluation covering six datasets and five state-of-the-art GNN architectures reveal that GraphReach is consistently superior and provides up to 40\% relative improvement in the predictive tasks of link prediction and pairwise node classification . In addition, GraphReach is more robust against adversarial attacks.
 Majority of the existing graph neural networks (GNN) learn node embeddings that encode their local neighborhoods but not their positions. Consequently, two nodes that are vastly distant but located in similar local neighborhoods map to similar embeddings in those networks . This limitation prevents accurate performance in predictive tasks that rely on position information. In this paper,we develop GraphReach, a position-aware inductive GNN that captures the global positions of nodes through reachability estimations with respect to a set of anchor nodes. The anchors are strategically selected so that reachability estimations across all the nodes are maximized. We show that this combinatorial anchor selection problem is NP-hard and , consequently, develop a greedy (1-1/e) approximation heuristic. Empirical evaluation against state-of-the-art GNN architectures reveal that GraphReach provides up to 40\% relative improvement in accuracy . In addition, it is more robust to adversarial attacks.
D
Learning feature space node embeddings that encode the position of a node within the context of a graph is useful in several graph prediction tasks.
D
would
A
in those networks
R
may prevent
prevents
R
address this gap by developing
develop
R
, inductive GNN . GraphReach
inductive GNN that
R
though
through
R
nodes called anchors. The reachability estimations compute the frequency with which a node may visit an anchor through any possible path. The
anchor nodes. The
D
the
A
the
A
,
R
. An extensive experimental evaluation covering six datasets and five
heuristic. Empirical evaluation against
D
is consistently superior and
R
the predictive tasks of link prediction and pairwise node classification
accuracy
R
GraphReach
it
R
against
to