Network Density of States (NDOS)

This repository contains the experiments of the Network Density of States by Kun Dong, Austin Benson, David Bindel. This paper will be appearing at KDD 2019.

The bibliographic information for the paper will be updated once the proceeding is published.

@inproceedings{dong2019networkdos,
  title={Network Density of States},
  author={Dong, Kun and Benson, Austin R Bindel, David},
  booktitle={Proceedings of the 25th ACM SIGKDD International Conference on 
    Knowledge Discovery \& Data Mining},
  year={2019},
  organization={ACM}
}

Contents

1. Introduction
2. Setup
3. Usage
   1. Compute DOS/PDOS
   2. Motif Filtering
   3. Model Comparison: BTER
   4. Other Demos

Introduction

Spectral analysis connects graph structure to the eigenvalues and eigenvectors of associated matrices. Much of spectral graph theory has focused on results involving only a few extreme eigenvalues and their associated eigenvalues; The study of graphs through the overall distribution of eigenvalues --- spectral density --- is largely limited to simple random graph models; and the interior of the spectrum of real-world graphs remains largely unexplored, difficult to compute and to interpret.

In our paper, 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 are able to compute spectral densities for graphs with over a billion edges even on a single compute node.

Setup

Clone the repository.

For Matlab:

• If you would like to download the data used in our demos, check the data folder where we supply a shell script fetch.sh.
• run startup.m.

For Python,

• pyDOS is implemented in Python2. Demos are coming soon.

Usage

Compute DOS/PDOS

Our first demo is a simple computation of density of states (DOS) and pointwise density of states (PDOS). To run this experiment and produce the figure below, you can use the demo_dos and demo_ldos commands. By default, they use Kernel Polynomial Method (KPM) to compute 1000 Chebyshev moments with 20 probe vectors for the Erdős Collaboration Network.

• method: 'cheb'(default), 'lan', 'nd', 'exact'
• dname: Use one from RODGER dataset, or supply an adjacency matrix.

Note that 'exact' method uses full matrix-matrix multiplication, so it should be avoided on large networks. When 'lan' is used for PDOS, we only compute a subsample of 100 nodes.

For DOS, the blue bars are the exact count of eigenvalues in each bin, and the red dots are our approximation. The middle figure zooms in near the bottom. For PDOS, the y-axis represents the node index, the x-axis represents eigenvalues, and the colors indicate the heights of the spectral histogram.

Motif Filtering

In this demo, we demonstrate the effect of our motif filtering method. Use the code demo_HepTh to reproduce this experiment on the Arxiv High Energy Physics Theory Collaboration Network.

Local motifs in a network are associated with certain eigenvalues. As a result, frequent occurrence of these motifs leads to high multiplicities of some eigenvalues. We can observe this phenomenon as these spikes at λ=0, -1/2, -1/3, -1/4 in the spectral density of the normalized adjacency matrix. Consequently, we need to compute more moments due to those irregularities.

To overcome this issue, we detect common motifs by hashing the adjacency lists of nodes. Afterwards, we pre-compute a filter to project the random probe vectors onto the orthogonal complement of the eigenvectors corresponding to these spikes. Thus, we are able to improve the smoothness of the spectral density, and the convergence of the approximation. The figures below show the process where we sequentially apply filters at various locations.

(a) No Filter              (b) Filter at λ=0

(c) Filter at λ=-1/3             (d) Filter at λ=-1/2

(e) Filter at λ=-1/3             (f) Relative Error

Model Comparison: BTER

BTER model closely captures many properties of a graph, such as degree distribution, clustering coefficient, and distribution of eigenvalues of the adjacency matrix. We followed this guide to create a model for the Erdős collaboration network and compare its DOS/PDOS against the original. We find the construction process of BTER, particular its treatment of degree-one nodes, leads to an abundance of motifs absent in the original graph. Use the command demo_bter_comparison to run this demo.

(a) Erdős DOS              (b) BTER DOS

(c) Erdős PDOS              (d) BTER PDOS

Other demos

A few demos are coming in the near future. Thank you for your patience.