Position-Sensing Graph Neural Networks: Proactively Learning Nodes Relative Positions.

Area of Science:

• Artificial Intelligence
• Machine Learning
• Graph Neural Networks

Background:

• Graph Neural Networks (GNNs) commonly use message passing but lack inherent understanding of relative node positions.
• Existing position-aware GNNs (P-GNNs) use fixed anchors, which can compromise both positional awareness and feature extraction capabilities.
• Optimal anchor selection for comprehensive graph embedding is an NP-complete problem, hindering deterministic algorithmic solutions.

Purpose of the Study:

• To develop a novel Graph Neural Network (GNN) architecture capable of learning relative node positions within graphs.
• To address the limitations of arbitrary anchor selection in existing position-aware GNNs (P-GNNs).
• To propose an efficient and scalable method for enhancing GNNs' positional awareness without succumbing to NP-completeness challenges.

Main Methods:

• Introduced Position-Sensing GNNs (PSGNNs) that learn anchor selection through a backpropagatable approach.
• Demonstrated the importance of evenly distributed and asymmetric anchors for effective position awareness.
• Validated the proposed method against state-of-the-art GNNs on diverse synthetic and real-world graph datasets.

Main Results:

• PSGNNs significantly improve performance in pairwise node classification and link prediction tasks compared to existing methods.
• Achieved an average Area Under the Curve (AUC) boost of over 14% for pairwise node classification.
• Demonstrated an average AUC improvement of over 18% for link prediction, showcasing substantial gains.
• Exhibited stable scalability across various graph datasets.

Conclusions:

• PSGNNs effectively learn relative node positions by adaptively selecting anchors in a backpropagatable manner.
• The proposed method overcomes the NP-completeness issue associated with optimal anchor selection.
• PSGNNs offer a promising advancement in GNNs, enhancing their ability to capture complex graph structures and relationships.