Position-Sensing Graph Neural Networks: Proactively Learning Nodes Relative Positions
Most existing graph neural networks (GNNs) learn node embeddings using the framework of message passing and aggregation. Such GNNs are incapable of learning relative positions between graph nodes within a graph. To empower GNNs with the awareness of node positions, some nodes are set as anchors. Then, using the distances from a node to the anchors, GNNs can infer relative positions between nodes. However, P-GNNs arbitrarily select anchors, leading to compromising position-awareness and feature extraction. To eliminate this compromise, we demonstrate that selecting evenly distributed and asymmetric anchors is essential. On the other hand, we show that choosing anchors that can aggregate embeddings of all the nodes within a graph is NP-hard. Therefore, devising efficient optimal algorithms in a deterministic approach is practically not feasible. To ensure position-awareness and bypass NP-completeness, we propose Position-Sensing Graph Neural Networks (PSGNNs), learning how to choose anchors in a back-propagatable fashion. Experiments verify the effectiveness of PSGNNs against state-of-the-art GNNs, substantially improving performance on various synthetic and real-world graph datasets while enjoying stable scalability. Specifically, PSGNNs on average boost AUC more than 14% for pairwise node classification and 18% for link prediction over the existing state-of-the-art position-aware methods. Our source code is publicly available at: https://github.com/ZhenyueQin/PSGNN
Code (1)
Tasks
Link PredictionNode ClassificationPositionSimilar Papers 제목 키워드 기반
mmSnap: Bayesian One-Shot Fusion in a Self-Calibrated mmWave Radar Network
We present mmSnap, a collaborative RF sensing framework using multiple radar nodes, and demonstrate its feasibility and efficacy using commercially available mmWave MIMO radars. Collaborative fusion requires network cali…
Leveraging commonsense for object localisation in partial scenes
We propose an end-to-end solution to address the problem of object localisation in partial scenes, where we aim to estimate the position of an object in an unknown area given only a partial 3D scan of the scene. We propo…
Graph Neural NetworkObjectPositionPA-GM: Position-Aware Learning of Embedding Networks for Deep Graph Matching
Graph matching can be formalized as a combinatorial optimization problem, where there are corresponding relationships between pairs of nodes that can be represented as edges. This problem becomes challenging when there a…
Combinatorial OptimizationGraph MatchingPositionGRPE: Relative Positional Encoding for Graph Transformer
We propose a novel positional encoding for learning graph on Transformer architecture. Existing approaches either linearize a graph to encode absolute position in the sequence of nodes, or encode relative position with a…
Graph ClassificationGraph RegressionGraph Representation LearningMolecular Property Prediction+2GraphReach: Position-Aware Graph Neural Network using Reachability Estimations
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 neigh…
Graph Neural NetworkLink PredictionNode ClassificationPosition