冯诺依曼图熵（VNGE）Python实现及近似计算

简介

冯·诺依曼图熵（VNGE）有助于测量图序列中图之间的信息差异和距离。

给定第一个无向图 $G=(V, E, A)$ , 其中 $A$ 是对称的邻接矩阵。度矩阵定义为 $D=diag(d_1,...,d_n)$ ，则它的拉普拉斯矩阵为 $L=D-A$ 。其中后者的特征值 $\lambda_i$ 被称为拉普拉斯谱。这里， $H_{vn}(G)$ 为冯诺依曼图熵（von Neumann graph entropy）。

$H_{vn}(G)=-\sum \limits_{i=1}^{n}(\frac{\lambda_i}{vol(G)}\log\frac{\lambda_i}{vol(G)})$

图的容量为 $vol(G)=\sum_{i=1}^{n}\lambda_i=trace(L)$ 。时间复杂度较高，是 $O(n^3)$ 。

我提供了Python版本代码来计算VNGE。应该注意的是陈等人给出了一种称为FINGER [1]的近似方法，该方法将VNGE的三次复杂度降低为节点和边的数量的线性复杂度。

VNGE和FINGER的代码如下。

代码

# Name: VNGE
# Author: Reacubeth
# Time: 2021/1/25 16:01
# Mail: noverfitting@gmail.com
# Site: www.omegaxyz.com
# *_*coding:utf-8 *_*

import time
import numpy as np
from scipy.sparse.linalg.eigen.arpack import eigsh

def normalized_laplacian(adj_matrix):
    nodes_degree = np.sum(adj_matrix, axis=1)
    nodes_degree_sqrt = 1/np.sqrt(nodes_degree)
    degree_matrix = np.diag(nodes_degree_sqrt)
    eye_matrix = np.eye(adj_matrix.shape[0])
    return eye_matrix - degree_matrix * adj_matrix * degree_matrix

def unnormalized_laplacian(adj_matrix):
    nodes_degree = np.sum(adj_matrix, axis=1)
    degree_matrix = np.diag(nodes_degree)
    return degree_matrix - adj_matrix

def VNGE_exact(adj_matrix):
    start = time.time()
    nodes_degree = np.sum(adj_matrix, axis=1)
    c = 1.0 / np.sum(nodes_degree)
    laplacian_matrix = c * unnormalized_laplacian(adj_matrix)
    eigenvalues, _ = np.linalg.eig(laplacian_matrix)
    eigenvalues[eigenvalues &lt; 0] = 0
    pos = eigenvalues &gt; 0
    H_vn = - np.sum(eigenvalues[pos] * np.log2(eigenvalues[pos]))
    print('H_vn exact:', H_vn)
    print('Time:', time.time() - start)

def VNGE_FINGER(adj_matrix):
    start = time.time()
    nodes_degree = np.sum(adj_matrix, axis=1)
    c = 1.0 / np.sum(nodes_degree)
    edge_weights = 1.0 * adj_matrix[np.nonzero(adj_matrix)]
    approx = 1.0 - np.square(c) * (np.sum(np.square(nodes_degree)) + np.sum(np.square(edge_weights)))
    laplacian_matrix = unnormalized_laplacian(adj_matrix)
    '''
    eigenvalues, _ = np.linalg.eig(laplacian_matrix)
    eig_max = c * max(eigenvalues)
    '''
    eig_max, _ = eigsh(laplacian_matrix, 1, which='LM')
    eig_max = eig_max[0] * c
    H_vn = - approx * np.log2(eig_max)
    print('H_vn approx:', H_vn)
    print('Time:', time.time() - start)

nodes_num = 3000
sparsity = 0.01

tmp_m = np.random.uniform(0, 1, (nodes_num, nodes_num))
pos1 = tmp_m &gt; sparsity
pos2 = tmp_m &lt;= sparsity
tmp_m[pos1] = 0
tmp_m[pos2] = 1
tmp_m = np.triu(tmp_m)
adj_m = tmp_m + np.transpose(tmp_m)

VNGE_exact(adj_m)
VNGE_FINGER(adj_m)

# Name: VNGE

# Author: Reacubeth

# Time: 2021/1/25 16:01

# Mail: noverfitting@gmail.com

# Site: www.omegaxyz.com

# *_*coding:utf-8 *_*

import time

import numpy as np

from scipy.sparse.linalg.eigen.arpack import eigsh

def normalized_laplacian(adj_matrix):

nodes_degree = np.sum(adj_matrix, axis=1)

nodes_degree_sqrt = 1/np.sqrt(nodes_degree)

degree_matrix = np.diag(nodes_degree_sqrt)

eye_matrix = np.eye(adj_matrix.shape[0])

return eye_matrix - degree_matrix * adj_matrix * degree_matrix

def unnormalized_laplacian(adj_matrix):

nodes_degree = np.sum(adj_matrix, axis=1)

degree_matrix = np.diag(nodes_degree)

return degree_matrix - adj_matrix

def VNGE_exact(adj_matrix):

start = time.time()

nodes_degree = np.sum(adj_matrix, axis=1)

c = 1.0 / np.sum(nodes_degree)

laplacian_matrix = c * unnormalized_laplacian(adj_matrix)

eigenvalues, _ = np.linalg.eig(laplacian_matrix)

eigenvalues[eigenvalues < 0] = 0

pos = eigenvalues > 0

H_vn = - np.sum(eigenvalues[pos] * np.log2(eigenvalues[pos]))

print('H_vn exact:', H_vn)

print('Time:', time.time() - start)

def VNGE_FINGER(adj_matrix):

start = time.time()

nodes_degree = np.sum(adj_matrix, axis=1)

c = 1.0 / np.sum(nodes_degree)

edge_weights = 1.0 * adj_matrix[np.nonzero(adj_matrix)]

approx = 1.0 - np.square(c) * (np.sum(np.square(nodes_degree)) + np.sum(np.square(edge_weights)))

laplacian_matrix = unnormalized_laplacian(adj_matrix)

'''

eigenvalues, _ = np.linalg.eig(laplacian_matrix)

eig_max = c * max(eigenvalues)

'''

eig_max, _ = eigsh(laplacian_matrix, 1, which='LM')

eig_max = eig_max[0] * c

H_vn = - approx * np.log2(eig_max)

print('H_vn approx:', H_vn)

print('Time:', time.time() - start)

nodes_num = 3000

sparsity = 0.01

tmp_m = np.random.uniform(0, 1, (nodes_num, nodes_num))

pos1 = tmp_m > sparsity

pos2 = tmp_m <= sparsity

tmp_m[pos1] = 0

tmp_m[pos2] = 1

tmp_m = np.triu(tmp_m)

adj_m = tmp_m + np.transpose(tmp_m)

VNGE_exact(adj_m)

VNGE_FINGER(adj_m)

结果

H_vn exact: 11.496599468152386
Time: 13.172455072402954
H_vn approx: 10.63029083591871
Time: 0.23734617233276367

[1] Chen, Pin-Yu, et al. "Fast incremental von neumann graph entropy computation: Theory, algorithm, and applications." International Conference on Machine Learning. PMLR, 2019.

冯诺依曼图熵（VNGE）Python实现及近似计算

NLG文本评估任务或许并不需要真值或参考文本

大模型中的RepE表征工程

大模型也是一种优化器（LLM as Optimizer）

全栈开发与快速部署Demo

学术idea自动发现与生成

自回归语言模型（language model）Python实现

粉丝期待的三体电影宇宙（近四十部电影与电视剧集）

基于历史对比学习的时序知识图谱推理

泰拉瑞亚Terriaria快速部署Linux服务器

iPad生产力指南——编程

留下评论取消回复

简介

代码

结果

相关文章

留下评论取消回复