Графовое преобразование Фурье

В математике — преобразование Фурье графа это математическое преобразование , которое разлагает матрицу Лапласа графа на собственные значения и собственные векторы . Аналогично классическому преобразованию Фурье , собственные значения представляют частоты , а собственные векторы образуют так называемый базис графа Фурье .

Графовое преобразование Фурье играет важную роль в теории спектральных графов . Он широко применяется в недавних исследованиях алгоритмов обучения со структурой графов , таких как широко используемые сверточные сети .

Определение

Учитывая неориентированный взвешенный граф $G=(V,E)$, где $V$ представляет собой набор узлов с $|V|=N$ ( $N$ количество узлов) и $E$ это набор ребер, сигнал графа $f:V\rightarrow \mathbb {R}$ — функция, определенная в вершинах графа $G$. Сигнал $f$ отображает каждую вершину $\{v_{i}\}_{i=1,\ldots ,N}$ на действительное число $f(i)$. Любой графический сигнал можно спроецировать на собственные векторы матрицы Лапласа. $L$. Позволять $\lambda _{l}$ и $\mu _{l}$ быть $l_{\text{th}}$ собственное значение и собственный вектор Лапласа матрицы $L$ (собственные значения отсортированы в порядке возрастания, т.е. $0=\lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{N-1}$), графовое преобразование Фурье (GFT) ${\hat {f}}$ графического сигнала $f$ на вершинах $G$ это расширение $f$ с точки зрения собственных функций $L$. Он определяется как:

${\mathcal {GF}}[f](\lambda _{l})={\hat {f}}\left(\lambda _{l}\right)=\langle f,\mu _{l}\rangle =\sum _{i=1}^{N}f(i)\mu _{l}^{*}(i),$

где $\mu _{l}^{*}=\mu _{l}^{\text{T}}$.

С $L$ — действительная симметричная матрица , ее собственные векторы $\{\mu _{l}\}_{l=0,\cdots ,N-1}$ образуют ортогональный базис . Следовательно, существует обратное графовое преобразование Фурье (IGFT), и оно записывается как:

${\mathcal {I}}{\mathcal {G}}{\mathcal {F}}[{\hat {f}}](i)=f(i)=\sum _{l=0}^{N-1}{\hat {f}}(\lambda _{l})\mu _{l}(i)$

Аналогично классическому преобразованию Фурье , преобразование Фурье графа позволяет представить сигнал в двух разных областях: вершинной области и спектральной области графа . Обратите внимание, что определение графового преобразования Фурье и его обратного преобразования зависит от выбора собственных векторов Лапласа, которые не обязательно являются уникальными. Собственные векторы нормализованной матрицы Лапласа также являются возможной основой для определения прямого и обратного преобразования Фурье графа.

Характеристики

Личность Парсеваля

Соотношение Парсеваля справедливо для преобразования Фурье графа: то есть для любого $f,h\in \mathbb {R} ^{N}$

$\langle f,h\rangle =\langle {\hat {f}},{\hat {h}}\rangle .$

Это дает нам личность Парсеваля :

$\sum _{i=1}^{N}|f(i)|^{2}=\|f\|_{2}^{2}=\langle f,f\rangle =\langle {\hat {f}},{\hat {f}}\rangle =\|{\hat {f}}\|_{2}^{2}=\sum _{l=0}^{N-1}\left|{\hat {f}}\left(\lambda _{l}\right)\right|^{2}.$

Обобщенный оператор свертки

Определение свертки между двумя функциями $f$ и $g$ не может быть напрямую применено к графическим сигналам, поскольку трансляция сигнала не определена в контексте графов. Однако, заменяя комплексный экспоненциальный сдвиг в классическом преобразовании Фурье собственными векторами Лапласа графа, свертку двух сигналов графа можно определить как:

$(f*g)={\mathcal {I}}{\mathcal {G}}{\mathcal {F}}[{\mathcal {G}}{\mathcal {F}}[f]\cdot {\mathcal {G}}{\mathcal {F}}[g]],$

$(f*g)(i)=\sum _{l=0}^{N-1}{\hat {f}}(\lambda _{l}){\hat {g}}(\lambda _{l})\mu _{l}(i).$

Свойства оператора свертки

Обобщенный оператор свертки удовлетворяет следующим свойствам:

• Обобщенная свертка в вершинной области — это умножение в спектральной области графа: ${\widehat {f*g}}={\hat {f}}{\hat {g}}.$
• Коммутативность : $f*g=g*f$
• Дистрибутивность : $f*(g+h)=f*g+f*h$
• Ассоциативность : $(f*g)*h=f*(g*h)$
• Ассоциативность со скалярным умножением: $\alpha (f*g)=(\alpha f)*g=f*(\alpha g)$, для любого $\alpha \in \mathbb {R}$.
• Мультипликативное тождество : $f*g_{0}=f$, где $g_{0}(i)=\sum _{l=0}^{N-1}\mu _{l}(i)$ является тождеством обобщенного оператора свертки.
• Сумма обобщенной свертки двух сигналов равна произведению сумм двух сигналов на константу:

$\sum _{i=1}^{N}(f*g)(i)={\sqrt {N}}{\hat {f}}(0){\hat {g}}(0)={\frac {1}{\sqrt {N}}}\left[\sum _{i=1}^{N}f(i)\right]\left[\sum _{i=1}^{N}g(i)\right].$

Обобщенный оператор перевода

Как уже говорилось ранее, классический оператор перевода $T_{v}$ не может быть обобщено на настройку графика. Один из способов определить оператор обобщенного перевода — использовать обобщенную свертку с дельта-функцией с центром в вершине. $n$: $\left(T_{n}f\right)(i)={\sqrt {N}}\left(f*\delta _{n}\right)(i){=}{\sqrt {N}}\sum _{l=0}^{N-1}{\hat {f}}\left(\lambda _{l}\right)u_{l}^{*}(n)u_{l}(i),$

где $\delta _{i}(n)={\begin{cases}1,&{\text{if }}i=n,\\0,&{\text{otherwise.}}\end{cases}}$

Константа нормализации ${\sqrt {N}}$ гарантирует, что оператор перевода сохраняет среднее значение сигнала, то есть,

$\sum _{i=1}^{N}(T_{n}f)(i)=\sum _{i=1}^{N}f(i).$

Свойства оператора перевода

Обобщенный оператор свертки удовлетворяет следующим свойствам:

Для любого $f,g\in \mathbb {R} ^{N}$, и $j,k\in \{1,2,\dots ,N\}$,

• $T_{j}(f*g)=(T_{j}f)*g=f*(T_{j}g)$
• $T_{j}T_{k}f=T_{k}T_{j}f$
• $\sum _{i=1}^{N}(T_{j}f)(i)={\sqrt {N}}{\hat {f}}(0)=\sum _{i=1}^{N}f(i)$
• $\left\|T_{j}f\right\|\neq \|f\|$

Приложения

Сжатие изображения

Представление сигналов в частотной области является распространенным подходом к сжатию данных. Поскольку сигналы графа могут быть редкими в своей спектральной области графа, преобразование Фурье графа также можно использовать для сжатия изображений .

Уменьшение шума графика

Подобно классическому шумоподавлению сигналов на основе преобразования Фурье, графовые фильтры на основе графового преобразования Фурье могут быть предназначены для шумоподавления графового сигнала.

Классификация данных

Поскольку преобразование Фурье графа позволяет определять свертку на графах, оно позволяет адаптировать обычные сверточные нейронные сети (CNN) для работы с графами. со структурой графа, Алгоритмы полуконтролируемого обучения такие как сверточная сеть графа (GCN), способны распространять метки сигнала графа по всему графу с небольшим подмножеством помеченных узлов, теоретически работая как аппроксимация первого порядка сверток спектрального графа без вычислений. граф Лапласа и его собственное разложение.

Ящик для инструментов

GSPBOX представляет собой набор инструментов для обработки сигналов графов, включая преобразование Фурье графа. Он поддерживает языки Python и MATLAB .

Внешние ссылки

• DeepGraphLibrary Бесплатный пакет Python, созданный для простой реализации графовых нейронных сетей.