Graph Reduction in Multirelational Networks: A Spreading-Oriented Reduction Benchmark

Resumo Técnico: Redução de Grafos em Redes Multirelacionais (SORB)

Definição do Problema
Redes do mundo real são frequentemente incompletas, ruidosas e evoluem dinamicamente, tornando a análise direta computacionalmente exigente. Embora a Maximização de Influência (IM) — a tarefa de identificar nós semente para maximizar a propagação de informação — seja amplamente estudada, o impacto da redução de grafos (esparsidade e coalescência/coarsening) como uma etapa de pré-processamento na precisão da IM permanece pouco explorado. Os benchmarks existentes tipicamente focam em grafos de relação única ou classificação de nós, falhando em abordar como as estratégias de redução afetam os processos de propagação em sistemas multirelacionais complexos. Além disso, a interação entre a redução de grafos e as propriedades estruturais específicas de redes multicamadas não foi amplamente examinada.

Metodologia: O Benchmark de Redução Orientada à Propagação (SORB)
Os autores introduzem o SORB, um framework de código aberto e padronizado, projetado para avaliar sistematicamente modelos de IM através de diversos cenários de tarefas, integrando a redução de grafos diretamente no pipeline de avaliação.

• Arquitetura do Pipeline: O fluxo de trabalho consiste em três estágios:

  1. Módulo de Redução: Gera versões reduzidas dos grafos de entrada usando uma grade de taxas de redução ($r \in \{0.01, \dots, 0.9\}$) e métodos.
  2. Módulo de Predição: Executa modelos de seleção de sementes tanto nos grafos originais quanto nos reduzidos.
  3. Difusão e Avaliação: Executa simulações do Modelo de Cascata Independente Multicamadas (MICM) nos grafos originais utilizando os conjuntos de sementes previstos a partir dos grafos reduzidos. Isso garante que as métricas de desempenho reflitam o verdadeiro potencial de propagação nos dados completos, isolando o efeito da redução na qualidade da predição.

• Datasets: O benchmark utiliza sete redes do mundo real, incluindo grafos homogêneos (WikiCS, Amazon-CS) e redes multicamadas (Freebase, IMDB, FinDKG, arxiv, timik).

• Estratégia de Achatamento (Flattening): Como a maioria dos algoritmos de redução opera em grafos homogêneos, as redes multicamadas são transformadas em multigrafos de camada única via um processo de "achatamento". Isso agrega as relações entre camadas em um único conjunto de arestas, preservando a agregação de atores, mas introduzindo potencial duplicação de arestas. Os autores tratam isso como um compromisso pragmático para testar algoritmos existentes, reconhecendo-o como uma operação estrutural com custos inerentes.

• Métodos de Redução: O estudo avalia cinco técnicas de esparsidade (Random, LocalDegree, Jaccard similarity, TSpanner, ForestFire) e duas técnicas de coalescência (VariationNeighborhoods, AffinityGs).

• Modelos de IM: Seis modelos de seleção de sementes são testados, variando de heurísticas de baixa complexidade (Degree Centrality, Degree Discount, Neighbourhood Size) a modelos de aprendizagem de alta complexidade (ts-net) e extensões multicamadas (v-rnk-m).

• Métricas de Avaliação:

  • Gain@k: Mede a qualidade dos conjuntos de sementes selecionados de tamanho $k$ (nó único ou porcentagem de atores).
  • $AUC_{cutoff}$: Mede a concordância entre o ranking de influência real e o ranking previsto dentro dos 80% superiores de atores.

Principais Contribuições e Descobertas
O estudo aborda quatro questões de pesquisa relativas ao impacto da redução no desempenho da IM, o papel das taxas de redução, a consistência entre redes e o uso de recursos computacionais.

1. Impacto na Qualidade do Conjunto de Sementes (Gain@k):

   • Esparsidade: Em redes de camada única (homogêneas), a esparsidade preserva a qualidade do conjunto de sementes em todos os tamanhos examinados. O desempenho médio permanece nos níveis de baseline, e a variância frequentemente diminui.
   • Coalescência (Coarsening): Na subseção de redes onde a coalescência foi computacionalmente viável, ela resultou em apenas um declínio marginal no Gain@k, acompanhado por uma melhor estabilidade dos resultados (menor variância).
   • Contexto Multicamadas: Redes multicamadas achatadas exibem uma degradação sistemática de ranking, independentemente da estratégia de redução, sugerindo que os métodos atuais de redução têm dificuldade com a complexidade estrutural introduzida pelo achatamento.

2. Papel da Taxa de Redução ($r$) vs. Estratégia:

   • Não há uma relação monotônica estatisticamente significativa entre a taxa de redução nominal $r$ e a degradação do desempenho downstream ($AUC_{cutoff}$).
   • A degradação é impulsionada principalmente pela escolha da estratégia de redução em vez da porcentagem de arestas removidas. Por exemplo, o ForestFire comporta-se como uma função degrau (mantendo a estrutura até um limiar), enquanto o TSpanner exibe uma relação invertida com $r$ em alguns contextos.
   • A sensibilidade estrutural é alta; mesmo a remoção aleatória de arestas induz mudanças de ranking estatisticamente significativas.

3. Consistência entre Redes:

   • Redes homogêneas mostram um comportamento consistente e estável sob redução.
   • Redes heterogêneas (multicamadas) apresentam um desafio distinto. A transformação de achatamento introduz um overhead (duplicação de arestas) que pode neutralizar a economia de memória em taxas de redução baixas ($r \le 0.5$), particularmente para modelos baseados em aprendizagem como o ts-net.

4. Recursos Computacionais:

   • A esparsidade produz reduções mensuráveis no tempo de inferência e no consumo de memória, notadamente para modelos mais pesados (v-rnk-m e ts-net).
   • No entanto, para grafos heterogêneos, a etapa de achatamento pode aumentar os requisitos de memória para o ts-net em taxas de redução baixas, porque o grafo de camada única resultante contém estritamente mais arestas do que qualquer camada individual.

Significância e Alegações
Os autores alegam que o SORB desloca o foco de testar algoritmos de IM isoladamente para quantificar como a redução de grafos altera o desempenho preditivo sob condições realistas. A principal significância do trabalho reside em demonstrar que:

• A redução de grafos é uma etapa de pré-processamento viável para IM, particularmente para esparsidade em redes homogêneas, oferecendo economia de recursos com perda mínima de desempenho.
• A escolha da estratégia de redução é mais crítica do que a própria taxa de redução.
• Os métodos atuais de redução não são bem adequados para redes multicamadas quando aplicados via um pipeline de "achatar-e-reduzir", destacando uma lacuna na literatura para algoritmos dedicados de redução multicamadas.

O artigo conclui que, embora a esparsidade ofereça potencial para análise eficiente, a falta de abordagens dedicadas para grafos heterogêneos continua sendo um desafio. Os autores posicionam o SORB como uma fundação para trabalhos futuros que incorporem condensação de grafos e métodos especificamente projetados para estruturas de redes heterogêneas.