ビッグデータがグラフ理論を新たな次元へと導いた方法

グラフ理論だけでは不十分です。

つながりを論じる数学的言語は、通常、ネットワーク、つまり頂点（点）と辺（それらを結ぶ線）に基づいており、少なくとも18世紀以来、現実世界の現象をモデル化する上で非常に貴重な手段となってきました。しかし数十年前、巨大なデータセットの出現により、研究者はツールボックスの拡張を余儀なくされ、同時に、新たな数学的洞察を適用するための広大なサンドボックスが与えられました。コロラド大学ボルダー校のコンピュータ科学者、ジョシュ・グロコウ氏によると、それ以来、ビッグデータのノイズの中から複雑な構造やシグナルを見つけることができる新しい種類のネットワークモデルが研究者によって開発され、急速な成長を遂げてきました。

グロコウ氏も、ビッグデータにおけるつながりの発見においてグラフ理論には限界があると指摘する研究者の一人です。グラフはあらゆる関係性を二者関係、つまり相互作用のペアとして表現します。しかし、多くの複雑なシステムは二者関係だけでは表現できません。この分野における最近の進歩は、今後の展望を示しています。

子育てのネットワークモデルを構築してみることを考えてみましょう。明らかに、それぞれの親は子供と繋がりを持っていますが、グラフ理論がモデル化するような、子育て関係は単なる二つの繋がりの合計ではありません。これは、同調圧力のような現象をモデル化する場合にも当てはまります。

「直感的に理解できるモデルは数多くあります。社会力学における仲間からのプレッシャーの影響を捉えられるのは、データに既にグループが含まれている場合のみです」と、ドイツのアーヘン工科大学のレオニー・ノイホイザー氏は述べています。しかし、バイナリネットワークではグループの影響を捉えることができません。

数学者やコンピュータ科学者は、二項対立的なつながりではなく、集団のダイナミクスが個々の行動に及ぼす複雑な影響を説明するために、「高次相互作用」という用語を使用します。これらの数学的現象は、量子力学におけるエンタングルメント相互作用から、集団を介した病気の蔓延の軌跡まで、あらゆるものに現れます。例えば、薬理学者が薬物相互作用をモデル化したい場合、グラフ理論は2種類の薬物がどのように反応するかを示すことができますが、3種類、あるいは4種類の場合はどうでしょうか？

こうした相互作用を探索するためのツール自体は新しいものではないが、高次元データセットが発見のエンジンとなり、数学者やネットワーク理論家に新たなアイデアを与えたのは近年のことである。こうした取り組みは、グラフの限界やスケールアップの可能性について興味深い結果をもたらしてきた。

「ネットワークは物事の影に過ぎないことが分かりました」とグロチョウ氏は述べた。データセットが複雑な基礎構造を持つ場合、グラフとしてモデル化しても全体像の限定的な投影しか明らかにならない可能性がある。

「数学的な観点から物事を研究するために使用してきたデータ構造は、データで観察されるものとあまり一致していないことに私たちは気づいた」とパシフィック・ノースウエスト国立研究所の数学者エミリー・パーバイン氏は語った。

そのため、数学者、コンピュータ科学者、その他の研究者は、グラフ理論（その様々な形態）を一般化し、高階現象を探求する方法にますます焦点を当てています。ここ数年、こうした相互作用を特徴づけ、高次元データセットにおいて数学的に検証する方法が次々と提案されてきました。

パーヴァイン氏にとって、高次相互作用の数学的探究は、新たな次元のマッピングのようなものだ。「グラフを二次元的な土地の土台と考えてみてください」と彼女は言う。その上に建てられる三次元的な建物は、それぞれ大きく異なる可能性がある。「地上から見るとどれも同じに見えますが、その上に構築するものは異なります。」

ハイパーグラフに入る

こうした高次元構造の探索は、数学が特に複雑かつ興味深い領域となる部分です。例えば、グラフの高次元版はハイパーグラフと呼ばれ、エッジの代わりに「ハイパーエッジ」を持ちます。ハイパーエッジは複数のノードを接続できるため、多方向（または多重線形）の関係を表すことができます。ハイパーエッジは直線ではなく、3箇所以上に杭を打ち込んだ防水シートのような面として捉えられるかもしれません。

それはそれで良いのですが、これらの構造が従来の構造とどのように関係しているかについては、まだ多くのことが分かっていません。数学者は現在、グラフ理論のどの規則が高階相互作用にも適用されるかを研究しており、新たな探究分野が示唆されています。

ハイパーグラフがビッグデータセットからどのような関係性を引き出せるか（そして通常のグラフでは引き出せない関係性）を説明するために、パーヴァイン氏は身近な例として科学出版の世界を挙げています。2つのデータセットがあり、それぞれ最大3人の数学者が共著した論文が含まれているとします。分かりやすくするために、これらをA、B、Cと名付けましょう。一方のデータセットには6本の論文が含まれており、それぞれ3つの異なるペア（AB、AC、BC）による論文が2本ずつ含まれています。もう一方のデータセットには、3人の数学者全員が共著した論文が2本だけ含まれています（ABC）。

どちらのデータセットから得られた共著関係のグラフ表現も三角形のように見えるかもしれません。これは、各数学者（3つのノード）が他の2人（3つのリンク）と共同研究していたことを示しています。もし誰が誰と共同研究していたかだけが問題であれば、ハイパーグラフは必要ない、とパーバイン氏は言います。

しかし、ハイパーグラフがあれば、それほど明白ではない構造に関する疑問にも答えることができます。例えば、最初のセット（論文6本）のハイパーグラフには、各数学者が4本の論文に貢献したことを示すハイパーエッジが含まれる可能性があります。2つのセットのハイパーグラフを比較すると、最初のセットでは論文の著者が異なりますが、2番目のセットでは同じであることがわかります。

野生のハイパーグラフ

このような高階手法は、応用研究において既に有用であることが証明されています。例えば、生態学者たちは1990年代にイエローストーン国立公園にオオカミが再導入された際に、生物多様性と食物連鎖の構造にどのような変化が生じたかを示しました。また、最近の論文では、パーヴァイン氏らは、ウイルス感染に対する生物学的反応のデータベースを分析し、ハイパーグラフを用いて最も重要な遺伝子を特定しました。彼らはまた、グラフ理論による通常のペアワイズ分析では、これらの相互作用が見逃されていたであろうことを示しました。

「ハイパーグラフには、グラフの域を超えた力があると考えています」とパーバイン氏は語った。

しかし、グラフからハイパーグラフへの一般化はすぐに複雑になります。これを説明する一つの方法は、グラフ理論の標準カット問題を考えることです。これは、「グラフ上の2つの異なるノードが与えられたとき、2つのノード間のすべての接続を完全に切断するために、最小で何本のエッジをカットできるか」という問いです。多くのアルゴリズムは、与えられたグラフに対して最適なカット数を容易に見つけることができます。

しかし、ハイパーグラフの切断はどうでしょうか？「この切断の概念をハイパーグラフに一般化する方法はたくさんあります」とコーネル大学の数学者オースティン・ベンソンは述べています。しかし、ハイパーエッジは様々な方法で切断され、新たなノードのグループが生成される可能性があるため、明確な解決策は一つではないと彼は言います。

ベンソンは最近、2人の同僚と共に、ハイパーグラフを分割する様々な方法を形式化しようと試みました。その結果、様々な計算複雑性が示唆されました。状況によっては、問題は多項式時間で容易に解けました。これは基本的に、コンピューターが妥当な時間で解を処理できることを意味します。しかし、他の状況では、問題は基本的に解けない、つまり解が存在するかどうかを確実に知ることは不可能でした。

「まだ多くの未解決の疑問が残っています」とベンソン氏は述べた。「これらの不可能性の結果の中には、グラフに還元することが不可能であるという点が興味深いものがあります。そして理論的な観点から言えば、グラフで発見できるような結果に還元できていないということは、そこに何か新しいものがあることを示しています。」

数学的サンドイッチ

しかし、ハイパーグラフは高階相互作用を探求する唯一の方法ではありません。位相幾何学（物体を引き伸ばしたり、圧縮したり、その他の変形を加えても変化しない幾何学的特性を数学的に研究する学問）は、より視覚的なアプローチを提供します。位相幾何学者はネットワークを研究する際に、形状、面、次元を探します。2つのノードを結ぶ辺が1次元であることに気づき、異なるネットワークにおける1次元物体の特性について疑問を持つかもしれません。あるいは、3つのノードを結ぶことで形成される2次元の三角形の面を見て、同様の疑問を持つかもしれません。

位相幾何学者はこれらの構造を単体複体と呼びます。これらは、事実上、位相幾何学の枠組みを通して見たハイパーグラフです。機械学習の一般的なカテゴリーに分類されるニューラルネットワークは、その好例です。ニューラルネットワークは、人間の脳のニューロンが情報を処理する方法を模倣するように設計されたアルゴリズムによって駆動されます。グラフニューラルネットワーク（GNN）は、物体間の接続を2つ1組の接続としてモデル化し、大規模なデータセットから欠落しているデータを推測することに優れていますが、他のアプリケーションと同様に、3つ以上のグループからのみ発生する相互作用を見逃す可能性があります。近年、コンピューター科学者は、高階複体を用いてGNNのアプローチを一般化し、これらの効果を発見する単体ニューラルネットワークを開発しました。

単体複体は位相幾何学とグラフ理論を結びつけ、ハイパーグラフと同様に、将来の研究を牽引する魅力的な数学的問題を提起します。例えば位相幾何学では、単体複体の特殊な部分集合はそれ自体も単体複体であり、したがって同じ性質を持ちます。もしハイパーグラフにも同じことが当てはまるとすれば、部分集合にはその中のすべてのハイパーエッジ、つまり埋め込まれたすべての双方向エッジが含まれることになります。

しかし、必ずしもそうとは限りません。「現在私たちが目にしているのは、データがこの中間領域に陥っているということです。つまり、すべてのハイパーエッジ、すべての複雑な相互作用が、他のすべてと同じサイズではないということです」とパーヴァイン氏は言います。「三者間相互作用はあり得ますが、二者間相互作用はあり得ません。」ビッグデータセットは、生物学的シグナル伝達ネットワークであれ、同調圧力のような社会的行動であれ、集団の影響力が個人の影響力をはるかに上回ることが多いことを明確に示しています。

パーヴァイン氏は、データは一種の数学的なサンドイッチの真ん中を埋めているかのように表現し、その上部は位相幾何学の考え方によって、下部はグラフの限界によって束縛されていると述べている。ネットワーク理論家は今、高階相互作用の新たなルールを見つけるという課題に直面している。そして数学者には「まだ活躍の余地がある」と彼女は述べた。

ランダムウォークと行列

創造的な「遊び」の感覚は他のツールにも及んでいます。グラフとデータ記述のための他のツールの間には、様々な美しいつながりが存在します、とベンソン氏は言います。「しかし、より高次の設定に移ると、こうしたつながりを見つけるのは難しくなります。」

これは、マルコフ連鎖の高次元版を考えてみると特に明らかだと彼は述べた。マルコフ連鎖は、次の段階が要素の現在の位置のみに依存する多段階のプロセスを表す。研究者たちは、情報、エネルギー、さらにはお金などがシステム内をどのように流れるかをマルコフモデルを用いて説明してきた。マルコフ連鎖の最もよく知られた例は、おそらくランダムウォークだろう。これは、各ステップが前のステップからランダムに決定される経路を表す。ランダムウォークはまた、特定のグラフでもある。グラフに沿った任意のウォークは、リンクに沿ってノードからノードへと移動するシーケンスとして表すことができる。

しかし、歩くという単純な動作をスケールアップするにはどうすればいいのでしょうか？研究者たちは、現在の位置だけでなく、過去の状態を多く考慮できる高次マルコフ連鎖に注目しています。このアプローチは、ウェブ閲覧行動や空港の交通流といったシステムのモデリングに有効であることが証明されています。ベンソン氏は、この手法を拡張する他の方法についてもアイデアを持っています。彼と彼の同僚は最近、高次マルコフ連鎖とテンソルと呼ばれる別のツールを組み合わせた、確率的（ランダム）プロセスの新しいモデルを発表しました。彼らは、ニューヨーク市のタクシー乗車のデータセットに対してこのモデルをテストし、軌道予測の精度を調べました。結果はまちまちでした。彼らのモデルは通常のマルコフ連鎖よりもタクシーの動きをうまく予測しましたが、どちらのモデルもあまり信頼できるものではありませんでした。

テンソル自体は、近年注目を集めるようになった高次相互作用を研究するための新たなツールです。テンソルを理解するには、まず行列を思い浮かべてください。行列は、データを行と列の配列に整理するものです。次に、行列で構成された行列、あるいは行と列だけでなく、深さなどのデータの次元も持つ行列を想像してみてください。これらがテンソルです。もしすべての行列が音楽のデュエットに対応するとしたら、テンソルはあらゆる楽器の構成を網羅することになります。

テンソルは物理学者にとって目新しいものではありません。彼らは長年、例えば粒子の様々な量子状態を記述するためにテンソルを用いてきました。しかし、ネットワーク理論家はこのツールを、高次元データセットにおける行列の威力を拡張するために採用しました。そして数学者たちは、テンソルを用いて新たな種類の問題を解明しようとしています。グロコウはテンソルを用いて同型性問題を研究しています。同型性問題は、本質的には、2つの物体が何らかの点で同じかどうかをどのようにして判断するかという問題です。グロコウは最近、喬有明と共同で、解決が困難あるいは不可能となる可能性のある複雑な問題を特定する新たな方法を生み出しました。

責任あるハイパーグラフ化の方法

ベンソンの結論の出ないタクシーモデルは、普遍的な疑問を提起する。研究者はハイパーグラフのようなツールを実際にいつ必要とするのか？ 多くの場合、適切な条件下では、ハイパーグラフはグラフと全く同じ種類の予測と分析を提供する。「何かが既にネットワークにカプセル化されている場合、システムを（高階として）モデル化する必要は本当にあるのだろうか？」とアーヘン工科大学のマイケル・シャウブは問う。

それはデータセット次第だと彼は言った。「グラフはソーシャルネットワークの抽象化には適していますが、ソーシャルネットワークはそれだけではありません。高階システムでは、モデル化の方法がさらに増えます。」グラフ理論は、例えば個人がどのようにつながっているかを示すことはできますが、ソーシャルメディア上の友人集団が互いの行動にどのように影響を与えているかを捉えることはできません。

同じ高次相互作用がすべてのデータセットに現れるわけではないため、不思議なことに、新しい理論はデータによって推進されます。これは、パーヴァイン氏がそもそもこの分野に惹かれた根底にある論理的感覚に疑問を投げかけるものです。「数学の好きなところは、論理に基づいていて、正しい方向に従えば正しい答えにたどり着けることです。しかし、全く新しい数学の分野を定義する際には、何が正しいやり方なのかという主観が入り込むことがあります」と彼女は言います。「そして、複数のやり方があることを認識しなければ、コミュニティを間違った方向に導いてしまう可能性があります。」

グロチョウ氏は、これらのツールは究極的には一種の自由を意味すると述べた。研究者がデータをより深く理解できるようにするだけでなく、数学者やコンピューター科学者が新たな可能性の世界を探求することを可能にするのだ。「探求すべきものは無限にあります。それは興味深く、美しく、そして多くの素晴らしい疑問の源となるのです。」

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、 シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。

WIREDのその他の素晴らしい記事

• 📩 テクノロジー、科学などの最新情報: ニュースレターを購読しましょう!
• ハリネズミのインスタグラムのダークサイド：羽根ペンのように見える
• ロボットが溢れる農業の未来は悪夢か、それともユートピアか?
• 自動的に消えるメッセージを送信する方法
• ディープフェイクがビジネスに活用される
• カーゴパンツを復活させる時が来た
• 👁️ 新しいデータベースで、これまでにないAIを探索しましょう
• 🎮 WIRED Games: 最新のヒントやレビューなどを入手
• 🏃🏽‍♀️ 健康になるための最高のツールをお探しですか？ギアチームが選んだ最高のフィットネストラッカー、ランニングギア（シューズとソックスを含む）、最高のヘッドフォンをご覧ください