Counting Triangles of Graphs via Randomized Trace Estimation with Incomplete Matrix-Vector Products

全体像：巨大なウェブにおける三角形のカウント

想像してみてください。あなたは、誰もが多くの人とつながっている、巨大なソーシャルネットワークのような、広大な友人のネットワークを持っています。このウェブの中で、「三角形」とは非常に特定のパターンを指します。つまり、人物Aが人物Bを知っており、人物Bが人物Cを知っており、そして人物Cが人物Aを知っているという状態です。

これらの三角形を数えることは、データサイエンティストにとって非常に重要です。これによって、コミュニティがいかに結束しているか、次に誰が友達になりそうか、あるいは異常な行動（詐欺グループなど）を見つけ出すことができます。

問題点：
ネットワークが小さい場合は、三角形を一つずつ数えることができます。しかし、ネットワークに数百万人もの人々がいる場合、それらをすべて数えるのは、ビーチにあるすべての砂粒を手作業で数えようとするようなものです。膨大な時間とコンピュータの計算能力が必要になります。

三角形を数えるための標準的な数学的トリックは、ネットワーク全体を表す巨大な格子（行列と呼ばれます）を使用することです。答えを得るには、通常、この格子を自分自身と3回掛け合わせる必要があります。しかし、巨大なネットワークの場合、その「掛け合わせた格子」を作成することは不可能です。なぜなら、地球上のすべてのコンピュータを合わせたよりも多くのメモリが必要になるからです。

旧来の解決策：「推測ゲーム」

これを解決するために、数学者はハッチソン（Hutchinson）の推定法という手法を使います。これは、「平均を当てるゲーム」のようなものです。

正確な数を計算する代わりに、格子の図に対してランダムにたくさんのダーツを投げます。そしてコンピュータにこう問いかけます。「もしこの格子にこのランダムなダーツを掛け合わせたら、どうなるだろうか？」 これを何度も繰り返し、その結果の平均を取ります。すると、魔法のように、その平均値が三角形の総数の非常に優れた推定値となります。

これは、巨大な掛け合わせ済みの格子を作る必要がなく、元の格子を使った単純な掛け算だけで済むため、非常に高速です。

新たな問題：「遅れている人」と「騒がしい部屋」

この論文は、多くのプロセッサが協力して動く大規模なコンピュータシステム（例：パズルを解くチームのようなもの）でこの手法を実行しようとしたときに発生する、特定の問題に取り組んでいます。

あなたが、ある「ダーツ投げ」の結果を計算するために、100人のチームを持っていると想像してください。

1. 会話のコスト： 最終的な答えを得るために、全員が自分の計算の一部を全員と共有しなければなりません。巨大なネットワークでは、この「会話（通信）」に時間がかかり、すべてを遅らせてしまいます。
2. 遅れている人（ストラグラ）： 時には、チームの中に他の人よりも遅い人（例えば、コンピュータが他の作業で忙しいなど）が1人や2人混じることがあります。伝統的な設定では、チーム全体が次のステップに進む前に、最も遅い人の完了を待たなければなりません。これは「同期待ち」と呼ばれます。

著者たちは、全員が終了してすべての数字を共有するのを待つことは、時間の無駄であることに気づきました。

新しい解決策：「部分的な覗き見」

著者たちは、この推測ゲームの遊び方として、巧妙な新しい方法を提案しています。チーム全員が計算を終えてすべての数字を共有するのを待つ代わりに、ランダムな一部の数字だけを「覗き見」して、すぐに次の工程へ進むことを許可するのです。

比喩：
群衆の平均身長を推定しようとしている場面を想像してください。

• 従来の方法： 全員が体重計の上に立ち、身長を書き留めて中央のコンピュータに送るのを待ちます。最も遅い人が終わるまで、あなたは平均値の計算をできません。
• 新しい方法： 群衆にこう言います。「もし気が向いたら、かつ、ランダムな場所に立っている場合のみ、身長を叫んでください」。全員を待つことはしません。聞こえてきた声だけを拾い、素早く計算を行い、次のラウンドへ進みます。

論文では、これを**「部分観測（partial observation）」**と呼んでいます。彼らは、計算のどの部分を見て、どの部分を無視するかをランダムに決定します。また、「遅い」プロセッサが全体の足を引っ張ることなく、後からデータを貢献することも許可しています。

彼らが証明したこと（「科学的」な部分）

「データを無視したら、答えは間違ってしまうのではないか？」と思うかもしれません。著者たちは、重厚な数学を用いて3つのことを証明しました。

1. 公平であること（不偏性）： たとえ断片的なピースしか見ていなくても、推測の平均は依然として完全に正確です。彼らはズルをしているのではなく、単に効率化しているのです。
2. 信頼できること（分散）： 彼らは、答えがどれくらい変動するかを正確に計算しました。データが欠けていても、実験を十分に繰り返せば、答えは真実に近い状態を保つことを証明しました。
3. 高速であること： 「全員を待つ」ステップをスキップすることで、特にコンピュータが異なる場所にあったり、速度が異なったりする場合に、システムが大幅に高速に動作することを示しました。

結果：本当に機能するのか？

彼らは、3種類の異なるネットワークでこの新手法をテストしました。

1. 論文を共同執筆した科学者の実在のネットワーク。
2. 架空のランダムなネットワーク。
3. ハーバード大学のウェブページからなるネットワーク。

彼らは、この「部分的な覗き見」法を「完全な待ち」法と比較しました。

• 発見： 「部分的な覗き見」法は、完全な方法とほぼ同じ精度の答えを出しました。
• トレードオフ： 時間を節約するために覗き見る数字を減らすと、答えに少し「ノイズ（ばらつき）」が生じますが（信頼区間が広くなる）、それでも非常に優れた結果でした。
• 勝利： システムの最も遅い部分が追いつくのを待たないことで、膨大な時間とコンピュータのリソースを節約できました。

まとめ

この論文は、巨大なネットワークにおける三角形のカウントを行うための、よりスマートな方法を紹介しています。大規模なコンピュータチームに対し、すべての詳細を共有し終えるまで待つことを強いるのではなく、コンピュータが非同期に動作し、ランダムで部分的な情報のみを共有することを可能にしました。

彼らは、この「怠慢な」アプローチが平均して正しい答えを導き出すことを数学的に証明し、実験を通じて、それが現実の世界でも非常によく機能することを明らかにしました。これにより、以前よりもはるかに高速に巨大なネットワークを分析することが可能になりました。