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

Сравнение графов — фундаментальная задача в анализе данных, но традиционные подходы часто дают сбои при работе с разреженными, зашумлёнными или неполными графами. Новый метод Diffusion Semi-Relaxed Fused Gromov-Wasserstein (DsrFGW), представленный в работе на arXiv, решает эту проблему, объединяя оптимальный транспорт с диффузионными процессами. Это позволяет учитывать как локальные признаки узлов, так и глобальные паттерны распространения сигнала, делая сравнение более робастным в реальных условиях.

Как работает DsrFGW

DsrFGW развивает идеи семейства методов Gromov-Wasserstein (GW), которые сравнивают графы на основе попарных расстояний между узлами. Полурелаксированные варианты, такие как srGW и srFGW, уже позволяют сопоставлять графы разного размера, но их точность резко падает при наличии шума или пропущенных рёбер. DsrFGW добавляет в эту схему диффузионные процессы: информация распространяется между узлами, и графы считаются похожими, если они обеспечивают сходные паттерны передачи информации. Это напоминает идею Graph Diffusion Distance, но интегрированную в оптимизационную структуру оптимального транспорта.

Почему это важно

Традиционные методы сравнения графов, такие как Gromov-Wasserstein и его полурелаксированные варианты (srGW, srFGW), эффективны, но плохо работают с разреженными, зашумлёнными или частично наблюдаемыми графами. DsrFGW решает эту проблему, используя идею Graph Diffusion Distance: графы считаются похожими, если они обеспечивают сходные паттерны передачи информации. Это делает метод более робастным в реальных условиях, где данные часто неполны или зашумлены.

Детали эксперимента

Авторы протестировали DsrFGW на 36 синтетических задачах попарного сопоставления графов трёх уровней сложности (лёгкий, средний, сложный). Результаты показали превосходство над srFGW: точность улучшилась на 0–20 процентных пунктов, а Adjusted Rand Index (ARI) показал драматический рост. В задачах средней сложности srFGW часто давал отрицательный ARI (хуже случайного), тогда как DsrFGW демонстрировал лучшую кластеризацию. Даже при сильном шуме DsrFGW улучшил качество кластеризации в 92% синтетических задач, при этом оптимальный масштаб диффузии адаптировался к сложности задачи.

Какие задачи решает DsrFGW

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

Как DsrFGW справляется с шумом и неполнотой данных?

Диффузионные процессы в DsrFGW позволяют информации распространяться между узлами, снижая чувствительность к шуму и пропущенным рёбрам. В отличие от srFGW, который опирается только на точные попарные расстояния, DsrFGW использует сглаженные представления, что делает его более устойчивым к искажениям. Например, при удалении 20% рёбер точность srFGW падает на 30%, а DsrFGW — только на 10%.

Что пока неизвестно

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