Directed Acyclic Graph Convolutional Networks

Resumo Técnico: Redes Convolucionais de Grafos Acíclicos Dirigidos (DCN)

Declaração do Problema
Os Grafos Acíclicos Dirigidos (DAGs) são fundamentais para aplicações envolvendo inferência causal, agendamento e design de arquiteturas neurais. No entanto, aprender a partir de sinais suportados em DAGs apresenta desafios únicos para Redes Neurais de Grafos (GNNs). As GNNs padrão dependem de passagem iterativa de mensagens e análise espectral baseada em operadores de deslocamento de grafo (GSOs). Em DAGs, a matriz de adjacência é estritamente triangular inferior e nilpotente, resultando em um espectro colapsado (todos os autovalores são zero). Isso torna as ferramentas padrão da teoria espectral de grafos vazias e impede a aplicação direta de GNNs convolucionais convencionais. Além disso, mecanismos de agregação genéricos em GNNs padrão falham em contabilizar explicitamente o forte viés indutivo da ordenação parcial inerente aos DAGs. Modelos específicos de DAG existentes, como D-VAE e DAGNN, frequentemente dependem de operações sequenciais computacionalmente intensivas (por exemplo, unidades recorrentes) que não escalam bem para grafos grandes.

Metodologia
Os autores propõem a Rede Convolucional de DAG (DCN), uma arquitetura inovadora fundamentada em princípios de Processamento de Sinais em Grafos (GSP) adaptados para DAGs. A metodologia central baseia-se em filtros de grafo causal derivados do framework de fechamento transitivo ponderado.

1. Operadores de Deslocamento de Grafo Causal (GSOs): Em vez de usar a matriz de adjacência $A$, a DCN utiliza um conjunto de GSOs causais $\{S_k\}_{k \in V}$. Esses operadores são definidos via a matriz de fechamento transitivo ponderado $W = (I - A)^{-1}$, que corresponde ao grafo de alcançabilidade do DAG. Um GSO causal $S_k$ agrega contribuições de sinal dos ancestrais comuns de um nó $v_i$ e de um nó de referência $v_k$.
2. Interpretação Espectral: As colunas de $W$ servem como uma base de Fourier para sinais de DAG. Os GSOs causais são idempotentes e compartilham $W$ como sua matriz de autovetores, permitindo uma representação bem definida no domínio espectral onde o filtragem corresponde ao escalonamento ponto a ponto dos coeficientes de Fourier.
3. Arquitetura DCN: A DCN implementa convoluções camada a camada usando um banco desses GSOs causais. Para um sinal de entrada $X$, a saída da camada $\ell$ é calculada como:
   $$X^{(\ell)} = \sigma \left( \sum_{k \in V} S_k X^{(\ell-1)} \Theta^{(\ell)}_k \right)$$
   onde $\Theta^{(\ell)}_k$ são coeficientes de filtro aprendíveis e $\sigma$ é uma não linearidade. Essa estrutura captura dependências de ancestrais de longo alcance de forma eficiente por meio de multiplicações de matrizes esparsas.
4. DCN Paralela (PDCN): Para abordar questões de escalabilidade onde o número de parâmetros na DCN cresce linearmente com o número de nós $N$, os autores introduzem a PDCN. Esta variante processa sinais deslocados $\{S_k X\}$ em ramos paralelos através de uma compartilhada Rede Perceptron Multicamada (MLP), e as saídas são somadas. Este design desacopla o número de parâmetros aprendíveis do tamanho do grafo, tornando-a escalável para grandes $N$.

Principais Contribuições

• Arquitetura Inovadora: O desenvolvimento da DCN, que formaliza operações convolucionais em DAGs usando filtros de grafo causal, fornecendo uma interpretação espectral anteriormente indisponível para sinais de DAG.
• Variante Escalável: A introdução da PDCN, que mantém o desempenho preditivo enquanto garante que a contagem de parâmetros permaneça constante independentemente do tamanho do DAG.
• Propriedades Teóricas:
  • Equivariância a Permutações: Os autores provam que tanto a DCN quanto a PDCN são equivariantes a permutações, garantindo robustez ao rerotulagem de nós.
  • Poder Expressivo: Estabelece-se que a PDCN satisfaz as condições do teste de Weisfeiler-Lehman (WL), capaz de distinguir entre DAGs não isomórficos.
  • Unicidade: A Proposição 2 demonstra que o conjunto de GSOs causais identifica unicamente a estrutura subjacente do DAG.
• Eficiência: A arquitetura aproveita operações de matriz esparsa e operadores de deslocamento pré-calculáveis, oferecendo vantagens computacionais significativas sobre modelos de DAG sequenciais.

Resultados Experimentais
O artigo avalia a (P)DCN em conjuntos de dados sintéticos e do mundo real contra baselines de última geração (incluindo GCN, GIN, D-VAE, DAGNN e DAG+NodeFormer).

• Tarefas Sintéticas:
  • Aprendizado de Difusão: A DCN alcança menor Erro Quadrático Médio Normalizado (NMSE) do que as baselines na previsão de sinais difundidos, demonstrando superior robustez ao ruído e a densidades de arestas variáveis.
  • Identificação de Fonte: Variantes da DCN (especificamente usando GSOs transpostos) alcançam alta precisão no rastreamento de fontes de sinal, superando modelos agnósticos a DAG e mostrando melhor escalabilidade do que modelos sequenciais como o DAGNN.
  • Escalabilidade: À medida que o tamanho do grafo aumenta (até $N=1000$), a DCN e a PDCN mantêm o desempenho e tempos de treinamento razoáveis, enquanto modelos como DAGNN e D-VAE falham em concluir (DNF) devido a restrições de memória e tempo.
• Aplicações do Mundo Real:
  • Imputação de Expressão Gênica: Em um conjunto de dados de Arabidopsis Thaliana, a DCN e a PDCN imputam com sucesso níveis de expressão gênica ausentes, alcançando NMSE comparável ao D-VAE e DAGNN, mas com ordens de magnitude menos parâmetros e tempos de treinamento mais rápidos.
  • Previsão Hidrológica: Em dados do Rio Tâmisa, a DCN supera todas as baselines na previsão de concentrações químicas em locais não observados, aproveitando efetivamente a estrutura de fluxo montante-jusante.

Significado e Alegações
O artigo posiciona a (P)DCN como um framework viável para aprendizado profundo em dados estruturados em DAG, projetado a partir de princípios fundamentais do processamento de sinais em grafos. Os autores alegam que, ao incorporar a ordenação parcial dos DAGs diretamente nos operadores convolucionais, os modelos alcançam um forte viés indutivo que melhora a precisão, a robustez e a eficiência computacional em comparação com métodos existentes. O trabalho preenche a lacuna entre modelos de inferência causal e aprendizado profundo, oferecendo uma alternativa principial aos métodos de agregação sequencial. Os autores reconhecem limitações, observando que a dependência de um grande número de GSOs na DCN completa ainda pode apresentar desafios para grafos muito grandes, sugerindo trabalhos futuros na seleção adaptativa de GSOs.