We address the problem of encoding a graph of order n into a graph of order k < n in a way to minimize reconstruction error. We characterize this encoding in terms of a particular factorization of the adjacency matrix of the original graph. The factorization is determined as the solution of a discrete optimization problem, which is for convenience relaxed into a continuous, but equivalent, one. We propose a new multiplicative update rule for the optimization task. Experiments are conducted to assess the effectiveness of the proposed approach.
A Matrix Factorization Approach to Graph Compression
NOURBAKHSH, FARSHAD;PELILLO, Marcello
2014-01-01
Abstract
We address the problem of encoding a graph of order n into a graph of order k < n in a way to minimize reconstruction error. We characterize this encoding in terms of a particular factorization of the adjacency matrix of the original graph. The factorization is determined as the solution of a discrete optimization problem, which is for convenience relaxed into a continuous, but equivalent, one. We propose a new multiplicative update rule for the optimization task. Experiments are conducted to assess the effectiveness of the proposed approach.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.