Resumo Técnico: Condensação de Grafos Atribuídos a Texto via Seleção de Texto e Correspondência de Atributos

Declaração do Problema

Grafos Atribuídos a Texto (TAGs) integram a topologia do grafo com descrições textuais dos nós, permitindo tarefas subsequentes poderosas como classificação zero-shot e classificação de artigos através do treinamento conjunto de Redes Neurais de Grafos (GNNs) e Modelos de Linguagem (LMs). No entanto, esse treinamento de modalidade dupla é computacionalmente caro, exigindo memória e tempo significativos, particularmente em conjuntos de dados de larga escala.

Embora a Condensação de Conjunto de Dados ofereça uma solução ao comprimir grandes conjuntos de dados em outros menores e representativos, os métodos existentes falham em abordar os TAGs de forma eficaz:

1. Condensação de Grafo Tradicional (ex: GCond): Esses métodos normalmente comprimem apenas a modalidade de grafo, ignorando a rica informação textual. Além disso, frequentemente dependem de supervisão de rótulos, o que é incompatível com cenários de TAG onde rótulos de verdade fundamental (ground-truth) são escassos ou caros de obter.
2. Condensação Multimodal (ex: MTT-VL): Métodos baseados em Correspondência de Trajetórias de Treinamento (MTT) tentam comprimir tanto imagem quanto texto. No entanto, ao aplicados a TAGs, enfrentam dois problemas críticos:
   • Texto Ilegível: O MTT otimiza o texto no espaço de incorporação (embedding) contínuo via gradiente descendente. Isso produz vetores de incorporação ilegíveis que são incompatíveis com tokenizadores e modelos de linguagem subsequentes.
   • Treinamento Instável: Em TAGs, os modelos professores são frequentemente treinados via aprendizado contrastivo. A perda no aprendizado contrastivo depende de todo o lote (batch), levando a uma alta variância nas trajetórias de treinamento. Essa instabilidade dificulta a habilidade do modelo aluno de corresponder à trajetória do professor, resultando em uma convergência subótima.

A questão central de pesquisa é: É possível projetar um método de condensação de TAG para cenários sem rótulos que gere textos discretos e legíveis e alcance uma convergência estável?

Metodologia: TAGSAM

Os autores propõem o TAGSAM, um framework de condensação composto por dois componentes principais: Seleção de Texto de Subgrafo e Correspondência de Similaridade de Atributos.

1. Seleção de Texto de Subgrafo

Em vez de otimizar incorporações contínuas, o TAGSAM seleciona e mescla fragmentos de texto representativos do espaço discreto original para formar textos comprimidos concisos e legíveis.

• Processo:
  1. Amostragem de Subgrafo: Amostra aleatoriamente $M$ subgrafos do grafo original usando Busca em Largura (BFS).
  2. Fragmentação de Texto e Pontuação: Divide o texto dentro de cada subgrafo em fragmentos (chunks). Calcula um Score de Representatividade (RS) para cada fragmento baseado na Informação Mútua por Fragmento (CMI). O RS maximiza a cobertura de informação do subgrafo enquanto penaliza a redundância.
  3. Seleção e Mesclagem: Um algoritmo ganancioso seleciona sequencialmente os top-$k$ fragmentos com o maior RS para formar um texto comprimido $\hat{T}_i$.
• Garantia Teórica: Os autores provam que esta seleção gananciosa aproxima a solução ótima dentro de um fator de $(1 - 1/e)$.

2. Correspondência de Similaridade de Atributos (ASM)

Para comprimir a estrutura do grafo e os atributos dos nós, o TAGSAM substitui a abordagem instável de MTT pela Correspondência de Similaridade de Atributos.

• Mecanismo: Em vez de alinhar trajetórias completas de atualização de parâmetros (que sofrem de alta variância), o ASM alinha as matrizes de similaridade de atributos entre os modelos professor e aluno.
  • A matriz de similaridade $S_M$ é computada como o produto das incorporações de grafo e das incorporações de texto para todos os pares de nós.
  • A perda de correspondência minimiza a discrepância entre a matriz de similaridade do aluno e a do professor, usando um softmax por linha antes da Entropia Cruzada Binária (sBCE) para garantir gradientes mais suaves.
• Justificativa Teórica: Os autores demonstram que, no aprendizado contrastivo, a similaridade ótima entre atributos corresponde à sua Informação Mútua Pontual (PMI). Diferente das trajetórias completas, que são sensíveis a matrizes de rotação e escala arbitrárias no espaço do codificador, a matriz de similaridade é inerentemente estável e invariante a essas transformações.
• Eficiência: Ao contrário do MTT, que requer o treinamento de múltiplos modelos professores (tipicamente 15) para capturar trajetórias diversas, o ASM requer apenas um único modelo professor, reduzindo significativamente o custo computacional.

Principais Contribuições

1. Identificação do Problema: Os autores identificam que a condensação de grafos tradicional é inadequada para TAGs devido à negligência do texto e dependência de rótulos, enquanto os métodos multimodais existentes falham devido a saídas de texto ilegíveis e instabilidade de treinamento causada por trajetórias contrastivas de alta variância.
2. Framework Inovador (TAGSAM):
   • Seleção de Texto de Subgrafo: Um método para comprimir texto no espaço discreto selecionando fragmentos representativos via informação mútua, garantindo que a saída permaneça legível e compatível com tokenizadores.
   • Correspondência de Similaridade de Atributos: Uma técnica de condensação robusta que alinha matrizes de similaridade de atributos estáveis em vez de trajetórias de treinamento voláteis, melhorando a estabilidade da convergência.
3. Análise Teórica: O artigo fornece provas teóricas mostrando que a seleção de texto gananciosa aproxima a solução ótima e que a similaridade de atributos serve como uma estimativa estável de PMI, justificando a robustez da estratégia de correspondência.

Resultados Experimentais

Os autores avaliaram o TAGSAM em cinco conjuntos de dados (Cora, Photo, Computer, Arxiv, Products) variando de 2.7K a 2.4M de nós, comparando-o com seis baselines de estado da arte (Random, Herding, K-Center, GCond*, MTT-TAG, MTT-KNN).

• Acurácia de Classificação: O TAGSAM superou consistentemente todos os baselines. Em média, ele melhorou a acurácia em 4,9% sobre o melhor baseline (MTT-TAG). Notavelmente, alcançou acurácia competitiva mesmo ao condensar o conjunto de dados para apenas 1% de seu tamanho original.
• Predição de Links: O TAGSAM alcançou melhorias significativas de AUC (até 4,1% sobre o Random e 2,1% sobre o MTT-TAG), indicando uma melhor retenção de informação estrutural.
• Generalização de Arquitetura Cruzada: Modelos treinados em dados condensados pelo TAGSAM mantiveram uma acurácia mais alta quando testados com diferentes arquiteturas de codificador (ex: GCN, SAGE, Cheby) em comparação com os baselines.
• Eficiência: Embora a condensação incorra em um custo único, o TAGSAM acelera significativamente as buscas de hiperparâmetros subsequentes. Devido ao requisito de um único professor, o TAGSAM é mais escalável do que os métodos baseados em MTT para grafos grandes.
• Estudos de Ablação: Experimentos confirmaram que tanto a seleção de texto de subgrafo quanto a correspondência de similaridade de atributos são essenciais, com a combinação gerando desempenho superior sobre variantes que utilizam seleção aleatória ou correspondência de trajetória.

Significância

O artigo afirma que o TAGSAM torna o pré-treinamento eficiente em Grafos Atribuídos a Texto de larga escala viável. Ao abordar os desafios específicos da compressão de texto discreto e da instabilidade do aprendizado contrastivo, o TAGSAM permite a criação de conjuntos de dados altamente comprimidos que preservam a informação conjunta necessária para uma classificação zero-shot eficaz e outras tarefas de TAG, sem depender de supervisão de rótulos dispendiosa.