Stop Thinking, Just Do!

Sungsoo Kim's Blog

Position-Aware Graph Neural Network using Reachability Estimations

tagsTags

27 June 2022


Article Source


GraphReach; Position-Aware Graph Neural Network using Reachability Estimations

  • This is a recorded presentation of one of the contributed talks at ARCS 2022 with the following details:
  • Title: GraphReach: Position-Aware Graph Neural Network using Reachability Estimations Originally published at: IJCAI 21 Authors: Sunil Nishad, Shubhangi Agarwal, Arnab Bhattacharya and Sayan Ranu

Find out more at the ARCS website: https://event.india.acm.org/ARCS/

Abstract

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 evalu- ation 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.


comments powered by Disqus