research-article

Generative Graph Models based on Laplacian Spectra?

Authors:

David KempeAuthors Info & Claims

WWW '19: The World Wide Web Conference

Pages 1691 - 1701

https://doi.org/10.1145/3308558.3313631

Published: 13 May 2019 Publication History

Abstract

We present techniques for generating random graphs whose Laplacian spectrum approximately matches that of a given input graph. The motivation for matching the Laplacian spectrum is that it naturally encodes high-level connectivity information about the input graph; most existing models (e.g., variants of the Configuration Model, Stochastic Block Model, or Kronecker Graphs) focus on local structure or limited high-level partitions.

Our techniques succeed in matching the spectrum of the input graph more closely than the benchmark models. We also evaluate our generative model using other global and local properties, including shortest path distances, betweenness centrality, degree distribution, and clustering coefficients. The graphs produced by our model almost always match the input graph better than those produced by the benchmark models with respect to shortest path distance and clustering coefficient distributions. The performance on betweenness centrality is comparable to the benchmarks, while a worse match on the degree distribution is a price our method pays for more global similarity.

Our results suggest that focusing on spectral properties may lead to good performance for other global properties, at a modest loss in local similarity. Since global connectivity patterns are usually more important than local features for processes such as information flow, spread of epidemics, routing, etc., our main goal is to advocate for a shift in focus from graph generative models matching local properties to those matching global connectivity patterns.

References

[1]

P.-A. Absil, Robert Mahony, and Rodolphe Sepulchre. 2009. Optimization algorithms on matrix manifolds. Princeton University Press.

[2]

P.-A. Absil and Je´r&ocir;me Malick. 2012. Projection-like retractions on matrix manifolds. SIAM Journal on Optimization22, 1 (2012), 135-158.

Digital Library

[3]

Luca Baldesi, Carter T Butts, and Athina Markopoulou. 2018. Spectral Graph Forge: Graph Generation Targeting Modularity. In Proc. 37th IEEE INFOCOM Conference. IEEE, 1727-1735.

Digital Library

[4]

Albert-László Barabási and Re´ka Albert. 1999. Emergence of scaling in random networks. Science286, 5439 (1999), 509-512.

[5]

Edward A. Bender and E. Rodney Canfield. 1978. The asymptotic number of labelled graphs with given degree sequences. Journal of Combinatorial Theory (A)24 (1978), 296-307.

[6]

Noam Berger, Christian Borgs, Jennifer Chayes, and Amin Saberi. 2005. On the Spread of Viruses on the Internet. In Proc. 16th ACM-SIAM Symp. on Discrete Algorithms. 301-310.

Digital Library

[7]

Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. 2018. NetGAN: Generating Graphs via Random Walks. In Proc. 35th Intl. Conf. on Machine Learning. 610-619.

[8]

Be´la Bollobás. 1998. Random Graphs. In Modern Graph Theory. Springer, 215-252.

[9]

Alberto Borobia and Roberto Canogar. 2017. The real nonnegative inverse eigenvalue problem is NP-hard. Linear Algebra Appl.522(2017), 127 - 139.

[10]

Steve Butler and Jason Grout. 2011. A construction of cospectral graphs for the normalized Laplacian. The Electronic Journal of Combinatorics18, 1 (2011), 231.

[11]

Chen Chen, Hanghang Tong, B. Aditya Prakash, Tina Eliassi-Rad, Michalis Faloutsos, and Christos Faloutsos. 2016. Eigen-Optimization on large graphs by edge manipulation. ACM Transactions on Knowledge Discovery from Data10, 4 (2016), 49.

Digital Library

[12]

Moody T. Chu and Gene H. Golub. 2005. Inverse Eigenvalue Problems: Theory, Algorithms, and Applications. Oxford University Press.

[13]

Fan R. K. Chung. 1997. Spectral Graph Theory. American Mathematical Society.

Digital Library

[14]

Fan R. K. Chung and Linyuan Lu. 2002. The average distance in random graphs with given expected degrees. Proc. Natl. Acad. Sci. USA99 (2002), 15879-15882.

[15]

Fan R. K. Chung, Linyuan Lu, and Van Vu. 2003. The spectra of random graphs with given expected degrees. Proc. Natl. Acad. Sci. USA100, 11 (2003), 6313-6318.

[16]

Fan R. K. Chung and Mary Radcliffe. 2011. On the spectra of general random graphs. The Electronic Journal of Combinatorics18, 1 (2011), P215.

[17]

Nicola De Cao and Thomas Kipf. 2018. MolGAN: An implicit generative model for small molecular graphs. In ICML 2018 Workshop on Theoretical Foundations and Applications of Deep Generative Models.

[18]

Alan Edelman, Tomás A. Arias, and Steven T. Smith. 1998. The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl.20, 2 (1998), 303-353.

Digital Library

[19]

Stanley C. Eisenstat and Ilse C. F. Ipsen. 1995. Relative perturbation techniques for singular value problems. SIAM J. Numer. Anal.32, 6 (1995), 1972-1988.

Digital Library

[20]

Matthew Fickus, Dustin G. Mixon, Miriam J. Poteet, and Nate Strawn. 2013. Constructing all self-adjoint matrices with prescribed spectrum and diagonal. Advances in Computational Mathematics39, 3-4 (2013), 585-609.

Digital Library

[21]

Miroslav Fiedler. 1973. Algebraic connectivity of graphs. Czechoslovak mathematical journal23, 2 (1973), 298-305.

[22]

Miroslav Fiedler. 1974. Eigenvalues of nonnegative symmetric matrices. Linear Algebra Appl.9(1974), 119-142.

[23]

Miroslav Fiedler. 1975. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Mathematical Journal25, 4 (1975), 619-633.

[24]

Ove Frank and David Strauss. 1986. Markov Graphs. J. Amer. Statist. Assoc.81, 395 (1986), 832-842.

[25]

Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. 2006. Dependent rounding and its applications to approximation algorithms. J. ACM53, 3 (2006), 324-360.

Digital Library

[26]

Ayalvadi Ganesh, Laurent Massoulie´, and Donald Towlsey. 2005. The effect of network topology on the spread of viruses. In Proc. 24th IEEE INFOCOM Conference. 1455-1466.

[27]

Minas Gjoka, Maciej Kurant, and Athina Markopoulou. 2013. 2.5 k-graphs: from sampling to generation. In Proc. 32nd IEEE INFOCOM Conference. IEEE, 1968-1976.

[28]

Chris D. Godsil and Brendan D. McKay. 1982. Constructing cospectral graphs. Aequationes Mathematicae25, 1 (1982), 257-268.

[29]

Paul W. Holland, Kathryn B. Laskey, and Samuel Leinhardt. 1983. Stochastic Blockmodels: Some First Steps. Social Networks5(1983), 109-137.

[30]

Brian Karrer and Mark E. J. Newman. 2011. Stochastic Blockmodels and Community Structure in Networks. Physical Review E83(2011), 016107.

[31]

Tosio Kato. 1987. Variation of Discrete Spectra. Communications in Mathematical Physics111 (1987), 501-504.

[32]

Vaishnavy Krishnamurthy, Michalis Faloutsos, Marek Chrobak, Jun-Hong Cui, Li Lao, and Allon G. Percus. 2007. Reducing Large Internet Topologies for Faster Simulations. Computer Networks51, 15 (2007), 4284-4302.

Digital Library

[33]

Thomas J. Laffey and Helena Šmigoc. 2007. Construction of nonnegative symmetric matrices with given spectrum. Linear algebra and its applications421, 1 (2007), 97-109.

[34]

Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. 2008. Benchmark graphs for testing community detection algorithms. Physical Review E78(2008), 046110.

[35]

James R. Lee, Shayan Oveis Gharan, and Luca Trevisan. 2014. Multiway spectral partitioning and higher-order Cheeger inequalities. J. ACM61, 6 (2014), 37.

Digital Library

[36]

Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. 2010. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research11 (2010), 985-1042.

Digital Library

[37]

Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2007. Graph Evolution: Densification and Shrinking Diameters. ACM Transactions on Knowledge Discovery from Data1, 1 (2007), 2.

Digital Library

[38]

Jure Leskovec and Rok Sosic. 2016. SNAP: A General-Purpose Network Analysis and Graph-Mining Library. ACM Transactions on Intelligent Systems and Technology8, 1(2016), 1.

Digital Library

[39]

Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. 2018. Learning deep generative models of graphs. (2018). arXiv preprint arXiv:1803.03324.

[40]

Russell Merris. 1997. Large families of Laplacian isospectral graphs. Linear and Multilinear Algebra43, 1-3 (1997), 201-205.

[41]

Michael Molloy and Bruce Reed. 1995. A critical point for random graphs with a given degree sequence. Random Structures and Algorithms6, 2-3 (1995), 161-180.

Digital Library

[42]

Mark E. J. Newman. 2006. Finding community structure in networks using the eigenvectors of matrices. Physical Review E74(2006), 036104.

[43]

Mark E. J. Newman. 2009. Random graphs with clustering. Physical Review Letters103, 5 (2009), 058701.

[44]

Mark E. J. Newman, Steven H. Strogatz, and Duncan J. Watts. 2001. Random graphs with arbitrary degree distributions and their applications. Physical Review E64, 2 (2001), 026118.

[45]

Jorge Nocedal and Stephen Wright. 2006. Numerical Optimization. Springer.

[46]

Chiara Orsini, Marija M. Dankulov, Pol Colomer-de Simón, Almerima Jamakovic, Priya Mahadevan, Amin Vahdat, Kevin E. Bassler, Zoltán Toroczkai, Marián Bogu&ntiled;á, Guido Caldarelli, Santo Fortunato, and Dmitri Kiroukov. 2015. Quantifying randomness in real networks. Nature Communications6(2015), 8627.

[47]

Garry Robins, Philippa Pattison, Yuval Kalish, and Dean Lusher. 2007. An introduction to exponential random graph (p*) models for social networks. Social Networks29(2007), 173-191.

[48]

Christian L Staudt, Michael Hamann, Alexander Gutfraind, Ilya Safro, and Henning Meyerhenke. 2017. Generating realistic scaled complex networks. Applied Network Science2, 1 (2017), 36.

[49]

Yuchung J. Wang and George Y. Wong. 1987. Stochastic Blockmodels for Directed Graphs. J. Amer. Statist. Assoc.82, 397 (1987), 8-19.

[50]

Duncan J. Watts and Steven Strogatz. 1998. Collective dynamics of 'small-world' networks. Nature393(1998), 440-442.

[51]

Zaiwen Wen and Wotao Yin. 2013. A feasible method for optimization with orthogonality constraints. Mathematical Programming142, 1-2 (2013), 397-434.

Digital Library

[52]

David White and Richard C. Wilson. 2007. Spectral generative models for graphs. In Proc. Intl. Conf. on Image Analysis and Processing. 35-42.

Digital Library

[53]

David H. White. 2009. Generative Models for Graphs. Ph.D. Dissertation.

[54]

Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. 2019. A comprehensive survey on graph neural networks. (2019). arXiv preprint arXiv:1901.00596.

[55]

Bai Xiao and Edwin R. Hancock. 2006. A spectral generative model for graph structure. In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR). 173-181.

Digital Library

[56]

Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. 2018. GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models. In Proc. 35th Intl. Conf. on Machine Learning. 5708-5717.

Cited By

Ferguson DMeyer F(2023)Theoretical analysis and computation of the sample Fréchet mean of sets of large graphs for various metricsInformation and Inference: A Journal of the IMA10.1093/imaiai/iaad00212:3(1347-1404)Online publication date: 28-Mar-2023
https://doi.org/10.1093/imaiai/iaad002
Richter H(2023)Spectral dynamics of guided edge removals and identifying transient amplifiers for death–Birth updatingJournal of Mathematical Biology10.1007/s00285-023-01937-187:1Online publication date: 7-Jun-2023
https://doi.org/10.1007/s00285-023-01937-1
Wills PMeyer F(2020)Metrics for graph comparison: A practitioner’s guidePLOS ONE10.1371/journal.pone.022872815:2(e0228728)Online publication date: 12-Feb-2020
https://doi.org/10.1371/journal.pone.0228728

Recommendations

Laplacian spectra of regular graph transformations

Given a graph G with vertex set V(G)=V and edge set E(G)=E, let G^l be the line graph and G^c the complement of G. Let G^0 be the graph with V(G^0)=V and with no edges, G^1 the complete graph with the vertex set V, G^+=G and G^-=G^c. Let B(G) (B^c(G)) ...
Efficient edge domination in regular graphs
Abstract
An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum ...
The spectra and the signless Laplacian spectra of graphs with pockets

Let G[F, Vk, Hv] be the graph with k pockets, where F is a simple graph of order n1, Vk={v1,,vk} is a subset of the vertex set of F and Hv is a simple graph of order m2, v is a specified vertex of Hv. Also let G[F, Ek, Huv] be the graph with k edge-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

WWW '19: The World Wide Web Conference

May 2019

3620 pages

ISBN:9781450366748

DOI:10.1145/3308558

Editors:
Ling Liu
Georgia Tech, USA
,
Ryen White
Microsoft Research, USA

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

IW3C2: International World Wide Web Conference Committee

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 May 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

WWW '19

WWW '19: The Web Conference

May 13 - 17, 2019

CA, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
399
Total Downloads

Downloads (Last 12 months)30
Downloads (Last 6 weeks)6

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ferguson DMeyer F(2023)Theoretical analysis and computation of the sample Fréchet mean of sets of large graphs for various metricsInformation and Inference: A Journal of the IMA10.1093/imaiai/iaad00212:3(1347-1404)Online publication date: 28-Mar-2023
https://doi.org/10.1093/imaiai/iaad002
Richter H(2023)Spectral dynamics of guided edge removals and identifying transient amplifiers for death–Birth updatingJournal of Mathematical Biology10.1007/s00285-023-01937-187:1Online publication date: 7-Jun-2023
https://doi.org/10.1007/s00285-023-01937-1
Wills PMeyer F(2020)Metrics for graph comparison: A practitioner’s guidePLOS ONE10.1371/journal.pone.022872815:2(e0228728)Online publication date: 12-Feb-2020
https://doi.org/10.1371/journal.pone.0228728

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents