(57)【要約】  ノード分類方法、モデル訓練方法、装置、機器及び記憶媒体であって、インターネットの技術分野に関する。該方法は、ターゲットノードセット中の分類対象ノードを取得するステップ（１０１）と、ターゲットノードセットから前記分類対象ノードのネイバーノードセットを取得するステップ（１０２）であって、ネイバーノードセットは少なくとも１つのネイバーノードを含み、ネイバーノードと分類対象ノードは関連付け関係を有するステップ（１０２）と、ノード分類モデルによって、前記ネイバーノードセットに応じて前記分類対象ノードのターゲット特徴情報を抽出するステップ（１０３）と、ターゲット特徴情報に応じて前記分類対象ノードの分類結果を決定するステップ（１０４）であって、ノード分類モデルは少なくとも１つのサンプルノードサブセットに応じて訓練されたモデルであり、該サンプルノードサブセットはサンプルノードセットのサブセットであり、サンプルノードセット中のノードはノードタイプがマークされているステップ（１０４）と、を含む。大規模グラフの場合、該方法は一部のノードのみに基づいて訓練を行うことができ、毎回グラフ中の一部のノードを反復計算すればよく、グラフ中の各ノードをトラバーサルする必要がなく、計算オーバーヘッドを大幅に削減させるとともに、計算リソースを節約する。
2021533474.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ機器に適用するノード分類方法であって、
ターゲットノードセット中の分類対象ノードを取得するステップであって、前記分類対象ノードは前記ターゲットノードセット中の少なくとも１つのノードを含み、且つ前記分類対象ノードの数は前記ターゲットノードセット中のノードの数よりも小さいステップと、
前記ターゲットノードセットから前記分類対象ノードのネイバーノードセットを取得するステップであって、前記ネイバーノードセットは少なくとも１つのネイバーノードを含み、前記ネイバーノードと前記分類対象ノードは関連付け関係を有するステップと、
ノード分類モデルによって、前記ネイバーノードセットに応じて前記分類対象ノードのターゲット特徴情報を抽出するステップと、
前記ターゲット特徴情報に応じて前記分類対象ノードの分類結果を決定するステップであって、前記ノード分類モデルは少なくとも１つのサンプルノードサブセットによって訓練されたモデルであり、前記サンプルノードサブセットはサンプルノードセットのサブセットであり、前記サンプルノードセット中のノードはノードタイプがマークされているステップと、を含むことを特徴とするノード分類方法。
【請求項２】
前記ターゲットノードセットから前記分類対象ノードのネイバーノードセットを取得する前記ステップは、
前記分類対象ノードに応じて前記ターゲットノードセット中の各候補ネイバーノードの第１候補確率を計算するステップと、
各前記候補ネイバーノードの前記第１候補確率に応じて前記ネイバーノードセットを決定するステップと、を含むことを特徴とする請求項１に記載のノード分類方法。
【請求項３】
前記分類対象ノードに応じて前記ターゲットノードセット中の各候補ネイバーノードの第１候補確率を計算する前記ステップは、
前記分類対象ノードと第ｕ個の前記候補ネイバーノードとの間の連結エッジ重み、及び前記分類対象ノードと前記ターゲットノードセット中のノードとの連結エッジ重みによって、第ｕ個の選択対象ネイバーノードの前記第１候補確率を決定するステップであって、ｕは正の整数であるステップを含むことを特徴とする請求項２に記載のノード分類方法。
【請求項４】
コンピュータ機器に適用するモデル訓練方法であって、
ターゲットノードタイプがマークされているサンプルノードセットから、ターゲットノードサブセット及び前記ターゲットノードサブセットに対応するネイバーノードサブセットを取得するステップであって、前記ネイバーノードサブセット中のネイバーノードと前記ターゲットノードサブセット中のターゲットノードは関連付け関係を有するステップと、
前記ネイバーノードサブセットに合わせてノード分類モデルによって前記ターゲットノードサブセットのノード特徴サブセットを抽出するステップであって、前記ノード特徴サブセットは前記ターゲットノードのノード特徴ベクトルを含むステップと、
前記ノード特徴サブセットに応じて前記ターゲットノードに対してタイプ予測を行い、予測タイプ確率サブセットを得るステップと、
前記予測タイプ確率サブセット及び前記ターゲットノードの前記ターゲットノードタイプに応じて前記ノード分類モデルのターゲットモデルパラメータを訓練するステップと、を含むことを特徴とするモデル訓練方法。
【請求項５】
ターゲットノードタイプがマークされているサンプルノードセットから、ターゲットノードサブセット及び前記ターゲットノードサブセットに対応するネイバーノードサブセットを取得する前記ステップは、
前記サンプルノードセットから前記ターゲットノードサブセットを取得するステップと、
前記ターゲットノードサブセットに応じて前記サンプルノードセット中の選択対象ネイバーノードの第２候補確率を計算するステップと、
前記選択対象ネイバーノードの前記第２候補確率に応じて前記ネイバーノードサブセットを決定するステップと、を含むことを特徴とする請求項４に記載のモデル訓練方法。
【請求項６】
前記ターゲットノードサブセットに応じて前記サンプルノードセット中の選択対象ネイバーノードの第２候補確率を計算する前記ステップは、
前記ターゲットノードサブセット中の前記ターゲットノードと第ｕ個の前記選択対象ネイバーノードとの間の連結エッジ重み、及び前記ターゲットノードと前記サンプルノードセット中のノードとの連結エッジ重みによって、第ｕ個の前記選択対象ネイバーノードの前記第２候補確率を決定するステップであって、ｕは正の整数であるステップを含むことを特徴とする請求項５に記載のモデル訓練方法。
【請求項７】
前記ネイバーノードサブセットに合わせてノード分類モデルによって前記ターゲットノードサブセットのノード特徴サブセットを抽出する前記ステップは、
前記ノード分類モデルのターゲットモデルパラメータを決定するステップであって、前記ターゲットモデルパラメータは訓練対象のモデルパラメータであるステップと、
前記ターゲットモデルパラメータ及び前記ネイバーノードサブセットに応じて前記ターゲットノードサブセットのノード特徴サブセットを抽出するステップと、を含むことを特徴とする請求項４に記載のモデル訓練方法。
【請求項８】
前記ターゲットモデルパラメータ及び前記ネイバーノードサブセットに応じて前記ターゲットノードサブセットのノード特徴サブセットを抽出する前記ステップは、
第ｉ個の前記ターゲットノードと前記ネイバーノードとの間の連結エッジ重み、前記ネイバーノードの特徴ベクトル及び前記ターゲットモデルパラメータに応じて、第ｉ個の前記ターゲットノードのノード特徴を決定するステップであって、ｉは正の整数であるステップを含むことを特徴とする請求項７に記載のモデル訓練方法。
【請求項９】
前記予測タイプ確率サブセット及び前記ターゲットノードの前記ターゲットノードタイプに応じて前記ノード分類モデルのターゲットモデルパラメータを訓練する前記ステップは、
前記予測タイプ確率サブセット及び前記ターゲットノードの前記ターゲットノードタイプに応じてターゲット損失値を決定するステップと、
前記ターゲット損失値に応じてモデルパラメータ勾配を決定するステップと、
前記モデルパラメータ勾配に応じて前記ターゲットモデルパラメータを訓練するステップと、を含むことを特徴とする請求項４〜８のいずれか一項に記載のモデル訓練方法。
【請求項１０】
前記モデルパラメータ勾配に応じて前記ターゲットモデルパラメータを訓練する前記ステップは、
前記モデルパラメータ勾配と所定の学習率との積を前記ターゲットモデルパラメータの調整差とするステップと、
前記調整差で前記ターゲットモデルパラメータを調整するステップと、を含むことを特徴とする請求項９に記載のモデル訓練方法。
【請求項１１】
コンピュータ機器に適用するノード分類装置であって、
ターゲットノードセット中の分類対象ノードを取得することに用いられ、さらに前記ターゲットノードセットから前記分類対象ノードのネイバーノードセットを取得することに用いられる取得モジュールであって、前記ネイバーノードセットは少なくとも１つのネイバーノードを含み、前記ネイバーノードと前記分類対象ノードは関連付け関係を有する取得モジュールと、
ノード分類モデルによって、前記ネイバーノードセットに応じて前記分類対象ノードのターゲット特徴情報を抽出することに用いられる抽出モジュールと、
前記ターゲット特徴情報に応じて前記分類対象ノードの分類結果を決定することに用いられる決定モジュールであって、前記ノード分類モデルは少なくとも１つのサンプルノードサブセットによって訓練されたモデルであり、前記サンプルノードサブセットはサンプルノードセットのサブセットであり、前記サンプルノードセット中のノードはノードタイプがマークされている決定モジュールと、を備えることを特徴とするノード分類装置。
【請求項１２】
前記取得モジュールはさらに、前記分類対象ノードに応じて前記ターゲットノードセット中の各候補ネイバーノードの第１候補確率を計算し、各前記候補ネイバーノードの前記第１候補確率に応じて前記ネイバーノードセットを決定することに用いられることを特徴とする請求項１１に記載のノード分類装置。
【請求項１３】
前記取得モジュールはさらに、前記分類対象ノードと第ｕ個の前記候補ネイバーノードとの間の連結エッジ重み、及び前記分類対象ノードと前記ターゲットノードセット中のノードとの連結エッジ重みによって、第ｕ個の選択対象ネイバーノードの前記第１候補確率を決定することに用いられ、ｕは正の整数であることを特徴とする請求項１２に記載のノード分類装置。
【請求項１４】
コンピュータ機器に適用するモデル訓練装置であって、
ターゲットノードタイプがマークされているサンプルノードセットから、ターゲットノードサブセット及び前記ターゲットノードサブセットに対応するネイバーノードサブセットを取得することに用いられる取得モジュールであって、前記ネイバーノードサブセット中のネイバーノードと前記ターゲットノードサブセット中のターゲットノードは関連付け関係を有する取得モジュールと、
前記ネイバーノードサブセットに合わせてノード分類モデルによって前記ターゲットノードサブセットのノード特徴サブセットを抽出することに用いられる抽出モジュールであって、前記ノード特徴サブセットは前記ターゲットノードのノード特徴ベクトルを含む抽出モジュールと、
前記ノード特徴サブセットに応じて前記ターゲットノードに対してタイプ予測を行い、予測タイプ確率サブセットを得ることに用いられる予測モジュールと、
前記予測タイプ確率サブセット及び前記ターゲットノードの前記ターゲットノードタイプに応じて前記ノード分類モデルのターゲットモデルパラメータを訓練することに用いられる訓練モジュールと、を備えることを特徴とするモデル訓練装置。
【請求項１５】
前記取得モジュールはさらに、前記サンプルノードセットから前記ターゲットノードサブセットを取得し、前記ターゲットノードサブセットに応じて前記サンプルノードセット中の選択対象ネイバーノードの第２候補確率を計算し、前記選択対象ネイバーノードの前記第２候補確率に応じて前記ネイバーノードサブセットを決定することに用いられることを特徴とする請求項１４に記載のモデル訓練装置。
【請求項１６】
前記取得モジュールはさらに、前記ターゲットノードサブセット中の前記ターゲットノードと第ｕ個の前記選択対象ネイバーノードとの間の連結エッジ重み、及び前記ターゲットノードと前記サンプルノードセット中のノードとの連結エッジ重みによって、第ｕ個の前記選択対象ネイバーノードの前記第２候補確率を決定することに用いられ、ｕは正の整数であることを特徴とする請求項１５に記載のモデル訓練装置。
【請求項１７】
前記抽出モジュールはさらに、前記ノード分類モデルのターゲットモデルパラメータを決定することに用いられ、前記ターゲットモデルパラメータは訓練対象のモデルパラメータであり、前記ターゲットモデルパラメータ及び前記ネイバーノードサブセットに応じて前記ターゲットノードサブセットのノード特徴サブセットを抽出することに用いられることを特徴とする請求項１４に記載のモデル訓練装置。
【請求項１８】
前記抽出モジュールはさらに、第ｉ個の前記ターゲットノードと前記ネイバーノードとの間の連結エッジ重み、前記ネイバーノードの特徴ベクトル及び前記ターゲットモデルパラメータに応じて、第ｉ個の前記ターゲットノードのノード特徴を決定することに用いられ、ｉは正の整数であることを特徴とする請求項１７に記載のモデル訓練装置。
【請求項１９】
前記訓練モジュールはさらに、前記予測タイプ確率サブセット及び前記ターゲットノードの前記ターゲットノードタイプに応じてターゲット損失値を決定し、前記ターゲット損失値に応じてモデルパラメータ勾配を決定し、前記モデルパラメータ勾配に応じて前記ターゲットモデルパラメータを訓練することに用いられることを特徴とする請求項１４〜１８のいずれか一項に記載のモデル訓練装置。
【請求項２０】
前記訓練モジュールはさらに、前記モデルパラメータ勾配と所定の学習率との積を前記ターゲットモデルパラメータの調整差とし、前記調整差で前記ターゲットモデルパラメータを調整することに用いられることを特徴とする請求項１９に記載のモデル訓練装置。
【請求項２１】
コンピュータ機器であって、プロセッサ及びメモリを備え、前記メモリは少なくとも１つの命令、少なくとも１つのプログラム、コードセット又は命令セットを記憶し、前記少なくとも１つの命令、前記少なくとも１つのプログラム、前記コードセット又は命令セットが前記プロセッサによって読み込んで実行されると、請求項１〜３のいずれか一項に記載のノード分類方法又は請求項４〜１０のいずれか一項に記載のモデル訓練方法を実現することを特徴とするコンピュータ機器。
【請求項２２】
コンピュータに請求項１〜３のいずれか一項に記載のノード分類方法又は請求項４〜１０のいずれか一項に記載のモデル訓練方法を実現することを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、２０１８年１１月１５日に提出した出願番号が２０１８１１３６１４０９．０、発明名称が「ノード分類方法、モデル訓練方法及び装置」の中国特許出願の優先権を主張し、その全内容が引用により本願に組み込まれる。
【０００２】
本願はインターネットの技術分野に関し、特にノード分類方法、モデル訓練方法並びに、その装置、機器及びコンピュータプログラムに関する。
【背景技術】
【０００３】
機械学習技術の発展に伴い、ピクチャ分類タスクは目覚ましい進歩を遂げ、関連技術は自動運転、セキュリティ及びゲーム等の多くのシーンに適用されている。ピクチャと同様に、グラフも一般的なデータであり、例えば、ソーシャルネットワーク、ナレッジグラフ及び薬物の分子構造等が挙げられる。
【０００４】
関連技術では、大規模グラフに対して、グラフノード情報を統合するために、専用の反復計算を設定する必要がある。図１に示すように、図１は関連技術におけるグラフノード分類向けのグラフ畳み込みニューラルネットワーク（ｇｒａｐｈ  ｃｏｎｖｏｌｕｔｉｏｎａｌ  ｎｅｔｗｏｒｋｓ、ＧＣＮ）分類モデルの模式図であり、図示するように、ｖはノードであり、ａは２つのノードを連結するエッジであり、入力層の各ノードに対して特徴ベクトルの計算を行うと、グラフ情報全体を更新でき、第１層の情報を得て、ｓｏｆｔｍａｘ関数を用いて第１層の情報中の各ノードに対してノードタイプを予測する。
【０００５】
大規模グラフの場合、数千万ひいては数億のノード数が含まれ、数十億の連結エッジが含まれていることが多い。しかしながら、各ノードの特徴情報を更新するために、ＧＣＮは１回の特徴情報計算では各ノードをトラバーサルする必要があり、その結果、計算コストが高すぎ、計算リソースが過剰に消費されてしまう。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本願の実施例はノード分類方法、モデル訓練方法並びに、その装置、機器及びコンピュータプログラムを提供し、ＧＣＮが１回の特徴情報計算では各ノードをトラバーサルする必要があり、その結果、計算コストが高すぎ、計算リソースが過剰に消費されてしまう問題を解決することができる。
【課題を解決するための手段】
【０００７】
一態様によれば、コンピュータ機器に適用するノード分類方法を提供し、
ターゲットノードセット中の分類対象ノードを取得するステップであって、前記分類対象ノードは前記ターゲットノードセット中の少なくとも１つのノードを含み、且つ前記分類対象ノードの数は前記ターゲットノードセット中のノードの数よりも小さいステップと、
前記ターゲットノードセットから前記分類対象ノードのネイバー（neighbor）ノードセットを取得するステップであって、前記ネイバーノードセットは少なくとも１つのネイバーノードを含み、前記ネイバーノードと前記分類対象ノードは関連付け関係を有するステップと、
ノード分類モデルによって、前記ネイバーノードセットに応じて前記分類対象ノードのターゲット特徴情報を抽出するステップと、
前記ターゲット特徴情報に応じて前記分類対象ノードの分類結果を決定するステップであって、前記ノード分類モデルは少なくとも１つのサンプルノードサブセットによって訓練されたモデルであり、前記サンプルノードサブセットはサンプルノードセットのサブセットであり、前記サンプルノードセット中のノードはノードタイプがマークされているステップと、を含む。
【０００８】
別の態様によれば、コンピュータ機器に適用するモデル訓練方法を提供し、
ターゲットノードタイプがマークされているサンプルノードセットから、ターゲットノードサブセット及び前記ターゲットノードサブセットに対応するネイバーノードサブセットを取得するステップであって、前記ネイバーノードサブセット中のネイバーノードと前記ターゲットノードサブセット中のターゲットノードは関連付け関係を有するステップと、
前記ネイバーノードサブセットに合わせてノード分類モデルによって前記ターゲットノードサブセットのノード特徴サブセットを抽出するステップであって、前記ノード特徴サブセットは前記ターゲットノードのノード特徴ベクトルを含むステップと、
前記ノード特徴サブセットに応じて前記ターゲットノードに対してタイプ予測を行い、予測タイプ確率サブセットを得るステップと、
前記予測タイプ確率サブセット及び前記ターゲットノードの前記ターゲットノードタイプに応じて前記ノード分類モデルのターゲットモデルパラメータを訓練するステップと、を含む。
【０００９】
別の態様によれば、コンピュータ機器に適用するノード分類装置を提供し、
ターゲットノードセット中の分類対象ノードを取得することに用いられる取得モジュールであって、さらに前記ターゲットノードセットから前記分類対象ノードのネイバーノードセットを取得することに用いられ、前記ネイバーノードセットは少なくとも１つのネイバーノードを含み、前記ネイバーノードと前記分類対象ノードは関連付け関係を有する取得モジュールと、
ノード分類モデルによって、前記ネイバーノードセットに応じて前記分類対象ノードのターゲット特徴情報を抽出することに用いられる抽出モジュールと、
前記ターゲット特徴情報に応じて前記分類対象ノードの分類結果を決定することに用いられる決定モジュールであって、前記ノード分類モデルは少なくとも１つのサンプルノードサブセットによって訓練されたモデルであり、前記サンプルノードサブセットはサンプルノードセットのサブセットであり、前記サンプルノードセット中のノードはノードタイプがマークされている決定モジュールと、を備える。
【００１０】
別の態様によれば、コンピュータ機器に適用するモデル訓練装置を提供し、
ターゲットノードタイプがマークされているサンプルノードセットから、ターゲットノードサブセット及び前記ターゲットノードサブセットに対応するネイバーノードサブセットを取得することに用いられる取得モジュールであって、前記ネイバーノードサブセット中のネイバーノードと前記ターゲットノードサブセット中のターゲットノードは関連付け関係を有する取得モジュールと、
前記ネイバーノードサブセットに合わせてノード分類モデルによって前記ターゲットノードサブセットのノード特徴サブセットを抽出することに用いられる抽出モジュールであって、前記ノード特徴サブセットは前記ターゲットノードのノード特徴ベクトルを含む抽出モジュールと、
前記ノード特徴サブセットに応じて前記ターゲットノードに対してタイプ予測を行い、予測タイプ確率サブセットを得ることに用いられる予測モジュールと、
前記予測タイプ確率サブセット及び前記ターゲットノードの前記ターゲットノードタイプに応じて前記ノード分類モデルのターゲットモデルパラメータを訓練することに用いられる訓練モジュールと、を備える。
【００１１】
別の態様によれば、コンピュータ機器を提供し、プロセッサ及びメモリを備え、前記メモリは少なくとも１つの命令、少なくとも１つのプログラム、コードセット又は命令セットを記憶し、前記少なくとも１つの命令、前記少なくとも１つのプログラム、前記コードセット又は命令セットが前記プロセッサによって読み込んで実行されると、上記本願の実施例のいずれかに記載のノード分類方法又はモデル訓練方法を実現する。
【００１２】
別の態様によれば、コンピュータ可読記憶媒体を提供し、前記記憶媒体は少なくとも１つの命令、少なくとも１つのプログラム、コードセット又は命令セットを記憶し、前記少なくとも１つの命令、前記少なくとも１つのプログラム、前記コードセット又は命令セットが前記プロセッサによって読み込んで実行されると、上記本願の実施例のいずれかに記載のノード分類方法又はモデル訓練方法を実現する。
【００１３】
別の態様によれば、コンピュータプログラム製品を提供し、前記コンピュータプログラム製品がコンピュータによって実行されると、コンピュータに如上記本願の実施例のいずれかに記載のノード分類方法又はモデル訓練方法を実行させる。
【発明の効果】
【００１４】
以上の技術的解決手段からわかるように、本願の実施例は次の利点を有する。
【００１５】
本願の実施例では、ノード分類過程においてノードに対して特徴更新を行う際に、ターゲットノードセットから分類対象ノードを選択し、該分類対象ノードのネイバーノードセットに応じて該分類対象ノードのノード特徴を決定し、それによってノード特徴に応じてノード分類結果を取得し、上記のようにして、大規模グラフの場合、毎回グラフ中の一部のノードを反復計算すればよく、グラフ中の各ノードをトラバーサルする必要がなく、計算オーバーヘッドを大幅に削減させるとともに、計算リソースを節約する。
【図面の簡単な説明】
【００１６】
本願の実施例の技術的解決手段をより明確に説明するために、以下、実施例の説明に必要な図面を簡単に説明し、明らかなように、以下説明される図面は単に本願のいくつかの実施例であり、当業者は創造的な努力をせずに、これらの図面に基づいてほかの図面を想到し得る。
【図１】関連技術におけるグラフノード分類向けのグラフ畳み込みニューラルネットワーク分類モデルの模式図である。
【図２】本願の実施例における大規模グラフの模式図である。
【図３】本願の実施例におけるノード分類システムのアーキテクチャ模式図である。
【図４】本願の実施例におけるノード分類方法の実施例の模式図である。
【図５】本願の実施例におけるモデル訓練方法の実施例の模式図である。
【図６】本願の実施例におけるグラフのノードをサンプリングする実施例の模式図である。
【図７】本願の実施例におけるグラフノードに対してモデル訓練を行う模式的なフローチャートである。
【図８】本願の実施例における予測タイプ確率サブセット及びターゲットノードのターゲットノードタイプに応じてノード分類モデルのターゲットモデルパラメータを訓練するフローチャートである。
【図９】本願の実施例におけるグラフノードに対してモデル訓練を行う模式的なフローチャートである。
【図１０】本願の例示的な実施例に係るノード分類装置の構造ブロック図である。
【図１１】本願の例示的な実施例に係るモデル訓練装置の構造ブロック図である。
【図１２】本願の実施例におけるサーバの構造模式図である。
【発明を実施するための形態】
【００１７】
本願の実施例はノード分類方法、モデル訓練方法及び装置を提供し、大規模グラフの場合、一部のノードのみに基づいて訓練を行うことができ、毎回グラフ中の一部のノードを反復計算すればよく、グラフ中の各ノードをトラバーサルする必要がなく、計算オーバーヘッドを大幅に削減させるとともに、計算リソースを節約する。
【００１８】
本願の明細書、特許請求の範囲及び上記図面における用語「第１」、「第２」、「第３」、「第４」等（存在する場合）は類似する対象を区別することに用いられ、特定の順序又は順番を示すものではない。理解されるように、ここで説明される本願の実施例が例えば、ここで図示又は説明される順序以外の順序で実施できるように、このように使用されるデータは適切な場合、相互に交換されてもよい。また、用語「含む」、「有する」及びそれらの任意の変形は、非排他的な包含をカバーすることを意図し、例えば、一連のステップ又はユニットを含むプロセス、方法、システム、製品又は機器は明確にリストされるそれらのステップ又はユニットに限定されず、明確にリストされていない又はこれらのプロセス、方法、製品又は機器に固有のほかのステップ又はユニットを含んでもよい。
【００１９】
理解されるように、本願の実施例は主に大規模グラフに適用され、大規模グラフノード向けの分類及び学習を行うことができる。グラフとは、多くのノードを相互に連結して形成されるデータ構造であり、図２に示すように、図２は本願の実施例における大規模グラフの模式図であり、図示するように、各ノードは１つのメンバーを示し、２つのノード間の連結線は連結エッジと呼ばれ、該連結エッジは連結される２つのノードに対応する２つのメンバーが互いに知っていることを示すことに用いられ、Ａ１で指示されるメンバーは同一のクラスに属し、Ａ２で指示されるメンバーは同一のクラスに属し、Ａ３で指示されるメンバーは同一のクラスに属し、Ａ４で指示されるメンバーは同一のクラスに属する。
【００２０】
選択可能に、ノードは通常、人又は組織を指し、ノード間の連結（エッジ）は、多くの場合、特定の社会的関係（例えば、親族関係や取引行為等）を示す。ノードごとに、１つの特徴ベクトルが付与されてもよく、例えば、
2021533474.tif 000003
ノードの特徴ベクトルは
2021533474.tif 000004
であり、該ノードの属性を記述することに用いられる。各エッジは重み値
2021533474.tif 000005
を有してもよく、連結の緊密さを記述することに用いられ、重み値
2021533474.tif 000006
が大きいほど、ノード間が緊密に関連付けられることを示す。各エッジは向きを有してもよく、連結の方向性を示すことに用いられる。選択可能に、本願の実施例におけるグラフの連結エッジは方向性を限定しない。
【００２１】
実際の応用では、ユーザー推薦、友達分類及びネットワークセキュリティシステムの監視等の機能を実現するために、さらにグラフ中のノード間の分類を行う必要がある。即ち、ノードの特徴ベクトル及びノード間の連結関係に応じて、類似するノードを同一タイプに分けるタスクはグラフノード分類と呼ばれ、即ち、ノード
2021533474.tif 000007
をタイプ
2021533474.tif 000008
に分ける。例えば、ソーシャル類アプリケーションプログラム（大規模なグラフ）では、ユーザー画像及びユーザーの友達関係に応じて、ユーザーを、例えば、バスケットボール愛好者、サッカー愛好者又はバレーボール愛好者等の様々なスポーツの愛好者に分けることができる。
【００２２】
理解できるように、本願は適用範囲が広く、上記いくつかのシーンに加えて、支払いネットワークにおける不正ユーザー（例えば、マルチや賭博等）の捕獲（捕捉）に適用されてもよく、友達分類、関係マイニング及び商品推薦等のシーンに適用されてもよく、ここでは限定しない。
【００２３】
理解されるように、本願の実施例で説明されるノード分類システムは図３に示され、図３は本願の実施例におけるノード分類システムのアーキテクチャ模式図であり、ノード分類方法及びモデル訓練方法はいずれもサーバ３１０に配置されており、サーバ３１０は大量の端末機器３２０から送信される情報を受信し、１つの端末機器３２０が１つのユーザーに対応するとすると、各ユーザーは１つのノードを示し、該ユーザーの情報（例えば、ソーシャル情報）はノード情報を示す。サーバは大量のノードに対応するノード情報を収集して１つの大規模グラフを形成する。理解できるように、図３に示されるサーバ３１０は１台のサーバであってもよく、複数のサーバを集積したシステムであってもよい。端末機器３２０はスマートフォン、タブレットコンピュータ、パーソナルコンピュータ（ｐｅｒｓｏｎａｌ  ｃｏｍｐｕｔｅｒ、ＰＣ）、ノートブックコンピュータ及びパームトップコンピュータを含むが、これらに限定されず、ここでは単に例示的なものであり、本願を限定しないと理解すべきである。
【００２４】
上記説明と組み合わせて、本願におけるノード分類方法を説明し、図４に示すように、本願の例示的な実施例に係るノード分類方法のフローチャートであり、該方法が図３に示されるサーバ３１０に適用されることを例として説明し、該方法は、ステップ１０１〜１０４を含む。
【００２５】
ステップ１０１では、ターゲットノードセット中の分類対象ノードを取得する。
【００２６】
選択可能に、該分類対象ノードはターゲットノードセット中の少なくとも１つのノードを含み、且つ分類対象ノードの数はターゲットノードセット中のノードの数よりも小さい。
【００２７】
選択可能に、ターゲットノードセットからノードの一部を分類対象ノードとして選択する。
【００２８】
本実施例では、サーバは、まず、分類対象のノードを取得する必要があり、１つのノードはグラフ中の１つのユーザーに対応し、従って、該分類対象ノードは分類を必要とするターゲットユーザーとみなされてもよい。
【００２９】
ステップ１０２では、ターゲットノードセットから分類対象ノードのネイバーノードセットを取得し、ネイバーノードセットは少なくとも１つのネイバーノードを含み、ネイバーノードと分類対象ノードは関連付け関係を有する。
【００３０】
本実施例では、サーバが分類対象ノードを取得した後、該分類対象ノードに応じて、それに関連付けられる少なくとも１つのネイバーノードを取得でき、これらのネイバーノードは１つのネイバーノードセットを形成する。分類対象ノードがターゲットユーザーであることを例として、該ターゲットユーザーに関連付けられるネイバーノードは通常、該ターゲットユーザーの友達であってもよい。
【００３１】
理解できるように、ネイバーノードは、分類対象ノードと直接関連付けを有する（即ち、分類対象ノードとネイバーノードがエッジを有する）ノードに加えて、分類対象ノードと間接関連付けを有するノードであってもよく、ここでは限定しない。
【００３２】
選択可能に、該分類対象ノードのネイバーノードセット中のネイバーノードは、少なくとも２つの分類対象ノードと関連付け関係を有するノード、又は、ｎ個の分類対象ノードと関連付け関係を有するノードであり、ｎは正の整数である。
【００３３】
選択可能に、ネイバーノードセットを決定する際に、まず、分類対象ノードに応じて、ターゲットノードセット中の各候補ネイバーノードの第１候補確率を計算し、各候補ネイバーノードの第１候補確率に応じてネイバーノードセットを決定する。分類対象ノードと第ｕ個の候補ネイバーノードとの間の連結エッジ重み、及び分類対象ノードとターゲットノードセット中のノードとの連結エッジ重みによって、第ｕ個の候補ネイバーノードの第１候補確率を決定し、ｕは正の整数である。
【００３４】
選択可能に、該候補ネイバーノードの第１候補確率の計算方式は以下の式１を参照する。
【００３５】
【数１】
2021533474.tif 000009
ただし、
2021533474.tif 000010
は第
2021533474.tif 000011
個の候補ネイバーノードの第１候補確率、
2021533474.tif 000012
はターゲットノードセット中の第
2021533474.tif 000013
個のノード、
2021533474.tif 000014
は分類対象ノード、
2021533474.tif 000015
は分類対象ノードのノード数、
2021533474.tif 000016
はターゲットノードセットのノード数、
2021533474.tif 000017
は１〜
2021533474.tif 000018
の整数、
2021533474.tif 000019
は１〜
2021533474.tif 000020
の整数、
2021533474.tif 000021
は第
2021533474.tif 000022
個の分類対象ノードと第
2021533474.tif 000023
個の候補ネイバーノードとの間の連結エッジ重み、
2021533474.tif 000024
は第
2021533474.tif 000025
個の分類対象ノードとターゲットノードセット中の第
2021533474.tif 000026
個のノードとの間の連結エッジ重みを示す。
【００３６】
本実施例では、まず、大規模グラフに対応するターゲットノードセットから分類対象ノードを取得し、その後、毎回該部分の分類対象ノードのみを更新すると同時に、この部分の分類対象ノードに応じて特定数の共通関連付けノード（即ち、ネイバーノードセット）を収集して情報統合を行う。
【００３７】
分類対象ノードがターゲットユーザーであることを例として、該ターゲットユーザーに関連付けられるネイバーノードは通常、該ターゲットユーザーの友達であってもよい。理解できるように、ネイバーノードは、分類対象ノードと直接関連付けを有する（即ち、分類対象ノードとネイバーノードが連結エッジを有する）ノードに加えて、ターゲットノードと間接関連付けを有するノードであってもよく、ここでは限定しない。
【００３８】
ステップ１０３では、ノード分類モデルによって、ネイバーノードセットに応じて分類対象ノードのターゲット特徴情報を抽出する。
【００３９】
本実施例では、サーバはネイバーノードセットによって分類対象ノードの特徴を強化してもよく、それによって該分類対象ノードに対応するターゲット特徴情報を得る。
【００４０】
具体的には、以下の式２を用いて分類対象ノードのターゲット特徴情報を得ることができる。
【００４１】
【数２】
2021533474.tif 000027
ただし、
2021533474.tif 000028
は分類対象ノード、
2021533474.tif 000029
は分類対象ノードのターゲット特徴情報（即ち、特徴ベクトル）、
2021533474.tif 000030
はネイバーノードセット中のノード数、
2021533474.tif 000031
は１〜
2021533474.tif 000032
の整数、
2021533474.tif 000033
は第ｎ個のネイバーノード、
2021533474.tif 000034
は第ｎ個のネイバーノードの多次元特徴ベクトル、
2021533474.tif 000035
は分類対象ノードと第ｎ個のネイバーノードとの連結エッジ重み、
2021533474.tif 000036
はノード分類モデルのモデルパラメータを示す。
【００４２】
以上からわかるように、分類対象ノードのターゲット特徴情報を更新するために、該分類対象ノードに対応するネイバーノードを１つのモデルパラメータと乗算し、さらに合計してターゲット特徴情報を得て、それによって更新後のターゲット特徴情報はそのすべてのネイバーノードの特徴を統合し、且つ情報量を豊か（enrich）にする。
【００４３】
ステップ１０４では、ターゲット特徴情報に応じて分類対象ノードの分類結果を決定し、ノード分類モデルは少なくとも１つのサンプルノードサブセットに応じて訓練されたモデルであり、該サンプルノードサブセットはサンプルノードセットのサブセットであり、サンプルノードセット中のノードはノードタイプがマークされている。
【００４４】
本実施例では、ノード分類モデルがターゲット特徴情報を計算した後、該ターゲット特徴情報に応じて、該分類対象ノードに対応する分類結果を出力し、例えば、出力される分類結果は分類対象ノードが異常ノードに属することであり、又は、出力される分類結果は分類対象ノードがバスケットボール愛好者ノードに属することである。
【００４５】
ノード分類モデルは少なくとも１つのサンプルノードサブセットに応じて訓練されたものであり、各サンプルノードサブセットのノード数はサンプルノードセットのノード数よりも小さく、つまり、ノード分類モデルはノードの一部に基づいて訓練され、毎回ノードの一部を反復計算し、反復回数が閾値に達するまで繰り返す。機械学習では、分類モデルとは、入力データに対して特定の情報統合を行った後、対応するタイプを出力するものである。分類モデルは１組のモデルパラメータを含み、これらのモデルパラメータは訓練によって最適化調整することができる。
【００４６】
なお、実際の応用では、機械学習方法は、多くの場合、複数回の反復によって各ノードのモデルパラメータを更新する必要があり、毎回、反復はターゲットノードセットからサンプリングされる分類対象ノードのみを対象として行われる。毎回、反復がごく一部のデータのみを使用するが、複数回の反復を経て（毎回反復してサンプリングされる分類対象ノードは異なる）、ターゲットノードセット中のすべてのノードをトラバーサルすることができる。
【００４７】
本願の実施例では、ノード分類方法を提供し、ノード分類過程においてノードに対して特徴更新を行う際に、ターゲットノードセットから分類対象ノードを選択し、該分類対象ノードのネイバーノードセットに応じて該分類対象ノードのノード特徴を決定し、それによってノード特徴に応じてノード分類結果を取得し、上記のようにして、大規模グラフの場合、毎回グラフ中の一部のノードを反復計算すればよく、グラフ中の各ノードをトラバーサルする必要がなく、計算オーバーヘッドを大幅に削減させるとともに、計算リソースを節約する。
【００４８】
上記ノード分類モデルについて、該ノード分類モデルの訓練プロセスを説明し、図５は本願の例示的な実施例に係るモデル訓練方法のフローチャートであり、該方法が図３に示されるサーバ３１０に適用されることを例として説明し、図５に示すように、該方法はステップ２０１〜２０４を含む。
【００４９】
ステップ２０１では、ターゲットノードタイプがマークされているサンプルノードセットから、ターゲットノードサブセット及びターゲットノードサブセットに対応するネイバーノードサブセットを取得し、ネイバーノードサブセット中のネイバーノードとターゲットノードサブセット中のターゲットノードは関連付け関係を有する。
【００５０】
本実施例では、まず、大規模グラフに対応するサンプルノードセットからサンプルノードセットを取得し、その後、毎回ノードの一部（即ち、ターゲットノードサブセット）のみを更新すると同時に、この部分のノード（ターゲットノードサブセット）応じて特定数の共通関連付けノード（即ち、ネイバーノードサブセット）を収集して情報統合を行う。
【００５１】
理解の便宜上、図６に示すように、図６は本願の実施例におけるグラフのノードをサンプリングする実施例の模式図であり、図示するように、サンプルノードセットから１０個のノードを含むサンプルノードサブセットを取得し、サンプルノードサブセットは２個のターゲットノード（即ち、図中のノードＭ及びノードＮ）を含み、ターゲットノードに応じて、それに関連付けられる８個のネイバーノード（即ち、図中の水玉模様付きノード）を取得し、図６中の白色ノードはサンプルノードセット中のノードに属するが、今回の訓練の対象として選択されていない。
【００５２】
ターゲットノードがターゲットユーザーであることを例として、該ターゲットユーザーに関連付けられるネイバーノードは通常、該ターゲットユーザーの友達であってもよい。理解できるように、ネイバーノードは、ターゲットノードと直接関連付けを有する（即ち、ターゲットノードとネイバーノードがエッジを有する）ノードに加えて、ターゲットノードと間接関連付けを有するノードであってもよく、ここでは限定しない。
【００５３】
選択可能に、このターゲットノードサブセット及びネイバーノードサブセットを取得する方式は、サンプルノードセットからターゲットノードサブセットを取得し、ターゲットノードサブセットに応じてサンプルノードセット中の各候補ネイバーノードの第２候補確率を計算するステップと、選択対象ネイバーノードの第２候補確率に応じてネイバーノードサブセットを決定するステップと、を含む。ターゲットノードサブセット中のターゲットノードと第ｕ個の選択対象ネイバーノードとの間の連結エッジ重み、及びターゲットノードとサンプルノードセット中のノードとの連結エッジ重みによって、第ｕ個の選択対象ネイバーノードの第２候補確率を決定し、ｕは正の整数である。選択可能に、該選択対象ネイバーノードの選択方式は、上記ステップ１０２で示される式１を参照すればよく、本実施例では重複説明を省略する。
【００５４】
選択可能に、ターゲットノードに関連付けられるノードは多い可能性があり、このとき、ターゲットノードサブセットに応じてサンプルノードセット中の各選択対象ネイバーノードの確率を計算し、その後、確率が大きい選択対象ネイバーノードをネイバーノードサブセットとして選択する必要がある。
【００５５】
なお、訓練するごとに、選択されるターゲットノードは重複しないが、選択されるネイバーノードは重複する可能性がある。ターゲットノードをサンプリングする際に、ランダムに選択され、極端な条件では、サンプリングされるターゲットノードの共有ネイバーが非常に少なく、このとき、非共有ネイバーノードをネイバーノードとしてもよい。
【００５６】
ステップ２０２では、ネイバーノードサブセットに合わせて、ノード分類モデルによってターゲットノードサブセットのノード特徴サブセットを抽出し、ノード特徴サブセットはターゲットノードのノード特徴ベクトルを含む。
【００５７】
本実施例では、サーバはターゲットノードサブセット及びネイバーノードサブセットに応じて、ネイバーノードサブセットを利用してターゲットノードサブセット中の各ターゲットノードの特徴を更新し、各ターゲットノードは１つのノード特徴ベクトルに対応し、この場合、各ターゲットノードのノード特徴ベクトルはノード特徴サブセットを形成する。
【００５８】
ステップ２０３では、ノード特徴サブセットに応じてターゲットノードに対してタイプ予測を行い、予測タイプ確率サブセットを得る。
【００５９】
本実施例では、サーバはターゲットノードサブセット及びノード特徴サブセットを取得した後、各ターゲットノード及びそれに対応するノード特徴ベクトルに応じて、各ターゲットノードの予測タイプ確率を計算し、各ターゲットノードの予測タイプ確率は１つの予測タイプ確率サブセットを形成する。
【００６０】
予測タイプ確率はターゲットノードが特定のタイプであると予測される確率を示すことに用いられ、従って、予測時、通常、確率が最も大きいタイプを該ターゲットノードのタイプとして選択する。
【００６１】
ステップ２０４では、予測タイプ確率サブセット及びターゲットノードのターゲットノードタイプに応じて、ノード分類モデルのターゲットモデルパラメータを訓練する。
【００６２】
本実施例では、サーバは予測タイプ確率サブセットとターゲットノードタイプとの差に応じて、該ノード分類モデルのターゲットモデルパラメータを調整する。
【００６３】
該ターゲットモデルパラメータは、初期化値、つまり予め定義された１つのパラメータに対応してもよく、又は、該ターゲットモデルパラメータは前回サンプリングされたノードから計算されるモデルパラメータであってもよい。ここでは、各ターゲットノードの予測タイプ確率を利用して第１ターゲットモデルパラメータを最適化し、それによって実際のモデルにさらに近いターゲットモデルパラメータを取得することに相当する。
【００６４】
本実施例では、最後に、サーバは今回訓練された第２モデルパラメータを利用して訓練してノード分類モデルを得る。
【００６５】
なお、実際の応用では、機械学習方法は、多くの場合、複数回の反復によってモデルパラメータを訓練する必要があり、毎回、反復はサンプリングされる小さいノードセットのみを使用する。毎回、反復がごく一部のデータのみを使用するが、複数回の反復を経て（毎回反復用のデータは異なり、即ち、毎回反復訓練用のサンプリングされるターゲットノードは異なり、ネイバーノードも完全に同じではない）、グラフ中のすべてのノードをトラバーサルすることができる。
【００６６】
本願の実施例では、大規模グラフに基づくモデル訓練方法を提供し、まず、サーバはサンプルノードセットからサンプルノードサブセットを取得し、その後、サンプルノードサブセットに応じてノード特性ベクトルサブセットを決定し、サーバはさらにターゲットノードサブセット及びノード特性ベクトルサブセットに応じて予測タイプ確率サブセットを決定し、予測タイプ確率サブセットは少なくとも１つの予測タイプ確率を含み、予測タイプ確率とターゲットノードは対応付け関係を有し、最後に、予測タイプ確率サブセット及び第１モデルパラメータに応じて第２モデルパラメータを決定し、第２モデルパラメータに応じて訓練してノード分類モデルを得る。上記のようにして、大規模グラフの場合、一部のノードのみに基づいて訓練を行うことができ、毎回グラフ中の一部のノードを反復計算すればよく、グラフ中の各ノードをトラバーサルする必要がなく、計算オーバーヘッドを大幅に削減させるとともに、計算リソースを節約する。
【００６７】
選択可能に、上記図５に対応する実施例をもとに、本願の実施例に係るモデル訓練方法の選択可能な実施例では、ネイバーノードサブセットに合わせて、ノード分類モデルによってターゲットノードサブセットのノード特徴サブセットを抽出し、即ち、上記ステップ２０２は以下のステップ２０２１〜ステップ２０２２をさらに含んでもよく、図７に示される。
【００６８】
ステップ２０２１では、ノード分類モデルのターゲットモデルパラメータを決定し、該ターゲットモデルパラメータは訓練対象のモデルパラメータである。
【００６９】
ステップ２０２２では、ターゲットモデルパラメータ及びネイバーノードサブセットに応じて、ターゲットノードサブセットのノード特徴サブセットを抽出する。
【００７０】
選択可能に、ターゲットモデルパラメータ及びネイバーノードサブセットに応じてノード特徴サブセットを計算する時、第ｉ個のターゲットノードに対して、該第ｉ個のターゲットノードとネイバーノードとの間の連結エッジ重み、ネイバーノードの特徴ベクトル及びターゲットモデルパラメータに応じて、第ｉ個のターゲットノードのノード特徴を決定し、ｉは正の整数であり、例示的には、該計算プロセスは式３を参照する。
【００７１】
【数３】
2021533474.tif 000037
ただし、
2021533474.tif 000038
は第
2021533474.tif 000039
個のターゲットノード、
2021533474.tif 000040
は第
2021533474.tif 000041
個のターゲットノードのノード特徴、
2021533474.tif 000042
はターゲットノードサブセットのノード数、
2021533474.tif 000043
は１〜
2021533474.tif 000044
の整数、
2021533474.tif 000045
は第
2021533474.tif 000046
個のネイバーノード、
2021533474.tif 000047
は第
2021533474.tif 000048
個のネイバーノードの特徴ベクトル、
2021533474.tif 000049
は第
2021533474.tif 000050
個のターゲットノードと第
2021533474.tif 000051
個のネイバーノードとの連結エッジ重み、
2021533474.tif 000052
はターゲットモデルパラメータを示す。
【００７２】
選択可能に、上記図５に対応する実施例をもとに、本願の実施例に係るモデル訓練方法の選択可能な実施例では、予測タイプ確率サブセット及びターゲットノードのターゲットノードタイプに応じてノード分類モデルのターゲットモデルパラメータを訓練し、即ち、上記ステップ２０４は以下のステップ２０４１〜ステップ２０４３をさらに含んでもよく、図８に示される。
【００７３】
ステップ２０４１では、予測タイプ確率サブセット及びターゲットノードのターゲットノードタイプに応じてターゲット損失値を決定する。
【００７４】
選択可能に、該ターゲット損失値は損失関数又はコスト関数によって計算された数値であり、損失関数又はコスト関数はいずれも予測誤差の程度を測定することができる。つまり、１つのアルゴリズムが良好なアルゴリズムであるか否かを評価するには、１つの損失関数を予め定義する必要があり、それによってこのアルゴリズムが最適であるか否かを判断し、後続では連続的に最適化して勾配降下を求め、損失関数を最小化する。
【００７５】
選択可能に、該ターゲット損失値の計算方式は以下の式４を参照する。
【００７６】
【数４】
2021533474.tif 000053
ただし、
2021533474.tif 000054
はターゲット損失値、
2021533474.tif 000055
はターゲットノードサブセットのノード数、
2021533474.tif 000056
は１〜
2021533474.tif 000057
の整数、
2021533474.tif 000058
は第
2021533474.tif 000059
個のターゲットノード、
2021533474.tif 000060
は第
2021533474.tif 000061
個のターゲットノードの
2021533474.tif 000062
次元特徴ベクトル、
2021533474.tif 000063
は第
2021533474.tif 000064
個のターゲットノードの第
2021533474.tif 000065
次元特徴ベクトル、
2021533474.tif 000066
は指数関数、
2021533474.tif 000067
は
2021533474.tif 000068
の第
2021533474.tif 000069
個の成分、
2021533474.tif 000070
は第
2021533474.tif 000071
個のターゲットノードの実際タイプ情報、
2021533474.tif 000072
は第
2021533474.tif 000073
個のターゲットノードの第
2021533474.tif 000074
個の予測タイプ確率が実際タイプ情報に等しい確率を示す。
【００７７】
選択可能に、第ｉ個のターゲットノードの予測タイプ確率の計算方式は以下の式５を参照する。
【００７８】
【数５】
2021533474.tif 000075
選択可能に、予測時、最大確率に対応するタイプを該ターゲットノードのタイプとして選択し、即ち、
【００７９】
【数６】
2021533474.tif 000076
であり、
ただし、
2021533474.tif 000077
は第
2021533474.tif 000078
個のターゲットノードの予測タイプを示す。
【００８０】
ステップ２０４２では、ターゲット損失値に応じてモデルパラメータ勾配を決定する。
【００８１】
選択可能に、該モデルパラメータ勾配の計算方式は以下の式６を参照する。
【００８２】
【数７】
2021533474.tif 000079
ただし、
2021533474.tif 000080
はモデルパラメータ勾配を示し、各
2021533474.tif 000081
の計算方式は以下の式７を参照する。
【００８３】
【数８】
2021533474.tif 000082
ただし、
2021533474.tif 000083
はターゲット損失、
2021533474.tif 000084
は第
2021533474.tif 000085
次元特徴ベクトルの勾配、
2021533474.tif 000086
は第
2021533474.tif 000087
個のターゲットノードの特徴ベクトルの次元数、
2021533474.tif 000088
はターゲットノードサブセットのノード数、
2021533474.tif 000089
は１〜
2021533474.tif 000090
の整数、
2021533474.tif 000091
は１〜
2021533474.tif 000092
の整数、
2021533474.tif 000093
は第
2021533474.tif 000094
個のターゲットノードの第
2021533474.tif 000095
次元特徴ベクトル、
2021533474.tif 000096
は第
2021533474.tif 000097
個のターゲットノードの実際タイプ情報、
2021533474.tif 000098
は判断関数、
2021533474.tif 000099
は第
2021533474.tif 000100
個のネイバーノード、
2021533474.tif 000101
は第
2021533474.tif 000102
個のネイバーノードの特徴ベクトル、
2021533474.tif 000103
は指数関数を示す。
【００８４】
選択可能に、該モデルパラメータ勾配の導出プロセスは以下の通りである。
【００８５】
【数９】
2021533474.tif 000104
ステップ２０４３では、モデルパラメータ勾配に応じてターゲットモデルパラメータを訓練する。
【００８６】
選択可能に、モデルパラメータ勾配と所定の学習率との積を、ターゲットモデルパラメータの調整差として、該調整差でターゲットモデルパラメータを調整する。
【００８７】
選択可能に、該ターゲットモデルパラメータの調整方式は以下の式８を参照する。
【００８８】
【数１０】
2021533474.tif 000105
ただし、
2021533474.tif 000106
は調整後のターゲットモデルパラメータ、
2021533474.tif 000107
は調整前のモデルパラメータ、
2021533474.tif 000108
は所定の学習率、
2021533474.tif 000109
はモデルパラメータ勾配を示す。
【００８９】
選択可能に、モデル訓練過程では、通常、訓練の回数に応じて、動的に変化する学習率を設定でき、例えば、最初に、モデル訓練を行う時、学習率を０．０１〜０．００１に制御し、所定の回数だけ反復すると、学習率が徐々に減衰し、訓練終了直前、学習率の減衰が通常１００倍以上になる。
【００９０】
学習率は主にモデルの学習進度を制御することに用いられ、データセットのサイズに応じて適切な学習率を選択でき、二乗誤差を使用する場合及びコスト関数とする場合、データ量の増加に伴い、学習率は適宜より小さい値に設定されるべきである。
【００９１】
異なる反復では異なる学習率を選択し、最初の反復では、学習率はやや大きく、終了直前、学習率はやや小さい。毎回反復後、推定されるモデルパラメータを使用して誤差関数の値を確認し、前回の反復に比べてエラー率が減少すると、学習率を大きくし、前回の反復に比べて、エラー率が増加すると、前回の反復の値を再設定すべきであり、且つ学習率をこの前の５０％まで小さくする。従って、これは学習率の適応調整の方法である。
【００９２】
なお、本実施例における学習率
2021533474.tif 000110
は０．０１に設定されてもよく、実際の応用では、学習率
2021533474.tif 000111
はさらに０．００００１、０．０００１、０．００１、０．００３、０．０３、０．１、０．３、１、３又は１０等に設定されてもよく、ここでは限定しない。
【００９３】
選択可能に、本願の実施例では、ターゲットモデルパラメータを訓練する方法を提供し、即ち、サーバは予測タイプ確率サブセット及び実際タイプ情報サブセットに応じてターゲット損失を計算し、その後、ターゲット損失に応じてモデルパラメータ勾配を決定し、最後に、モデルパラメータ勾配に合わせてモデルパラメータを調整する。上記のようにして、確率的勾配降下を採用して各サンプルによってパラメータを１回反復更新し、サンプル全体をトラバーサルせずに最適解を見つけることができ、それによってアルゴリズムの収束速度を大幅に向上させ、また、各サンプルの損失関数を最小化し、毎回の反復結果は必ずしもグローバル最適解ではないが、常にこの方向に展開されるため、最終結果は常にグローバル最適解に近い。
【００９４】
説明の便宜上、図９に示すように、図９は本願の実施例におけるグラフノードに対してモデル訓練を行う模式的なフローチャートであり、図示するように、具体的にはステップＳ１〜Ｓ１３を含む。
【００９５】
ステップＳ１では、モデル訓練のプロセスを開始する。
【００９６】
ステップＳ２では、反復カウンタｔ＝１とし、サンプリングされるノード数ｂ＝１２８を設定し、反復カウンタはプログラムが何回反復されるかを記録し、ｔ＝１の場合、プログラムは第１回の反復を開始し、即ち、ステップＳ２〜ステップＳ１０を実行し、その後、反復回数を１増やし、反復カウンタによって記録される反復回数が１０６に達するか否かを判断し、ＮＯであると、さらに第２回の反復を行う。
【００９７】
ステップＳ３では、反復カウンタによって記録される反復回数が１０６よりも大きいか否かを判断し、反復回数が１０６よりも大きいと、ステップＳ１２に進み、一方、反復回数が１０６以下であると、ステップＳ４に進み、即ち、１回の反復計算を開始する。
【００９８】
ステップＳ４では、サンプルノードセットから１２８個のターゲットノードをサンプリングし、即ち
2021533474.tif 000112
である。
【００９９】
ステップＳ５では、上記式１を利用して１２８個のネイバーノード
2021533474.tif 000113
を収集する。
【０１００】
ステップＳ６では、上記式３を利用して１２８個のターゲットノードの特徴ベクトル
2021533474.tif 000114
を収集する。
【０１０１】
ステップＳ７では、上記式５を利用してターゲットノードの予測タイプ
2021533474.tif 000115
を得る。
【０１０２】
ステップＳ８では、交差エントロピーに応じて予測タイプと実際タイプの損失値を比較する。
【０１０３】
ステップＳ９では、上記式７を利用してモデルパラメータの勾配を計算する。
【０１０４】
ステップＳ１０では、上記式８を利用してモデルパラメータを更新する。
【０１０５】
ステップＳ１１では、反復カウンタの値を１増やし、即ち、ｔ＝ｔ＋１である。
【０１０６】
ステップＳ１２では、ｔが１０６よりも大きいことを満たすと、モデルパラメータを出力する。
【０１０７】
ステップＳ１３では、モデル訓練のプロセスが終了する。
【０１０８】
本願に係るモデル訓練方法に基づいて、実際のソーシャルネットワークに対して試験を行ったが、該ネットワークは合計で３１９６５個のノード及び１１６０６９１９本のエッジを有し、各ノードの特徴次元数は６０２であり、該ネットワークはタイプ数が合計で４１である。２つのノード間に連結エッジを有する場合、重みを１とし、一方、２つのノード間に連結エッジがない場合、重みを０とする。モデル訓練を実現するために、ノード数が１５２４１０の訓練セットを構築し、訓練セット中のノードタイプは既知である。
【０１０９】
また、さらにノード数が５５３３４のテストセットを構築し、分類モデルの予測精度をテストすることに用いられる。現在、予測精度を採用して分類モデルの予測能力を評価する。
【０１１０】
【数１１】
2021533474.tif 000116
ただし、
2021533474.tif 000117
はテストセット中のタイプ予測が正確なノード数を示し、
2021533474.tif 000118
は予測能力を示し、
2021533474.tif 000119
が大きいほど、予測能力が高い。また、さらにモデルの毎回の訓練時間を比較することによって実行速度を評価してもよい。
【０１１１】
次に、本願の実施例で採用される方法を、従来の解決手段で採用されるＧＣＮと比較し、表１に示すように、同様な実験条件における比較は以下の通りである。
【０１１２】
【表１】
2021533474.tif 000120
以上からわかるように、本願の実施例で採用される方法に対応する予測精度はＧＣＮに非常に近いが、実行時間が大幅に減少した。従って、サンプリングに基づく仮定アルゴリズムによって、毎回のノード特徴の更新を小さいノードサブセットで行うだけでよく、実際実行速度を大幅に向上させ、メモリを削減させる。実際のソーシャルネットワークデータにおいて、得られる予測精度がＧＣＮに近いが、速度が約５０倍向上した。
【０１１３】
図１０は本願の例示的な実施例に係るノード分類装置の構造ブロック図であり、該装置がコンピュータ機器に適用されることを例として、図１０に示すように、該装置は、取得モジュール１０１０、抽出モジュール１０２０及び決定モジュール１０３０を備え、
取得モジュール１０１０は、ターゲットノードセット中の分類対象ノードを取得することに用いられ、
前記取得モジュール１０１０はさらに、前記ターゲットノードセットから前記分類対象ノードのネイバーノードセットを取得することに用いられ、前記ネイバーノードセットは少なくとも１つのネイバーノードを含み、前記ネイバーノードと前記分類対象ノードは関連付け関係を有し、
抽出モジュール１０２０は、ノード分類モデルによって、前記ネイバーノードセットに応じて前記分類対象ノードのターゲット特徴情報を抽出することに用いられ、
決定モジュール１０３０は、前記ターゲット特徴情報に応じて前記分類対象ノードの分類結果を決定することに用いられ、前記ノード分類モデルは少なくとも１つのサンプルノードサブセットによって訓練されたモデルであり、前記サンプルノードサブセットはサンプルノードセットのサブセットであり、前記サンプルノードセット中のノードはノードタイプがマークされている。
【０１１４】
選択可能な実施例では、前記取得モジュール１０１０はさらに、前記分類対象ノードに応じて前記ターゲットノードセット中の各候補ネイバーノードの第１候補確率を計算し、各前記候補ネイバーノードの前記第１候補確率に応じて前記ネイバーノードセットを決定することに用いられる。
【０１１５】
選択可能な実施例では、前記取得モジュール１０１０はさらに、前記分類対象ノードと第ｕ個の前記候補ネイバーノードとの間の連結エッジ重み、及び前記分類対象ノードと前記ターゲットノードセット中のノードとの連結エッジ重みによって、第ｕ個の前記選択対象ネイバーノードの前記第１候補確率を決定することに用いられ、ｕは正の整数である。
【０１１６】
以上のように、本実施例に係るノード分類装置は、ノード分類過程においてノードに対して特徴更新を行う際に、ターゲットノードセットから分類対象ノードを選択し、該分類対象ノードのネイバーノードセットに応じて該分類対象ノードのノード特徴を決定し、それによってノード特徴に応じてノード分類結果を取得し、上記のようにして、大規模グラフの場合、毎回グラフ中の一部のノードを反復計算すればよく、グラフ中の各ノードをトラバーサルする必要がなく、計算オーバーヘッドを大幅に削減させるとともに、計算リソースを節約する。
【０１１７】
図１１は本願の例示的な実施例に係るモデル訓練装置の構造ブロック図であり、該装置がコンピュータ機器に適用されることを例として、図１１に示すように、該装置は、取得モジュール１１１０、抽出モジュール１１２０、予測モジュール１１３０及び訓練モジュール１１４０を備え、
取得モジュール１１１０は、ターゲットノードタイプがマークされているサンプルノードセットから、ターゲットノードサブセット及び前記ターゲットノードサブセットに対応するネイバーノードサブセットを取得することに用いられ、前記ネイバーノードサブセット中のネイバーノードと前記ターゲットノードサブセット中のターゲットノードは関連付け関係を有し、
抽出モジュール１１２０は、前記ネイバーノードサブセットに合わせてノード分類モデルによって前記ターゲットノードサブセットのノード特徴サブセットを抽出することに用いられ、前記ノード特徴サブセットは前記ターゲットノードのノード特徴ベクトルを含み、
予測モジュール１１３０は、前記ノード特徴サブセットに応じて前記ターゲットノードに対してタイプ予測を行い、予測タイプ確率サブセットを得ることに用いられ、
訓練モジュール１１４０は、前記予測タイプ確率サブセット及び前記ターゲットノードの前記ターゲットノードタイプに応じて前記ノード分類モデルのターゲットモデルパラメータを訓練することに用いられる。
【０１１８】
選択可能な実施例では、前記取得モジュール１１１０はさらに、前記サンプルノードセットから前記ターゲットノードサブセットを取得し、前記ターゲットノードサブセットに応じて前記サンプルノードセット中の選択対象ネイバーノードの第２候補確率を計算し、前記選択対象ネイバーノードの前記第２候補確率に応じて前記ネイバーノードサブセットを決定することに用いられる。
【０１１９】
選択可能な実施例では、前記取得モジュール１１１０はさらに、前記ターゲットノードサブセット中の前記ターゲットノードと第ｕ個の前記選択対象ネイバーノードとの間の連結エッジ重み、及び前記ターゲットノードと前記サンプルノードセット中のノードとの連結エッジ重みによって、第ｕ個の前記選択対象ネイバーノードの前記第２候補確率を決定することに用いられ、ｕは正の整数である。
【０１２０】
選択可能な実施例では、前記抽出モジュール１１２０はさらに、前記ノード分類モデルのターゲットモデルパラメータを決定することに用いられ、前記ターゲットモデルパラメータは訓練対象のモデルパラメータであり、前記ターゲットモデルパラメータ及び前記ネイバーノードサブセットに応じて前記ターゲットノードサブセットのノード特徴サブセットを抽出することに用いられる。
【０１２１】
選択可能な実施例では、前記抽出モジュール１１２０はさらに、第ｉ個の前記ターゲットノードと前記ネイバーノードとの間の連結エッジ重み、前記ネイバーノードの特徴ベクトル及び前記ターゲットモデルパラメータに応じて、第ｉ個の前記ターゲットノードのノード特徴を決定することに用いられ、ｉは正の整数である。
【０１２２】
選択可能な実施例では、前記訓練モジュール１１４０はさらに、前記予測タイプ確率サブセット及び前記ターゲットノードの前記ターゲットノードタイプに応じてターゲット損失値を決定し、前記ターゲット損失値に応じて前記モデルパラメータ勾配を決定し、前記モデルパラメータ勾配に応じて前記ターゲットモデルパラメータを訓練することに用いられる。
【０１２３】
選択可能な実施例では、前記訓練モジュール１１４０はさらに、前記モデルパラメータ勾配と所定の学習率との積を前記ターゲットモデルパラメータの調整差とし、前記調整差で前記ターゲットモデルパラメータを調整することに用いられる。
【０１２４】
以上のように、本実施例に係るモデル訓練装置は、ノード分類過程においてノードに対して特徴更新を行う際に、ターゲットノードセットから分類対象ノードを選択し、該分類対象ノードのネイバーノードセットに応じて該分類対象ノードのノード特徴を決定し、それによってノード特徴に応じてノード分類結果を取得し、上記のようにして、大規模グラフの場合、毎回グラフ中の一部のノードを反復計算すればよく、グラフ中の各ノードをトラバーサルする必要がなく、計算オーバーヘッドを大幅に削減させるとともに、計算リソースを節約する。
【０１２５】
図１２は本願の例示的な実施例に係るサーバの構造模式図である。該サーバは図３に示されるサーバ３１０であってもよい。具体的には、
サーバ１２００は中央処理装置（ＣＰＵ、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１２０１と、ランダムアクセスメモリ（ＲＡＭ、Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１２０２及び読み出し専用メモリ（ＲＯＭ、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１２０３を含むシステムメモリ１２０４と、システムメモリ１２０４と中央処理装置１２０１とを接続するシステムバス１２０５と、を備える。サーバ１２００は、コンピュータ内の各デバイス間で情報を伝送するのを助ける基本的な入力／出力システム（Ｉ／Ｏシステム、Ｉｎｐｕｔ  Ｏｕｔｐｕｔ  Ｓｙｓｔｅｍ）１２０６と、オペレーティングシステム１２１３、アプリケーションプログラム１２１４及びほかのプログラムモジュール１２１５を記憶することに用いられる大容量記憶装置１２０７と、をさらに備える。
【０１２６】
基本的な入力／出力システム１２０６は、情報を表示することに用いられるディスプレイ１２０８と、例えば、マウス、キーボードのような、ユーザーが情報を入力することに用いられる入力機器１２０９と、を備える。ディスプレイ１２０８及び入力機器１２０９はいずれもシステムバス１２０５に接続される入力出力コントローラ１２１０によって中央処理装置１２０１に接続される。基本的な入力／出力システム１２０６は、キーボード、マウス、又は電子スタイラス等の複数のほかの機器からの入力を受信して処理することに用いられる入力出力コントローラ１２１０をさらに備えてもよい。同様に、入力出力コントローラ１２１０はさらにディスプレイスクリーン、プリンタ又はほかのタイプの出力機器への出力を提供する。
【０１２７】
大容量記憶装置１２０７はシステムバス１２０５に接続される大容量記憶コントローラ（図示せず）によって、中央処理装置１２０１に接続される。大容量記憶装置１２０７及びそれに関連付けられるコンピュータ可読媒体はサーバ１２００に不揮発性記憶を提供する。つまり、大容量記憶装置１２０７は、例えば、ハードディスク又は読み出し専用のコンパクトディスク（ＣＤ−ＲＯＭ、Ｃｏｍｐａｃｔ  Ｄｉｓｃ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）ドライブのようなコンピュータ可読媒体（図示せず）を含んでもよい。
【０１２８】
一般性を失うことなく、コンピュータ可読媒体はコンピュータ記憶媒体及び通信媒体を含んでもよい。コンピュータ記憶媒体は、例えば、コンピュータ可読命令、データ構造、プログラムモジュール又はほかのデータ等の情報を記憶することに用いられ任意の方法又は技術で実現される揮発性及び不揮発性、取り外し可能及び取り外し不能な媒体を含む。コンピュータ記憶媒体はＲＡＭ、ＲＯＭ、可消去可能プログラマブル読み出し専用メモリ（ＥＰＲＯＭ、Ｅｒａｓａｂｌｅ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、電気的消去可能プログラマブル読み出し専用メモリ（ＥＥＰＲＯＭ、Ｅｌｅｃｔｒｉｃａｌｌｙ  Ｅｒａｓａｂｌｅ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、フラッシュメモリ又はほかのソリッドステートメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ、Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）又はほかの光学記憶、テープカセット、磁気テープ、磁気ディスク記憶又はほかの磁気記憶装置を含む。勿論、当業者であれば、コンピュータ記憶媒体は上記のものに限定されないと理解できる。上記システムメモリ１２０４及び大容量記憶装置１２０７はメモリと総称されてもよい。
【０１２９】
本願の各実施例によれば、サーバ１２００はさらに、例えばインターネット等のネットワークによってネットワークにおける遠隔コンピュータに接続されて動作してもよい。即ち、サーバ１２００はシステムバス１２０５に接続されるネットワークインターフェースユニット１２１１によってネットワーク１２１２に接続されてもよく、又は、ネットワークインターフェースユニット１２１１を使用してほかのタイプのネットワーク又は遠隔コンピュータシステム（図示せず）に接続されてもよい。
【０１３０】
上記メモリは１つ以上のプログラムをさらに含んでもよく、１つ以上のプログラムはメモリに記憶され、ＣＰＵによって実行されるように構成される。
【０１３１】
本願の実施例はコンピュータ機器をさらに提供し、該コンピュータ機器はプロセッサ及びメモリを備え、該メモリは少なくとも１つの命令、少なくとも１つのプログラム、コードセット又は命令セットを記憶し、少なくとも１つの命令、少なくとも１つのプログラム、コードセット又は命令セットがプロセッサによって読み込んで実行されると、上記各方法の実施例に係るノード分類方法又はモデル訓練方法を実現する。
【０１３２】
本願の実施例はコンピュータ可読記憶媒体をさらに提供し、該コンピュータ可読記憶媒体は少なくとも１つの命令、少なくとも１つのプログラム、コードセット又は命令セットを記憶し、少なくとも１つの命令、少なくとも１つのプログラム、コードセット又は命令セットがプロセッサによって読み込んで実行されると、上記各方法の実施例に係るノード分類方法又はモデル訓練方法を実現する。
【０１３３】
理解されるように、本明細書に記載の「複数」とは２つ以上である。「及び／又は」は関連対象の関連関係を説明するものであり、３種の関係が存在することを示し、例えば、Ａ及び／又はＢの場合、Ａのみが存在すること、ＡとＢが同時に存在すること、及びＢのみが存在することを示す。文字「／」は、一般には、前後の関連対象が「又は」の関係を有することを示す。
【０１３４】
当業者が理解できるように、上記実施例のステップの全部又は一部は、ハードウェアによって実現されてもよく、プログラムによって関連ハードウェアに命令を出して実現されてもよく、上記プログラムはコンピュータ可読記憶媒体に記憶されてもよく、上記記憶媒体は読み出し専用メモリ、磁気ディスク又は光ディスク等であってもよい。
【０１３５】
以上、本願の選択可能な実施例を説明したが、本願を限定するものではない。本願の趣旨及び原則を逸脱せずに行われる任意の変更、同等置換や改良等はすべて本願の保護範囲に属する。
【図１】
2021533474.tif 000121
【図２】
2021533474.tif 000122
【図３】
2021533474.tif 000123
【図４】
2021533474.tif 000124
【図５】
2021533474.tif 000125
【図６】
2021533474.tif 000126
【図７】
2021533474.tif 000127
【図８】
2021533474.tif 000128
【図９】
2021533474.tif 000129
【図１０】
2021533474.tif 000130
【図１１】
2021533474.tif 000131
【図１２】
2021533474.tif 000132
【国際調査報告】
2021533474.tif 000133
2021533474.tif 000134
2021533474.tif 000135
2021533474.tif 000136