Rewire

Rewire identifies structural changes between two graphs by detecting which nodes have altered their network context and which remain stable.

---

Overview

Given two graphs over a shared node set:

• Learn node embeddings independently
• Align embedding spaces
• Measure per-node displacement
• Quantify neighborhood change
• Cluster the most shifted nodes

---

How it works

1. Load graphs from weighted edge list CSVs

2. Embed nodes independently using Node2Vec (random walks + skip-gram with negative sampling)

3. Align embeddings using Procrustes alignment (centering + optimal rotation)

4. Compute delta vectors (aligned graph2 − graph1)

5. Compute per-node metrics:

   • Delta L2: magnitude of displacement in embedding space
   • Neighbor Jaccard: overlap of k-nearest neighbors (Annoy angular distance)
   • Density shift: mean neighbor distance(graph1) − mean neighbor distance(graph2)

6. Cluster top N nodes using agglomerative clustering on delta vectors

7. Write results to CSV for downstream analysis

---

Requirements

• Go 1.22+
• SWIG 4.2+ (with Go support)
• g++
• git (for Annoy bindings)

---

Installation

git clone https://github.com/dfrll/rewire
cd rewire
bash build.sh

The build script:

• Builds Annoy bindings
• Compiles the binary

---

Input format

Each graph is a weighted edge list CSV with a header:

source,target,weight
nodeA,nodeB,0.85
nodeA,nodeC,0.72
nodeB,nodeD,0.91

Notes:

• Graph is treated as undirected
• Only nodes present in both graphs are analyzed

---

Usage

1. Configure

cp config.example.yaml config.yaml

2. Build embeddings

./rewire embed
./rewire embed --force

3. Run differential analysis

./rewire diff
./rewire diff --force

4. Query neighbors

Single node

./rewire query NODE --graph graph1 --n 10

Batch query

./rewire query --batch node_labels.txt --graph graph2 --n 50

---

Configuration

All parameters can be set via config.yaml or CLI flags.

Core parameters

Parameter	Description
graph1	Baseline graph
graph2	Comparison graph
workdir	Cache + output directory
force	Recompute cached artifacts
nTrees	Annoy trees (accuracy vs build time)

---

Embedding (embed)

Parameter	Default	Description
seed	0	random seed: set to a non-zero value for reproducibility
dim	64	Embedding dimension
walkLength	80	Walk length
nWalks	20	Walks per node
p	1.0	Return parameter
q	2.0	In-out parameter
restartProbability	0.02	Random walk restart probability
t	1e-5	Subsampling threshold
window	3	Context window
epochs	50	Training epochs
negSamples	5	Negative samples per positive
initLR	1e-1	Initial learning rate
minLR	1e-3	Minimum learning rate
convergenceThreshold	1e-5	Early stopping threshold
nRuns	1	Runs to average embeddings over
writeRuns	false	Write per-run embeddings to disk

---

Differential analysis (diff)

Parameter	Default	Description
numNeighbors	50	KNN size for metrics
cutThreshold	0	0 = adaptive threshold
linkage	average	Agglomerative linkage
distance	cosine	Distance metric
topN	20	Number of most shifted nodes (by delta_l2) to cluster (0 = all)

---

Output

All outputs are written to workdir.

Files

File	Description
all_nodes.csv	Metrics for all shared nodes
nodes.csv	Metrics + cluster assignments (top N)
distances.csv	Merge distances from clustering
delta.embeddings.csv	Delta vectors

Columns

Column	Description
node	Node ID
module	Cluster assignment (delta space)
delta_l2	Displacement magnitude
neighbor_jaccard	Neighbor overlap
density_shift	Change in mean neighbor distance

---

Interpretation

• High delta_l2 + low Jaccard - strong rewiring
• Low delta_l2 + high Jaccard - stable node
• Positive density_shift - neighborhood becomes tighter in graph2

---

Caching

Stored in workdir:

• .emb.gob - embeddings
• .ann.idx - Annoy indices

---

License

MIT