Node embeddings

import%20marimo%0A%0A__generated_with%20%3D%20%220.23.6%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22%2C%20app_title%3D%22Node%20embeddings%22)%0A%0A%0A%40app.cell%0Adef%20imports()%3A%0A%20%20%20%20import%20io%0A%20%20%20%20import%20urllib.request%0A%20%20%20%20from%20pathlib%20import%20Path%0A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20pandas%20as%20pd%0A%20%20%20%20import%20matplotlib%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20from%20matplotlib.collections%20import%20LineCollection%0A%20%20%20%20import%20igraph%20as%20ig%0A%0A%20%20%20%20from%20sklearn.cluster%20import%20KMeans%0A%20%20%20%20from%20sklearn.decomposition%20import%20PCA%2C%20TruncatedSVD%0A%20%20%20%20from%20sklearn.manifold%20import%20TSNE%0A%20%20%20%20from%20sklearn.linear_model%20import%20LogisticRegression%0A%20%20%20%20from%20sklearn.metrics%20import%20(%0A%20%20%20%20%20%20%20%20accuracy_score%2C%0A%20%20%20%20%20%20%20%20classification_report%2C%0A%20%20%20%20%20%20%20%20confusion_matrix%2C%0A%20%20%20%20%20%20%20%20f1_score%2C%0A%20%20%20%20%20%20%20%20silhouette_score%2C%0A%20%20%20%20)%0A%20%20%20%20from%20sklearn.model_selection%20import%20train_test_split%0A%0A%20%20%20%20matplotlib.rcParams.update(%7B%0A%20%20%20%20%20%20%20%20%22figure.facecolor%22%3A%20%22white%22%2C%0A%20%20%20%20%20%20%20%20%22axes.facecolor%22%3A%20%22white%22%2C%0A%20%20%20%20%20%20%20%20%22axes.edgecolor%22%3A%20%22%23444444%22%2C%0A%20%20%20%20%20%20%20%20%22axes.labelcolor%22%3A%20%22%23333333%22%2C%0A%20%20%20%20%20%20%20%20%22text.color%22%3A%20%22%23333333%22%2C%0A%20%20%20%20%20%20%20%20%22xtick.color%22%3A%20%22%23333333%22%2C%0A%20%20%20%20%20%20%20%20%22ytick.color%22%3A%20%22%23333333%22%2C%0A%20%20%20%20%20%20%20%20%22font.size%22%3A%2013%2C%0A%20%20%20%20%20%20%20%20%22axes.titlesize%22%3A%2015%2C%0A%20%20%20%20%20%20%20%20%22axes.labelsize%22%3A%2013%2C%0A%20%20%20%20%20%20%20%20%22figure.dpi%22%3A%20130%2C%0A%20%20%20%20%20%20%20%20%22axes.grid%22%3A%20True%2C%0A%20%20%20%20%20%20%20%20%22grid.alpha%22%3A%200.25%2C%0A%20%20%20%20%20%20%20%20%22grid.color%22%3A%20%22%23cccccc%22%2C%0A%20%20%20%20%20%20%20%20%23%20No%20surrounding%20%22axis%20box%22%20on%20any%20plot.%20Curves%20with%20meaningful%0A%20%20%20%20%20%20%20%20%23%20axes%20(Section%204%20accuracy)%20still%20show%20their%20tick%20marks%20and%0A%20%20%20%20%20%20%20%20%23%20labels%3B%20PCA%20%2F%20network%20%2F%20walk%20plots%20additionally%20clear%20ticks%0A%20%20%20%20%20%20%20%20%23%20in%20their%20own%20cells%2C%20so%20the%20panels%20read%20as%20pure%20scatter.%0A%20%20%20%20%20%20%20%20%22axes.spines.top%22%3A%20False%2C%0A%20%20%20%20%20%20%20%20%22axes.spines.right%22%3A%20False%2C%0A%20%20%20%20%20%20%20%20%22axes.spines.left%22%3A%20False%2C%0A%20%20%20%20%20%20%20%20%22axes.spines.bottom%22%3A%20False%2C%0A%20%20%20%20%7D)%0A%0A%20%20%20%20def%20parse_graphml(raw_bytes)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Parse%20a%20GraphML%20document%20with%20the%20stdlib%20XML%20parser.%0A%0A%20%20%20%20%20%20%20%20Pyodide's%20python-igraph%20wheel%20is%20compiled%20without%20GraphML%20support%0A%20%20%20%20%20%20%20%20(no%20libxml2)%2C%20so%20we%20cannot%20call%20%60%60ig.Graph.Read_GraphML%60%60%20in%20the%0A%20%20%20%20%20%20%20%20browser.%20This%20helper%20produces%20the%20same%20kind%20of%20igraph.Graph%20by%0A%20%20%20%20%20%20%20%20reading%20the%20GraphML%20XML%20directly.%0A%0A%20%20%20%20%20%20%20%20Recognised%3A%20%60%60%3Ckey%3E%60%60%20declarations%20(so%20attribute%20names%20and%20types%0A%20%20%20%20%20%20%20%20survive)%2C%20%60%60%3Cnode%3E%60%60%20ids%20and%20per-node%20%60%60%3Cdata%3E%60%60%20values%2C%20and%0A%20%20%20%20%20%20%20%20%60%60%3Cedge%3E%60%60%20source%2Ftarget%20pairs.%20Directed%20graphs%20are%20collapsed%20to%0A%20%20%20%20%20%20%20%20undirected%20to%20match%20the%20rest%20of%20the%20app.%20Self-loops%20and%20parallel%0A%20%20%20%20%20%20%20%20edges%20are%20simplified%20away.%20The%20original%20GraphML%20node%20ids%20are%0A%20%20%20%20%20%20%20%20preserved%20as%20%60%60g.vs%5B'id'%5D%60%60.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20import%20xml.etree.ElementTree%20as%20_ET%0A%0A%20%20%20%20%20%20%20%20_root%20%3D%20_ET.fromstring(raw_bytes)%0A%20%20%20%20%20%20%20%20_ns%20%3D%20%22%22%0A%20%20%20%20%20%20%20%20if%20_root.tag.startswith(%22%7B%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ns%20%3D%20_root.tag%5B1%3A%5D.split(%22%7D%22%2C%201)%5B0%5D%0A%20%20%20%20%20%20%20%20def%20_qn(tag)%3A%20return%20f%22%7B%7B%7B_ns%7D%7D%7D%7Btag%7D%22%20if%20_ns%20else%20tag%0A%0A%20%20%20%20%20%20%20%20_keys%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20for%20_k%20in%20_root.findall(_qn(%22key%22))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_keys%5B_k.get(%22id%22)%5D%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22name%22%3A%20_k.get(%22attr.name%22%2C%20_k.get(%22id%22))%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22for%22%3A%20%20_k.get(%22for%22%2C%20%22node%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22type%22%3A%20_k.get(%22attr.type%22%2C%20%22string%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%0A%20%20%20%20%20%20%20%20_graph_el%20%3D%20_root.find(_qn(%22graph%22))%0A%20%20%20%20%20%20%20%20if%20_graph_el%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20raise%20ValueError(%22GraphML%20document%20has%20no%20%3Cgraph%3E%20element.%22)%0A%20%20%20%20%20%20%20%20_is_directed%20%3D%20(_graph_el.get(%22edgedefault%22%2C%20%22undirected%22)%20%3D%3D%20%22directed%22)%0A%0A%20%20%20%20%20%20%20%20_node_ids%2C%20_id_to_idx%2C%20_node_attrs%20%3D%20%5B%5D%2C%20%7B%7D%2C%20%7B%7D%0A%20%20%20%20%20%20%20%20for%20_n%20in%20_graph_el.findall(_qn(%22node%22))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_gid%20%3D%20_n.get(%22id%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20_idx%20%3D%20len(_node_ids)%0A%20%20%20%20%20%20%20%20%20%20%20%20_id_to_idx%5B_gid%5D%20%3D%20_idx%0A%20%20%20%20%20%20%20%20%20%20%20%20_node_ids.append(_gid)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_kid%2C%20_info%20in%20_keys.items()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_info%5B%22for%22%5D%20%3D%3D%20%22node%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_node_attrs.setdefault(_info%5B%22name%22%5D%2C%20%5B%5D).append(None)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_d%20in%20_n.findall(_qn(%22data%22))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_kid%20%3D%20_d.get(%22key%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_kid%20not%20in%20_keys%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_info%20%3D%20_keys%5B_kid%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_info%5B%22for%22%5D%20!%3D%20%22node%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_val%20%3D%20(_d.text%20or%20%22%22).strip()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_t%20%3D%20_info%5B%22type%22%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_t%20in%20(%22int%22%2C%20%22integer%22%2C%20%22long%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20try%3A%20_val%20%3D%20int(_val)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20except%20ValueError%3A%20pass%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20elif%20_t%20in%20(%22float%22%2C%20%22double%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20try%3A%20_val%20%3D%20float(_val)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20except%20ValueError%3A%20pass%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20elif%20_t%20in%20(%22bool%22%2C%20%22boolean%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_val%20%3D%20_val.strip().lower()%20in%20(%22true%22%2C%20%221%22%2C%20%22yes%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_node_attrs%5B_info%5B%22name%22%5D%5D%5B_idx%5D%20%3D%20_val%0A%0A%20%20%20%20%20%20%20%20_edges%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20_e%20in%20_graph_el.findall(_qn(%22edge%22))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_s%20%3D%20_e.get(%22source%22)%3B%20_t%20%3D%20_e.get(%22target%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20_s%20in%20_id_to_idx%20and%20_t%20in%20_id_to_idx%20and%20_s%20!%3D%20_t%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_edges.append((_id_to_idx%5B_s%5D%2C%20_id_to_idx%5B_t%5D))%0A%0A%20%20%20%20%20%20%20%20_g%20%3D%20ig.Graph(n%3Dlen(_node_ids)%2C%20edges%3D_edges%2C%20directed%3D_is_directed)%0A%20%20%20%20%20%20%20%20if%20_is_directed%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_g%20%3D%20_g.as_undirected(mode%3D%22collapse%22)%0A%20%20%20%20%20%20%20%20_g.simplify()%0A%20%20%20%20%20%20%20%20_g.vs%5B%22id%22%5D%20%3D%20_node_ids%0A%20%20%20%20%20%20%20%20for%20_name%2C%20_vals%20in%20_node_attrs.items()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_g.vs%5B_name%5D%20%3D%20_vals%0A%20%20%20%20%20%20%20%20return%20_g%0A%0A%20%20%20%20def%20_load_public_bytes(filename)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Read%20bytes%20from%20public%2F%3Cfilename%3E%2C%20working%20both%20locally%20and%20in%20WASM.%0A%0A%20%20%20%20%20%20%20%20Marimo's%20WASM%20exporter%20bundles%20the%20%60%60public%2F%60%60%20directory%20alongside%20the%0A%20%20%20%20%20%20%20%20notebook%20and%20serves%20it%20from%20%60%60mo.notebook_location()%60%60.%20Locally%2C%0A%20%20%20%20%20%20%20%20%60%60notebook_location()%60%60%20returns%20a%20filesystem%20path%2C%20so%20the%20same%20call%0A%20%20%20%20%20%20%20%20site%20works%20in%20both%20environments.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20target%20%3D%20mo.notebook_location()%20%2F%20%22public%22%20%2F%20filename%0A%20%20%20%20%20%20%20%20target_str%20%3D%20str(target)%0A%20%20%20%20%20%20%20%20if%20target_str.startswith((%22http%3A%2F%2F%22%2C%20%22https%3A%2F%2F%22))%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20with%20urllib.request.urlopen(target_str)%20as%20f%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20f.read()%0A%20%20%20%20%20%20%20%20local%20%3D%20Path(target_str)%0A%20%20%20%20%20%20%20%20if%20local.exists()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20local.read_bytes()%0A%20%20%20%20%20%20%20%20%23%20Fallback%20for%20%60marimo%20edit%60%20invocations%20where%20notebook_location()%0A%20%20%20%20%20%20%20%20%23%20may%20not%20resolve%20to%20this%20file's%20directory.%0A%20%20%20%20%20%20%20%20return%20(Path(__file__).parent%20%2F%20%22public%22%20%2F%20filename).read_bytes()%0A%0A%20%20%20%20def%20load_graphml(filename)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Return%20an%20igraph%20Graph%20from%20public%2F%3Cfilename%3E.%0A%0A%20%20%20%20%20%20%20%20Uses%20the%20in-app%20GraphML%20parser%20because%20Pyodide's%20igraph%20wheel%20ships%0A%20%20%20%20%20%20%20%20without%20GraphML%20support.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20return%20parse_graphml(_load_public_bytes(filename))%0A%0A%20%20%20%20def%20load_npy(filename)%3A%0A%20%20%20%20%20%20%20%20return%20np.load(io.BytesIO(_load_public_bytes(filename)))%0A%0A%20%20%20%20def%20load_npz(filename)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Load%20an%20.npz%20archive%20from%20public%2F%20as%20a%20%7Bname%3A%20array%7D%20dict.%22%22%22%0A%20%20%20%20%20%20%20%20with%20np.load(io.BytesIO(_load_public_bytes(filename)))%20as%20archive%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%7Bk%3A%20archive%5Bk%5D%20for%20k%20in%20archive.files%7D%0A%0A%20%20%20%20PALETTE%20%3D%20list(matplotlib.colormaps%5B%22tab20%22%5D.colors)%0A%20%20%20%20ACCENT%20%3D%20%22%230b789d%22%0A%0A%20%20%20%20%23%20Conference%20IDs%20in%20the%20bundled%20football%20dataset%20map%20to%20the%20actual%0A%20%20%20%20%23%20NCAA%20conference%20names%20in%20alphabetical%20order%20(Girvan%20%26%20Newman%202002).%0A%20%20%20%20%23%20Verified%20by%20inspecting%20which%20teams%20sit%20in%20each%20ID-group.%0A%20%20%20%20FOOTBALL_CONFERENCES%20%3D%20%7B%0A%20%20%20%20%20%20%20%200%3A%20%22Atlantic%20Coast%22%2C%0A%20%20%20%20%20%20%20%201%3A%20%22Big%20East%22%2C%0A%20%20%20%20%20%20%20%202%3A%20%22Big%20Ten%22%2C%0A%20%20%20%20%20%20%20%203%3A%20%22Big%20Twelve%22%2C%0A%20%20%20%20%20%20%20%204%3A%20%22Conference%20USA%22%2C%0A%20%20%20%20%20%20%20%205%3A%20%22Independents%22%2C%20%20%20%20%20%20%20%23%20not%20a%20real%20conference%20%E2%80%94%20see%20app%20note%0A%20%20%20%20%20%20%20%206%3A%20%22Mid-American%22%2C%0A%20%20%20%20%20%20%20%207%3A%20%22Mountain%20West%22%2C%0A%20%20%20%20%20%20%20%208%3A%20%22Pacific%20Ten%22%2C%0A%20%20%20%20%20%20%20%209%3A%20%22Southeastern%22%2C%0A%20%20%20%20%20%20%20%2010%3A%20%22Sun%20Belt%22%2C%0A%20%20%20%20%20%20%20%2011%3A%20%22Western%20Athletic%22%2C%0A%20%20%20%20%7D%0A%20%20%20%20KARATE_FACTIONS%20%3D%20%7B0%3A%20%22Mr%20Hi's%20faction%22%2C%201%3A%20%22Officer's%20faction%22%7D%0A%0A%20%20%20%20%23%20Les%20Mis%C3%A9rables%20community%20labels%20were%20obtained%20by%20running%20Louvain%0A%20%20%20%20%23%20community%20detection%20on%20the%20co-appearance%20graph%20(Knuth's%20dataset%0A%20%20%20%20%23%20from%20the%20node2vec%20paper).%20The%20names%20below%20were%20assigned%20by%0A%20%20%20%20%23%20inspecting%20which%20characters%20fell%20into%20each%20cluster.%0A%20%20%20%20LESMIS_COMMUNITIES%20%3D%20%7B%0A%20%20%20%20%20%20%20%200%3A%20%22Bishop's%20circle%22%2C%0A%20%20%20%20%20%20%20%201%3A%20%22Valjean%20%26%20ex-convicts%22%2C%0A%20%20%20%20%20%20%20%202%3A%20%22Fantine's%20friends%22%2C%0A%20%20%20%20%20%20%20%203%3A%20%22Th%C3%A9nardier's%20gang%22%2C%0A%20%20%20%20%20%20%20%204%3A%20%22Gillenormand%20family%22%2C%0A%20%20%20%20%20%20%20%205%3A%20%22ABC%20revolutionaries%22%2C%0A%20%20%20%20%7D%0A%0A%20%20%20%20def%20class_names_for(graph_data)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Return%20a%20list%20of%20length%20n_classes%20with%20human-readable%20names%2C%0A%20%20%20%20%20%20%20%20or%20string%20class%20IDs%20if%20no%20canonical%20mapping%20is%20known.%22%22%22%0A%20%20%20%20%20%20%20%20name%20%3D%20graph_data.get(%22name%22%2C%20%22%22)%0A%20%20%20%20%20%20%20%20labels%20%3D%20graph_data.get(%22labels%22)%0A%20%20%20%20%20%20%20%20if%20labels%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%5B%5D%0A%20%20%20%20%20%20%20%20classes%20%3D%20sorted(set(int(c)%20for%20c%20in%20labels))%0A%20%20%20%20%20%20%20%20if%20name.startswith(%22Football%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%5BFOOTBALL_CONFERENCES.get(c%2C%20f%22class%20%7Bc%7D%22)%20for%20c%20in%20classes%5D%0A%20%20%20%20%20%20%20%20if%20name.startswith(%22Karate%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%5BKARATE_FACTIONS.get(c%2C%20f%22class%20%7Bc%7D%22)%20for%20c%20in%20classes%5D%0A%20%20%20%20%20%20%20%20if%20name.startswith(%22Les%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%5BLESMIS_COMMUNITIES.get(c%2C%20f%22class%20%7Bc%7D%22)%20for%20c%20in%20classes%5D%0A%20%20%20%20%20%20%20%20return%20%5Bstr(c)%20for%20c%20in%20classes%5D%0A%0A%20%20%20%20def%20style_minimal(ax%2C%20no_ticks%3DFalse)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Strip%20the%20surrounding%20spines%20(the%20black%20axis%20box).%0A%0A%20%20%20%20%20%20%20%20Pass%20%60%60no_ticks%3DTrue%60%60%20for%20plots%20whose%20x%2Fy%20axes%20have%20no%20physical%0A%20%20%20%20%20%20%20%20meaning%20(PCAs%2C%20network%20layouts)%20%E2%80%94%20that%20also%20clears%20the%20tick%20marks%0A%20%20%20%20%20%20%20%20and%20tick%20labels.%20Curves%20with%20meaningful%20axes%20(e.g.%20accuracy%20vs.%0A%20%20%20%20%20%20%20%20epoch)%20leave%20the%20ticks%20in%20place%20and%20just%20lose%20the%20surrounding%0A%20%20%20%20%20%20%20%20box.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20for%20_s%20in%20ax.spines.values()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_s.set_visible(False)%0A%20%20%20%20%20%20%20%20if%20no_ticks%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.set_xticks(%5B%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.set_yticks(%5B%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.set_xlabel(%22%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.set_ylabel(%22%22)%0A%0A%20%20%20%20def%20procrustes_align(coords_2d%2C%20anchor_idx%2C%20anchor_targets)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Find%20the%20rotation%20%2B%20reflection%20%2B%20uniform%20scale%20that%20best%20maps%0A%20%20%20%20%20%20%20%20%60%60coords_2d%5Banchor_idx%5D%60%60%20onto%20%60%60anchor_targets%60%60%20(3%C3%972).%20Apply%0A%20%20%20%20%20%20%20%20that%20transform%20to%20every%20row%20of%20%60%60coords_2d%60%60%20and%20return%20the%20result.%0A%0A%20%20%20%20%20%20%20%20This%20is%20full%20Procrustes%20(Sch%C3%B6nemann%201966)%20with%20scaling%2C%20so%20all%0A%20%20%20%20%20%20%20%202-d%20embedding%20plots%20end%20up%20in%20roughly%20the%20same%20orientation%20and%0A%20%20%20%20%20%20%20%20size%20as%20the%20network%20layout%20%E2%80%94%20only%20the%20*internal*%20geometry%20of%20each%0A%20%20%20%20%20%20%20%20method's%20embedding%20differs%20from%20one%20panel%20to%20the%20next.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20src%20%3D%20np.asarray(coords_2d%2C%20dtype%3Dfloat)%0A%20%20%20%20%20%20%20%20anchors_src%20%3D%20src%5Blist(anchor_idx)%5D%0A%20%20%20%20%20%20%20%20src_mean%20%3D%20anchors_src.mean(axis%3D0)%0A%20%20%20%20%20%20%20%20tgt_mean%20%3D%20np.asarray(anchor_targets%2C%20dtype%3Dfloat).mean(axis%3D0)%0A%20%20%20%20%20%20%20%20src_c%20%3D%20anchors_src%20-%20src_mean%0A%20%20%20%20%20%20%20%20tgt_c%20%3D%20np.asarray(anchor_targets%2C%20dtype%3Dfloat)%20-%20tgt_mean%0A%20%20%20%20%20%20%20%20%23%20Optimal%20R%3A%20SVD%20of%20cross-covariance.%0A%20%20%20%20%20%20%20%20M%20%3D%20src_c.T%20%40%20tgt_c%0A%20%20%20%20%20%20%20%20U%2C%20S%2C%20Vt%20%3D%20np.linalg.svd(M)%0A%20%20%20%20%20%20%20%20R%20%3D%20U%20%40%20Vt%20%20%23%202%C3%972%20orthogonal%20(det%20%3D%20%C2%B11%3B%20reflection%20allowed)%0A%20%20%20%20%20%20%20%20%23%20Optimal%20isotropic%20scale.%0A%20%20%20%20%20%20%20%20src_norm_sq%20%3D%20float((src_c%20**%202).sum())%0A%20%20%20%20%20%20%20%20s%20%3D%20float(S.sum()%20%2F%20src_norm_sq)%20if%20src_norm_sq%20%3E%201e-12%20else%201.0%0A%20%20%20%20%20%20%20%20return%20(src%20-%20src_mean)%20%40%20(R%20*%20s)%20%2B%20tgt_mean%0A%0A%20%20%20%20%23%20A%20second%20palette%20specifically%20for%20k-means%20cluster%20colours%2C%20so%0A%20%20%20%20%23%20they%20don't%20get%20confused%20with%20the%20per-class%20palette%20used%20everywhere%0A%20%20%20%20%23%20else.%20Picked%20from%20matplotlib's%20%22Set2%22%20colormap%20(colourblind-friendly%0A%20%20%20%20%23%20pastels%2C%20distinct%20from%20the%20tab20%20default).%0A%20%20%20%20KMEANS_PALETTE%20%3D%20list(matplotlib.colormaps%5B%22Set2%22%5D.colors)%20%2B%20%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20list(matplotlib.colormaps%5B%22Set3%22%5D.colors)%0A%0A%20%20%20%20def%20network_with_cluster_colors(ax%2C%20g%2C%20coords%2C%20edges_iter%2C%20cluster_ids%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20palette%3DNone%2C%20struct_anchors%3DNone%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20title%3DNone%2C%20names%3DNone%2C%20show_labels%3DFalse%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20anchor_names_always%3DTrue)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Draw%20the%20FR-laid-out%20network%20with%20node%20colours%20coming%20from%20a%0A%20%20%20%20%20%20%20%20k-means%20clustering%20of%20an%20embedding.%20Edges%20stay%20plain%20grey%0A%20%20%20%20%20%20%20%20(per%20user%20feedback%20%E2%80%94%20colouring%20them%20by%20cluster%20made%20the%20plots%0A%20%20%20%20%20%20%20%20noisier%20than%20they%20helped).%20Anchor%20nodes%20get%20a%20hollow%20black%0A%20%20%20%20%20%20%20%20square%3B%20their%20*names*%20are%20written%20next%20to%20the%20square%20by%0A%20%20%20%20%20%20%20%20default.%22%22%22%0A%20%20%20%20%20%20%20%20from%20matplotlib.collections%20import%20LineCollection%20as%20_LC%0A%20%20%20%20%20%20%20%20_pal%20%3D%20palette%20if%20palette%20is%20not%20None%20else%20KMEANS_PALETTE%0A%20%20%20%20%20%20%20%20ax.set_facecolor(%22white%22)%0A%20%20%20%20%20%20%20%20_segs%20%3D%20%5B%5Bcoords%5Be.source%5D%2C%20coords%5Be.target%5D%5D%20for%20e%20in%20edges_iter%5D%0A%20%20%20%20%20%20%20%20ax.add_collection(_LC(_segs%2C%20colors%3D%22%23dddddd%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20linewidths%3D0.5%2C%20alpha%3D0.6%2C%20zorder%3D1))%0A%20%20%20%20%20%20%20%20_colors%20%3D%20%5B_pal%5Bint(c)%20%25%20len(_pal)%5D%20for%20c%20in%20cluster_ids%5D%0A%20%20%20%20%20%20%20%20ax.scatter(coords%5B%3A%2C%200%5D%2C%20coords%5B%3A%2C%201%5D%2C%20s%3D55%2C%20c%3D_colors%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolor%3D%22%23333333%22%2C%20linewidth%3D0.4%2C%20zorder%3D3)%0A%20%20%20%20%20%20%20%20if%20struct_anchors%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_i%20in%20struct_anchors%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ax.scatter(coords%5B_i%2C%200%5D%2C%20coords%5B_i%2C%201%5D%2C%20s%3D260%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20marker%3D%22s%22%2C%20facecolors%3D%22none%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolor%3D%22black%22%2C%20linewidth%3D1.8%2C%20zorder%3D5)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20anchor_names_always%20and%20names%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ax.annotate(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20str(names%5B_i%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xy%3D(coords%5B_i%2C%200%5D%2C%20coords%5B_i%2C%201%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(8%2C%208)%2C%20textcoords%3D%22offset%20points%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D7%2C%20color%3D%22%23222222%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.2%22%2C%20fc%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ec%3D%22%23888888%22%2C%20alpha%3D0.9%2C%20lw%3D0.5)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D6%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20if%20show_labels%20and%20names%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_i%2C%20_nm%20in%20enumerate(names)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20struct_anchors%20and%20_i%20in%20struct_anchors%20and%20anchor_names_always%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ax.annotate(str(_nm)%2C%20xy%3D(coords%5B_i%2C%200%5D%2C%20coords%5B_i%2C%201%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(3%2C%203)%2C%20textcoords%3D%22offset%20points%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D6%2C%20color%3D%22%23333333%22%2C%20alpha%3D0.8%2C%20zorder%3D6)%0A%20%20%20%20%20%20%20%20ax.set_xticks(%5B%5D)%3B%20ax.set_yticks(%5B%5D)%3B%20ax.grid(False)%3B%20ax.set_aspect(%22equal%22)%0A%20%20%20%20%20%20%20%20if%20title%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ax.set_title(title%2C%20fontsize%3D10)%0A%0A%20%20%20%20def%20biased_walk(graph%2C%20start%2C%20length%2C%20p%2C%20q%2C%20rng)%3A%0A%20%20%20%20%20%20%20%20%22%22%22One%20node2vec%20random%20walk%3A%20bias%20%601%2Fp%60%20to%20return%20to%20the%20previous%0A%20%20%20%20%20%20%20%20node%2C%20%601%60%20to%20step%20to%20a%20distance-1%20neighbour%2C%20%601%2Fq%60%20to%20step%20to%20a%0A%20%20%20%20%20%20%20%20distance-2%20neighbour.%22%22%22%0A%20%20%20%20%20%20%20%20walk%20%3D%20%5Bint(start)%5D%0A%20%20%20%20%20%20%20%20if%20length%20%3C%202%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20walk%0A%20%20%20%20%20%20%20%20nbrs0%20%3D%20graph.neighbors(start)%0A%20%20%20%20%20%20%20%20if%20not%20nbrs0%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20walk%0A%20%20%20%20%20%20%20%20walk.append(int(rng.choice(nbrs0)))%0A%20%20%20%20%20%20%20%20inv_p%20%3D%201.0%20%2F%20p%0A%20%20%20%20%20%20%20%20inv_q%20%3D%201.0%20%2F%20q%0A%20%20%20%20%20%20%20%20for%20_%20in%20range(length%20-%202)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20cur%20%3D%20walk%5B-1%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20prev%20%3D%20walk%5B-2%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20nbrs%20%3D%20graph.neighbors(cur)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20not%20nbrs%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20%20%20%20%20%20%20%20%20prev_set%20%3D%20set(graph.neighbors(prev))%20%7C%20%7Bprev%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20w%20%3D%20np.empty(len(nbrs)%2C%20dtype%3Dnp.float64)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20i%2C%20x%20in%20enumerate(nbrs)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20x%20%3D%3D%20prev%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20w%5Bi%5D%20%3D%20inv_p%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20elif%20x%20in%20prev_set%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20w%5Bi%5D%20%3D%201.0%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20w%5Bi%5D%20%3D%20inv_q%0A%20%20%20%20%20%20%20%20%20%20%20%20cw%20%3D%20np.cumsum(w)%0A%20%20%20%20%20%20%20%20%20%20%20%20r%20%3D%20rng.random()%20*%20cw%5B-1%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20walk.append(int(nbrs%5Bint(np.searchsorted(cw%2C%20r))%5D))%0A%20%20%20%20%20%20%20%20return%20walk%0A%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20KMeans%2C%0A%20%20%20%20%20%20%20%20LineCollection%2C%0A%20%20%20%20%20%20%20%20LogisticRegression%2C%0A%20%20%20%20%20%20%20%20PALETTE%2C%0A%20%20%20%20%20%20%20%20PCA%2C%0A%20%20%20%20%20%20%20%20TSNE%2C%0A%20%20%20%20%20%20%20%20TruncatedSVD%2C%0A%20%20%20%20%20%20%20%20accuracy_score%2C%0A%20%20%20%20%20%20%20%20biased_walk%2C%0A%20%20%20%20%20%20%20%20class_names_for%2C%0A%20%20%20%20%20%20%20%20f1_score%2C%0A%20%20%20%20%20%20%20%20ig%2C%0A%20%20%20%20%20%20%20%20io%2C%0A%20%20%20%20%20%20%20%20load_graphml%2C%0A%20%20%20%20%20%20%20%20load_npy%2C%0A%20%20%20%20%20%20%20%20load_npz%2C%0A%20%20%20%20%20%20%20%20mo%2C%0A%20%20%20%20%20%20%20%20network_with_cluster_colors%2C%0A%20%20%20%20%20%20%20%20np%2C%0A%20%20%20%20%20%20%20%20parse_graphml%2C%0A%20%20%20%20%20%20%20%20pd%2C%0A%20%20%20%20%20%20%20%20plt%2C%0A%20%20%20%20%20%20%20%20procrustes_align%2C%0A%20%20%20%20%20%20%20%20silhouette_score%2C%0A%20%20%20%20%20%20%20%20train_test_split%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20title(mo)%3A%0A%20%20%20%20mo.md(%22%22%22%0A%20%20%20%20%23%20Node%20embeddings%20and%20what%20we%20can%20do%20with%20them%0A%0A%20%20%20%20*Javier%20Garcia-Bernardo%20%E2%80%94%20ODISSEI%20Social%20Data%20Science%20team%20(SoDa)%20%26%20Department%20of%20Methodology%20and%20Statistics%2C%20Utrecht%20University*%0A%0A%20%20%20%20A%20**node%20embedding**%20turns%20every%20vertex%20of%20a%20network%20into%20a%20vector.%0A%20%20%20%20Once%20that's%20done%2C%20*%22is%20node%20A%20like%20node%20B%3F%22*%20becomes%20a%20question%0A%20%20%20%20about%20**distance**%20%E2%80%94%20and%20the%20full%20toolkit%20of%20geometry%2C%20statistics%2C%0A%20%20%20%20and%20machine%20learning%20becomes%20available%20to%20answer%20it.%0A%0A%20%20%20%20Below%20we%20build%20three%20families%20of%20embeddings%2C%20then%20close%20the%20loop%0A%20%20%20%20with%20a%20classification%20benchmark%3A%0A%0A%20%20%20%201.%20**Spectral%20methods**%20%E2%80%94%20top%20eigenvectors%20of%20the%20adjacency%20or%0A%20%20%20%20%20%20%20Laplacian.%20Deterministic%2C%20fast%2C%20classical.%0A%20%20%20%202.%20**node2vec**%20%E2%80%94%20random%20walks%20fed%20through%20*word2vec*.%20Same%20kind%20of%0A%20%20%20%20%20%20%20trick%20that%20turns%20words%20into%20vectors%2C%20applied%20to%20nodes.%20Two%20knobs%0A%20%20%20%20%20%20%20(%24p%24%2C%20%24q%24)%20let%20us%20tune%20what%20*kind*%20of%20structure%20it%20captures%3A%0A%20%20%20%20%20%20%20community%20vs.%20role.%0A%20%20%20%203.%20**GCN%20(graph%20convolutional%20network)**%20%E2%80%94%20a%20supervised%20graph%0A%20%20%20%20%20%20%20neural%20network%20that%20learns%20its%20embedding%20**with**%20the%20labels%20in%0A%20%20%20%20%20%20%20hand.%20The%20fanciest%2C%20and%20the%20only%20one%20that%20gets%20to%20see%20classes%0A%20%20%20%20%20%20%20during%20training.%0A%0A%20%20%20%20For%20each%2C%20we%20then%20ask%3A%20how%20well%20does%20the%20embedding%20predict%20the%0A%20%20%20%20class%20when%20plugged%20into%20a%20plain%20multinomial%20logistic%20regression%3F%0A%0A%20%20%20%20%3E%20_Pick%20a%20network%20in%20the%20sidebar%20%E2%80%94%20football%2C%20karate%2C%20Les%20Mis%C3%A9rables%2C%0A%20%20%20%20%3E%20or%20upload%20your%20own%20%E2%80%94%20and%20the%20five%20sections%20below%20all%20re-run%20on%0A%20%20%20%20%3E%20the%20new%20graph._%0A%0A%20%20%20%20---%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20sec1_widgets(mo)%3A%0A%20%20%20%20dataset_choice%20%3D%20mo.ui.radio(%0A%20%20%20%20%20%20%20%20options%3D%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Les%20Mis%C3%A9rables%20(77%20characters%2C%206%20communities)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Football%20(115%20nodes%2C%2012%20conferences)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Karate%20(34%20nodes%2C%202%20factions)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Upload%20my%20own%20(CSV%20or%20GraphML)%22%2C%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%20%20%20%20value%3D%22Les%20Mis%C3%A9rables%20(77%20characters%2C%206%20communities)%22%2C%0A%20%20%20%20%20%20%20%20label%3D%22Dataset%22%2C%0A%20%20%20%20)%0A%20%20%20%20upload%20%3D%20mo.ui.file(%0A%20%20%20%20%20%20%20%20filetypes%3D%5B%22.csv%22%2C%20%22.graphml%22%2C%20%22.xml%22%5D%2C%0A%20%20%20%20%20%20%20%20multiple%3DFalse%2C%0A%20%20%20%20%20%20%20%20label%3D%22CSV%20or%20GraphML%22%2C%0A%20%20%20%20)%0A%20%20%20%20show_node_labels%20%3D%20mo.ui.checkbox(value%3DFalse%2C%20label%3D%22Show%20node%20labels%20on%20all%20networks%22)%0A%20%20%20%20return%20dataset_choice%2C%20show_node_labels%2C%20upload%0A%0A%0A%40app.cell%0Adef%20sidebar(dataset_choice%2C%20mo%2C%20show_node_labels%2C%20upload)%3A%0A%20%20%20%20mo.sidebar(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%22%23%23%23%20Dataset%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20dataset_choice%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%22_Or%20upload%20your%20own%3A_%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20upload%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22_CSV%3A%20needs%20a%20%60source%60%20and%20%60target%60%20column%20(the%20edge%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22list).%20An%20optional%20third%20column%20named%20%60class%60%20or%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%60label%60%20becomes%20the%20per-node%20class%20label._%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%22---%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%22%23%23%23%20Display%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20show_node_labels%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%22---%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22_The%20active%20network%20drives%20every%20section%20below%20%E2%80%94%20pick%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22it%20once%20here%2C%20then%20scroll._%22%0A%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20sec1_header(mo)%3A%0A%20%20%20%20mo.md(%22%22%22%0A%20%20%20%20%23%23%20Section%201%3A%20The%20dataset%0A%0A%20%20%20%20The%20default%20is%20the%20**US%20college%20football%20network**%20(115%20teams%2C%2012%0A%20%20%20%20conferences).%20Each%20node%20is%20a%20team%3B%20each%20edge%20is%20a%20game%20played%20in%20the%0A%20%20%20%202000%20regular%20season.%20The%20**conference**%20a%20team%20belongs%20to%20is%20our%20class%0A%20%20%20%20label%20%E2%80%94%20geographically%20and%20competitively%20coherent%2C%20so%20a%20good%20test%20case%0A%20%20%20%20for%20%22does%20the%20embedding%20recover%20community%20structure%3F%22.%0A%0A%20%20%20%20You%20can%20also%20switch%20to%20**Zachary's%20karate%20club**%20(34%20members%2C%202%0A%20%20%20%20factions)%20for%20a%20small%20example%2C%20or%20**upload%20your%20own**%20network%20in%20the%0A%20%20%20%20sidebar%3A%0A%0A%20%20%20%20-%20a%20CSV%20with%20columns%20%60source%2Ctarget%60%20(edge%20list%2C%20no%20class%20labels)%2C%20or%0A%20%20%20%20-%20a%20%60.graphml%60%20file%20(class%20labels%20are%20picked%20up%20from%20the%20node%0A%20%20%20%20%20%20attribute%20%60value%60%2C%20%60class%60%2C%20%60label%60%2C%20or%20%60group%60%20if%20present).%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20build_graph(%0A%20%20%20%20dataset_choice%2C%0A%20%20%20%20ig%2C%0A%20%20%20%20io%2C%0A%20%20%20%20load_graphml%2C%0A%20%20%20%20np%2C%0A%20%20%20%20parse_graphml%2C%0A%20%20%20%20pd%2C%0A%20%20%20%20upload%2C%0A)%3A%0A%20%20%20%20%23%20The%20classic%20Zachary%20faction%20assignment%20(Zachary%201977).%0A%20%20%20%20_zachary_factions%20%3D%20np.array(%5B%0A%20%20%20%20%20%20%20%200%2C%200%2C%200%2C%200%2C%200%2C%200%2C%200%2C%200%2C%201%2C%201%2C%0A%20%20%20%20%20%20%20%200%2C%200%2C%200%2C%200%2C%201%2C%201%2C%200%2C%200%2C%201%2C%200%2C%0A%20%20%20%20%20%20%20%201%2C%200%2C%201%2C%201%2C%201%2C%201%2C%201%2C%201%2C%201%2C%201%2C%0A%20%20%20%20%20%20%20%201%2C%201%2C%201%2C%201%2C%0A%20%20%20%20%5D)%0A%0A%20%20%20%20_choice%20%3D%20dataset_choice.value%0A%20%20%20%20_is_byod%20%3D%20False%0A%20%20%20%20_classes_available%20%3D%20True%0A%20%20%20%20_description%20%3D%20%22%22%0A%20%20%20%20_g%20%3D%20None%0A%20%20%20%20_labels%20%3D%20None%0A%20%20%20%20_err%20%3D%20None%0A%0A%20%20%20%20def%20_coerce_labels(values)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Try%20to%20parse%20a%20per-node%20attribute%20as%20an%20integer%20class%20label.%22%22%22%0A%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20np.array(%5Bint(v)%20for%20v%20in%20values%5D)%0A%20%20%20%20%20%20%20%20except%20(TypeError%2C%20ValueError)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20pass%0A%20%20%20%20%20%20%20%20%23%20Fall%20back%20to%20a%20categorical%20encoding%20(stable%20order%20by%20first%20appearance).%0A%20%20%20%20%20%20%20%20seen%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20out%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20v%20in%20values%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20key%20%3D%20str(v)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20key%20not%20in%20seen%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20seen%5Bkey%5D%20%3D%20len(seen)%0A%20%20%20%20%20%20%20%20%20%20%20%20out.append(seen%5Bkey%5D)%0A%20%20%20%20%20%20%20%20return%20np.array(out%2C%20dtype%3Dint)%0A%0A%20%20%20%20if%20_choice.startswith(%22Upload%22)%20and%20upload.value%3A%0A%20%20%20%20%20%20%20%20_file%20%3D%20upload.value%5B0%5D%0A%20%20%20%20%20%20%20%20_raw%20%3D%20_file.contents%0A%20%20%20%20%20%20%20%20_fname%20%3D%20(_file.name%20or%20%22%22).lower()%0A%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20_fname.endswith(%22.graphml%22)%20or%20_fname.endswith(%22.xml%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20GraphML%20upload%3A%20use%20the%20stdlib-XML%20parser%20(Pyodide's%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20python-igraph%20wheel%20has%20no%20GraphML%20support).%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_g%20%3D%20parse_graphml(_raw)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Names%3A%20prefer%20'name'%2C%20then%20'id'%2C%20else%20integer%20indices.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20%22name%22%20in%20_g.vs.attributes()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_g.vs%5B%22name%22%5D%20%3D%20%5Bstr(x)%20for%20x%20in%20_g.vs%5B%22name%22%5D%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20elif%20%22id%22%20in%20_g.vs.attributes()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_g.vs%5B%22name%22%5D%20%3D%20%5Bstr(x)%20for%20x%20in%20_g.vs%5B%22id%22%5D%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_g.vs%5B%22name%22%5D%20%3D%20%5Bf%22v%7Bi%7D%22%20for%20i%20in%20range(_g.vcount())%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Labels%3A%20try%20common%20attribute%20names.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_label_attr%20%3D%20None%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20_cand%20in%20(%22value%22%2C%20%22class%22%2C%20%22label%22%2C%20%22group%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_cand%20in%20_g.vs.attributes()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_label_attr%20%3D%20_cand%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_label_attr%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_labels%20%3D%20_coerce_labels(_g.vs%5B_label_attr%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_classes_available%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_is_byod%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_description%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22**User-uploaded%20GraphML**%20with%20%7B_g.vcount()%7D%20nodes%2C%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%7B_g.ecount()%7D%20edges%2C%20and%20%7Blen(set(_labels))%7D%20classes%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22(from%20node%20attribute%20%60%7B_label_attr%7D%60).%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_labels%20%3D%20None%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_classes_available%20%3D%20False%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_is_byod%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_description%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22**User-uploaded%20GraphML**%20with%20%7B_g.vcount()%7D%20nodes%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22and%20%7B_g.ecount()%7D%20edges.%20_No%20node-class%20attribute%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22(%60value%60%20%2F%20%60class%60%20%2F%20%60label%60%20%2F%20%60group%60)%20was%20found%2C%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22so%20the%20classification%20panels%20are%20hidden._%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_df%20%3D%20pd.read_csv(io.BytesIO(_raw))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cols%20%3D%20%5Bc.lower()%20for%20c%20in%20_df.columns%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_df.columns%20%3D%20cols%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20%22source%22%20not%20in%20cols%20or%20%22target%22%20not%20in%20cols%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_g%20%3D%20None%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_err%20%3D%20%22CSV%20must%20have%20columns%20'source'%20and%20'target'.%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_df%5B%22source%22%5D%20%3D%20_df%5B%22source%22%5D.astype(str)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_df%5B%22target%22%5D%20%3D%20_df%5B%22target%22%5D.astype(str)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_nodes%20%3D%20sorted(set(_df%5B%22source%22%5D).union(set(_df%5B%22target%22%5D)))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_idx%20%3D%20%7Bn%3A%20i%20for%20i%2C%20n%20in%20enumerate(_nodes)%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_edges%20%3D%20%5B(_idx%5Bs%5D%2C%20_idx%5Bt%5D)%20for%20s%2C%20t%20in%20zip(_df%5B%22source%22%5D%2C%20_df%5B%22target%22%5D)%20if%20s%20!%3D%20t%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_g%20%3D%20ig.Graph(n%3Dlen(_nodes)%2C%20edges%3D_edges%2C%20directed%3DFalse)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_g.simplify()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_g.vs%5B%22name%22%5D%20%3D%20_nodes%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Optional%20third%20column%20with%20per-node%20class%20labels.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_class_col%20%3D%20next((_c%20for%20_c%20in%20(%22class%22%2C%20%22label%22%2C%20%22group%22)%20if%20_c%20in%20cols)%2C%20None)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_class_col%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Build%20a%20node%E2%86%92class%20map%20from%20the%20edge%20list%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20whichever%20value%20appears%20most%20for%20each%20node%20wins%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20(handles%20duplicates%20gracefully).%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_node_cls%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20_s%2C%20_t%2C%20_c%20in%20zip(_df%5B%22source%22%5D%2C%20_df%5B%22target%22%5D%2C%20_df%5B_class_col%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20_node%20in%20(_s%2C%20_t)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_node_cls.setdefault(_node%2C%20%5B%5D).append(_c)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20from%20collections%20import%20Counter%20as%20_Counter%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_per_node%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_Counter(_node_cls.get(_n%2C%20%5B%22%3F%22%5D)).most_common(1)%5B0%5D%5B0%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20_n%20in%20_nodes%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_labels%20%3D%20_coerce_labels(_per_node)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_classes_available%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_is_byod%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_description%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22**User-uploaded%20CSV%20edge%20list**%20with%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%7B_g.vcount()%7D%20nodes%2C%20%7B_g.ecount()%7D%20edges%2C%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22and%20%7Blen(set(_labels))%7D%20classes%20(from%20column%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%60%7B_class_col%7D%60).%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_labels%20%3D%20None%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_classes_available%20%3D%20False%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_is_byod%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_description%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22**User-uploaded%20CSV%20edge%20list**%20with%20%7B_g.vcount()%7D%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22nodes%20and%20%7B_g.ecount()%7D%20edges.%20_No%20%60class%60%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22column%20found%2C%20so%20classification%20panels%20are%20hidden._%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20except%20Exception%20as%20e%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_g%20%3D%20None%0A%20%20%20%20%20%20%20%20%20%20%20%20_err%20%3D%20f%22Failed%20to%20read%20upload%3A%20%7Be%7D%22%0A%20%20%20%20elif%20_choice.startswith(%22Karate%22)%3A%0A%20%20%20%20%20%20%20%20_g%20%3D%20ig.Graph.Famous(%22Zachary%22)%0A%20%20%20%20%20%20%20%20%23%20Conventional%20names%20from%20Zachary%20(1977)%3A%20node%200%20is%20%22Mr%20Hi%22%20(the%0A%20%20%20%20%20%20%20%20%23%20instructor)%20and%20node%2033%20is%20%22Officer%22%20(the%20club%20president).%20The%0A%20%20%20%20%20%20%20%20%23%20other%2032%20members%20are%20anonymised%20-%20we%20just%20label%20them%20by%20index.%0A%20%20%20%20%20%20%20%20_karate_names%20%3D%20%5Bf%22v%7Bi%7D%22%20for%20i%20in%20range(_g.vcount())%5D%0A%20%20%20%20%20%20%20%20_karate_names%5B0%5D%20%3D%20%22Mr%20Hi%22%0A%20%20%20%20%20%20%20%20_karate_names%5B33%5D%20%3D%20%22Officer%22%0A%20%20%20%20%20%20%20%20_g.vs%5B%22name%22%5D%20%3D%20_karate_names%0A%20%20%20%20%20%20%20%20_labels%20%3D%20_zachary_factions.copy()%0A%20%20%20%20%20%20%20%20_description%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22**Zachary%20karate%20club**%20(34%20members%2C%2078%20ties).%20The%20classic%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22split%20into%20Mr%20Hi's%20and%20the%20officer's%20faction%20after%20a%20dispute.%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20elif%20_choice.startswith(%22Les%22)%3A%0A%20%20%20%20%20%20%20%20_g%20%3D%20load_graphml(%22les_miserables.graphml%22)%0A%20%20%20%20%20%20%20%20_g.vs%5B%22name%22%5D%20%3D%20%5Bstr(x)%20for%20x%20in%20_g.vs%5B%22id%22%5D%5D%0A%20%20%20%20%20%20%20%20_labels%20%3D%20np.array(%5Bint(v)%20for%20v%20in%20_g.vs%5B%22value%22%5D%5D)%0A%20%20%20%20%20%20%20%20_description%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22**Les%20Mis%C3%A9rables%20co-appearance%20network**%20(Knuth%201993%3B%20used%20as%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22the%20demo%20dataset%20in%20the%20node2vec%20paper).%2077%20characters%2C%20254%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22co-appearance%20ties%20across%20the%20chapters%20of%20Hugo's%20novel.%20Class%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22labels%20come%20from%20Louvain%20community%20detection%20on%20the%20graph%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22itself%20%E2%80%94%20six%20communities%20that%20line%20up%20with%20the%20novel's%20main%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22social%20circles.%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20elif%20_choice.startswith(%22Upload%22)%3A%0A%20%20%20%20%20%20%20%20%23%20User%20selected%20upload%20but%20nothing%20was%20uploaded%20yet%20%E2%80%94%20fall%20back%20to%20football%0A%20%20%20%20%20%20%20%20_g%20%3D%20load_graphml(%22football_network.graphml%22)%0A%20%20%20%20%20%20%20%20_g.vs%5B%22name%22%5D%20%3D%20list(_g.vs%5B%22id%22%5D)%0A%20%20%20%20%20%20%20%20_labels%20%3D%20np.array(%5Bint(v)%20for%20v%20in%20_g.vs%5B%22value%22%5D%5D)%0A%20%20%20%20%20%20%20%20_description%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22**Football**%20(showing%20while%20you%20choose%20a%20file).%20115%20teams%2C%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22613%20games%2C%2012%20conferences%20as%20classes.%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_g%20%3D%20load_graphml(%22football_network.graphml%22)%0A%20%20%20%20%20%20%20%20_g.vs%5B%22name%22%5D%20%3D%20list(_g.vs%5B%22id%22%5D)%0A%20%20%20%20%20%20%20%20_labels%20%3D%20np.array(%5Bint(v)%20for%20v%20in%20_g.vs%5B%22value%22%5D%5D)%0A%20%20%20%20%20%20%20%20_description%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22**US%20college%20football%20network**%20(Girvan%20%26%20Newman%202002)%3A%20115%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22teams%2C%20613%20games%2C%2012%20conferences.%20Teams%20in%20the%20same%20conference%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22play%20each%20other%20more%20often%2C%20so%20the%20conference%20structure%20is%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22visible%20in%20the%20network.%22%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20if%20_g%20is%20None%3A%0A%20%20%20%20%20%20%20%20graph_data%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22graph%22%3A%20None%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22labels%22%3A%20None%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22names%22%3A%20None%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22name%22%3A%20%22upload-error%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22is_byod%22%3A%20True%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22classes_available%22%3A%20False%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22precomp_prefix%22%3A%20None%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22description%22%3A%20f%22_Could%20not%20build%20a%20graph%3A%20%7B_err%7D._%22%2C%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%23%20Which%20precomputed%20embedding%20bundle%20(if%20any)%20belongs%20to%20this%20graph%3F%0A%20%20%20%20%20%20%20%20if%20_choice.startswith(%22Football%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_prefix%20%3D%20%22%22%0A%20%20%20%20%20%20%20%20elif%20_choice.startswith(%22Karate%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_prefix%20%3D%20%22karate_%22%0A%20%20%20%20%20%20%20%20elif%20_choice.startswith(%22Les%22)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_prefix%20%3D%20%22lesmis_%22%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_prefix%20%3D%20None%0A%20%20%20%20%20%20%20%20graph_data%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22graph%22%3A%20_g%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22labels%22%3A%20_labels%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22names%22%3A%20list(_g.vs%5B%22name%22%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22name%22%3A%20_choice%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22is_byod%22%3A%20_is_byod%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22classes_available%22%3A%20_classes_available%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22precomp_prefix%22%3A%20_prefix%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22description%22%3A%20_description%2C%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20return%20(graph_data%2C)%0A%0A%0A%40app.cell%0Adef%20compute_layout(graph_data%2C%20np)%3A%0A%20%20%20%20_g%20%3D%20graph_data%5B%22graph%22%5D%0A%20%20%20%20_coords%20%3D%20None%0A%20%20%20%20_anchor_idx%20%3D%20None%0A%20%20%20%20if%20_g%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20import%20random%20as%20_random%0A%20%20%20%20%20%20%20%20_random.seed(1546)%0A%20%20%20%20%20%20%20%20np.random.seed(1546)%0A%20%20%20%20%20%20%20%20_g_for_layout%20%3D%20_g.copy()%0A%20%20%20%20%20%20%20%20_layout%20%3D%20_g_for_layout.layout_fruchterman_reingold(niter%3D400)%0A%20%20%20%20%20%20%20%20_coords%20%3D%20np.array(_layout.coords)%0A%0A%20%20%20%20%20%20%20%20%23%20Pick%20three%20anchor%20nodes%20by%20farthest-point%20sampling%20on%20the%0A%20%20%20%20%20%20%20%20%23%20layout.%20We%20use%20their%20layout%20positions%20as%20the%20canonical%20target%0A%20%20%20%20%20%20%20%20%23%20for%20every%202-d%20PCA%20below%2C%20so%20all%20panels%20share%20an%20orientation.%0A%20%20%20%20%20%20%20%20_start%20%3D%20int(np.argmax(_coords%5B%3A%2C%201%5D))%0A%20%20%20%20%20%20%20%20_chosen%20%3D%20%5B_start%5D%0A%20%20%20%20%20%20%20%20for%20_%20in%20range(2)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_d%20%3D%20np.min(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20np.linalg.norm(_coords%20-%20_coords%5B_chosen%5D%5B%3A%2C%20None%5D%2C%20axis%3D2)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20axis%3D0%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20_chosen.append(int(np.argmax(_d)))%0A%20%20%20%20%20%20%20%20_anchor_idx%20%3D%20_chosen%0A%20%20%20%20layout_data%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%22coords%22%3A%20_coords%2C%0A%20%20%20%20%20%20%20%20%22anchor_idx%22%3A%20_anchor_idx%2C%0A%20%20%20%20%20%20%20%20%22anchor_targets%22%3A%20None%20if%20_coords%20is%20None%20else%20_coords%5B_anchor_idx%5D%2C%0A%20%20%20%20%7D%0A%20%20%20%20return%20(layout_data%2C)%0A%0A%0A%40app.cell%0Adef%20stats_panel(graph_data%2C%20mo)%3A%0A%20%20%20%20_g%20%3D%20graph_data%5B%22graph%22%5D%0A%20%20%20%20if%20_g%20is%20None%3A%0A%20%20%20%20%20%20%20%20_stats_md%20%3D%20mo.md(graph_data%5B%22description%22%5D)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_n%20%3D%20_g.vcount()%0A%20%20%20%20%20%20%20%20_m%20%3D%20_g.ecount()%0A%20%20%20%20%20%20%20%20_density%20%3D%202%20*%20_m%20%2F%20(_n%20*%20(_n%20-%201))%20if%20_n%20%3E%201%20else%200.0%0A%20%20%20%20%20%20%20%20_trans%20%3D%20_g.transitivity_undirected(mode%3D%22zero%22)%0A%20%20%20%20%20%20%20%20_n_classes%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20int(len(set(graph_data%5B%22labels%22%5D)))%20if%20graph_data%5B%22labels%22%5D%20is%20not%20None%20else%200%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_classes_line%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22-%20Classes%3A%20**%7B_n_classes%7D**%22%20if%20graph_data%5B%22classes_available%22%5D%20else%20%22-%20Classes%3A%20_none%20(BYOD)_%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_stats_md%20%3D%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20graph_data%5B%22description%22%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%2B%20%22%5Cn%5Cn%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%2B%20f%22-%20Nodes%3A%20**%7B_n%7D**%5Cn%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%2B%20f%22-%20Edges%3A%20**%7B_m%7D**%5Cn%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%2B%20f%22-%20Density%3A%20**%7B_density%3A.3f%7D**%5Cn%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%2B%20f%22-%20Transitivity%20(global%20clustering)%3A%20**%7B_trans%3A.3f%7D**%5Cn%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%2B%20_classes_line%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20_stats_md%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20plot_network(%0A%20%20%20%20LineCollection%2C%0A%20%20%20%20PALETTE%2C%0A%20%20%20%20class_names_for%2C%0A%20%20%20%20graph_data%2C%0A%20%20%20%20layout_data%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20show_node_labels%2C%0A%20%20%20%20struct_anchors%2C%0A)%3A%0A%20%20%20%20_g%20%3D%20graph_data%5B%22graph%22%5D%0A%20%20%20%20mo.stop(_g%20is%20None%2C%20mo.md(%22_(No%20graph%20to%20display.)_%22))%0A%20%20%20%20_coords%20%3D%20layout_data%5B%22coords%22%5D%0A%20%20%20%20_labels%20%3D%20graph_data%5B%22labels%22%5D%0A%20%20%20%20_node_names%20%3D%20graph_data%5B%22names%22%5D%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(8.5%2C%206.5))%0A%20%20%20%20_ax.set_facecolor(%22white%22)%0A%20%20%20%20_segs%20%3D%20%5B%5B_coords%5Be.source%5D%2C%20_coords%5Be.target%5D%5D%20for%20e%20in%20_g.es%5D%0A%20%20%20%20_lc%20%3D%20LineCollection(_segs%2C%20colors%3D%22%23bbbbbb%22%2C%20linewidths%3D0.6%2C%20alpha%3D0.7%2C%20zorder%3D1)%0A%20%20%20%20_ax.add_collection(_lc)%0A%20%20%20%20if%20_labels%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20_classes%20%3D%20sorted(set(int(c)%20for%20c%20in%20_labels))%0A%20%20%20%20%20%20%20%20_names%20%3D%20class_names_for(graph_data)%0A%20%20%20%20%20%20%20%20_name_for%20%3D%20dict(zip(_classes%2C%20_names))%0A%20%20%20%20%20%20%20%20for%20_c%20in%20_classes%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_mask%20%3D%20(_labels%20%3D%3D%20_c)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_coords%5B_mask%2C%200%5D%2C%20_coords%5B_mask%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20s%3D60%2C%20color%3DPALETTE%5Bint(_c)%20%25%20len(PALETTE)%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolor%3D%22%23333333%22%2C%20linewidth%3D0.4%2C%20zorder%3D2%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20label%3D_name_for%5B_c%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_ax.legend(%0A%20%20%20%20%20%20%20%20%20%20%20%20loc%3D%22center%20left%22%2C%20bbox_to_anchor%3D(1.02%2C%200.5)%2C%20fontsize%3D9%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20frameon%3DFalse%2C%20handletextpad%3D0.3%2C%20labelspacing%3D0.4%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20title%3D%22Class%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20_coords%5B%3A%2C%200%5D%2C%20_coords%5B%3A%2C%201%5D%2C%20s%3D55%2C%20c%3D%22%230b789d%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20edgecolor%3D%22%23333333%22%2C%20linewidth%3D0.4%2C%20zorder%3D2%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%23%20Anchor%20names%20are%20always%20shown%20so%20the%20same%20nodes%20are%20identifiable%0A%20%20%20%20%23%20across%20every%20figure%20that%20uses%20the%20layout.%0A%20%20%20%20if%20struct_anchors%20and%20_node_names%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20for%20_i%20in%20struct_anchors%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.scatter(_coords%5B_i%2C%200%5D%2C%20_coords%5B_i%2C%201%5D%2C%20s%3D260%2C%20marker%3D%22s%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20facecolors%3D%22none%22%2C%20edgecolor%3D%22black%22%2C%20linewidth%3D1.8%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D3)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.annotate(str(_node_names%5B_i%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xy%3D(_coords%5B_i%2C%200%5D%2C%20_coords%5B_i%2C%201%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(8%2C%208)%2C%20textcoords%3D%22offset%20points%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D8%2C%20color%3D%22%23111111%22%2C%20fontweight%3D%22bold%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.25%22%2C%20fc%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ec%3D%22%23666666%22%2C%20alpha%3D0.9%2C%20lw%3D0.5)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D5)%0A%20%20%20%20if%20show_node_labels.value%20and%20_node_names%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20for%20_i%2C%20_nm%20in%20enumerate(_node_names)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20struct_anchors%20and%20_i%20in%20struct_anchors%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.annotate(str(_nm)%2C%20xy%3D(_coords%5B_i%2C%200%5D%2C%20_coords%5B_i%2C%201%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(3%2C%203)%2C%20textcoords%3D%22offset%20points%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D6%2C%20color%3D%22%23333333%22%2C%20alpha%3D0.8%2C%20zorder%3D4)%0A%20%20%20%20_ax.set_xticks(%5B%5D)%0A%20%20%20%20_ax.set_yticks(%5B%5D)%0A%20%20%20%20_ax.grid(False)%0A%20%20%20%20_ax.set_title(f%22%7Bgraph_data%5B'name'%5D.split('(')%5B0%5D.strip()%7D%20%20(coloured%20by%20class)%22)%0A%20%20%20%20_ax.set_aspect(%22equal%22)%0A%20%20%20%20_fig.tight_layout()%0A%20%20%20%20_fig%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20sec1_data_note(graph_data%2C%20mo)%3A%0A%20%20%20%20%22%22%22Footnote%20about%20the%20Independents%20in%20the%20football%20data.%22%22%22%0A%20%20%20%20if%20graph_data.get(%22name%22%2C%20%22%22).startswith(%22Football%22)%3A%0A%20%20%20%20%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%20%20%20%20%3E%20**Why%20are%20a%20few%20teams%20in%20odd%20places%20on%20the%20layout%3F**%20The%2012%0A%20%20%20%20%20%20%20%20%3E%20%22classes%22%20come%20from%20the%20original%20Girvan%20%26%20Newman%20(2002)%20data%2C%0A%20%20%20%20%20%20%20%20%3E%20and%20**class%205%20is%20_Independents_**%20%E2%80%94%20Central%20Florida%2C%0A%20%20%20%20%20%20%20%20%3E%20Connecticut%2C%20Navy%2C%20Notre%20Dame%2C%20and%20Utah%20State.%20The%0A%20%20%20%20%20%20%20%20%3E%20Independents%20are%20not%20a%20real%20conference%3A%20they%20don't%20play%20a%0A%20%20%20%20%20%20%20%20%3E%20shared%20round-robin%20schedule%2C%20so%20they%20end%20up%20scattered%20across%0A%20%20%20%20%20%20%20%20%3E%20the%20layout%2C%20embedded%20among%20whichever%20conferences%20they%20happen%0A%20%20%20%20%20%20%20%20%3E%20to%20have%20played%20the%20most.%20These%20five%20are%20also%20the%20nodes%20where%0A%20%20%20%20%20%20%20%20%3E%20**all**%20the%20embedding%20methods%20below%20struggle%20the%20most%20%E2%80%94%20they%0A%20%20%20%20%20%20%20%20%3E%20genuinely%20don't%20have%20a%20conference-shaped%20community%20structure.%0A%20%20%20%20%20%20%20%20%22%22%22)%0A%20%20%20%20elif%20graph_data.get(%22name%22%2C%20%22%22).startswith(%22Karate%22)%3A%0A%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22_The%20two%20classes%20are%20the%20two%20factions%20the%20karate%20club%20split%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22into%20after%20a%20dispute%20between%20Mr%20Hi%20and%20the%20officer%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22(Zachary%201977)._%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20elif%20graph_data.get(%22name%22%2C%20%22%22).startswith(%22Les%22)%3A%0A%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22_The%20communities%20(Bishop's%20circle%2C%20Valjean%20%26%20ex-convicts%2C%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Fantine's%20friends%2C%20the%20Th%C3%A9nardier%20gang%2C%20the%20Gillenormand%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22family%2C%20the%20ABC%20revolutionaries)%20come%20from%20running%20Louvain%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22modularity%20maximisation%20on%20the%20graph%20itself%20%E2%80%94%20so%20this%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22network%20is%20the%20*most*%20community-shaped%20of%20the%20three%2C%20by%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22construction.%20Node2vec's%20DFS-vs-BFS%20contrast%20also%20tends%20to%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22show%20up%20most%20clearly%20here._%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20sec2_header(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%20%20%20%20%23%23%20Section%202%3A%20Spectral%20embeddings%0A%0A%20%20%20%20Spectral%20methods%20turn%20a%20matrix%20that%20describes%20the%20graph%20(the%20adjacency%0A%20%20%20%20matrix%20%24A%24%20or%20the%20Laplacian%20%24L%20%3D%20D%20-%20A%24)%20into%20a%20low-dimensional%0A%20%20%20%20coordinate%20system%20by%20taking%20its%20top%20%E2%80%94%20or%20bottom%20%E2%80%94%20eigenvectors.%20They%0A%20%20%20%20are%20*deterministic*%2C%20*cheap*%2C%20and%20a%20natural%20starting%20point.%0A%0A%20%20%20%20Three%20classics%2C%20side%20by%20side%20on%20the%20same%20network%3A%0A%0A%20%20%20%20-%20**Truncated%20SVD%20of%20%24A%24**%3A%20the%20strongest%20connection%20patterns%20in%0A%20%20%20%20%20%20the%20adjacency%20matrix.%20The%20very%20first%20one%20on%20a%20near-regular%20graph%0A%20%20%20%20%20%20like%20football%20is%20basically%20*node%20degree*%20%E2%80%94%20every%20team%20plays%0A%20%20%20%20%20%20roughly%20ten%20games%2C%20so%20%22how%20many%20games%20does%20this%20team%20play%22%20is%20the%0A%20%20%20%20%20%20single%20biggest%20pattern.%20That's%20why%20the%20SVD%20panel%20below%20has%20a%0A%20%20%20%20%20%20degree-shaped%20first%20axis.%0A%20%20%20%20-%20**PCA%20of%20%24A%24**%3A%20the%20same%20idea%2C%20but%20PCA%20*centres*%20the%20data%20first.%0A%20%20%20%20%20%20Centering%20subtracts%20out%20the%20%22everyone%20plays%20~10%20games%22%20baseline%2C%0A%20%20%20%20%20%20which%20removes%20that%20degree%20mode.%20So%20**PCA-of-%24A%24%20is%20exactly%20the%0A%20%20%20%20%20%20same%20as%20SVD-of-%24A%24%20with%20its%20first%20(degree)%20component%20dropped**%20%E2%80%94%0A%20%20%20%20%20%20we%20verified%20that%20the%20SVD's%20second%20and%20third%20columns%20match%20PCA's%0A%20%20%20%20%20%20first%20and%20second%20columns%20almost%20perfectly.%0A%20%20%20%20-%20**Laplacian%20Eigenmaps**%3A%20the%20smoothest%20variations%20across%20the%0A%20%20%20%20%20%20graph.%20The%20matrix%20%24L_%7B%5Ctext%7Bsym%7D%7D%20%3D%20I%20-%20D%5E%7B-1%2F2%7D%20A%20D%5E%7B-1%2F2%7D%24%20is%0A%20%20%20%20%20%20the%20*normalised*%20Laplacian%20(degree-corrected)%3B%20its%20smallest%0A%20%20%20%20%20%20eigenvectors%20are%20the%20patterns%20that%20change%20*least*%20between%0A%20%20%20%20%20%20neighbours%20%E2%80%94%20and%20that%20is%20exactly%20what%20a%20community%20label%20looks%0A%20%20%20%20%20%20like%20(roughly%20constant%20within%20a%20community%2C%20varying%20between%20them).%0A%20%20%20%20%20%20This%20is%20what%20classical%20spectral%20clustering%20uses.%0A%0A%20%20%20%20Each%20method%20has%20its%20own%20sweet%20spot%20for%20dimensionality%2C%20and%20the%20two%0A%20%20%20%20families%20behave%20in%20**opposite%20ways**%20as%20you%20give%20them%20more%0A%20%20%20%20components%3A%0A%0A%20%20%20%20-%20**SVD%20and%20PCA%3A%20more%20dims%20%E2%86%92%20more%20signal.**%20Every%20direction%20picked%0A%20%20%20%20%20%20up%20by%20SVD%2FPCA%20is%20a%20real%20pattern%20in%20how%20nodes%20connect%20%E2%80%94%20community%2C%0A%20%20%20%20%20%20brokerage%2C%20neighbourhood%20shape%2C%20%E2%80%A6%20none%20of%20them%20is%20noise.%20So%20we%0A%20%20%20%20%20%20use%20**%24k%20%3D%2032%24**%20for%20SVD%2FPCA.%0A%20%20%20%20-%20**Laplacian%20Eigenmaps%3A%20more%20dims%20%E2%86%92%20more%20noise.**%20The%20Laplacian%0A%20%20%20%20%20%20orders%20its%20components%20from%20%22smooth%20across%20the%20whole%20graph%22%20to%0A%20%20%20%20%20%20%22wiggly%20inside%20individual%20communities%22.%20After%20roughly%20**as%20many%0A%20%20%20%20%20%20components%20as%20there%20are%20classes**%2C%20the%20rest%20are%20wiggles%20*inside*%0A%20%20%20%20%20%20the%20existing%20communities%20%E2%80%94%20not%20useful%20for%20telling%20classes%20apart.%0A%20%20%20%20%20%20So%20we%20use%20**%24k%20%5Capprox%202%5Ctimes%5Ctext%7Bn%5C_classes%7D%24%20(max%2016)**.%0A%20%20%20%20%20%20Pushing%20LE%20to%2032%20dimensions%20drops%20its%20F1%20from%20~0.88%20down%20to%0A%20%20%20%20%20%20~0.83.%0A%0A%20%20%20%20%3E%20**Reading%20the%20silhouette%20score.**%20For%20every%20node%2C%20silhouette%0A%20%20%20%20%3E%20compares%20its%20average%20distance%20to%20other%20nodes%20**in%20its%20own%20class**%0A%20%20%20%20%3E%20(%24a%24)%20with%20its%20average%20distance%20to%20the%20**nearest%20other%20class**%0A%20%20%20%20%3E%20(%24b%24)%3A%20%24s%20%3D%20(b%20-%20a)%20%2F%20%5Cmax(a%2C%20b)%24.%20The%20average%20over%20all%20nodes%20is%0A%20%20%20%20%3E%20what%20we%20report.%20Values%20are%20in%20%24%5B-1%2C%201%5D%24%3A%0A%20%20%20%20%3E%20**%24%2B1%24**%20means%20classes%20form%20tight%2C%20well-separated%20clumps%20in%20the%0A%20%20%20%20%3E%20embedding%3B%20**%240%24**%20means%20the%20clumps%20overlap%3B%20**negative**%20values%0A%20%20%20%20%3E%20mean%20nodes%20are%20typically%20closer%20to%20a%20different%20class%20than%20to%20their%0A%20%20%20%20%3E%20own.%20It%20is%20an%20*intrinsic*%20score%20%E2%80%94%20no%20classifier%20is%20fit%2C%20it%20only%0A%20%20%20%20%3E%20looks%20at%20distances%20in%20the%20embedding%20space.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20compute_spectral(PCA%2C%20TruncatedSVD%2C%20graph_data%2C%20mo%2C%20np)%3A%0A%20%20%20%20_g%20%3D%20graph_data%5B%22graph%22%5D%0A%20%20%20%20mo.stop(_g%20is%20None%2C%20mo.md(%22_(No%20graph.)_%22))%0A%20%20%20%20_A%20%3D%20np.array(_g.get_adjacency().data%2C%20dtype%3Dfloat)%0A%20%20%20%20_n%20%3D%20_A.shape%5B0%5D%0A%0A%20%20%20%20%23%20Each%20spectral%20method%20has%20its%20own%20sweet%20spot%2C%20so%20we%20use%20different%0A%20%20%20%20%23%20k's.%20SVD-of-A%20and%20PCA-of-A%20keep%20gaining%20signal%20with%20more%20dims%0A%20%20%20%20%23%20(they're%20general-purpose%20dimensionality%20reductions)%3B%20Laplacian%0A%20%20%20%20%23%20Eigenmaps%20peaks%20around%20k%20~%20number%20of%20clusters%20-%20beyond%20that%20the%0A%20%20%20%20%23%20high-frequency%20Laplacian%20eigenvectors%20are%20essentially%20noise%20and%0A%20%20%20%20%23%20the%20embedding%20*degrades*.%20This%20is%20the%20canonical%20%22k%20~%20%23clusters%22%0A%20%20%20%20%23%20rule%20from%20spectral%20clustering%20(Shi-Malik%201997%2C%20von%20Luxburg%202007).%0A%20%20%20%20_k_full%20%3D%20min(32%2C%20_n%20-%201)%20%20%20%20%20%20%20%20%23%20for%20SVD%20%2F%20PCA%3A%20more%20dims%20help%0A%20%20%20%20if%20graph_data.get(%22classes_available%22)%20and%20graph_data%5B%22labels%22%5D%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20_n_classes%20%3D%20len(set(int(c)%20for%20c%20in%20graph_data%5B%22labels%22%5D))%0A%20%20%20%20%20%20%20%20_k_lap%20%3D%20min(16%2C%20max(4%2C%202%20*%20_n_classes)%2C%20_n%20-%201)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_k_lap%20%3D%20min(16%2C%20_n%20-%201)%20%20%20%20%20%20%23%20for%20LE%3A%20k%20tied%20to%20%23clusters%0A%0A%20%20%20%20%23%20Truncated%20SVD%20of%20A.%20We%20keep%20all%20k%20components%2C%20including%20the%20top%0A%20%20%20%20%23%20singular%20vector.%20That%20top%20vector%20is%20Perron-Frobenius%20-%20on%20a%20near-%0A%20%20%20%20%23%20regular%20graph%20it%20correlates%20~0.75%20with%20degree%20centrality%20-%20but%0A%20%20%20%20%23%20the%20downstream%20classifier%20ignores%20it%20(degree%20doesn't%20separate%0A%20%20%20%20%23%20conferences)%2C%20so%20it%20doesn't%20hurt%20F1%20and%20it%20lets%20the%20SVD%20panel%0A%20%20%20%20%23%20stay%20visibly%20different%20from%20the%20centered%20PCA%20panel.%0A%20%20%20%20_svd%20%3D%20TruncatedSVD(n_components%3D_k_full%2C%20random_state%3D1546)%0A%20%20%20%20_emb_svd%20%3D%20_svd.fit_transform(_A)%0A%0A%20%20%20%20%23%20Laplacian%20Eigenmaps%20with%20the%20symmetric%20normalised%20Laplacian%0A%20%20%20%20%23%20L_sym%20%3D%20I%20-%20D%5E%7B-1%2F2%7D%20A%20D%5E%7B-1%2F2%7D%20(Shi-Malik%201997%2C%20Ng-Jordan-Weiss%0A%20%20%20%20%23%202002).%20np.linalg.eigh%20returns%20ascending%20eigenvalues%2C%20so%20cols%0A%20%20%20%20%23%201..k%20are%20the%20bottom-k%20non-trivial%20eigenvectors.%0A%20%20%20%20_deg%20%3D%20_A.sum(axis%3D1)%0A%20%20%20%20_d_inv_sqrt%20%3D%20np.zeros_like(_deg)%0A%20%20%20%20_nz%20%3D%20_deg%20%3E%200%0A%20%20%20%20_d_inv_sqrt%5B_nz%5D%20%3D%201.0%20%2F%20np.sqrt(_deg%5B_nz%5D)%0A%20%20%20%20_A_norm%20%3D%20_A%20*%20_d_inv_sqrt%5B%3A%2C%20None%5D%20*%20_d_inv_sqrt%5BNone%2C%20%3A%5D%0A%20%20%20%20_L_sym%20%3D%20np.eye(_n)%20-%20_A_norm%0A%20%20%20%20_w%2C%20_v%20%3D%20np.linalg.eigh(_L_sym)%0A%20%20%20%20_emb_lap%20%3D%20_v%5B%3A%2C%201%20%3A%20_k_lap%20%2B%201%5D%0A%0A%20%20%20%20_pca%20%3D%20PCA(n_components%3D_k_full%2C%20random_state%3D1546)%0A%20%20%20%20_emb_pca%20%3D%20_pca.fit_transform(_A)%0A%0A%20%20%20%20spectral_embs%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%22Truncated%20SVD%20(of%20A)%22%3A%20np.asarray(_emb_svd%2C%20dtype%3Dfloat)%2C%0A%20%20%20%20%20%20%20%20%22Laplacian%20Eigenmaps%20(of%20L_sym)%22%3A%20np.asarray(_emb_lap%2C%20dtype%3Dfloat)%2C%0A%20%20%20%20%20%20%20%20%22PCA%20(of%20A)%22%3A%20np.asarray(_emb_pca%2C%20dtype%3Dfloat)%2C%0A%20%20%20%20%7D%0A%20%20%20%20%23%20%22Primary%22%20spectral%20embedding%20used%20downstream%20(Section%205).%0A%20%20%20%20spectral_emb%20%3D%20spectral_embs%5B%22Laplacian%20Eigenmaps%20(of%20L_sym)%22%5D%0A%20%20%20%20spectral_k%20%3D%20%7B%22svd_pca%22%3A%20_k_full%2C%20%22lap%22%3A%20_k_lap%7D%0A%20%20%20%20return%20(spectral_embs%2C)%0A%0A%0A%40app.cell%0Adef%20plot_spectral(%0A%20%20%20%20KMeans%2C%0A%20%20%20%20PALETTE%2C%0A%20%20%20%20graph_data%2C%0A%20%20%20%20layout_data%2C%0A%20%20%20%20network_with_cluster_colors%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20procrustes_align%2C%0A%20%20%20%20show_node_labels%2C%0A%20%20%20%20silhouette_score%2C%0A%20%20%20%20spectral_embs%2C%0A%20%20%20%20struct_anchors%2C%0A)%3A%0A%20%20%20%20_labels%20%3D%20graph_data%5B%22labels%22%5D%0A%20%20%20%20_names%20%3D%20graph_data%5B%22names%22%5D%0A%20%20%20%20_anchor_idx%20%3D%20layout_data%5B%22anchor_idx%22%5D%0A%20%20%20%20_anchor_targets%20%3D%20layout_data%5B%22anchor_targets%22%5D%0A%20%20%20%20_coords%20%3D%20layout_data%5B%22coords%22%5D%0A%20%20%20%20_g%20%3D%20graph_data%5B%22graph%22%5D%0A%20%20%20%20_n_classes%20%3D%20len(set(int(c)%20for%20c%20in%20_labels))%20if%20_labels%20is%20not%20None%20else%204%0A%20%20%20%20_fig%2C%20_axes%20%3D%20plt.subplots(2%2C%203%2C%20figsize%3D(14.5%2C%209.0)%2C%20height_ratios%3D%5B1%2C%201%5D)%0A%20%20%20%20for%20_ax%2C%20(_name%2C%20_emb)%20in%20zip(_axes%5B0%5D%2C%20spectral_embs.items())%3A%0A%20%20%20%20%20%20%20%20%23%20Plot%20the%20first%20two%20raw%20dimensions%20of%20each%20method%2C%20honestly.%0A%20%20%20%20%20%20%20%20%23%20For%20SVD-of-A%20this%20means%20dim%200%20is%20roughly%20degree%20(the%0A%20%20%20%20%20%20%20%20%23%20Perron-Frobenius%20eigenvector)%3B%20the%20SVD%20panel%20therefore%20looks%0A%20%20%20%20%20%20%20%20%23%20different%20from%20PCA%2C%20and%20the%20*very*%20next%20pair%20of%20SVD%20dims%0A%20%20%20%20%20%20%20%20%23%20(cols%201%2C%202)%20is%20what%20PCA's%20cols%200%2C%201%20already%20are.%20Z-score%20each%0A%20%20%20%20%20%20%20%20%23%20axis%20so%20panels%20with%20very%20different%20per-column%20scales%20don't%0A%20%20%20%20%20%20%20%20%23%20collapse%20under%20the%20isotropic%20Procrustes%20rescale.%0A%20%20%20%20%20%20%20%20_emb2%20%3D%20_emb%5B%3A%2C%20%3A2%5D.astype(float)%0A%20%20%20%20%20%20%20%20_emb2%20%3D%20(_emb2%20-%20_emb2.mean(axis%3D0))%20%2F%20(_emb2.std(axis%3D0)%20%2B%201e-12)%0A%20%20%20%20%20%20%20%20if%20_anchor_idx%20is%20not%20None%20and%20_anchor_targets%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_emb2%20%3D%20procrustes_align(_emb2%2C%20_anchor_idx%2C%20_anchor_targets)%0A%20%20%20%20%20%20%20%20if%20_labels%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_colors%20%3D%20%5BPALETTE%5Bint(c)%20%25%20len(PALETTE)%5D%20for%20c%20in%20_labels%5D%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_colors%20%3D%20%5B%22%230b789d%22%5D%20*%20_emb.shape%5B0%5D%0A%20%20%20%20%20%20%20%20_ax.scatter(_emb2%5B%3A%2C%200%5D%2C%20_emb2%5B%3A%2C%201%5D%2C%20s%3D45%2C%20c%3D_colors%2C%20edgecolor%3D%22%23333333%22%2C%20linewidth%3D0.4)%0A%20%20%20%20%20%20%20%20%23%20Anchor%20squares%20(hollow%20black)%20on%20the%20spectral%20panels%20too.%0A%20%20%20%20%20%20%20%20if%20struct_anchors%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_i%20in%20struct_anchors%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_emb2%5B_i%2C%200%5D%2C%20_emb2%5B_i%2C%201%5D%2C%20s%3D280%2C%20marker%3D%22s%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20facecolors%3D%22none%22%2C%20edgecolor%3D%22black%22%2C%20linewidth%3D1.8%2C%20zorder%3D5%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax.annotate(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20str(_names%5B_i%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xy%3D(_emb2%5B_i%2C%200%5D%2C%20_emb2%5B_i%2C%201%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(8%2C%208)%2C%20textcoords%3D%22offset%20points%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D7%2C%20color%3D%22%23222222%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.2%22%2C%20fc%3D%22white%22%2C%20ec%3D%22%23888888%22%2C%20alpha%3D0.9%2C%20lw%3D0.5)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20if%20show_node_labels.value%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_i%2C%20_nm%20in%20enumerate(_names)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20struct_anchors%20and%20_i%20in%20struct_anchors%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax.annotate(str(_nm)%2C%20xy%3D(_emb2%5B_i%2C%200%5D%2C%20_emb2%5B_i%2C%201%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(3%2C%203)%2C%20textcoords%3D%22offset%20points%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D6%2C%20color%3D%22%23444444%22%2C%20alpha%3D0.7%2C%20zorder%3D4)%0A%20%20%20%20%20%20%20%20_ax.set_xticks(%5B%5D)%0A%20%20%20%20%20%20%20%20_ax.set_yticks(%5B%5D)%0A%20%20%20%20%20%20%20%20_ax.grid(False)%0A%20%20%20%20%20%20%20%20_ax.set_aspect(%22equal%22)%0A%20%20%20%20%20%20%20%20_ax.set_title(_name)%0A%20%20%20%20%20%20%20%20if%20_labels%20is%20not%20None%20and%20len(set(_labels))%20%3E%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_sil%20%3D%20silhouette_score(_emb%2C%20_labels)%0A%20%20%20%20%20%20%20%20%20%20%20%20_sil_txt%20%3D%20f%22silhouette%20%3D%20%7B_sil%3A.3f%7D%22%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_sil_txt%20%3D%20%22silhouette%3A%20n%2Fa%22%0A%20%20%20%20%20%20%20%20_ax.text(%0A%20%20%20%20%20%20%20%20%20%20%20%200.98%2C%0A%20%20%20%20%20%20%20%20%20%20%20%200.02%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20_sil_txt%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20transform%3D_ax.transAxes%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22right%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20va%3D%22bottom%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D10%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.3%22%2C%20fc%3D%22white%22%2C%20ec%3D%22%23888888%22%2C%20alpha%3D0.9)%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%23%20Bottom%20row%3A%20same%20network%20laid%20out%20by%20FR%2C%20coloured%20by%20k-means%20on%0A%20%20%20%20%23%20each%20embedding.%20The%20clusters%20should%20look%20like%20the%20true%20community%0A%20%20%20%20%23%20palette%20for%20methods%20that%20capture%20homophily%2C%20and%20cut%20across%0A%20%20%20%20%23%20communities%20for%20methods%20that%20don't.%0A%20%20%20%20if%20_g%20is%20not%20None%20and%20_coords%20is%20not%20None%20and%20_n_classes%20%3E%3D%202%3A%0A%20%20%20%20%20%20%20%20for%20_ax%2C%20(_name%2C%20_emb)%20in%20zip(_axes%5B1%5D%2C%20spectral_embs.items())%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_km%20%3D%20KMeans(n_clusters%3D_n_classes%2C%20n_init%3D10%2C%20random_state%3D1546).fit(_emb)%0A%20%20%20%20%20%20%20%20%20%20%20%20network_with_cluster_colors(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax%2C%20_g%2C%20_coords%2C%20_g.es%2C%20_km.labels_%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20struct_anchors%3Dstruct_anchors%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20title%3Df%22network%20coloured%20by%20k-means%20on%20%7B_name.split('(')%5B0%5D.strip()%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20names%3D_names%2C%20show_labels%3Dshow_node_labels.value%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20_fig.tight_layout()%0A%20%20%20%20_fig%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20sec3_header(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%20%20%20%20%23%23%20Section%203%3A%20Random%20walks%20and%20node2vec%0A%0A%20%20%20%20Pick%20a%20node.%20Start%20walking.%20The%20neighbours%20you%20tend%20to%20visit%0A%20%20%20%20together%20capture%20the%20local%20structure%20of%20the%20graph.%20**node2vec**%0A%20%20%20%20turns%20these%20walks%20into%20vectors%20with%20*word2vec*%20%E2%80%94%20yes%2C%20the%20NLP%20one%20%E2%80%94%0A%20%20%20%20by%20treating%20each%20walk%20as%20a%20sentence%20and%20each%20node%20as%20a%20token.%0A%0A%20%20%20%20Two%20parameters%20shape%20the%20walk%3A%0A%0A%20%20%20%20-%20**%24p%24%20(return%20bias)**%3A%20%24p%20%3C%201%24%20encourages%20**going%20back**%20to%20the%0A%20%20%20%20%20%20previous%20node%3B%20%24p%20%3E%201%24%20discourages%20it.%0A%20%20%20%20-%20**%24q%24%20(in-out%20bias)**%3A%20%24q%20%3C%201%24%20pushes%20the%20walk%20**outward**%0A%20%20%20%20%20%20(depth-first%20%E2%86%92%20**homophily%20%2F%20community**%20structure)%3B%20%24q%20%3E%201%24%0A%20%20%20%20%20%20keeps%20it%20**close**%20to%20the%20start%20(breadth-first%20%E2%86%92%20**structural%0A%20%20%20%20%20%20roles**).%0A%0A%20%20%20%20Move%20the%20sliders%20to%20see%20how%20a%20single%20walk%20changes%3B%20click%20**%E2%86%BB%20Roll%0A%20%20%20%20a%20new%20walk**%20to%20draw%20another%20one%20without%20changing%20the%20parameters.%0A%20%20%20%20The%20sliders%20only%20drive%20this%20illustration%20%E2%80%94%20the%20three%20node2vec%0A%20%20%20%20panels%20further%20down%20come%20from%20a%20separate%2C%20pre-trained%20run.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20sec3_walk_widgets(graph_data%2C%20mo)%3A%0A%20%20%20%20_g%20%3D%20graph_data%5B%22graph%22%5D%0A%20%20%20%20if%20_g%20is%20None%3A%0A%20%20%20%20%20%20%20%20start_node%20%3D%20mo.ui.dropdown(options%3D%5B%22%E2%80%94%22%5D%2C%20value%3D%22%E2%80%94%22%2C%20label%3D%22Start%20node%22)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_names%20%3D%20list(graph_data%5B%22names%22%5D)%0A%20%20%20%20%20%20%20%20start_node%20%3D%20mo.ui.dropdown(options%3D_names%2C%20value%3D_names%5B0%5D%2C%20label%3D%22Start%20node%22)%0A%20%20%20%20walk_length%20%3D%20mo.ui.slider(start%3D3%2C%20stop%3D20%2C%20step%3D1%2C%20value%3D10%2C%20label%3D%22Walk%20length%22)%0A%20%20%20%20p_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D0.1%2C%20stop%3D10.0%2C%20step%3D0.1%2C%20value%3D1.0%2C%20label%3D%22p%20(return%20bias)%22%2C%0A%20%20%20%20%20%20%20%20show_value%3DTrue%2C%0A%20%20%20%20)%0A%20%20%20%20q_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D0.1%2C%20stop%3D10.0%2C%20step%3D0.1%2C%20value%3D1.0%2C%20label%3D%22q%20(in-out%20bias)%22%2C%0A%20%20%20%20%20%20%20%20show_value%3DTrue%2C%0A%20%20%20%20)%0A%20%20%20%20%23%20A%20button%20to%20re-roll%20the%20walk%20without%20touching%20the%20sliders.%20Pressing%0A%20%20%20%20%23%20it%20increments%20a%20counter%20that%20sample_walk%20re-reads%2C%20so%20the%20cell%0A%20%20%20%20%23%20re-fires%20with%20a%20fresh%20RNG%20seed.%0A%20%20%20%20reroll%20%3D%20mo.ui.run_button(label%3D%22%E2%86%BB%20Roll%20a%20new%20walk%22)%0A%20%20%20%20return%20p_slider%2C%20q_slider%2C%20reroll%2C%20start_node%2C%20walk_length%0A%0A%0A%40app.cell%0Adef%20sample_walk(%0A%20%20%20%20biased_walk%2C%0A%20%20%20%20graph_data%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20np%2C%0A%20%20%20%20p_slider%2C%0A%20%20%20%20q_slider%2C%0A%20%20%20%20reroll%2C%0A%20%20%20%20start_node%2C%0A%20%20%20%20walk_length%2C%0A)%3A%0A%20%20%20%20_g%20%3D%20graph_data%5B%22graph%22%5D%0A%20%20%20%20mo.stop(_g%20is%20None%2C%20mo.md(%22_(No%20graph.)_%22))%0A%20%20%20%20%23%20Touch%20reroll.value%20so%20the%20cell%20re-fires%20when%20the%20button%20is%20clicked%0A%20%20%20%20%23%20(its%20value%20is%20the%20click%20count).%20A%20fresh%20RNG%20seed%20each%20time.%0A%20%20%20%20_%20%3D%20reroll.value%0A%20%20%20%20_names%20%3D%20graph_data%5B%22names%22%5D%0A%20%20%20%20_name_to_idx%20%3D%20%7Bn%3A%20i%20for%20i%2C%20n%20in%20enumerate(_names)%7D%0A%20%20%20%20_start_idx%20%3D%20_name_to_idx.get(start_node.value%2C%200)%0A%0A%20%20%20%20_rng%20%3D%20np.random.default_rng()%0A%20%20%20%20walk_indices%20%3D%20biased_walk(%0A%20%20%20%20%20%20%20%20_g%2C%20_start_idx%2C%20int(walk_length.value)%2C%0A%20%20%20%20%20%20%20%20float(p_slider.value)%2C%20float(q_slider.value)%2C%20_rng%2C%0A%20%20%20%20)%0A%20%20%20%20return%20(walk_indices%2C)%0A%0A%0A%40app.cell%0Adef%20plot_walk(%0A%20%20%20%20LineCollection%2C%0A%20%20%20%20PALETTE%2C%0A%20%20%20%20graph_data%2C%0A%20%20%20%20layout_data%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20walk_indices%2C%0A)%3A%0A%20%20%20%20_g%20%3D%20graph_data%5B%22graph%22%5D%0A%20%20%20%20mo.stop(_g%20is%20None%2C%20mo.md(%22_(No%20graph.)_%22))%0A%20%20%20%20_coords%20%3D%20layout_data%5B%22coords%22%5D%0A%20%20%20%20_labels%20%3D%20graph_data%5B%22labels%22%5D%0A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(6.5%2C%205.5))%0A%20%20%20%20_ax.set_facecolor(%22white%22)%0A%20%20%20%20_bg%20%3D%20%5B%5B_coords%5Be.source%5D%2C%20_coords%5Be.target%5D%5D%20for%20e%20in%20_g.es%5D%0A%20%20%20%20_bg_lc%20%3D%20LineCollection(_bg%2C%20colors%3D%22%23dddddd%22%2C%20linewidths%3D0.5%2C%20alpha%3D0.7%2C%20zorder%3D1)%0A%20%20%20%20_ax.add_collection(_bg_lc)%0A%20%20%20%20if%20_labels%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20_colors%20%3D%20%5BPALETTE%5Bint(c)%20%25%20len(PALETTE)%5D%20for%20c%20in%20_labels%5D%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_colors%20%3D%20%5B%22%23cccccc%22%5D%20*%20_g.vcount()%0A%20%20%20%20_ax.scatter(_coords%5B%3A%2C%200%5D%2C%20_coords%5B%3A%2C%201%5D%2C%20s%3D35%2C%20c%3D_colors%2C%20edgecolor%3D%22%23777777%22%2C%20linewidth%3D0.3%2C%20zorder%3D2%2C%20alpha%3D0.75)%0A%20%20%20%20_walk_segs%20%3D%20%5B%5D%0A%20%20%20%20for%20i%20in%20range(len(walk_indices)%20-%201)%3A%0A%20%20%20%20%20%20%20%20_walk_segs.append(%5B_coords%5Bwalk_indices%5Bi%5D%5D%2C%20_coords%5Bwalk_indices%5Bi%20%2B%201%5D%5D%5D)%0A%20%20%20%20if%20_walk_segs%3A%0A%20%20%20%20%20%20%20%20_walk_lc%20%3D%20LineCollection(_walk_segs%2C%20colors%3D%22%23d62728%22%2C%20linewidths%3D2.2%2C%20alpha%3D0.85%2C%20zorder%3D3)%0A%20%20%20%20%20%20%20%20_ax.add_collection(_walk_lc)%0A%20%20%20%20_wx%20%3D%20%5B_coords%5Bi%2C%200%5D%20for%20i%20in%20walk_indices%5D%0A%20%20%20%20_wy%20%3D%20%5B_coords%5Bi%2C%201%5D%20for%20i%20in%20walk_indices%5D%0A%20%20%20%20_ax.scatter(_wx%2C%20_wy%2C%20s%3D80%2C%20facecolor%3D%22%23d62728%22%2C%20edgecolor%3D%22black%22%2C%20linewidth%3D0.6%2C%20zorder%3D4)%0A%20%20%20%20_ax.scatter(%5B_coords%5Bwalk_indices%5B0%5D%2C%200%5D%5D%2C%20%5B_coords%5Bwalk_indices%5B0%5D%2C%201%5D%5D%2C%20s%3D180%2C%20facecolor%3D%22gold%22%2C%20edgecolor%3D%22black%22%2C%20linewidth%3D1.0%2C%20zorder%3D5%2C%20label%3D%22start%22)%0A%20%20%20%20_ax.legend(loc%3D%22upper%20right%22%2C%20fontsize%3D10)%0A%20%20%20%20_ax.set_xticks(%5B%5D)%0A%20%20%20%20_ax.set_yticks(%5B%5D)%0A%20%20%20%20_ax.grid(False)%0A%20%20%20%20_ax.set_title(f%22A%20biased%20random%20walk%20of%20length%20%7Blen(walk_indices)%7D%22)%0A%20%20%20%20_ax.set_aspect(%22equal%22)%0A%20%20%20%20_fig.tight_layout()%0A%20%20%20%20walk_fig%20%3D%20_fig%0A%20%20%20%20return%20(walk_fig%2C)%0A%0A%0A%40app.cell%0Adef%20walk_sentence(graph_data%2C%20mo%2C%20walk_indices)%3A%0A%20%20%20%20_names%20%3D%20graph_data%5B%22names%22%5D%0A%20%20%20%20_sentence%20%3D%20%22%20-%3E%20%22.join(_names%5Bi%5D%20for%20i%20in%20walk_indices)%0A%20%20%20%20walk_sentence_md%20%3D%20mo.md(f%22**The%20walk%20as%20a%20sentence%3A**%5Cn%5Cn%60%7B_sentence%7D%60%22)%0A%20%20%20%20return%20(walk_sentence_md%2C)%0A%0A%0A%40app.cell%0Adef%20sec3_layout(%0A%20%20%20%20mo%2C%0A%20%20%20%20p_slider%2C%0A%20%20%20%20q_slider%2C%0A%20%20%20%20reroll%2C%0A%20%20%20%20start_node%2C%0A%20%20%20%20walk_fig%2C%0A%20%20%20%20walk_length%2C%0A%20%20%20%20walk_sentence_md%2C%0A)%3A%0A%20%20%20%20_left%20%3D%20mo.vstack(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%22**Tweak%20the%20walk%3A**%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20start_node%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20walk_length%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20p_slider%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20q_slider%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20reroll%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.md(%22---%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20walk_sentence_md%2C%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%20%20%20%20gap%3D0.6%2C%0A%20%20%20%20)%0A%20%20%20%20mo.hstack(%5B_left%2C%20walk_fig%5D%2C%20widths%3D%5B1%2C%201.4%5D%2C%20gap%3D1.2%2C%20align%3D%22start%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20sec3_n2v_intro(graph_data%2C%20mo)%3A%0A%20%20%20%20_g%20%3D%20graph_data%5B%22graph%22%5D%0A%20%20%20%20if%20_g%20is%20None%20or%20graph_data%5B%22precomp_prefix%22%5D%20is%20None%3A%0A%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22_Node2vec%20embeddings%20are%20precomputed%20only%20for%20the%20football%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22and%20karate%20networks.%20Switch%20to%20one%20of%20those%20to%20see%20the%20three%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%24q%24-settings%20below._%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%23%20node2vec%20embeddings%20at%20three%20%24q%24%20settings%0A%0A%20%20%20%20%20%20%20%20Repeat%20the%20biased%20walk%20above%20many%20times%20from%20every%20node%2C%20feed%0A%20%20%20%20%20%20%20%20the%20corpus%20of%20walks%20into%20word2vec%2C%20and%20you%20get%20a%2016-d%20vector%0A%20%20%20%20%20%20%20%20per%20node.%20The%20three%20panels%20share%20the%20same%20walk%20settings%20%E2%80%94%0A%20%20%20%20%20%20%20%20**length%2050%2C%2010%20walks%20per%20node%2C%20window%2010**%20%E2%80%94%20and%20only%20the%0A%20%20%20%20%20%20%20%20in-out%20bias%20%24q%24%20changes%3A%0A%0A%20%20%20%20%20%20%20%20-%20**%24q%20%3D%200.1%24%20(very%20DFS)**%3A%20walks%20strongly%20prefer%20stepping%0A%20%20%20%20%20%20%20%20%20%20*outward*%20from%20each%20start%20%E2%86%92%20embedding%20leans%20toward%0A%20%20%20%20%20%20%20%20%20%20**homophily%20%2F%20community**.%0A%20%20%20%20%20%20%20%20-%20**%24q%20%3D%201%24**%3A%20vanilla%20random%20walk.%0A%20%20%20%20%20%20%20%20-%20**%24q%20%3D%2010%24%20(very%20BFS)**%3A%20walks%20strongly%20prefer%20**staying%0A%20%20%20%20%20%20%20%20%20%20close**%20to%20each%20start%20%E2%86%92%20embedding%20leans%20toward%0A%20%20%20%20%20%20%20%20%20%20**structural%20role**.%0A%0A%20%20%20%20%20%20%20%20We%20pushed%20%24q%24%20further%20than%20the%20paper's%20%24q%3D0.5%24%20%2F%20%24q%3D2%24%20because%0A%20%20%20%20%20%20%20%20on%20the%20small%2C%20dense%20graphs%20in%20this%20app%20the%20paper's%20range%0A%20%20%20%20%20%20%20%20produces%20panels%20that%20look%20almost%20identical.%20Even%20at%20%24q%3D10%24%20the%0A%20%20%20%20%20%20%20%20contrast%20is%20**subtle%20in%20the%20raw%20scatter**%20(the%20embeddings%20still%0A%20%20%20%20%20%20%20%20share%20most%20of%20their%20global%20structure)%3B%20the%20visible%20story%20lives%0A%20%20%20%20%20%20%20%20in%20the%20*bottom%20row*%20%E2%80%94%20the%20k-means%20cluster%20colouring%20on%20the%0A%20%20%20%20%20%20%20%20network.%20_Honest%20caveat%3A_%20standard%20node2vec%20uses%0A%20%20%20%20%20%20%20%20named-neighbour%20co-occurrence%2C%20so%20it%20can%20recognise%20*types*%20of%0A%20%20%20%20%20%20%20%20community%20structure%2C%20but%20it%20cannot%20really%20put%20two%20distant%0A%20%20%20%20%20%20%20%20sub-protagonists%20in%20the%20same%20cluster%20just%20because%20they%20share%0A%20%20%20%20%20%20%20%20a%20structural%20role.%20For%20pure%20structural-role%20detection%20the%0A%20%20%20%20%20%20%20%20right%20tools%20are%20struc2vec%20%2F%20GraphWave.%0A%0A%20%20%20%20%20%20%20%20_Top%20row_%3A%202-d%20**t-SNE**%20of%20each%2032-d%20embedding%20(linear%0A%20%20%20%20%20%20%20%20projections%20look%20near-identical%20here%3B%20t-SNE%20preserves%20local%0A%20%20%20%20%20%20%20%20geometry%20where%20the%20actual%20contrast%20lives).%0A%0A%20%20%20%20%20%20%20%20_Bottom%20row_%3A%20the%20**same%20network%20laid%20out%20as%20in%20Section%201**%2C%0A%20%20%20%20%20%20%20%20but%20coloured%20by%20**k-means%20on%20each%20embedding**%20instead%20of%20the%0A%20%20%20%20%20%20%20%20true%20labels%20%E2%80%94%20exactly%20as%20in%20Figure%203%20of%20the%20node2vec%20paper%0A%20%20%20%20%20%20%20%20(Grover%20%26%20Leskovec%202016).%20For%20a%20homophily%20embedding%20the%0A%20%20%20%20%20%20%20%20colours%20should%20*match*%20the%20community%20palette%20from%20Section%201%3B%0A%20%20%20%20%20%20%20%20for%20a%20structural-role%20embedding%20they%20should%20*cut%20across*%0A%20%20%20%20%20%20%20%20communities%20%E2%80%94%20bridges%20in%20different%20parts%20of%20the%20graph%20end%20up%0A%20%20%20%20%20%20%20%20the%20same%20colour.%0A%0A%20%20%20%20%20%20%20%20**%E2%98%85%20Watch%20the%20three%20gold%20stars.**%20They%20are%20the%0A%20%20%20%20%20%20%20%20highest-**betweenness**%20node%20in%20three%20different%20classes%20%E2%80%94%20i.e.%0A%20%20%20%20%20%20%20%20three%20%22bridges%22%20between%20communities.%20Bridges%20have%20a%20similar%0A%20%20%20%20%20%20%20%20structural%20role%20even%20though%20they%20live%20in%20different%20parts%20of%0A%20%20%20%20%20%20%20%20the%20network.%20The%20%22**hub%20pull**%22%20number%20under%20each%20panel%0A%20%20%20%20%20%20%20%20measures%20how%20close%20those%20three%20end%20up%20in%20the%20embedding%0A%20%20%20%20%20%20%20%20compared%20with%20three%20random%20nodes%3A%0A%0A%20%20%20%20%20%20%20%20-%20values%20**below%201**%20%E2%86%92%20bridges%20are%20pulled%20*together*%20(the%0A%20%20%20%20%20%20%20%20%20%20embedding%20sees%20them%20as%20structurally%20similar%20regardless%20of%0A%20%20%20%20%20%20%20%20%20%20community)%3B%20this%20is%20the%20**BFS%20%2F%20structural**%20signature.%0A%20%20%20%20%20%20%20%20-%20values%20**above%201**%20%E2%86%92%20bridges%20are%20pushed%20*apart*%20(the%0A%20%20%20%20%20%20%20%20%20%20embedding%20has%20organised%20them%20by%20community)%3B%20this%20is%20the%0A%20%20%20%20%20%20%20%20%20%20**DFS%20%2F%20homophily**%20signature.%0A%20%20%20%20%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20load_n2v_all(graph_data%2C%20load_npy)%3A%0A%20%20%20%20_g%20%3D%20graph_data%5B%22graph%22%5D%0A%20%20%20%20_prefix%20%3D%20graph_data%5B%22precomp_prefix%22%5D%0A%20%20%20%20if%20_g%20is%20None%20or%20_prefix%20is%20None%3A%0A%20%20%20%20%20%20%20%20n2v_embs%20%3D%20None%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%23%20Paper-faithful%20(Grover%20%26%20Leskovec%202016%2C%20Fig%203)%3A%20same%20walk%0A%20%20%20%20%20%20%20%20%23%20config%20across%20the%20three%2C%20only%20q%20varies.%0A%20%20%20%20%20%20%20%20n2v_embs%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22DFS%20(p%3D1%2C%20q%3D0.1)%5Cn%E2%86%92%20homophily%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20load_npy(f%22%7B_prefix%7Dnode2vec_dfs.npy%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22balanced%20(p%3D1%2C%20q%3D1)%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20load_npy(f%22%7B_prefix%7Dnode2vec_balanced.npy%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22BFS%20(p%3D1%2C%20q%3D10)%5Cn%E2%86%92%20structural%20roles%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20load_npy(f%22%7B_prefix%7Dnode2vec_bfs.npy%22)%2C%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20return%20(n2v_embs%2C)%0A%0A%0A%40app.cell%0Adef%20select_structural_anchors(graph_data%2C%20np)%3A%0A%20%20%20%20%22%22%22Pick%20a%20few%20nodes%20that%20have%20*similar%20structural%20role*%20(high%0A%20%20%20%20betweenness%20%E2%80%94%20they%20sit%20on%20shortcuts%20between%20communities)%20but%20live%0A%20%20%20%20in%20*different%20classes*.%20High-betweenness%20nodes%20are%20the%20canonical%0A%20%20%20%20'bridges'%20of%20a%20network%3A%20they%20have%20a%20comparable%20structural%20job%0A%20%20%20%20even%20when%20they%20live%20in%20different%20parts%20of%20the%20graph.%20On%20football%0A%20%20%20%20this%20picks%20up%20Notre%20Dame%20(an%20Independent%20%E2%80%94%20a%20literal%20cross-%0A%20%20%20%20conference%20bridge)%3B%20on%20Les%20Mis%20it%20picks%20up%20Valjean%2C%20Myriel%2C%20and%0A%20%20%20%20Gavroche%20%E2%80%94%20the%20three%20characters%20who%20connect%20the%20most%20disparate%0A%20%20%20%20parts%20of%20the%20novel.%22%22%22%0A%20%20%20%20_g%20%3D%20graph_data%5B%22graph%22%5D%0A%20%20%20%20_labels%20%3D%20graph_data%5B%22labels%22%5D%0A%20%20%20%20if%20_g%20is%20None%20or%20_labels%20is%20None%3A%0A%20%20%20%20%20%20%20%20struct_anchors%20%3D%20%5B%5D%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_bet%20%3D%20np.array(_g.betweenness())%0A%20%20%20%20%20%20%20%20_classes%20%3D%20sorted(set(int(c)%20for%20c%20in%20_labels))%0A%20%20%20%20%20%20%20%20_candidates%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20_c%20in%20_classes%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_mask%20%3D%20(_labels%20%3D%3D%20_c)%0A%20%20%20%20%20%20%20%20%20%20%20%20_idx%20%3D%20np.where(_mask)%5B0%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20len(_idx)%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%20%20%20%20%20%20%20%20%20%20%20%20_best%20%3D%20int(_idx%5Bnp.argmax(_bet%5B_idx%5D)%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20_candidates.append((_best%2C%20float(_bet%5B_best%5D)))%0A%20%20%20%20%20%20%20%20_candidates.sort(key%3Dlambda%20x%3A%20-x%5B1%5D)%0A%20%20%20%20%20%20%20%20struct_anchors%20%3D%20%5Bc%5B0%5D%20for%20c%20in%20_candidates%5B%3A%20min(3%2C%20len(_candidates))%5D%5D%0A%20%20%20%20return%20(struct_anchors%2C)%0A%0A%0A%40app.cell%0Adef%20plot_n2v_all(%0A%20%20%20%20KMeans%2C%0A%20%20%20%20PALETTE%2C%0A%20%20%20%20TSNE%2C%0A%20%20%20%20graph_data%2C%0A%20%20%20%20layout_data%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20n2v_embs%2C%0A%20%20%20%20network_with_cluster_colors%2C%0A%20%20%20%20np%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20show_node_labels%2C%0A%20%20%20%20silhouette_score%2C%0A%20%20%20%20struct_anchors%2C%0A)%3A%0A%20%20%20%20mo.stop(n2v_embs%20is%20None%2C%20mo.md(%22%22))%0A%20%20%20%20_labels%20%3D%20graph_data%5B%22labels%22%5D%0A%20%20%20%20_names%20%3D%20graph_data%5B%22names%22%5D%0A%20%20%20%20_coords%20%3D%20layout_data%5B%22coords%22%5D%0A%20%20%20%20_g%20%3D%20graph_data%5B%22graph%22%5D%0A%20%20%20%20_n_classes%20%3D%20len(set(int(c)%20for%20c%20in%20_labels))%20if%20_labels%20is%20not%20None%20else%204%0A%0A%20%20%20%20def%20_hub_ratio(_emb_arr)%3A%0A%20%20%20%20%20%20%20%20if%20not%20struct_anchors%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20None%0A%20%20%20%20%20%20%20%20from%20numpy.linalg%20import%20norm%0A%20%20%20%20%20%20%20%20_a%20%3D%20_emb_arr%5Bstruct_anchors%5D%0A%20%20%20%20%20%20%20%20_da%20%3D%20float(np.mean(%5Bnorm(_a%5Bi%5D%20-%20_a%5Bj%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20i%20in%20range(len(_a))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20j%20in%20range(i%20%2B%201%2C%20len(_a))%5D))%0A%20%20%20%20%20%20%20%20_rng%20%3D%20np.random.default_rng(0)%0A%20%20%20%20%20%20%20%20_bases%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20_%20in%20range(100)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_s%20%3D%20_rng.choice(_emb_arr.shape%5B0%5D%2C%20size%3Dlen(struct_anchors)%2C%20replace%3DFalse)%0A%20%20%20%20%20%20%20%20%20%20%20%20_es%20%3D%20_emb_arr%5B_s%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_bases.append(float(np.mean(%5Bnorm(_es%5Bi%5D%20-%20_es%5Bj%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20i%20in%20range(len(_es))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20j%20in%20range(i%20%2B%201%2C%20len(_es))%5D)))%0A%20%20%20%20%20%20%20%20return%20_da%20%2F%20float(np.mean(_bases))%0A%0A%20%20%20%20_fig%2C%20_axes%20%3D%20plt.subplots(2%2C%203%2C%20figsize%3D(14.5%2C%209.0)%2C%20height_ratios%3D%5B1%2C%201%5D)%0A%20%20%20%20for%20_ax%2C%20(_name%2C%20_emb)%20in%20zip(_axes%5B0%5D%2C%20n2v_embs.items())%3A%0A%20%20%20%20%20%20%20%20%23%202-d%20t-SNE%20projection%20(UMAP%20gave%20odd%20placements%20on%20small%2C%0A%20%20%20%20%20%20%20%20%23%20weighted%20graphs%3B%20t-SNE%20is%20the%20safer%20default%20for%20visualisation).%0A%20%20%20%20%20%20%20%20_n%20%3D%20_emb.shape%5B0%5D%0A%20%20%20%20%20%20%20%20_perp%20%3D%20max(5%2C%20min(30%2C%20_n%20%2F%2F%204))%0A%20%20%20%20%20%20%20%20_tsne%20%3D%20TSNE(%0A%20%20%20%20%20%20%20%20%20%20%20%20n_components%3D2%2C%20perplexity%3D_perp%2C%20random_state%3D1546%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20init%3D%22pca%22%2C%20learning_rate%3D%22auto%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_emb2%20%3D%20_tsne.fit_transform(_emb)%0A%20%20%20%20%20%20%20%20_emb2%20%3D%20(_emb2%20-%20_emb2.mean(axis%3D0))%20%2F%20(_emb2.std(axis%3D0)%20%2B%201e-12)%0A%20%20%20%20%20%20%20%20if%20_labels%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_colors%20%3D%20%5BPALETTE%5Bint(c)%20%25%20len(PALETTE)%5D%20for%20c%20in%20_labels%5D%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_colors%20%3D%20%5B%22%230b789d%22%5D%20*%20_emb.shape%5B0%5D%0A%20%20%20%20%20%20%20%20_ax.scatter(_emb2%5B%3A%2C%200%5D%2C%20_emb2%5B%3A%2C%201%5D%2C%20s%3D45%2C%20c%3D_colors%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolor%3D%22%23333333%22%2C%20linewidth%3D0.4)%0A%20%20%20%20%20%20%20%20%23%20Structural%20anchors%3A%20highest-betweenness%20node%20per%20class.%0A%20%20%20%20%20%20%20%20%23%20Marker%20is%20a%20*hollow%20black%20square*%20so%20the%20node's%20own%20colour%0A%20%20%20%20%20%20%20%20%23%20stays%20readable.%0A%20%20%20%20%20%20%20%20if%20struct_anchors%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_i%20in%20struct_anchors%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_emb2%5B_i%2C%200%5D%2C%20_emb2%5B_i%2C%201%5D%2C%20s%3D280%2C%20marker%3D%22s%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20facecolors%3D%22none%22%2C%20edgecolor%3D%22black%22%2C%20linewidth%3D1.8%2C%20zorder%3D5%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax.annotate(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20str(_names%5B_i%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xy%3D(_emb2%5B_i%2C%200%5D%2C%20_emb2%5B_i%2C%201%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(8%2C%208)%2C%20textcoords%3D%22offset%20points%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D7%2C%20color%3D%22%23222222%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.2%22%2C%20fc%3D%22white%22%2C%20ec%3D%22%23888888%22%2C%20alpha%3D0.9%2C%20lw%3D0.5)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20if%20show_node_labels.value%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_i%2C%20_nm%20in%20enumerate(_names)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20struct_anchors%20and%20_i%20in%20struct_anchors%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20continue%20%20%23%20already%20labelled%20above%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax.annotate(str(_nm)%2C%20xy%3D(_emb2%5B_i%2C%200%5D%2C%20_emb2%5B_i%2C%201%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(3%2C%203)%2C%20textcoords%3D%22offset%20points%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D6%2C%20color%3D%22%23444444%22%2C%20alpha%3D0.7%2C%20zorder%3D4)%0A%20%20%20%20%20%20%20%20_ax.set_xticks(%5B%5D)%3B%20_ax.set_yticks(%5B%5D)%3B%20_ax.grid(False)%3B%20_ax.set_aspect(%22equal%22)%0A%20%20%20%20%20%20%20%20_ax.set_title(_name%2C%20fontsize%3D11)%0A%20%20%20%20%20%20%20%20_sil%20%3D%20silhouette_score(_emb%2C%20_labels)%0A%20%20%20%20%20%20%20%20_hub%20%3D%20_hub_ratio(_emb)%0A%20%20%20%20%20%20%20%20_hub_line%20%3D%20%22%22%20if%20_hub%20is%20None%20else%20f%22%5Cnhub%20pull%20%3D%20%7B_hub%3A.2f%7D%C3%97%20chance%22%0A%20%20%20%20%20%20%20%20_ax.text(%0A%20%20%20%20%20%20%20%20%20%20%20%200.98%2C%200.02%2C%20f%22silhouette%20%3D%20%7B_sil%3A.3f%7D%7B_hub_line%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20transform%3D_ax.transAxes%2C%20ha%3D%22right%22%2C%20va%3D%22bottom%22%2C%20fontsize%3D10%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.3%22%2C%20fc%3D%22white%22%2C%20ec%3D%22%23888888%22%2C%20alpha%3D0.9)%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%23%20Bottom%20row%3A%20same%20FR%20layout%2C%20coloured%20by%20k-means%20on%20each%20embedding%0A%20%20%20%20%23%20%E2%80%94%20Fig%203%20of%20Grover%20%26%20Leskovec%202016.%0A%20%20%20%20if%20_g%20is%20not%20None%20and%20_coords%20is%20not%20None%20and%20_n_classes%20%3E%3D%202%3A%0A%20%20%20%20%20%20%20%20for%20_ax%2C%20(_name%2C%20_emb)%20in%20zip(_axes%5B1%5D%2C%20n2v_embs.items())%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_km%20%3D%20KMeans(n_clusters%3D_n_classes%2C%20n_init%3D10%2C%20random_state%3D1546).fit(_emb)%0A%20%20%20%20%20%20%20%20%20%20%20%20_short%20%3D%20_name.split(%22(%22)%5B0%5D.strip().split(%22%5Cn%22)%5B0%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20network_with_cluster_colors(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax%2C%20_g%2C%20_coords%2C%20_g.es%2C%20_km.labels_%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20struct_anchors%3Dstruct_anchors%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20title%3Df%22network%20coloured%20by%20k-means%20%C2%B7%20%7B_short%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20names%3D_names%2C%20show_labels%3Dshow_node_labels.value%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20_fig.tight_layout()%0A%20%20%20%20_fig%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20sec4_header_md(mo)%3A%0A%20%20%20%20sec4_header_md%20%3D%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Section%204%3A%20A%20GNN%20that%20learns%20to%20predict%20the%20label%0A%0A%20%20%20%20The%20previous%20methods%20are%20purely%20structural%20%E2%80%94%20they%20never%20see%20the%0A%20%20%20%20class%20labels.%20A%20**graph%20neural%20network**%20can%20do%20something%20stronger%3A%0A%20%20%20%20trained%20*with*%20labels%2C%20it%20can%20learn%20an%20embedding%20whose%20geometry%20is%0A%20%20%20%20shaped%20by%20the%20task%20it%20is%20being%20asked%20to%20solve.%0A%0A%20%20%20%20We%20train%20a%203-layer%20**Graph%20Convolutional%20Network%20(GCN)**%20(with%0A%20%20%20%20dropout%20for%20regularisation)%20for%20200%20epochs%20to%20predict%20the%20class%20of%0A%20%20%20%20each%20node.%20We%20picked%20GCN%20over%20GraphSAGE%20and%20GAT%20after%20a%20local%0A%20%20%20%20architecture%20sweep%3A%20a%203-layer%20GCN%20with%20hidden%20size%20128%20was%20the%20only%0A%20%20%20%20setup%20that%20consistently%20*beat*%20the%20unsupervised%20spectral%20baselines%0A%20%20%20%20on%20this%20dataset%20(macro-F1%20%E2%89%88%200.93%20vs%200.92%20for%20SVD%2FPCA).%0A%0A%20%20%20%201.%20**Split**%20the%20nodes%20into%20a%2050%2F50%20train%2Ftest%20set%2C%20stratified%20by%0A%20%20%20%20%20%20%20class%20(right%20%E2%86%92).%20The%20GNN%20sees%20the%20labels%20of%20the%20train%20nodes%20only.%0A%20%20%20%202.%20**Message%20passing**%3A%20each%20GCN%20layer%20rewrites%20every%20node's%20vector%0A%20%20%20%20%20%20%20as%20a%20symmetric-normalised%20average%20of%20itself%20and%20its%20neighbours%0A%20%20%20%20%20%20%20(%24D%5E%7B-1%2F2%7D%20A%20D%5E%7B-1%2F2%7D%24).%20After%20three%20layers%2C%20each%20node's%0A%20%20%20%20%20%20%20representation%20has%20folded%20in%20information%20from%20nodes%20three%20hops%0A%20%20%20%20%20%20%20away.%20**Dropout**%20randomly%20zeros%2050%25%20of%20the%20hidden%20activations%0A%20%20%20%20%20%20%20during%20training%2C%20which%20prevents%20the%20GNN%20from%20memorising%20single%0A%20%20%20%20%20%20%20training%20nodes%20and%20improves%20generalisation%20to%20the%20held-out%20test%0A%20%20%20%20%20%20%20set.%0A%20%20%20%203.%20**Loss**%3A%20**cross-entropy**%20against%20the%20train%20labels.%20For%20each%0A%20%20%20%20%20%20%20train%20node%20%24i%24%20the%20GNN%20outputs%20a%20vector%20of%20class%20scores%3B%20softmax%0A%20%20%20%20%20%20%20turns%20them%20into%20probabilities%20%24%5Chat%7Bp%7D_%7Bic%7D%24%20and%20the%20loss%20is%0A%20%20%20%20%20%20%20%24-%5Clog%20%5Chat%7Bp%7D_%7Bi%2C%20y_i%7D%24%20%E2%80%94%20i.e.%20how%20surprised%20the%20model%20is%20by%0A%20%20%20%20%20%20%20the%20true%20class.%20Averaged%20over%20train%20nodes%2C%20this%20is%20the%20quantity%0A%20%20%20%20%20%20%20the%20optimiser%20pushes%20down%20each%20epoch.%0A%20%20%20%204.%20The%2032-d%20output%20of%20the%20third%20layer%20is%20the%20**learned%20embedding**.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%20(sec4_header_md%2C)%0A%0A%0A%40app.cell%0Adef%20load_gnn(graph_data%2C%20load_npz)%3A%0A%20%20%20%20_prefix%20%3D%20graph_data%5B%22precomp_prefix%22%5D%0A%20%20%20%20if%20graph_data%5B%22graph%22%5D%20is%20None%20or%20_prefix%20is%20None%20or%20not%20graph_data%5B%22classes_available%22%5D%3A%0A%20%20%20%20%20%20%20%20gnn%20%3D%20None%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20gnn%20%3D%20load_npz(f%22%7B_prefix%7Dgnn_supervised.npz%22)%0A%20%20%20%20return%20(gnn%2C)%0A%0A%0A%40app.cell%0Adef%20plot_gnn_split(%0A%20%20%20%20LineCollection%2C%0A%20%20%20%20PALETTE%2C%0A%20%20%20%20gnn%2C%0A%20%20%20%20graph_data%2C%0A%20%20%20%20layout_data%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20struct_anchors%2C%0A)%3A%0A%20%20%20%20mo.stop(%0A%20%20%20%20%20%20%20%20gnn%20is%20None%2C%0A%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22_The%20supervised%20GCN%20story%20is%20precomputed%20for%20the%20football%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22and%20karate%20networks%20only.%20Switch%20to%20one%20of%20those%20to%20see%20it._%22%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20)%0A%20%20%20%20_g%20%3D%20graph_data%5B%22graph%22%5D%0A%20%20%20%20_coords%20%3D%20layout_data%5B%22coords%22%5D%0A%20%20%20%20_labels%20%3D%20graph_data%5B%22labels%22%5D%0A%20%20%20%20_train_mask%20%3D%20gnn%5B%22train_mask%22%5D%0A%20%20%20%20_test_mask%20%3D%20gnn%5B%22test_mask%22%5D%0A%20%20%20%20_node_names%20%3D%20graph_data%5B%22names%22%5D%0A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(6.2%2C%205.6))%0A%20%20%20%20_ax.set_facecolor(%22white%22)%0A%20%20%20%20_bg%20%3D%20%5B%5B_coords%5Be.source%5D%2C%20_coords%5Be.target%5D%5D%20for%20e%20in%20_g.es%5D%0A%20%20%20%20_bg_lc%20%3D%20LineCollection(_bg%2C%20colors%3D%22%23dddddd%22%2C%20linewidths%3D0.5%2C%20alpha%3D0.7%2C%20zorder%3D1)%0A%20%20%20%20_ax.add_collection(_bg_lc)%0A%0A%20%20%20%20_colors%20%3D%20%5BPALETTE%5Bint(c)%20%25%20len(PALETTE)%5D%20for%20c%20in%20_labels%5D%0A%20%20%20%20_colors_arr%20%3D%20list(_colors)%0A%20%20%20%20_tr%20%3D%20_train_mask%0A%20%20%20%20_te%20%3D%20_test_mask%0A%20%20%20%20%23%20Convention%20used%20throughout%20the%20app%3A%20train%20%3D%20filled%20%2B%20thick%20black%0A%20%20%20%20%23%20edge%20(%22the%20GCN%20saw%20this%20one%22)%3B%20test%20%3D%20filled%20%2B%20no%20edge.%0A%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20_coords%5B_tr%2C%200%5D%2C%20_coords%5B_tr%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20s%3D80%2C%20c%3D%5B_colors_arr%5Bi%5D%20for%20i%20in%20range(len(_colors_arr))%20if%20_tr%5Bi%5D%5D%2C%0A%20%20%20%20%20%20%20%20edgecolor%3D%22black%22%2C%20linewidth%3D1.2%2C%20zorder%3D3%2C%20label%3Df%22train%20(%7Bint(_tr.sum())%7D)%22%2C%0A%20%20%20%20)%0A%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20_coords%5B_te%2C%200%5D%2C%20_coords%5B_te%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20s%3D80%2C%20c%3D%5B_colors_arr%5Bi%5D%20for%20i%20in%20range(len(_colors_arr))%20if%20_te%5Bi%5D%5D%2C%0A%20%20%20%20%20%20%20%20edgecolor%3D%22none%22%2C%20zorder%3D4%2C%20label%3Df%22test%20(%7Bint(_te.sum())%7D)%22%2C%0A%20%20%20%20)%0A%20%20%20%20%23%20Always-on%20anchor%20names%20so%20the%20same%20nodes%20can%20be%20found%20across%20figures.%0A%20%20%20%20if%20struct_anchors%20and%20_node_names%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20for%20_i%20in%20struct_anchors%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.scatter(_coords%5B_i%2C%200%5D%2C%20_coords%5B_i%2C%201%5D%2C%20s%3D260%2C%20marker%3D%22s%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20facecolors%3D%22none%22%2C%20edgecolor%3D%22black%22%2C%20linewidth%3D1.8%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D5)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.annotate(str(_node_names%5B_i%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xy%3D(_coords%5B_i%2C%200%5D%2C%20_coords%5B_i%2C%201%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(8%2C%208)%2C%20textcoords%3D%22offset%20points%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D8%2C%20color%3D%22%23111111%22%2C%20fontweight%3D%22bold%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.25%22%2C%20fc%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ec%3D%22%23666666%22%2C%20alpha%3D0.9%2C%20lw%3D0.5)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D6)%0A%20%20%20%20_ax.set_xticks(%5B%5D)%0A%20%20%20%20_ax.set_yticks(%5B%5D)%0A%20%20%20%20_ax.grid(False)%0A%20%20%20%20_ax.set_title(%22Train%2Ftest%20split%20(train%20%3D%20thick%20black%20edge)%22)%0A%20%20%20%20_ax.set_aspect(%22equal%22)%0A%20%20%20%20_ax.legend(loc%3D%22upper%20right%22%2C%20fontsize%3D10)%0A%20%20%20%20_fig.tight_layout()%0A%20%20%20%20gnn_split_fig%20%3D%20_fig%0A%20%20%20%20return%20(gnn_split_fig%2C)%0A%0A%0A%40app.cell%0Adef%20sec4_layout(gnn_split_fig%2C%20mo%2C%20sec4_header_md)%3A%0A%20%20%20%20mo.md(%22---%22)%0A%20%20%20%20mo.hstack(%0A%20%20%20%20%20%20%20%20%5Bsec4_header_md%2C%20gnn_split_fig%5D%2C%0A%20%20%20%20%20%20%20%20widths%3D%5B1%2C%201.1%5D%2C%0A%20%20%20%20%20%20%20%20gap%3D1.5%2C%0A%20%20%20%20%20%20%20%20align%3D%22start%22%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20plot_gnn_curves(gnn%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20mo.stop(gnn%20is%20None%2C%20mo.md(%22%22))%0A%20%20%20%20_tr_acc%20%3D%20gnn%5B%22train_acc_history%22%5D%0A%20%20%20%20_te_acc%20%3D%20gnn%5B%22test_acc_history%22%5D%0A%20%20%20%20_epochs%20%3D%20np.arange(1%2C%20len(_tr_acc)%20%2B%201)%0A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(7.5%2C%204.0))%0A%20%20%20%20_ax.plot(_epochs%2C%20_tr_acc%2C%20color%3D%22%230b789d%22%2C%20linewidth%3D1.6%2C%20label%3D%22train%22)%0A%20%20%20%20_ax.plot(_epochs%2C%20_te_acc%2C%20color%3D%22%23d62728%22%2C%20linewidth%3D1.6%2C%20label%3D%22test%22)%0A%20%20%20%20_ax.set_xlabel(%22epoch%22)%0A%20%20%20%20_ax.set_ylabel(%22accuracy%22)%0A%20%20%20%20_ax.set_title(%22GCN%20train%20%2F%20test%20accuracy%20during%20training%22)%0A%20%20%20%20_ax.set_ylim(-0.02%2C%201.02)%0A%20%20%20%20_ax.legend(loc%3D%22lower%20right%22%2C%20fontsize%3D10)%0A%20%20%20%20_fig.tight_layout()%0A%20%20%20%20_fig%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20gnn_summary(gnn%2C%20mo)%3A%0A%20%20%20%20mo.stop(gnn%20is%20None%2C%20mo.md(%22%22))%0A%20%20%20%20_final_tr%20%3D%20float(gnn%5B%22train_acc_history%22%5D%5B-1%5D)%0A%20%20%20%20_final_te%20%3D%20float(gnn%5B%22test_acc_history%22%5D%5B-1%5D)%0A%20%20%20%20_best_te%20%3D%20float(gnn%5B%22test_acc_history%22%5D.max())%0A%20%20%20%20_train_n%20%3D%20int(gnn%5B%22train_mask%22%5D.sum())%0A%20%20%20%20_test_n%20%3D%20int(gnn%5B%22test_mask%22%5D.sum())%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20f%22**Final%20train%20accuracy%3A**%20%60%7B_final_tr%3A.3f%7D%60%20%26nbsp%3B%7C%26nbsp%3B%20%22%0A%20%20%20%20%20%20%20%20f%22**Final%20test%20accuracy%3A**%20%60%7B_final_te%3A.3f%7D%60%20%26nbsp%3B%7C%26nbsp%3B%20%22%0A%20%20%20%20%20%20%20%20f%22**Best%20test%20accuracy%20during%20training%3A**%20%60%7B_best_te%3A.3f%7D%60%20%26nbsp%3B%7C%26nbsp%3B%20%22%0A%20%20%20%20%20%20%20%20f%22**Train%20size%3A**%20%7B_train_n%7D%20%26nbsp%3B%7C%26nbsp%3B%20**Test%20size%3A**%20%7B_test_n%7D%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20gnn_embedding_fig(%0A%20%20%20%20PALETTE%2C%0A%20%20%20%20TSNE%2C%0A%20%20%20%20class_names_for%2C%0A%20%20%20%20gnn%2C%0A%20%20%20%20graph_data%2C%0A%20%20%20%20np%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20silhouette_score%2C%0A)%3A%0A%20%20%20%20%22%22%22Build%20(but%20don't%20display)%20the%20GCN-embedding%20t-SNE%20figure.%0A%0A%20%20%20%20Layout%20for%20misclassified%20test%20nodes%3A%20keep%20the%20circle's%20colour%20%3D%0A%20%20%20%20*true*%20class%20(the%20node's%20%22real%20identity%22)%20and%20overlay%20a%20square%0A%20%20%20%20whose%20colour%20%3D%20*predicted*%20class%20(what%20the%20GCN%20guessed).%20That%20way%0A%20%20%20%20you%20can%20read%20both%20at%20a%20glance%20%E2%80%94%20%22true%20purple%2C%20predicted%20orange%22.%0A%20%20%20%20%22%22%22%0A%20%20%20%20if%20gnn%20is%20None%3A%0A%20%20%20%20%20%20%20%20gnn_emb_fig%20%3D%20None%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_labels%20%3D%20graph_data%5B%22labels%22%5D%0A%20%20%20%20%20%20%20%20_emb%20%3D%20gnn%5B%22emb%22%5D%0A%20%20%20%20%20%20%20%20_preds%20%3D%20gnn%5B%22preds%22%5D%0A%20%20%20%20%20%20%20%20_train_mask%20%3D%20gnn%5B%22train_mask%22%5D%0A%20%20%20%20%20%20%20%20_test_mask%20%3D%20gnn%5B%22test_mask%22%5D%0A%20%20%20%20%20%20%20%20_n%20%3D%20_emb.shape%5B0%5D%0A%20%20%20%20%20%20%20%20_perp%20%3D%20max(5%2C%20min(30%2C%20_n%20%2F%2F%204))%0A%20%20%20%20%20%20%20%20_emb2%20%3D%20TSNE(n_components%3D2%2C%20perplexity%3D_perp%2C%20random_state%3D1546%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20init%3D%22pca%22%2C%20learning_rate%3D%22auto%22).fit_transform(_emb)%0A%20%20%20%20%20%20%20%20_emb2%20%3D%20(_emb2%20-%20_emb2.mean(axis%3D0))%20%2F%20(_emb2.std(axis%3D0)%20%2B%201e-12)%0A%20%20%20%20%20%20%20%20_wrong%20%3D%20(_preds%20!%3D%20_labels)%20%26%20_test_mask%0A%0A%20%20%20%20%20%20%20%20_classes%20%3D%20sorted(set(int(c)%20for%20c%20in%20_labels))%0A%20%20%20%20%20%20%20%20_short_names%20%3D%20class_names_for(graph_data)%0A%20%20%20%20%20%20%20%20_name_for%20%3D%20dict(zip(_classes%2C%20_short_names))%0A%0A%20%20%20%20%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(6.0%2C%206.0))%0A%20%20%20%20%20%20%20%20_colors%20%3D%20np.array(%5BPALETTE%5Bint(c)%20%25%20len(PALETTE)%5D%20for%20c%20in%20_labels%5D)%0A%20%20%20%20%20%20%20%20%23%20Train%20nodes%3A%20filled%20%2B%20thick%20BLACK%20edge%20(the%20nodes%20the%20GCN%20was%0A%20%20%20%20%20%20%20%20%23%20allowed%20to%20see).%0A%20%20%20%20%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20_emb2%5B_train_mask%2C%200%5D%2C%20_emb2%5B_train_mask%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20s%3D70%2C%20c%3D_colors%5B_train_mask%5D%2C%20edgecolor%3D%22black%22%2C%20linewidth%3D1.2%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D2%2C%20label%3Df%22train%20(%7Bint(_train_mask.sum())%7D)%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%23%20Test%20nodes%3A%20filled%2C%20NO%20edge%20%E2%80%94%20they%20should%20look%20like%20'normal'%0A%20%20%20%20%20%20%20%20%23%20nodes%3B%20the%20train%20ones%20get%20the%20visible%20black%20border%20to%20mark%0A%20%20%20%20%20%20%20%20%23%20what%20the%20GCN%20was%20trained%20on.%0A%20%20%20%20%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20_emb2%5B_test_mask%2C%200%5D%2C%20_emb2%5B_test_mask%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20s%3D70%2C%20c%3D_colors%5B_test_mask%5D%2C%20edgecolor%3D%22none%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D3%2C%20label%3Df%22test%20(%7Bint(_test_mask.sum())%7D)%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20if%20_wrong.any()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Each%20error%3A%20a%20SQUARE%20OUTLINE%20in%20the%20predicted-class%20colour%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20around%20the%20misclassified%20node.%20Transparent%20fill%20so%20the%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20original%20node%20colour%20stays%20visible%20%E2%80%94%20read%20as%20%22true%20colour%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20inside%2C%20predicted%20colour%20on%20the%20border%22.%0A%20%20%20%20%20%20%20%20%20%20%20%20_pred_colors%20%3D%20np.array(%5BPALETTE%5Bint(c)%20%25%20len(PALETTE)%5D%20for%20c%20in%20_preds%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_i%20in%20np.where(_wrong)%5B0%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_emb2%5B_i%2C%200%5D%2C%20_emb2%5B_i%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20s%3D220%2C%20marker%3D%22s%22%2C%20facecolors%3D%22none%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolor%3D_pred_colors%5B_i%5D%2C%20linewidth%3D2.4%2C%20zorder%3D5%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.scatter(%5B%5D%2C%20%5B%5D%2C%20s%3D180%2C%20marker%3D%22s%22%2C%20facecolors%3D%22none%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolor%3D%22%23333333%22%2C%20linewidth%3D2.0%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20label%3Df%22test%20errors%20(%7Bint(_wrong.sum())%7D%2C%20square%20%3D%20predicted%20class)%22)%0A%20%20%20%20%20%20%20%20_ax.legend(loc%3D%22upper%20right%22%2C%20fontsize%3D9)%0A%20%20%20%20%20%20%20%20_ax.set_xticks(%5B%5D)%0A%20%20%20%20%20%20%20%20_ax.set_yticks(%5B%5D)%0A%20%20%20%20%20%20%20%20_ax.grid(False)%0A%20%20%20%20%20%20%20%20_ax.set_aspect(%22equal%22)%0A%20%20%20%20%20%20%20%20_ax.set_title(%22Learned%20GCN%20embedding%20%E2%80%94%202D%20t-SNE%22%2C%20fontsize%3D11)%0A%20%20%20%20%20%20%20%20_sil%20%3D%20silhouette_score(_emb%2C%20_labels)%0A%20%20%20%20%20%20%20%20_ax.text(%0A%20%20%20%20%20%20%20%20%20%20%20%200.98%2C%0A%20%20%20%20%20%20%20%20%20%20%20%200.02%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22silhouette%20(full%2032-d)%20%3D%20%7B_sil%3A.3f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20transform%3D_ax.transAxes%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22right%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20va%3D%22bottom%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D10%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.3%22%2C%20fc%3D%22white%22%2C%20ec%3D%22%23888888%22%2C%20alpha%3D0.9)%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_fig.tight_layout()%0A%20%20%20%20%20%20%20%20gnn_emb_fig%20%3D%20_fig%0A%20%20%20%20return%20(gnn_emb_fig%2C)%0A%0A%0A%40app.cell%0Adef%20gnn_errors_network_fig(%0A%20%20%20%20LineCollection%2C%0A%20%20%20%20PALETTE%2C%0A%20%20%20%20class_names_for%2C%0A%20%20%20%20gnn%2C%0A%20%20%20%20graph_data%2C%0A%20%20%20%20layout_data%2C%0A%20%20%20%20np%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20struct_anchors%2C%0A)%3A%0A%20%20%20%20%22%22%22Network%20view%20with%20the%20same%20test-set%20errors%20highlighted%20and%20the%0A%20%20%20%20predicted%20(wrong)%20class%20annotated%20next%20to%20each%20error.%22%22%22%0A%20%20%20%20if%20gnn%20is%20None%3A%0A%20%20%20%20%20%20%20%20gnn_errors_fig%20%3D%20None%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_g%20%3D%20graph_data%5B%22graph%22%5D%0A%20%20%20%20%20%20%20%20_coords%20%3D%20layout_data%5B%22coords%22%5D%0A%20%20%20%20%20%20%20%20_labels%20%3D%20graph_data%5B%22labels%22%5D%0A%20%20%20%20%20%20%20%20_preds%20%3D%20gnn%5B%22preds%22%5D%0A%20%20%20%20%20%20%20%20_train_mask%20%3D%20gnn%5B%22train_mask%22%5D%0A%20%20%20%20%20%20%20%20_test_mask%20%3D%20gnn%5B%22test_mask%22%5D%0A%20%20%20%20%20%20%20%20_wrong%20%3D%20(_preds%20!%3D%20_labels)%20%26%20_test_mask%0A%0A%20%20%20%20%20%20%20%20_classes%20%3D%20sorted(set(int(c)%20for%20c%20in%20_labels))%0A%20%20%20%20%20%20%20%20_short_names%20%3D%20class_names_for(graph_data)%0A%20%20%20%20%20%20%20%20_name_for%20%3D%20dict(zip(_classes%2C%20_short_names))%0A%0A%20%20%20%20%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(6.0%2C%206.0))%0A%20%20%20%20%20%20%20%20_ax.set_facecolor(%22white%22)%0A%20%20%20%20%20%20%20%20_bg%20%3D%20%5B%5B_coords%5Be.source%5D%2C%20_coords%5Be.target%5D%5D%20for%20e%20in%20_g.es%5D%0A%20%20%20%20%20%20%20%20_bg_lc%20%3D%20LineCollection(_bg%2C%20colors%3D%22%23dddddd%22%2C%20linewidths%3D0.5%2C%20alpha%3D0.7%2C%20zorder%3D1)%0A%20%20%20%20%20%20%20%20_ax.add_collection(_bg_lc)%0A%20%20%20%20%20%20%20%20_colors%20%3D%20np.array(%5BPALETTE%5Bint(c)%20%25%20len(PALETTE)%5D%20for%20c%20in%20_labels%5D)%0A%20%20%20%20%20%20%20%20%23%20Train%3A%20filled%20%2B%20thick%20black%20edge.%0A%20%20%20%20%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20_coords%5B_train_mask%2C%200%5D%2C%20_coords%5B_train_mask%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20s%3D70%2C%20c%3D_colors%5B_train_mask%5D%2C%20edgecolor%3D%22black%22%2C%20linewidth%3D1.2%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D3%2C%20label%3Df%22train%20(%7Bint(_train_mask.sum())%7D)%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%23%20Test%3A%20filled%2C%20no%20edge.%0A%20%20%20%20%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20_coords%5B_test_mask%2C%200%5D%2C%20_coords%5B_test_mask%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20s%3D70%2C%20c%3D_colors%5B_test_mask%5D%2C%20edgecolor%3D%22none%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D4%2C%20label%3Df%22test%20(%7Bint(_test_mask.sum())%7D)%22%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20if%20_wrong.any()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_pred_colors%20%3D%20np.array(%5BPALETTE%5Bint(c)%20%25%20len(PALETTE)%5D%20for%20c%20in%20_preds%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_i%20in%20np.where(_wrong)%5B0%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax.scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_coords%5B_i%2C%200%5D%2C%20_coords%5B_i%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20s%3D220%2C%20marker%3D%22s%22%2C%20facecolors%3D%22none%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolor%3D_pred_colors%5B_i%5D%2C%20linewidth%3D2.4%2C%20zorder%3D5%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.scatter(%5B%5D%2C%20%5B%5D%2C%20s%3D180%2C%20marker%3D%22s%22%2C%20facecolors%3D%22none%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolor%3D%22%23333333%22%2C%20linewidth%3D2.0%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20label%3Df%22test%20errors%20(%7Bint(_wrong.sum())%7D%2C%20square%20%3D%20predicted%20class)%22)%0A%20%20%20%20%20%20%20%20if%20struct_anchors%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_node_names%20%3D%20graph_data%5B%22names%22%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_i%20in%20struct_anchors%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax.scatter(_coords%5B_i%2C%200%5D%2C%20_coords%5B_i%2C%201%5D%2C%20s%3D260%2C%20marker%3D%22s%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20facecolors%3D%22none%22%2C%20edgecolor%3D%22black%22%2C%20linewidth%3D1.8%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D6)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_ax.annotate(str(_node_names%5B_i%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xy%3D(_coords%5B_i%2C%200%5D%2C%20_coords%5B_i%2C%201%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(-10%2C%2010)%2C%20textcoords%3D%22offset%20points%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D8%2C%20color%3D%22%23111111%22%2C%20fontweight%3D%22bold%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.25%22%2C%20fc%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ec%3D%22%23666666%22%2C%20alpha%3D0.9%2C%20lw%3D0.5)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D7)%0A%20%20%20%20%20%20%20%20_ax.set_xticks(%5B%5D)%0A%20%20%20%20%20%20%20%20_ax.set_yticks(%5B%5D)%0A%20%20%20%20%20%20%20%20_ax.grid(False)%0A%20%20%20%20%20%20%20%20_ax.set_aspect(%22equal%22)%0A%20%20%20%20%20%20%20%20_ax.set_title(%22Same%20nodes%20on%20the%20actual%20network%22%2C%20fontsize%3D11)%0A%20%20%20%20%20%20%20%20_ax.legend(loc%3D%22upper%20right%22%2C%20fontsize%3D9)%0A%20%20%20%20%20%20%20%20_fig.tight_layout()%0A%20%20%20%20%20%20%20%20gnn_errors_fig%20%3D%20_fig%0A%20%20%20%20return%20(gnn_errors_fig%2C)%0A%0A%0A%40app.cell%0Adef%20sec5_header(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%20%20%20%20%23%23%20Section%205%3A%20Predicting%20the%20class%20from%20each%20embedding%0A%0A%20%20%20%20Take%20each%20embedding%20we%20built%20%E2%80%94%20spectral%2C%20node2vec%2C%20and%20the%20supervised%0A%20%20%20%20GCN%20%E2%80%94%20and%20use%20it%20as%20input%20features%20for%20a%20plain%20**multinomial%0A%20%20%20%20(softmax)%20logistic%20regression**%20that%20predicts%20the%20node%20class.%0A%0A%20%20%20%20To%20make%20the%20comparison%20apples-to-apples%2C%20every%20method%20uses%20the%0A%20%20%20%20**same%20train%2Ftest%20split**%20that%20the%20GCN%20was%20trained%20on%3A%0A%0A%20%20%20%20-%20the%20GNN%20sees%20the%20train-node%20labels%20during%20its%20training%2C%0A%20%20%20%20-%20each%20logistic%20regression%20sees%20the%20train-node%20labels%20during%20its%20fit%2C%0A%20%20%20%20-%20everything%20is%20evaluated%20on%20the%20held-out%20test%20nodes%20%E2%80%94%20**no%20method%0A%20%20%20%20%20%20ever%20saw%20the%20test-node%20labels.**%20Including%20the%20GCN%20embedding%0A%20%20%20%20%20%20here%20is%20fair%3A%20only%20train%20labels%20touched%20it.%0A%0A%20%20%20%20The%20table%20below%20shows%20test-set%20**accuracy**%2C%20**macro-averaged%0A%20%20%20%20precision%20%2F%20recall%20%2F%20F1**%2C%20fit%20for%20every%20embedding%20side%20by%20side.%0A%20%20%20%20The%20classifier%20is%20%60LogisticRegression(C%3D10%2C%20solver%3D%22lbfgs%22)%60%3B%20we%0A%20%20%20%20use%20a%20weaker-than-default%20L2%20penalty%20(%60C%3D10%60%20instead%20of%20sklearn's%0A%20%20%20%20%60C%3D1%60)%20so%20the%20high-frequency%20components%20of%20the%20Laplacian%20Eigenmaps%0A%20%20%20%20are%20not%20over-regularised%20away%20%E2%80%94%20every%20method%20gets%20the%20same%20setting.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20classification_split(gnn%2C%20graph_data%2C%20np%2C%20train_test_split)%3A%0A%20%20%20%20%22%22%22Train%2Ftest%20split%20used%20in%20Section%205.%0A%0A%20%20%20%20For%20football%20and%20karate%20we%20reuse%20the%20exact%20mask%20the%20GCN%20was%0A%20%20%20%20trained%20on%20(so%20every%20method%20sees%20the%20same%20train%20and%20test%20nodes).%20For%0A%20%20%20%20a%20user-uploaded%20labelled%20graph%2C%20we%20compute%20a%2050%2F50%20stratified%20split%0A%20%20%20%20on%20the%20fly%20with%20a%20fixed%20seed.%0A%20%20%20%20%22%22%22%0A%20%20%20%20_labels%20%3D%20graph_data%5B%22labels%22%5D%0A%20%20%20%20if%20not%20graph_data%5B%22classes_available%22%5D%20or%20_labels%20is%20None%3A%0A%20%20%20%20%20%20%20%20split%20%3D%20None%0A%20%20%20%20elif%20gnn%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20split%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22train_mask%22%3A%20gnn%5B%22train_mask%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22test_mask%22%3A%20gnn%5B%22test_mask%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22source%22%3A%20%22graphsage%22%2C%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_n%20%3D%20len(_labels)%0A%20%20%20%20%20%20%20%20_idx%20%3D%20np.arange(_n)%0A%20%20%20%20%20%20%20%20_u%2C%20_counts%20%3D%20np.unique(_labels%2C%20return_counts%3DTrue)%0A%20%20%20%20%20%20%20%20_strat%20%3D%20_labels%20if%20_counts.min()%20%3E%3D%202%20else%20None%0A%20%20%20%20%20%20%20%20_tr%2C%20_te%20%3D%20train_test_split(%0A%20%20%20%20%20%20%20%20%20%20%20%20_idx%2C%20test_size%3D0.5%2C%20stratify%3D_strat%2C%20random_state%3D1546%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_tm%20%3D%20np.zeros(_n%2C%20dtype%3Dbool)%3B%20_tm%5B_tr%5D%20%3D%20True%0A%20%20%20%20%20%20%20%20split%20%3D%20%7B%22train_mask%22%3A%20_tm%2C%20%22test_mask%22%3A%20~_tm%2C%20%22source%22%3A%20%22fresh%22%7D%0A%20%20%20%20return%20(split%2C)%0A%0A%0A%40app.cell%0Adef%20classify_all(%0A%20%20%20%20LogisticRegression%2C%0A%20%20%20%20accuracy_score%2C%0A%20%20%20%20f1_score%2C%0A%20%20%20%20gnn%2C%0A%20%20%20%20graph_data%2C%0A%20%20%20%20load_npy%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20pd%2C%0A%20%20%20%20spectral_embs%2C%0A%20%20%20%20split%2C%0A)%3A%0A%20%20%20%20from%20sklearn.metrics%20import%20precision_score%2C%20recall_score%0A%0A%20%20%20%20mo.stop(%0A%20%20%20%20%20%20%20%20not%20graph_data%5B%22classes_available%22%5D%20or%20split%20is%20None%2C%0A%20%20%20%20%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22_The%20current%20network%20has%20no%20class%20labels%2C%20so%20the%20comparison%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22table%20is%20hidden.%20Switch%20to%20Football%20or%20Karate%2C%20or%20upload%20a%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22GraphML%20with%20a%20node-class%20attribute%2C%20to%20see%20it._%22%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20)%0A%0A%20%20%20%20_labels%20%3D%20graph_data%5B%22labels%22%5D%0A%20%20%20%20_prefix%20%3D%20graph_data%5B%22precomp_prefix%22%5D%0A%20%20%20%20_train_mask%20%3D%20split%5B%22train_mask%22%5D%0A%20%20%20%20_test_mask%20%3D%20split%5B%22test_mask%22%5D%0A%0A%20%20%20%20_methods%20%3D%20%5B%5D%0A%20%20%20%20for%20_name%2C%20_emb%20in%20spectral_embs.items()%3A%0A%20%20%20%20%20%20%20%20_methods.append((f%22Spectral%20%C2%B7%20%7B_name%7D%22%2C%20_emb))%0A%20%20%20%20if%20_prefix%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20for%20_q_label%2C%20_file%20in%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20(%22node2vec%20%E2%80%94%20DFS%20(p%3D1%2C%20q%3D0.1)%22%2C%20%20%20%22node2vec_dfs.npy%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(%22node2vec%20%E2%80%94%20balanced%20(p%3D1%2C%20q%3D1)%22%2C%20%22node2vec_balanced.npy%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20(%22node2vec%20%E2%80%94%20BFS%20(p%3D1%2C%20q%3D10)%22%2C%20%20%20%20%20%22node2vec_bfs.npy%22)%2C%0A%20%20%20%20%20%20%20%20%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_methods.append((_q_label%2C%20load_npy(f%22%7B_prefix%7D%7B_file%7D%22)))%0A%20%20%20%20if%20gnn%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20_methods.append((%22GCN%20(supervised)%22%2C%20gnn%5B%22emb%22%5D))%0A%0A%20%20%20%20_rows%20%3D%20%5B%5D%0A%20%20%20%20for%20_name%2C%20_emb%20in%20_methods%3A%0A%20%20%20%20%20%20%20%20_Xtr%20%3D%20_emb%5B_train_mask%5D%0A%20%20%20%20%20%20%20%20_ytr%20%3D%20_labels%5B_train_mask%5D%0A%20%20%20%20%20%20%20%20_Xte%20%3D%20_emb%5B_test_mask%5D%0A%20%20%20%20%20%20%20%20_yte%20%3D%20_labels%5B_test_mask%5D%0A%20%20%20%20%20%20%20%20%23%20C%3D10%20gives%20weaker%20L2%20regularisation%20than%20the%20sklearn%20default%0A%20%20%20%20%20%20%20%20%23%20of%20C%3D1.%20Default-C%20over-penalises%20features%20that%20look%20noisy%20in%0A%20%20%20%20%20%20%20%20%23%20the%20train%20sample%20(notably%20the%20higher-frequency%20Laplacian%0A%20%20%20%20%20%20%20%20%23%20eigenvectors)%2C%20so%20all%20methods%20-%20and%20Laplacian%20Eigenmaps%20in%0A%20%20%20%20%20%20%20%20%23%20particular%20-%20perform%20substantially%20better%20here.%0A%20%20%20%20%20%20%20%20_clf%20%3D%20LogisticRegression(max_iter%3D2000%2C%20solver%3D%22lbfgs%22%2C%20C%3D10.0)%0A%20%20%20%20%20%20%20%20_clf.fit(_Xtr%2C%20_ytr)%0A%20%20%20%20%20%20%20%20_yhat%20%3D%20_clf.predict(_Xte)%0A%20%20%20%20%20%20%20%20_rows.append(%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22embedding%22%3A%20_name%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22accuracy%22%3A%20round(float(accuracy_score(_yte%2C%20_yhat))%2C%203)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22precision%20(macro)%22%3A%20round(float(precision_score(_yte%2C%20_yhat%2C%20average%3D%22macro%22%2C%20zero_division%3D0))%2C%203)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22recall%20(macro)%22%3A%20round(float(recall_score(_yte%2C%20_yhat%2C%20average%3D%22macro%22%2C%20zero_division%3D0))%2C%203)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22f1%20(macro)%22%3A%20round(float(f1_score(_yte%2C%20_yhat%2C%20average%3D%22macro%22%2C%20zero_division%3D0))%2C%203)%2C%0A%20%20%20%20%20%20%20%20%7D)%0A%20%20%20%20_df%20%3D%20pd.DataFrame(_rows).sort_values(%22accuracy%22%2C%20ascending%3DFalse).reset_index(drop%3DTrue)%0A%0A%20%20%20%20_note%20%3D%20(%0A%20%20%20%20%20%20%20%20%22same%20split%20as%20the%20GCN%20training%20above%22%0A%20%20%20%20%20%20%20%20if%20split%5B%22source%22%5D%20%3D%3D%20%22graphsage%22%0A%20%20%20%20%20%20%20%20else%20%2250%2F50%20stratified%20split%20(no%20precomputed%20GCN%20for%20this%20graph)%22%0A%20%20%20%20)%0A%20%20%20%20_summary%20%3D%20mo.md(%0A%20%20%20%20%20%20%20%20f%22_Train%20set%3A%20%7Bint(_train_mask.sum())%7D%20nodes%20%26nbsp%3B%C2%B7%26nbsp%3B%20%22%0A%20%20%20%20%20%20%20%20f%22Test%20set%3A%20%7Bint(_test_mask.sum())%7D%20nodes%20%26nbsp%3B%C2%B7%26nbsp%3B%20%22%0A%20%20%20%20%20%20%20%20f%22%7B_note%7D._%22%0A%20%20%20%20)%0A%20%20%20%20mo.vstack(%5B_summary%2C%20mo.ui.table(_df%2C%20selection%3DNone)%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20sec5_errors_header(gnn%2C%20graph_data%2C%20mo)%3A%0A%20%20%20%20mo.stop(gnn%20is%20None%2C%20mo.md(%22%22))%0A%20%20%20%20_name%20%3D%20graph_data.get(%22name%22%2C%20%22%22)%0A%20%20%20%20if%20_name.startswith(%22Football%22)%3A%0A%20%20%20%20%20%20%20%20_interp%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Most%20errors%20typically%20sit%20on%20**inter-conference%20edges**%20%E2%80%94%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22teams%20that%20played%20a%20lot%20of%20out-of-conference%20games%20(the%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Independents%20and%20a%20few%20transitioning%20conferences)%20are%20the%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22hardest%20to%20place.%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20elif%20_name.startswith(%22Karate%22)%3A%0A%20%20%20%20%20%20%20%20_interp%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22With%20only%20two%20factions%20any%20errors%20will%20be%20club%20members%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22who%20interact%20across%20the%20Mr%20Hi%20%2F%20Officer%20dispute%20line%2C%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22which%20is%20exactly%20where%20the%20disputed%20members%20of%20the%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22original%20Zachary%20(1977)%20study%20sit.%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20elif%20_name.startswith(%22Les%22)%3A%0A%20%20%20%20%20%20%20%20_interp%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Errors%20are%20typically%20characters%20who%20appear%20across%20**multiple%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22social%20circles**%20in%20Hugo's%20novel%20%E2%80%94%20Valjean%2C%20Marius%2C%20Cosette%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22and%20Gavroche%20bridge%20the%20prison%2C%20the%20Friends%20of%20the%20ABC%2C%20and%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22the%20Th%C3%A9nardier%20subplots%2C%20so%20a%20single%20'community'%20label%20is%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22always%20going%20to%20be%20a%20lossy%20summary%20of%20who%20they%20really%20are.%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20_interp%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Errors%20typically%20sit%20on%20the%20boundary%20between%20two%20classes%20%E2%80%94%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22nodes%20whose%20connections%20span%20multiple%20groups%20are%20inherently%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22harder%20to%20classify%20than%20nodes%20deep%20inside%20a%20single%20group.%22%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20mo.md(rf%22%22%22%0A%20%20%20%20%23%23%23%20Where%20does%20GCN%20go%20wrong%20on%20the%20test%20set%3F%0A%0A%20%20%20%20Left%3A%20the%20**learned%2032-d%20GCN%20embedding**%2C%20projected%20to%202-d%20with%0A%20%20%20%20**t-SNE**.%20Right%3A%20the%20**same%20nodes%20back%20on%20the%20actual%20network**.%0A%20%20%20%20Conventions%3A%0A%0A%20%20%20%20-%20**Train%20nodes**%20%E2%80%94%20coloured%20by%20class%2C%20**thick%20black%20edge**%20(the%0A%20%20%20%20%20%20GCN%20was%20allowed%20to%20see%20these%20labels).%0A%20%20%20%20-%20**Test%20nodes**%20%E2%80%94%20coloured%20by%20class%2C%20no%20edge%20(held-out%20from%0A%20%20%20%20%20%20training).%0A%20%20%20%20-%20**Misclassified%20test%20nodes**%20%E2%80%94%20a%20hollow%20**square**%20drawn%20around%0A%20%20%20%20%20%20the%20node%2C%20**edge%20coloured%20by%20the%20predicted%20class**.%20So%20the%0A%20%20%20%20%20%20circle%20inside%20still%20shows%20the%20true%20class%2C%20and%20the%20square's%0A%20%20%20%20%20%20colour%20shows%20what%20the%20GCN%20guessed.%0A%0A%20%20%20%20%7B_interp%7D%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20sec5_errors_layout(gnn%2C%20gnn_emb_fig%2C%20gnn_errors_fig%2C%20mo)%3A%0A%20%20%20%20mo.stop(gnn%20is%20None%2C%20mo.md(%22%22))%0A%20%20%20%20mo.hstack(%0A%20%20%20%20%20%20%20%20%5Bgnn_emb_fig%2C%20gnn_errors_fig%5D%2C%20widths%3D%5B1%2C%201%5D%2C%20gap%3D1.0%2C%20align%3D%22start%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20conclusion(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%20%20%20%20%23%23%20Wrap-up%3A%20when%20to%20use%20which%20method%3F%0A%0A%20%20%20%20%7C%20Method%20%7C%20Sees%20labels%3F%20%7C%20Best%20at%20%7C%20Watch%20out%20for%20%7C%0A%20%20%20%20%7C---%7C---%7C---%7C---%7C%0A%20%20%20%20%7C%20**Truncated%20SVD%20%2F%20PCA%20of%20%24A%24**%20%7C%20no%20%7C%20a%20strong%20general-purpose%20baseline%3B%20cheap%2C%20deterministic%2C%20and%20works%20whenever%20the%20network%20has%20any%20structure%20at%20all%20%7C%20needs%20the%20right%20number%20of%20dimensions%20%E2%80%94%20too%20few%20drops%20accuracy.%20SVD's%20first%20axis%20is%20degree-shaped%20(it%20disappears%20if%20you%20centre%2C%20which%20is%20what%20PCA%20does)%20%7C%0A%20%20%20%20%7C%20**Laplacian%20Eigenmaps**%20%7C%20no%20%7C%20recovering%20**community-shaped**%20classes%20%E2%80%94%20especially%20when%20classes%20look%20like%20cliques%20in%20the%20graph%20%7C%20only%20the%20*first%20few*%20eigenvectors%20are%20useful%3B%20adding%20more%20dimensions%20actually%20*hurts*.%20Performance%20falls%20off%20classes%20that%20aren't%20real%20communities%20(Independents%20on%20football)%20%7C%0A%20%20%20%20%7C%20**node2vec**%20%7C%20no%20%7C%20shifting%20between%20**community**%20(%24q%20%5C!%3C%5C!%201%24%2C%20DFS)%20and%20**structural-role**%20(%24q%20%5C!%3E%5C!%201%24%2C%20BFS)%20views%20of%20the%20same%20network%20%E2%80%94%20by%20changing%20two%20knobs%20%7C%20many%20hyperparameters%20(p%2C%20q%2C%20walk%20length%2C%20window)%20%E2%80%94%20on%20a%20dense%2C%20near-regular%20network%20like%20football%20the%20bias%20has%20little%20room%20to%20move%2C%20the%20differences%20become%20subtle%20%7C%0A%20%20%20%20%7C%20**GCN%20(supervised)**%20%7C%20YES%20%7C%20every%20dataset%20where%20you%20have%20*some*%20labels%3B%20trained%20directly%20on%20the%20classification%20objective%2C%20so%20it%20can%20pick%20up%20patterns%20SVD%2FLE%2Fnode2vec%20miss%20%7C%20the%20most%20expensive%20option%3B%20needs%20careful%20regularisation%20(dropout%2C%20weight%20decay)%20to%20not%20overfit%20on%20small%20training%20sets.%20Without%20enough%20train%20labels%20it%20just%20memorises%20them%20and%20doesn't%20generalise%20%7C%0A%0A%20%20%20%20**General%20lessons**%20the%20football%20and%20karate%20networks%20reveal%3A%0A%0A%20%20%20%20-%20The%20**easy%20classes**%20(large%2C%20dense%2C%20well-separated%20conferences)%20are%0A%20%20%20%20%20%20solved%20by%20basically%20every%20method.%20The%20interesting%20question%20is%0A%20%20%20%20%20%20always%20how%20each%20method%20handles%20the%20**hard%20classes**%20%E2%80%94%20here%20the%0A%20%20%20%20%20%20Independents%20and%20Sun%20Belt%20teams%2C%20which%20lack%20a%20clear%20community%0A%20%20%20%20%20%20structure.%20SVD%2FPCA%20and%20GCN%20handle%20them%20best%20because%20they%20can%20pick%0A%20%20%20%20%20%20up%20*which*%20communities%20each%20team%20interacted%20with%2C%20not%20just%20*that*%0A%20%20%20%20%20%20it%20interacted%20with%20some%20community.%0A%20%20%20%20-%20**Supervised%20wins%2C%20but%20not%20by%20much**.%20The%20GCN%20beats%20the%0A%20%20%20%20%20%20unsupervised%20methods%20by%20only%20a%20few%20F1%20points%20(~0.93%20vs%20~0.92%20on%0A%20%20%20%20%20%20football)%20%E2%80%94%20because%20the%20structure%20of%20the%20network%20already%20encodes%0A%20%20%20%20%20%20almost%20all%20of%20the%20label%20information.%20On%20graphs%20where%20labels%20are%0A%20%20%20%20%20%20*less*%20tied%20to%20structure%2C%20the%20gap%20would%20widen.%0A%20%20%20%20-%20**Embeddings%20are%20not%20interpretable%20axes**.%20Throughout%20we%20used%0A%20%20%20%20%20%202-d%20projections%20(the%20first%20two%20components%20for%20spectral%20methods%2C%0A%20%20%20%20%20%20PCA%20for%20GCN%2C%20t-SNE%20for%20node2vec)%20%E2%80%94%20but%20the%20underlying%20spaces%20are%0A%20%20%20%20%20%2032-dimensional%20and%20their%20individual%20axes%20don't%20carry%20meaning.%0A%20%20%20%20%20%20That's%20why%20we%20strip%20the%20tick%20labels%3A%20only%20the%20*geometry*%20matters.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20footer(mo)%3A%0A%20%20%20%20mo.md(%22%22%22%0A%20%20%20%20---%0A%0A%20%20%20%20_Javier%20Garcia-Bernardo%20%E2%80%94%20SoDa%20%26%20Utrecht%20University._%0A%0A%20%20%20%20_An%20interactive%20companion%20on%20node%20embeddings%2C%20built%20with%20%5Bmarimo%5D(https%3A%2F%2Fmarimo.io)._%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A