Обучение на гиперграфах (Hypergraph Learning)

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
 
Строка 1: Строка 1:
-
{{well|Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium) и проверена участником [[Участник:Valeriia Berdnikova |Valeriia Berdnikova]] 16:50, 19 июля 2026 (MSD). Промпт приводится полностью в [[Обсуждение:Обучение на гиперграфах (Hypergraph Learning)]].}}
+
{{well|Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium) и проверена участником [[Участник:Valeriia Berdnikova |Valeriia Berdnikova]] 17:05, 19 июля 2026 (MSD). Промпт приводится полностью в [[Обсуждение:Обучение на гиперграфах (Hypergraph Learning)]].}}
{{TOCright}}
{{TOCright}}

Текущая версия

Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium) и проверена участником Valeriia Berdnikova 17:05, 19 июля 2026 (MSD). Промпт приводится полностью в Обсуждение:Обучение на гиперграфах (Hypergraph Learning).


Содержание

Обучение на гиперграфах (англ. hypergraph learning) — совокупность методов машинного обучения, в которых объекты и отношения между ними представляются гиперграфом. В отличие от обычного графа, где каждое ребро соединяет ровно две вершины, гиперребро может одновременно связывать произвольное число вершин. Это позволяет непосредственно моделировать групповые, многоместные и отношения высокого порядка.[1][1]

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

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

История развития

Гиперграфы сформировались как самостоятельный объект дискретной математики во второй половине XX века. Классические исследования рассматривали гиперграфы как системы конечных множеств и изучали раскраски, покрытия, независимые множества, связность и разбиения.[1]

В машинном обучении ранние методы часто преобразовывали гиперграф в обычный взвешенный граф, после чего применяли графовые алгоритмы. Важным этапом стала работа Чжоу, Хуана и Шёлькопфа, в которой были предложены нормированный гиперграфовый лапласиан, спектральное вложение, кластеризация и трансдуктивная классификация.[1]

С развитием графовых нейронных сетей появились дифференцируемые гиперграфовые модели. HGNN перенёс спектральную гиперграфовую свёртку в архитектуру глубокой сети,[1] а последующие методы ввели внимание, явные представления гиперрёбер, двухэтапную передачу сообщений, обучаемое построение структуры и универсальные функции над мультимножествами.[1]

Обычный граф и гиперграф

Обычный граф

Неориентированный граф задаётся парой

G=(V,E),

где V — множество вершин, а каждое ребро имеет вид

e=\{u,v\},\qquad u,v\in V.

Таким образом, ребро представляет парное отношение.

Гиперграф

Неориентированный гиперграф определяется как

{\cal H}=(V,{\cal E}),

где

{\cal E}\subseteq 2^V\setminus\{\varnothing\}.

Каждое гиперребро e\in{\cal E} является непустым подмножеством вершин:

e=\{v_1,\ldots,v_k\},\qquad k\geq 1.

Обычный неориентированный граф является частным случаем гиперграфа, в котором

|e|=2

для всех рёбер.

Гиперграф называется r-однородным, если каждое гиперребро содержит ровно r вершин:

|e|=r,\qquad e\in{\cal E}.

Во многих прикладных гиперграфах размеры гиперрёбер различаются.

Почему парных связей может быть недостаточно

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

Такое преобразование не всегда позволяет различить:

  • одно совместное событие с четырьмя участниками;
  • шесть независимых парных взаимодействий;
  • несколько разных групповых событий, породивших одинаковый набор пар;
  • роль и вес исходного гиперребра;
  • контекст, общий только для всей группы.

Кроме того, крупное гиперребро при полном разложении создаёт

\frac{|e|(|e|-1)}{2}

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

Математическое представление гиперграфа

Матрица инцидентности

Пусть

V=\{v_1,\ldots,v_n\},\qquad {\cal E}=\{e_1,\ldots,e_m\}.

Матрица инцидентности имеет размер n\times m и определяется как

H_{ve}=1, если v\in e, и H_{ve}=0, если v\notin e.

Взвешенное или мягкое представление допускает значения

H_{ve}\geq 0,

которые характеризуют силу участия вершины в гиперребре.

Число ненулевых элементов матрицы равно общему числу инцидентностей:

M={\rm nnz}(H)=\sum_{e\in{\cal E}}|e|.

Именно величина M, а не произведение nm, определяет стоимость многих разреженных алгоритмов.

Веса гиперрёбер

Каждому гиперребру назначается вес

w(e)>0.

Диагональная матрица весов имеет вид

W={\rm diag}(w(e_1),\ldots,w(e_m)).

Вес может задаваться экспертно, вычисляться по сходству объектов или обучаться совместно с моделью.

Степени вершин

Степень вершины определяется суммой весов инцидентных гиперрёбер:

d(v)=\sum_{e\in{\cal E}}w(e)H_{ve}.

Диагональная матрица степеней вершин:

D_v={\rm diag}(d(v_1),\ldots,d(v_n)).

Степени гиперрёбер

Степень или мощность гиперребра равна числу входящих в него вершин:

\delta(e)=\sum_{v\in V}H_{ve}=|e|.

Соответствующая диагональная матрица:

D_e={\rm diag}(\delta(e_1),\ldots,\delta(e_m)).

В мягких гиперграфах \delta(e) может определяться суммой весов инцидентности.

Признаки вершин и гиперрёбер

Признаки вершин записываются матрицей

X\in{\bf R}^{n\times d_v},

а признаки гиперрёбер — матрицей

Z\in{\bf R}^{m\times d_e}.

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

Основные операции над гиперграфами

Подгиперграф

Для подмножества вершин U\subseteq V индуцированный подгиперграф содержит вершины U и пересечения исходных гиперрёбер с U, если эти пересечения непусты.

Двойственный гиперграф

В двойственном гиперграфе исходные гиперрёбра становятся вершинами, а исходные вершины задают новые гиперрёбра. Матрица инцидентности двойственного гиперграфа равна

H^{\mathsf T}.

Двойственное представление полезно для задач классификации и кластеризации гиперрёбер.

Клика-расширение

Каждое гиперребро заменяется кликой на входящих в него вершинах. Одна из распространённых взвешенных проекций имеет матрицу

A_{\rm clique}=HWD_e^{-1}H^{\mathsf T}-D_{\rm diag},

где диагональная часть удаляется или обрабатывается отдельно.

Преимущество клика-расширения состоит в возможности применять обычные графовые алгоритмы. Недостаток — потеря идентичности гиперрёбер и потенциальный квадратичный рост числа связей.

Звёздное расширение

Гиперграф преобразуется в двудольный граф с двумя типами узлов:

  • исходными вершинами;
  • узлами, соответствующими гиперрёбрам.

Рёбра двудольного графа задаются ненулевыми элементами H. Такое представление сохраняет структуру инцидентности и естественно приводит к двухэтапной передаче сообщений «вершины — гиперрёбра — вершины».

Линейный граф гиперграфа

В линейном графе вершинами являются гиперрёбра исходного гиперграфа, а два узла соединяются, если соответствующие гиперрёбра пересекаются. Это представление удобно для анализа отношений между группами, но не сохраняет всю внутреннюю структуру гиперрёбер.

Гиперграфовый лапласиан

Нормированный оператор распространения

В спектральной модели Чжоу и соавторов используется симметричный оператор

\Theta=D_v^{-1/2}HWD_e^{-1}H^{\mathsf T}D_v^{-1/2}.

Он описывает переход:

  1. от вершины к инцидентному гиперребру;
  2. от гиперребра к одной из содержащихся в нём вершин;
  3. с нормировкой по степеням вершин и размерам гиперрёбер.

Нормированный гиперграфовый лапласиан определяется как

L_{\cal H}=I-\Theta.

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

Квадратичная форма

Для вектора f\in{\bf R}^n квадратичная форма имеет вид

f^{\mathsf T}L_{\cal H}f=\frac{1}{2}\sum_{e\in{\cal E}}\sum_{u,v\in e}\frac{w(e)}{\delta(e)}\left(\frac{f(u)}{\sqrt{d(u)}}-\frac{f(v)}{\sqrt{d(v)}}\right)^2.

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

При положительных весах и ненулевых степенях матрица L_{\cal H} симметрична и положительно полуопределена:

f^{\mathsf T}L_{\cal H}f\geq 0.

Связь с обычным лапласианом

Если каждое гиперребро содержит ровно две вершины, гиперграф вырождается в обычный граф, а оператор становится вариантом нормированного графового лапласиана.

При гиперрёбрах большего размера матричный оператор всё равно действует на пары вершин после умножения HD_e^{-1}H^{\mathsf T}. Поэтому данный лапласиан частично интерпретируется как специальная взвешенная проекция гиперграфа на граф. Он сохраняет влияние размеров и весов гиперрёбер, но не кодирует все возможные различия между гиперграфами с одинаковой проекцией.

Спектральные методы

Собственные значения и собственные векторы

Рассматривается задача

L_{\cal H}u_i=\lambda_i u_i.

Собственные значения упорядочиваются:

0\leq\lambda_1\leq\lambda_2\leq\cdots\leq\lambda_n.

Малые собственные значения соответствуют направлениям, которые слабо изменяются внутри гиперрёбер.

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

Спектральное вложение

Пусть U_k содержит k собственных векторов, соответствующих наименьшим собственным значениям:

U_k=[u_1,\ldots,u_k]\in{\bf R}^{n\times k}.

Строка

y_v=(U_k)_{v,:}

является спектральным представлением вершины v.

Вложение можно получить из задачи

\min_{Y\in{\bf R}^{n\times k}}{\rm Tr}(Y^{\mathsf T}L_{\cal H}Y),\qquad Y^{\mathsf T}Y=I.

Решение образуют собственные векторы, соответствующие наименьшим собственным значениям.

Гиперграфовая спектральная кластеризация

Общий алгоритм:

  1. построить гиперграф и матрицу инцидентности;
  2. вычислить D_v, D_e и W;
  3. сформировать L_{\cal H};
  4. найти k собственных векторов;
  5. представить каждую вершину строкой матрицы U_k;
  6. нормировать строки при необходимости;
  7. применить k-means или другой алгоритм кластеризации.

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

Полуобучение и распространение информации

Пусть известны метки только части вершин. Матрица исходных меток имеет вид

Y\in{\bf R}^{n\times c},

где c — число классов.

Один из вариантов регуляризованного полуобучения решает задачу

\min_F {\rm Tr}(F^{\mathsf T}L_{\cal H}F)+\mu\|F-Y\|_F^2.

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

Условие оптимальности:

(L_{\cal H}+\mu I)F=\mu Y.

Следовательно,

F=\mu(L_{\cal H}+\mu I)^{-1}Y.

На практике явное обращение матрицы не выполняется. Используются итерационные методы или рекуррентное распространение:

F^{(t+1)}=\alpha\Theta F^{(t)}+(1-\alpha)Y.

При 0<\alpha<1 и подходящих спектральных условиях итерация сходится к фиксированной точке.

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

Передача сообщений на гиперграфах

Общая гиперграфовая нейронная сеть может быть представлена двумя стадиями.

Сначала вычисляется представление гиперребра:

h_e^{(l+1)}=\phi_e^{(l)}\left(\{h_v^{(l)}:v\in e\},z_e\right).

Затем обновляется вершина:

h_v^{(l+1)}=\phi_v^{(l)}\left(h_v^{(l)},\{h_e^{(l+1)}:e\ni v\}\right).

Функции \phi_e и \phi_v должны быть инвариантны к перестановке элементов, если порядок вершин внутри гиперребра не имеет смысла.

Типичные агрегаторы:

  • сумма;
  • среднее;
  • максимум;
  • степенное среднее;
  • механизм внимания;
  • Deep Sets;
  • Set Transformer;
  • обучаемая функция над мультимножеством.

Двухэтапная схема сохраняет явную роль гиперрёбер лучше, чем однократное распространение по клика-расширению.

Hypergraph Neural Network

Архитектура HGNN

В HGNN используется оператор

S=D_v^{-1/2}HWD_e^{-1}H^{\mathsf T}D_v^{-1/2}.

Один слой имеет вид

X^{(l+1)}=\sigma\left(SX^{(l)}\Theta^{(l)}\right),

где

Матричное умножение можно выполнять без формирования плотной матрицы S:

X\longrightarrow H^{\mathsf T}D_v^{-1/2}X\longrightarrow WD_e^{-1}H^{\mathsf T}D_v^{-1/2}X\longrightarrow D_v^{-1/2}HWD_e^{-1}H^{\mathsf T}D_v^{-1/2}X.

Это соответствует агрегации признаков из вершин в гиперрёбра и обратно.

Обучение

Для классификации вершин используется, например, перекрёстная энтропия:

{\cal L}_{\rm cls}=-\sum_{v\in V_L}\sum_{c=1}^C y_{vc}\ln \hat y_{vc},

где V_L — размеченные вершины.

Полная функция потерь может содержать регуляризацию:

{\cal L}={\cal L}_{\rm cls}+\lambda\sum_l\|\Theta^{(l)}\|_F^2.

Параметры обучаются градиентными методами.

Преимущества HGNN

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

Ограничения HGNN

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

HGNN не следует автоматически считать обучением на полной комбинаторной структуре гиперграфа: используемый линейный оператор не различает некоторые гиперграфы, имеющие одинаковую нормированную проекцию.

Гиперграфовые сети внимания

Терминология

Обозначение HAN неоднозначно. В литературе оно также используется для Heterogeneous Attention Network. В данной статье под Hypergraph Attention Network понимается гиперграфовая сеть с обучаемыми коэффициентами внимания по инцидентностям, основанная на операторе гиперграфового внимания Бая, Чжана и Торра.[1]

Внимание внутри гиперребра

Пусть g_e — текущее представление гиперребра. Оценка инцидентности может задаваться как

q_{ve}={\rm LeakyReLU}\left(a^{\mathsf T}[W_vh_v;W_eg_e]\right).

Нормированный коэффициент:

\alpha_{ve}=\frac{\exp(q_{ve})}{\sum_{u\in e}\exp(q_{ue})}.

Представление гиперребра:

g_e'=\sigma\left(\sum_{v\in e}\alpha_{ve}W_vh_v\right).

Затем гиперрёбра агрегируются для вершины:

h_v'=\sigma\left(\sum_{e\ni v}\beta_{ev}W_eg_e'\right),

где \beta_{ev} может быть фиксированным нормировочным или обучаемым коэффициентом.

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

Многоголовое внимание

Для K голов вычисляются независимые коэффициенты:

h_v'=\mathop{\Vert}_{k=1}^K h_{v,k}',

либо их среднее:

h_v'=\frac{1}{K}\sum_{k=1}^K h_{v,k}'.

Многоголовая схема позволяет изучать несколько типов групповой зависимости, но увеличивает память и время вычислений.

Преимущества внимания

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

Коэффициент внимания не является гарантированным причинным объяснением решения модели.

Ограничения внимания

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

Другие архитектуры

HyperGCN

HyperGCN аппроксимирует каждое гиперребро небольшим набором парных связей. Для гиперребра выбираются наиболее различающиеся вершины, после чего добавляются связи через промежуточные вершины гиперребра.[1]

Преимущества:

  • использование стандартных GCN;
  • меньше связей, чем при полном клика-расширении;
  • возможность динамического обновления аппроксимации.

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

HNHN

HNHN вводит явные нейроны гиперрёбер и нелинейные преобразования на обеих стадиях:

Z^{(l+1)}=\sigma\left(D_e^{-\alpha}H^{\mathsf T}D_v^{-\beta}X^{(l)}W_e^{(l)}\right),
X^{(l+1)}=\sigma\left(D_v^{-\gamma}HD_e^{-\delta}Z^{(l+1)}W_v^{(l)}\right).

Показатели нормировки управляют влиянием крупных гиперрёбер и вершин высокой степени.[1]

HNHN сохраняет раздельные представления вершин и гиперрёбер, но требует настройки дополнительных нормировок.

Hyper-SAGNN

Hyper-SAGNN использует [[Механизм внимания|самовнимание]] для построения контекстно зависимых представлений вершин внутри предполагаемого гиперребра. Модель предназначена в том числе для предсказания существования гиперрёбер переменного размера и для неоднородных гиперграфов.[1]

Для набора вершин e динамическое представление вершины зависит от остальных участников:

d_v={\rm Attn}\left(h_v,\{h_u:u\in e,\ u\ne v\}\right).

Вероятность гиперребра может вычисляться по различию статических и динамических представлений:

\hat p(e)=\sigma\left(\frac{1}{|e|}\sum_{v\in e}r(h_v,d_v)\right).

Самовнимание способно моделировать взаимодействия внутри группы, но его стоимость для гиперребра размера |e| обычно квадратична.

UniGNN

UniGNN формулирует гиперграфовую передачу сообщений через две перестановочно-инвариантные функции:

h_e=\phi_1(\{x_v:v\in e\}),
x_v'=\phi_2\left(x_v,\{h_e:e\ni v\}\right).

Выбор разных \phi_1 и \phi_2 позволяет переносить идеи GCN, GAT, GIN и GraphSAGE на гиперграфы. Авторы также рассматривают глубокую модель UniGCNII и показывают ограничение выразительности схемы классом обобщённого теста Вейсфейлера — Лемана первого порядка.[1]

AllSet

AllSet рассматривает вершины внутри гиперребра и гиперрёбра около вершины как мультимножества. Слой имеет общий вид

h_e=\phi_{\rm edge}(\{\!\{h_v:v\in e\}\!\}),
h_v'=\phi_{\rm node}(\{\!\{h_e:e\ni v\}\!\}).

Функции могут реализовываться через Deep Sets или Set Transformer. Такая формулировка включает многие ранее предложенные HGNN как частные случаи.[1]

Преимущество AllSet — универсальность. Недостатки зависят от выбранной функции мультимножества: простая сумма может быть недостаточно выразительной, а Set Transformer требует больше памяти и вычислений.

Построение гиперграфа

Качество обучения часто определяется не архитектурой сети, а способом построения гиперрёбер.

Гиперрёбра по известным отношениям

Гиперребро задаётся наблюдаемой группой:

  • авторами одной статьи;
  • товарами одной транзакции;
  • участниками одной встречи;
  • генами одного биологического комплекса;
  • объектами одного изображения;
  • сущностями одного факта знаний.

Это наиболее интерпретируемый вариант.

Гиперрёбра по ближайшим соседям

Для каждой вершины создаётся гиперребро, содержащее её и k ближайших соседей:

e_i=\{v_i\}\cup{\cal N}_k(v_i).

Вес может задаваться через ядро:

w(e_i)=\exp\left(-\frac{1}{|e_i|}\sum_{v\in e_i}\frac{\|x_v-x_i\|^2}{\sigma^2}\right).

Такой гиперграф зависит от метрики, масштаба признаков, k и \sigma.

Мультимодальные гиперграфы

Для каждой модальности можно построить отдельное множество гиперрёбер:

{\cal E}={\cal E}^{(1)}\cup\cdots\cup{\cal E}^{(p)}.

Модель может обучать веса модальностей или гиперрёбер. Этот подход применялся в HGNN для объединения нескольких типов признаков.[1]

Обучаемая структура

В глубоких моделях матрица инцидентности или веса могут вычисляться из представлений:

H_{ve}=g_\psi(h_v,z_e).

Преимущество — адаптация структуры к задаче. Ограничения:

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

Функции потерь

Классификация вершин

{\cal L}_{\rm node}=-\sum_{v\in V_L}\sum_{c=1}^C y_{vc}\ln\hat y_{vc}.

Классификация гиперрёбер

{\cal L}_{\rm edge}=-\sum_{e\in{\cal E}_L}\sum_{c=1}^C y_{ec}\ln\hat y_{ec}.

Предсказание гиперрёбер

Для положительных и отрицательных примеров:

{\cal L}_{\rm pred}=-\sum_{e\in{\cal E}^+}\ln\hat p(e)-\sum_{e\in{\cal E}^-}\ln(1-\hat p(e)).

Качество сильно зависит от способа генерации отрицательных гиперрёбер. Случайные отрицательные примеры могут оказаться слишком простыми.

Кластеризация

Вложение Z можно оптимизировать совместно с кластерными центрами:

{\cal L}_{\rm clust}=\sum_{v\in V}\min_{1\leq j\leq k}\|z_v-\mu_j\|^2+\lambda{\rm Tr}(Z^{\mathsf T}L_{\cal H}Z).

Первый член соответствует k-means, второй сохраняет гиперграфовую гладкость.

Реконструкция структуры

Автоэнкодер может восстанавливать инцидентности:

{\cal L}_{\rm rec}=\sum_{v,e}{\rm BCE}(H_{ve},\hat H_{ve}).

При разреженном H необходимы выборка отрицательных инцидентностей или взвешенная функция потерь.

Вычислительная сложность

Пусть

n=|V|,\qquad m=|{\cal E}|,\qquad M=\sum_{e\in{\cal E}}|e|.

Спектральные методы

Одно умножение лапласиана на матрицу из d столбцов требует

O(Md)

при разреженной реализации.

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

O(n^3)

и непригодно для больших гиперграфов.

HGNN

Разреженная агрегация «вершины — гиперрёбра — вершины» требует

O(Md_l)

операций, а линейное преобразование —

O(nd_ld_{l+1}).

Память одного слоя составляет приблизительно

O(M+nd_l+md_l).

Внимание по инцидентностям

Если коэффициент вычисляется отдельно для каждой пары (v,e), стоимость равна

O(Md).

Для полного самовнимания внутри каждого гиперребра:

O\left(d\sum_{e\in{\cal E}}|e|^2\right).

Крупные гиперрёбра становятся основным вычислительным ограничением.

Клика-расширение

Число порождённых парных связей может достигать

O\left(\sum_{e\in{\cal E}}|e|^2\right).

Поэтому звёздное представление часто экономнее для гиперрёбер большой мощности.

Способы масштабирования

  • мини-пакеты вершин и гиперрёбер;
  • выборка инцидентностей;
  • ограничение мощности гиперрёбер;
  • разреженные матричные операции;
  • приближённый поиск соседей;
  • кластерное разбиение гиперграфа;
  • предварительное вычисление нормировок;
  • распределённая генерация сообщений;
  • низкоранговые аппроксимации.

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

Применения

Компьютерное зрение

Вершинами могут быть изображения, области, точки облака или объекты сцены. Гиперрёбра связывают:

  • визуально похожие объекты;
  • области одного изображения;
  • точки одной геометрической поверхности;
  • объекты с общим признаком;
  • наблюдения нескольких модальностей.

HGNN исследовался в задачах распознавания визуальных объектов и мультимодального представления.[1]

Сегментация изображений

Гиперребро может объединять несколько пикселей или суперпикселей с общей текстурой, цветом, расположением или принадлежностью одному региону. Это позволяет учитывать согласованность группы, а не только соседних пар.

Ограничение состоит в высокой стоимости построения гиперрёбер для изображений большого разрешения.

Социальные сети

Гиперрёбра естественно описывают:

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

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

Рекомендательные системы

Вершинами могут быть пользователи, товары и сеансы. Гиперребро может представлять:

  • один заказ;
  • пользовательскую сессию;
  • группу совместно просмотренных товаров;
  • общую категорию;
  • временной контекст.

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

Биоинформатика

Гиперграфы применяются для представления:

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

Hyper-SAGNN исследовался, в частности, на данных одно-клеточного Hi-C для моделирования взаимодействий переменного порядка.[1]

Анализ текстов

Вершинами могут быть слова, предложения, документы или сущности. Гиперрёбра задаются:

  • предложениями;
  • темами;
  • документами;
  • общими ключевыми словами;
  • совместными упоминаниями;
  • синтаксическими или семантическими группами.

Гиперграфовая модель не заменяет последовательное кодирование: если порядок слов существенен, необходимы дополнительные позиционные признаки или последовательная архитектура.

Моделирование знаний

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

r(v_1,\ldots,v_k).

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

Мультимодальное обучение

Гиперребро может связывать изображение, текст, аудио и метаданные одного объекта. Модель объединяет модальности через общую групповую структуру.

Ключевая проблема — отсутствие части модальностей и неодинаковая надёжность источников.

Сравнение методов

Метод Представление данных Требования Вычислительная стоимость Преимущества Ограничения
Спектральное обучение на гиперграфах Матрица инцидентности и веса Гиперграф задаётся заранее Собственные векторы; разреженно около O(kM) умножений Строгая связь с разрезами и гладкостью Трансдуктивность, стоимость спектрального разложения
HGNN Фиксированный взвешенный гиперграф и признаки Размеченные или частично размеченные вершины Около O(Md+nd^2) на слой Простая разреженная реализация Фиксированная агрегация, сглаживание
Гиперграфовая сеть внимания Гиперграф и обучаемые веса инцидентностей Достаточно данных для обучения внимания От O(Md) до O(\sum_e|e|^2d) Контекстно зависимая агрегация Более высокая стоимость и риск переобучения
Обычная GNN на клика-расширении Парный граф, полученный из гиперграфа Требуется правило преобразования Зависит от числа созданных парных рёбер Использование стандартных GNN Потеря идентичности гиперрёбер
Графовые нейронные сети Парные рёбра Естественная парная структура Около O(|E|d) на агрегацию Зрелые библиотеки и масштабируемость Не моделируют групповое отношение непосредственно
Спектральная кластеризация Матрица сходства обычного графа Парные сходства Спектральное разложение матрицы графа Нелинейные границы кластеров Не сохраняет происхождение групповых отношений
k-means Независимые векторы объектов Евклидово представление и число кластеров Около O(Tnkd) Простота и высокая скорость Игнорирование отношений и несферических кластеров
Глубокая нейронная сеть Тензоры или векторы фиксированной структуры Большая обучающая выборка Зависит от архитектуры Автоматическое извлечение признаков Структурные отношения нужно кодировать отдельно
Трансформер Последовательность или множество токенов Позиционное или структурное кодирование Полное внимание около O(n^2d) Гибкие дальние взаимодействия Нет встроенного понятия гиперребра; высокая стоимость

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

Ограничения обучения на гиперграфах

Неоднозначность построения структуры

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

Шумные гиперрёбра

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

Неравномерная мощность гиперрёбер

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

Гомофилия и гетерофилия

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

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

Чрезмерное сглаживание

При большом числе слоёв представления вершин могут становиться похожими:

h_u^{(l)}\approx h_v^{(l)}.

Для борьбы используются остаточные связи, нормализация, начальные признаки, разреживание структуры и ограничение глубины.

Избыточное сжатие информации

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

Ограниченная интерпретируемость

Даже при наличии явных гиперрёбер глубокая модель может использовать их непрозрачным образом. Веса внимания помогают анализу, но не гарантируют причинного объяснения.

Отсутствие единой спектральной теории

Для обычных графов существует стандартный набор лапласианов. Для гиперграфов предложено несколько неэквивалентных определений, основанных на:

Выводы, доказанные для одного лапласиана, нельзя автоматически переносить на другой.[1]

Когда гиперграф оправдан

Гиперграфовое обучение целесообразно, если:

  • отношение естественно объединяет три и более объекта;
  • важна принадлежность одной общей группе;
  • клика-расширение теряет контекст;
  • размеры групп несут информацию;
  • имеются признаки гиперрёбер;
  • нужно предсказывать или классифицировать группы;
  • данные мультимодальны;
  • структура инцидентности разрежена.

Обычный граф предпочтительнее, если:

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

Практический порядок построения модели

  1. Определить содержательный смысл вершины и гиперребра.
  2. Проверить, нельзя ли решить задачу на обычном графе без потери информации.
  3. Построить разреженную матрицу инцидентности.
  4. Проанализировать распределение степеней и размеров гиперрёбер.
  5. Нормировать признаки и веса.
  6. Выбрать спектральный или нейронный метод.
  7. Сравнить с обычной GNN на клика- и звёздном расширении.
  8. Сравнить с моделью без структуры.
  9. Провести абляцию способа построения гиперрёбер.
  10. Оценить чувствительность к шуму и крупным гиперрёбрам.
  11. Измерить время, память и качество на одинаковом разбиении данных.

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

Современные направления

  • обучаемое построение гиперграфа;
  • динамические и временные гиперграфы;
  • неоднородные и типизированные гиперграфы;
  • ориентированные и упорядоченные гиперрёбра;
  • гиперрёбра с собственными признаками;
  • контрастивное и самоконтролируемое обучение;
  • генеративные модели гиперграфов;
  • предсказание гиперрёбер переменного размера;
  • масштабируемая выборка;
  • устойчивость к шуму и структурным атакам;
  • объяснимые гиперграфовые модели;
  • объединение гиперграфов и трансформеров;
  • теоретический анализ выразительности.

Универсального лучшего алгоритма не существует. Спектральные методы удобны для малых и средних трансдуктивных задач, HGNN — для простого полуобучения, attention-модели — для неодинаковой значимости участников, а AllSet и UniGNN — для экспериментов с более общими функциями агрегации.

См. также

Примечания


Литература

  • Bai S., Zhang F., Torr P. H. S. Hypergraph Convolution and Hypergraph Attention // Pattern Recognition. — 2021. — Т. 110. — С. 107637.
Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%B0_%D0%B3%D0%B8%D0%BF%D0%B5%D1%80%D0%B3%D1%80%D0%B0%D1%84%D0%B0%D1%85_%28Hypergraph_Learning%29»
Личные инструменты