В новом документе мультиинституциональной исследовательской группы предлагается CW Networks, метод передачи сообщений, который обеспечивает лучшую выразительность, чем обычно используемые графовые нейронные сети (GNN), и позволяет получать самые современные результаты в различных наборах молекулярных данных.
Выразительная сила GNN в основном отражает их способность различать, являются ли два заданных графа изоморфными или нет. Однако недавние исследования показали, что GNN борются с дальнодействующими взаимодействиями и не имеют принципиального способа моделирования структур более высокого порядка, что ограничивает их выразительную способность.
В статье Weisfeiler и Lehman Go Cellular: CW Networks исследователи из Кембриджского университета, Имперского колледжа Лондона и Twitter, UCLA, MPI-MIS, SJTU и UNSW предлагают сети CW (CWN). Новая схема передачи сообщений позволяет принципиальное моделирование сигналов более высокого порядка и сжатие расстояний между узлами. Он действует на обычные клеточные комплексы и демонстрирует более сильную экспрессивную способность, чем GNN.
Проблема изоморфизма графов является NP-промежуточной, и тест Вайсфейлера-Лемана (WL), представленный в статье 1968 года Приведение графа к канонической форме и алгебре, возникающей во время этой редукции, может использоваться для оценки выразительной силы современных GNN.
Команда сначала показывает, как преобразовывать графы в клеточные комплексы более высокой размерности, выполняя уточнение цвета на полученных клеточных комплексах, чтобы упростить оценку их изоморфизма.
Для своей схемы уточнения цвета для клеточных комплексов команда выбрала Cellular WL (CWL), который обобщает тесты Simplicial WL и WL. Процедура для отдельной ячейки включает три шага: 1) Учитывая регулярный комплекс ячеек, все ячейки инициализируются одним и тем же цветом; 2) Учитывая цвет ячейки на каждой итерации, цвет ячейки на следующей итерации вычисляется путем инъективного сопоставления множественных наборов цветов, принадлежащих соседним ячейкам, с использованием фиксированной функции HASH; 3) Алгоритм останавливается при достижении устойчивой окраски. Два клеточных комплекса считаются неизоморфными, если их цветовые гистограммы различаются - в противном случае тест не дает результатов. Исследователи также показывают, что для широкого диапазона преобразований CWL, примененный к клеточным комплексам, более эффективен, чем WL, примененный к исходным графам.
Команда далее описывает CWN с прикладным акцентом на молекулярных графах. Ячейки в предложенных CWN получают два типа сообщений: первый определяет сообщения от атомов к связям и от связей к кольцу; а второй определяет сообщения между атомами, соединенными связью, и сообщения между связями, которые являются частью одного и того же кольца. Команда сначала показывает, что CWN не более мощны, чем CWL; и что за счет уменьшения общего количества уровней, необходимых при наличии взаимодействия узлов на большом расстоянии, CWN могут решить проблемы взаимодействия на большом расстоянии, которые мешают традиционным GNN. Более того, CWN можно рассматривать как (нелинейное) обобщение операторов линейной диффузии на клеточных комплексах, вычислительная сложность которых линейна по размеру входного комплекса, который намного меньше, чем GNN.
Команда использует модель сети изоморфизма ячеек (CIN), которая объединяет слои CWN с локальными агрегаторами, как в GIN. Они протестировали предложенную модель на восьми тестах TUDataset с малыми и средними размерами из биологии (БЕЛКИ), химии (то есть молекул - MUTAG, PTC, NCI1 и NCI109) и социальных сетей (IMDB-B, IMDB-M, RDT-B). Они сравнили CIN с базовыми методами RWK, GK (с k = 3), PK, ядром WL, DCNN, DGCNN, IGN, GIN, PPGN, Natural GN, GSN и SIN.
CIN достиг наилучших результатов средней точности по четырем из восьми наборов данных и занял второе место среди остальных. Эксперименты показывают, что предлагаемый подход CW Networks позволяет получать самые современные результаты на популярных крупномасштабных наборах данных молекулярных графов и других связанных задачах, подтверждая его высокую производительность передачи сообщений на клеточных комплексах.
Статья Weisfeiler and Lehman Go Cellular: CW Networks находится на arXiv.
Автор: Геката Хе | Редактор: Майкл Саразен, Чейн Чжан
Мы знаем, что вы не хотите пропустить какие-либо новости или научные открытия. Подпишитесь на нашу популярную рассылку Synced Global AI Weekly, чтобы получать еженедельные обновления AI.
