Краткое содержание

arXiv:2511.12838v1 Тип: новая статья Аннотация: Графовые нейронные сети высшего порядка (HOGNN), основанные на 2-FWL тесте, достигают превосходной выразительности за счет моделирования взаимодействий между 2 и 3 узлами, но при вычислительной сложности $\mathcal{O}(n^3)$. Однако это вычислительное бремя обычно смягчается существующими методами оптимизации ценой снижения выразительности. Мы предлагаем **Co-Sparsify**, фреймворк разрежения с учетом связности, который устраняет *доказуемо избыточные* вычисления, сохраняя при этом полную выразительную мощность 2-FWL. Наше ключевое наблюдение заключается в том, что трёхузловые взаимодействия экспрессивно необходимы только внутри *двусвязных компонент* — максимальных подграфов, где каждая пара узлов лежит на цикле. За пределами этих компонент структурные отношения могут быть полностью описаны посредством передачи сообщений между 2 узлами или глобального считывания (readout), что делает моделирование высшего порядка избыточным. Co-Sparsify ограничивает передачу сообщений между 2 узлами связными компонентами, а трёхузловые взаимодействия — двусвязными компонентами, удаляя