Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Moment-Based Parameter Estimation in Binomial Random Intersection Graph Models Kapitel lesen Erstes Kapitel lesen

2017 | Supplement | Buchkapitel

Kernels on Graphs as Proximity Measures

verfasst von : Konstantin Avrachenkov, Pavel Chebotarev, Dmytro Rubanov

Erschienen in: Algorithms and Models for the Web Graph

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

Kernels and, broadly speaking, similarity measures on graphs are extensively used in graph-based unsupervised and semi-supervised learning algorithms as well as in the link prediction problem. We analytically study proximity and distance properties of various kernels and similarity measures on graphs. This can potentially be useful for recommending the adoption of one or another similarity measure in a machine learning method. Also, we numerically compare various similarity measures in the context of spectral clustering and observe that normalized heat-type similarity measures with log modification generally perform the best.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Common Adversaries Form Alliances: Modelling Complex Networks via Anti-transitivity
Nächstes Kapitel Endogenous Differentiation of Consumer Preferences Under Quality Uncertainty in a SPA Network
Fußnoten
1
M. Saerens [36] has remarked that a more suitable name could be Neumann diffusion kernel, referring to the Neumann series \(\sum _{k=0}^\infty T^k\) (where T is an operator) named after Carl Gottfried Neumann, while a connection of that to John von Neumann is not obvious (the concept of von Neumann kernel in group theory is essentially different).
 
2
In fact, L. Katz considered \(\sum _{k=1}^\infty (\alpha W)^k.\)
 
3
For the properties of M-matrices, we refer to [29].
 
4
If K is symmetric, then (6) coincides with (2).
 
5
On various alternative versions of the triangle inequality, we refer to [17].
 
Literatur
1.
Avrachenkov, K., Mishenin, A., Gonçalves, P., Sokol, M.: Generalized optimization framework for graph-based semi-supervised learning. In: Proceedings of the 2012 SIAM International Conference on Data Mining, pp. 966–974 (2012)
2.
Avrachenkov, K., Gonçalves, P., Sokol, M.: On the choice of kernel and labelled data in semi-supervised learning methods. In: Bonato, A., Mitzenmacher, M., Prałat, P. (eds.) WAW 2013. LNCS, vol. 8305, pp. 56–67. Springer, Cham (2013). doi:10.​1007/​978-3-319-03536-9_​5 CrossRef
3.
Avrachenkov, K., Chebotarev, P., Mishenin, A.: Semi-supervised learning with regularized Laplacian. Optim. Methods Softw. 32(2), 222–236 (2017)MathSciNetCrossRefMATH
4.
Avrachenkov, K., van der Hofstad, R., Sokol, M.: Personalized PageRank with node-dependent restart. In: Proceedings of International Workshop on Algorithms and Models for the Web-Graph, pp. 23–33 (2014)
5.
Backstrom, L., Leskovec, J.: Supervised random walks: predicting and recommending links in social networks. Proc. ACM WSDM 2011, 635–644 (2011)
6.
Boley, D., Ranjan, G., Zhang, Z.L.: Commute times for a directed graph using an asymmetric Laplacian. Linear Algebra Appl. 435(2), 224–242 (2011)MathSciNetCrossRefMATH
7.
Chapelle, O., Schölkopf, B., Zien, A.: Semi-Supervised Learning. MIT Press, Cambridge (2006)CrossRef
8.
9.
Chebotarev, P.: A class of graph-geodetic distances generalizing the shortest-path and the resistance distances. Discrete Appl. Math. 47(3), 403–413 (2011)MathSciNetMATH
10.
11.
Chebotarev, P. Yu., Shamis, E.V.: On the proximity measure for graph vertices provided by the inverse Laplacian characteristic matrix. In: Abstracts of the conference “Linear Algebra and its Application”, 10–12 June 1995, The Institute of Mathematics and its Applications, in conjunction with the Manchester Center for Computational Mathematics, Manchester, UK (pp. 6–7), URL http://​www.​ma.​man.​ac.​uk/​higham/​laa95/​abstracts.​ps (1995)
12.
Chebotarev, P.Y., Shamis, E.V.: The matrix-forest theorem and measuring relations in small social groups. Autom. Remote Control 58(9), 1505–1514 (1997)MATH
13.
Chebotarev, P.Y., Shamis, E.V.: On a duality between metrics and \(\varSigma \)-proximities. Autom. Remote Control 59(4), 608–612 (1998)MATH
14.
Chebotarev, P.Y., Shamis, E.V.: On proximity measures for graph vertices. Autom. Remote Control 59(10), 1443–1459 (1998)MATH
15.
Chung, F.: Spectral graph theory, vol. 92. American Math. Soc. (1997)
16.
Chung, F.: The heat kernel as the pagerank of a graph. Proc. Natl. Acad. Sci. 104(50), 19735–19740 (2007)CrossRef
17.
18.
Dhillon, I.S., Fan, J., Guan, Y.: Efficient clustering of very large document collections. Data Min. sci. Eng. Appl. 2, 357–381 (2001)
19.
Dhillon, I.S., Guan, Y., Kulis, B.: Kernel k-means: spectral clustering and normalized cuts. Proc. ACM KDD 2004, 551–556 (2004)
20.
Estrada, E., Hatano, N.: Statistical-mechanical approach to subgraph centrality in complex networks. Chem. Phys. Lett. 439, 247–251 (2007)CrossRef
21.
22.
Estrada, E., Silver, G.: Accounting for the role of long walks on networks via a new matrix function. J. Math. Anal. Appl. 449, 1581–1600 (2017)MathSciNetCrossRefMATH
23.
Fouss, F., Yen L., Pirotte, A., Saerens, M.: An experimental investigation of graph kernels on a collaborative recommendation task. In: Proceedings of the Sixth International Conference on Data Mining (ICDM 2006), pp. 863–868, IEEE (2006)
24.
Fouss, F., Saerens, M., Shimbo, M.: Algorithms and Models for Network Data and Link Analysis. Cambridge University Press, Cambridge (2016)CrossRef
25.
Horn, R.A., Johnson, C.R.: Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2013)MATH
26.
Ivashkin, V., Chebotarev, P.: Do logarithmic proximity measures outperform plain ones in graph clustering? In: Kalyagin, V.A., et al. (eds.) Models, Algorithms and Technologies for Network Analysis. Springer Proceedings in Mathematics & Statistics, vol. 197, pp. 87–105. Springer, Cham (2017)CrossRef
27.
28.
Katz, L.: A new status index derived from sociometric analysis. Psychometrika 18(1), 39–43 (1953)CrossRefMATH
29.
Kirkland, S.J., Neumann, M.: Group Inverses of M-matrices and Their Applications. CRC Press, Boca Raton (2012)MATH
30.
Kivimäki, I., Shimbo, M., Saerens, M.: Developments in the theory of randomized shortest paths with a comparison of graph node distances. Phys. A 393, 600616 (2014)CrossRef
31.
Kondor, R.I., Lafferty, J.: Diffusion kernels on graphs and other discrete input spaces. In: Proceedings of ICML, pp. 315–322 (2002)
32.
33.
Liben-Nowell, D., Kleinberg, J.: The link-prediction problem for social networks. J. Assoc. Inform. Sci. Technol. 58(7), 1019–1031 (2007)CrossRef
34.
Schoenberg, I.J.: Remarks to Maurice Fréchet’s article “Sur la définition axiomatique d’une classe d’espace distanciés vectoriellement applicable sur l’espace de Hilbert”. Ann. Math. 36(3), 724–732 (1935)MathSciNetCrossRefMATH
35.
36.
37.
Kandola, J., Shawe-Taylor, J., Cristianini, N.: Learning semantic similarity. In: Neural Information Processing Systems 15 (NIPS 2015). MIT Press (2002)
38.
Shawe-Taylor, J., Cristianini, N.: Kernel Methods for Pattern Analysis. Cambridge University Press, Cambridge (2004)CrossRefMATH
39.
Smola, A.J., Kondor, R.: Kernels and regularization on graphs. In: Learning Theory and Kernel Machines, pp. 144–158 (2003)
40.
Sommer, F., Fouss, F., Saerens, M.: Comparison of graph node distances on clustering tasks. In: Villa, A.E.P., Masulli, P., Pons Rivero, A.J. (eds.) ICANN 2016. LNCS, vol. 9886, pp. 192–201. Springer, Cham (2016). doi:10.​1007/​978-3-319-44778-0_​23 CrossRef
41.
Vishwanathan, S.V.N., Schraudolph, N.N., Kondor, R., Borgwardt, K.M.: Graph kernels. J. Mach. Learn. Res. 11, 1201–1242 (2010)MathSciNetMATH
42.
43.
Zhou, D., Schölkopf, B., Hofmann, T.: Semi-supervised learning on directed graphs. In: Proceeedings of NIPS, pp. 1633–1640 (2004)
44.
Müller, K.-R., Mika, S., Rätsch, G., Tsuda, K., Schölkopf, B.: An Introduction to kernel-based learning algorithms. IEEE Trans. Neural Networks 12(2), 181–202 (2001)CrossRef
Metadaten
Titel
Kernels on Graphs as Proximity Measures
verfasst von
Konstantin Avrachenkov
Pavel Chebotarev
Dmytro Rubanov
Copyright-Jahr
2017
Buch
Algorithms and Models for the Web Graph

Print ISBN: 978-3-319-67809-2

Electronic ISBN: 978-3-319-67810-8

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-67810-8_3