-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathgraph_stats.py
158 lines (126 loc) · 5.55 KB
/
graph_stats.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
import networkx as nx
import numpy as np
import pandas as pd
from torch_geometric.utils import to_networkx
from torch_geometric.datasets import (
CitationFull,
GNNBenchmarkDataset,
Coauthor,
Reddit2,
AttributedGraphDataset,
Amazon,
Planetoid,
KarateClub,
)
from ogb.nodeproppred import PygNodePropPredDataset
from sparsifiers.sparsifier_class import TreeSparsifier
import networkx as nx
import numpy as np
import time
def compute_graph_statistics(graph):
# Number of nodes and edges
num_nodes = graph.number_of_nodes()
num_edges = graph.number_of_edges()
# Degree sequence
degrees = [degree for node, degree in graph.degree()]
# Average degree and standard deviation
avg_degree = np.mean(degrees)
std_degree = np.std(degrees)
# 90th percentile degree
percentile_90_degree = np.percentile(degrees, 90)
percentile_95_degree = np.percentile(degrees, 95)
percentile_99_degree = np.percentile(degrees, 99)
percentile_999_degree = np.percentile(degrees, 99.9)
# Node with the highest degree
highest_degree_node = max(graph.degree(), key=lambda x: x[1])[0]
# Average clustering coefficient
avg_clustering_coeff = nx.average_clustering(graph)
# Diameter (only if the graph is connected; may be slow)
# diameter = nx.diameter(graph) if nx.is_connected(graph) else float('inf')
# # Average shortest path length (only if the graph is connected; may be slow)
# avg_shortest_path_length = nx.average_shortest_path_length(graph) if nx.is_connected(graph) else float('inf')
# # Assortativity
# assortativity = nx.degree_assortativity_coefficient(graph)
# # Degree centrality statistics
# degree_centrality = nx.degree_centrality(graph)
# max_degree_centrality = max(degree_centrality.values())
# min_degree_centrality = min(degree_centrality.values())
# median_degree_centrality = np.median(list(degree_centrality.values()))
# Return as a dictionary
return {
"num_nodes": num_nodes,
"num_edges": num_edges,
"avg_degree": avg_degree,
"std_degree": std_degree,
"90th_percentile_degree": percentile_90_degree,
"95th_percentile_degree": percentile_95_degree,
"99th_percentile_degree": percentile_99_degree,
"99.9th_percentile_degree": percentile_999_degree,
"highest_degree_node": highest_degree_node,
"avg_clustering_coeff": avg_clustering_coeff,
# "diameter": diameter, # Potentially slow
# "avg_shortest_path_length": avg_shortest_path_length, # Potentially slow
# "assortativity": assortativity,
# "max_degree_centrality": max_degree_centrality,
# "min_degree_centrality": min_degree_centrality,
# "median_degree_centrality": median_degree_centrality
}
datasets = [
Planetoid(root="dataset/", name="Cora"),
Amazon(root="dataset/", name="Photo"),
Amazon(root="dataset/", name="Computers"),
Planetoid(root="dataset/", name="Pubmed"),
Coauthor(root="dataset/", name="CS"),
Coauthor(root="dataset/", name="Physics"),
Planetoid(root="dataset/", name="CiteSeer"),
#PygNodePropPredDataset(name="ogbn-arxiv"),
AttributedGraphDataset(root="dataset/", name="BlogCatalog"),
]
from tqdm import tqdm
tree_function_names=["dfs", "pseudo_random_spanning_tree","low_degree_spanning_tree", "bfs"]
sampler_names=["low_degree", "random", "tree", "leverage",]
one_or_k=["k"]
nr_dividers=10
# List to store statistics for each dataset
stats_list = []
for dataset in datasets:
dataset_name = dataset.name
print(dataset_name)
data = dataset[0]
graph = to_networkx(data, to_undirected=True)
n = graph.number_of_nodes()
m = graph.number_of_edges()
min_number_of_edges = n - 1
remaining_edges = m - min_number_of_edges
extra_edges = [
min_number_of_edges + remaining_edges // i
for i in range(nr_dividers + 1, 1, -1)
]
for tree_func in tqdm(tree_function_names):
print(tree_func)
for sampler in sampler_names:
for k in one_or_k:
for i in tqdm(range(nr_dividers)):
for nr_extra_edges in extra_edges:
time_start = time.time()
sparsifier = TreeSparsifier(
graph,
tree_func,
k,
sampler,
nr_extra_edges,)
sparsifier.compute_sparsifier()
sparsifier.get_sparsifier()
graph_statistics = compute_graph_statistics(sparsifier.sparsified_graph)
time_end = time.time()
total_time = time_end - time_start
# Add dataset name to the statistics dictionary
graph_statistics["dataset_name"] = dataset_name
graph_statistics["tree_func"] = tree_func
graph_statistics["sampler"] = sampler
graph_statistics["nr_edges_sparsifier"] = sparsifier.sparsified_graph.number_of_edges()
graph_statistics["sparsification_time"] = total_time
stats_list.append(graph_statistics)
# Convert list of dictionaries to a DataFrame and save as CSV
stats_df = pd.DataFrame(stats_list)
stats_df.to_csv("graph_statistics_sparsifier.csv", index=False)