2014年に発表された論文
論文メモと言いつつ、どちらかというとグラフ信号処理のベースを勉強するために読んだ。なので主にその辺の話が多い（本稿でもほとんどそういう話で、提案手法っぽいところは短い。）
最終的に提案していることはproduct graphを使うと高速化できるし、グラフフーリエ変換を使うことでグラフデータを圧縮できるということだけを言っている。
Big Data Analysis with Signal Processing on Graphs
abst
- データの収集と分析は様々な分野で行われ重要
- 主な対象はソーシャルネットワーク、生物分子学、コマースやセキュリティなど。
- 有益な情報処理の方法としてDiscrete Signal Processing on graphs ($DSP_G$)を考える
- DSP_Gを従来の信号処理と照らし合わしながら考え、paralellizationとvectorizationに基づくproduct graphを検討する
intro
- 多次元データの表現は multi-way arraysを使った方法で分析される
- biomedical signal processing, array signal processing などなど
- 高次元データの低次元表現の手法として、graph Laplacianの固有基底が生成する低次元への射影がある
- これら低次元表現に対し、従来の信号処理を当てはめることでグラフ離散信号処理($DSP_G$)を行うことができる。
- 本論ではビッグデータへの応用を考える
Signal Processing on Graphs
DSP_Gの主なコンセプトについて説明
無向グラフ、有向グラフのどちらも考えます。
Graph Signals
Notation
$G = (V,{\bf A})$
$V$はノード集合で${v_0, \dots, v_{N-1}}$ 、${\bf A}$は重み付き隣接行列。$N$はノード数。
グラフ信号${\bf s}$を次のような写像で定義
\begin{align}
{\bf s} &: V \rightarrow \mathbb{C} \\
& v_n \rightarrow s_n \\
\end{align}
where\ {\bf s} = [s_0, \dots, s_{N-1}]^T \in \mathbb{C}^N
単に頂点と頂点ごとの特徴量を定義している。
グラフ例は原著(離散時間信号、センサーアレイ、Website、SNS)参照.
Graph Shift
離散信号処理では時間遅れオペレータを考える（信号処理では時間信号に対するz変換における基底$z^-1$。時系列モデリングで現れるラグオペレータを想像してもらいたい。)。信号処理ではサンプル時間Nでデータが周期していることを仮定する。（これはデータが有限長であることに起因するものであり、何らかの意味で都合のよい仮定ということではないことには注意）
$DSP_G$ではこの時間遅れオペレータを、あるノードに対して接しているノードとエッジの重みの和で考える。
\tilde s_n = \sum_{m \in \mathcal{N}_n}{\bf A}_{n,m} s_n
（グラフの時間発展は情報量の流入出なのでこの定義と思われる。）
グラフ信号${\bf s}$に隣接行列をかけることで表現できる。
\tilde {\bf s} = {\bf A}{\bf s}
つまり、隣接行列${\bf A}$がグラフ信号領域の時間遅れオペレータ。
他の定義も存在して、隣接ノードの平均でも良いが、これだとフィルタ処理や周波数の概念、フーリエ変換が導けなくなる。らしい。
Graph Filters and z-transform
フィルタリングを考える。
フィルタは線形時不変システム(LTI)を考えることと同義。（つまり線型性とシフト不変性を持つ、あと異なるフィルタを二つ持ってきて、A→Bとかけても、B→Aとかけても結果が変わらない）
z変換を考える。
(z変換はざっくりいうとラプラス変換の離散時間版で、離散時間信号（ベクトル）にz変換を施すと、次のスカラーの多項式でかける便利な性質があります。)
s(z^{-1}) = \sum_{n=0}^{N-1}s_n z^{-n}
$s(z^{-1})$はz領域の信号。(z変換はラプラス変換と同様の性質を持っているので、フィルタリング（フィルタ信号と解析信号の畳み込み）が掛け算になる性質も持っています。)
\tilde s(z^{-1}) = h(z^{-1})s(z^{-1}) {\rm mod} (z^{-N}-1)
$h(z^{-1})$はz領域のフィルタ。
さっきグラフ信号に対する時間遅れオペレータを定義した。z変換では$z^{-1}$が時間遅れオペレータなので、置き換えてやればよく、グラフフィルタ$h({\bf A})$は結局次のようになる。
h({\bf A}) =\sum_{n=0}^{L-1} h_l {\bf A}^l
先に説明した通りz領域のフィルタリングは掛け算なので、フィルタリングしたグラフ信号を得るには上のhをかけてあげれば良い。なお、逆グラフフィルタはサイズNの線型方程式の解として得られる。
また、グラフフィルタの最大タップ長は隣接行列${\bf A}$の最小多項式の次数に一致する。（最小多項式の話は圏論が出てくるのでよくわかりませんが、隣接行列のランク分だけしかフィルタの次数を確保できないイメージ。）
さらに、グラフフィルタは次式の通りに因数分解できる。
h({\bf A}) = h_{L-1} \prod_{l=0}^{L-1}({\bf A}-g_l{\bf I})
フィルタタップ長$L$は$N$より小さいこと。
（一次元の有限インパルス応答フィルタからのアナロジーで考えると、上の多項式から周波数特性におけるゼロ点が求まるので、上の多項式からグラフ周波数特性におけるゼロ点が求まる？？）
Graph Fourier Transfrom
（この辺調べたらいっぱい出てくるので雑に説明）
一般の（という言い方がいいのか）フーリエ変換は演算子の固有関数で関数展開するもの。
なのでグラフシフト演算子の固有関数を求め、それによってグラフ信号を展開するとグラフフーリエ変換になる。
具体的には隣接行列を固有値分解をして得られた固有ベクトル行列の逆行列がグラフフーリエ変換行列になる。逆変換行列は通常の固有ベクトル行列。
なおこの時の固有値はグラフ周波数領域における周波数に該当。
固有ベクトルの計算は時々不安定なのでラプラシアン行列の特異ベクトルなども利用できる。が、元のグラフが無向グラフであることをを仮定しなければならない。
Frequency Responce of Graph Filters
（グラフ周波数領域のフィルタリングについても最近GCNの流行で調べたらいっぱい出てくると思うので雑に）
ざっくりいうと、グラフ周波数領域ではフィルタリング（畳み込み）が掛け算になるので、グラフ周波数ごとに直接次のようにフィルタリングすることになる。
h(\lambda_n)=\sum_{l=0}^{L-1}h_l \lambda_n^l
この$h(\lambda_n)$がグラフフィルタのグラフ周波数応答になる。（なるんか・・・？大事なところなんだけどここだけ信号処理とのアナロジーになっていない気がして、スッキリ行かない。）
Low and High Frequency on Graphs
DSPでは、時系列や画像を正弦波で特徴付けている。周波数はこの正弦波の周波数に一致する。
グラフの周波数成分もこのアナロジーから低い周波数と、高い周波数で特徴付けられる。
グラフの周波数はグラフ全体の変化の割合で見ればよく、すなわち、特定の周波数で、どのくらい信号が各々のノードで変化しているかを見れば良い。結果的にはその変化の大きさは固有値の降順に一致する。（複素数なら絶対値）
Applications
- データ圧縮, 復元, デノイジング， 分類などなど
- 一例としては欠測や破損データの検出ができる。
- 時系列ならハイパスフィルタで抽出でき、グラフならグラフハイパスフィルタで検出できる。
Challenges of Big Data
ビッグデータに共通に言われる特徴はデータのボリューム、速度、多様さである。
これらの特徴ごとに課題が考えられる。
処理されるデータのボリュームは効率的な分散かつスケーラブルなストレージである必要があるし、継続的にデータが蓄積される。
新しいデータの処理には高速なアルゴリズムが要求される。
しかも収集されたデータは数字、文字、視覚データなど様々な種類がある。
$DSP_G$はこのデータの多様性に対して効果的である。
一方で従来の信号処理の手法では、データ処理の速度という面では劣っている。
ここでグラフ信号とグラフフィルタのことを考える。
グラフフィルタリングには計算として$O(LN^2)$必要になる。
また${\bf A}$がスパースで$K$程度の要素しかないときはあるときには$O(LNK)$になる。メモリ空間も同様に使用する。
加えてグラフフーリエ変換は$O(N^2)$のオーダーで計算される。固有値分解を行えば$O(N^３)$のオーダーとなる。グラフフィルタリングは$N^２$のオーダーだが固有値分解を要求する。当然これらの計算オーダーはビッグデータでは看過できない。
なので本論ではFFTを用いた方法によ$DSP_G$の実装を検討する。
モデルはproduct graphを採用する。
Product Graphs
グラフの直積。
グラフ1,2を考える$G_1=(V_1, {\bf A}_1),G_2=(V_2, {\bf A}_2)$
この時のproduct graphを次のように考える。
G=G_1\diamond G_2=(V,{\bf A}_\diamond)
ここでノード$V$は$|V|=N_1N_2$を満たす。隣接行列${\bf A}_\diamond$は$N_1N_2\times N_1N_2$の行列になる。products graphはクロネッカー積、直積、strong productの三つがある。
Kronecker product graphはproduct graphとして得られる隣接行列をクロネッカー積で表す。
{\bf A}_\otimes = {\bf A}_1\otimes {\bf A}_1
なお、行列のクロネッカー積は次のようになる。
{\bf B} \in \mathbb{C}^{M\times N}\\
{\bf C} \in \mathbb{C}^{K\times L}\\
{\bf B} \otimes {\bf C} = \left[
\begin{array}[ccc]
bb_{0,0}{\bf C}& \dots & b_{0,N-1}{\bf C} \\
\vdots& \vdots & \vdots \\
b_{M-1,0}{\bf C}& \dots & b_{M-1,N-1}{\bf C}
\end{array}
\right]
Cartesian product graph$G_1\times G_2$は次式
{\bf A}_\times = {\bf A}_1\otimes {\bf I}_{N_1} + {\bf I}_{N_2} \otimes {\bf A}_2
strong product$G=G_1\boxtimes G_1$ は次式
{\bf A}_\boxtimes = {\bf A}_1 \otimes {\bf A}_2 + {\bf A}_1 \otimes {\bf I}_{N_1} + {\bf I}_{N_2} \otimes {\bf A}_2
strong productはKroneckerとCartesianの和
これらのproduct graph表現の分解の手法もいくつか検討されている。
Product graphは様々な表現ができる。（図例が本文中にあり）
- 従来のDSPと比べると、画像や映像のような多次元信号はCartesian product graphで表現することができる。
- マルチセンサーアレイでは、センサーアレイ間の関係を無向グラフ、時間方向の遷移を有向グラフで書くとすると、各々の情報をstrong productで表現できる。
- ソーシャルネットワークにおける、各々のコミュニティ内の関係と、コミュニティ間の関係を異なるグラフで表し、全体をその二つのグラフのCartesian product graphで近似できる。
Signal Processing on Product Graph
ここではproduct graphがグラフフィルタとグラフフーリエ変換のモジュール化に寄与することを説明する。
product graphはグラフフィルタリングとグラフフーリエ変換を並列化することに寄与する。
(多分proposedなので大事だが疲れたのでざっくり)
- 行列演算は並列化できるし、ベクトル化できるから早いよ
- グラフフーリエ変換するときもproduct graphの要素になるグラフごとから得た複数の変換行列のクロネッカー積で書いてもいいから全体の隣接行列を固有値分解しなくてもいいよ
（色々数式で説明してあるが、上までの式が終えてたらほぼ自明な計算しかしてないので特に載せない。）
Example Application
１５０地点×365日の気温を地点のグラフと時間のグラフのproduct graphで表現。さらにgraph fourier変換し、いくつかの成分のみ残して復元した結果1/50程度の数のフーリエ係数で元のグラフを95%再現できる。1/3程度使用すれば99.3%は再現できることがわかった。
感想
Big Data "Analysis"というのは少し違った気がする。
次はDiscrete Signal Processing on Graphs: Frequency Analysisを読もうと思います。
2019/07/01 上の論文を読みましたが目立って紹介することもなかったので特に紹介記事は書かないことにしました。