Bridging the Gap between Community and Node Representations: Graph Embedding via Community Detection
https://arxiv.org/abs/1912.08808
https://github.com/eXascaleInfolab/daor
AGPL-3.0 License, C++ (в качестве бэка для CommunityDetection их же разработка из статьи выше)
Продолжение статьи выше.
TL;DR авторы предлагают использовать алгоритмы CommunityDetection для построения графовых эмбеддингов. Сравнивают с Node2Vec/DeepWalk, LINE и VERSE (от участника ODS @xgfs). На задачах классификации вершин их разработка (по их бенчмаркам) обходит как DeepWalk-like, так и LIME с VERSE. На задачах предсказания связей Node2Vec и VERSE выглядят лучше, но разработка авторов в топ-3.
По сути идея на поверхности и очень красивая. Мы знаем очень много классных алгоритмов CommunityDetection, которые выдают иерархию сообществ. Это все Louvain-стайл алгоритмы, а также "старые" агломеративные алгоритмы, типа Girvan-Newman и прочих. И эта иерархия и является их скрытым представлением для вершин.
Авторы идут от самых больших кластеров к самым маленьким. Чтобы не плодить кучу одинаковых эмбеддингов (в Louvain некоторые кластеры могут вообще не меняться от шага к шагу), они накладывают условие, что новый эмбеддинг добавляется лишь при условии, что плотность весов в кластере больше, чем в любом его супер-кластере (т.е. они ищут "ядро" каждого кластера верхнего уровня иерархии).
Выглядит на самом деле очень-очень круто по следующим причинам:
можно использовать множество разных алгоритмов CommunityDetection, включая Louvain, для которого есть реализации в большинстве пакетов
фичи получаются очень хорошо интерпретируемые - по сути это сообщества
работает мега быстро (я не уверен, что они именно там с чем сравнивают, но если верить их табличкам, то примерно в 1000-и раз быстрее, чем VERSE, LINE, Node2Vec)
можно переиспользовать уже полученные результаты кластеризаци
можно использовать как supervised-определитель того, какой уровень иерархии сообществ на какую задачу влияет (это особенно круто, т.к. тот же Louvain выдает сообщества от десятков тысяч сообществ в начале, до десятков в конце и понять какой уровень лучше изучать бывает трудно)
parameter free подход (как и все Louvain-style алгоритмы он не требует настройки), хотя руками обрезать пространство эмбеддингов все же можно
они там пишут про робастность, но с этим я не очень понял