A Maximum Entropy approach to Massive Graph Spectra

Diego Granziol, Robin Ru, Stefan Zohren, Xiaowen Dong, Michael A. Osborne, Stephen J. RobertsarXiv 2019 · arXiv

Introduction

In network science, a graph’s spectrum—the set of eigenvalues of its adjacency or Laplacian matrix—serves as its structural DNA, revealing insights into connectivity, community structure, and network similarity. However, for a graph with $n$ nodes, calculating the exact spectrum requires $O(n^3)$ time, a prohibitive cost for modern networks with millions of nodes. While iterative methods like the Lanczos algorithm can estimate these spectra, they produce "spiky" distributions that typically require ad-hoc kernel smoothing (e.g., Gaussian kernels) for interpretation.

Researchers from the University of Oxford have identified a fundamental flaw in this standard practice: kernel smoothing is mathematically biased. They prove that smoothing systematically alters the moments of the spectral density, leading to inaccuracies in downstream tasks. To address this, they introduced the Entropic Graph Spectrum (EGS) learner, an information-theoretically optimal approach that scales linearly with the number of edges ($O(E)$).

Methodology: From Moments to Maximum Entropy

The EGS learner operates in two primary stages:

  1. Stochastic Trace Estimation (STE): Instead of direct eigenvalue computation, randomized techniques are used to estimate the moments of the spectral density. This process relies on matrix-vector multiplications, achieving high efficiency on massive graphs.
  2. Maximum Entropy (MaxEnt) Reconstruction: Rather than applying an arbitrary smoothing kernel, the Principle of Maximum Entropy is used to find the "flattest" distribution that matches the estimated moments.
Convergence of the MaxEnt estimate as the number of moments increases, shown via KL divergence.

This approach ensures the resulting density is the least biased estimate possible given the available information. Furthermore, the exponential form of the MaxEnt distribution allows for analytic expressions of KL divergence, enabling efficient graph comparison without expensive numerical integration.

Key Results and Visual Fidelity

The EGS method was evaluated against synthetic models (Erdős-Rényi, Watts-Strogatz, Barabási-Albert) and massive real-world datasets from the SNAP repository, including social networks like YouTube and infrastructure networks.

Visual Reconstruction

A significant advantage of EGS is its ability to capture the "bulk" of the spectral distribution much faster than traditional iterative methods. While Lanczos-based approaches often focus on extreme outliers first, EGS provides a coherent overall picture of the network's structure with relatively few iterations.

Progressive refinement of the spectral density estimate (EGS) as the number of moments (m) increases from 3 to 100.

Performance in Downstream Tasks

  • Graph Similarity: EGS successfully identified that the YouTube network's spectrum most closely resembles a scale-free Barabási-Albert model.
  • Clustering Accuracy: In estimating the number of connected components, EGS consistently outperformed the standard Lanczos + smoothing approach, particularly as network size and complexity increased.

Limitations and Future Outlook

Despite its strengths, the MaxEnt approach faces challenges with certain graph types. For instance, Barabási-Albert graphs often exhibit extremely sharp central peaks in their spectra, requiring a higher number of moments for a precise fit. Additionally, the lack of definitive "ground truth" for community structure in massive real-world datasets remains a hurdle for validation.

Future work may extend this framework to graph signal processing and the optimization of Graph Convolutional Networks (GCNs), leveraging the efficiency and mathematical rigor of the Maximum Entropy approach.

Summary updated

Abstract

Graph spectral techniques for measuring graph similarity, or for learning the cluster number, require kernel smoothing. The choice of kernel function and bandwidth are typically chosen in an ad-hoc manner and heavily affect the resulting output. We prove that kernel smoothing biases the moments of the spectral density. We propose an information theoretically optimal approach to learn a smooth graph spectral density, which fully respects the moment information. Our method's computational cost is linear in the number of edges, and hence can be applied to large networks, with millions of nodes. We apply our method to the problems to graph similarity and cluster number learning, where we outperform comparable iterative spectral approaches on synthetic and real graphs.
BibTeX
@misc{granziol2019maximum,
  author = {Diego Granziol and Robin Ru and Stefan Zohren and Xiaowen Dong and Michael A. Osborne and Stephen J. Roberts},
  title = {{A Maximum Entropy approach to Massive Graph Spectra}},
  year = {2019},
  eprint = {1912.09068},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1912.09068},
}
Figure