Resumo Técnico: Mem-GF (Filtragem de Grafos com Eficiência de Memória)

1. Definição do Problema

A Filtragem Colaborativa (CF) tem dependido cada vez mais de Redes Convolucionais de Grafos (GCNs) para modelar a conectividade de alta ordem entre usuários e itens. No entanto, as GCNs sofrem com problemas de escalabilidade devido à sua natureza recursiva de passagem de mensagens e aos extensos requisitos de treinamento. Como alternativa, surgiram métodos de CF baseados em Filtragem de Grafos (GF) sem necessidade de treinamento, que utilizam filtros predefinidos (ex: lineares ou polinomiais) em grafos de similaridade de itens para suavizar sinais de grafos de forma eficiente.

Apesar de suas vantagens computacionais, os métodos baseados em GF existentes enfrentam um gargalo crítico de memória. Essas abordagens normalmente dependem de um filtro de grafo universal e agnóstico ao usuário com dimensões $|I| \times |I|$ (onde $|I|$ é o número de itens). Mesmo utilizando operações de matriz esparsa ou aproximações de autovalores top-$k$, a etapa de filtragem frequentemente exige o armazenamento ou a operação sobre a matriz de similaridade de itens completa. Como demonstrado no artigo, isso leva a erros de Falta de Memória (OOM - Out-of-Memory) em conjuntos de dados de larga escala (ex: Amazon-book, ML-20M), mesmo em hardware com 48GB de VRAM e 128GB de RAM, limitando severamente a aplicabilidade prática de métodos GF de alta precisão em ambientes do mundo real com recursos restritos.

2. Metodologia: Mem-GF

Os autores propõem o Mem-GF (Filtragem de Grafos com Eficiência de Memória), um novo método de CF que elimina a necessidade de armazenar explicitamente a matriz de similaridade de itens completa. A inovação central reside em utilizar a estrutura dos subespaços de Krylov não apenas como um atalho computacional, mas como o mecanismo fundamental para aproximar filtros de grafos polinomiais em uma base por usuário.

Mecanismo Central

Em vez de aplicar um filtro global a todos os usuários, o Mem-GF constrói um subespaço de Krylov específico para o usuário para o vetor de interação de cada usuário $r_u$.

1. Construção do Subespaço de Krylov: Para um usuário $u$ com vetor de interação $r_u$, o método gera um subespaço de Krylov $\mathcal{K}_K(\tilde{P}, r_u)$ gerado por $\{r_u, \tilde{P}r_u, \tilde{P}^2r_u, \dots, \tilde{P}^{K-1}r_u\}$, onde $\tilde{P}$ é a matriz de similaridade de itens.
2. Algoritmo de Lanczos: Para evitar a formação explícita de $\tilde{P}$ (o que exigiria memória $O(|I|^2)$), o Mem-GF utiliza o algoritmo de Lanczos. Ele computa iterativamente produtos matriz-vetor usando a matriz de interação ajustada $\bar{R}$ (onde $\tilde{P} = \bar{R}^\top \bar{R}$). Isso gera:
   • Uma base de Krylov ortonormal $Q_u \in \mathbb{R}^{|I| \times K}$.
   • Uma matriz tridiagonal de baixa dimensão $T_u = Q_u^\top \tilde{P} Q_u \in \mathbb{R}^{K \times K}$.
3. Filtragem Polinomial: Um filtro de grafo polinomial $f(\tilde{P}) = \sum a_n \tilde{P}^n$ é aproximado dentro do subespaço como $f(T_u)$. Os escores de predição finais $s_u$ são computados como:
   $$s_u = \|r_u\|^2 Q_u f(T_u) e_1$$
   Esta formulação permite o cálculo de filtros polinomiais de alta ordem (ex: 5ª ordem) sem nunca armazenar a matriz densa $|I| \times |I|$.

Garantias Teóricas

O artigo fornece uma análise teórica (Teorema IV.1) afirmando que, se o grau do polinômio $N$ for menor que o tamanho do subespaço de Krylov $K$ ($N < K$), o algoritmo de Lanczos incorre em zero erro de aproximação sob aritmética exata. Isso garante que a projeção do subespaço reproduz perfeitamente a ação do filtro polinomial sobre o sinal do usuário.

Complexidade

• Complexidade de Espaço: Reduzida de $O(|I|^2)$ para $O(\text{nnz}(R) + |I|K + K^2)$, onde $\text{nnz}(R)$ é o número de interações. Como $K \ll |I|$, isso é linear em relação ao número de itens.
• Complexidade de Tempo: $O(|U| K (\text{nnz}(R) + |I|))$, que escala linearmente com o número de usuários, itens e interações.

3. Principais Contribuições

1. Identificação do Problema: Os autores demonstram empiricamente que a dependência de filtros de grafos universais e agnósticos ao usuário causa um uso de memória proibitivo nos métodos GF de última geração, tornando-os inviáveis para conjuntos de dados de larga escala.
2. Solução Principiada: O Mem-GF introduz uma abordagem de CF sem treinamento que integra subespaços de Krylov como o princípio fundamental de filtragem, permitindo a aproximação de filtros por usuário sem armazenar a matriz de similaridade de itens completa.
3. Suporte Teórico: O artigo analisa rigorosamente as condições para aproximação sem perdas (especificamente $K > N$) e prova a complexidade de espaço/tempo linear em relação ao tamanho do conjunto de dados.
4. Design de Filtro de Alta Ordem: Ao operar no espaço de Krylov reduzido, o Mem-GF facilita o uso de filtros polinomiais de alta ordem (até a 5ª ordem) para aproximar respostas de frequência complexas (ex: filtros Gaussianos), que eram anteriormente inviáveis devido às restrições de memória.

4. Resultados Experimentais

Experimentos foram conduzidos em três conjuntos de dados de referência: Yelp, Amazon-book e MovieLens-20M (ML-20M). O Mem-GF foi comparado contra 21 competidores, incluindo métodos baseados em MF, GCN, autoencoders e outros métodos baseados em GF.

• Eficiência de Memória: O Mem-GF alcançou até 5,74$\times$ menor uso de memória em comparação com os melhores competidores baseados em GF. Notavelmente, enquanto outros métodos (ex: EASE, GF-CF, PGSP) falharam com erros de OOM nos conjuntos de dados Amazon-book e ML-20M, o Mem-GF operou com sucesso dentro de aproximadamente 5–8 GB de VRAM.
• Aceleração de Tempo de Execução (Runtime):
  • Pré-processamento: O Mem-GF demonstrou uma aceleração de 4,38$\times$ no tempo de pré-processamento em comparação com o segundo melhor método GF.
  • Inferência: Alcançou até 26,2$\times$ de aceleração no tempo de inferência em comparação com GF-CF e Turbo-CF, com tempos de inferência tão baixos quanto 0,0044 segundos no Yelp.
• Acurácia: Apesar de ser projetado primariamente para eficiência, o Mem-GF alcançou consistentemente a acurácia de recomendação de estado da arte (medida por Recall@20 e NDCG@20) em todos os conjuntos de dados, superando tanto modelos baseados em treinamento como GCNs (ex: LightGCN, NGCF) quanto outros métodos GF sem treinamento.
• Escalabilidade: O método exibiu um escalonamento quase linear tanto em memória quanto em tempo de execução conforme o número de usuários, itens e interações aumentava, validando a análise de complexidade teórica.

5. Significância e Alegações

O artigo afirma que o Mem-GF estabelece uma solução praticável e teoricamente fundamentada para a filtragem colaborativa eficiente. Sua significância reside em:

• Quebrar o Gargalo de Memória: Permite a implementação de filtragem de grafos sem treinamento e de alta acurácia em conjuntos de dados de larga escala (dezenas de milhões de interações) em hardware padrão, onde métodos anteriores falharam.
• Equilibrar Acurácia e Eficiência: Demonstra que a eficiência de memória não exige um compromisso na qualidade da recomendação; de fato, a capacidade de usar filtros expressivos de alta ordem dentro de um framework com restrição de memória leva a uma acurácia superior.
• Aplicabilidade no Mundo Real: A baixa latência de inferência e a natureza sem treinamento tornam o Mem-GF adequado para sistemas de recomendação em tempo real com restrições rigorosas de hardware.

Os autores observam limitações, incluindo a adequação primária do método para grafos de similaridade de itens derivados de interações usuário-item (em vez de grafos heterogêneos) e a potencial sensibilidade a sinais de usuários extremamente esparsos (cenários de cold-start). Trabalhos futuros são propostos para estender o Mem-GF para estruturas de grafos heterogêneos e sistemas distribuídos.