Motif-based filtrations for persistent homology: A framework for graph isomorphism and property prediction

Título: Filtrações Baseadas em Motivos para Homologia Persistente: Um Framework para Isomorfismo de Grafos e Predição de Propriedades

1. O Problema

O problema central abordado é a distinção entre grafos isomorfos e não isomorfos, uma tarefa fundamental em áreas como química molecular (verificação de estruturas) e análise de redes sociais. Embora a determinação exata do isomorfismo seja um problema computacionalmente caro (na classe NP, sem algoritmo polinomial conhecido para o caso geral), métodos existentes, como o teste de Weisfeiler-Leman (WL), falham em distinguir certos grafos altamente regulares ou simétricos (ex: grafos regulares fortes, grafos cúbicos). Além disso, há uma necessidade de métodos que não apenas distinguem grafos, mas também capturem informações estruturais ricas para tarefas de aprendizado de máquina, como a predição de propriedades de grafos e a análise de sensibilidade a perturbações.

2. Metodologia

Os autores propõem um framework que utiliza a Homologia Persistente (uma ferramenta de Análise de Dados Topológicos - TDA) aplicada a grafos, focando especificamente na escolha da filtração (a maneira como os dados são transformados em uma sequência de complexos simpliciais).

• Filtrações Baseadas em Motivos (Ciclos): A inovação principal é o uso de esquemas de ponderação de arestas baseados na densidade de ciclos sem cordas (chordless cycles):
  • Triângulos ($eT$)
  • Quadrados sem cordas ($eS$)
  • Pentágonos sem cordas ($eP$)
  • Soma das densidades desses ciclos ($e\Sigma$)
  • Essas densidades são calculadas para cada aresta e usadas como valores de filtração.
• Pipeline de Análise:
  1. Ponderação: As arestas (e nós, por extensão) recebem pesos baseados nas densidades de motivos.
  2. Expansão Simplicial: O grafo é expandido em um complexo simplicial (completando cliques), onde os simplexos são ponderados pelo valor máximo de suas faces.
  3. Homologia Persistente: Calcula-se o diagrama de persistência, que rastreia o surgimento (nascimento) e desaparecimento (morte) de características topológicas (componentes conectados e ciclos) à medida que o parâmetro de filtração aumenta.
  4. Comparação: A distância de gargalo ($d_B$) entre os diagramas de persistência de dois grafos é calculada. Se a distância for zero (ou abaixo de um limiar de precisão), os grafos são considerados isomorfos.
• Comparativos: O método é comparado com outras filtrações existentes, incluindo baseadas em grau ($nD$), curvatura (Ollivier-Ricci $eO$, Forman-Ricci $eF$), distância (Vietoris-Rips $mV$), centralidade ($eB$) e métodos baseados em graphlets ($nG$).

3. Contribuições Principais

• Novo Framework de Filtração: Introdução e validação sistemática de filtrações baseadas na densidade de ciclos sem cordas (triângulos, quadrados e pentágonos) para homologia persistente.
• Superioridade em Grafos Difíceis: Demonstração de que essas filtrações superam métodos tradicionais (baseados em grau, curvatura e distância) na distinção de grafos não isomorfos, especialmente em famílias desafiadoras como grafos regulares fortes e grafos cúbicos, onde métodos clássicos falham.
• Eficiência Computacional: O método oferece um equilíbrio favorável entre expressividade e custo computacional, sendo mais eficiente que métodos baseados em graphlets (que exigem contagem de órbitas complexas) e mais expressivo que métodos baseados apenas em grau.
• Aplicabilidade em Aprendizado de Máquina: Validação do método em tarefas de predição de propriedades estruturais (como diâmetro, raio, coeficiente de agrupamento) em dados reais (conjunto ogbg-molhiv), mostrando que as características topológicas capturadas são altamente informativas.
• Análise de Sensibilidade: Demonstração de que as filtrações baseadas em ciclos são altamente sensíveis a pequenas perturbações estruturais (remoção ou reencaminhamento de arestas), atuando como detectores precoces de mudanças topológicas.

4. Resultados

• Isomorfismo de Grafos:
  • Nas bases de dados de grafos regulares fortes e cúbicos, as filtrações $eS$, $eP$e$e\Sigma$ alcançaram taxas de sucesso perfeitas ou quase perfeitas (100%) em distinguir pares não isomorfos, superando significativamente a filtração baseada em curvatura de Ollivier-Ricci e a distância de egonet.
  • No conjunto de dados de benchmark BREC (que inclui grafos difíceis como CFI e regulares), a filtração $e\Sigma$ (soma das densidades) consistentemente obteve o melhor desempenho, superando o teste 3-WL (Weisfeiler-Leman) e métodos de estado da arte como a distância de egonet, especialmente em níveis de expansão de clique mais baixos ($k=1$).
• Predição de Propriedades:
  • Em tarefas de regressão para prever propriedades de grafos moleculares, as filtrações baseadas em ciclos ($eS, eT, eP, e\Sigma$) obtiveram os melhores rankings (menor erro médio absoluto) na maioria das propriedades, superando métodos baseados em grau e centralidade.
  • Isso indica que a informação sobre a distribuição de ciclos em múltiplas escalas é crucial para capturar a estrutura intrínseca do grafo.
• Sensibilidade:
  • As filtrações $e\Sigma$ e o coeficiente de agrupamento ($nC$) mostraram a maior sensibilidade a perturbações (remoção e reencaminhamento de arestas), detectando mudanças topológicas mais cedo do que métodos baseados em grau ($nD$), que tendem a ser mais estáveis e menos discriminativos para pequenas alterações.

5. Significado e Conclusão

O trabalho estabelece que a escolha da filtração é o fator determinante para a eficácia da homologia persistente em análise de grafos. As filtrações baseadas em densidade de ciclos sem cordas emergem como uma abordagem superior, pois:

1. Capturam informações de motivos de ordem superior (mesoescala) que conectam descritores locais (grau) e globais (espectro).
2. São computacionalmente escaláveis para redes esparsas do mundo real.
3. Oferecem uma expressividade teórica e prática que supera ou iguala os melhores métodos atuais (SOTA) para isomorfismo e aprendizado de grafos, com menor custo computacional.

O estudo sugere que essas filtrações são uma ferramenta robusta e interpretável para comparação de grafos, com aplicações promissoras em neurociência, química e ciência de redes, preenchendo a lacuna entre a análise topológica de dados e a ciência de redes.