EAGL: Learning and Summarizing Graphical Models using Eigen Analysis of Graph Laplacian

Summarizing Graphical Models using Eigen Analysis of Graph Laplacian (Steps)

Figure: Proposed EAGL Algorithm for summarizing a directed probabilistic graphical model based an available dataset.

Using the code:

A Jupyter notebook named "Example_GraphSummarization.ipynb" is provided for step by step guide to use the "EAGL" library for summarizing graphs. For the using the code directly from python IDE please use the file "Example_GraphSummarization.py" provided in the " Code " folder.

An implementation of Graph Laplacian for Directed Graphs can be found here. This was coded in Matlab. For a python implementation please check the NetworkX library.

Enter the following when prompt to reproduce the results:

Setup 1: Single edge reduction (Method='False')

• Enter if tree connection to be maintained (True or False): True
• Enter Tree Extraction method (dfs or bfs): bfs
• Enter Traversing Start Node(0 to 9): 0
• Enter Number of Iterations: 20
• Enter for which Eigenvalue (1st or 2nd) perform the calculation: 2

This will result in:

Number of Edges on the Updated DAG: 30

Compression: 40.0 %

Figure: Summarizing the Barabasi Albert Graph.

Setup 2: Multiple edge reduction (Method='True')

• Enter if tree connection to be maintained (True or False): True
• Enter Tree Extraction method (dfs or bfs): dfs
• Enter Traversing Start Node(0 to 9):0
• Enter Number of Iterations: 10
• Enter for which Eigenvalue (1st or 2nd) perform the calculation: 2
• Enter Cut-off Value: 0.05

This will result in:

Number of Edges on the Updated DAG: 38

Compression: 24.0 %

Figure: Summarizing the Barabasi Albert Graph.

Dependecies

• Scipy
• Numpy
• Networkx
• Matplotlib

*The code was tested using Python 3.6