はじめに

この記事は「ただただアウトプットを癖付けるための Advent Calendar 2024」に投稿した記事です。

最初の記事にも書いた通り、私は生物物理の実験を専門にしている研究者です。
最近はデータ解析のため機械学習のコード開発も行っており、幸いにもその成果がNeurIPSに採択されました。

アドベントカレンダー5日目の記事では、EVOという遺伝子配列生成AIの論文紹介をおこないました。
10日目の今回は、趣向を変えて、ハイパーグラフと層という論文を紹介します。
私自身、グラフニューラルネットワークは扱ったことがあります。ハイパーグラフはその発展形として、少し学んでいるテーマでした。
また、ここ数年は抽象数学のほうにも手を伸ばしたいと思っており、層はそのなかで触れたテーマです。
ただ、層はまだまだ理解が浅く、具体的な意味がイメージしづらい状況でしたので、この論文を読むことでその理解も深めたいと思いました。

関連記事

前の記事「生物物理屋がローカルLLMでサーベイ論文生成を試してみた話」

次の記事「生物物理屋が日本語LLMを試してみた話」

TL;DR

層(sheaf)とのアナロジーを用いてハイパーグラフニューラルネットワークの演算を拡張しました。大まかにはハイパーグラフラプラシアンの途中に線形写像を導入したものです。これにより、ハイパーグラフにおけるベンチマークテストの精度が向上しました。

論文

Sheaf Hypergraph Networks

こちらはarXivに投稿されたプレプリントです。とは言ってもNeurIPS2023にポスターとして採択されています。
その際のポスターと、著者による解説動画はこちらです。

誰が書いたのか

ケンブリッジ大とローマ大所属の著者が各2人ずつ、計4人で書かれています。

用語など

グラフとは

平たい言葉でいうとネットワークです。
点と、それを結ぶ線からなるもので、点をノード、線をエッジと呼びます。
この線に向きがある場合（矢印になる）は有向グラフ、ない場合は無向グラフと呼びます。
ただし、無向グラフも双方向に矢印があると考えることで、有向グラフの特別な場合として扱うこともできます。

ハイパーグラフとは

ハイパーグラフは、エッジが2つのノードではなく、任意の数のノードを結ぶものです。
エッジはもはや線ではなく、面になります。
このようなハイパーグラフは、3つ以上のノードが関連するようなデータを表現するのに適しています。

層 (Sheaf) とは

以下、層の定義はwikipediaの記述を参照しています。前に学んだときと大体同じだったはず。。
層は、数学的な概念で、位相空間における連続関数の局所的な性質を記述するものです。
まず、ある位相空間の開集合$U$に対して、集合$\mathcal{F}(U)$を割り当てます。
もし開集合$U$が開集合$V$に含まれる($U\subset V$)ならば、制限写像(resriction map)$\rho_U^V : \mathcal{F}(V) \to \mathcal{F}(U)$が存在します。
このとき、$\rho_U^U$が恒等写像であって、$U\subset V\subset W \Rightarrow \rho_U^V \circ \rho_V^W = \rho_U^W$を満たすなら、$\mathcal{F}$は前層であるといいます。
ここで、各開集合$U$に対して$\mathcal{F}(U)$の元$s$を、$U$上の層の切断といいます。
制限写像はこの切断にも作用し$V$上の切断$s$に対して、$s|_U=\rho_U^V(s)$を$s$の$U$への制限といいます。

前層が層であるための条件は、この切断と関係してきます。
位相空間$X$の開被覆(重複してもいいから$X$全体を覆いつくすようにとった、$X$の開集合の集まり)をとります。この開被覆全体を$U$と書きます。集合としては$X$と等しいはず。

$\mathcal{F}(U)$の元$s,t$を取ります。開被覆から任意の開集合$U_¥lambda$をとったとき、そこでの2つの制限$s|{U_¥lambda}=t|{U_¥lambda}$が等しいならば$s=t$である。
各開集合$U_\lambda$に対して$s_\lambda\in\mathcal{F}(U_\lambda)$を取ります（切断の族）。これらについて、開集合の共通部分への制限が常に等しい($s_\lambda|{U\lambda\cup U_\mu}=s_\mu|{U\lambda\cup U_\mu}$)ならば、$\mathcal{F}(U)$の元$s$があって$s|{U\lambda}=s_\lambda$を満たす。
これらの条件を満たす前層を層といいます。
1)の条件を一言でいうと、グローバルな情報が局所的な情報の張り合わせのみで表現できるということです。局所的な情報をすべてかき集めたらグローバルな情報を表現するのに十分であり、他の情報は不要ということです。
2)の条件は、局所的な情報が重なる部分で一致するということです。こちらは基本的に制限写像の性質への要請です。

と、ここまで書いていてなんなのですが、この論文で用いられている層はCellular Sheafというもので、上記の定義とは異なるもののようです。
実際、グラフにおけるエッジの集合は開集合の性質を満たさないため、上記の定義をそのまま適用することはできません。
Cellular Sheafは、どうやらトポロジカルデータ解析でも使われるもののようですが、私はまだよくわかっていません。
（これについての詳しい話は、また後々補完出来たらと思います。）

この論文で実装されたもの

Sheaf Hypergraphの演算

この論文のハイパーグラフでも、ノードに特徴量を持たせています。
この特徴量をハイパーエッジに伝達し、ハイパーエッジに含まれるノードに戻すという演算をおこなっています。
このノードとハイパーエッジの特徴量は$\mathbb{R}^d$の元です。
層との対応関係でいうと、（上でも述べた通り厳密には違いますが）ノードとハイパーエッジが開集合に対応し、$\mathbb{R}^d$がそれに割り当てられた集合に対応します。
制限写像は、ハイパーエッジの特徴量からノードへの線形写像です。これは$\mathbb{R}^{d\times d}$の行列で表現されます。
一方で、ノードからハイパーエッジへの写像は、ノードの特徴量をハイパーエッジに伝達するものです。これは同じハイパーエッジからノードへの写像の転置行列で表現される線形写像として定義されています。これは層にはなかった演算です。

Sheaf Hypergraph Laplacian

ハイパーグラフラプラシアンを、上記の演算によって拡張しています。
ハイパーグラフラプラシアンは、元々は同じハイパーエッジに属するノード同士の特徴量の差をそのまま計算するものです。
これをあるノードについて、そのノードが属するハイパーエッジのそれぞれ、さらにそこに属する他のノードそれぞれとの各ペアについて計算し、それを足し合わせることで、ハイパーグラフラプラシアンを定義しています。
Sheaf Hypergraph Laplacianは、このハイパーグラフラプラシアンを、ハイパーエッジとノードの特徴量の伝達演算を用いて拡張したものです。
ハイパーエッジ上で差を計算する前に制限写像を適用し、ハイパーエッジ上の差の総和をノードに戻す前に伝達演算を適用することで、ハイパーグラフラプラシアンを拡張しています。
ただの差ではないことによって、伝達における特徴量の重みを考慮した演算が可能になります。
特に、制限写像がフルランクでなく、固有値ゼロを持つものである場合には、その固有ベクトルに対応する成分が消去されて伝達されることになります。ある種の情報の取捨選択と言えそうです。

Sheaf Hypergraph Neural Network

ハイパーグラフラプラシアンを用いて、ノードの特徴量を更新するネットワークを定義しています。
各ノードの属するハイパーエッジの数からなる行列によって、shef hypergraph laplacianを規格化し、ノード個数を次元に持つ単位行列から引いたものを用います。
これに学習対象のパラメータ行列をかけ、活性化関数を適用することで、ノードの特徴量を更新します。

これによって、ハイパーグラフにおけるベンチマークテストの精度が向上したことが報告されています。

まとめ

この論文では、層を用いてハイパーグラフの演算を拡張しました。
ハイパーグラフラプラシアンを拡張することで、ハイパーグラフにおけるベンチマークテストの精度が向上しました。
気になるのは、この定義において、ノードとハイパーエッジの特徴量の次元を揃える必要はあるのか、という点です。
もちろん、より簡単な定義をおこなうという意味では、次元を揃えることは自然なことです。
ただ、今後の拡張として、次元を変える定義も可能ではあると思います。制限写像を非正方行列にすればいいわけです。
さらに言えば、需要はともかくとして、各ノードの次元を揃える必要もないように思います。
特に前者については、ハイパーエッジの特徴量の次元をノード特徴量の次元より低くすれば、前述した情報の取捨選択を最初から含めておくことができると思います。
このような拡張が可能であるかどうか、またその場合の性質についても、今後の研究が期待されます。