⬅ datasets/gsn/utils_graph_processing.py source

1 import torch
2 import numpy as np
  • F401 'torch_geometric.utils.remove_self_loops' imported but unused
3 from torch_geometric.utils import remove_self_loops, to_undirected
4 import networkx as nx
5  
6 try:
7 import graph_tool as gt
8 import graph_tool.topology as gt_topology
  • F841 Local variable 'e' is assigned to but never used
9 except Exception as e:
10 pass
11  
12  
13 def automorphism_orbits(edge_list, print_msgs=True, **kwargs):
  • W293 Blank line contains whitespace
14
  • E266 Too many leading '#' for block comment
  • W291 Trailing whitespace
15 ##### vertex automorphism orbits #####
16  
  • E225 Missing whitespace around operator
17 directed=kwargs['directed'] if 'directed' in kwargs else False
  • W293 Blank line contains whitespace
18
19 graph = gt.Graph(directed=directed)
20 graph.add_edge_list(edge_list)
21 gt.stats.remove_self_loops(graph)
22 gt.stats.remove_parallel_edges(graph)
23  
24 # compute the vertex automorphism group
  • E501 Line too long (109 > 79 characters)
25 aut_group = gt_topology.subgraph_isomorphism(graph, graph, induced=False, subgraph=True, generator=False)
26  
27 orbit_membership = {}
28 for v in graph.get_vertices():
29 orbit_membership[v] = v
  • W293 Blank line contains whitespace
30
  • E501 Line too long (94 > 79 characters)
31 # whenever two nodes can be mapped via some automorphism, they are assigned the same orbit
32 for aut in aut_group:
33 for original, vertex in enumerate(aut):
34 role = min(original, orbit_membership[vertex])
35 orbit_membership[vertex] = role
  • W293 Blank line contains whitespace
36
  • E231 Missing whitespace after ','
37 orbit_membership_list = [[],[]]
38 for vertex, om_curr in orbit_membership.items():
39 orbit_membership_list[0].append(vertex)
40 orbit_membership_list[1].append(om_curr)
41  
42 # make orbit list contiguous (i.e. 0,1,2,...O)
  • E501 Line too long (95 > 79 characters)
  • E251 Unexpected spaces around keyword / parameter equals (in 2 places)
43 _, contiguous_orbit_membership = np.unique(orbit_membership_list[1], return_inverse = True)
44  
  • E231 Missing whitespace after ','
  • E501 Line too long (115 > 79 characters)
45 orbit_membership = {vertex: contiguous_orbit_membership[i] for i,vertex in enumerate(orbit_membership_list[0])}
46  
47  
  • E303 Too many blank lines (2)
48 orbit_partition = {}
49 for vertex, orbit in orbit_membership.items():
  • E501 Line too long (110 > 79 characters)
50 orbit_partition[orbit] = [vertex] if orbit not in orbit_partition else orbit_partition[orbit]+[vertex]
  • W293 Blank line contains whitespace
51
52 aut_count = len(aut_group)
  • W293 Blank line contains whitespace
53
54 if print_msgs:
  • E501 Line too long (82 > 79 characters)
  • W291 Trailing whitespace
55 print('Orbit partition of given substructure: {}'.format(orbit_partition))
  • E702 Multiple statements on one line (semicolon)
  • E231 Missing whitespace after ';'
56 import pdb;pdb.set_trace()
57 print('Number of orbits: {}'.format(len(orbit_partition)))
58 print('Automorphism count: {}'.format(aut_count))
59  
60 return graph, orbit_partition, orbit_membership, aut_count
61  
  • E302 Expected 2 blank lines, found 1
62 def induced_edge_automorphism_orbits(edge_list, **kwargs):
  • W293 Blank line contains whitespace
63
  • E266 Too many leading '#' for block comment
  • E501 Line too long (93 > 79 characters)
64 ##### induced edge automorphism orbits (according to the vertex automorphism group) #####
  • W293 Blank line contains whitespace
65
  • E225 Missing whitespace around operator
66 directed=kwargs['directed'] if 'directed' in kwargs else False
  • E225 Missing whitespace around operator
  • E501 Line too long (87 > 79 characters)
67 directed_orbits=kwargs['directed_orbits'] if 'directed_orbits' in kwargs else False
68  
  • E501 Line too long (98 > 79 characters)
69 graph, orbit_partition, orbit_membership, aut_count = automorphism_orbits(edge_list=edge_list,
  • E501 Line too long (96 > 79 characters)
70 directed=directed,
  • E501 Line too long (95 > 79 characters)
71 print_msgs=False)
72 edge_orbit_partition = dict()
73 edge_orbit_membership = dict()
74 edge_orbits2inds = dict()
75 ind = 0
76  
  • W293 Blank line contains whitespace
77
  • E303 Too many blank lines (2)
78 if not directed:
  • E231 Missing whitespace after ',' (in 2 places)
  • E501 Line too long (105 > 79 characters)
79 edge_list = to_undirected(torch.tensor(graph.get_edges()).transpose(1,0)).transpose(1,0).tolist()
80  
81 # infer edge automorphisms from the vertex automorphisms
  • E231 Missing whitespace after ','
82 for i,edge in enumerate(edge_list):
83 if directed_orbits:
84 edge_orbit = (orbit_membership[edge[0]], orbit_membership[edge[1]])
85 else:
  • E501 Line too long (90 > 79 characters)
86 edge_orbit = frozenset([orbit_membership[edge[0]], orbit_membership[edge[1]]])
87 if edge_orbit not in edge_orbits2inds:
88 edge_orbits2inds[edge_orbit] = ind
89 ind_edge_orbit = ind
90 ind += 1
91 else:
92 ind_edge_orbit = edge_orbits2inds[edge_orbit]
93  
94 if ind_edge_orbit not in edge_orbit_partition:
95 edge_orbit_partition[ind_edge_orbit] = [tuple(edge)]
96 else:
  • W291 Trailing whitespace
97 edge_orbit_partition[ind_edge_orbit] += [tuple(edge)]
98  
99 edge_orbit_membership[i] = ind_edge_orbit
100  
  • E501 Line too long (88 > 79 characters)
  • W291 Trailing whitespace
101 print('Edge orbit partition of given substructure: {}'.format(edge_orbit_partition))
102 print('Number of edge orbits: {}'.format(len(edge_orbit_partition)))
103 print('Graph (vertex) automorphism count: {}'.format(aut_count))
  • W293 Blank line contains whitespace
104
105 return graph, edge_orbit_partition, edge_orbit_membership, aut_count
106  
107  
108 def subgraph_isomorphism_vertex_counts(edge_index, **kwargs):
  • W293 Blank line contains whitespace
109
  • E266 Too many leading '#' for block comment
110 ##### vertex structural identifiers #####
  • W293 Blank line contains whitespace
111
  • E501 Line too long (103 > 79 characters)
112 subgraph_dict, induced, num_nodes = kwargs['subgraph_dict'], kwargs['induced'], kwargs['num_nodes']
113 directed = kwargs['directed'] if 'directed' in kwargs else False
  • W293 Blank line contains whitespace
114
115 G_gt = gt.Graph(directed=directed)
  • E231 Missing whitespace after ','
116 G_gt.add_edge_list(list(edge_index.transpose(1,0).cpu().numpy()))
117 gt.stats.remove_self_loops(G_gt)
  • W291 Trailing whitespace
118 gt.stats.remove_parallel_edges(G_gt)
  • W293 Blank line contains whitespace
119
120 # compute all subgraph isomorphisms
  • E501 Line too long (127 > 79 characters)
121 sub_iso = gt_topology.subgraph_isomorphism(subgraph_dict['subgraph'], G_gt, induced=induced, subgraph=True, generator=True)
  • W293 Blank line contains whitespace
122
  • E266 Too many leading '#' for block comment
  • W291 Trailing whitespace
123 ## num_nodes should be explicitly set for the following edge case:
  • E266 Too many leading '#' for block comment
124 ## when there is an isolated vertex whose index is larger
  • E266 Too many leading '#' for block comment
125 ## than the maximum available index in the edge_index
  • W293 Blank line contains whitespace
126
127 counts = np.zeros((num_nodes, len(subgraph_dict['orbit_partition'])))
128 for sub_iso_curr in sub_iso:
  • E231 Missing whitespace after ','
129 for i,node in enumerate(sub_iso_curr):
130 # increase the count for each orbit
  • E225 Missing whitespace around operator
131 counts[node, subgraph_dict['orbit_membership'][i]] +=1
132 counts = counts/subgraph_dict['aut_count']
  • W293 Blank line contains whitespace
133
134 counts = torch.tensor(counts)
  • W293 Blank line contains whitespace
135
136 return counts
137  
138  
139 def subgraph_isomorphism_edge_counts(edge_index, **kwargs):
  • W293 Blank line contains whitespace
140
  • E266 Too many leading '#' for block comment
141 ##### edge structural identifiers #####
  • W293 Blank line contains whitespace
142
143 subgraph_dict, induced = kwargs['subgraph_dict'], kwargs['induced']
144 directed = kwargs['directed'] if 'directed' in kwargs else False
  • W293 Blank line contains whitespace
145
  • E231 Missing whitespace after ','
146 edge_index = edge_index.transpose(1,0).cpu().numpy()
147 edge_dict = {}
  • W291 Trailing whitespace
148 for i, edge in enumerate(edge_index):
149 edge_dict[tuple(edge)] = i
  • W293 Blank line contains whitespace
150
151 if not directed:
  • E501 Line too long (139 > 79 characters)
  • E231 Missing whitespace after ',' (in 2 places)
152 subgraph_edges = to_undirected(torch.tensor(subgraph_dict['subgraph'].get_edges().tolist()).transpose(1,0)).transpose(1,0).tolist()
153  
  • W293 Blank line contains whitespace
154
  • E303 Too many blank lines (2)
155 G_gt = gt.Graph(directed=directed)
156 G_gt.add_edge_list(list(edge_index))
157 gt.stats.remove_self_loops(G_gt)
  • W291 Trailing whitespace
158 gt.stats.remove_parallel_edges(G_gt)
  • W293 Blank line contains whitespace
159
160 # compute all subgraph isomorphisms
  • E501 Line too long (127 > 79 characters)
161 sub_iso = gt_topology.subgraph_isomorphism(subgraph_dict['subgraph'], G_gt, induced=induced, subgraph=True, generator=True)
  • W293 Blank line contains whitespace
162
  • W293 Blank line contains whitespace
163
  • E303 Too many blank lines (2)
  • E501 Line too long (83 > 79 characters)
164 counts = np.zeros((edge_index.shape[0], len(subgraph_dict['orbit_partition'])))
  • W293 Blank line contains whitespace
165
166 for sub_iso_curr in sub_iso:
167 mapping = sub_iso_curr.get_array()
168 # import pdb;pdb.set_trace()
  • E231 Missing whitespace after ','
  • W291 Trailing whitespace
169 for i,edge in enumerate(subgraph_edges):
  • W293 Blank line contains whitespace
170
  • E501 Line too long (100 > 79 characters)
171 # for every edge in the graph H, find the edge in the subgraph G_S to which it is mapped
  • W291 Trailing whitespace
172 # (by finding where its endpoints are matched).
  • E501 Line too long (89 > 79 characters)
173 # Then, increase the count of the matched edge w.r.t. the corresponding orbit
174 # Repeat for the reverse edge (the one with the opposite direction)
  • W293 Blank line contains whitespace
175
176 edge_orbit = subgraph_dict['orbit_membership'][i]
177 mapped_edge = tuple([mapping[edge[0]], mapping[edge[1]]])
178 counts[edge_dict[mapped_edge], edge_orbit] += 1
  • W293 Blank line contains whitespace
179
  • W293 Blank line contains whitespace
180
  • E303 Too many blank lines (2)
181 counts = counts/subgraph_dict['aut_count']
  • W293 Blank line contains whitespace
182
183 counts = torch.tensor(counts)
  • W293 Blank line contains whitespace
184
185 return counts
186  
  • W293 Blank line contains whitespace
187
  • W293 Blank line contains whitespace
188
  • W293 Blank line contains whitespace
189
  • W293 Blank line contains whitespace
190
  • E303 Too many blank lines (5)
  • E265 Block comment should start with '# '
191 #----------------------- line graph edge automorphism: deprecated
  • W293 Blank line contains whitespace
192
193  
194  
  • E303 Too many blank lines (3)
195 def edge_automorphism_orbits(edge_list, **kwargs):
  • W293 Blank line contains whitespace
196
  • E266 Too many leading '#' for block comment
197 ##### edge automorphism orbits according to the line graph #####
  • W293 Blank line contains whitespace
198
  • E225 Missing whitespace around operator
199 directed=kwargs['directed'] if 'directed' in kwargs else False
200  
201 graph_nx = nx.from_edgelist(edge_list)
202 graph = gt.Graph(directed=directed)
203 graph.add_edge_list(edge_list)
204 gt.stats.remove_self_loops(graph)
205 gt.stats.remove_parallel_edges(graph)
  • E501 Line too long (109 > 79 characters)
206 aut_group = gt_topology.subgraph_isomorphism(graph, graph, induced=False, subgraph=True, generator=False)
207 aut_count = len(aut_group)
  • W293 Blank line contains whitespace
208
  • E266 Too many leading '#' for block comment
209 ##### compute line graph vertex automorphism orbits #####
210  
211 graph_nx_line = nx.line_graph(graph_nx)
  • E231 Missing whitespace after ','
212 mapping = {node: i for i,node in enumerate(graph_nx_line.nodes)}
  • E231 Missing whitespace after ','
213 inverse_mapping = {i: node for i,node in enumerate(graph_nx_line.nodes)}
214  
215 graph_nx_line = nx.relabel_nodes(graph_nx_line, mapping)
216 line_graph = gt.Graph(directed=directed)
217 line_graph.add_edge_list(list(graph_nx_line.edges))
218  
219 gt.stats.remove_self_loops(line_graph)
  • W291 Trailing whitespace
220 gt.stats.remove_parallel_edges(line_graph)
221  
  • E501 Line too long (125 > 79 characters)
222 aut_group_edges = gt_topology.subgraph_isomorphism(line_graph, line_graph, induced=False, subgraph=True, generator=False)
223  
224 orbit_membership = {}
225 for v in line_graph.get_vertices():
226 orbit_membership[v] = v
227  
228 for aut in aut_group_edges:
229 for original, vertex in enumerate(aut):
230 role = min(original, orbit_membership[vertex])
231 orbit_membership[vertex] = role
232  
  • E231 Missing whitespace after ','
233 orbit_membership_list = [[],[]]
234 for vertex, om_curr in orbit_membership.items():
235 orbit_membership_list[0].append(vertex)
236 orbit_membership_list[1].append(om_curr)
237  
  • E501 Line too long (95 > 79 characters)
  • E251 Unexpected spaces around keyword / parameter equals (in 2 places)
238 _, contiguous_orbit_membership = np.unique(orbit_membership_list[1], return_inverse = True)
239  
  • E231 Missing whitespace after ','
  • E501 Line too long (115 > 79 characters)
240 orbit_membership = {vertex: contiguous_orbit_membership[i] for i,vertex in enumerate(orbit_membership_list[0])}
241  
  • E225 Missing whitespace around operator
242 orbit_partition= {}
243 for vertex, orbit in orbit_membership.items():
  • E501 Line too long (144 > 79 characters)
  • W291 Trailing whitespace
244 orbit_partition[orbit] = [inverse_mapping[vertex]] if orbit not in orbit_partition else orbit_partition[orbit]+[inverse_mapping[vertex]]
245  
  • E266 Too many leading '#' for block comment
  • E501 Line too long (80 > 79 characters)
246 ##### transfer line graph vertex automorphism orbits to original edges #####
247  
248 orbit_membership_new = {}
  • E231 Missing whitespace after ','
  • W291 Trailing whitespace
249 for i,edge in enumerate(graph.get_edges()):
  • E501 Line too long (107 > 79 characters)
  • E231 Missing whitespace after ','
250 mapped_edge = mapping[tuple(edge)] if tuple(edge) in mapping else mapping[tuple([edge[1],edge[0]])]
251 orbit_membership_new[i] = orbit_membership[mapped_edge]
252  
  • E501 Line too long (83 > 79 characters)
  • W291 Trailing whitespace
253 print('Edge orbit partition of given substructure: {}'.format(orbit_partition))
254 print('Number of edge orbits: {}'.format(len(orbit_partition)))
255 print('Graph (vertex) automorphism count: {}'.format(aut_count))
  • W293 Blank line contains whitespace
256
257 return graph, orbit_partition, orbit_membership_new, aut_count