SpectralMPNN: Spectral Graph Architectures For Neural Algorithmic Reasoning
Autores
|
7584 |
2315,250,3274
|
|
|
7585 |
2315,250,3274
|
|
|
7586 |
2315,250,3274
|
Informações:
Publicações do PESC
Neural algorithmic reasoning é um subcampo emergente do aprendizado de representações que se concentra no treinamento de modelos neurais para imitar de forma eficaz as execuções de algoritmos clássicos da ciência da computação. Essa área tem demonstrado grande valor tanto em aplicações práticas—onde modelos pré-treinados em dados algorítmicos apresentam desempenho aprimorado—quanto em pesquisas teóricas, ao revelar aspectos arquiteturais das redes neurais que favorecem o computação discreta.A maioria das abordagens existentes restringem as arquiteturas aplicadas ao tipo de Redes Neurais Message-Passing em grafos. Essa escolha decorre principalmente da versatilidade das estruturas de grafos, capazes de aproximar uma ampla variedade de estruturas de dados, e de descobertas teóricas recentes que destacam a relação entre a passagem de mensagens e a programação dinâmica. No entanto, existe uma limitação fundamental associada a este paradigma: seu viés inerente para representações suaves no grafo. Esse viés está diretamente relacionado ao fenômeno de over-smoothing, no qual múltiplas rodadas de message-passing fazem com que todas as representações de nós convirjam para um mesmo valor. Essa limitação dificulta a aplicação das Message-Passing GNNs a grafos heterofílicos, onde nós conectados frequentemente apresentam características distintas, que é o cenário presente em grande parte das tarefas algorítmicas. Por outro lado, Spectral GNNs representam uma classe de redes neurais em grafos que exploram a estrutura do grafo aprendendo filtros diretamente no domínio da Transformada de Fourier no grafo. Isso as permite atuar como filtros adaptativos, possibilitando a propagação de sinais de forma flexível com base na frequência. Nesta dissertação, propomos o uso de Spectral GNNs para o Neural Algorithmic Reasoning e introduzimos a SpectralMPNN—uma Spectral GNN que combina filtragem adaptativa com uma camada de message-passing. A SpectralMPNN foi projetada para manter os vieses indutivos benéficos de message-passing, ao mesmo tempo em que incorpora filtragem adaptativa de frequências. Nossos experimentos mostram que essa arquitetura supera os modelos existentes em diversos algoritmos do benchmark CLRS-30.
Neural algorithmic reasoning is an emerging subfield of representation learning that focuses on training neural models to effectively mimic the execution traces of classical computer science algorithms. This field has shown significant value in practical applications—where models pre-trained on algorithmic data exhibit enhanced performance—and in theoretical research by shedding light on the architectural aspects of neural networks that facilitate discrete reasoning. Most existing approaches to this problem restrict the design space to Message-Passing GNNs. This choice is primarily driven by the versatility of graph structures, which can approximate a wide range of data structures, and by recent theoretical findings highlighting the alignment between message passing and dynamic programming. However, prior studies have underscored a fundamental limitation of message passing: its inherent bias toward smooth representations across the graph. This characteristic is closely linked to the over-smoothing phenomenon, where multiple rounds of message passing cause all node representations to converge to the same value. This limitation poses challenges for applying Message-Passing GNNs to heterophilic graphs, where connected nodes often have distinct features, which is commonly the case for algorithmic tasks. Conversely, Spectral GNNs represent a class of graph neural networks that leverage the graph structure by learning effective filters directly in the Graph Fourier domain. This enables them to function as adaptive filters, allowing flexible frequency-based signal propagation. In this dissertation, we propose using Spectral GNNs for neural algorithmic reasoning and introduce SpectralMPNN—a Spectral GNN that integrates filtering with a Message-Passing layer. SpectralMPNN is designed to retain the beneficial inductive biases of message passing while incorporating adaptive frequency filtering. Our experiments show that this architecture outperforms existing models across multiple algorithms in the CLRS-30 benchmark.