[Database] Introducing PGX - Parallel Graph Analytics - 2.2.1

原文はこちら。
https://blogs.oracle.com/labs/entry/introducing_pgx_parallel_graph_analytics

OracleのR&D LabsからParallel Graph Analytics (PGX) 2.2.1がリリースされました。
Oracle Labs PGX Downloads
http://www.oracle.com/technetwork/oracle-labs/parallel-graph-analytics/downloads/index.html
これは、透過的に並列化可能なアルゴリズムをフレームワークが記述するためのDSLを使ってグラフのアルゴリズム的解析と、SQLライクなクエリ言語を使ったグラフのパターンマッチング、その両方のグラフ解析を実施するための高性能なツールキットです。
PGQL · Property Graph Query Language
http://pgql-lang.org/
Groovyシェルを使って対話的に利用することも、様々なAPIを使った自動化ワークフローに統合することもできます。
既にPGXのことをご存知であれば、PGX 2.2.1の新機能をご覧ください。
PGX 2.2.1 Documentation
What is New in PGX 2.2
https://docs.oracle.com/cd/E56133_01/2.2.1/whatsnew/whatsnew.html
グラフ解析は、あなたが持っているデータで明示的に表現されるものではなく、既に持っているデータ要素間の関係のネットワークで表現される潜在情報を明らかにします。

Who Has A Graph?

みんな持っています。あるフィールドを共有するデータがある場合(リレーショナルデータベースを使用している場合)、知っているかどうかに関わらず、グラフを持ちます。
ソーシャルネットワークのおかげでグラフ分析が知られています。最も明白でアクセス可能なグラフの例が、ソーシャルネットワークが生成する友人間のネットワークです。この例は非常に鮮明ゆえに、ソーシャルネットワーク分析はこの種の技術が適しているという印象を作り出します(とはいえ、真実以上のものはないのですが)。グラフ分析のパワーは、グラフの頂点がすべて同じ種類のものではない場合に顕著に現れます。 例えば次のような場合です。
  • ある頂点が人で、ある頂点が評価した動画であるグラフを作成します(マトリックス因数分解や、アルゴリズム技術を使うと、推奨エンジンを作成することができます)。そして実際、これはNetflixが実施している推奨方法です。
    Using PGX as a Recommendation Engine
    https://docs.oracle.com/cd/E56133_01/2.2.1/use-cases/recommendation/index.html
    • リコメンデーションとは予測です。既存データを使って存在しないデータを外挿したり、データ内の潜在的な関係を予測したいどんな領域にも、このテクニックだけを応用することができます。
  • 異常検出
    どのような関係がデータセット内で典型的であるかを検出します。例えば、特定の専門分野の医師がどんな薬をどのようなランクで処方しているのかを基にして、典型的ではない医師を特定します。また、保険の請求や保険金請求者、車両事故をグラフでモデリングし、地理的に近い複数の請求の両方の立場の関係者を見つけ出して、保険金の搾取高位を検出します。
    Detect Anomalies in a Healthcare System
    https://docs.oracle.com/cd/E56133_01/2.2.1/use-cases/healthcare-fraud/index.html
  • 電力グリッドのモデリングや、オフラインのグリッド個々の要素のダウンストリーム効果を判断して、脆弱性の識別やメンテナンスを計画します。
    Modeling an Electric Network With PGX
    https://docs.oracle.com/cd/E56133_01/1.2.0/use-cases/electric-network/index.html
これらはグラフ解析の利用例の一例に過ぎません。別の興味深い例として、どうやってAmerican Revolutionが利用可能なメタデータやこうしたテクニックを使えなくさせたのか、という以下の記事です。
Using Metadata to find Paul Revere
https://kieranhealy.org/blog/archives/2013/06/09/using-metadata-to-find-paul-revere/
ここがポイントです。テクノロジ業界はグラフ解析のアプリケーションの表面をほとんど傷つけず、PGXによって、これまで政府にのみ利用可能になっていた数学のツールがすぐ使えるようになりました。

Using PGX

たくさんのチュートリアルがご利用いただけますが、PGXを操作するにあたって主要な手順はシンプルです。
Tutorials
https://docs.oracle.com/cd/E56133_01/2.2.1/tutorials/index.html
PGXツールキットをダウンロード、インストールしてから、コマンドラインで実行するのはプログラムpgxを実行するのと同じぐらい簡単です。pgxはPGXシェルとグラフ・エンジン(リモートにデプロイされているものでもOK)の組み込みインスタンスを始動します。

一般的な利用パターンはシンプルです。
  1. (SQLデータベース、Oracle NoSQL、フラットファイル、Hadoop、Apache Sparkなどから)グラフをロードする
  2. 多くのビルトインされている(もしくはカスタム開発した)アルゴリズムのうちの一つもしくは複数をグラフに対して実行する。アルゴリズムは通常新しいプロパティをグラフの頂点やエッジに追加する。
    Algorithms
    https://docs.oracle.com/cd/E56133_01/2.2.1/reference/algorithms/index.html
  3.     PGQLを使ってアルゴリズムを用いたパターンマッチを実行する
このプロセスの手順を必要に応じて繰り返すことができ、結果を使ってレポートの生成やCSVファイルの出力ができます。PGXのJava APIやNode.jsのAPIを使っている場合、自動化されたワークフローに参加させることもできます。これらの手順全てをGroovyスクリプトとして保存し、再実行することができます。グラフ解析の重要な要素の一つは、再生産できること、アップデートされたデータに対して後で適用できることです。

Examples

Groovy Shell

PGXを手早く動かすにあたっては、Groovyシェルが最も簡単です。これを使うと対話的にグラフ解析ができます。例えば以下のような感じです。
graph = session.readGraphWithProperties(
  "../gameofthrones/stormofswords.json").undirect();

prop = analyst.eigenvectorCentrality(g);
graph.queryPgql(
  "SELECT v.id(), v.eigenvector WHERE (v)
            ORDER BY DESC(v.eigenvector)")

PGQL

Property Graph Query Language(PGQL)はオープンソースのSQLライクなグラフをクエリするための言語です。特に、値による制約(例:eigenvector > 0.9)とともに、トポロジーの制約を指定することができます。これらを使って、グラフの接続内で探索するパターンを指定することができます。
SELECT v.id() WHERE (t WITH t.id() = 'Tyrion') -[]-> () -[]-> (v)
この例では、TyrionというIDを持つ頂点に間接的に接続されている全ての頂点を検索しています。

Recursive topological constraints

パスクエリを定義し利用すると、再帰的にパターンを適用することもできます。以下は2人の共通の祖先を全て探す例です。
PATH has_parent := () -[:has_father|has_mother]-> ()
SELECT ancestor.name
WHERE
  (:Person WITH name = 'Mario') -/:has_parent*/-> (ancestor:Person),
  (:Person WITH name = 'Luigi') -/:has_parent*/-> (ancestor)
上記の例では、Marioのクエリは、ancestorという名前のMarioの祖先のある場所で頂点を定義しています。第2のLuigiの制約では、ancestorが、Mario用に定義された同じ頂点がある(つまり両方の祖先と同じ人物)ことを発見することを求めています。出力は、SQLの結果セットとは似ていない結果セットですが、これをレポートの生成や後続の処理に使用できます。

Green-Marl

Green-Marlは、ファーストクラスの言語要素として、頂点、エッジ、プロパティ、幅優先、深さ優先の検索を持つグラフアルゴリズムを記述するための言語です。特に、ループ構造は、同時実行性を管理するコードを記述しなくても、ランタイムによって透過的に並列化されるため、記述したアルゴリズムは自動的に利用可能な処理能力の全てを利用します。

PGXには多数のアルゴリズムが組み込まれていますが、自身でアルゴリズムを記述しコンパイルすることができるため、必要な分析タスクを柔軟に実行することができます。
proc weighted_degree_centrality( g: graph,
  weightProp: E_P<double>; outputProperty: N_P<double> ) {

    // Get the range of weight values
    int minWeight = min( curr_edge : g.edges ) { curr_edge.weightProp }; // find the lowest weight value
    int maxWeight = max( curr_edge : g.edges ) { curr_edge.weightProp }; // find the highest weight value

    foreach ( vtx : g.nodes ) { // iterate every node
        double weight = 0;
        for ( curr_edge : vtx.outEdges ) { // sum the weights
            weight += curr_edge.weightProp;
        }
        // Compute and assign the weighted result for this vertex
        vtx.outputProperty = vtx.degree()  * ( ( weight - minWeight ) + 1 );
    }
}

Using PGX with Apache Zeppelin

PGXのこのリリースには、Apache Zeppelinのインタープリタが含まれています。これは"notebook"サーバと言われるもので、解析のステップ、これらのステップの説明、インタラクティブかつ協働して分析を実施したり、インタラクティブなレポートの形で結果を保持する方法を取得するための簡便な方法を提供します。
Apache Zeppelin
https://zeppelin.apache.org/
利用にあたっては、Zeppelinをインストールし、Zeppelinインタープリタをダウンロードして、Zeppelinのinterpreterディレクトリにインストールして、新しいnotebookを構成する必要があります。
Oracle Labs PGX Downloads
http://www.oracle.com/technetwork/oracle-labs/parallel-graph-analytics/downloads/index.html

Performance

グラフはPGXのメモリ上にあるため、パフォーマンスはメモリの容量と利用可能なCPUの個数によってのみ制限を受けます。Javaエンジンはオフヒープストレージと非常に効率的なデータ構造を使うため、サーバークラスのハードウェアが有用ではあるにせよ、驚くほど大きなグラフをラップトップで分析することができます。そして、アルゴリズム分析、パターンマッチング分析の両方を並列化するので、どんなコンピュート・リソースも十分に活用することができます。
大量のデータがある場合、データを他の場所にあるメモリに取り込むインメモリ解析が不便になる可能性があります。 ただし、次の点を考慮してください。
  • グラフ解析の特徴の1つとして、指定された任意のアルゴリズムで、頂点を任意の順序で何回も訪れることができます。
  • HadoopやSparkのような環境では、データが複数のマシンに分散しており、それらのマシンでHadoopやSparkが動作するため、共有コンピュート・リソースで利用される変数の単純なアップデートでさえもネットワークI/Oが発生します。そして変数は何度も更新される可能性があり、ときにはグラフのノードの個数の倍になることがあります(ネットワークアクセスはネットワークI/Oに比べて数桁遅いのです)
要約すると、グラフ解析の性質ゆえに、1回のグラフをロード(して、そしてメモリアクセスの速度で解析を実行できる)するI/Oコストは例えばSparkのGraphXよりもずっと低コストです。
PGXには、単一のノードに収まらない大きなグラフを解析するための、複数のマシンにセットアップ可能な分散分析エンジンも含まれています。

0 件のコメント:

コメントを投稿