特許ウォッチ

公開番号2024116079
公報種別公開特許公報(A)
公開日2024-08-27
出願番号2024008699
出願日2024-01-24
発明の名称グラフにおけるパスをトレースするための方法、システム、およびソフトウェア
出願人株式会社日立製作所
代理人弁理士法人サンネクスト国際特許事務所
主分類G06F 16/28 20190101AFI20240820BHJP(計算;計数)
要約【課題】グラフにおけるパスをトレースするための方法、システムおよびソフトウェアを提供する。
【解決手段】グラフ構造データセットの入力について、方法は、入力されたグラフ構造データセットから異種グラフを生成するために、複数のノードおよび複数のエッジのためのタイプおよび属性を定義することと、類似性に基づいて複数のノードを互いに関連付けることと、定義されたフローに基づいて複数のノードおよび複数のエッジ間のメタパスのためのスキームを定義することと、定義されたスキームに基づいて、選択されたノードのための正のメタパスおよび負のメタパスを異種グラフからサンプリングすることと、関連付けられた前記複数のノードを埋め込みベクトルに投影することと、事前に設定された閾値よりも大きい、ユーザによって指定された開始ノードと類似性を有する関連付けられたノードのパスをトレースすることと、を含む。
【選択図】図4A
特許請求の範囲【請求項１】
メタパスを通してグラフ構造データセットにおけるノードのフローをトレースする方法であって、
複数のノードおよび複数のエッジを含み、前記複数のノードの各々はオブジェクトを表し、前記複数のエッジの各々は前記複数のノードの各々の間のインタラクションを表すグラフ構造データセットの入力について、
前記入力されたグラフ構造データセットから異種グラフを生成するために、前記複数のノードおよび前記複数のエッジのためのタイプおよび属性を定義することと、
類似性に基づいて前記複数のノードを互いに関連付けることと、
定義されたフローに基づいて前記複数のノードおよび前記複数のエッジ間のメタパスのためのスキームを定義することと、
定義された前記スキーム、関連付けられた前記複数のノード、および関連付けられた前記複数のノードのための定義された前記タイプおよび属性に基づいて、選択されたノードのための正のメタパスおよび負のメタパスを前記異種グラフからサンプリングすることと、
関連付けられた前記複数のノードを埋め込みベクトルに投影することと、
事前に設定された閾値よりも大きい類似性を有する関連付けられた前記ノードのサンプリングされた前記正のメタパスおよび前記負のメタパスのうちのメタパスを選択することによって、前記異種グラフからサンプリングされた前記正のメタパスおよび前記負のメタパスをトレースすることと、
サンプリングされた前記正のメタパスおよび前記負のメタパスのうちの選択された前記メタパスを、インターフェースを介して出力することと
を含む、方法。
続きを表示（約 1,700 文字）【請求項２】
前記複数のノードの各々が会社と関連付けられ、前記複数のエッジの各々が前記会社と商品との間の調達もしくは製造インタラクションを表す、請求項１に記載の方法。
【請求項３】
選択された前記ノードと関連付けられた前記複数のエッジを監視することをさらに含む、請求項２に記載の方法。
【請求項４】
前記類似性に基づいて前記複数のノードを互いに関連付けることが、入力品もしくは出力品の物理的フローのタイプおよび属性に基づいて前記複数のノードを分類することと、前記分類から類似性スコアを判定することとを含む、請求項２に記載の方法。
【請求項５】
前記複数のノードの各々がソーシャルメディアユーザおよび投稿を表し、前記複数のエッジの各々が、読まれる入力投稿またはソーシャルメディアプラットフォーム上の出力投稿を表す、請求項１に記載の方法。
【請求項６】
前記類似性に基づいて前記複数のノードを互いに関連付けることは、リアルニュースもしくはフェイクニュースに対するソーシャルメディアアカウントおよびソーシャルメディア投稿のタイプおよび属性の類似性に基づいて前記ソーシャルメディア投稿をリアルニュースもしくはフェイクニュースに分類することと、前記複数のエッジに対する重みを判定するために前記タイプおよび属性の前記類似性に基づいて前記複数のノードおよび前記複数のエッジをクラスタ化することとを含む、請求項５に記載の方法。
【請求項７】
前記関連付けられた前記複数のノードを埋め込みベクトルに投影することは、サンプリングされた前記正のメタパスおよび前記負のメタパスを空間ベースのグラフニューラルネットワークに入力することを含む、請求項１に記載の方法。
【請求項８】
前記正のメタパスが、選択された前記ノードから前記複数のノードのうちの別のノードまでの可能なパスを表し、前記負のメタパスが、選択された前記ノードによって到達可能でない前記複数のノードのうちのノードを表す、請求項１に記載の方法。
【請求項９】
メタパスを通してグラフ構造データセットにおけるノードのフローをトレースする命令を記憶する非一時的コンピュータ可読媒体であって、前記命令が、
複数のノードおよび複数のエッジを含み、前記複数のノードの各々はオブジェクトを表し、前記複数のエッジの各々は前記複数のノードの各々の間のインタラクションを表すグラフ構造データセットの入力について、
前記入力されたグラフ構造データセットから異種グラフを生成するために、前記複数のノードおよび前記複数のエッジのためにタイプおよび属性を定義することと、
類似性に基づいて前記複数のノードを互いに関連付けることと、
定義されたフローに基づいて前記複数のノードおよび前記複数のエッジ間のメタパスのためのスキームを定義することと、
定義された前記スキーム、関連付けられた前記複数のノード、および関連付けられた前記複数のノードのための定義された前記タイプおよび属性に基づいて、選択されたノードのための正のメタパスおよび負のメタパスを前記異種グラフからサンプリングすることと、
関連付けられた前記複数のノードを埋め込みベクトルに投影することと、
事前に設定された閾値よりも大きい類似性を有する関連付けられた前記ノードのサンプリングされた前記正のメタパスおよび前記負のメタパスのうちのメタパスを選択することによって、前記異種グラフからサンプリングされた前記正のメタパスおよび前記負のメタパスをトレースすることと、
サンプリングされた前記正のメタパスおよび前記負のメタパスのうちの選択された前記メタパスを、インターフェースを介して出力することと
を含む、非一時的コンピュータ可読媒体。
【請求項１０】
前記複数のノードの各々が会社と関連付けられ、前記複数のエッジの各々が前記会社と商品との間の調達もしくは製造インタラクションを表す、請求項９に記載の非一時的コンピュータ可読媒体。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本開示は、一般にデータ管理システムに関し、より詳しくはグラフにおけるパスをトレースするための方法、システム、およびソフトウェアに関係する。
続きを表示（約 2,500 文字）【背景技術】
【０００２】
サプライチェーン、ソーシャルネットワーク、およびコンタクトネットワークなどのグラフ構造化データにおいて、パスをトレースすることは関心の的となる場合が多い。そのようなパスのトレースは、サプライチェーンの混乱後の損失を軽減するためにサプライチェーン内の製品の物理的フローをトレースすることと、情報のソースを特定するため、または影響を最大限にするためにソーシャルネットワーク内におけるニュースの情報フローをトレースすること、または流行の予測、さらには予防のために伝染病の感染ルートをトレースすることを含み得る。
【０００３】
図１は、サプライチェーン内の物理的フローの例、すなわちチップ不足によって引き起こされた自動車の製造停止を示す図である。チップ不足、エンジン不足、および自動車の製造停止後、自動車部品の需要が結果として最終的に減少する。
【０００４】
自動車部品製造業者の場合、自動車の物理的フローをトレースすることは、需要の減少を事前に予測して損失を軽減するのを助け得る。同様に、サプライチェーンにおけるキャッシュフローをトレースすることは、金融機関が運転資金についての可能性のある要求を予測して適時に金融サービスを提供することを助けることができる。
【０００５】
しかしながら、グラフ構造データでは、通常、複数のエンティティ、すなわち各エンティティの入力オブジェクトおよび出力オブジェクト間に複数のパスが存在する。さらに、通常、入力オブジェクトと出力オブジェクトとの間の対応関係は未知である。例えば、サプライチェーンでは、各企業が異なる製品を製造する。入力（原料および部品）と出力（製品）との間の相関は、通常機密である。したがって、図２に示すように、各製品の物理的フローは決してトレース可能ではなく、サプライチェーンの混乱に直面したときに部品企業を変更するのが困難になる。
【０００６】
図３に示されるソーシャルネットワークにおいて、フェイクニュース伝播のパスをトレースすることは、ソーシャルメディアプラットフォームがユーザをフェイク情報から遠ざけることを助け得る。しかしながら、ソーシャルネットワークでは、各ユーザは、他のユーザからの複数の投稿を読むこと、複数のメッセージを他のユーザに対して投稿することなど、他のユーザとの複数の着信および発信インタラクションを有する。着信投稿と発信投稿との相関は未知であり、フェイクニュース伝播のパスをトレースすることを困難にしている。
【０００７】
グラフ構造化データにおけるパスをトレースするために多数の関連技術の実装が提案されている。サプライチェーンの場合、供給業者および調達者などのエージェントが特定のルールにしたがうエージェントベースのモデルが、負のショックの伝播をモデル化するために使用される。しかしながら、そのモデルでは、ある分野の各々の会社がその分野に特化した製品のみを製造すると仮定されるが、必ずしもそうとは限らない。例えば、リチウム電池、冷蔵庫などの複数の種類の製品を製造する会社が存在し得るが、関連技術の実装によってモデル化できない。
【０００８】
ソーシャルネットワークの領域において、関連技術は、ソーシャルネットワークにおけるフェイクニュース伝播パスのトレースに焦点を合わせている。フェイクニュースを投稿したユーザは、まず検出および分類され、次いで、伝播パスを学習するためにそのユーザの近隣者が繰り返しトレースされる。ただし、そのような関連技術の実装は、着信メッセージを理由としてユーザがフェイクニュースを投稿することを仮定しているが、それは正しくない。現実世界では、ユーザは、通常、実際のニュースおよびフェイクニュースと混合された複数の着信インタラクションを受信する。フェイクニュースの発信投稿は、着信インタラクションの一部によってのみ発生される。
【０００９】
したがって、関連技術の方法は、エンティティ間の情報共有の意欲に依存するか、または一般的に適用可能でないかのいずれかである。いくつかの関連技術の実装は、サプライチェーンの調査監視を行う仲介者を使用してアンケートを関連企業に送信することによってサプライチェーン内の物理的フローをトレースすることを実現している。他の関連技術の実装では、電子データ交換（ＥＤＩ）メッセージおよび無線ＩＤタグ（ＲＦＩＤ）を含む追跡技術がそれぞれ使用される。例示的な関連技術の実装では、アセンブリ、サブアセンブリ（ここでは部品と定義される）、および最終製品間の関係を有する部品表（ＢＯＭ）が、グラフ構造化データにおけるパスをトレースするために入力と出力との相関として利用される。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
本明細書で説明する例示的な実装は、グラフ構造化データにおけるパスをトレースするための方法、システム、およびソフトウェアを伴う。そのようなパスのトレースは、サプライチェーンにおける各製品の物理的フローもしくはキャッシュフローをトレースすること、またはソーシャルネットワークにおけるフェイクニュースの伝播パスをトレースすることを伴い得る。しかしながら、これらのグラフ構造化データでは、エンティティ間において複数のインタラクションが存在する。例えば、サプライチェーンでは、各会社が複数のタイプの製品を多種多様な中間製品および材料を使用して製造する。ソーシャルネットワークでは、各ユーザが、複数の投稿を受信および送信する。さらに、着信および発信インタラクション（材料と製品、着信投稿と発信投稿）間の相関は未知である。そのようなグラフ構造化データにおけるパスのトレースは、本明細書で説明する例示的な実装によって対処される問題である。
【課題を解決するための手段】
（【００１１】以降は省略されています）

関連特許