Исчисление на конечных взвешенных графах

В математике , исчисление на конечных взвешенных графов является дискретным исчисление для функций, домен представляет собой множество вершин из графа с конечным числом вершин и весов , связанных с краями . Это включает в себя формулирование дискретных операторов на графах, которые аналогичны дифференциальным операторам в исчислении , таких как лапласианы графов (или дискретные операторы Лапласа ) как дискретные версии лапласиана , и использование этих операторов для формулирования дифференциальных уравнений , разностных уравнений, или вариационные модели на графах, которые можно интерпретировать как дискретные версии уравнений в частных производных или вариационные модели континуума. Такие уравнения и модели являются важными инструментами для математического моделирования, анализа и обработки дискретной информации во многих различных областях исследований, например, в обработке изображений , машинном обучении и сетевом анализе .

В приложениях конечные взвешенные графы представляют конечное число объектов посредством вершин графа, любые парные отношения между этими объектами посредством ребер графа, а значимость связи посредством весовой функции ребер. Дифференциальные уравнения или разностные уравнения на таких графах могут использоваться для использования структуры графа для таких задач, как сегментация изображения (где вершины представляют пиксели, а взвешенные края кодируют сходство пикселей на основе сравнения окрестностей Мура или больших окон), кластеризация данных , данные классификация , или обнаружение сообщества в социальной сети (где вершины представляют пользователей сети, ребра представляют связи между пользователями, а весовая функция указывает силу взаимодействия между пользователями).

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

Если конечный взвешенный граф геометрически вложен в евклидово пространство, т. Е. Вершины графа представляют точки этого пространства, то его можно интерпретировать как дискретную аппроксимацию связанного с ним нелокального оператора в континууме.

Основные определения [ править ]

Конечное взвешенный граф определяется как тройка , для которой${\ displaystyle G}$${\ Displaystyle G = (V, E, w)}$

• ${\ displaystyle V = \ {x_ {1}, \ dots, x_ {n} \}, n \ in \ mathbb {N}}$, - конечный набор индексов, обозначаемых как вершины или узлы графа ,
• ${\ Displaystyle E \ подмножество V \ раз V}$конечное множество (ориентированных) ребер графа, соединяющих подмножество вершин,
• ${\ Displaystyle с \ двоеточием E \ rightarrow \ mathbb {R}}$- весовая функция ребер, определенная на ребрах графа.

В ориентированном графе каждое ребро имеет начальный и конечный узел . В неориентированном графе для каждого ребра существует ребро, и весовая функция должна быть симметричной, т . Е .. ^[1] В оставшейся части этой страницы графики будут считаться неориентированными, если специально не указано иное. Многие идеи, представленные на этой странице, можно обобщить на ориентированные графы. ^[1]${\ displaystyle (x_ {i}, x_ {j}) \ in E}$ ${\ displaystyle x_ {i} \ in V}$ ${\ displaystyle x_ {j} \ in V}$${\ displaystyle (x_ {i}, x_ {j})}$${\displaystyle (x_{j},x_{i})}$${\displaystyle w(x_{i},x_{j})=w(x_{j},x_{i})}$

Функция края веса ассоциирует каждое ребро реальной стоимости . Как по математическим причинам, так и по причинам, связанным с конкретным приложением, весовая функция на краях часто должна быть строго положительной, и на этой странице предполагается, что это так, если специально не указано иное. Возможны обобщения многих идей, представленных на этой странице, для включения ребер с отрицательным весом. Иногда рассматривается расширение области определения весовой функции ребра до (при этом результирующая функция по-прежнему называется весовой функцией ребра ) путем установки when .${\displaystyle w}$${\displaystyle (x_{i},x_{j})\in E}$${\displaystyle w(x_{i},x_{j})>0}$${\displaystyle V\times V}$${\displaystyle w(x_{i},x_{j})=0}$${\displaystyle (x_{i},x_{j})\not \in E}$

В приложениях каждая вершина графа обычно представляет собой один объект в заданных данных, например, элементы конечного набора данных, пиксели в изображении или пользователей в социальной сети. График край представляет собой связь между двумя объектами, например попарных взаимодействий или сходства на основе сравнения геометрических окрестностей (например пикселей в изображениях) или другого элемента, с весом ребра , кодирующего прочность этих отношений. Наиболее часто используемые весовые функции нормализованы для отображения на значения от 0 до 1, т . Е ..${\displaystyle x\in V}$${\displaystyle w:E\rightarrow (0,1]}$

Далее предполагается, что рассматриваемые графы связаны без петель и кратных ребер между вершинами. Эти предположения в основном безвредны, поскольку во многих приложениях каждый компонент связности несвязного графа может рассматриваться как отдельный граф, каждое появление (которое было бы ненулевым при наличии петель) появляется при наличии другого фактора. который исчезает, когда (см. раздел об операторах дифференциального графа ниже), а веса ребер могут кодировать такую ​​же информацию, как и несколько ребер.${\displaystyle w(x_{i},x_{i})}$${\displaystyle i=j}$

Окрестности [ править ]

Узел является соседом узла, если существует ребро . С точки зрения обозначений это отношение может быть сокращено до , что следует читать как « является соседом ». В противном случае, если не сосед одного пишет . Окрестности вершины просто множество соседей . Степень вершины является взвешенным размером его окрестностей: ${\displaystyle x_{j}\in V}$${\displaystyle x_{i}\in V}$${\displaystyle (x_{i},x_{j})\in E}$${\displaystyle x_{j}\sim x_{i}}$${\displaystyle x_{j}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle x_{i}}$${\displaystyle x_{j}\not \sim x_{i}}$ ${\displaystyle {\mathcal {N}}(x_{i})}$${\displaystyle x_{i}\in V}$${\displaystyle {\mathcal {N}}(x_{i}):=\{x_{j}\in V\colon x_{j}\sim x_{i}\}}$${\displaystyle x_{i}\in V}$

${\displaystyle \deg(x_{i}):=\sum _{j\,:\,x_{j}\sim x_{i}}w(x_{i},x_{j}).}$

Обратите внимание, что в частном случае, когда on (т.е. график невзвешен ), мы имеем .${\displaystyle w\equiv 1}$${\displaystyle E}$${\displaystyle \deg(x_{i}):=|{\mathcal {N}}(x_{i})|}$

Пространство вещественных вершинных функций [ править ]

Позвольте быть пространство (реальных) вершинных функций . Так как конечное множество, любая вершинная функция может быть представлена в виде n - мерного вектора (где ) и , следовательно , пространство вершинных функций могут быть идентифицированы с помощью n - мерного пространства Гильберта: . Внутренний продукт определяется как:${\displaystyle {\mathcal {H}}(V):=\{f:V\rightarrow \mathbb {R} \}}$${\displaystyle V}$${\displaystyle f\in {\mathcal {H}}(V)}$${\displaystyle n}$${\displaystyle f\in \mathbb {R} ^{n}}$${\displaystyle n:=|V|}$${\displaystyle {\mathcal {H}}(V)}$${\displaystyle n}$${\displaystyle {\mathcal {H}}(V)\cong \mathbb {R} ^{n}}$${\displaystyle {\mathcal {H}}(V)}$

${\displaystyle \langle f,g\rangle _{{\mathcal {H}}(V)}:=\sum _{x_{i}\in V}f(x_{i})g(x_{i}),\quad \forall f,g\in {\mathcal {H}}(V).}$

Кроме того, для любой функции вершины -норме и -унормы определяется как:${\displaystyle f\in {\mathcal {H}}(V)}$${\displaystyle \ell _{p}}$${\displaystyle \ell _{\infty }}$${\displaystyle f}$

${\displaystyle \|f\|_{p}={\begin{cases}\left(\sum _{x_{i}\in V}|f(x_{i})|^{p}\right)^{\frac {1}{p}},&{\text{ for }}1\leqslant p<\infty \ ,\\\max _{x_{i}\in V}|f(x_{i})|,&{\text{ for }}p=\infty \ .\end{cases}}}$

-Норме индуцируется внутреннего продукта.${\displaystyle \ell _{2}}$

В приложениях вершинные функции полезны для маркировки вершин узлов. Например, в кластеризации данных на основе графа каждый узел представляет точку данных, а функция вершин используется для определения принадлежности узлов к кластеру.

Пространство реальных граничных функций [ править ]

Аналогично вещественным вершинным функциям можно ввести пространство вещественных граничных функций . Поскольку любая функция ребер определена на конечном множестве ребер , ее можно представить как -мерный вектор , где . Следовательно, пространство краевых функций можно идентифицировать как -мерное гильбертово пространство, т . Е ..${\displaystyle {\mathcal {H}}(E):=\{F:E\rightarrow \mathbb {R} \}}$${\displaystyle F}$${\displaystyle E}$${\displaystyle m}$${\displaystyle F\in \mathbb {R} ^{m}}$${\displaystyle m:=|E|}$${\displaystyle {\mathcal {H}}(E)}$${\displaystyle m}$${\displaystyle {\mathcal {H}}(E)\cong \mathbb {R} ^{m}}$

Частным случаем краевой функции является нормированная весовая функция ребра, введенная выше в разделе, посвященном основным определениям . Подобно этой функции, любую функцию края можно тривиально расширить до , установив if . Пространство этих расширенных краевых функций все еще обозначается и может быть отождествлено с , где теперь .${\displaystyle w\colon E\rightarrow (0,1]}$${\displaystyle F}$${\displaystyle V\times V}$${\displaystyle F(x_{i},x_{j}):=0}$${\displaystyle (x_{i},x_{j})\not \in E}$${\displaystyle {\mathcal {H}}(E)}$${\displaystyle \mathbb {R} ^{m}}$${\displaystyle m:=|V|^{2}}$

Внутренний продукт определяется как:${\displaystyle {\mathcal {H}}(E)}$

${\displaystyle \langle F,G\rangle _{{\mathcal {H}}(E)}:=\sum _{(x_{i},x_{j})\in E}F(x_{i},x_{j})G(x_{i},x_{j}),\quad \forall F,G\in {\mathcal {H}}(E).}$

Кроме того, для любого ребра функции -норме и -унормы определяется как:${\displaystyle F\in {\mathcal {H}}(V)}$${\displaystyle \ell _{p}}$${\displaystyle \ell _{\infty }}$${\displaystyle F}$

${\displaystyle \|F\|_{p}={\begin{cases}\left(\sum _{(x_{i},x_{j})\in E}|F(x_{i},x_{j})|^{p}\right)^{\frac {1}{p}}&{\text{ for }}1\leqslant p<\infty \ ,\\\max _{(x_{i},x_{j})\in E}|F(x_{i},x_{j})|,&{\text{ for }}p=\infty \ .\end{cases}}}$

-Норме индуцируется внутреннего продукта.${\displaystyle \ell _{2}}$

Если расширить набор ребер таким образом, что станет ясно, что, потому что . Это означает, что каждую краевую функцию можно отождествить с линейным матричным оператором.${\displaystyle E}$${\displaystyle E=V\times V}$${\displaystyle {\mathcal {H}}(E)\cong \mathbb {R} ^{n\times n}}$${\displaystyle {\mathcal {H}}(V)\cong \mathbb {R} ^{n}}$

Операторы дифференциального графа [ править ]

Важным компонентом исчисления на конечных взвешенных графах является имитация стандартных дифференциальных операторов из континуума в дискретной настройке конечных взвешенных графов. Это позволяет перенести хорошо изученные математические инструменты, такие как уравнения в частных производных и вариационные методы, и сделать их пригодными для использования в приложениях, которые лучше всего можно моделировать с помощью графа. Фундаментальная концепция, которая делает этот перевод возможным, - это градиент графа, оператор разности первого порядка на графах. На основе этого можно получить разностные операторы более высокого порядка, например, лапласиан графа.

Дифференциальные операторы первого порядка [ править ]

Взвешенные различия [ править ]

Позвольте быть конечным взвешенным графом и пусть быть вершинной функцией. Тогда взвешенная разность (или взвешенная производная графа ) вдоль направленного ребра равна${\displaystyle G=(V,E,w)}$${\displaystyle f\in {\mathcal {H}}(V)}$${\displaystyle f}$${\displaystyle (x_{i},x_{j})\in E}$

${\displaystyle \partial _{x_{j}}f(x_{i})\ :=\ {\sqrt {w(x_{i},x_{j})}}\left(f(x_{j})-f(x_{i})\right).}$

Для любой взвешенной разницы сохраняются следующие свойства:

• ${\displaystyle \partial _{x_{i}}f(x_{j})=-\partial _{x_{j}}f(x_{i}),}$
• ${\displaystyle \partial _{x_{i}}f(x_{i})=0,}$
• ${\displaystyle f(x_{i})=f(x_{j})\Rightarrow \partial _{x_{j}}f(x_{i})=0.}$

Взвешенный градиент [ править ]

На основе понятия взвешенных разностей оператор взвешенного градиента на графах определяется как${\displaystyle \nabla _{w}:{\mathcal {H}}(V)\rightarrow {\mathcal {H}}(E)}$

${\displaystyle (\nabla _{w}f)(x_{i},x_{j})\ =\ \partial _{x_{j}}f(x_{i}).}$

Это линейный оператор .

Для измерения локального изменения в функции вершины в вершине можно ограничить градиент от всех ориентированных ребер , начиная с и с помощью -норма этой краевой функции, т.е.${\displaystyle f}$${\displaystyle x_{i}\in V}$${\displaystyle \nabla _{w}f}$${\displaystyle f}$${\displaystyle x_{i}}$${\displaystyle \ell _{p}}$

${\displaystyle \|(\nabla _{w}f)(x_{i},\cdot )\|_{\ell _{p}}={\begin{cases}\left(\sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})^{\frac {p}{2}}|f(x_{j})-f(x_{i})|^{p}\right)^{\frac {1}{p}}&{\text{ for }}1\leq p<\infty ,\\\max _{x_{j}\sim x_{i}}{\sqrt {w(x_{i},x_{j})}}|f(x_{j})-f(x_{i})|&{\text{ for }}p=\infty .\end{cases}}}$

Взвешенное расхождение [ править ]

Сопряженный оператор взвешенного оператора градиента представляет собой линейный оператор , определяемый ${\displaystyle \nabla _{w}^{*}\colon {\mathcal {H}}(E)\rightarrow {\mathcal {H}}(V)}$

${\displaystyle \langle \nabla _{w}f,G\rangle _{{\mathcal {H}}(E)}=\langle f,\nabla _{w}^{*}G\rangle _{{\mathcal {H}}(V)}\quad {\text{ for all }}f\in {\mathcal {H}}(V),G\in {\mathcal {H}}(E).}$

Для неориентированных графов с симметричной весовой функцией сопряженный оператор функции в вершине имеет следующий вид:${\displaystyle w\in {\mathcal {H}}(E)}$${\displaystyle \nabla _{w}^{*}}$${\displaystyle F\in {\mathcal {H}}(E)}$${\displaystyle x_{i}\in V}$

${\displaystyle \left(\nabla _{w}^{*}F\right)(x_{i})\ =\ \sum _{x_{j}\sim x_{i}}{{\sqrt {w(x_{i},x_{j})}}(F(x_{j},x_{i})-F(x_{i},x_{j}))}.}$

Затем можно определить оператор взвешенной дивергенции на графах с помощью сопряженного оператора как . Дивергенция на графе измеряет чистый исход функции ребра в каждой вершине графа.${\displaystyle \operatorname {div} _{w}:=-\nabla _{w}^{*}}$

Дифференциальные операторы второго порядка [ править ]

Графический оператор Лапласа [ править ]

Взвешенный граф лапласиан представляет собой хорошо изученный оператор в настройке графа. Подражая связи оператора Лапласа в континууме, лапласиан взвешенного графа может быть получен для любой вершины как:${\displaystyle \Delta _{w}:{\mathcal {H}}(V)\rightarrow {\mathcal {H}}(V)}$${\displaystyle \operatorname {div} (\nabla f)=\Delta f}$${\displaystyle x_{i}\in V}$

${\displaystyle {\begin{aligned}(\operatorname {div} _{w}(\nabla _{w}f))(x_{i})&={\frac {1}{2}}\sum _{x_{j}\sim x_{i}}{\sqrt {w(x_{i},x_{j})}}(\nabla _{w}f(x_{j},x_{i})-\nabla _{w}f(x_{i},x_{j}))\\&={\frac {1}{2}}\sum _{x_{j}\sim x_{i}}{\sqrt {w(x_{i},x_{j})}}\left({\sqrt {w(x_{i},x_{j})}}(f(x_{j})-f(x_{i}))-{\sqrt {w(x_{j},x_{i})}}(f(x_{i})-f(x_{j}))\right)\\&={\frac {1}{2}}\sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})(2f(x_{j})-2f(x_{i}))\\&=\sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})(f(x_{j})-f(x_{i}))\ =:\ (\Delta _{w}f)(x_{i}).\end{aligned}}}$

Обратите внимание, что нужно предполагать, что граф неориентирован и имеет симметричную весовую функцию для этого представления.${\displaystyle G}$${\displaystyle w(x_{i},x_{j})=w(x_{j},x_{i})}$

Графические операторы p-Лапласа [ править ]

Непрерывный оператор -Лапласа - это дифференциальный оператор второго порядка, который может быть хорошо преобразован в конечные взвешенные графы. Это позволяет переводить различные дифференциальные уравнения в частных производных, например уравнение теплопроводности, в настройку графика.${\displaystyle p}$

На основе операторов частных разностей первого порядка на графах можно формально вывести семейство взвешенных операторов Лапласа${\displaystyle p}$ на графах для путем минимизации дискретного функционала энергии Дирихле${\displaystyle \Delta _{w,p}\colon {\mathcal {H}}(V)\rightarrow {\mathcal {H}}(V)}$${\displaystyle 1\leq p<\infty }$${\displaystyle p}$

${\displaystyle E(f)\ :=\ {\frac {1}{p}}\sum _{x_{i}\in V}\|\nabla _{w}f(x_{i},\cdot )\|_{\ell _{p}}^{p}.}$

Необходимые условия оптимальности для минимизатора функционала энергии приводят к следующему определению графа -лапласиана:${\displaystyle E}$${\displaystyle p}$

${\displaystyle (\Delta _{w,p}f)(x_{i})\ :=\ \sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})^{\frac {p}{2}}|f(x_{j})-f(x_{i})|^{p-2}(f(x_{j})-f(x_{i})).}$

Обратите внимание, что оператор Лапласа-граф является частным случаем оператора Лапласа-графа для , т. Е.${\displaystyle p}$${\displaystyle p=2}$

${\displaystyle (\Delta _{w,2}f)(x_{i})\ =\ (\Delta _{w}f)(x_{i})\ =\ \sum _{x_{j}\sim x_{i}}w(x_{i},x_{j})(f(x_{j})-f(x_{i})).}$

Приложения [ править ]

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

• шумоподавление изображения ^{[2] [3]}
• сегментация изображения ^[4]
• рисование изображения ^{[2] [5]}
• томографическая реконструкция ^[6]
• обратные задачи ^[7]
• кластеризация данных ^[8]
• сжатие облака точек ^[9]
• распознавание рукописных цифр ^[3]

См. Также [ править ]

• Модели фазового поля на графиках

Заметки [ править ]

1. ^ Обратите внимание, что также используется несколько иное определение неориентированного графа, в котором неориентированное ребро рассматривается как двойное множество (набор с двумя различными элементами) вместо пары упорядоченных пар и . Здесь необходимо последнее описание, так как требуется, чтобы граничные функции в (см. Раздел о пространстве граничных функций ) могли принимать разные значения на и .${\displaystyle \{x_{i},x_{j}\}}$ ${\displaystyle (x_{i},x_{j})}$${\displaystyle (x_{j},x_{i})}$${\displaystyle {\mathcal {H}}(E)}$${\displaystyle (x_{i},x_{j})}$${\displaystyle (x_{j},x_{i})}$

Ссылки [ править ]