ИИ-метод LUCID находит сообщества в графах без разметки данных

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

В новой работе на arXiv представлен метод LUCID, который использует большие языковые модели (LLM) для решения этой задачи. Подход полностью unsupervised, то есть не требует разметки, и training-free — не нуждается в дополнительном обучении. При этом он сохраняет интерпретируемость: LLM переводит скрытые закономерности в явные логические правила.

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

На первом этапе Local-View Community Initialization граф кодируется с помощью k-эго контекстов и unsupervised-ролей узлов. На втором этапе Multi-factor Community Merge итеративно объединяет локальные сообщества на основе правил, сформулированных LLM. Третий этап Multi-grain Community Refinement применяет параллельные грубые и точные правила для снижения граничного шума. Наконец, Global-view Community Selection отбирает качественные сообщества по топологической компактности и чёткости границ.

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

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