関係を信頼すべきはいつか？多関係グラフ学習における操作コスト・露出・信頼の罠

- 多関係グラフ学習における関係の信頼性を問う研究 - 敵対者が各関係・各行動の操作に異なるコストを払う状況を想定 - コストを与件として、ある関係を使うことが無視するより悪くなる条件を理論的に特徴づける - 主な貢献は2つの理論結果 - degree gating が関係の選択・再重み付けより厳密に優れる条件とその sharp 性 - per-node exposure bound による関係の harden 優先度付け - 線形関係モデル・R-GCN・tree ensembles 向けの解析ツールと選択プロトコルも提示

- 従来の multi-relational graph detector は clean data から各関係の信頼度を学習 - 敵対コストの非対称性を考慮しない - 本研究は操作コストを明示的に取り込み、関係使用が無視より悪化する条件を証明 - degree gating が任意の選択・再重み付けを厳密に上回る条件を示し、その window が sharp であることを証明 - exposure per unit cost が、攻撃情報なしで harden すべき関係を高精度に選べることを示す(16中15) - 比較対象の informativeness・cheapness・等コスト解析は最大7にとどまる

- 操作コストを所与とした理論解析 - degree gating と関係選択・再重み付けの比較定理 - 一部集団が関係上で孤立し、攻撃者が gate を開くコストを払えない場合の優越性と sharp 性 - per-node exposure bound を提案し、message passing へ拡張 - 攻撃なしで計算した exposure per unit cost で harden 対象を選定 - 解析ツール - 線形関係モデルの exact worst case - R-GCN と tree ensembles の certified brackets - adversarial validation の finite-sample guarantee - 結果に基づく選択プロトコルを構築

- 実グラフ上で validated gating の利得が条件を満たす関係にのみ現れることを確認 - exposure per unit cost が harden により trap threshold を最も上げる関係を16中15で選択 - 比較手法は最大7 - 6グラフ・90設定で、clean-trained graph detector が graph-free counterpart を下回ることを確認(58/90) - 選択プロトコルは graph 無視より有意に悪化しないことを検証 - 関係が最大4では主に abstain - 関係が多い場合の cost-aware proposals は合成グラフで有効性を確認

- コスト情報がない場合の安全な選択は abstain であると結論 - 関係が少ない場合、選択プロトコルは validation のみと同様に主に abstain する - cost-aware proposals の有効性は現時点では合成グラフでのみ示されており、実グラフでの検証は今後の課題 - 理論結果の sharp 性や finite-sample guarantee の実用上の tightness については要旨からは不明

- R-GCN に関する研究 - tree ensembles に関する研究 - multi-relational graph 上の adversarial attack / defense 研究 - graph neural network の certified robustness 研究 - adversarial validation に関する研究