Entropic Spectral Learning in Large Scale Networks

Diego Granziol, Bin Xin Ru, Stefan Zohren, Xiaowen Dong, Michael A. Osborne, Stephen J. Roberts

TL;DR

This paper introduces a novel Maximum Entropy-based approach for learning the spectral density of large-scale graphs. This method accurately captures spectral moments, overcoming limitations of existing kernel smoothing techniques, and demonstrates superior performance in graph similarity and community detection tasks.

What Problem Does This Paper Address?

Analyzing large-scale networks (like social networks or the web) often involves understanding their structure through graph spectra, which are derived from the eigenvalues of graph matrices (adjacency or Laplacian). However, for massive graphs, computing the full spectrum via eigen-decomposition is computationally prohibitive. Existing methods rely on iterative approximations that match spectral moments but often use kernel smoothing to achieve a positive, continuous spectral density. The authors argue that this kernel smoothing process actually loses crucial moment information, leading to inaccurate representations. This loss of information hinders tasks like comparing graph similarity or identifying communities within networks. The core problem is the need for an efficient, accurate, and everywhere-positive approximation of the spectral density for large graphs that preserves essential moment information.

Methods

The paper proposes a Maximum Entropy (MaxEnt) approach to approximate the spectral density. The core idea is to find the probability distribution (the spectral density) that maximizes entropy subject to constraints imposed by the spectral moments. This method has several advantages:

  • Exact Moment Matching: Unlike kernel smoothing, MaxEnt directly matches the computed spectral moments, preserving this vital information.
  • Everywhere Positive: The resulting spectral density is guaranteed to be positive, which is a desirable property for probability distributions.
  • New Algorithm: The authors develop a computationally efficient algorithm (Algorithm 2 and 3) to learn the MaxEnt spectral density by optimizing the entropic functional and estimating spectral moments using stochastic trace estimation (Algorithm 1). This involves using random vectors to approximate matrix-vector products, making it scalable for large sparse matrices.
  • Analytic Forms: The MaxEnt framework allows for analytic derivations of differential entropy and KL divergences, useful for comparing spectra.

The paper contrasts this with the Lanczos algorithm, a standard iterative method for approximating spectra, which, when combined with kernel smoothing, is shown to lose moment information.

Datasets

The paper evaluates its method on a variety of datasets:

  • Synthetic Networks:
    • Erdős-Rényi (ER) random graphs
    • Barabási-Albert (BA) random graphs
    • Watts-Strogatz (WS) random graphs
    • Disconnected sub-graphs with varying sizes and cluster numbers.
  • Real-World Networks:
    • Orkut, YouTube, and Amazon social networks (from the SNAP dataset)
    • Email network (from the SNAP dataset)
    • Biological networks (3)
    • Citation networks (5)
    • Road networks (3)
    • DBLP, Amazon, and YouTube networks (large-scale datasets)
    • Net Science collaboration network

Key Insights and Ideas

  • Kernel Smoothing Loses Information: A critical insight is that the common practice of kernel smoothing to make spectral approximations positive actually discards valuable moment information, leading to biased estimates.
  • Moments are Informative: The paper strongly advocates for the importance of spectral moments, showing they faithfully represent the underlying stochastic process of a network.
  • MaxEnt as a Superior Approximation: The Maximum Entropy principle provides a principled way to construct a spectral density that exactly matches moments and is inherently positive, making it a more robust approximation than smoothed Dirac sums.
  • Scalability for Large Graphs: The use of stochastic trace estimation makes the MaxEnt approach computationally feasible for graphs with millions or billions of nodes, where eigen-decomposition is impossible.
  • Unifying Framework: The MaxEnt spectral density provides a consistent representation that can be used for diverse tasks like graph similarity comparison and community detection.

Key Results

  • Improved Graph Similarity: The MaxEnt spectral density allows for more meaningful comparisons of graph similarity, as demonstrated by lower divergences between networks generated from the same model compared to kernel-smoothed methods.
  • Accurate Community Detection: The proposed MaxEnt method significantly outperforms the Lanczos algorithm with kernel smoothing in estimating the number of clusters (communities) in both synthetic and real-world networks, especially for larger graphs and more clusters. For instance, in synthetic networks, MaxEnt consistently shows lower fractional errors.
  • Classification of Network Types: The method can effectively classify real-world networks based on their spectral similarity to synthetic graph models, correctly identifying the YouTube network as best modeled by the Barabási-Albert graph.
  • Insight into Network Structure: The spectral densities derived from MaxEnt reveal clear spectral gaps in certain large networks (DBLP, Amazon), indicating the presence of distinct clusters, while others (YouTube) show no such clear gap, suggesting a lack of strong community structure.

Limitations and Future Work

  • Choice of Moments: While the paper shows that increasing the number of moments generally improves accuracy, the optimal number of moments for specific tasks or network types is not definitively established and might require tuning.
  • Computational Cost: Although more efficient than eigen-decomposition, the MaxEnt approach still involves iterative computations, and its performance on extremely massive graphs might be a consideration.
  • Future Work: The authors suggest exploring the temporal evolution of real-world networks using their method and conducting a more complete analysis of how the number of moments affects network classification accuracy. They also mention the potential for this method in other applications beyond graph analysis.

Summary updated

Abstract

Graph spectra have been successfully used to classify network types, compute the similarity between graphs, and determine the number of communities in a network. For large graphs, where an eigen-decomposition is infeasible, iterative moment matched approximations to the spectra and kernel smoothing are typically used. We show that the underlying moment information is lost when using kernel smoothing. We further propose a spectral density approximation based on the method of Maximum Entropy, for which we develop a new algorithm. This method matches moments exactly and is everywhere positive. We demonstrate its effectiveness and superiority over existing approaches in learning graph spectra, via experiments on both synthetic networks, such as the Erd\H{o}s-R\'{e}nyi and Barab\'{a}si-Albert random graphs, and real-world networks, such as the social networks for Orkut, YouTube, and Amazon from the SNAP dataset.
BibTeX
@misc{granziol2018entropic,
  author = {Diego Granziol and Bin Xin Ru and Stefan Zohren and Xiaowen Dong and Michael A. Osborne and Stephen J. Roberts},
  title = {{Entropic Spectral Learning in Large Scale Networks}},
  year = {2018},
  eprint = {1804.06802},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1804.06802},
}
Figure