背景ナレッジグラフシステムの構築には、エンジニアリングとアルゴリズムの緊密な連携が不可欠です。エンジニアリングレベルでは、Ant Groupは昨年、OpenKGオープンナレッジグラフコミュニティと共同で、産業グレードのナレッジグラフセマンティクス標準であるOpenSPGをオープンソース化しました。アルゴリズムレベルでは、Ant Groupは知識融合、知識推論、グラフ応用といった分野において、継続的に進歩を続けています。 🌟OpenSPG GitHub、お気軽にスターを付けてフォローしてください! https://github.com/OpenSPG/openspg この記事では、ナレッジグラフで一般的に用いられる推論アルゴリズムの概要を述べ、それらの相違点、関連性、適用範囲、長所と短所について考察します。ナレッジグラフの計算と推論機能の背景にある考え方を明確にし、ナレッジグラフ推論アルゴリズムを理解したい、あるいは業務で活用する必要がある方々に、概要とガイダンスを提供することを目的としています。本稿はパート1であり、主に「距離ベース翻訳モデル」と「グラフ伝播ベースモデル」の2つのセクションを紹介します。 ナレッジグラフアルゴリズムの概要この章では、一般的に使用されるグラフ推論アルゴリズムの概要を説明します。業界には多くのアルゴリズムが存在するため、1つの記事ですべてを網羅することは困難です。そのため、グラフ推論と関連性の高いアルゴリズムを厳選し、類似のアルゴリズムについても代表的なアルゴリズムを取り上げ、各アルゴリズムの機能を可能な限り網羅的に網羅することを目指しました。
まず、マインドマップを使用してこれらのグラフ推論アルゴリズムを要約します。 01 ：記号的推論：論理的規則に基づく推論
02 : 数値推論：グラフ表現学習に基づく推論ナレッジグラフ埋め込み（KEP）は、ナレッジグラフ内のエンティティと関係性を学習し、グラフの元の構造と意味情報を保持しながら低次元ベクトルを形成する手法です。したがって、優れたエンティティベクトルセットは、エンティティ間の関係性を完全に表現できます。ほとんどの機械学習アルゴリズムは低次元ベクトル入力を容易に処理できるため、リンク予測、分類、属性値計算、類似度計算など、ほとんどの一般的なタスクに適用できます。 距離ベースの翻訳モデル これらのモデルは、距離ベースのスコアリング関数を用いてトリプルの確率を評価し、末尾ノードを先頭ノードと関係変換の結果として扱います。この種の手法の例としては、TransE、TransH、TransRなどが挙げられます。 TransEモデルは、反射的関係／多対1関係／1対多関係を適切にモデル化できません。解決策1：TransHとTransRのように、同じエンティティが異なる関係において異なる表現を持つことを許可します。解決策2：TransM、TransF、ManifoldEのように、エンティティと関係間の置換仮定を緩和します。 意味ベースのマッチングモデル これらのモデルは、類似度に基づくスコアリング関数を用いてトリプルの確率を評価し、エンティティと関係を潜在的意味空間にマッピングすることで類似度を測定します。これらの手法は2つのカテゴリーに分類されます。1つはRESCALテンソル分解モデルやその派生モデルなどの単純なマッチングモデル、もう1つはSME（構造化エミュレータ）、NTN（ニューラルテンソルネットワーク）、MLP（平均水準プログラミング）、NAM（ニューラルアンプリファイア）などのディープニューラルネットワークです。 グラフベースの伝播モデル このタイプのモデルでは、グラフをノードとそれらを接続するエッジとして扱います。情報はグラフに沿って伝播します。これらのモデルは一般的に2つのカテゴリに分類されます。
詳細なアルゴリズム分析01 ：距離ベースの翻訳モデルこれらのモデルは、距離ベースのスコアリング関数を使用してトリプルの確率を評価し、末尾ノードを先頭ノードおよび関係変換の結果として扱います。 トランスETransE [6]は、実体と関係を低次元ベクトルとして表現するシンプルなモデルです。このモデルは、知識グラフのベクトル化表現のデフォルトのベースラインとなり、様々な派生モデルを生み出してきました。TransEは、ヘッドベクトルhと関係ベクトルrの合計とテールベクトルtの間の距離に注目し、これを最適化の目的関数とします。最終的に、各ノードと関係の埋め込みベクトルは学習によって得られます。以下の一連のアルゴリズムの学習プロセスは類似しており、ここでは繰り返しません。 距離スコアの計算式は次のとおりです。 TransEモデルは単純すぎる。任意の2つのベクトルが与えられた場合、3つ目のベクトルは本質的に固定されている。そのため、1-N、N-1、NN問題では、N個の類似した埋め込みベクトルが生成される。さらに、対称的な関係に遭遇するとr=0となるため、これらの問題の処理には理想的とは言えない。その後の研究では、TransEを基盤として、1-N、N-1、NN問題を効果的に解くTransRやTransHなどのモデルが提案された。 トランスRTransR [7]では、各関係rにはマッピング行列Mrがあり、異なる関係が異なるマッピング空間で距離スコアを計算できる。 距離スコアの計算式: トランスHTransH [8]はTransRの考え方を継承していますが、マッピング行列Mrの代わりにマッピング平面（投影面）の法線ベクトルwrを使用することで簡素化されています。これによりパラメータ空間が大幅に削減されます。 これは、TransH が 1-N、N-1、NN 問題や、TransR などの類似のアルゴリズムを解決できる理由を説明しています。TransE の問題は、トリプル内の任意の 2 つのベクトルが固定されると、3 番目のベクトルに自由度がなくなり、空間的に類似した埋め込みベクトルが生成されることにあります。TransH はこの問題を回避します。図に示すように、ヘッド ベクトル h とテール ベクトル t は、特定の関係に対応する投影平面に投影されます。したがって、投影平面の法線 (破線) 上の任意の位置にあるヘッド ベクトルとテール ベクトルは、潜在的にヘッド ベクトル h とテール ベクトル t になる可能性があります (青い矢印で表示)。ここで、h と t には自由度があります。この自由度により、TransH は TransE とは異なり、任意の 2 つのベクトルが与えられたときに 3 番目のベクトルが常に同じ位置を指すとは限らないため、1-N、N-1、NN 問題をより適切に解決できます。TransH、TransR、および TransD モデルはすべて、追加の自由度を追加することでこれを実現できます。 TransH距離スコアの計算式 トランスDTransD [9]はTransHに小さな変更を加え、異なるヘッドベクトルとテールベクトルに独自のマッピング空間を与えました。 距離スコアの計算式: トランスパースTranSparse [10]はTransRに基づいていますが、マッピングマトリックスに異なるデータスパース情報を組み込んでいます。 変換行列は h と t で同じです。 h と t の変換行列は異なります。 距離スコアの計算式: トランスAこれまでのtrans法では、ベクトルの各次元を同等に扱っていましたが、実際には各次元の重要性は異なります。有効な次元は一部だけで、ノイズとみなされ効果を弱める次元もあります。TransA [11]モデルは、重み付け行列を導入することで各次元に重みを割り当てます。空間的な観点から見ると、これは選択空間を円から楕円に変更することと同等です。 TransAは、異なる次元の重みベクトルに行列を導入し、LDL法を用いて分解します。これは対角行列であり、対角要素は異なる次元の重みを表します。この論文のハイライトは、様々な損失指標を画像を用いて説明し、より直感的な理解を可能にしている点です。 トランスA'TransA' [12]は適応マージンを得るための学習が可能です。Transシリーズアルゴリズムの損失は以下のとおりで、これは事実トリプルと負のサンプルトリプルを距離の観点から可能な限り分離することを意味します。 ここで、マージンとは、正のトリプルと負のトリプルを区別するために使用される定数です。マージンが大きいほど、より多くの誤りのあるトリプル（つまり、 f (h,r,t) がf (h',r',t')より大きいトリプル）が損失計算に含まれるようになり、過剰適合につながる可能性があります。逆に、マージンが小さいほど、スコアに近い多くの正のサンプルと負のサンプル（つまり、 f (h,r,t) がf (h',r',t')に近いトリプル）が除外される可能性が高くなり、不足適合につながる可能性があります。 従来のトランスモデルのマージンは固定されていたが、異なるマージンを設定することでモデルの性能を向上させることができるだろうか？TransA' [12]は、マージンをエンティティ部分と関係部分に分割し、線形補間を用いてそれらを結合するというアプローチを提案した。エンティティ部分のマージンは、内側の円により多くの正例（円で表す）が含まれ、外側の円に可能な限り多くの負例（四角で表す）が含まれるようにする必要がある。関係部分については、TransA'は関係の長さ、すなわちL2ノルムを用いて類似関係を測定した。具体的な式を下図に示す。 記事中の実験では、適応マージンを採用すると効果が大幅に向上する（MRが大幅に向上する）ことが示されています。 回転1) 原則 RotatE [13]は実体と関係を複素ベクトル空間に写像し、各関係をヘッド実体からテール実体への回転として定義する。RotatE はオイラーの恒等式 を借用している。関係は回転の度合いを表し、 である。三つ組 (h,r,t) が与えられたとき、 h は r だけ回転した後に t に等しくなることが期待される。ここで h,r,t は C に属する。 、これがアダマール積である場合、複素空間の各次元に対して次の式が成り立ちます。 距離関数は次のとおりです。 2) 複雑な関係性をサポート 本稿では、対称／非対称、反対称、組み合わせといった異なるアルゴリズムの有効性を検証するための別の視点を提示します。これら3種類の関係は以下のように定義されます。
記事では、実験結果に基づいた非常に直感的な説明も提供されています。下図に示すように、対称関係「similar_to」の場合、「RotatE」はほとんどの場合「r」に対応する値を学習しますが、いくつかのケースでは「r」も学習します（「r」が0に近い対称的な結果も学習します。「transE」はこれを目的として特別に設計されています）。 下の図に示すように、反対関係である上位語と下位語の積は、整数倍に相当します。 for2-1 & winner & for1 の組み合わせ関係については、h と r を結合して t を引くと、自然に整数倍になります。 他にもよくある状況がいろんなところに散在しています。 この記事の付録では、RotatE が単純な回転操作によって、上記のすべてのリレーショナルスキーマを効果的にモデル化できることを示しています。また、以下の表に示すように、いくつかの一般的なアルゴリズムで使用されるスキーマも一覧表示しています。 ご覧のとおり、RotatEはこれらのアルゴリズムのすべてのパターンを満たすモデルです。TransXは、transHやtransRのように、先頭ベクトルと末尾ベクトルをマッピングしてから距離を計算するモデルのクラスを表します。記事内の表には誤りがあります。transXは逆の関係も満たすことができるためです。TransHを例にとると、TransEは逆の関係と組み合わせの関係を満たしており、投影後のtransHはTransEと同じであるため、逆の関係も満たします。 RotatE が対称関係と非対称関係の両方を満たすことができるのはなぜでしょうか？回転は周期的であり、対称関係は2つの回転操作を重ね合わせて原点に戻った結果と等価だからです。1回の回転操作が周期の半分である場合、この条件は満たされます。さらに、1回の回転が周期の半分または周期の倍数に等しくない場合は、非対称関係に相当します。 なぜTransXは対称関係と非対称関係の両方を満たすことができるのでしょうか？証明は比較的簡単です。結論として、TransXは自然に非対称関係を満たします。あとは、TransXが対称関係も満たしていることを証明するだけで十分です。TransHを例に挙げると、TransHが対称関係に遭遇した場合、学習したパラメータはゼロではないという条件を満たす必要があります。後者がゼロではないため、このパラメータは異なる関係を区別することができます。 3) 複雑な関係性に関する比較実験
上の表からわかるように、モデルはそれぞれ異なるパターンに適用できるため、データセットによってパフォーマンスが異なります。TransEは対称的な関係には適していないため、4つのデータセットすべてでパフォーマンスが低下します。ComplExは組み合わせ関係にのみ適していないため、最初の2つのデータセットではパフォーマンスが向上しますが、最後の2つのデータセットではパフォーマンスが低下します。RotatEはすべての関係に適しているため、4つのデータセットすべてでパフォーマンスが向上します。 4) 自己抵抗的負のサンプリング 本論文では、良好な結果をもたらす自己敵対的ネガティブサンプリング法を提案する。従来のネガティブサンプリングの損失は以下の通りである。すべてのトリプルを均一に、すなわち1/kの係数で扱うと、訓練中に多くの例が明らかに偽物であり、意味のある情報を提供しないため、問題が生じる。 そこで、ネガティブサンプリング法の改良として「自己敵対的ネガティブサンプリング」が提案されている。これは、現在の埋め込みモデルのスコアに基づいてネガティブサンプルをサンプリングする手法である。具体的には、ネガティブトリプルは以下の分布に従ってサンプリングされる。 この確率分布を負の例の重みとして扱うと、自己敵対的トレーニングによる最終的な負のサンプリング損失関数は次のようになります。 注: 区別が難しい負のサンプル (スコアが低いもの) に高い重みが与えられるように、重み付け係数は最終的に負になる必要があります。 5) ネガティブサンプリング比較実験 上の表からわかるように、TransE は自己敵対的ネガティブサンプリングを使用した後、大幅な改善を示しています。 上の表からわかるように、このネガティブサンプリング法は他のモデルでもうまく機能します。そのため、RotatEの利点はそれほど明白ではありません。 DTransEDTransEアルゴリズムは、当社のナレッジグラフチームが独自に開発したアルゴリズムです。詳細については、本記事末尾のATA関連記事シリーズをご覧ください。このアルゴリズムは、下図に示すように、セマンティックマッチングモデルと距離モデルを統合しています。 図: DtransE原理の模式図 スコアリング関数は次のように表現されます。 これはトリプルのスコアリングを伴います。ここで、h、r、tはそれぞれヘッドノードベクトル、リレーションベクトル、テールノードベクトルであり、乗算は位置に基づいて行われます。DTransEアルゴリズムには以下の特徴があります。
パフォーマンスの面では、DTransE アルゴリズムは、FB15K-237、WN18、YAGO3-10 などの複数のデータセットで最先端の結果を達成または匹敵します。 トランスシリーズアルゴリズムの概要:アルゴリズム transH、transD、および transR は幾何学的に等価で、ベクトル h および t に対して空間変換を実行します (角度変換と長さのスケーリングを含む)。 異なる関係 r は異なる変換行列に対応し、異なる数のパラメーターを持ちます。 実験では、パフォーマンスの点から、一貫して transH > transD > transR が示されています。 なぜ異なるのでしょうか。これは、パラメーターの数が異なるためです。 transH には法線ベクトル w <sub>r</sub>という 1 つのパラメーターしかありませんが、 transR には変換行列があります。 transD は transR を縮小したもので、パラメーターは 3 つのベクトル w <sub>r </sub> 、 w <sub> h</sub> 、および w<sub> t</sub>に縮小されています。 パラメーター数の観点からは、transH < transD < transR です。 そのため、トレーニング データが限られている場合、最適なモデルを学習するのが最も簡単なのは transH であり、次に transD が続きます。 TransR は、過剰適合する傾向があるため (パラメーターが多く、自由度が高いが、収束するのが難しい)、学習が最も困難です。 tranSparse、transA、transA'は、それぞれ異なる特定領域をターゲットとしたアップグレードです。RotatEは、対称/非対称、反対称、組み合わせ関係を同時に満たすことができ、付随する自己敵対的ネガティブサンプリングの性能も良好です。DTransEアルゴリズムは、対称/非対称、反対称、組み合わせ関係をサポートし、モデルサイズと計算量を大幅に削減しながら、良好な結果を達成しています。 02: グラフベースの伝播モデルグラフ埋め込みは、グラフの構造情報を反映した低次元の稠密ベクトルを用いてグラフ内のノードを表現します。2つのノードが共有する隣接ノードの数が多いほど、対応するベクトルは近くなります。このベクトル表現の利点は、あらゆる機械学習モデルに入力して特定の問題を解決できることです。
CNNアルゴリズムは画像および動画処理において大きな成功を収めていますが、データセットがユークリッド構造を持つことが前提となります（下図左）。画像および動画データ内の整然と配置されたピクセルの行列は、この要件を完全に満たしています。しかし、グラフは非ユークリッド構造であるため（下図右）、CNNはグラフ処理には不向きです。CNNは非ユークリッドデータに対して並進不変性を維持できません。簡単に言えば、位相グラフでは、異なる頂点の隣接頂点の数が常に同じとは限らないため、同じサイズと構造を持つ単一の畳み込みカーネルを使用して、グラフ上で並進による畳み込み演算を実行することはできません。そのため、グラフベースのディープラーニングモデルが必要です。
グラフ アルゴリズムを解くには、空間法とスペクトル法という 2 つのアプローチがあります。 空間領域で解決するためのアルゴリズムには、Structure2vec、GNN、GatedGNN、GraphSAGE、GAT、GeniePath などがあります。 スペクトル領域で解決するためのアルゴリズムには、オリジナルの GCN、ChebNet などがあります。 このセクションでは、ランダムウォークアルゴリズムnode2vecの紹介から始め、続いてmetapath2vecとCOSNETを紹介します。次に、Alpsプラットフォームに既に実装されている3つの教師ありアルゴリズム（Structure2Vec、GeniePath、GAT）を紹介します。最後に、当社のグラフチームが独自に開発したアルゴリズムNCLFとKARIを紹介します。 ノード2ベクトル
node2vec [23]はディープウォークアルゴリズムに類似しており、グラフの構造情報をランダムウォークを通してノードの埋め込みベクトルに表現します。node2vecの主な革新性は、ランダムウォーク戦略を改良した点です（ディープウォークは2つのシーケンスを取得する完全なランダムウォークです）。node2vecは2つのパラメータpとqを定義し、BFS（幅優先探索）とDFS（深さ優先探索）のバランスを実現し、局所情報とマクロ情報の両方を考慮し、高い適応性を備えています。
最初のステップはランダムウォークです。各ノードからr回のランダムウォークを実行し、各ノードのパスを生成します。このパスを文として扱い、word2vecを使って学習します。 2つ目のステップであるword2vecでは、各単語のワンホットベクトルにVxN行列を乗じてベクトルを圧縮します。次に、コンテキストが存在すると仮定し、ウィンドウC内で条件付き確率（CBOW）を計算します。最後に、目的関数を用いて埋め込みベクトルを学習します。 最適化目標 Node2vecとword2vecは、同じ最適化目標（損失）を共有しています。図に示すように、損失はすべての点vからuへの確率の合計を最大化することとして定義されます。2番目の式の分母はすべてのノードのペアワイズ積の合計を必要としますが、これは計算負荷が大きすぎるため、 元の分布を近似するためにランダムサンプリングが使用されます。正のサンプルは前のランダムウォークから得られた集合から取得され、負のサンプルはランダムネガティブサンプリングによって取得されます。明らかに、負のサンプルが多いほど、分布は元の分布に近づきます。
ご覧のとおり、教師なしモデルでは、node2vec は、BFS または DFS バイアスを含む戦略をランダム ウォークに組み込むことで、バイアスのない Deepwalk アルゴリズムを大幅に改善します。
ノード類似度の計算に使用され、リンク予測にも利用できます。教師なし学習であり、ラベル付きデータを必要としないため、幅広い応用が可能です。 メタパス2vec
2017年に発表されたmetapath2vec [24]は、メタパスベースのランダムウォークを用いてノードの異種近傍を再構築し、異種スキップグラムモデルを用いてノードのネットワーク表現を解きます。DeepWalkとnode2vecは同種ネットワークにおける表現学習法であり、異種ネットワークに直接適用することはできません。metapath2vecは異種グラフ上で直接ランダムウォークを実行できます。metapath2vecは、複数のノードタイプと複数の関係タイプを持つ異種グラフをサポートし、ノードの埋め込みベクトルを学習します。本論文では、metapath2vecとmetapath2vec++の2つのモデルを提案しています。 （１）metapath2vec：メタパスメカニズムに基づいてランダムウォークを実行することでノードシーケンスを構築します。 2) metapath2vec++: skipgram モデルのネガティブ サンプリングの改良。均質ネットワーク内のすべての (タイプ) ノードのランダム サンプリングを、現在のノード タイプのノードのみのサンプリングに変更します。 メタパス：メタパスとは、複数のノードタイプを一連の関係性を通して接続するパスです。異種ネットワーク内の異なるタイプのオブジェクト間の様々な接続や意味的関係を記述するために使用できます。 本論文は、異種ネットワーク表現学習問題を定式化し、複数のノードに対する低次元の暗黙的埋め込みベクトルを同時に学習することを目標とする。metapath2vecの目標は、与えられた異種ネットワークの構造と意味を保持する可能性を最大化することである。 ランダムウォークの遷移確率は、与えられたメタパスに従う必要があります。例えば、メタパスに従って次のノードの型がtである場合、近傍ノードのうちt型のノードのみが選択されます。他の型のノードや、現在のノード以外の近傍ノードは選択されません。
最初のステップは、メタパスのルールに従ってランダム ウォークを実行し、パスを取得することです。 （１）メタパスが与えられると、アルゴリズムはパスの長さがウォーク長に達するまでメタパスに沿って歩きます。 (2) 与えられたメタパスは、最初と最後のノードの型が同じである必要があります。正しい形式の例：「ABCA」、「VDEEV」、「ABA」など。 （3）与えられたmetaPathが「ABDSA」でwalkLengthが10の場合、walkの結果は「ABDSABDSAB」となり、10ノードに達すると切り捨てられます。 2 番目のステップでは、メタパス トラバーサルから取得したパスを「文」として使用し、それを word2vec に入力します。ここで、skip-gram を使用して埋め込みベクトルを学習します。
本論文では、ノード分類、多クラス分類、ノードクラスタリング、可視化、パラメータ感度分析に関する実験結果を紹介します。他の手法（主に典型的な同型グラフに対する手法）と比較して、metapath2vecは大幅な改善を示しました。しかし、多クラス分類においては、metapath2vec++はmetapath2vecよりもパフォーマンスが著しく劣ります。 コスネット
COSNET [25]は2015年に公開され、当初の目標はTwitter、Myspace、LiveJournal、Flickr、Last.fmといった異なるソーシャルネットワークを統合することでした。これらの異なるソーシャルネットワークは、異なるエッジタイプを持つ異種グラフです。COSNETは、大域的一貫性と局所的一貫性を目的関数として組み合わせた教師ありモデルであり、ラベル付きデータから学習することで、モデルの予測が大域的および局所的の両方で可能な限り一貫性を持つようにします。 目的関数は 3 つの部分から派生します。項はグローバル一貫性を表し、項はローカル (2 ホップ範囲) 一貫性を表し、項はローカル (3 ホップ範囲) 一貫性を表します。 ここで、候補ペアは、ペアリングが正しいかどうかを示すラベルで表されます。
このアルゴリズムは従来のアルゴリズムに比べて若干の改善が見られますが、その改善は限定的です。下表に示すように、COSNETは最も基本的なユーザー名IDに基づくマッチングと比較して、わずか10パーセントポイント強しかパフォーマンスが向上していません（図の「name-match」列）。さらに、「COSNET-」列は、グローバル一貫性の影響を差し引いた後でもわずか1パーセントポイントの変化しか見られず、本稿で導入したグローバル一貫性が大きな役割を果たしていないことを示しています。 GCN
一般的に、GCN [26-28]は主に2つのカテゴリに分類されます。1つはフーリエ領域における畳み込み、もう1つはグラフ上で直接畳み込みを行う「空間領域畳み込み」です。スペクトログラフ畳み込みは統一的な理論的裏付けがありますが、グラフラプラシアン演算子によって制限されることがあります。下の2つの図は、それぞれ1次元と2次元のグラフ畳み込みを示しており、赤い点は畳み込みの範囲を表しています。 図: 1次元および2次元グラフ畳み込みの模式図 文献[28]の式(3)-(5)は、空間情報の畳み込みから容易に適用可能な畳み込みカーネルを導出する方法をわかりやすく説明している。原文は以下の通りである。 上記の式(3)は、CNNの畳み込みを画像からグラフへと移したものです。CNNと比較することができます。ここで、構造関数gはカーネル関数であり、全ノードの特徴量からなる行列xは、CNNで畳み込み対象となる画像に相当します。下図に示すように、CNNは画像に対して畳み込みを行い、GCNはノードの特徴量に対して畳み込みを行います。 GCNをより深く理解するために、CNNとの類似性をさらに高めます。第一世代GCN [26 ]の畳み込みカーネルのサイズは、上記の式(3)に示すようにグラフ全体であり、グラフ上でグローバル畳み込みを実行することと同じです。これは計算コストが高すぎるため、後続のGCNでは近似が行われ、最も古典的なのはKipf [28]の研究で、上記の式(4)に示すようにチェビシェフ多項式を使用し、最初のK項を畳み込みカーネルの近似として採用しています。KはKホップによって選択される近傍の範囲に対応します（実際には、Kは2または3であることが多いです）。これは、グローバル畳み込みカーネルをローカル畳み込みカーネルに置き換えることと同じです。後でわかるように、K=2または3のとき、チェビシェフ多項式は2乗項と3乗項になり、これは元のGCNの比較的大まかな近似です。幸いなことに、各用語に重みを追加し、ラベルを使用して学習することで、このエラーを補うことができます。 ラプラシアン演算子について説明します。ラプラシアン演算子は、各ノードの次数から隣接ノードの次数を引いた値、つまりL = DAとなります。ここで、Dは次数行列（対角行列）、Aは隣接行列です。Lにxを掛けることは、各ノードの情報を隣接ノードに伝播させることと等価です。本質的に、ラプラシアン演算子は2階差分です。物理的には、対象ノードの情報を、その勾配に比例する力で近傍点に伝播させます。 注：畳み込み定理。関数の畳み込みのフーリエ変換は、関数のフーリエ変換の積です。これは次の式で表すことができます。関数との畳み込みは、それらのフーリエ変換の積と関数と の逆変換です。 式(3)の2つの固有行列Uを乗算する計算コストが大きすぎるため(O(N²))、式(4)はチェビシェフ多項式展開を使用して近似されます。したがって、式(3)は式(5)のように近似されます。ここで、多項式の次数は伝播範囲のホップ数に対応します。チェビシェフ多項式は次のとおりです。 GCNでは、1次集約は1つの畳み込み層に相当し、K次集約はKつの畳み込み層に相当します。CNNと同様に、すべての畳み込み層（アグリゲータ）はパラメータを共有するため、ラベル付きデータを入力することでこれらのパラメータを学習できます。このパラメータ共有によりパラメータ空間が大幅に削減され、モデルのスケーラビリティが向上します。上の図では、複数のGCN畳み込み層とReLU活性化関数を組み合わせることで、ノードはより遠くの近傍ノードからの情報を受信できます。 GCN畳み込み層の具体的な表現は次のようになり、層tから層t+1への伝播は次のように表すことができます。 ここで、 は正規化された隣接行列、 Hはノード表現ベクトル、 Wはモデルパラメータです。 。
适用的场景包括：节点属性预测（属性分类/ 回归）等，但有限制，只适用于双向图。 trick：当数据分布不均匀时（即绝大部分边集中于少数节点之间），一个技巧就是，在采样取K 度邻居的过程中，采取限制最大邻居数量等类似手段，可以对节点（特别是头部节点）采样的邻居数量进行限制。
可以看到GNN 的实验效果明显好于基于随机游走的Deepwalk 等基础算法。 Structure2Vec
kernel methods 在2002 年代是处理结构化数据的代表方法，包括两类：基于bag of structures 和基于probabilistic graphical models (GM)。但是kernel methods 特别依赖于核函数（即特征空间）的设计。缺点是不能处理大规模图。 为了能够处理大规模图，宋乐老师团队开发了Structure2Vec [29,30] 。因为不需要存储核矩阵（kernal Matrix）所以占用内存小了很多，应用了随机梯度下降后也具有处理大规模图的能力。Structure2Vec 包含了两种传播方式Mean Field 和Loopy Belief Propagation（后来扩展到了更多种传播方式）。
Structure2Vec [29,30]是什么： 是一个基于知识图谱的深度学习和推理算法，是一种graph embedding 算法。不仅仅考虑节点的特征，还考虑了节点和边之间的相互作用以及传播。
讲解原理之前首先介绍聚合算子的概念。图谱可以看作由多个中心节点和对应的邻居节点组成。下一步需要考虑的就是如何将信息从邻居节点汇聚到各个中心节点。下图给出了2 跳聚合算子的示例，中心节点A 的表示是由其邻居节点B、C、D 的信息聚合而来，而节点B、C、D 的信息是由它们各自的邻居信息聚合而来。最终得到了聚合算子(aggregator)，其作用是对邻居节点的信息进行聚合。为了方便理解，我们类比CNN，聚合算子就相当于卷积层，因为他们都起到了将周围点的信息汇聚起来的作用。 图：两跳聚合算子示例
解决了以前的深度学习技术难以用于诸如图形、网络和动态网络等组合结构数据的表示和特征学习。
图: Structure2Vec 的基本原理[30]
Y i ：节点i 的标签（label） X i : 节点i 的属性值（value of attribute） H i : 是一个隐变量，是输入X i的代言 ：节点i 的向量化表示，其初始化是通过对特征进行信息抽取得到。 W 1 、W 2 ：节点i 与自身以及与邻节点的相互作用，包含了图结构以及节点的特征信息。 V：节点i 的特征向量与输出Y i ' 之间的转换矩阵。注意参数W 2和V 并不是针对某一个节点的，而是整个网络都采用这同一套参数，即共享参数。 n：节点特征维度。 d：特征向量的维度。
（1）对于第i 个节点，该节点的特征信息传递给自己，邻居的信息再传递过来。然后经过K 度传播，可以获得以i 节点为中心的一个subgraph，作为训练集的一个基本单位。 （2）最小化损失函数loss=(Y i -V ) 2 。采用训练集训练（随机梯度下降），通过最小化损失函数得到模型W 1 ，W 2 ，V。 （3）在infer 过程中，先获取节点i 的K 度subgraph，然后将该subgraph 带入模型便可以得到该节点的嵌入向量以及预测结果。 说明：这里介绍的是Mean Field 方法，另外作者在文章中还介绍了一种方法Loopy Belief Propagation。这两种方法的区别是：前者的信息传播过程是，在一个超步内，通过对每一个相关节点上的信息进行收集得到的。后者的信息传播过程包含两步，在一个超步内，第一步对每条边上传播的信息进行汇总，第二步再对每条经过节点i 的边上面的汇总后的信息进行收集。
Structure2Vec 提供了一种能够同时整合节点特征、边特征、网络结构以及网络动态演化特征的深度学习和推理嵌入技术。它可以对网络中的节点和边进行推理，能够挖掘出节点之间的二度、三度甚至更深层次的关系。Structure2Vec 平台支持十亿节点、百亿边规模的图模型训练，并且对于实际小于百万节点的小规模业务场景，其也支持使用单机模式迅速训练，用户可以根据自己的需要进行随意切换或让系统自动切换。Structure2Vec 平台提供了一整套流式解决方案，从用户原始数据检查、到模型训练和导出模型和预测结果给业务，都可以通过简单配置设置例行运行。
1). 矩阵乘法采用GPU 加速； 2). T 度传播，当T 较小的时候，可以只加载局部图； 3). 利用Parameter Server 进行分布式计算。
Structure2Vec 需要与有监督学习相结合。其应用分为两类，一类是应用于静态图，一类是应用于动态图。 静态图应用中，Structure2Vec 可以分别对节点、边、子图的结构进行分类或回归。应用举例： 1) 垃圾账号识别，这属于节点分类问题。账号和设备之间的登录情况构成图谱，并且账号和设备也各自具有特征。然后利用带有标签的账号数据对经过T 次信息传播后的模型进行训练，得到传播权重W 1 、W 2和分类参数V 以及每个节点（账号）的嵌入向量。有了这些参数和嵌入向量就能对未打标签的节点进行预测了。 2) 基于分子结构预测光伏作用大小的问题，如下图所示，这就属于子图结构预测问题（预测的是连续值所以这是回归问题）。首先经过T 次传播，然后通过训练得到了传播权重W 1 、W 2和分类参数V 以及每个节点的嵌入向量。训练的目标函数是通过对这些嵌入向量的加权求和来表示光伏作用的大小，然后与打标的target 之间的平方差定义为loss。训练好了模型以后，就可以预测新的分子结构的光伏作用大小了。 3) 通过药物分子结构预测药物效果，就属于利用结构信息进行分类的问题，原理和过程与2) 类似只是由回归问题变成了分类问题。 图：利用Structure2Vec 基于分子结构预测光伏作用大小的问题
FC_RES 数据集描述的是RNA 将基因片段定向到DNA。SCOP 数据集是蛋白质结构分类，这两个都是子图分类问题。前面四种算法都是kernal method，后面两种是Structure2vec 的两种实现方式。可以看到Structure2vec 的效果明显好于kernal method。 这个实验是基于分子结构预测光伏作用大小的问题，WL 是kernal method，后面两种是Structure2vec 的两种实现方式。MAE 是平均误差，RMSE 是均方根误差。可以看到Structure2vec 的效果明显好于kernal method。另外，一个重要的区别是kernal method 是not scalable 的，而Structure2vec 是scalable 的，实验中WL lv-6 对于百万大小的数据集其参数数量比后两者多了1 万倍，速度却只慢了两倍。 动态图应用中，多了一个时间轴，Structure2Vec 可以对节点之间是否会发生交互以及交互的概率进行预测。应用举例： 1). 推荐系统。User 和iterm 随着时间的交互展开成一个单一方向的图结构，如图所示，通过强化学习得到嵌入向量，对某个时刻的user 和item 的嵌入向量做内积，就能判断二者在该时刻的交互发生的概率。 2). 对事件的预测，与1) 同理。
图：利用Structure2Vec 基于时间动态演化进行商品推荐 应用情况：目前Structure2Vec 在信用评估、推荐系统、行为预估、垃圾账号识别、保险反欺诈以及芝麻信用团队的反套现模型中都取得了非常好的效果。 GraphSAGE
GraphSAGE [31]和Structure2vec 比较类似，都是由聚合算子构建起来的图计算模型，都是共享参数的模型。GraphSAGE 是比较早期的经典GNN 算法，来自斯坦福发表于2017 年。很多文献都会和GraphSAGE 进行比较。这篇文章明确提出了图算法中的transductive learning 和inductive learning 的区别。 直推式(transductive) 学习：从特殊到特殊，仅考虑当前数据。在图中学习目标是学习目标是直接生成当前节点的embedding，例如DeepWalk、LINE，把每个节点embedding 作为参数进行学习，就不能对新节点进行infer。 归纳(inductive) 学习：也就是平时所说的一般的机器学习任务，以共享参数方式进行学习。从特殊到一般：目标是在未知数据上也有区分性。
GraphSAGE 同样采用聚合算子，其信息聚合的过程如上图所示，可以描述为以下三个步骤：
算法伪代码如下： 其中4、5 行的for 循环描述了汇聚算子的工作过程。第4 行描述了信息由k-1 层汇聚到第k 层。第5 行描述了中心节点信息由中心节点的k-1 层信息与中心节点的邻居信息进行拼接，并通过一个全连接层转换，最终得到中心节点在第k 层的嵌入向量。 GraphSAGE 提出了四种不同的聚合方式：平均聚合、GCN 归纳聚合、LSTM 聚合、pooling 聚合。 a. 平均聚合：先对邻居embedding 中每个维度取平均，然后与目标节点embedding 拼接后进行非线性转换。 b. GCN 归纳聚合：直接对目标节点和所有邻居emebdding 中每个维度取平均（替换伪代码中第5、6 行），后再非线性转换： c. LSTM 函数不符合“排序不变量” 的性质，需要先对邻居随机排序，然后将随机的邻居序列嵌入向量作为LSTM 输入。 d. 先对每个邻居节点上一层嵌入向量进行非线性转换（等价单个全连接层，每一维度代表在某方面的表示），再按维度应用max 或者mean pooling，捕获邻居集上在某方面的突出的或者综合的表现以此表示目标节点嵌入向量。
从实验结果上可以看到GraphSAGE 的四种聚合方式比传统算法均有所提升。 ガット
Graph Attention Networks (GAT) [32]算法的主要思想是利用attention 机制来代替GCN 中的卷积层，得到node embedding。同时该算法可以适用于transductive 和inductive 两种任务。transductive 任务是指测试集的节点和节点特征在训练过程中出现过；inductive 任务是指测试集中的节点不会在训练过程中出现。下面介绍其核心结构Graph Attention layer.
对于每一层，输入为每一个节点的feature, h={h 1 ,h 2 ,⋯,h N }, h i ∈R F ，N 为节点个数，F 为输入特征维数。输出亦为每一个节点的feature, h'={h′ 1 ,h′ 2 ,⋯,h′ N }, h′ i ∈R F′ ，F′为输出特征的维数。则attention 机制就是在对输入特征做线性变换W∈R F′×F后计算对于节点i 其周围节点（包括自身）的权重，最后加权求和通过激活函数即得到节点i 的输出特征。则节点j 对节点i 的权重（可以看做节点j 对于节点i 的重要性）为： 其中就是attention 机制，后面会给出几种具体的形式。则节点i 输出可由对其相邻点加权得到： 上面这一步softmax 为对权重的正则化。 上面这一步就是一个加权求和。注意到这个模型只用到了节点特征，没有用到边的信息。 文中给出的attention 机制有两类：一类是单层网络，如下： 另外一类是多头注意力网络（multi-head attention）的两个例子，第一个例子是将不同的head 得到的嵌入向量做拼接，第二个例子是做平均，如下: 图: Graph Attention Networks (GAT) 算法的Graph Attention layer 图示 因为Attention 计算相互独立，方便并行计算，所以比传统的GCN 高效。
可以看到实验结果都还不错，尤其是PPI 的结果，比GCN 的结果高太多了。文章发表在ICLR 2017 [32]上。
GAT 算法和下面将要介绍的GeniePath 算法比较相似，都是建立在GNN 基础之上，只是GAT 只添加了对邻居节点信息进行筛选的attention 机制，而GeniePath 除此之外，还采用了LSTM 机制来过滤经过多层传播的信息。从效果来讲，这两种算法的表现也比较接近，并且二者的表现都明显好于之前的GNN 算法。
因为算法特性一致，GNN 能够使用的场景（比如前面Structure2Vec 的应用场景），GAT 理论上应该都适用。 GeniePath
图: GeniePath 算法的发展脉络 GraphML 团队开发的GeniePath 算法[33,34]可以在聚合算子上结合节点的属性信息来判断到底有多少信息需要传播，有多少信息可以过滤掉。简单来讲就是，和structure2vec 相比，GeniePath 的聚合算子不仅仅采用了结构信息而且还结合了节点属性信息，就具有了更强大的表达能力。
下图揭示了GeniePath 的算法结构，其结构是在基本的聚合算子上做了扩展。虚线左边表示在广度上采用了attention 机制来筛选邻居节点；虚线右边表示在深度上采用了LSTM 机制来过滤经过多层传播的信息。 下面的方程就描述了GeniePath 在深度上的attention 机制以及广度上的LSTM 机制。
其中是输入门；是遗忘门；是输出门。
（8） GeniePath 沿用GNN 的计算框架，其特点在于会根据优化目标自动选择有用的邻居信息，来生成节点特征（embedding）。GeniePath 通过定义两个parametric 函数：自适应广度函数、和自适应深度函数，共同对子图进行广度、深度搜索。其中自适应广度函数限定朝哪个方向搜索重要节点，自适应深度函数限定搜索的深度。实现中如上图所示，GeniePath 使用一个attention 网络表达自适应广度函数来来筛选邻居节点，使用一个LSTM-style 网络表达自适应深度函数来过滤经过多层传播的信息。GeniePath 后来进行了升级，不仅能考虑节点特征，还能考虑边的特征。 目前所有的图神经网络方法都基于如下框架，做T 次迭代，相当于每个节点拿自己走T 跳可达的“邻居” 节点，来做传播和变换，最后的被用来直接参与到损失函数的计算，并通过反向传播优化参数。在GeniePath 之前的算法：Structure2Vec、GCN、GraphSAGE，他们的共同特点是对T 步内所有邻居做聚合（aggregate），且以固定的权重做聚合。这些经典的GNN 方法只会根据拓扑信息选择邻居并聚合生成特征，不会过滤和筛选有价值的邻居。而我们不但要看拓扑信息还要看节点的行为特征。GeniePath 关心在聚合的时候到底应该选取哪些重要的邻居信息、过滤那些不重要的节点信息。 图：自适应的感知域示例
1). 相比其他GNN 算法，在大数据上可能有更好的性能，效率更高！ 2). 可解释性更强。注意力权重可以区分出重要的边和次要的边，增加了可解释性。
Alipay 的数据集有1M 节点，2M 边，4k 特征。可以看到数据集越大，效率越高，效果越好。 对蛋白质相互作用推理，F1 值提升明显。
因为GeniePath 是其他GNN 算法的升级版，因此其他GNN 算法的应用场景（比如前面讲到的Structure2Vec 的应用场景）GeniePath 应该都能实现，并且一般都可以期待更好的性能。GeniePath 作为一个通用图神经网络算法已经在蚂蚁金服的风控场景实际使用，并得到较理想的效果，很好地提高了支付宝保护用户账户安全的能力[35]。其论文中还实现了的GeniePath 应用场景包括：引用网络、BlogCatalog 社交网络、蛋白质相互作用网络。 HeGNN
GraphML 团队开发的HeGNN [36]算法在GNN 算法的基础上引入了多层次注意力机制。该算法支持异质图，即支持不同类型的节点和不同类型的边。过程可以简单理解为将不同类型的关系做成多个同质图，然后合并在一起。具体如下： HeGNN 算法使用了MetaPath（元路径）。每一条元路径携带着不同的语义，可以帮助我们利用异质信息网络中丰富的结构信息。比如消费图谱中的“User - (fund transfer) - User” (UU) 记录了用户与用户之间的转账信息，“User-(transaction) -Merchant-(transaction)-User” (UMU) 记录了两个用户同时在一个商家交易的信息。有效地融合这些元路径信息，可以使得模型充分利用不同类型的边的差异信息。下一个问题是如何有效地聚合异质的邻居信息。 层次注意力机制 直觉而言，不同的邻居、特征以及元路径会对节点的表示产生不同的影响。因此，下面介绍如何建模节点对这些方面信息的偏好。 邻居注意力 参照GAT 算法的思想计算节点对每个邻居的注意力值，代表着每个邻居的贡献。可以按照如下的计算公式实现： 针对具体的场景，作者也给出了两种可替代的实现如下： (1) avg-pool : 针对大规模的业务场景，可以直接对元路径下的邻居的特征做加权平均。这样可以大大降低计算量，而且一般可以得到一个不错的结果。 (2) geniepath-pool : 对于每一条元路径下的邻居，可以复用geniepath 来实现单一元路径下的特征表示。 特征注意力 不同的特征可能对节点的表示存在不同的贡献。因此，参照文献，作者设计了如下的特征注意力层对每个特征点计算特征贡献值: 路径注意力 元路径抽取了节点在异质信息网络中的不同方面的信息，比如元路径“UU” 抽取了用户的转账信息，元路径“UMU” 抽取了用户的交易信息。所以需要设计路径的注意力层来捕获节点对不同元路径的偏好。具体地，按如下方式为每个节点计算它对元路径集合中每条元路径的注意力值： NCLFNCLF [37] （Neural Conditional Logic Field）是一种融合逻辑规则的推理算法。 我们知道神经网络的优点是学习能力强，但是需要的标注样本较多。而逻辑规则推理正好相反，它所需的标注样本少，但学习能力有限。NCLF 的出发点是把这两者的优点融合，填补各自的缺点。 把专家经验引入到学习中来提高学习效率最近很火，专家经验可以转述为一阶逻辑，经典的解法是马尔可夫逻辑网络（MLN），并采用变分推断（VI）来加速求解，NCLF 进一步引入GCN 来近似后验。在实现的过程中我们使用Hinge-Loss Markov Random Fields（HL-MRF）进一步简化计算，将全举过程近似为一次性计算，使其更适用于工业大数据。为了减少GCN 消息传播的衰减，引入了Loopy belief propagation。另外在构图上将二部图变为一般图。而引入规则之后，可以基于统计或学习得到规则权重，去掉坏规则可以进一步提高学习效果。在工程计算上，因为一阶逻辑的计算需要进行实例化（Grounding），计算量大，实际使用中需要进行分布式样本生成。 我们在公开数据集和业务规则数据上分别进行了效果对比。 カリKARI 算法是我们基于ALPS 的KGNN [38]框架延伸开发的算法框架。这里简要介绍其原理，详细内容可以查看KARI ATA 文章[39] 。本文前面介绍的传统的链接预测算法比如基于向量之间距离的Trans 系列算法、基于语义匹配模型RESCAL 系列算法、基于随机游走的node2vec 系列算法，这些算法把嵌入向量作为参数通过学习来获得，在小规模图上能够取得不错的效果，但对于大规模图来讲，参数空间暴涨，难以落地。GraphML 团队的KGNN 框架提出将传统算法和GNN 类算法相结合，就具有了共享参数这个优点。采用共享参数的聚合算子会极大降低参数空间，就能适用于大规模图推理。因此，为了充分挖掘大规模图谱中的结构信息以及充分学习图谱中丰富的异质信息导致的一对多、多对一、对称、非对称、相反、组合等关系，我们在Encoder-Decoder 的思想下，Encoder 选用GeniePath，Decoder 选用DtransE，再结合自对抗负采样等能力结合而成了KARI 算法。 Encoder-Decoder 框架 KARI 默认选取GeniePath 为Encoder，默认选取DTransE 为Decoder。KARI 通过自监督学习生成节点和边的表达（Embeddings），可输出给下游模型使用，补充图结构特征。这里自监督学习是指标签数据不需要人工打标生成，利用边表中已知的三元组可以构成正样本，然后随机生成负样本，就构成了训练集。 图：KARI 的Encoder-Decoder 框架示例 KARI 目前支持的Encoder 和Decoder 如下：
下图中Encoder 部分，中心节点A 的嵌入向量是由其邻居节点B、C、D 的信息聚合而来，而节点B、C、D 的信息是由它们各自的邻居信息聚合而来，每一层汇聚就是一次迭代。这样我们通过Encoder 中的T 次迭代就获得了中心节点A 的嵌入向量，重复这一过程还可以获得中心节点B 的嵌入向量。关系r 的嵌入向量最初由随机过程生成。然后将节点A、节点B 和关系r 的嵌入向量带入Decoder 计算得分，再利用得分来计算loss。 图：KARI 的Encoder 和Decoder 示意图 Decoder 的作用是将嵌入向量中的节点特征和图结构信息直观的表达为三元组的打分，该打分可以理解为三元组成立的“概率”。KARI 的Decoder 默认选择我们团队自研的DTransE 算法。 KARI 算法的特性总结如下：
KARI 目前支持的业务包括：最终受益人UBO 关系预测、可信关系降打扰、支付推荐、支付搜索、财富内容带货等等，并取得了较好的效果。 GraphSAINT
当数据有热点时，限制随机采样邻居个数这类做法可能导致采样到的邻居中有不重要的邻居，并且丢失了重要邻居的信息。特别是当我们需要计算多层邻居时，子图大小指数暴涨，难以计算。GraphSAINT [40]旨在解决稠密点的问题，它从根本上改变了采样方式。它不再在原图上采样邻居，而是从原图上采样一个子图下来，在这个子图上做局部的、完全展开的GCN。优点：
采样策略倾向于影响大的节点被保留下来。采样概率只和链接信息有关，和节点特征无关。很适合提前预采样，下游GCN 模型不用做改造。 上表给出了四种采样策略：
GCN 的通用表达式： 因为采样的图的分布和原图往往有差别，这会引入采样偏差。接下来的目的是尽量消除这个偏差。方法如下，采样以后中心节点的表达式修正如下： 其中和是指当v 被采样到的前提下，u 被采样到的概率，二者概率的期望会互相抵消。这样就消除了采样的偏差。同理，在损失函数中也除以一个参数，消除采样偏差。 其中指在一次采样图中采样到v 的概率。
可以看到效果提升明显，特别是PPI 数据集。而且效果比Cluster-GCN 略有提升。GraphSAINT 效果好的可能原因： 1. 消除了噪音信息 2. 朴素采样的GCN 的mini-batch 的方差较大，收敛性不好。 3. 小图计算量小，可以训练更多个epoch Cluster-GCN
Google 开发的Cluster-GCN [41]算法，通过聚类形成一个个簇，并将链接尽量限制在簇内，起到了前置采样的效果。论文中介绍了两个算法方案，朴素版本的Vanilla cluster-GCN，和升级版本的Multiple cluster-GCN。下面分别介绍。 Vanilla cluster-GCN 该算法先做一次聚类，每个聚类的子图用来进行训练。聚类的目的是使簇内连接远大于簇间连接。图变小了，算法效果也不错。从热点角度来看相当于从多个热点中选出了少量几个热点作为簇，并隔离了不同的簇。该算法最大的优点是减小了batch 之间的variance（偏差），效果提升，以及多层计算量呈线性而非指数增长。 只保留对角处的矩阵，近似忽略非对角处的矩阵。其含义是保留簇内的连接，忽略簇间的连接。 对于Vanilla cluster-GCN， 每个簇对应一个batch 。这样导致计算效率增加，计算精度提高。效率增加是因为随着层数增加，节点数量呈线性增长，而其他GCN 呈指数增长；精度增加其解释是减小了batch 间的Variance（偏差），以及增加了计算层数。 複数 cluster-GCN 尽管朴素Cluster-GCN 实现了良好的时间和空间复杂度，但仍然存在两个潜在问题：
为了解决上述问题，文中提出了一种随机多聚类方法，在簇接之间进行合并，并进一步减少batch 间的偏差（variance）。作者首先用一个较大的p 把图分割成p 个簇V 1 ,...,V p ，然后对于SGD 的更新重新构建一个batch B， 也就是一个batch 中有多个簇。随机地选择q 个簇，定义为t 1 ,...,t q , 并把它们的节点包含到这个batch B 中。此外， 在选择的簇之间的连接也被添加回去。作者在Reddit 数据集上进行了一个实验，证明了该方法的有效性。
实验中在两个公开数据集上达到了State-of-art 的效果。 話し合うアルゴリズム分類の観点から
无监督：Deepwalk、Node2Vec、Metapath2vec、LINE、Louvain 有监督：GCN (半监督)、GraphSAGE、SDNE (半监督)、GeniePath、GAT、Structure2Vec、HeGNN
支持异质图：HeGNN、metaPath2vec、KGNN 支持同质图：Deepwalk、Node2Vec、LINE、SDNE、GCN、GraphSAGE、GeniePath、GAT、Structure2Vec アプリケーションの観点から
所有的embedding 算法都支持链接预测。有一个区别是同质图模型支持一种关系预测，而异质图模型支持多种关系预测。（另外加上ALPS 平台尚未包括的trans 系列也可以做链接预测）。
所有的embedding 算法都支持相似度计算。相似度是由具体的任务目标来定义并体现在loss 中，一般的任务目标有距离相似性（两个节点有几度相连）、结构相似性、节点类型相似性（label 预测）。
GCN、GraphSAGE、GeniePath、GAT、Structure2Vec、HeGNN 等。 持续分享SPG 及 SPG + LLM 双驱架构相关干货及进展 官网：https://spg.openkg.cn/ Github：https://github.com/OpenSPG/openspg |
