Гиперграфы

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

Версия от 14:30, 18 июля 2026; Bogdan Kormalov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM DeepSeek-V3 и проверена участником Bogdan Kormalov 18:30, 18 июля 2026 (MSD)

Гиперграф (англ. hypergraph) — обобщение понятия обычного графа, в котором каждое ребро (называемое гиперребром) может соединять не две, а произвольное количество вершин. Формально гиперграф представляет собой пару $H = (V, E)$ , где $V = {v_1, v_2, \dots, v_n}$ — множество вершин, а $E = {e_1, e_2, \dots, e_m}$ — множество гиперрёбер, каждое из которых является непустым подмножеством $V$ ( $e_i \subseteq V$ ).

В отличие от классического графа, где ребро есть неупорядоченная пара вершин ( $e \subseteq V, |e| = 2$ ), мощность гиперребра $|e|$ может быть любой, что позволяет моделировать отношения высших порядков. Если мощности всех гиперрёбер одинаковы и равны $k$ , гиперграф называется $k$ -равномерным (k-uniform). Обычный граф, таким образом, является 2-равномерным гиперграфом.

Содержание

1 Историческая справка
2 Основные определения и математический аппарат
3 Мотивация: почему обычных графов недостаточно
4 Практические приложения гиперграфов
5 Гиперграфовые нейронные сети (HGNN)
6 Матрица инцидентности и лапласиан гиперграфа
7 Связанные понятия
8 Литература

Историческая справка

Хотя отдельные структуры, являющиеся по сути гиперграфами, эпизодически возникали в топологии и комбинаторике ранее, формальное рождение теории гиперграфов как самостоятельного раздела дискретной математики связывают с выходом фундаментальной монографии Клода Бержа «Graphes et Hypergraphes» в 1969 году (английский перевод — 1973)Berge, C. (1973). Graphs and Hypergraphs. North-Holland Publishing Company.. Берж систематизировал свойства этих объектов, введя базовые понятия дуального гиперграфа, матрицы инцидентности и хроматического числа, заложив основу для дальнейших теоретических исследований.

В конце XX века интерес к гиперграфам поддерживался в основном в рамках комбинаторного дизайна, теории баз данных (моделирование многозначных зависимостей) и САПР. Однако взрывной рост приложений произошел в 2010-х годах с развитием сетевой науки и машинного обучения. Исследователи столкнулись с тем, что попарные связи (графы) фундаментально ограничены при описании коалиций, групповых взаимодействий и многокомпонентных химических реакций. Это привело к появлению аппарата гиперграфовых нейронных сетей (Hypergraph Neural Networks, HGNN)Feng, Y., You, H., Zhang, Z., Ji, R., & Gao, Y. (2019). Hypergraph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence. и анализу сигналов на гиперграфах.

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

Формальное определение и матрица инцидентности

Пусть $H = (V, E)$ — гиперграф с $n = |V|$ вершинами и $m = |E|$ гиперребрами. Структура гиперграфа полностью описывается матрицей инцидентности $\mathbf{H} \in {0, 1}^{n \times m}$ , где строки соответствуют вершинам, а столбцы — гиперребрам:

$h_{ij} = \begin{cases} 1, & v_i \in e_j \\ 0, & v_i \notin e_j \end{cases}$

В отличие от обычного графа, сумма элементов в столбце $j$ (степень гиперребра) может быть больше двух. Степень вершины $d(v_i)$ в гиперграфе вычисляется как количество инцидентных ей гиперрёбер: $d(v_i) = \sum_{j=1}^{m} h_{ij}$ .

Дуальный гиперграф

Ключевой особенностью теории гиперграфов является принцип двойственности. Дуальный гиперграф $H^* = (V^, E^)$ строится путем обмена ролями вершин и гиперрёбер. Вершинами $H^$ становятся гиперребра исходного графа, а гиперребрами — исходные вершины. Матрица инцидентности $H^$ есть транспонированная матрица $\mathbf{H}^T$ . Это свойство не имеет аналога в обычных графах и крайне полезно в теоретическом анализе.

Виды гиперграфов

В прикладных задачах важно различать:

k-равномерный гиперграф: все гиперрёбра содержат ровно $k$ вершин. Например, 3-равномерный гиперграф состоит из треугольников.

Симплициальный комплекс: наследственный гиперграф, где любое подмножество гиперребра также является гиперребром. Используется в топологическом анализе данных (TDA).

Взвешенный гиперграф: каждому гиперребру приписан вес $w(e_j) > 0$ , что отражает силу группового взаимодействия.

Мотивация: почему обычных графов недостаточно

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

Рассмотрим граф соавторства научной публикации. Если статья написана тремя авторами А, Б и В, в обычном графе мы получим треугольник из ребер (А-Б, Б-В, А-В). Глядя на этот треугольник, невозможно определить, было ли взаимодействие парным (три отдельные статьи двух авторов), или групповым (одна статья трех авторов). Гиперграф, вводя гиперребро {А, Б, В}, однозначно моделирует это высшее коалиционное взаимодействие. Эта уникальная способность гиперграфов фиксировать мультиобъектные инциденции делает их незаменимыми в современном анализе данных.

Практические приложения гиперграфов

Библиографические сети и соавторство

В библиометрии гиперграфы являются стандартом для моделирования научных коллабораций. Вершины — исследователи, гиперребра — публикации. Гиперребро соединяет всех соавторов конкретной статьи. Вес гиперребра может отражать импакт-фактор журнала или число цитирований. Анализ таких сетей позволяет выявлять устойчивые научные группы, вычислять меры центральности авторов с учетом размера коллектива (например, гиперграфовую степень или векторное центральность) и прогнозировать будущие коллаборацииPatro, G. K., et al. (2021). Hypergraph models for collaboration analysis. ACM Computing Surveys.

Биоинформатика и белок-белковые взаимодействия

Белки в клетке функционируют не изолированно попарно, а в составе мультибелковых комплексов. Гиперграф позволяет представить комплекс (например, рибосому) как одно гиперребро, инцидентное десяткам вершин-белков. Это критично для предсказания функций генов и идентификации комплексов. Методы кластеризации на гиперграфах эффективно выделяют плотные подгиперграфы, соответствующие реальным биологическим модулямZhou, D., Huang, J., & Schölkopf, B. (2006). Learning with hypergraphs: Clustering, classification, and embedding. Advances in neural information processing systems, 19..

Анализ социальных сетей

В онлайн-социологии гиперребро — это групповой чат в мессенджере, сообщество по интересам или тред на форуме. Гиперграфы позволяют исследовать распространение информации с учетом «эффекта затравки» (одномоментное воздействие на всю группу) и оценивать влияние не отдельных людей, а целых когорт. Модели распространения эпидемий (SIR-модели) на гиперграфах демонстрируют фазовые переходы, принципиально отличные от графовых моделей, из-за возможности одномоментного заражения группы вершин одним гиперребромBodó, Á., Katona, G. Y., & Simon, P. L. (2016). SIS epidemic propagation on hypergraphs. Bulletin of mathematical biology.

Гиперграфовые нейронные сети (HGNN)

Развитие геометрического глубокого обучения привело к обобщению графовых сверточных сетей (GCN) на случай гиперграфов. Классическая GCN Kipf, T. N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907. использует матрицу смежности $A$ (парные связи). Для гиперграфа строится лапласиан, опирающийся на матрицу инцидентности $\mathbf{H}$ .

Основная идея фреймворка HGNN Feng, Y., et al. (2019) заключается в двухэтапной передаче сообщений:

Агрегация признаков от вершин к гиперребрам (функция агрегации по строкам $\mathbf{H}$ ).

Агрегация признаков от гиперребер обратно к вершинам (функция агрегации по столбцам $\mathbf{H}$ ).

Слой гиперграфовой свертки может быть записан как:

$\mathbf{X}^{(l+1)} = \sigma\left(\mathbf{D}_v^{-1/2} \mathbf{H} \mathbf{W} \mathbf{D}_e^{-1} \mathbf{H}^T \mathbf{D}_v^{-1/2} \mathbf{X}^{(l)} \mathbf{\Theta}\right)$

где $\mathbf{D}_v$ и $\mathbf{D}_e$ — диагональные матрицы степеней вершин и гиперрёбер, $\mathbf{W}$ — матрица весов гиперрёбер, $\mathbf{\Theta}$ — обучаемые параметры. Это позволяет извлекать не только признаки «соседей», но и признаки «контекстных групп», к которым принадлежит вершина. HGNN находят применение в распознавании 3D-объектов, анализе медицинских снимков и графах знаний.

Матрица инцидентности и лапласиан гиперграфа

Эффективное вычисление признаков требует построения оператора, аналогичного графовому Лапласиану. Вводится диагональная матрица степеней вершин $\mathbf{D}_v \in \mathbb{R}^{n \times n}$ и диагональная матрица степеней гиперрёбер $\mathbf{D}_e \in \mathbb{R}^{m \times m}$ . Нормализованный гиперграфовый Лапласиан Чжоу и др.Zhou, D., Huang, J., & Schölkopf, B. (2006). определяется как:

$\mathbf{L} = \mathbf{I} - \mathbf{D}_v^{-1/2} \mathbf{H} \mathbf{W} \mathbf{D}_e^{-1} \mathbf{H}^T \mathbf{D}_v^{-1/2}$

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

Связанные понятия

Граф — частный случай 2-равномерного гиперграфа.

Матроид — комбинаторная абстракция линейной независимости, тесно связанная с гиперграфами через системы независимости.

Симплициальный комплекс — гиперграф, замкнутый относительно взятия подмножеств, широко используемый в топологическом анализе данных (TDA) для анализа «формы» данных.

Литература

Berge, C. (1973). Graphs and Hypergraphs. North-Holland Publishing Company. (Классическая монография, заложившая основы теории).

Bretto, A. (2013). Hypergraph Theory: An Introduction. Springer. (Современный математический обзор).

Feng, Y., You, H., Zhang, Z., Ji, R., & Gao, Y. (2019). Hypergraph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 3558-3565. (Основополагающая работа по HGNN).

Patro, G. K., et al. (2021). A survey on hypergraph mining: Patterns, tools, and generators. ACM Computing Surveys, 54(1), 1-38. (Обзор приложений в Data Science).

Zhou, D., Huang, J., & Schölkopf, B. (2006). Learning with hypergraphs: Clustering, classification, and embedding. Advances in neural information processing systems, 19. (Введение гиперграфового лапласиана и спектральных методов).

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%93%D0%B8%D0%BF%D0%B5%D1%80%D0%B3%D1%80%D0%B0%D1%84%D1%8B»