Google Expanderチームは，Alloアプリケーションが写真に対してレコメンデーションを行なう基盤として使用されている，実行時間の一定な(constant-runtime)グラフストリーミングアルゴリズムを公表した。Googleの説明によれば，ラベルのないノードのカテゴリとプロパティ，この例であれば写真やテキストその他の不均一グラフを構成するデータを推測する上で，ノード相互の近接性を利用している。グラフアルゴリズムが数百万から数十億というグラフを処理して学習する必要のある場合，膨大なコストを必要とする教師付き(supervised)学習に比較して，半教師付き(semi-supervised)学習アプローチは，必要なトレーニングデータ量の削減が可能である。
テキストやイメージやビデオ入力で構成されたグラフ，あらゆるサイズと形式が混合したマルチモーダルなデータ，あるいはイメージピクセルやAlloの写真応答や，そういったデータのさまざまな”データ表現(data representations)など - データはリレーショナルや構造化データだけでなく，非構造的であったり，粗や密であったりなど，あらゆる形式で生データから取り出されて表現されます。
Googleはそのグラフ例の特徴をいくつかあげる中で，このアプローチが数百万，場合によっては数十億にもなるノードグラフに拡張できない点を指摘している。グラフの各ノードに対して“赤”あるいは“青”を予測する例について，Googleは次のように説明する。
ノードデータ間の関係はエッジで表現され，それぞれのエッジの厚みが接続の強度を示しています ... エッジの強度は組み込まれるベクトルの類似性を使って計算され — 類似性の低いエッジは無視されます ... “グレー”はラベルのないデータを，着色されたノードはラベル付きデータを表しています。ノードデータ間の関係はエッジを介して表現され，それぞれのエッジの厚みが接続の強度を示しています。具体的なグラフ構造や色の選択はタスク依存であることに注意してください ... このメソッドは，大規模なグラフには対応できません。
より実践的な，あるいは実世界のユースケース向けにGoogleが提供するのは，事前にラベル付けられ類似近接グラフに配置された単語から，ユーモラスな単語を識別するサンプルだ。
この実行時間の一定なアルゴリズムは，隣接ノードから分散的な方法で伝搬することで極めて大規模なグラフを対象として作動することが可能で，そのグラフ上に残る単語の感情的カテゴリを検出するように設定された半教師付き学習に基づいて，指定された単語がユーモラスかどうかを算出する。タスクの難易度や予測ラベルの数に関わらず，システムに対する複雑性空間とメモリ要件，さらにはアルゴリズム設計上の潜在的な出力空間因子のサイズが常に一定である，とGoogleは報告している。現時点で利用可能なコードサンプルやデータセット，あるいは属性は提供されていない。
“実際にはグラフ構造に対して，難しい非凸(non-convex)問題を引き起こしうる半教師付きグラフ学習のための追加的な情報や制約を取り入れて定義された，複雑性の最適化機能を使用しています。しかし現実的な課題としてあるのは，数十億のさまざまなラベルタイプが関与する複雑なタスクのための，数十億のノード，数兆のエッジを持つグラフに対して，これを効率的に拡張することです。”
この記事を評価
- 編集者評
- 編集長アクション