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.
2014
International Conference on Pattern Recognition
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/42444
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact