FastAlign: алгоритм оптимального транспорта ускоряет выравнивание сетей до 32 раз
Выравнивание сетей — задача нахождения соответствий между узлами разных графов, востребованная в анализе соцсетей, обнаружении мошенничества и интеграции графов знаний. Существующие методы на основе оптимального транспорта (OT) часто жертвуют масштабируемостью ради точности, работая с плотными матрицами.
В новой работе на arXiv исследователи предлагают FastAlign — фреймворк, который сохраняет исходную OT-формулировку, но переосмысливает вычисления как набор повторяющихся смешанных разреженно-плотных операций. Это позволяет избежать построения полных матриц на каждом шаге.
Ключевые инновации: слияние операций, специфичных для предметной области, и кастомное SpMM-ядро (разреженное умножение матриц). Такой подход сочетает разреженные графовые вычисления с эффективной обработкой плотных подзадач.
Тесты показали, что FastAlign обеспечивает качество выравнивания, сопоставимое с лучшими OT-методами, при значительном снижении времени выполнения. На CPU ускорение составило от 3,89 до 9,45 раза, на GPU — от 2,24 до 32,54 раза в зависимости от конфигурации.
Авторы отмечают, что FastAlign не вводит новую модель выравнивания, а оптимизирует существующую OT-вычислительную схему. Это делает его универсальным инструментом для задач, где важны как точность, так и скорость.
Разработка может найти применение в социальных сетях для сопоставления пользователей, в финансовом секторе для выявления мошеннических схем и в построении крупномасштабных графов знаний.
