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

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

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

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

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

Основные определения

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

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

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

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

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

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

Район

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

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

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

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

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

$\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).$

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

$\|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}}$

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

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

Пространство вещественных граничных функций

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

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

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

$\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).$

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

$\|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}}$

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

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

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

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

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

Взвешенные различия

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

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

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

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

Взвешенный градиент

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

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

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

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

$\|(\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}}$

Взвешенная дивергенция

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

$\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).$

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

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

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

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

Графовый оператор Лапласа

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

${\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}}$

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

Графовые операторы p-Лапласа

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

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

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

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

$(\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})).$

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

$(\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})).$

Приложения

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

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

См. также

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

Примечания

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