Directed Graph Topology Inference via Graph Filter Identification

Resumo Técnico: Inferência de Topologia de Grafos Direcionados via Identificação de Filtros de Grafo

Definição do Problema
O artigo aborda o desafio de inferir a topologia de um grafo direcionado (digrafo) a partir de medições nodais geradas por dinâmicas de difusão linear. Diferente de trabalhos anteriores focados em grafos não direcionados com excitações de sinal branco, este problema considera um cenário geral onde:

1. O grafo subjacente é um grafo direcionado com um operador de deslocamento de grafo (GSO) não simétrico, $S$.
2. Os sinais observados, $y$, são gerados por um filtro de convolução de grafo (um polinômio de $S$) atuando sobre sinais de entrada, $x$.
3. Os sinais de entrada não são necessariamente brancos; eles possuem correlações arbitrárias descritas por matrizes de covariância conhecidas $C_{x,m}$.
4. Os coeficientes do filtro e a estrutura do grafo são desconhecidos.

A dificuldade central surge porque, para grafos direcionados, o GSO e a matriz de covariância de observação não são simultaneamente diagonalizáveis, tornando inaplicáveis as abordagens espectrais padrão para grafos não direcionados. O objetivo é recuperar o GSO mais esparso e válido que explique os dados observados, dada a informação estatística prévia dos inputs.

Metodologia
Os autores propõem uma estrutura de inferência de duas etapas, seguida por uma abordagem de otimização conjunta para melhorar a complexidade de amostragem.

1. Etapa 1: Identificação de Filtro de Difusão Assimétrico

   • Formulação: O problema é modelado como um sistema de equações matriciais quadráticas: $C_{y,m} = H C_{x,m} H^\top$, onde $H$ é o filtro desconhecido e $C_{y,m}$ é a covariância de saída estimada.
   • Identificabilidade: Os autores estabelecem que o filtro $H$ é identificável (até a ambiguidade de sinal) se as covariâncias de entrada exibirem diversidade espectral suficiente. Especificamente, o Teorema 1 prova que, com $M=4$ processos, a unicidade é garantida se as bases de autovetores de entrada forem suficientemente distintas e os autovalores satisfizerem condições específicas de Kruskal-rank.
   • Algoritmo: Para resolver este sistema não convexo, o problema é reestruturado como uma minimização quadrática suave sujeita a restrições da variedade de Stiefel (restrições de ortogonalidade em matrizes de rotação). Um algoritmo de Minimização Alternada Inexata (IAM) é desenvolvido, utilizando o gradiente de Riemann para as variáveis de restrição de variedade e atualizações de forma fechada para o filtro $H$.

2. Etapa 2: Inferência de Topologia de Digrafo

   • Formulação: Dado o filtro estimado $\hat{H}$, o objetivo é encontrar um GSO esparso $S$ tal que $HS = SH$ (comutatividade), garantindo que $H$ seja um polinômio de $S$.
   • Algoritmo: Os autores formulam isso como um problema de minimização de norma $\ell_1$ convexo com uma restrição de comutatividade relaxada. Um algoritmo de Gradiente Proximal (PG) é empregado, que lida eficientemente com a restrição de esparsidade e as restrições estruturais (ex: pesos não negativos, ausência de auto-loops) via um operador proximal customizado.

3. Identificação Conjunta (Malha Fechada)

   • Para melhorar o desempenho, os autores propõem uma formulação conjunta que alterna entre a identificação do filtro e a inferência da topologia. Esta abordagem de "malha fechada" utiliza a estimativa atual de $S$ para regularizar a estimativa do filtro e vice-versa.
   • Convergência: Um algoritmo comprovadamente convergente (Algoritmo 3) é apresentado, que alterna entre passos de Gradiente Proximal para $S$, passos de gradiente de Riemann para as variáveis da variedade e passos de gradiente Euclidiano para $H$. A análise teórica confirma a convergência para um ponto crítico sob suposições moderadas.

Principais Contribuições

• Generalização para Grafos Direcionados: O trabalho estende a identificação de filtros de grafo de operadores simétricos (não direcionados) para assimétricos (direcionados), abordando a não-diagonalizabilidade do GSO e da covariância de saída.
• Teoria de Identificabilidade: O artigo fornece condições rigorosas (Teorema 1) sob as quais um filtro de difusão assimétrico é unicamente identificável a partir de estatísticas de segunda ordem de múltiplos processos de entrada-saída, destacando a necessidade de diversidade espectral nos inputs.
• Algoritmos Inovadores:
  • Um algoritmo IAM para identificação de filtro na variedade de Stiefel.
  • Um método de Gradiente Proximal para recuperar topologias direcionadas esparsas.
  • Um algoritmo conjunto de malha fechada que reforça mutuamente a estimativa de filtro e topologia.
• Garantias de Convergência: O artigo fornece uma análise de convergência para o problema não convexo conjunto envolvendo esparsidade $\ell_1$, restrições de variedade e acoplamento de comutatividade, utilizando a propriedade Kurdyka–Łojasiewicz (KL).

Resultados Experimentais
Os métodos propostos foram avaliados em dados sintéticos e estudos de caso do mundo real:

• Dados Sintéticos: Experimentos em grafos Erdős–Rényi, Barabási–Albert e Stochastic Block Model demonstram que a abordagem conjunta (malha fechada) supera significativamente a abordagem de duas etapas (malha aberta), particularmente quando o número de processos de entrada ($M$) ou amostras ($P$) é limitado. O método conjunto alcança uma recuperação de suporte quase perfeita com menos amostras do que o método de malha aberta.
• Dados do Mundo Real (Mobilidade Urbana): Aplicado a dados de corridas da Uber em Nova York, o algoritmo inferiu um grafo de mobilidade direcionado. Ao contrário de modelos não direcionados, o método proposto capturou fluxos de tráfego assimétricos, identificando corretamente os fluxos predominantes de saída de Manhattan para os distritos residenciais e aeroportos, consistentes com os padrões de deslocamento vespertino.
• Dados do Mundo Real (Otimização de Portfólio): Em uma aplicação financeira utilizando dados de ações, os grafos inferidos pelo método proposto levaram a portfólios com retornos significativamente maiores em comparação com as linhas de base (GFI, TITD) e alocação uniforme, sob estratégias de ponderação de centralidade de grau inverso e de autovetor inverso.

Significância e Alegações
O artigo alega que sua principal significância reside em fornecer uma estrutura unificada para a inferência de topologia de redes direcionadas que não depende da restritiva suposição de estacionaridade de grafo (que implica simetria). Ao alavancar a relação estrutural entre filtros de grafo e operadores de deslocamento, o método recupera as relações causais ou direcionais fundamentais em uma rede.

Os autores observam que, embora a abordagem seja eficaz, ela traz compromissos: requer múltiplos processos de entrada para garantir a identificabilidade e envolve complexidade computacional cúbica ($O(N^3)$) por iteração. O artigo posiciona-se como um avanço metodológico para aplicações onde a direcionalidade é crítica, como descoberta causal, redes de transporte e modelagem de dependência financeira, oferecendo uma alternativa mais precisa às ferramentas de aprendizado de grafos simétricos.