Improving Subgraph Extraction for Graph Invariant Learning via Graph Sinkhorn Attention.

Area of Science:

• Artificial Intelligence
• Machine Learning
• Graph Neural Networks

Background:

• Graph invariant learning (GIL) aims to identify stable relationships between graph data and labels despite distribution shifts.
• Existing methods for extracting invariant subgraphs often lack precise control over compactness or use non-differentiable selection methods, limiting their effectiveness.

Purpose of the Study:

• To address the limitations of current invariant subgraph extraction techniques.
• To propose a novel, fully differentiable mechanism for extracting sparse yet soft attention weights in graphs.

Main Methods:

• Developed Graph Sinkhorn Attention (GSINA), a novel mechanism based on optimal transport and Sinkhorn iterations.
• GSINA incorporates principles of separability, softness, and differentiability for robust subgraph extraction.
• Utilized Gumbel reparameterization for stable end-to-end training and theoretically analyzed convergence behavior.

Main Results:

• GSINA demonstrates superior performance in improving out-of-distribution generalization compared to existing approaches.
• Empirical results on synthetic and real-world datasets validate the effectiveness of the proposed method.
• The method provides explicit controls for separability and softness in subgraph identification.

Conclusions:

• GSINA offers a principled and effective approach to invariant subgraph extraction for graph invariant learning.
• The proposed method enhances generalization capabilities of graph models under distribution shifts.
• GSINA represents a significant advancement in differentiable graph attention mechanisms.