Resumo Técnico: Filtrações de Ciclos Sem Cordas para Detecção de Dimensionalidade em Redes Complexas via Análise Topológica de Dados

1. Declaração do Problema

Redes complexas em diversos domínios (biológicos, sociais, tecnológicos) frequentemente exibem padrões estruturais consistentes com uma geometria hiperbólica latente subjacente. Determinar a dimensionalidade efetiva ($D$) deste espaço latente é crucial para compreender a complexidade estrutural, a organização comunitária, a navegação na rede e a dinâmica do sistema. Embora existam várias definições de dimensionalidade de rede (por exemplo, fractal, espectral, métrica), e abordagens baseadas em modelos (como o modelo $S^D/H^{D+1}$) tenham estimado com sucesso a dimensionalidade projetando frequências de ciclos em espaços de configuração, esses métodos frequentemente exigem a geração de grandes ensembles de redes substitutas sintéticas para cada nova rede alvo. Esse processo é computacionalmente intensivo e carece de um framework unificado e orientado por dados que integre Análise Topológica de Dados (TDA) com aprendizado de máquina para contornar a geração de substitutas.

Além disso, as aplicações padrão de TDA na ciência de redes têm sido limitadas. A homologia persistente ordinária é inadequada para grafos porque ciclos (características unidimensionais) têm persistência infinita na ausência de símplices de dimensão superior para preenchê-los. Adicionalmente, esquemas de filtração existentes (por exemplo, baseados em grau de nó ou curvatura de Ricci) podem não capturar as assinaturas geométricas específicas necessárias para a estimação de dimensionalidade.

2. Metodologia

Os autores propõem uma abordagem dupla combinando topologia algébrica e aprendizado de máquina para estimar a dimensionalidade da rede.

A. Filtrações de Ciclos Sem Cordas e Persistência Estendida

A inovação topológica central é um esquema de ponderação baseado em ciclos sem cordas (ciclos sem cordas internas).

1. Ponderação: Para uma rede dada, três grafos ponderados em arestas são construídos. O peso de uma aresta é definido pela densidade local de ciclos sem cordas de comprimentos específicos: triângulos ($C_t$), quadrados ($C_s$) e pentágonos ($C_p$).
2. Persistência Estendida: Como os ciclos em grafos não morrem em filtrações padrão, os autores calculam persistência estendida. Isso envolve uma técnica para transformar o grafo ponderado em arestas em um grafo ponderado em nós topologicamente equivalente via "subdivisão por divisão de grau". Isso permite o uso de software padrão de TDA (Gudhi) para calcular a persistência estendida de ciclos, definida como a diferença entre o valor de nascimento na filtração subnível e o valor de nascimento na filtração supernível.
3. Descritores: A Persistência Estendida Total (a soma dos valores de persistência para todos os ciclos independentes) é calculada para cada uma das três filtrações, resultando em um vetor de características $(TP_t, TP_s, TP_p)$.

B. Abordagens de Estimação de Dimensionalidade

O artigo apresenta dois métodos para estimar $D$:

1. Vizinhos Mais Próximos (kNN) Baseado em Substitutas:

   • Para uma rede alvo, um ensemble de substitutas sintéticas é gerado usando o procedimento $D$-GR (Randomização Geométrica). Este método reconecta a rede para maximizar a verossimilhança do modelo $S^D/H^{D+1}$ enquanto preserva a sequência exata de graus da rede alvo.
   • A rede alvo e suas substitutas são mapeadas em um espaço de configuração definido por $(TP_t, TP_s, TP_p)$.
   • Um classificador kNN identifica a dimensão $D$ das substitutas mais próximas da rede alvo.

2. Rede Neural (DimNN):

   • Para evitar a geração de substitutas para cada nova rede, os autores treinam um Perceptron Multicamadas Residual (DimNN).
   • Dados de Treinamento: Um banco de dados de 792.000 redes sintéticas (SynNet) geradas a partir do modelo $S^D/H^{D+1}$ com dimensões conhecidas ($D \in [1, 10]$) e parâmetros variados (heterogeneidade de grau $\gamma$, temperatura inversa $\beta$).
   • Características de Entrada: O modelo utiliza um vetor de características de 12 dimensões incluindo:
     • Estatísticas de grafo: Número de nós ($N$), grau médio ($\langle k \rangle$), segundo momento normalizado da distribuição de graus ($\langle k^2 \rangle / \langle k \rangle^2$), graus mínimos/máximos e grau médio dos vizinhos ($\langle k_{nn} \rangle$).
     • Densidades de ciclos: Densidades médias de triângulos, quadrados e pentágonos sem cordas ($C_t, C_s, C_p$).
     • Descritores topológicos: Persistências estendidas totais ($TP_t, TP_s, TP_p$).
   • Arquitetura: Um MLP profundo com 21 camadas ocultas, ativações ReLU, dropout (50%) e conexões residuais, treinado com AdamW.
   • Validação: Um modelo de regressão secundário (usando perda MSE) foi treinado para verificar a robustez, mostrando alta concordância com o modelo de classificação.

3. Contribuições Principais

• Esquema de Filtração Novel: Introdução de um esquema de filtração baseado em densidade de ciclos sem cordas para grafos, especificamente adaptado para capturar propriedades geométricas relevantes para a dimensionalidade.
• Persistência Estendida para Grafos: Adaptação da persistência estendida para grafos ponderados em arestas via subdivisão por divisão de grau, permitindo o cálculo de tempos de vida finitos de ciclos em contextos de rede onde a persistência padrão falha.
• Estimação de Dimensionalidade Orientada por Dados: Desenvolvimento do DimNN, uma rede neural treinada em um banco de dados sintético massivo que pode estimar a dimensionalidade da rede diretamente a partir de uma única rede do mundo real sem gerar substitutas.
• Integração de TDA e ML: Demonstração de que características de TDA (persistência total) melhoram significativamente a precisão de modelos de aprendizado de máquina para estimação de dimensionalidade, superando modelos que usam apenas densidades de ciclos ou estatísticas de grau.

4. Resultados

• Correlação: Uma correlação negativa foi observada entre a dimensionalidade da rede e os valores de persistência estendida total, particularmente para quadrados e pentágonos (coeficientes de Pearson $\rho_s \approx -0,31$, $\rho_p \approx -0,24$).
• Validação Sintética:
  • O método kNN baseado em substitutas alcançou precisão razoável em alvos sintéticos, com matrizes de confusão mostrando alta fidelidade para a maioria das dimensões, embora alguma confusão tenha ocorrido entre dimensões adjacentes em redes altamente heterogêneas.
  • O DimNN alcançou uma precisão de classificação de 83,00% no conjunto de validação usando o vetor de características completo.
  • Estudos de ablação confirmaram que combinar persistência total com densidades médias de ciclos e características relacionadas a graus maximiza o desempenho. A remoção de características de TDA resultou em uma queda significativa na precisão.
• Aplicação no Mundo Real:
  • O método foi aplicado a 10 redes do mundo real bem conhecidas (por exemplo, Conectoma Humano, colaboração Jazz, redes de e-mail). As dimensões inferidas foram consistentes com a literatura anterior (por exemplo, conectomas cerebrais próximos a $D=3$, redes sociais exigindo dimensões ligeiramente maiores).
  • Quando aplicado a um conjunto de dados maior de 53 redes reais, o modelo previu dimensões variando de 1 (Software, grafos Web) a 10 (algumas redes sociais).
  • Robustez: Dois modelos treinados independentemente (classificação e regressão) mostraram alta concordância (até 88,86% em dados sintéticos), sugerindo que os modelos capturam relações subjacentes em vez de overfitting.
  • Validação: Redes substitutas geradas usando as dimensões previstas e embeddings D-Mercator reproduziram com sucesso propriedades topológicas chave das redes originais, incluindo distribuição de graus, espectro de agrupamento e limiares de percolação.

5. Significado e Alegações

O artigo afirma que este trabalho preenche a lacuna entre a teoria de redes complexas e a Análise Topológica de Dados, fornecendo um método robusto e eficaz para revelar a geometria oculta de redes complexas.

• Eficiência: A abordagem de rede neural oferece uma vantagem computacional significativa sobre os métodos anteriores baseados em substitutas, pois não requer retreinamento ou geração de substitutas para novas redes.
• Expressividade: O estudo demonstra que filtrações conscientes de ciclos e descritores de persistência estendida são características altamente expressivas para detecção de dimensionalidade, complementando descritores geométricos tradicionais.
• Generalização: O modelo transfere com sucesso dados de treinamento sintéticos para redes do mundo real, sugerindo que as estruturas geométricas latentes de redes reais são bem representadas pelo modelo $S^D/H^{D+1}$ dentro dos regimes de parâmetros testados.

Os autores observam modestamente que o framework visa principalmente redes geométricas ($\beta > D$) e que estender a abordagem para regimes fracamente geométricos ou otimizar a arquitetura neural para deslocamentos de distribuição mais amplos permanece uma direção para trabalhos futuros. O artigo posiciona-se como uma prova de conceito da utilidade de filtrações baseadas em ciclos na TDA e da viabilidade da estimação de dimensionalidade assistida por aprendizado profundo.