Skip to main content
Erschienen in: International Journal of Machine Learning and Cybernetics 4/2015

01.08.2015 | Original Article

A matrix factorization approach to graph compression with partial information

verfasst von: Farshad Nourbakhsh, Samuel Rota Bulò, Marcello Pelillo

Erschienen in: International Journal of Machine Learning and Cybernetics | Ausgabe 4/2015

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Weitere Produktempfehlungen anzeigen
Fußnoten
1
There is no explicit update rule in the paper to find the specific relaxed factorization, but it could be obtained by using Theorem 1.
 
2
This however should not be taken as a truth holding in general, for it depends also on the structure of the input graph.
 
3
For NMF and GNMF this coincides with the number of latent dimensions.
 
Literatur
1.
Zurück zum Zitat Airoldi EM, Blei DM, Fienberg SE, Xing EP (2008) Mixed membership stochastic blockmodels. J Mach Learn Res 9:1981–2014MATH Airoldi EM, Blei DM, Fienberg SE, Xing EP (2008) Mixed membership stochastic blockmodels. J Mach Learn Res 9:1981–2014MATH
2.
Zurück zum Zitat Baum LE, Eagon JA (1967) An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bull Am Math Soc 73:360–363MathSciNetCrossRefMATH Baum LE, Eagon JA (1967) An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bull Am Math Soc 73:360–363MathSciNetCrossRefMATH
3.
Zurück zum Zitat Blei DM, Ng AY, Jordan MI (2003) Latent Dirichlet allocation. J. Mach Learn Res 3:993–1022 Blei DM, Ng AY, Jordan MI (2003) Latent Dirichlet allocation. J. Mach Learn Res 3:993–1022
4.
Zurück zum Zitat Cai D, He X, Han J, Huang TS (2011) Graph regularized nonnegative matrix factorization for data representation. IEEE Trans Pattern Anal Mach Intell 33(8):1548–1560CrossRef Cai D, He X, Han J, Huang TS (2011) Graph regularized nonnegative matrix factorization for data representation. IEEE Trans Pattern Anal Mach Intell 33(8):1548–1560CrossRef
5.
Zurück zum Zitat Choi Y, Szpankowski W (2012) Compression of graphical structures: fundamental limits, algorithms, and experiments. IEEE Trans Inf Theory 58(2):620–638MathSciNetCrossRef Choi Y, Szpankowski W (2012) Compression of graphical structures: fundamental limits, algorithms, and experiments. IEEE Trans Inf Theory 58(2):620–638MathSciNetCrossRef
6.
Zurück zum Zitat Deerwester S, Dumais ST, Furnas GW, Landauer TK, Harshman R (1990) Indexing by latent semantic analysis. J Am Soc Inf Sci 41(6):391–407CrossRef Deerwester S, Dumais ST, Furnas GW, Landauer TK, Harshman R (1990) Indexing by latent semantic analysis. J Am Soc Inf Sci 41(6):391–407CrossRef
7.
Zurück zum Zitat Dhillon IS, Guan Y, Kulis B (2004) Kernel k-means: spectral clustering and normalized cuts. Int Conf Knowl Discov Data Min 10:551–556 Dhillon IS, Guan Y, Kulis B (2004) Kernel k-means: spectral clustering and normalized cuts. Int Conf Knowl Discov Data Min 10:551–556
8.
Zurück zum Zitat Ding C, He, X, Simon HD (2005) On the equivalence of nonnegative matrix factorization and spectral clustering. In: SIAM data mining conference, pp 606–610 Ding C, He, X, Simon HD (2005) On the equivalence of nonnegative matrix factorization and spectral clustering. In: SIAM data mining conference, pp 606–610
9.
Zurück zum Zitat Ding C, Li, T, Jordan MI (2008) Nonnegative matrix factorization for combinatorial optimization: spectral clustering, graph matching and clique finding. In: IEEE international conference on data mining, pp 183–192 Ding C, Li, T, Jordan MI (2008) Nonnegative matrix factorization for combinatorial optimization: spectral clustering, graph matching and clique finding. In: IEEE international conference on data mining, pp 183–192
10.
Zurück zum Zitat Ding C, Li T, Peng W (2008) On the equivalence between non-negative matrix factorization and probabilistic latent semantic indexing. Comput Stat Data Anal 52(8):3913–3927MathSciNetCrossRefMATH Ding C, Li T, Peng W (2008) On the equivalence between non-negative matrix factorization and probabilistic latent semantic indexing. Comput Stat Data Anal 52(8):3913–3927MathSciNetCrossRefMATH
11.
Zurück zum Zitat Goldenberg A, Zheng AX, Fienberg SE, Airoldi EM (2010) A survey of statistical network models. Found Trends Mach Learn 2(2):129–233CrossRef Goldenberg A, Zheng AX, Fienberg SE, Airoldi EM (2010) A survey of statistical network models. Found Trends Mach Learn 2(2):129–233CrossRef
12.
Zurück zum Zitat Hofmann T (2000) Learning the similarity of documents: an information-geometric approach to document retrieval and categorization. Adv Neural Inf Process Syst 12:914–920 Hofmann T (2000) Learning the similarity of documents: an information-geometric approach to document retrieval and categorization. Adv Neural Inf Process Syst 12:914–920
13.
14.
15.
Zurück zum Zitat Hubbard TJP, Murzin AG, Brenner SE, Chothia C (1995) SCOP: a structural classification of proteins database for the investigation of sequences and structures. J Mol Biol 247:536–540 Hubbard TJP, Murzin AG, Brenner SE, Chothia C (1995) SCOP: a structural classification of proteins database for the investigation of sequences and structures. J Mol Biol 247:536–540
16.
Zurück zum Zitat Jolliffe I (1987) Principal component analysis. Springer, New York Jolliffe I (1987) Principal component analysis. Springer, New York
17.
Zurück zum Zitat Kuang D, Park H, Ding C (2012) Symmetric nonnegative matrix factorization for graph clustering. In: SIAM international conference data mining, pp 106–117 Kuang D, Park H, Ding C (2012) Symmetric nonnegative matrix factorization for graph clustering. In: SIAM international conference data mining, pp 106–117
18.
Zurück zum Zitat Lakshminarayanan B, Raich R (2010) Non-negative matrix factorization for parameter estimation in hidden Markov models. In: IEEE international workshop on machine learning for signal processing, pp 89–94 Lakshminarayanan B, Raich R (2010) Non-negative matrix factorization for parameter estimation in hidden Markov models. In: IEEE international workshop on machine learning for signal processing, pp 89–94
19.
Zurück zum Zitat Lee DD, Seung HS (1999) Learning the parts of objects by non-negative matrix factorization. Nature 401:788–791CrossRef Lee DD, Seung HS (1999) Learning the parts of objects by non-negative matrix factorization. Nature 401:788–791CrossRef
20.
Zurück zum Zitat Lee DD, Seung HS (2000) Algorithms for non-negative matrix factorization. In: Advances in neural information processing systems, pp 556–562 Lee DD, Seung HS (2000) Algorithms for non-negative matrix factorization. In: Advances in neural information processing systems, pp 556–562
21.
Zurück zum Zitat Li P, Bu J, Yang Y, Ji R, Chen C, Cai D (2014) Discriminative orthogonal nonnegative matrix factorization with flexibility for data representation. Exp Syst Appl 41(4):1283–1293CrossRef Li P, Bu J, Yang Y, Ji R, Chen C, Cai D (2014) Discriminative orthogonal nonnegative matrix factorization with flexibility for data representation. Exp Syst Appl 41(4):1283–1293CrossRef
22.
Zurück zum Zitat Li P, Chen C, Bu J (2012) Clustering analysis using manifold kernel concept factorization. Neural Comput 87:120–131 Li P, Chen C, Bu J (2012) Clustering analysis using manifold kernel concept factorization. Neural Comput 87:120–131
23.
Zurück zum Zitat Lorrain F, White HC (1971) Structural equivalence of individuals in social networks. J Math Sociol 1:49–80CrossRef Lorrain F, White HC (1971) Structural equivalence of individuals in social networks. J Math Sociol 1:49–80CrossRef
25.
Zurück zum Zitat Navlakha S, Rastogi R, Shrivastava N (2008) Graph summarization with bounded error. In: ACM SIGMOD international conference on management of data, pp 419–432 Navlakha S, Rastogi R, Shrivastava N (2008) Graph summarization with bounded error. In: ACM SIGMOD international conference on management of data, pp 419–432
26.
Zurück zum Zitat Nepusz T, Petróczi A, Négyessy L, Bazsó F (2008) Fuzzy communities and the concept of bridgeness in complex networks. Phys Rev E 77(1):016107MathSciNetCrossRef Nepusz T, Petróczi A, Négyessy L, Bazsó F (2008) Fuzzy communities and the concept of bridgeness in complex networks. Phys Rev E 77(1):016107MathSciNetCrossRef
27.
Zurück zum Zitat Nourbakhsh F, Rota Bulò, S, Pelillo M (2014) A matrix factorization approach to graph compression. In: 22nd international conference on pattern recognition. IEEE, Stockholm, Sweden, 24–28 Aug 2014 Nourbakhsh F, Rota Bulò, S, Pelillo M (2014) A matrix factorization approach to graph compression. In: 22nd international conference on pattern recognition. IEEE, Stockholm, Sweden, 24–28 Aug 2014
28.
Zurück zum Zitat Paatero P, Tapper AU (1994) Positive matrix factorization: a non-negative factor model with optimal utilization of error estimates of data values. Environmetrics 5:111–126CrossRef Paatero P, Tapper AU (1994) Positive matrix factorization: a non-negative factor model with optimal utilization of error estimates of data values. Environmetrics 5:111–126CrossRef
29.
Zurück zum Zitat Psorakis I, Roberts S, Ebden M, Sheldon B (2011) Overlapping community detection using nonnegative matrix factorization. Phys Rev E 83(6):066114CrossRef Psorakis I, Roberts S, Ebden M, Sheldon B (2011) Overlapping community detection using nonnegative matrix factorization. Phys Rev E 83(6):066114CrossRef
30.
Zurück zum Zitat Rota Bulò S, Lourenço A, Fred, ALN, Pelillo M (2010) Pairwise probabilistic clustering using evidence accumulation. In: International workshop on structure and synthesis pattern recognition, pp 395–404 Rota Bulò S, Lourenço A, Fred, ALN, Pelillo M (2010) Pairwise probabilistic clustering using evidence accumulation. In: International workshop on structure and synthesis pattern recognition, pp 395–404
31.
Zurück zum Zitat Rota Bulò S, Pelillo M (2010) Probabilistic clustering using the baum-eagon inequality. In: International conference on pattern recognition, pp 1429–1432 Rota Bulò S, Pelillo M (2010) Probabilistic clustering using the baum-eagon inequality. In: International conference on pattern recognition, pp 1429–1432
32.
Zurück zum Zitat Schölkopf B, Smola A, M\(\ddot{\rm l}\)ler KR (1998) Nonlinear component analysis as a kernel eigenvalue problem. Neural Comput 10(5):1299–1319 Schölkopf B, Smola A, M\(\ddot{\rm l}\)ler KR (1998) Nonlinear component analysis as a kernel eigenvalue problem. Neural Comput 10(5):1299–1319
33.
Zurück zum Zitat Shi J, Malik J (2000) Normalized cuts and image segmentation. IEEE Trans Pattern Anal Mach Intell 22:888–905CrossRef Shi J, Malik J (2000) Normalized cuts and image segmentation. IEEE Trans Pattern Anal Mach Intell 22:888–905CrossRef
34.
Zurück zum Zitat Sperotto A, Pelillo M (2007) Szemerédis regularity lemma and its applications to pairwise clustering and segmentation. In: Energy minimization methods in computer vision and pattern recognition, pp 13–27 Sperotto A, Pelillo M (2007) Szemerédis regularity lemma and its applications to pairwise clustering and segmentation. In: Energy minimization methods in computer vision and pattern recognition, pp 13–27
35.
Zurück zum Zitat Szemerédi, E (1978) Regular partitions of graphs. In: Problèmes combinatoires et thorie des graphes. CNRS, Paris, pp 399–401 Szemerédi, E (1978) Regular partitions of graphs. In: Problèmes combinatoires et thorie des graphes. CNRS, Paris, pp 399–401
36.
Zurück zum Zitat Toivonen H, Zhou F, Hartikainen A, Hinkka A (2011) Compression of weighted graphs. In: International conference on knowledge discovery and data mining, pp 965–973 Toivonen H, Zhou F, Hartikainen A, Hinkka A (2011) Compression of weighted graphs. In: International conference on knowledge discovery and data mining, pp 965–973
37.
Zurück zum Zitat Verma D, Meila M (2003) Comparison of spectral clustering methods, Technical report. University of Washington Verma D, Meila M (2003) Comparison of spectral clustering methods, Technical report. University of Washington
38.
Zurück zum Zitat Xu W, Gong, Y (2004) Document clustering by concept factorization. In: Proceedings of 27th annual international ACM SIGIR conference on Research and development in information retrieval, pp 202–209 Xu W, Gong, Y (2004) Document clustering by concept factorization. In: Proceedings of 27th annual international ACM SIGIR conference on Research and development in information retrieval, pp 202–209
39.
Zurück zum Zitat Yang Z, Oja E (2012) Quadratic nonnegative matrix factorization. Pattern Recognit 45(4):1500–1510CrossRefMATH Yang Z, Oja E (2012) Quadratic nonnegative matrix factorization. Pattern Recognit 45(4):1500–1510CrossRefMATH
40.
Zurück zum Zitat Zhang H, Yang Z, Oja E (2014) Adaptive multiplicative updates for quadratic nonnegative matrix factorization. Neural Comput 134:206–213 Zhang H, Yang Z, Oja E (2014) Adaptive multiplicative updates for quadratic nonnegative matrix factorization. Neural Comput 134:206–213
Metadaten
Titel
A matrix factorization approach to graph compression with partial information
verfasst von
Farshad Nourbakhsh
Samuel Rota Bulò
Marcello Pelillo
Publikationsdatum
01.08.2015
Verlag
Springer Berlin Heidelberg
Erschienen in
International Journal of Machine Learning and Cybernetics / Ausgabe 4/2015
Print ISSN: 1868-8071
Elektronische ISSN: 1868-808X
DOI
https://doi.org/10.1007/s13042-014-0286-5

Weitere Artikel der Ausgabe 4/2015

International Journal of Machine Learning and Cybernetics 4/2015 Zur Ausgabe

Neuer Inhalt