Топология везде. Даже если нет явных, таких как социальная сеть, могут быть неявные, такие как графы, созданные в спектральной кластеризации (например, граф KNN).

CNN не может обрабатывать данные неевклидовой структуры: количество соседей каждого узла не является константой, мы не можем напрямую применить сверточное ядро ​​(с фиксированным размером) [2].

Существующие решения можно разделить на следующие два класса: 1). пространственная область; 2). спектральная область.

Спектральная область. Здесь мы сосредоточимся на спектральной области, которая составляет основу GCN. Спектральная теория графов относится к области исследований, в которой свойства графа изучаются с помощью собственных векторов и собственных значений его матрицы Лапласа.

Почему матрица Лапласа? (1) матрица Лапласа является симметричной матрицей, поэтому мы можем изучать ее спектральные свойства, выполняя на ней разложение по собственным значениям. (2) Матрица Лапласа довольно разреженная, только диагональные элементы и элементы, соответствующие соседям с 1 переходом, не равны нулю. (3) Мы можем связать матрицу Лапласа с оператором Лапласа.

Разложение по собственным значениям требует, чтобы матрица n на n в квадрате имела по крайней мере nлинейно независимыхсобственных векторов. К счастью, матрица Лапласа всегда полуположительно определена, из чего следует, что (1) она симметрична и, следовательно, имеет ровно n линейно независимых собственных векторов, (2) любое ее собственное значение неотрицательно, (3) любая пара ее собственных векторов ортогональны друг другу.

Почему именно спектральный подход? Как работает слой GCN?

Почему не пространственный подход? Перед ним стоит задача сопоставления местных районов. Не существует однозначного формального определения переноса на графах с пространственной точки зрения.

Однако спектральный подход обеспечивает четко определенный оператор локализации на графах с помощью сверток с дельтой Кронекера, реализованных в спектральной области. Теорема о свертке определяет свертки как линейные операторы, которые диагонализируются в базисе Фурье (собственные векторы оператора Лапласа). Хотя (1) фильтр, определенный в спектральной области, не локализован естественным образом и (2) переводы являются дорогостоящими из-за умножения O (n²) на базис графа Фурье. Оба ограничения могут быть устранены путем параметризации фильтра.

Свертка графа в спектральной области часто определяется как:

Самая простая параметризация ядра

Однако непараметрический фильтр не локализован в пространстве и имеет сложность обучения O(n). Чтобы изучить локализованный фильтр, мы используем свойство, которое

Параметризация фильтров SOTA основана на чебышевском разложении полиномиальных фильтров (K-1)-го порядка как

где

представляет собой диагональную матрицу перемасштабированных собственных значений лапласиана графа.

Мы можем переписать операцию фильтрации как

где

обозначает ремасштабированный лапласиан графа.

Обозначая

Мы можем вычислить операцию фильтрации на основе

то более высокие порядки могут быть вычислены по правилу многочлена Чебышева как:

и, наконец, получаем

Следовательно, временная сложность равна O(K|E|).

Объединение: требуются осмысленные окрестности, в которых похожие узлы сгруппированы вместе. Кластеризация графа — это NP-сложная задача, поэтому необходимо использовать эвристику. Подробности можно найти в статье [1].

В более поздней статье [3] авторы показывают, что, когда существует базовая сетевая структура (например, набор данных Cora), нам не нужно беспокоиться о части построения графа, которая выглядит довольно сложной в [1]. Они также показывают, что перемасштабированное приближение первого порядка (уравнение 8) превосходит другие эвристики.

Ссылка:

[1] Дефферрар, Микаэль, Ксавье Брессон и Пьер Вандергейнст. «Сверточные нейронные сети на графах с быстрой локализованной спектральной фильтрацией». В Достижения в системах обработки нейронной информации, стр. 3844–3852. 2016.

[2] Как понять GCN (на китайском языке)? https://www.zhihu.com/question/54504471/answer/332657604

[3] Кипф, Томас Н. и Макс Веллинг. «Полуконтролируемая классификация с использованием графовых сверточных сетей». препринт arXiv arXiv:1609.02907 (2016 г.).