技術要約：埋め込みベースのリンク予測における理論的限界について

1. 問題提起

本論文は、現代の知識グラフ埋め込み（KGE）モデルにおける根本的な限界である、線形出力層によって導入されるランク・ボトルネックを取り上げている。標準的なKGEアーキテクチャでは、エンティティとリレーションは低次元の埋め込み（通常 $d \in [10^2, 10^4]$）にマップされ、その後、線形層を介して高次元のエンティティ空間（通常 $|E| \in [10^5, 10^9]$）へと投影される。

著者らは、この線形投影が、モデルの出力を $|E|$ 次元空間内の $d$ 次元の線形部分空間に限定してしまうと主張している。$d \ll |E|$ であるとき、これは「ランク・ボトルネック」を生み出し、モデルの表現力を著しく制限する。具体的には、たとえ上流のニューラルエンコーダ（グラフニューラルネットワークやTransformerなど）がいかに強力であっても、モデルは複雑なダウンストリーム推論タスクに必要な任意のランキング順序、符号パターン（正・負のトリプル）、または確率分布を表現することができない。

2. 手法

理論的分析

著者らは、線形デコーダKGE（LD-KGE）が以下の3つの異なる予測タスクを満たすために必要な埋め込み次元 $d$ の必要条件を導出している：

1. ランキング再構成 (Ranking Reconstruction, RR): クエリに対するオブジェクトの順序を正しく並べる。
2. 符号再構成 (Sign Reconstruction, SR): トリプルを真または偽として正しく分類する。
3. 分布再構成 (Distributional Reconstruction, DR): トリプルに対して較正された確率を割り当てる。

これらのタスクを以下の2つの条件下で分析している：

• 普遍性 (Universality): 与えられたサイズのグラフに対して、考えられるすべてのパターンを表現する能力。論文では、普遍性のための条件として、$d$ は（RRおよびDRに対して）少なくとも $|E|-1$、または（SRに対して）$|E|$ でなければならないことを証明している。これらの境界値は、大規模なグラフにおいては実質的に不可能である。
• 実現可能性 (Realisability): 特定の観測されたグラフと一致するパターンを表現する能力。著者らは、必要な次元が、グラフの隣接行列（またはその符号行列）の符号ランク (sign rank) に依存することを示している。符号ランクは一般にフルランクよりも小さいが、その計算はNP困難である。

実用的な十分条件を提供するために、著者らは符号ランクをグラフの連結性と結びつけている。彼らは、必要な次元が、隣接行列の行における符号変化の最大数によって制限されることを示している。Reverse Cuthill-McKee (RCM) ヘリスティックを用いてエンティティを並べ替えることで、必要な次元が単なるエンティティ総数ではなく、グラフの連結性（具体的には、正の項の連続したブロック数）に応じてスケールすることを示している。しかし、最適な順序付けを行ったとしても、密なグラフは標準的な慣習を遥かに超える次元を必要とする。

提案手法：KGE-MOS

このボトルネックを、$d$ を増大させることによる膨大なパラメータコストを負うことなく打破するために、著者らは KGE-MOS (Knowledge Graph Embedding with Mixture of Softmaxes) を提案している。

• アーキテクチャ: 単一の線形層とそれに続くソフトマックスの代わりに、KGE-MOSは出力層を $K$ 個のソフトマックスの混合体（Mixture of Softmaxes）に置き換える。
• メカニズム: クエリ $(s, r)$ に対して、モデルは $K$ 個の分布の混合を計算する：
  $$P(O|s, r) = \sum_{k=1}^K \pi_k(h_{s,r}) \cdot \text{softmax}(f_k(h_{s,r})E^\top)$$
  ここで、$h_{s,r}$ は隠れ状態、$E$ は共有エンティティ埋め込み行列、$f_k$ はコンポーネント固有の非線形投影（MLP）、$\pi_k$ は混合重みである。
• 効率性: エンティティ埋め込み $E$ はすべてのコンポーネント間で共有される。追加されるパラメータは $f_k$ と $\pi_k$ の重みに限定されるため、そのコストは $O(Kd^2)$ となり、$d$ を増大させた場合の $O(d|E|)$ のコストと比較して無視できるほど小さい。

3. 主な貢献

1. 理論的境界: 本論文は、すべてのLD-KGE（双線形およびニューラル両方）に関する、普遍性と実現可能性に関する最初の必要条件となる境界を提供している。線形出力層が、大規模かつ密なグラフにおいて表現力を根本的に制限することを確立している。
2. 連結性分析: グラフの連結性（符号変化）に基づく実現可能性のための十分な次元を導出し、密なグラフは疎なグラフよりも理論的に適合が困難であることを示している。
3. KGE-MOS: ランク・ボトルネックを効率的に打破する、ドロップイン（そのまま置き換え可能な）非線形出力層を導入している。
4. 実証的検証: KGE-MOSが、大規模かつ密なデータセットにおいて、4つのベースラインモデル（DISTMULT, COMPLEX, RESCAL, CONVE）および1つのニューラルエンコーダ（COMPGCN）に対し、MRR（ランキング精度）とNLL（確率的適合度）の両面で向上することを示している。

4. 実験結果

著者らは、5つのデータセット（FB15k-237, Hetionet, ogbl-biokg, openbiolink, WN18RR）を用いて、4つのベースラインLD-KGEと1つのニューラルエンコーダを用いてKGE-MOSを評価した。

• 大規模/密なグラフにおける性能: 最も大きく、かつ結合密度が高い3つのデータセット（Hetionet, ogbl-biokg, openbiolink）において、KGE-MOSはMRRとNLLの両方でベースラインのLD-KGEを一貫して上回った。この利得は、理論的なボトルネックが最も深刻になる高連結性の領域で最も顕著であった。
• 小規模なグラフにおける性能: より小規模なFB15k-237データセットでは、KGE-MOSの改善は無視できる程度か、あるいはわずかな低下が見られた。これは、より小さく密度の低いグラフではボトルネックがそれほど重要ではないことを裏付けている。
• 次元のスケーリング: 埋め込み次元 $d$ を200から1000に増やすことは、ベースラインの性能を向上させたが、GPUメモリの制約によりバッチサイズを縮小する必要があり、それが最終的に性能を損なった。対照的に、KGE-MOSは $d=200$ において、ベースラインの $d=1000$ に匹敵する性能を、大幅に少ないパラメータ数で達成した。
• アブレーション解析: ソフトマックスのコンポーネント数（$K$）を増やすことは、一貫して性能向上につながった。非線形投影 $f_k$ も利得に寄与したが、混合（mixture）自体がボトルネックを打破する主要な要因であった。
• ランクの打破: 対数確率行列の経験的なランク分析によれば、標準的なモデルはランク $d+1$ に制限されていたのに対し、KGE-MOSはエンティティ集合のフル次元に近いランクを達成しており、事実上ボトルネックを打破していることが示された。

5. 意義と主張

本論文は、リンク予測の分野がエンコーダの改善（GNNやTransformerの使用など）に重点を置く一方で、出力層の限界を軽視してきたと主張している。著者らは、より表現力のある非線形出力層を探求することは、KGEを大規模かつ密なグラフへとスケールさせるための、必要かつ有望な道筋であると述べている。

彼らは、KGE-MOSが低いパラメータコストで性能と確率的忠実度を向上させる「ドロップイン」ソリューションを提供し、「単に埋め込み次元を増やすことが、より大きなグラフを扱う唯一の方法である」という仮定に異を唱えている。この研究は、今後の研究が、エンコーディング中心の改善を超えて、埋め込みベースのモデルにおけるデコーディング・プロセスの構造的な制限に対処すべきであることを示唆している。