Abstract | ||
---|---|---|
We address the problem of encoding a graph of order \(\mathsf {n}\) into a graph of order \(\mathsf {k}<\mathsf {n}\) in a way to minimize reconstruction error. This encoding is characterized 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. Our formulation does not require to have the full graph, but it can factorize the graph also in the presence of partial information. We propose a multiplicative update rule for the optimization task resembling the ones introduced for nonnegative matrix factorization, and convergence properties are proven. Experiments are conducted to assess the effectiveness of the proposed approach. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/s13042-014-0286-5 | Int. J. Machine Learning & Cybernetics |
Keywords | Field | DocType |
Matrix factorization, Graph compression, Stochastic blockmodel | Adjacency matrix,Discrete mathematics,Combinatorics,Graph energy,Line graph,Graph factorization,Directed graph,Regular graph,Graph bandwidth,Voltage graph,Mathematics | Journal |
Volume | Issue | ISSN |
6 | 4 | 1868-808X |
Citations | PageRank | References |
3 | 0.40 | 21 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Farshad Nourbakhsh | 1 | 13 | 3.02 |
Samuel Rota Bulò | 2 | 564 | 33.69 |
Marcello Pelillo | 3 | 1888 | 150.33 |