統計学輪講 第18回

スペクトルグラフ疎化とはエネルギー関数を近似しながらグラフの辺数を削減する手法で，近年はそのハイパーグラフへの拡張が注目を集めている．その難しさは，通常のグラフと異なりエネルギー関数の定義中に非線形演算が現れる点にある．これに対し，ハイパーグラフの構造を用いたチェイニングを行うことで（頂点数nに関する依存性がpolylogを除いて）タイトな評価を得られることが示されている．
本発表では，Oko, Sakaue & Tanigawa (2022) による有向ハイパーグラフに対するO*(n^2)サイズの疎化を主に取り上げる．これは Koutis & Xu (2014) のスパナーを用いたグラフ疎化に着想を得て，有向ハイパーグラフにおけるスパナーの対応物となるハイパー辺集合を考え，これを選んで残りのハイパー辺をランダムにサンプルすることを繰り返すことで得られる．このようにアルゴリズムは比較的シンプルであるが，解析ではスパナーの対応物の存在の事実と組合せ論的考察に基づいてチェイニングの離散化写像の構成を行う必要がある．
また，Kapralov, Krauthgamer, Tardos & Yoshida (2021) によるweight balancingを用いた一般の無向ハイパーグラフに対するO^*(n)サイズの疎化や，他の離散構造への応用，更なる改善といった直近の進展を概観する．

参考文献: Oko Kazusato, Shinsaku Sakaue, and Shin-ichi Tanigawa. “Nearly Tight Spectral Sparsification of Directed Hypergraphs by a Simple Iterative Sampling Algorithm.” arXiv preprint arXiv:2204.02537 (2022).