背景ナレッジグラフシステムの構築には、エンジニアリングとアルゴリズムの緊密な連携が不可欠です。エンジニアリングレベルでは、Ant Groupは昨年、OpenKGオープンナレッジグラフコミュニティと共同で、産業グレードのナレッジグラフセマンティクス標準であるOpenSPGをオープンソース化しました。アルゴリズムレベルでは、Ant Groupは知識融合、知識推論、グラフ応用といった分野において、継続的に進歩を続けています。 OpenSPG GitHub、お気軽にスターを付けたりフォローしてください! https://github.com/OpenSPG/openspg この記事では、ナレッジグラフで一般的に用いられる推論アルゴリズムの概要を説明し、各アルゴリズムの違い、関連性、適用範囲、長所と短所について考察します。ナレッジグラフの計算・推論能力を構築するための思考プロセスを明確にし、ナレッジグラフ推論アルゴリズムを理解したい、あるいは実際に活用する必要がある学生に概要とガイダンスを提供することを目的としています。 ナレッジグラフ推論アルゴリズムのレビュー第1部「距離ベース翻訳モデル」と「グラフ伝播モデル」では、これらのアルゴリズムで使用されている詳細なアルゴリズムについて考察しました。第2部では、セマンティックベースのマッチングモデル、すなわちテンソル分解モデルとニューラルネットワークの種類に焦点を当てます。 ナレッジグラフアルゴリズムの概要この章では、一般的に使用されるグラフ推論アルゴリズムの概要を説明します。業界には多くのアルゴリズムが存在するため、1つの記事ですべてを網羅することは困難です。そのため、グラフ推論と関連性の高いアルゴリズムを厳選し、類似のアルゴリズムについても代表的なアルゴリズムを取り上げ、各アルゴリズムの機能を可能な限り網羅的に網羅することを目指しました。
まず、マインドマップを使用してこれらのグラフ推論アルゴリズムを要約します。 記号的推論：論理的規則に基づいた推論
数値推論：知識グラフ埋め込みに基づく推論知識グラフ埋め込み（KEP）は、知識グラフ内のエンティティと関係性を学習し、グラフの元の構造と意味情報を保持しながら低次元ベクトルを取得する手法です。したがって、優れたエンティティベクトルセットは、エンティティ間の関係性を完全に表現できます。ほとんどの機械学習アルゴリズムは低次元ベクトル入力を容易に処理できるため、リンク予測、分類、属性値計算、類似度計算など、最も一般的なタスクに適用できます。これには、距離ベースの翻訳モデル、グラフ伝播ベースのモデル、意味ベースのマッチングモデルが含まれます。本稿では、意味ベースのマッチングモデルに焦点を当てます。 意味ベースのマッチングモデル これらのモデルは、類似度に基づくスコアリング関数を用いてトリプルの確率を評価し、エンティティと関係を潜在的意味空間にマッピングすることで類似度を測定します。これらの手法は2つのカテゴリーに分類されます。1つはRESCALテンソル分解モデルやその派生モデルなどの単純なマッチングモデル、もう1つはSME（構造化エミュレータ）、NTN（ニューラルテンソルネットワーク）、MLP（平均水準プログラミング）、NAM（ニューラルアンプリファイア）などのディープニューラルネットワークです。 詳細なアルゴリズム分析意味ベースのマッチングモデル - テンソル分解モデル再スケールTransシリーズのアルゴリズムは、ヘッドノードへの関係の影響を表現するために加算を使用していますが、RESCAL [14]は、回転と伸縮を使用してヘッドノードへの関係の影響を表現しています。回転と伸縮の操作は、数学的に行列Mrに掛けられます。RESCALテンソル分解アルゴリズムは、知識グラフ全体を大きなテンソルとして扱い、テンソル分解技術によってそれを複数の小さなテンソル片に分解します。つまり、高次元の知識グラフに対して次元削減処理を実行し、計算中にデータ規模を大幅に削減します。テンソル構築の基本的な方法は、エンティティiとエンティティjに関係kがある場合、そうでない場合は0であるというものです。 その目的関数は次のようになります（ベクトルの内積の一種）。 分散マルチDistMult [15]は、行列Mrの代わりに対角行列diag(r)を用いてRESCALのパラメータ空間を縮小する。これはTransHとTransEの関係に似ている。その目的関数は以下の通りである。 対角行列 diag(r) が使用され、h と t は交換後に等しくなるため (下の式を参照)、DistMult は「A - クラスメート - B」などの対称関係のみを処理でき、「A - 父親 - B」などの非対称関係は処理できないことに注意することが重要です。 穴HolE [16]は、RESCALのパラメータ空間を削減しながら非対称関係を扱うために開発された。この手法は、まず高速フーリエ変換を用いてヘッドベクトルとテールベクトルをiビットずつシフトし、その後内積演算を行う。ヘッドベクトルとテールベクトルのシフトビット数が異なるため、対称性が破れ、非対称関係を扱うことができる。その目的関数は以下の通りである。 複雑なComplEx [17]と HolE は、RESCAL のパラメータ空間を縮小しつつ、非対称関係を扱えるようにするという共通の目標を共有しています。ComplEx は複素アプローチを採用し、実部と虚部の両方を含むように拡張することで自由度を高め、非対称関係を解くことができます。その目的関数は以下のとおりです。 類推ANALOGY [18]は、より良い結果を得るために、DistMult、HolE、ComplExの3種類のモデルを統合しています。 意味ベースのマッチングモデル - ニューラルネットワーク型中小企業SME [19]は、ディープニューラルネットワークを用いてh、r、tをネットワークに入力する2値分類モデルを構築した。まず、隠れ層g_uとg_vはそれぞれhとr、tとrを結合する。次に、出力層でこれら2つの結果の内積を計算し、スコアを求める。知識グラフに(h, r, t)が実際に存在する場合、確率は1に近い値になるはずである。存在しない場合、確率は0に近い値になるはずである。スコアリング関数は以下の通りである。 隠れ層 g <sub>u</sub>と g <sub>v </sub> は、それぞれ h と r、t と r を結合します。2つのバージョンがあり、そのうちの1つは線形バージョンです。 もう 1 つは双線形バージョンです。 NTNNTN [20]は別のタイプのニューラルネットワーク構造である。SMEの平坦化構造とは異なり、NTNはまず隠れ層でhとtを結合し、活性化関数tanhを通過させた後、出力層で関係ベクトルrと結合する。スコアリング関数は以下の通りである。 MLPMLP [21]モデルはより単純である。h、r、tは入力層で結合され、活性化関数tanhを通過して重みM1 、 M2 、 M3を持つ非線形隠れ層を得る。最後に重みwを持つ線形出力層を通過する。スコアリング関数は以下の通りである。 ナムNAM [22]は、まず入力層を通してhとrを結合し、次に多層DNNを隠れ層として使用し、最初の層はz ( )である。 スコアリング関数は次のとおりです。 2種類の損失
ロジスティック損失はRESCALシリーズモデルに適しています。これはClose World仮定に基づいており、観測されていないトリプルは無効とみなされます。正しいトリプルには報酬が与えられ、誤ったトリプルにはペナルティが課されます。
ペアワイズランキング損失は、トランスシリーズモデルに適しています。これはオープンワールド仮定に基づいており、観測されていないトリプルを潜在的に無効とみなします。ファクトトリプルと観測されていないトリプルを可能な限り距離によって分離します。 ここでは、正のトリプレットと負のトリプレットを分離するために使用される一定のマージンが指定されています。は正のサンプルのスコアであり、 は負のサンプルのスコアです。
上記のアルゴリズムはすべてデフォルトでランダムに初期化されます。初期化には柔軟性があり、例えば外部の知識ソースを事前学習に利用することも可能です。 応用
3 つの組み合わせ (h、r、t) のうちの 2 つが与えられた場合、3 つ目を予測します。 評価指標には以下が含まれます。
与えられた 3 つの要素 (h、r、t) が真か偽かを判断します。
ここで使用される手法は、エンティティの分類が「Is A」関係の検出に変換されるというものです。
2 つのエンティティのベクトルが等しい場合、それらは同じエンティティであると判断されます。 Trans、Rescual、SMEシリーズのモデルは、パラメータ数がノード数に比例するため、大規模なグラフ推論には不十分となることがよくあります。この難点を克服するために、グラフニューラルネットワーク（GNN）が導入されました。GNNはその後、包括的なシステムへと進化しており、本稿ではGCN、GAT、Structure2vec、GeniePathなどのアルゴリズムについても後ほど解説します。GNNアルゴリズムはパラメータを共有することでパラメータ空間を削減するため、大規模なグラフ推論に適しています。 文献では上記のアルゴリズムを下の表にまとめており、上記のアルゴリズムのエンティティと関係の埋め込みベクトル、スコアリング関数、制約情報の表現は次のように整理されています。 まとめアルゴリズム分類の観点から 教師なし学習: Deepwalk、Node2Vec、Metapath2vec、LINE、Louvain 教師あり学習: GCN (半教師あり学習)、GraphSAGE、SDNE (半教師あり学習)、GeniePath、GAT、Structure2Vec、HeGNN アプリケーションの観点から リンク予測：すべての埋め込みアルゴリズムはリンク予測をサポートしています。ただし、同種グラフモデルは1種類の関係予測をサポートするのに対し、異種グラフモデルは複数の関係予測をサポートするという違いがあります。（さらに、ALPSプラットフォームにはまだ含まれていませんが、transシリーズもリンク予測を実行できます。） エンティティ正規化（類似度計算）：すべての埋め込みアルゴリズムは類似度計算をサポートしています。類似度は特定のタスク目標によって定義され、損失に反映されます。一般的なタスク目標には、距離類似度（2つのノードが何次接続されているか）、構造類似度、ノードタイプ類似度（ラベル予測）などがあります。 属性値予測（ラベル予測）：GCN、GraphSAGE、GeniePath、GAT、Structure2Vec、HeGNN など。
今後も、SPG および SPG + LLM デュアルドライブ アーキテクチャとそのアプリケーションに関する最新情報を共有していきます。公式サイトをご覧ください: https://spg.openkg.cn/ Github: https://github.com/OpenSPG/openspg |
