Towards scalable and evolving graph-based collaborative filtering for data stream recommendation

Abstract

Resumo: Sistemas de recomendação são projetados para recomendar itens para usuários com base em seus interesses, a fim de aumentar seu engajamento ao interagir com sistemas online. O aumento significativo no volume de dados gerados por usuários em alta frequência resulta na necessidade de projetar sistemas de recomendação escaláveis e capazes de aprender dinamicamente, com base somente em dados recém gerados, ao menos tão rápido quanto à sua chegada, e que também sejam capazes de recomendar itens com base em informações atuais, com recursos de processamento e memória restritos. No entanto, algoritmos de recomendação bem sucedidos, que tradicionalmente dependem de re-treinamento esporádico a partir de dados previamente armazenados, não são projetados para adaptar-se de tal maneira, gerando problemas de escalabilidade e adaptabilidade. Uma alternativa é projetar sistemas de recomendação como uma tarefa de mineração de fluxos contínuos de dados, usando aprendizado incremental. Tal abordagem permite processar feedback de usuários continuamente e atualizar modelos de recomendação com base apenas em novos dados recebidos, sem a necessidade de armazenar estes dados, que podem então ser descartados após seu processamento. Embora sistemas de recomendação baseados em fluxos contínuos de dados estejam recentemente tornando-se um tópico ativo de pesquisa, ainda são pouco frequentes na literatura, e diversos problemas associados à sua aplicação, tais como esparsidade, precisão, escalabilidade e desvio de conceito, seguem em aberto. Neste contexto, a principal contribuição desta pesquisa é um modelo baseado em fluxo contínuo de dados, IGSI ˆ ???? , que consiste em um grafo de interações sequenciais com esquecimento para recomendação em fluxo contínuo de dados com feedback implícito. IGSI ˆ ???? incorpora feedback em um grafo, cujos vértices representam itens, de maneira incremental, com a suposição de que o comportamento dos usuários pode ser extraído dessas sequências de interações com o passar do tempo, capturando interesses de curto prazo e de longo prazo. Nossa proposta é robusta à esparsidade, possui alta capacidade incremental e flexibilidade no processo de recomendação. A abordagem recomenda itens para usuários com base em simulações de passeios aleatórios curtos, o que permite a geração de recomendações escaláveis. Nosso trabalho também contribui com um mecanismo de esquecimento, local neighborhood decay, projetado especificamente para explorar as vantagens de IGSI ˆ ???? , e que pode ser generalizada para abordagens relacionadas. Tal mecanismo reutiliza as amostras de passeios aleatórios geradas originalmente para recomendação para capturar informações estruturais do grafo, e inferir a relevância dos itens. Arestas obsoletas são então eliminadas com base nessas informações e em fatores de popularidade. Avaliamos nossa proposta utilizando várias métricas e comparamos os resultados com vários algoritmos incrementais em fluxos de dados simulados. Os resultados demonstram a eficácia de nossa proposta, que em geral supera outros algoritmos em taxa de acerto, com tempos de atualização e recomendação muito competitivos. Além disso, os resultados demonstram que nossa técnica de esquecimento é capaz de aumentar escalabilidade, taxa de acerto e diversidade.

Abstract: Recommender systems are designed to recommend items to users based on their interests, enhancing their engagement and satisfaction when interacting with online systems. The explosion of user-generated data at fast rates in online services leads to the need for designing scalable recommender systems that are able to learn on-the-fly. Such design requires learning from newly generated data on a single pass, at least as fast as data arrives, while also allowing the recommendation of relevant items based on up-to-date information with restricted time and processing requirements. However, successful recommendation algorithms, which traditionally rely on batch processing, are not designed to adapt to continuous flow of data, raising scalability and adaptability issues. An alternative approach is to view the recommendation problem under a data stream framework and design Stream-Based Recommender Systems, using incremental learning. This design allows continuous processing of user feedback and the update of models solely with incoming data, without requiring storage of observations, which can be discarded after processing. Although stream-based approaches are recently becoming an active topic of research, recommendation under the lens of data streams is still infrequent, and several issues still pertain, such as sparsity, accuracy, scalability and concept drift. Thus, the main contribution of this research is a stream-based model, IGSI ˆ ???? , that consists in an evolving graph of sequential interactions with forgetting for data stream recommendation with implicit feedback. IGSI ˆ ???? incorporates feedback into an item-graph in incremental manner with the assumption that user behavior can be extracted from such sequence of interactions as time passes, capturing short-term and long-term interests. By focusing on a graph-based approach, our proposal is robust to sparsity, has natural incremental capability and flexibility on the recommendation procedure. It recommends items to users based on simulations of short random walks, which allows the generation of scalable recommendations. This work also contributes with a forgetting mechanism, local neighborhood decay, specifically designed to explore the advantages of IGSI ˆ ???? , that can be generalized to related approaches. This mechanism reuses the random walk samples originally generated for recommendation to capture structural information from the graph and infer the relevance of items. Obsolete connections are then faded based on this information and popularity factors. We evaluated our proposal under several metrics and compared the results with other related incremental algorithms on simulated data stream settings. The results suggest the effectiveness of our proposal, which generally outperforms competing algorithms in accuracy, with very competitive update and recommendation times. Also, the results suggest that our proposed forgetting technique is able to increase scalability, accuracy and diversity.