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

Основная информация

• ID статьи: 2511.11245
• Название: Heterogeneous Attributed Graph Learning via Neighborhood-Aware Star Kernels
• Авторы: Hong Huang, Haiming Chen, Hang Gao, Chengyu Yao
• Учреждение: Институт программного обеспечения Китайской академии наук
• Классификация: cs.LG (Машинное обучение)
• Дата публикации: 14 ноября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2511.11245

Аннотация

Атрибутированные графы широко распространены в социальных сетях, биоинформатике и хеминформатике, обычно имея нерегулярную топологию и смешанные числовые и категориальные атрибуты. Хотя методы ядер графов обеспечивают теоретическую основу для измерения сходства графов, существующие методы ядер испытывают трудности с одновременным захватом гетерогенной семантики атрибутов и информации о соседстве. В данной работе предлагается NASK (Neighborhood-Aware Star Kernels) — новый метод ядра графа. NASK использует экспоненциальное преобразование коэффициента сходства Гауэра для эффективного моделирования числовых и категориальных признаков и применяет звездные подструктуры, расширенные итерацией Вейсфейлера-Лемана, для интеграции информации о многомасштабной структуре соседства. Теоретически доказано, что NASK является положительно определённым, обеспечивая совместимость с фреймворками обучения на ядрах, такими как SVM. Обширные эксперименты на 11 атрибутированных графах и 4 крупномасштабных реальных графовых эталонах демонстрируют постоянное превосходство NASK над 16 современными базовыми методами (включая 9 ядер графов и 7 графовых нейронных сетей).

Исследовательский контекст и мотивация

1. Основные проблемы, которые необходимо решить

Обучение на атрибутированных графах сталкивается с двумя основными вызовами:

• Моделирование гетерогенных атрибутов: узлы и рёбра графа одновременно содержат числовые и категориальные атрибуты, существующие методы испытывают трудности с их унифицированной обработкой
• Захват структурной информации: необходимо эффективно интегрировать информацию о локальной структуре соседства и зависимостях на несколько шагов

2. Важность проблемы

Атрибутированные графы имеют широкое применение в нескольких критических областях:

• Хеминформатика: представление молекулярной структуры (типы атомов как категориальные атрибуты, химические свойства как числовые атрибуты)
• Биоинформатика: анализ структуры белков
• Социальные сети: профилирование пользователей и моделирование отношений

3. Ограничения существующих методов

Недостатки методов ядер графов:

• Методы дискретизации (например, Hash Graph Kernel) приводят к потере исходной семантики атрибутов
• Методы на основе распределений (например, WWL) не имеют формальных гарантий положительной определённости
• Методы прямого комбинирования (взвешенное суммирование) приводят к потере семантической информации

Ограничения графовых нейронных сетей:

• Выразительная способность теоретически не превышает тест 1-WL
• Низкая стабильность в сценариях с малым количеством примеров
• Недостаточная интерпретируемость

4. Исследовательская мотивация

Данная работа направлена на разработку метода ядра графа, который одновременно удовлетворяет следующим требованиям:

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

Основные вклады

1. Предложение метода NASK: первый положительно определённый метод ядра графа, эффективно обрабатывающий одновременно гетерогенные атрибуты и информацию о структуре соседства
2. Разработка положительно определённой функции сходства атрибутов: на основе экспоненциального преобразования коэффициента сходства Гауэра с теоретическим доказательством положительной определённости, унифицированное моделирование числовых и категориальных признаков
3. Слияние звездных подструктур и итерации WL: использование звёздных графов как локальных структурных единиц, реализация многошаговой агрегации информации о соседстве через алгоритм WL
4. Полный теоретический анализ: формальное доказательство положительной определённости NASK и всех его компонентов, обеспечение индукции эффективного воспроизводящего ядерного гильбертова пространства (RKHS)
5. Обширная экспериментальная верификация: превосходство над 16 сильными базовыми методами на 15 наборах данных эталонов, максимальное улучшение точности на 10,2%

Подробное описание метода

Определение задачи

Входные данные: набор атрибутированных графов $\mathcal{G} = \{G_1, G_2, ..., G_N\}$, где каждый граф $G = \langle A, V, E, \lambda, F \rangle$

• $V$: множество узлов
• $E$: множество рёбер
• $A$: множество имён атрибутов
• $F$: множество значений атрибутов (содержит числовые и категориальные значения)
• $\lambda: A \times (V \cup E) \rightarrow F$: функция отображения атрибутов

Выходные данные: матрица ядра между графами $K \in \mathbb{R}^{N \times N}$, где $K_{ij} = K_{NAS}(G_i, G_j)$

Цель: разработка положительно определённой функции ядра для задачи классификации графов (через SVM)

Архитектура модели

NASK использует трёхуровневый прогрессивный дизайн:

Уровень 1: Функция сходства атрибутов P

Для одного измерения атрибута $d$ сначала определяется сходство Гауэра:

Числовые атрибуты: $s_d(x_d, x'_d) = 1 - \frac{|x_d - x'_d|}{\text{range}_d}$

Категориальные атрибуты: $s_d(x_d, x'_d) = \begin{cases} 1, & \text{если } x_d = x'_d \\ 0, & \text{иначе} \end{cases}$

Затем применяется экспоненциальное преобразование для получения положительно определённого ядра: $s'_d(x_d, x'_d) = \exp(-\gamma(1 - s_d(x_d, x'_d)))$

Сходство многомерных атрибутов: $P(v, v') = \frac{1}{D} \sum_{d=1}^{D} s'_d(\lambda(A,v)_d, \lambda'(A',v')_d)$

Ключевое инновационное решение: путём доказательства того, что $f_d(x_d, x'_d) = 1 - s_d(x_d, x'_d)$ является условно отрицательно определённой (CND) функцией, используя классический результат Берга и др., гарантируется положительная определённость после экспоненциального преобразования.

Уровень 2: Ядро звездной подструктуры $k_s$

Определение звездной подструктуры: $S = \langle A, V, E, \lambda, F, C, L \rangle$

• $C$: центральный узел
• $L$: множество листовых узлов (все соседи центрального узла)

Извлечение звездной подструктуры: $\mathcal{F}(v, G) = \langle G.A, \{v\} \cup N(v), \{(v,u) \in E | u \in N(v)\}, G.\lambda, G.F, v, N(v) \rangle$

Ядро звездной подструктуры: $k_s(S, S') = \sum_{n \in R^{-1}(S)} \sum_{n' \in R^{-1}(S')} P(C, C') \cdot P(n, n')$

где $R^{-1}(S)$ — эффективная декомпозиция звёздного графа (узлы и рёбра), член $P(C, C')$ подчёркивает важность сходства центрального узла.

Уровень 3: Ядро звезды, учитывающее соседство $K_{NAS}^{(H)}$

Расширение итерации WL: $\mathcal{L}: S^{h-1} \times G \rightarrow S^h$

Инициализация: $\hat{S}^{(1)}(G) = \{\mathcal{F}(v, G) | v \in V\}$

Рекурсия: $\hat{S}^{(h)}(G) = \{\mathcal{L}(S^{(h-1)}, G) | S^{(h-1)} \in \hat{S}^{(h-1)}(G)\}$

Окончательное определение ядра: $K_{NAS}^{(H)}(G, G') = \sum_{h=1}^{H} \sum_{S \in \hat{S}^{(h)}(G)} \sum_{S' \in \hat{S}^{(h)}(G')} k_s(S, S')$

При $H=1$ вырождается в базовое звездное ядро $K_S$; с увеличением $H$ захватываются взаимодействия структур более высокого порядка.

Технические инновационные решения

1. Унифицированная обработка гетерогенных атрибутов

• Сравнение с кодированием One-Hot: избежание взрыва размерности и проблем разреженности
• Сравнение с евклидовым расстоянием: нормализация числовых атрибутов, предоставление значимого сходства для категориальных атрибутов
• Преимущества: сохранение вычислительной эффективности при сохранении исходной семантики

2. Обоснованность звездных подструктур

• Универсальность: повсеместно встречаются в реальных графах
• Семантичность: захват локальных паттернов соседства узла
• Эффективность: линейная временная сложность $O(|V|)$ для извлечения всех звёздных графов
• Сравнение со случайными блужданиями: фиксированное центральное представление обеспечивает более стабильные семантические отношения

3. Необходимость итерации WL

• Преодоление ограничений фиксированных подструктур
• Пошаговая агрегация информации о многошаговом соседстве
• Теоретическое усиление выразительной способности (приближение к k-WL тесту)
• Абляционные эксперименты показывают, что удаление WL приводит к снижению производительности на 3,5%-6,7%

4. Полнота теоретических гарантий

Полная цепь доказательства положительной определённости:

• Лемма 1: $f_d$ является CND
• Лемма 2: $s'_d$ является положительно определённой
• Теорема 1: $P$ является положительно определённой
• Теорема 2: $k_s$ является положительно определённой
• Теорема 3: $K_S$ является положительно определённой
• Теорема 4: $K_{NAS}^{(H)}$ является положительно определённой

Анализ сложности

Временная сложность в худшем случае: $O(Hn^2(n+m)^2d)$

• $H$: глубина итерации WL
• $n, m$: количество узлов и рёбер
• $d$: размерность атрибутов

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

Экспериментальная установка

Наборы данных

Графы с категориальными атрибутами (5 наборов):

• MUTAG (188 графов, мутагенность молекул)
• NCI1 (4110 графов, активность соединений)
• PTC_MR (344 графа, канцерогенность)
• D&D (1178 графов, структура белков)
• PROTEINS (1113 графов, функция белков)

Графы с числовыми атрибутами (2 набора):

• SYNTHETIC (4337 графов, синтетические молекулы)
• SYNTHIE (400 графов, 4 класса синтетических данных)

Графы с гетерогенными атрибутами (4 набора):

• ENZYMES (600 графов, классификация ферментов, 18-мерные числовые + категориальные атрибуты)
• PROTEINS_full (1113 графов, смешанные атрибуты)
• BZR (405 графов, молекулы лекарств)
• COX2 (467 графов, молекулы лекарств)

Крупномасштабные реальные графы (4 набора):

• Pubmed (сеть цитирования, признаки TF-IDF)
• Cora (2708 статей, 1433 измерения)
• Citeseer (3327 статей, 3703 измерения)
• Pokec (социальная сеть, атрибуты пользователей)

Метрики оценки

• Точность классификации: 10-кратная перекрёстная проверка, повторённая 10 раз (всего 100 запусков)
• Формат отчёта: среднее значение ± стандартное отклонение
• Статистическая значимость: обеспечивается множественными запусками

Методы сравнения

Методы ядер графов (9 методов):

• WL-VH, PK, GH, ML: ранние методы
• HGK-WL: ускорение хешированием
• WWL: расстояние Вассерштейна
• RetGK: вероятность возврата
• RWK: регуляризованное случайное блуждание
• SWWL: срезанное расстояние Вассерштейна

Графовые нейронные сети (7 методов):

• GCN, GraphSAGE, GIN: классические архитектуры
• GAT: механизм внимания
• KerGNN, AKGNN, KAGNN: ядро-усиленные GNN

Детали реализации

Конфигурация NASK:

• $\gamma$: выбирается через набор валидации
• Глубина WL $H$: по умолчанию 4 (определено анализом чувствительности)
• Параметр SVM $C$: поиск по сетке из $\{10^{-3}, ..., 10^3\}$

Конфигурация GNN:

• 2-слойная архитектура, 64 скрытых единицы на слой
• Активация ReLU, глобальное суммирующее объединение
• Скорость обучения: {0.001, 0.005, 0.01}
• Ранняя остановка: терпение=10

Аппаратное окружение:

• GPU: NVIDIA RTX 4090
• Все методы оцениваются на одинаковом оборудовании

Результаты экспериментов

Основные результаты

Графы с числовыми и гетерогенными атрибутами (Таблица 1)

Ключевые выводы:

• Достижение SOTA на всех 6 наборах данных
• Среднее улучшение на 2,0% по сравнению с лучшим методом ядра графа
• Значительное превосходство над методами GNN (например, GIN на ENZYMES только 59,6%)

Графы с категориальными атрибутами (Таблица 2)

Ключевые выводы:

• Наиболее значительное улучшение на PTC_MR (+6,2%), демонстрирующее сильную способность моделирования сложных молекулярных структур
• На PROTEINS улучшение на 9,5% по сравнению с GNN (против GCN 63,1%)

Крупномасштабные реальные графы (Таблица 3)

Ключевые выводы:

• Сохранение оптимальности на всех крупномасштабных наборах данных
• Доказательство масштабируемости и практической применимости

Абляционные эксперименты

Анализ вклада компонентов (Таблица 4, MUTAG/PTC_MR/PROTEINS_full/BZR):

Подробный анализ:

1. Важность звездной подструктуры:
   • Замена на случайное блуждание приводит к снижению на D&D на 21,5%
   • Фиксированное центральное представление захватывает более богатые семантические отношения
2. Преимущества функции сходства атрибутов P:
   • На PROTEINS_full на 3,7% выше, чем One-Hot
   • На 2,2% выше, чем евклидово расстояние
   • Способность унифицированной обработки смешанных атрибутов является ключевой
3. Необходимость итерации WL:
   • Удаление приводит к снижению на 3,5%-6,7%
   • Информация о многошаговом соседстве критична для моделирования сложных структур

Анализ чувствительности к глубине WL

Тренд точности (Рисунок 2a):

• От NASK-1 к NASK-4: постоянное улучшение точности
• NCI1: 85,0% → 88,0% (+3,0%)
• PROTEINS: 79,8% → 82,5% (+2,7%)
• NASK-5: переобучение на некоторых наборах данных

Время выполнения (Рисунок 2b):

• От NASK-4 к NASK-5: значительное увеличение времени выполнения
• NCI1: +28,7%
• PROTEINS: +41,8%

Оптимальная конфигурация: NASK-4 достигает лучшего баланса между точностью и эффективностью

Анализ конкретных случаев

Визуализация молекулярного графа NCI1 (Рисунок 3):

• Демонстрация расширения звездной подструктуры от k=1 к k=4 шагам
• k=1: захват прямого химического окружения (простые функциональные группы)
• Увеличение k: захват более крупных подструктур и зависимостей отношений
• Верификация эффективности разработки извлечения звездной подструктуры

Тепловая карта вероятностей классов (Рисунок 6):

• Сильные вертикальные полосы: модель назначает высокую уверенность классам
• Редкие и сконцентрированные неправильно классифицированные примеры
• Демонстрация дискриминативной способности и согласованности предсказаний

Анализ робастности

Эксперименты с возмущением атрибутов (Рисунок 5):

Гауссов шум:

• BZR: точность остаётся >86% (шум 30%)
• COX2: остаётся >77%
• Медианная точность стабильна

Маскирование признаков:

• Более значительное снижение производительности, но остаётся конкурентоспособным
• Узкий межквартильный размах демонстрирует стабильность

Вывод: NASK демонстрирует лучшую толерантность к непрерывным возмущениям, чем потеря дискретной информации

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

Верификация эффективности (Таблица 6):

• MUTAG: 0,61s (против ML 8+ часов)
• NCI1: 12 мин (против GH 3,7 часов)
• PROTEINS_full: 59s (против ML 2,8 часов)

Ключевые преимущества:

• На несколько порядков быстрее, чем GH и ML
• Конкурентоспособно с лёгкими методами (PK, RetGK)
• Превосходство на средних и крупномасштабных наборах данных

Связанные работы

1. Ранние методы ядер графов

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

2. Методы дискретизации

• Hash Graph Kernel (HGK): преобразование атрибутов функциями хеширования
• Преимущества: хорошая масштабируемость
• Недостатки: потеря исходной семантики атрибутов
• Улучшение NASK: сохранение исходной информации об атрибутах

3. Методы на основе распределений

• WWL: на основе расстояния Вассерштейна
• Isolation Graph Kernel: ядро среднего значения ядра
• Проблема: отсутствие формальных гарантий положительной определённости
• Улучшение NASK: полное теоретическое доказательство

4. Методы взвешенного комбинирования

• Прямое взвешенное суммирование: R-convolution ядро + оптимальное назначающее ядро
• Проблема: потеря семантической информации
• Улучшение NASK: унифицированный фреймворк совместного моделирования

5. Графовые нейронные сети

• GCN/GIN/GraphSAGE: архитектуры передачи сообщений
• Выразительная способность: теоретически не превышает 1-WL
• Проблема малых выборок: низкая стабильность
• Преимущество NASK: лучшая интерпретируемость и стабильность

6. Ядро-усиленные GNN

• AKGNN/KerGNN/KAGNN: комбинирование методов ядер
• Остающиеся проблемы: недостаточное моделирование атрибутов
• Позиционирование NASK: чистый метод ядра с более сильными теоретическими гарантиями

Заключение и обсуждение

Основные выводы

1. Эффективность метода: NASK полностью превосходит 16 сильных базовых методов на 15 эталонах, среднее улучшение 2-6%
2. Полнота теории: полное доказательство положительной определённости, гарантирующее индукцию эффективного RKHS, обеспечивающее сходимость и обобщающую способность алгоритмов обучения, таких как SVM
3. Унифицированная способность моделирования: успешное решение проблемы совместного моделирования гетерогенных атрибутов и структурной информации
4. Практичность: сохранение конкурентоспособности на крупномасштабных реальных графах, приемлемое время выполнения

Ограничения

1. Вычислительная сложность:
   • Худший случай $O(Hn^2(n+m)^2d)$
   • Хотя оптимизация отсечением значительна, на сверхкрупномасштабных графах (миллионы узлов) может быть ограничена
2. Чувствительность гиперпараметров:
   • Параметр $\gamma$ требует оптимизации на наборе валидации
   • Выбор глубины WL $H$ требует компромисса между точностью и эффективностью
3. Предположения:
   • Предполагается известность диапазона атрибутов (для нормализации)
   • Обработка пропущенных атрибутов не обсуждается подробно
4. Границы выразительной способности:
   • Хотя превосходит 1-WL, всё ещё ограничена k-WL
   • Может быть неспособна различать некоторые проблемы изоморфизма графов высокого порядка

Направления будущих исследований

1. Приближённые алгоритмы:
   • Стратегии выборки для уменьшения количества пар звездных подструктур
   • Низкоранговая аппроксимация для ускорения вычисления матрицы ядра
2. Слияние с глубоким обучением:
   • Использование NASK как механизма внимания GNN
   • Сквозное обучение параметров ядра
3. Расширение на динамические графы:
   • Обработка временных атрибутированных графов
   • Инкрементальное обновление матрицы ядра
4. Многозадачное обучение:
   • Классификация узлов и предсказание ссылок
   • Задачи генерации графов

Глубокая оценка

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

1. Теоретическая строгость (★★★★★)

• Полная цепь доказательства положительной определённости (6 теорем/лемм)
• Использование классических результатов CND функций и теоремы Берга
• Формальные гарантии сходимости алгоритмов обучения
• Это относительно редко в области методов ядер графов, большинство методов не имеют теоретических гарантий

2. Инновационность метода (★★★★★)

• Моделирование атрибутов: первое применение экспоненциального преобразования коэффициента Гауэра в ядрах графов, баланс между эффективностью и выразительной способностью
• Моделирование структуры: комбинация звездных подструктур и итерации WL является новой, баланс между локальной и глобальной информацией
• Унифицированный фреймворк: бесшовная интеграция гетерогенных атрибутов и структуры, избежание потери информации

3. Полнота экспериментов (★★★★★)

• Разнообразие наборов данных: 15 наборов данных охватывают категориальные/числовые/гетерогенные атрибуты
• Полнота базовых методов: 16 сильных базовых методов (9 ядер графов + 7 GNN)
• Полнота абляции: систематический анализ вклада каждого компонента
• Верификация робастности: эксперименты с возмущением шума
• Визуальный анализ: анализ конкретных случаев повышает интерпретируемость

4. Ясность письма (★★★★☆)

• Поэтапное описание метода
• Подробные математические выводы и доказательства (приложение)
• Богатые диаграммы для поддержки понимания
• Небольшой недостаток: некоторые символы не определены перед первым использованием

5. Практическая ценность (★★★★☆)

• Относительно простая реализация (на основе существующих библиотек)
• Приемлемое время выполнения
• Применимо к нескольким практическим областям (химия, биология, социальные сети)

Недостатки

1. Ограничения масштабируемости (★★★☆☆)

• Хотя показывает хорошие результаты на графах среднего размера, применимость к графам уровня миллионов узлов не верифицирована
• Хранение матрицы ядра $O(N^2)$ может стать узким местом на крупных наборах данных
• Рекомендация: предоставить приближённые алгоритмы или распределённую реализацию

2. Детали экспериментальной установки (★★★☆☆)

• Выбор гиперпараметров некоторых базовых методов не описан подробно
• Обучение GNN с относительно небольшим количеством эпох (максимум 100), может быть недостаточно сходящимся
• Отсутствие статистических тестов значимости (например, t-тест)

3. Глубина сравнительного анализа (★★★☆☆)

• Теоретическое сравнение с методами, такими как WWL, недостаточно глубоко
• Почему гарантия положительной определённости важна на практике? Отсутствуют анализы случаев отказа
• Рекомендация: демонстрация примеров, где неположительно определённые ядра приводят к отказу SVM

4. Обсуждение обобщающей способности (★★★☆☆)

• Производительность на синтетических наборах данных не анализируется отдельно
• Способность обобщения между областями (например, от химии к социальным сетям) не оценивается
• Сценарии обучения с малыми выборками не исследуются

5. Пространство для оптимизации вычислений (★★★☆☆)

• Стратегии параллелизации вычисления матрицы ядра не обсуждаются
• Потенциал ускорения GPU не полностью использован
• Детали реализации стратегии отсечения недостаточны

Оценка влияния

Вклад в область (★★★★★)

• Теоретический вклад: новая парадигма для положительной определённости ядер графов
• Методологический вклад: унифицированное решение для моделирования гетерогенных атрибутов
• Эмпирический вклад: установление новых SOTA на нескольких эталонах

Практическая ценность (★★★★☆)

• Хеминформатика: эффективный инструмент для предсказания молекулярных свойств
• Биоинформатика: классификация функции белков
• Ограничение: требует определённого фонового знания методов ядер

Воспроизводимость (★★★★☆)

• Преимущества:
  • Подробное описание метода
  • Полные математические формулы
  • Общедоступные наборы данных
• Недостатки:
  • Код не открыт (на момент публикации статьи)
  • Некоторые детали реализации (например, пороги отсечения) не ясны

Вдохновляющий потенциал (★★★★★)

• Направления последующих работ:
  • Слияние методов ядер и глубокого обучения
  • Расширение на динамические и временные графы
  • Применение в других областях (например, рекомендательные системы)

Применимые сценарии

Сценарии с сильной рекомендацией

1. Классификация графов с малыми выборками: когда данные обучения ограничены, методы ядер более стабильны, чем GNN
2. Атрибутированные графы с гетерогенными атрибутами: одновременное наличие числовых и категориальных атрибутов
3. Высокие требования к интерпретируемости: необходимость понимания основы решений модели
4. Требования теоретических гарантий: критические приложения, требующие гарантий сходимости

Применимые сценарии

1. Графы среднего размера: узлы <10 000
2. Статические графы: структура и атрибуты не меняются со временем
3. Контролируемое обучение: доступны помеченные данные

Не рекомендуемые сценарии

1. Сверхкрупномасштабные графы: миллионы узлов, вычислительные затраты слишком высоки
2. Графы без атрибутов: чистая структурная информация, методы WL ядра проще
3. Предсказание в реальном времени: задержка вычисления матрицы ядра высока
4. Неконтролируемое обучение: метод разработан для контролируемой классификации

Комплексная оценка

Избранные ссылки

1. Haussler (1999): Convolution kernels on discrete structures - теоретическая основа R-convolution
2. Berg et al. (1984): Harmonic Analysis on Semigroups - классические результаты CND функций и положительно определённых ядер
3. Gower (1971): A general coefficient of similarity - исходная статья коэффициента сходства Гауэра
4. Leman & Weisfeiler (1968): исходная статья алгоритма WL
5. Togninalli et al. (2019): WWL kernel - основной конкурирующий метод
6. Morris et al. (2023): Weisfeiler and Leman go machine learning - обзор методов WL

Резюме

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