Network Density of States

Kun Dong, Austin R. Benson, David Bindel

TL;DR

This paper moves beyond looking at just the "extremes" of a graph's spectrum (like the largest eigenvalues) to analyze the Network Density of States (DOS)—the full distribution of eigenvalues. By adapting tools from condensed matter physics and introducing a novel "motif filtering" technique, the authors provide a highly scalable framework that can generate visual "fingerprints" for graphs with billions of edges on a single compute node.

What Problem Does This Paper Address?

In spectral graph theory, we usually focus on the "edges" of the spectrum: the largest eigenvalue (related to node centrality) or the second-smallest (related to how easily a graph can be partitioned). However, these extreme values only tell a fraction of the story. The "interior" of the spectrum—the vast majority of the eigenvalues—contains deep information about a network's structure, such as the prevalence of specific motifs like triangles or dangling nodes.

The problem is that computing the full set of eigenvalues for a large graph is computationally ruinous, scaling at $O(N^3)$. Consequently, researchers have largely ignored the global spectral distribution for real-world networks. This paper aims to bridge that gap by providing efficient, scalable algorithms to estimate the DOS and the Pointwise Density of States (PDOS), which gives spectral information localized to specific nodes.

Methods

The authors leverage and adapt two primary techniques from physics, plus a novel graph-specific optimization:

  1. Kernel Polynomial Method (KPM): This approximates the spectral density using an expansion of Chebyshev polynomials. To avoid the $O(N^3)$ cost, it uses stochastic trace estimation, which allows the authors to estimate the "trace" of the matrix polynomials using only a few random "probe" vectors and fast matrix-vector multiplications.
  2. Gauss Quadrature via Lanczos (GQL): An alternative approach that uses the Lanczos iteration to approximate the spectral density. It is particularly effective for smooth functions of the spectrum.
  3. Nested Dissection (ND): A divide-and-conquer method used to compute the PDOS (local information) more accurately for specific sets of nodes by exploiting the graph's separator structure.
  4. Motif Filtering (The "Secret Sauce"): Real-world graphs often have "spikes" in their spectrum caused by common local symmetries (e.g., two nodes sharing the exact same neighbors). These spikes make polynomial approximation difficult. The authors introduce a randomized hashing technique to identify these motifs and "filter" them out, allowing the algorithms to focus on the smoother, remaining part of the spectrum for much higher accuracy.

Datasets

The authors evaluated their methods on a massive variety of networks (20+ datasets):

  • Social & Collaboration: Facebook, Gplus, Twitter, LiveJournal, Friendster (1.8 billion edges), Orkut, and the Erdős and HepTh collaboration networks.
  • Infrastructure: Minnesota and California road networks.
  • Biological & Others: A Megascale Cell-Cell similarity network (Neuron), Amazon product networks, and even a Harry Potter character network.
  • Synthetic Models: Scale-free, small-world, and Block Two-Level Erdős-Rényi (BTER) models for verification.

Key Insights and Ideas

  • Spectral Fingerprinting: The DOS acts as a unique visual signature. For example, road networks have a very different "shape" than social networks, reflecting their underlying physical constraints versus preferential attachment growth.
  • Spikes = Symmetry: High-multiplicity eigenvalues (spikes) are almost always tied to local graph motifs. Identifying these isn't just a computational trick; it reveals the "building blocks" of the network.
  • Hearing the Shape of a Graph: Borrowing from Mark Kac’s famous question, "Can one hear the shape of a drum?", the authors show that while you can't perfectly reconstruct a graph from its spectrum alone, the DOS provides enough information to distinguish between different generative models (like BTER vs. Erdős-Rényi) in ways that simple statistics cannot.
  • Scalability: Because the core operations are matrix-vector multiplications, the method is embarrassingly parallel and memory-efficient.

Key Results

  • Massive Scale: The authors successfully computed the spectral density of the Friendster network (65M nodes, 1.8B edges). Each Chebyshev moment took about 1000 seconds on a single node, meaning a rough approximation of the entire spectrum is achievable in less than a day.
  • Accuracy Boost: Motif filtering significantly reduced the relative error of the spectral histograms. For the HepTh network, filtering out just a few common motifs dropped the approximation error by nearly half.
  • Model Verification: The authors used DOS to show that the BTER model, while good, often over-represents certain motifs (like isolated edges) compared to the real-world collaboration networks it's meant to mimic.

Limitations and Future Work

  • Nested Dissection Constraints: The ND method for local spectral density relies on the graph having small "separators." While common in many real-world networks, it might struggle with extremely dense or expander-like graphs.
  • Interpretation: While the "spikes" are well-understood, the meaning of the "valleys" or the specific curvature of the smooth parts of the DOS in a social context is still an open area for research.
  • Directed Graphs: While the paper mentions extensions to directed graphs via singular values, the primary focus and results are on symmetric (undirected) matrices. Applying this to massive directed web crawls remains a promising future direction.

Summary updated

Abstract

Spectral analysis connects graph structure to the eigenvalues and eigenvectors of associated matrices. Much of spectral graph theory descends directly from spectral geometry, the study of differentiable manifolds through the spectra of associated differential operators. But the translation from spectral geometry to spectral graph theory has largely focused on results involving only a few extreme eigenvalues and their associated eigenvalues. Unlike in geometry, the study of graphs through the overall distribution of eigenvalues --- the \em spectral density --- is largely limited to simple random graph models. The interior of the spectrum of real-world graphs remains largely unexplored, difficult to compute and to interpret. In this paper, we delve into the heart of spectral densities of real-world graphs. We borrow tools developed in condensed matter physics, and add novel adaptations to handle the spectral signatures of common graph motifs. The resulting methods are highly efficient, as we illustrate by computing spectral densities for graphs with over a billion edges on a single compute node. Beyond providing visually compelling fingerprints of graphs, we show how the estimation of spectral densities facilitates the computation of many common centrality measures, and use spectral densities to estimate meaningful information about graph structure that cannot be inferred from the extremal eigenpairs alone.
BibTeX
@inproceedings{dong2019network,
  author = {Kun Dong and Austin R. Benson and David Bindel},
  title = {{Network Density of States}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2019},
  url = {https://openreview.net/forum?id=IemHLKQ58W},
}

Loading related content...

Figure