YuWang0103/LGGM-Text2Graph
1
1###############################################################################2#3# Adapted from https://github.com/lrjconan/GRAN/ which in turn is adapted from https://github.com/JiaxuanYou/graph-generation4#5###############################################################################6# import graph_tool.all as gt7##Navigate to the ./util/orca directory and compile orca.cpp8# g++ -O2 -std=c++11 -o orca orca.cpp9import os10import copy11import torch12import torch.nn as nn13import numpy as np14import networkx as nx15import subprocess as sp16import concurrent.futures17 18import pygsp as pg19import secrets20from string import ascii_uppercase, digits21from datetime import datetime22from scipy.linalg import eigvalsh23from scipy.stats import chi224from analysis.dist_helper import compute_mmd, gaussian_emd, gaussian, emd, gaussian_tv, disc25from torch_geometric.utils import to_networkx26import wandb27from collections import defaultdict28 29 30PRINT_TIME = False31__all__ = ['degree_stats', 'clustering_stats', 'orbit_stats_all', 'spectral_stats', 'eval_acc_lobster_graph']32 33 34def degree_worker(G):35 return np.array(nx.degree_histogram(G))36 37 38def degree_stats(graph_ref_list, graph_pred_list, is_parallel=True, compute_emd=False):39 ''' Compute the distance between the degree distributions of two unordered sets of graphs.40 Args:41 graph_ref_list, graph_target_list: two lists of networkx graphs to be evaluated42 '''43 sample_ref = []44 sample_pred = []45 # in case an empty graph is generated46 graph_pred_list_remove_empty = [47 G for G in graph_pred_list if not G.number_of_nodes() == 048 ]49 50 prev = datetime.now()51 if is_parallel:52 with concurrent.futures.ThreadPoolExecutor() as executor:53 for deg_hist in executor.map(degree_worker, graph_ref_list):54 sample_ref.append(deg_hist)55 with concurrent.futures.ThreadPoolExecutor() as executor:56 for deg_hist in executor.map(degree_worker, graph_pred_list_remove_empty):57 sample_pred.append(deg_hist)58 else:59 for i in range(len(graph_ref_list)):60 degree_temp = np.array(nx.degree_histogram(graph_ref_list[i]))61 sample_ref.append(degree_temp)62 for i in range(len(graph_pred_list_remove_empty)):63 degree_temp = np.array(64 nx.degree_histogram(graph_pred_list_remove_empty[i]))65 sample_pred.append(degree_temp)66 67 # mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=gaussian_emd)68 # mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=emd)69 if compute_emd:70 # EMD option uses the same computation as GraphRNN, the alternative is MMD as computed by GRAN71 # mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=emd)72 mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=gaussian_emd)73 else:74 mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=gaussian_tv)75 # mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=gaussian)76 77 elapsed = datetime.now() - prev78 if PRINT_TIME:79 print('Time computing degree mmd: ', elapsed)80 return mmd_dist81 82 83###############################################################################84 85def spectral_worker(G, n_eigvals=-1):86 # eigs = nx.laplacian_spectrum(G)87 try:88 eigs = eigvalsh(nx.normalized_laplacian_matrix(G).todense())89 except:90 eigs = np.zeros(G.number_of_nodes())91 if n_eigvals > 0:92 eigs = eigs[1:n_eigvals + 1]93 spectral_pmf, _ = np.histogram(eigs, bins=200, range=(-1e-5, 2), density=False)94 spectral_pmf = spectral_pmf / spectral_pmf.sum()95 return spectral_pmf96 97 98def get_spectral_pmf(eigs, max_eig):99 spectral_pmf, _ = np.histogram(np.clip(eigs, 0, max_eig), bins=200, range=(-1e-5, max_eig), density=False)100 spectral_pmf = spectral_pmf / spectral_pmf.sum()101 return spectral_pmf102 103 104def eigval_stats(eig_ref_list, eig_pred_list, max_eig=20, is_parallel=True, compute_emd=False):105 ''' Compute the distance between the degree distributions of two unordered sets of graphs.106 Args:107 graph_ref_list, graph_target_list: two lists of networkx graphs to be evaluated108 '''109 sample_ref = []110 sample_pred = []111 112 prev = datetime.now()113 if is_parallel:114 with concurrent.futures.ThreadPoolExecutor() as executor:115 for spectral_density in executor.map(get_spectral_pmf, eig_ref_list,116 [max_eig for i in range(len(eig_ref_list))]):117 sample_ref.append(spectral_density)118 with concurrent.futures.ThreadPoolExecutor() as executor:119 for spectral_density in executor.map(get_spectral_pmf, eig_pred_list,120 [max_eig for i in range(len(eig_ref_list))]):121 sample_pred.append(spectral_density)122 else:123 for i in range(len(eig_ref_list)):124 spectral_temp = get_spectral_pmf(eig_ref_list[i])125 sample_ref.append(spectral_temp)126 for i in range(len(eig_pred_list)):127 spectral_temp = get_spectral_pmf(eig_pred_list[i])128 sample_pred.append(spectral_temp)129 130 # mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=gaussian_emd)131 if compute_emd:132 mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=emd)133 else:134 mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=gaussian_tv)135 # mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=gaussian)136 137 elapsed = datetime.now() - prev138 if PRINT_TIME:139 print('Time computing eig mmd: ', elapsed)140 return mmd_dist141 142 143def eigh_worker(G):144 L = nx.normalized_laplacian_matrix(G).todense()145 try:146 eigvals, eigvecs = np.linalg.eigh(L)147 except:148 eigvals = np.zeros(L[0, :].shape)149 eigvecs = np.zeros(L.shape)150 return (eigvals, eigvecs)151 152 153def compute_list_eigh(graph_list, is_parallel=False):154 eigval_list = []155 eigvec_list = []156 if is_parallel:157 with concurrent.futures.ThreadPoolExecutor() as executor:158 for e_U in executor.map(eigh_worker, graph_list):159 eigval_list.append(e_U[0])160 eigvec_list.append(e_U[1])161 else:162 for i in range(len(graph_list)):163 e_U = eigh_worker(graph_list[i])164 eigval_list.append(e_U[0])165 eigvec_list.append(e_U[1])166 return eigval_list, eigvec_list167 168 169def get_spectral_filter_worker(eigvec, eigval, filters, bound=1.4):170 ges = filters.evaluate(eigval)171 linop = []172 for ge in ges:173 linop.append(eigvec @ np.diag(ge) @ eigvec.T)174 linop = np.array(linop)175 norm_filt = np.sum(linop ** 2, axis=2)176 hist_range = [0, bound]177 hist = np.array([np.histogram(x, range=hist_range, bins=100)[0] for x in norm_filt]) # NOTE: change number of bins178 return hist.flatten()179 180 181def spectral_filter_stats(eigvec_ref_list, eigval_ref_list, eigvec_pred_list, eigval_pred_list, is_parallel=False,182 compute_emd=False):183 ''' Compute the distance between the eigvector sets.184 Args:185 graph_ref_list, graph_target_list: two lists of networkx graphs to be evaluated186 '''187 prev = datetime.now()188 189 class DMG(object):190 """Dummy Normalized Graph"""191 lmax = 2192 193 n_filters = 12194 filters = pg.filters.Abspline(DMG, n_filters)195 bound = np.max(filters.evaluate(np.arange(0, 2, 0.01)))196 sample_ref = []197 sample_pred = []198 if is_parallel:199 with concurrent.futures.ThreadPoolExecutor() as executor:200 for spectral_density in executor.map(get_spectral_filter_worker, eigvec_ref_list, eigval_ref_list,201 [filters for i in range(len(eigval_ref_list))],202 [bound for i in range(len(eigval_ref_list))]):203 sample_ref.append(spectral_density)204 with concurrent.futures.ThreadPoolExecutor() as executor:205 for spectral_density in executor.map(get_spectral_filter_worker, eigvec_pred_list, eigval_pred_list,206 [filters for i in range(len(eigval_ref_list))],207 [bound for i in range(len(eigval_ref_list))]):208 sample_pred.append(spectral_density)209 else:210 for i in range(len(eigval_ref_list)):211 try:212 spectral_temp = get_spectral_filter_worker(eigvec_ref_list[i], eigval_ref_list[i], filters, bound)213 sample_ref.append(spectral_temp)214 except:215 pass216 for i in range(len(eigval_pred_list)):217 try:218 spectral_temp = get_spectral_filter_worker(eigvec_pred_list[i], eigval_pred_list[i], filters, bound)219 sample_pred.append(spectral_temp)220 except:221 pass222 223 if compute_emd:224 # EMD option uses the same computation as GraphRNN, the alternative is MMD as computed by GRAN225 # mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=emd)226 mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=gaussian_emd)227 else:228 mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=gaussian_tv)229 230 elapsed = datetime.now() - prev231 if PRINT_TIME:232 print('Time computing spectral filter stats: ', elapsed)233 return mmd_dist234 235 236def spectral_stats(graph_ref_list, graph_pred_list, is_parallel=True, n_eigvals=-1, compute_emd=False):237 ''' Compute the distance between the degree distributions of two unordered sets of graphs.238 Args:239 graph_ref_list, graph_target_list: two lists of networkx graphs to be evaluated240 '''241 sample_ref = []242 sample_pred = []243 # in case an empty graph is generated244 graph_pred_list_remove_empty = [245 G for G in graph_pred_list if not G.number_of_nodes() == 0246 ]247 248 prev = datetime.now()249 if is_parallel:250 with concurrent.futures.ThreadPoolExecutor() as executor:251 for spectral_density in executor.map(spectral_worker, graph_ref_list, [n_eigvals for i in graph_ref_list]):252 sample_ref.append(spectral_density)253 with concurrent.futures.ThreadPoolExecutor() as executor:254 for spectral_density in executor.map(spectral_worker, graph_pred_list_remove_empty,255 [n_eigvals for i in graph_ref_list]):256 sample_pred.append(spectral_density)257 else:258 for i in range(len(graph_ref_list)):259 spectral_temp = spectral_worker(graph_ref_list[i], n_eigvals)260 sample_ref.append(spectral_temp)261 for i in range(len(graph_pred_list_remove_empty)):262 spectral_temp = spectral_worker(graph_pred_list_remove_empty[i], n_eigvals)263 sample_pred.append(spectral_temp)264 265 # mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=gaussian_emd)266 # mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=emd)267 if compute_emd:268 # EMD option uses the same computation as GraphRNN, the alternative is MMD as computed by GRAN269 # mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=emd)270 mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=gaussian_emd)271 else:272 mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=gaussian_tv)273 # mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=gaussian)274 275 elapsed = datetime.now() - prev276 if PRINT_TIME:277 print('Time computing degree mmd: ', elapsed)278 return mmd_dist279 280 281###############################################################################282 283def clustering_worker(param):284 G, bins = param285 clustering_coeffs_list = list(nx.clustering(G).values())286 hist, _ = np.histogram(287 clustering_coeffs_list, bins=bins, range=(0.0, 1.0), density=False)288 return hist289 290 291def clustering_stats(graph_ref_list,292 graph_pred_list,293 bins=100,294 is_parallel=True, compute_emd=False):295 sample_ref = []296 sample_pred = []297 graph_pred_list_remove_empty = [298 G for G in graph_pred_list if not G.number_of_nodes() == 0299 ]300 301 prev = datetime.now()302 if is_parallel:303 with concurrent.futures.ThreadPoolExecutor() as executor:304 for clustering_hist in executor.map(clustering_worker,305 [(G, bins) for G in graph_ref_list]):306 sample_ref.append(clustering_hist)307 with concurrent.futures.ThreadPoolExecutor() as executor:308 for clustering_hist in executor.map(309 clustering_worker, [(G, bins) for G in graph_pred_list_remove_empty]):310 sample_pred.append(clustering_hist)311 312 # check non-zero elements in hist313 # total = 0314 # for i in range(len(sample_pred)):315 # nz = np.nonzero(sample_pred[i])[0].shape[0]316 # total += nz317 # print(total)318 else:319 for i in range(len(graph_ref_list)):320 clustering_coeffs_list = list(nx.clustering(graph_ref_list[i]).values())321 hist, _ = np.histogram(322 clustering_coeffs_list, bins=bins, range=(0.0, 1.0), density=False)323 sample_ref.append(hist)324 325 for i in range(len(graph_pred_list_remove_empty)):326 clustering_coeffs_list = list(327 nx.clustering(graph_pred_list_remove_empty[i]).values())328 hist, _ = np.histogram(329 clustering_coeffs_list, bins=bins, range=(0.0, 1.0), density=False)330 sample_pred.append(hist)331 332 if compute_emd:333 # EMD option uses the same computation as GraphRNN, the alternative is MMD as computed by GRAN334 # mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=emd, sigma=1.0 / 10)335 mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=gaussian_emd, sigma=1.0 / 10, distance_scaling=bins)336 else:337 mmd_dist = compute_mmd(sample_ref, sample_pred, kernel=gaussian_tv, sigma=1.0 / 10)338 339 elapsed = datetime.now() - prev340 if PRINT_TIME:341 print('Time computing clustering mmd: ', elapsed)342 return mmd_dist343 344 345# maps motif/orbit name string to its corresponding list of indices from orca output346motif_to_indices = {347 '3path': [1, 2],348 '4cycle': [8],349}350COUNT_START_STR = 'orbit counts:'351 352 353def edge_list_reindexed(G):354 idx = 0355 id2idx = dict()356 for u in G.nodes():357 id2idx[str(u)] = idx358 idx += 1359 360 edges = []361 for (u, v) in G.edges():362 edges.append((id2idx[str(u)], id2idx[str(v)]))363 return edges364 365 366def orca(graph):367 # tmp_fname = f'analysis/orca/tmp_{"".join(secrets.choice(ascii_uppercase + digits) for i in range(8))}.txt'368 tmp_fname = f'orca/tmp_{"".join(secrets.choice(ascii_uppercase + digits) for i in range(8))}.txt'369 tmp_fname = os.path.join(os.path.dirname(os.path.realpath(__file__)), tmp_fname)370 # print(tmp_fname, flush=True)371 f = open(tmp_fname, 'w')372 f.write(373 str(graph.number_of_nodes()) + ' ' + str(graph.number_of_edges()) + '\n')374 for (u, v) in edge_list_reindexed(graph):375 f.write(str(u) + ' ' + str(v) + '\n')376 f.close()377 output = sp.check_output(378 [str(os.path.join(os.path.dirname(os.path.realpath(__file__)), 'orca/orca')), 'node', '4', tmp_fname, 'std'])379 output = output.decode('utf8').strip()380 idx = output.find(COUNT_START_STR) + len(COUNT_START_STR) + 2381 output = output[idx:]382 node_orbit_counts = np.array([383 list(map(int,384 node_cnts.strip().split(' ')))385 for node_cnts in output.strip('\n').split('\n')386 ])387 388 try:389 os.remove(tmp_fname)390 except OSError:391 pass392 393 return node_orbit_counts394 395 396def motif_stats(graph_ref_list, graph_pred_list, motif_type='4cycle', ground_truth_match=None,397 bins=100, compute_emd=False):398 # graph motif counts (int for each graph)399 # normalized by graph size400 total_counts_ref = []401 total_counts_pred = []402 403 num_matches_ref = []404 num_matches_pred = []405 406 graph_pred_list_remove_empty = [G for G in graph_pred_list if not G.number_of_nodes() == 0]407 indices = motif_to_indices[motif_type]408 409 for G in graph_ref_list:410 orbit_counts = orca(G)411 motif_counts = np.sum(orbit_counts[:, indices], axis=1)412 413 if ground_truth_match is not None:414 match_cnt = 0415 for elem in motif_counts:416 if elem == ground_truth_match:417 match_cnt += 1418 num_matches_ref.append(match_cnt / G.number_of_nodes())419 420 # hist, _ = np.histogram(421 # motif_counts, bins=bins, density=False)422 motif_temp = np.sum(motif_counts) / G.number_of_nodes()423 total_counts_ref.append(motif_temp)424 425 for G in graph_pred_list_remove_empty:426 orbit_counts = orca(G)427 motif_counts = np.sum(orbit_counts[:, indices], axis=1)428 429 if ground_truth_match is not None:430 match_cnt = 0431 for elem in motif_counts:432 if elem == ground_truth_match:433 match_cnt += 1434 num_matches_pred.append(match_cnt / G.number_of_nodes())435 436 motif_temp = np.sum(motif_counts) / G.number_of_nodes()437 total_counts_pred.append(motif_temp)438 439 total_counts_ref = np.array(total_counts_ref)[:, None]440 total_counts_pred = np.array(total_counts_pred)[:, None]441 442 443 if compute_emd:444 # EMD option uses the same computation as GraphRNN, the alternative is MMD as computed by GRAN445 # mmd_dist = compute_mmd(total_counts_ref, total_counts_pred, kernel=emd, is_hist=False)446 mmd_dist = compute_mmd(total_counts_ref, total_counts_pred, kernel=gaussian, is_hist=False)447 else:448 mmd_dist = compute_mmd(total_counts_ref, total_counts_pred, kernel=gaussian, is_hist=False)449 return mmd_dist450 451 452def orbit_stats_all(graph_ref_list, graph_pred_list, compute_emd=False):453 total_counts_ref = []454 total_counts_pred = []455 456 graph_pred_list_remove_empty = [457 G for G in graph_pred_list if not G.number_of_nodes() == 0458 ]459 460 for G in graph_ref_list:461 orbit_counts = orca(G)462 orbit_counts_graph = np.sum(orbit_counts, axis=0) / G.number_of_nodes()463 total_counts_ref.append(orbit_counts_graph)464 465 for G in graph_pred_list:466 orbit_counts = orca(G)467 orbit_counts_graph = np.sum(orbit_counts, axis=0) / G.number_of_nodes()468 total_counts_pred.append(orbit_counts_graph)469 470 total_counts_ref = np.array(total_counts_ref)471 total_counts_pred = np.array(total_counts_pred)472 473 # mmd_dist = compute_mmd(474 # total_counts_ref,475 # total_counts_pred,476 # kernel=gaussian,477 # is_hist=False,478 # sigma=30.0)479 480 # mmd_dist = compute_mmd(481 # total_counts_ref,482 # total_counts_pred,483 # kernel=gaussian_tv,484 # is_hist=False,485 # sigma=30.0) 486 487 if compute_emd:488 # mmd_dist = compute_mmd(total_counts_ref, total_counts_pred, kernel=emd, sigma=30.0)489 # EMD option uses the same computation as GraphRNN, the alternative is MMD as computed by GRAN490 mmd_dist = compute_mmd(total_counts_ref, total_counts_pred, kernel=gaussian, is_hist=False, sigma=30.0)491 else:492 mmd_dist = compute_mmd(total_counts_ref, total_counts_pred, kernel=gaussian_tv, is_hist=False, sigma=30.0)493 return mmd_dist494 495 496def eval_acc_lobster_graph(G_list):497 G_list = [copy.deepcopy(gg) for gg in G_list]498 count = 0499 for gg in G_list:500 if is_lobster_graph(gg):501 count += 1502 return count / float(len(G_list))503 504 505def eval_acc_tree_graph(G_list):506 count = 0507 for gg in G_list:508 if nx.is_tree(gg):509 count += 1510 return count / float(len(G_list))511 512 513def eval_acc_grid_graph(G_list, grid_start=10, grid_end=20):514 count = 0515 for gg in G_list:516 if is_grid_graph(gg):517 count += 1518 return count / float(len(G_list))519 520 521def eval_acc_sbm_graph(G_list, p_intra=0.3, p_inter=0.005, strict=True, refinement_steps=1000, is_parallel=True):522 count = 0.0523 if is_parallel:524 with concurrent.futures.ThreadPoolExecutor() as executor:525 for prob in executor.map(is_sbm_graph,526 [gg for gg in G_list], [p_intra for i in range(len(G_list))],527 [p_inter for i in range(len(G_list))],528 [strict for i in range(len(G_list))],529 [refinement_steps for i in range(len(G_list))]):530 count += prob531 else:532 for gg in G_list:533 count += is_sbm_graph(gg, p_intra=p_intra, p_inter=p_inter, strict=strict,534 refinement_steps=refinement_steps)535 return count / float(len(G_list))536 537 538def eval_acc_planar_graph(G_list):539 count = 0540 for gg in G_list:541 if is_planar_graph(gg):542 count += 1543 return count / float(len(G_list))544 545 546def is_planar_graph(G):547 return nx.is_connected(G) and nx.check_planarity(G)[0]548 549 550def is_lobster_graph(G):551 """552 Check a given graph is a lobster graph or not553 554 Removing leaf nodes twice:555 556 lobster -> caterpillar -> path557 558 """559 ### Check if G is a tree560 if nx.is_tree(G):561 G = G.copy()562 ### Check if G is a path after removing leaves twice563 leaves = [n for n, d in G.degree() if d == 1]564 G.remove_nodes_from(leaves)565 566 leaves = [n for n, d in G.degree() if d == 1]567 G.remove_nodes_from(leaves)568 569 num_nodes = len(G.nodes())570 num_degree_one = [d for n, d in G.degree() if d == 1]571 num_degree_two = [d for n, d in G.degree() if d == 2]572 573 if sum(num_degree_one) == 2 and sum(num_degree_two) == 2 * (num_nodes - 2):574 return True575 elif sum(num_degree_one) == 0 and sum(num_degree_two) == 0:576 return True577 else:578 return False579 else:580 return False581 582 583def is_grid_graph(G):584 """585 Check if the graph is grid, by comparing with all the real grids with the same node count586 """587 all_grid_file = f"data/all_grids.pt"588 if os.path.isfile(all_grid_file):589 all_grids = torch.load(all_grid_file)590 else:591 all_grids = {}592 for i in range(2, 20):593 for j in range(2, 20):594 G_grid = nx.grid_2d_graph(i, j)595 n_nodes = f"{len(G_grid.nodes())}"596 all_grids[n_nodes] = all_grids.get(n_nodes, []) + [G_grid]597 torch.save(all_grids, all_grid_file)598 599 n_nodes = f"{len(G.nodes())}"600 if n_nodes in all_grids:601 for G_grid in all_grids[n_nodes]:602 if nx.faster_could_be_isomorphic(G, G_grid):603 if nx.is_isomorphic(G, G_grid):604 return True605 return False606 else:607 return False608 609 610# def is_sbm_graph(G, p_intra=0.3, p_inter=0.005, strict=True, refinement_steps=1000):611# """612# Check if how closely given graph matches a SBM with given probabilites by computing mean probability of Wald test statistic for each recovered parameter613# """614 615# adj = nx.adjacency_matrix(G).toarray()616# idx = adj.nonzero()617# g = gt.Graph()618# g.add_edge_list(np.transpose(idx))619# try:620# state = gt.minimize_blockmodel_dl(g)621# except ValueError:622# if strict:623# return False624# else:625# return 0.0626 627# # Refine using merge-split MCMC628# for i in range(refinement_steps):629# state.multiflip_mcmc_sweep(beta=np.inf, niter=10)630 631# b = state.get_blocks()632# b = gt.contiguous_map(state.get_blocks())633# state = state.copy(b=b)634# e = state.get_matrix()635# n_blocks = state.get_nonempty_B()636# node_counts = state.get_nr().get_array()[:n_blocks]637# edge_counts = e.todense()[:n_blocks, :n_blocks]638# if strict:639# if (node_counts > 40).sum() > 0 or (node_counts < 20).sum() > 0 or n_blocks > 5 or n_blocks < 2:640# return False641 642# max_intra_edges = node_counts * (node_counts - 1)643# est_p_intra = np.diagonal(edge_counts) / (max_intra_edges + 1e-6)644 645# max_inter_edges = node_counts.reshape((-1, 1)) @ node_counts.reshape((1, -1))646# np.fill_diagonal(edge_counts, 0)647# est_p_inter = edge_counts / (max_inter_edges + 1e-6)648 649# W_p_intra = (est_p_intra - p_intra) ** 2 / (est_p_intra * (1 - est_p_intra) + 1e-6)650# W_p_inter = (est_p_inter - p_inter) ** 2 / (est_p_inter * (1 - est_p_inter) + 1e-6)651 652# W = W_p_inter.copy()653# np.fill_diagonal(W, W_p_intra)654# p = 1 - chi2.cdf(abs(W), 1)655# p = p.mean()656# if strict:657# return p > 0.9 # p value < 10 %658# else:659# return p660 661 662def eval_fraction_isomorphic(fake_graphs, train_graphs):663 count = 0664 for fake_g in fake_graphs:665 for train_g in train_graphs:666 if nx.faster_could_be_isomorphic(fake_g, train_g):667 if nx.is_isomorphic(fake_g, train_g):668 count += 1669 break670 return count / float(len(fake_graphs))671 672 673def eval_fraction_unique(fake_graphs, precise=False):674 count_non_unique = 0675 fake_evaluated = []676 for fake_g in fake_graphs:677 unique = True678 if not fake_g.number_of_nodes() == 0:679 for fake_old in fake_evaluated:680 if precise:681 if nx.faster_could_be_isomorphic(fake_g, fake_old):682 if nx.is_isomorphic(fake_g, fake_old):683 count_non_unique += 1684 unique = False685 break686 else:687 if nx.faster_could_be_isomorphic(fake_g, fake_old):688 if nx.could_be_isomorphic(fake_g, fake_old):689 count_non_unique += 1690 unique = False691 break692 if unique:693 fake_evaluated.append(fake_g)694 695 frac_unique = (float(len(fake_graphs)) - count_non_unique) / float(696 len(fake_graphs)) # Fraction of distinct isomorphism classes in the fake graphs697 698 return frac_unique699 700 701def eval_fraction_unique_non_isomorphic_valid(fake_graphs, train_graphs, validity_func=(lambda x: True)):702 count_valid = 0703 count_isomorphic = 0704 count_non_unique = 0705 fake_evaluated = []706 for fake_g in fake_graphs:707 unique = True708 709 for fake_old in fake_evaluated:710 if nx.faster_could_be_isomorphic(fake_g, fake_old):711 if nx.is_isomorphic(fake_g, fake_old):712 count_non_unique += 1713 unique = False714 break715 if unique:716 fake_evaluated.append(fake_g)717 non_isomorphic = True718 for train_g in train_graphs:719 if nx.faster_could_be_isomorphic(fake_g, train_g):720 if nx.is_isomorphic(fake_g, train_g):721 count_isomorphic += 1722 non_isomorphic = False723 break724 if non_isomorphic:725 if validity_func(fake_g):726 count_valid += 1727 728 frac_unique = (float(len(fake_graphs)) - count_non_unique) / float(729 len(fake_graphs)) # Fraction of distinct isomorphism classes in the fake graphs730 frac_unique_non_isomorphic = (float(len(fake_graphs)) - count_non_unique - count_isomorphic) / float(731 len(fake_graphs)) # Fraction of distinct isomorphism classes in the fake graphs that are not in the training set732 frac_unique_non_isomorphic_valid = count_valid / float(733 len(fake_graphs)) # Fraction of distinct isomorphism classes in the fake graphs that are not in the training set and are valid734 return frac_unique, frac_unique_non_isomorphic, frac_unique_non_isomorphic_valid735 736 737class SpectreSamplingMetrics(nn.Module):738 def __init__(self, data_loaders, compute_emd, metrics_list):739 super().__init__()740 741 self.train_graphs = self.loader_to_nx(data_loaders['train'])742 self.val_graphs = self.loader_to_nx(data_loaders['val'])743 self.test_graphs = self.loader_to_nx(data_loaders['test'])744 self.num_graphs_test = len(self.test_graphs)745 self.num_graphs_val = len(self.val_graphs)746 self.compute_emd = compute_emd747 self.metrics_list = metrics_list748 749 def loader_to_nx(self, loader):750 networkx_graphs = []751 for i, batch in enumerate(loader):752 data_list = batch.to_data_list()753 for j, data in enumerate(data_list):754 networkx_graphs.append(to_networkx(data, node_attrs=None, edge_attrs=None, to_undirected=True,755 remove_self_loops=True))756 return networkx_graphs757 758 def forward(self, generated_graphs: list, local_rank, test=False):759 reference_graphs = self.test_graphs if test else self.val_graphs760 if local_rank == 0:761 print(f"Computing sampling metrics between {len(generated_graphs)} generated graphs and {len(reference_graphs)}"762 f" test graphs -- emd computation: {self.compute_emd}")763 networkx_graphs = []764 adjacency_matrices = []765 if local_rank == 0:766 print("Building networkx graphs...")767 for graph in generated_graphs:768 node_types, edge_types = graph769 A = edge_types.bool().cpu().numpy()770 adjacency_matrices.append(A)771 772 nx_graph = nx.from_numpy_array(A)773 networkx_graphs.append(nx_graph)774 775 np.savez('generated_adjs.npz', *adjacency_matrices)776 777 to_log = {}778 if 'degree' in self.metrics_list:779 if local_rank == 0:780 print("Computing degree stats..")781 degree = degree_stats(reference_graphs, networkx_graphs, is_parallel=True,782 compute_emd=self.compute_emd)783 784 to_log['degree'] = degree785 786 if wandb.run:787 wandb.run.summary['degree'] = degree788 789 # val_eigvals = [graph["eigval"][1:self.k + 1].cpu().detach().numpy() for graph in self.val]790 # train_eigvals = [graph["eigval"][1:self.k + 1].cpu().detach().numpy() for graph in self.train]791 792 # eigval_stats(eig_ref_list, eig_pred_list, max_eig=20, is_parallel=True, compute_emd=False)793 # spectral_filter_stats(eigvec_ref_list, eigval_ref_list, eigvec_pred_list, eigval_pred_list, is_parallel=False,794 # compute_emd=False) # This is the one called wavelet795 796 797 if 'spectre' in self.metrics_list:798 if local_rank == 0:799 print("Computing spectre stats...")800 spectre = spectral_stats(reference_graphs, networkx_graphs, is_parallel=True, n_eigvals=-1,801 compute_emd=self.compute_emd)802 803 to_log['spectre'] = spectre804 if wandb.run:805 wandb.run.summary['spectre'] = spectre806 807 if 'clustering' in self.metrics_list:808 if local_rank == 0:809 print("Computing clustering stats...")810 clustering = clustering_stats(reference_graphs, networkx_graphs, bins=100, is_parallel=True,811 compute_emd=self.compute_emd)812 to_log['clustering'] = clustering813 if wandb.run:814 wandb.run.summary['clustering'] = clustering815 816 if 'motif' in self.metrics_list:817 if local_rank == 0:818 print("Computing motif stats")819 motif = motif_stats(reference_graphs, networkx_graphs, motif_type='4cycle', ground_truth_match=None, bins=100,820 compute_emd=self.compute_emd)821 to_log['motif'] = motif822 if wandb.run:823 wandb.run.summary['motif'] = motif824 825 if 'orbit' in self.metrics_list:826 if local_rank == 0:827 print("Computing orbit stats...")828 orbit = orbit_stats_all(reference_graphs, networkx_graphs, compute_emd=self.compute_emd)829 to_log['orbit'] = orbit830 if wandb.run:831 wandb.run.summary['orbit'] = orbit832 833 if 'sbm' in self.metrics_list:834 if local_rank == 0:835 print("Computing accuracy...")836 acc = eval_acc_sbm_graph(networkx_graphs, refinement_steps=100, strict=True)837 to_log['sbm_acc'] = acc838 if wandb.run:839 wandb.run.summary['sbmacc'] = acc840 841 if 'planar' in self.metrics_list:842 if local_rank ==0:843 print('Computing planar accuracy...')844 planar_acc = eval_acc_planar_graph(networkx_graphs)845 to_log['planar_acc'] = planar_acc846 if wandb.run:847 wandb.run.summary['planar_acc'] = planar_acc848 849 if 'sbm' or 'planar' in self.metrics_list:850 if local_rank == 0:851 print("Computing all fractions...")852 frac_unique, frac_unique_non_isomorphic, fraction_unique_non_isomorphic_valid = eval_fraction_unique_non_isomorphic_valid(853 networkx_graphs, self.train_graphs, is_sbm_graph if 'sbm' in self.metrics_list else is_planar_graph)854 frac_non_isomorphic = 1.0 - eval_fraction_isomorphic(networkx_graphs, self.train_graphs)855 to_log.update({'sampling/frac_unique': frac_unique,856 'sampling/frac_unique_non_iso': frac_unique_non_isomorphic,857 'sampling/frac_unic_non_iso_valid': fraction_unique_non_isomorphic_valid,858 'sampling/frac_non_iso': frac_non_isomorphic})859 860 if local_rank == 0:861 print("Sampling statistics", to_log)862 if wandb.run:863 wandb.log(to_log, commit=False)864 865 def reset(self):866 pass867 868 869def loader_to_nx(loader):870 networkx_graphs = {}871 for i, batch in enumerate(loader):872 data_list = batch.to_data_list()873 for j, data in enumerate(data_list):874 networkx_graphs[data.prompt_id.squeeze(0).item()] = [to_networkx(data, node_attrs=None, edge_attrs=None, to_undirected=True, remove_self_loops=True)]875 876 return networkx_graphs877 878def compute_metrics(generated_graphs, referenced_graphs):879 networkx_graphs = defaultdict(list)880 adjacency_matrices = defaultdict(list)881 for key in generated_graphs:882 for graph in generated_graphs[key]:883 node_types, edge_types = graph884 A = edge_types.bool().cpu().numpy()885 nx_graph = nx.from_numpy_array(A)886 887 networkx_graphs[key].append(nx_graph)888 adjacency_matrices[key].append(A)889 890 new_referenced_graphs = []891 for key in referenced_graphs:892 new_referenced_graphs.extend(referenced_graphs[key])893 referenced_graphs = new_referenced_graphs894 895 nx_graphs = []896 for key in networkx_graphs:897 nx_graphs.extend(networkx_graphs[key])898 899 return nx_graphs 900 901 902 903 904class Comm20SamplingMetrics(SpectreSamplingMetrics):905 def __init__(self, data_loaders):906 super().__init__(data_loaders=data_loaders,907 compute_emd=True,908 metrics_list=['degree', 'clustering', 'orbit'])909 910 911class PlanarSamplingMetrics(SpectreSamplingMetrics):912 def __init__(self, data_loaders):913 super().__init__(data_loaders=data_loaders,914 compute_emd=False,915 metrics_list=['degree', 'clustering', 'orbit', 'spectre', 'planar'])916 917 918class SBMSamplingMetrics(SpectreSamplingMetrics):919 def __init__(self, data_loaders):920 super().__init__(data_loaders=data_loaders,921 compute_emd=False,922 metrics_list=['degree', 'clustering', 'orbit', 'spectre', 'sbm'])923 924class CrossDomainSamplingMetrics(SpectreSamplingMetrics):925 def __init__(self, data_loaders):926 super().__init__(data_loaders=data_loaders,927 compute_emd=False,928 metrics_list=['degree', 'clustering', 'orbit', 'spectre'])929