From communities to interpretable network and word embedding: an unified approach
Authors:
- Thibault ProuteauTPThibault Prouteau
- Nicolas DuguéNDNicolas Dugué
- Simon GuillotSGSimon Guillot
Preprint
Abstract
Modelling information from complex systems such as humans social interaction or words co-occurrences in our languages can help to understand how these systems are organized and function. Such systems can be modelled by networks, and network theory provides a useful set of methods to analyze them. Among these methods, graph embedding is a powerful tool to summarize the interactions and topology of a network in a vectorized feature space. When used in input of machine learning algorithms, embedding vectors help with common graph problems such as link prediction, graph matching, etc. Word embedding has the goal of representing the sense of words, extracting it from large text corpora. Despite differences in the structure of information in input of embedding algorithms, many graph embedding approaches are adapted and inspired from methods in NLP. Limits of these methods are observed in both domains. Most of these methods require long and resource greedy training. Another downside to most methods is that they are black-box, from which understanding how the information is structured is rather complex. Interpretability of a model allows understanding how the vector space is structured without the need for external information, and thus can be audited more easily. With both these limitations in mind, we propose a novel framework to efficiently embed network vertices in an interpretable vector space. Our Lower Dimension Bipartite Framework (LDBGF) leverages the bipartite projection of a network using cliques to reduce dimensionality. Along with LDBGF, we introduce two implementations of this framework that rely on communities instead of cliques: SINr-NR and SINr-MF. We show that SINr-MF can perform well on classical graphs and SINr-NR can produce high-quality graph and word embeddings that are interpretable and stable across runs.Keywords
All Related Versions
- Version 1, 2024-12-11, ArXiv
- Published version: Journal of Complex Networks, 12 (6).
This publication has 40 references indexed in Scilit:
- Green Algorithms: Quantifying the Carbon Footprint of ComputationAdvanced Science, 2021
- SINr: Fast Computing of Sparse Interpretable Node Representations is not a Sin!2021
- Stop explaining black box machine learning models for high stakes decisions and use interpretable models insteadNature Machine Intelligence, 2019
- Systematic Biases in Link Prediction: Comparing Heuristic and Graph Embedding Based Methods2018
- Online graph regularized non-negative matrix factorization for large-scale datasetsNeurocomputing, 2016
- Multi-scale Modularity and Dynamics in Complex Networks2013
- Learning the parts of objects by non-negative matrix factorizationNature, 1999
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- Clique partitions and clique coveringsDiscrete Mathematics, 1988
- Hierarchical structure in perceptual representationCognitive Psychology, 1977