Графовое преобразование Фурье
В математике — преобразование Фурье графа это математическое преобразование , которое разлагает матрицу Лапласа графа на собственные значения и собственные векторы . Аналогично классическому преобразованию Фурье , собственные значения представляют частоты , а собственные векторы образуют так называемый базис графа Фурье .
Графовое преобразование Фурье играет важную роль в теории спектральных графов . Он широко применяется в недавних исследованиях алгоритмов обучения со структурой графов , таких как широко используемые сверточные сети .
Определение
[ редактировать ]Учитывая неориентированный взвешенный граф , где представляет собой набор узлов с ( количество узлов) и это набор ребер, сигнал графа — функция, определенная в вершинах графа . Сигнал отображает каждую вершину на действительное число . Любой графический сигнал можно спроецировать на собственные векторы матрицы Лапласа. . [1] Позволять и быть собственное значение и собственный вектор Лапласа матрицы (собственные значения отсортированы в порядке возрастания, т.е. [2] ), графовое преобразование Фурье (GFT) графического сигнала на вершинах это расширение с точки зрения собственных функций . [3] Он определяется как: [1] [4]
где .
С — действительная симметричная матрица , ее собственные векторы образуют ортогональный базис . Следовательно, существует обратное графовое преобразование Фурье (IGFT), и оно записывается как: [4]
Аналогично классическому преобразованию Фурье , преобразование Фурье графа позволяет представить сигнал в двух разных областях: вершинной области и спектральной области графа . Обратите внимание, что определение графового преобразования Фурье и его обратного преобразования зависит от выбора собственных векторов Лапласа, которые не обязательно являются уникальными. [3] Собственные векторы нормализованной матрицы Лапласа также являются возможной основой для определения прямого и обратного преобразования Фурье графа.
Характеристики
[ редактировать ]Личность Парсеваля
[ редактировать ]Соотношение Парсеваля справедливо для преобразования Фурье графа: [5] то есть для любого
Это дает нам личность Парсеваля : [3]
Обобщенный оператор свертки
[ редактировать ]Определение свертки между двумя функциями и не может быть напрямую применено к графическим сигналам, поскольку трансляция сигнала не определена в контексте графов. [4] Однако, заменяя комплексный экспоненциальный сдвиг в классическом преобразовании Фурье собственными векторами Лапласа графа, свертку двух сигналов графа можно определить как: [3]
Свойства оператора свертки
[ редактировать ]Обобщенный оператор свертки удовлетворяет следующим свойствам: [3]
- Обобщенная свертка в вершинной области — это умножение в спектральной области графа:
- Коммутативность :
- Дистрибутивность :
- Ассоциативность :
- Ассоциативность со скалярным умножением: , для любого .
- Мультипликативное тождество : , где является тождеством обобщенного оператора свертки.
- Сумма обобщенной свертки двух сигналов равна произведению сумм двух сигналов на константу:
Обобщенный оператор перевода
[ редактировать ]Как уже говорилось ранее, классический оператор перевода не может быть обобщено на настройку графика. Один из способов определить оператор обобщенного перевода — использовать обобщенную свертку с дельта-функцией с центром в вершине. : [2]
где
Константа нормализации гарантирует, что оператор перевода сохраняет среднее значение сигнала, [4] то есть,
Свойства оператора перевода
[ редактировать ]Обобщенный оператор свертки удовлетворяет следующим свойствам: [3]
Для любого , и ,
Приложения
[ редактировать ]Сжатие изображения
[ редактировать ]Представление сигналов в частотной области является распространенным подходом к сжатию данных. Поскольку сигналы графа могут быть редкими в своей спектральной области графа, преобразование Фурье графа также можно использовать для сжатия изображений . [6] [7]
Уменьшение шума графика
[ редактировать ]Подобно классическому шумоподавлению сигналов на основе преобразования Фурье, графовые фильтры на основе графового преобразования Фурье могут быть предназначены для шумоподавления графового сигнала. [8]
Классификация данных
[ редактировать ]Поскольку преобразование Фурье графа позволяет определять свертку на графах, оно позволяет адаптировать обычные сверточные нейронные сети (CNN) для работы с графами. со структурой графа, Алгоритмы полуконтролируемого обучения такие как сверточная сеть графа (GCN), способны распространять метки сигнала графа по всему графу с небольшим подмножеством помеченных узлов, теоретически работая как аппроксимация первого порядка сверток спектрального графа без вычислений. граф Лапласа и его собственное разложение. [9]
Ящик для инструментов
[ редактировать ]GSPBOX [10] [11] представляет собой набор инструментов для обработки сигналов графов, включая преобразование Фурье графа. Он поддерживает языки Python и MATLAB .
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Рико, Бенджамин; Боргнат, Пьер; Трамбле, Николя; Гонсалвес, Пауло; Вандергейнст, Пьер (01 июля 2019 г.). «Фурье мог бы быть специалистом по данным: от преобразования Фурье графа к обработке сигналов на графиках» . Comptes Rendus Physique . Фурье и наука сегодняшнего дня / Фурье и наука о жизни. 20 (5): 474–488. Бибкод : 2019CRPhy..20..474R . дои : 10.1016/j.crhy.2019.08.003 . ISSN 1631-0705 .
- ^ Перейти обратно: а б Шуман, Давид I; Наранг, Сунил К.; Фроссар, Паскаль; Ортега, Антонио; Вандергейнст, Пьер (май 2013 г.). «Новая область обработки сигналов на графиках: распространение многомерного анализа данных на сети и другие нерегулярные области». Журнал обработки сигналов IEEE . 30 (3): 83–98. arXiv : 1211.0053 . Бибкод : 2013ISPM...30...83S . дои : 10.1109/MSP.2012.2235192 . ISSN 1558-0792 . S2CID 1594725 .
- ^ Перейти обратно: а б с д и ж Шуман, Давид I; Рико, Бенджамин; Вандергейнст, Пьер (01 марта 2016 г.). «Вершинно-частотный анализ на графах» . Прикладной и вычислительный гармонический анализ . 40 (2): 260–291. arXiv : 1307.5708 . дои : 10.1016/j.acha.2015.02.005 . ISSN 1063-5203 .
- ^ Перейти обратно: а б с д Нонато, Луис Густаво (29 августа 2017 г.). «График преобразования Фурье» (PDF) .
- ^ Хаммонд, Дэвид К.; Вандергейнст, Пьер; Грибонваль, Реми (01 марта 2011 г.). «Вейвлеты на графах с помощью теории спектральных графов» . Прикладной и вычислительный гармонический анализ . 30 (2): 129–150. arXiv : 0912.3848 . дои : 10.1016/j.acha.2010.04.005 . ISSN 1063-5203 . S2CID 5593503 .
- ^ Сандрыгайло, Алексей; Моура, Хосе М.Ф. (май 2013 г.). «Дискретная обработка сигналов на графах: преобразование Фурье графа». Международная конференция IEEE 2013 по акустике, речи и обработке сигналов . IEEE. стр. 6167–6170. дои : 10.1109/icassp.2013.6638850 . ISBN 978-1-4799-0356-6 . S2CID 14704192 .
- ^ Ху, Вэй; Чунг, Джин; Ортега, Антонио; Ау, Оскар К. (январь 2015 г.). «Преобразование Фурье графа с многоразрешением для сжатия кусочно-гладких изображений». Транзакции IEEE при обработке изображений . 24 (1): 419–433. Бибкод : 2015ITIP...24..419H . дои : 10.1109/TIP.2014.2378055 . ISSN 1941-0042 . ПМИД 25494508 . S2CID 9539186 .
- ^ Сандрыгайло, Алексей; Моура, Хосе МФ (июнь 2014 г.). «Дискретная обработка сигналов на графиках: частотный анализ». Транзакции IEEE по обработке сигналов . 62 (12): 3042–3054. arXiv : 1307.0468 . Бибкод : 2014ITSP...62.3042. . дои : 10.1109/TSP.2014.2321121 . ISSN 1941-0476 . S2CID 12110057 .
- ^ Кипф, Томас Н.; Веллинг, Макс (22 февраля 2017 г.). «Полуконтролируемая классификация с использованием сверточных сетей графов». arXiv : 1609.02907 [ cs.LG ].
- ^ Перроден, Натанаэль; Паратте, Йохан; Шуман, Дэвид; Мартин, Лайонел; Калофолиас, Василис; Вандергейнст, Пьер; Хаммонд, Дэвид К. (15 марта 2016 г.). «GSPBOX: набор инструментов для обработки сигналов на графиках». arXiv : 1408.5781 [ cs.IT ].
- ^ «PyGSP: обработка сигналов графа в Python — документация PyGSP 0.5.1» . pygsp.readthedocs.io . Проверено 22 июня 2020 г.
Внешние ссылки
[ редактировать ]- DeepGraphLibrary Бесплатный пакет Python, созданный для простой реализации графовых нейронных сетей.