Nodes and Edges
Think of your favorite map of the world. Cities are dots, and the roads connecting them are lines! In computer science, we call the dots Nodes (or vertices), and the connecting lines Edges.
A collection of nodes and edges is called a Graph. Graphs can describe social networks (where nodes are people and edges are friendships) or the internet itself (where nodes are web pages and edges are links)!
- Node (Vertex): An individual entity, person, city, or object in a network.
- Edge (Link): A relationship or connection between two nodes.
Directed vs Undirected Connections
Some roads are two-way streets where cars can travel in both directions: this is an Undirected edge. If you are friends with someone on Facebook, you are friends with each other.
Other roads are one-way streets where you can only go forward: this is a Directed edge! On Twitter or Instagram, you can follow an astronaut without the astronaut following you back.
- Undirected Edge: Symmetric connection where $(u, v) = (v, u)$.
- Directed Edge: Asymmetric arrow pointing strictly from source to target ($u o v$).
Finding the Shortest Path
When you use Google Maps to find the fastest way to school, the computer doesn't check every random road in the world. It uses graph pathfinding algorithms to find the path with the smallest total road length!
If every road has a distance or travel time attached to it, we call it a Weighted Graph.
- Weighted Graph: A network where edges have numeric costs, distances, or capacities.
- Shortest Path: The route between two nodes that minimizes the sum of edge weights.
Level 1 Completed: Junior Graph Topologies Certificate
Conferred for foundational competence in node-edge representations, directed/undirected symmetries, and weighted path concepts.
Adjacency Matrix vs Adjacency List
To store a graph in computer memory, we choose between two primary representations. An Adjacency Matrix is a $|V| imes |V|$ 2D grid where $A_{ij} = 1$ if an edge connects node $i$ to $j$. Checking if two nodes are connected is instant $O(1)$, but memory scales quadratically as $O(|V|^2)$.
For sparse graphs (like road networks or social networks where people only have a few hundred friends out of billions), an Adjacency List stores an array of linked lists. Memory scales linearly as $O(|V| + |E|)$, saving gigabytes of RAM.
- Adjacency Matrix: $|V| \times |V|$ grid with $O(1)$ edge query but $O(|V|^2)$ memory.
- Adjacency List: Array of neighbor lists with optimal $O(|V| + |E|)$ memory for sparse graphs.
Breadth-First Search (BFS) vs Depth-First (DFS)
Breadth-First Search (BFS) explores a graph in concentric ripples: visiting all immediate neighbors (distance 1) before exploring neighbors' neighbors (distance 2). Using a FIFO Queue, BFS is guaranteed to find the unweighted shortest path.
Depth-First Search (DFS) explores as deep as possible down a single path until hitting a dead end, then backtracks using a LIFO Stack or recursion. DFS is ideal for maze solving, topological sorting, and cycle detection.
- BFS Queue: Explores level-by-level, guarantees minimum-hop shortest path.
- DFS Stack: Explores down deep branches, computes connected components and topological orderings.
Dijkstra's Shortest Path Algorithm
When edges have varying positive weights (like drive times or packet latencies), BFS no longer guarantees the shortest path. Edsger Dijkstra developed the greedy shortest path algorithm in 1956.
Dijkstra's algorithm maintains a Min-Priority Queue of visited nodes ordered by cumulative distance from the source. By repeatedly relaxing edges from the closest unvisited node, it computes shortest paths in $O((|V| + |E|) \log |V|)$ time.
- Edge Relaxation: If $d[u] + w(u, v) < d[v]$, update $d[v] = d[u] + w(u, v)$.
- Priority Queue (Binary Heap): Extracts the minimum-distance unvisited node in $O(\log |V|)$ time.
Level 2 Completed: Graph Traversal & Pathfinding Specialist
Conferred for competence in adjacency list/matrix memory complexity, BFS/DFS traversal mechanics, and Dijkstra's shortest-path relaxation.
Network Centrality Metrics
Not all nodes in a network are equally influential. Centrality metrics quantify structural importance: Degree Centrality measures direct connections ($C_D(v) = \text{deg}(v)$).
Betweenness Centrality measures how often a node acts as a bridge along the shortest paths between all other node pairs. A node with high betweenness controls information flow and communication bottlenecks.
- Betweenness Centrality: $C_B(v) = \sum_{s \ne v \ne t} \frac{\sigma_{st}(v)}{\sigma_{st}}$.
- Closeness Centrality: Reciprocal of the sum of shortest distances to all other nodes ($C_C(v) = \frac{N-1}{\sum_u d(v, u)}$).
The PageRank Algorithm
Larry Page and Sergey Brin founded Google by modeling web surfing as a Markov random walk over the world wide web graph. A page is important if other important pages link to it.
PageRank simulates a surfer who follows random hyperlinks with probability $d$ (damping factor, typically 0.85) and teleports to a completely random webpage with probability $1 - d$. The stationary distribution of this Markov chain yields the PageRank score vector $\mathbf{r}$.
- Damping Factor ($d$): Balances following links ($d=0.85$) vs random uniform teleportation ($0.15$).
- Power Iteration: Iteratively computing $\mathbf{r}^{(t+1)} = \mathbf{M} \mathbf{r}^{(t)}$ until convergence.
The Graph Laplacian Matrix ($\mathbf{L} = \mathbf{D} - \mathbf{A}$)
Spectral graph theory analyzes the eigenvalues and eigenvectors of matrices associated with the graph. The Degree Matrix $\mathbf{D}$ is a diagonal matrix of node degrees ($D_{ii} = \sum_j A_{ij}$).
The Graph Laplacian is defined as $\mathbf{L} = \mathbf{D} - \mathbf{A}$. The Laplacian is symmetric and positive semi-definite. The number of zero eigenvalues ($\lambda = 0$) equals the number of connected components in the graph!
- Fiedler Vector ($\lambda_2$): The second smallest eigenvalue (algebraic connectivity) and its eigenvector partition the graph into two balanced communities.
- Quadratic Energy: $\mathbf{x}^T \mathbf{L} \mathbf{x} = rac{1}{2} \sum_{(i, j) \in E} (x_i - x_j)^2$.
Level 3 Completed: Spectral Graph Theory & Centrality Analyst
Conferred for mastery of betweenness/closeness centrality metrics, PageRank power iteration, and Graph Laplacian eigendecompositions.
Semantic Triples & RDF Data Models
Traditional databases store data in rigid tabular schemas that fracture when relationships become complex. The Resource Description Framework (RDF) represents all human and machine knowledge as atomic Subject-Predicate-Object statements called Triples.
For example: `(TimCook, CEO_Of, Apple)` or `(Apple, Headquartered_In, Cupertino)`. Every entity and relation is identified by a globally unique Uniform Resource Identifier (URI), creating an interconnected Web of Linked Open Data.
- Semantic Triple: Fundamental knowledge atom composed of $\langle \text{Subject}, \text{Predicate}, \text{Object} \rangle$.
- URI (Uniform Resource Identifier): Unique global address disambiguating entities (e.g. `http://dbpedia.org/resource/Apple_Inc.`).
SPARQL Query Language & Graph Patterns
SPARQL (SPARQL Protocol and RDF Query Language) is the SQL of Knowledge Graphs. Instead of joining relational tables, SPARQL matches graph patterns containing variable placeholders.
A query like: `SELECT ?person WHERE { ?person :worksFor :Apple . ?person :livesIn :California }` executes subgraph isomorphism matching across millions of semantic triples in milliseconds.
- Basic Graph Pattern (BGP): Set of triple patterns with shared variables to bind during graph matching.
- Graph Federation: Querying multiple external knowledge endpoints (Wikidata, DBpedia) simultaneously in one query.
Labeled Property Graphs (LPG) & Neo4j
While RDF is strictly standardized for academic ontology reasoning, industrial engineering favors Labeled Property Graphs (LPG, e.g. Neo4j). In an LPG, nodes have labels (e.g. `:Person`, `:Company`) and internal key-value property maps (`name: 'Alice', age: 30`).
Relationships also carry labels and rich properties (`[:TRANSACTED {amount: $500, date: '2026-09-14'}]`). Neo4j's Cypher query language provides intuitive ASCII-art pattern matching: `MATCH (u:User)-[r:TRANSFERRED]->(m:Merchant) RETURN u, r`.
- Labeled Property Graph: Nodes and edges both carry arbitrary key-value attribute maps.
- Cypher Language: Declarative graph pattern matching syntax (`(node)-[:REL]->(node)`).
Level 4 Completed: Knowledge Graph & Semantic Systems Architect
Conferred for mastery of RDF semantic triples, SPARQL pattern matching engines, and Neo4j Labeled Property Graph implementations.
Message Passing Neural Networks (MPNN)
Standard deep learning models assume inputs are Euclidean grids (images) or sequences (text). Graph Neural Networks (GNNs) operate directly on irregular non-Euclidean graph topologies using the Message Passing paradigm.
In each GNN layer, every node $v$ executes three operations: 1) Message: computes messages $m_{u \to v}$ from all adjacent neighbors $u \in \mathcal{N}(v)$, 2) Aggregate: aggregates incoming messages via a permutation-invariant operator (Sum, Mean, Max), and 3) Update: updates its own node embedding $\mathbf{h}_v^{(l+1)}$ using a neural network.
- Permutation Invariance: The aggregation operator must produce the same result regardless of the order in which neighbors are listed.
- Receptive Field: Stacking $K$ message-passing layers allows each node to aggregate information from its $K$-hop neighborhood.
Graph Convolutional Networks (GCN)
Kipf and Welling (2016) introduced Graph Convolutional Networks (GCN), defining a first-order localized spectral approximation. GCN normalizes the adjacency matrix by node degrees to prevent nodes with high degrees from blowing up feature magnitudes.
The GCN layer equation multiplies the symmetrically normalized adjacency matrix $\mathbf{ ilde{D}}^{-1/2} \mathbf{ ilde{A}} \mathbf{ ilde{D}}^{-1/2}$ by the feature matrix $\mathbf{H}^{(l)}$ and learnable weight matrix $\mathbf{W}^{(l)}$, followed by non-linear activation $\sigma$.
- Self-Loops ($\mathbf{ ilde{A}} = \mathbf{A} + \mathbf{I}$): Ensures each node retains its own features during message aggregation.
- Symmetric Normalization: $ ilde{A}_{ij} / \sqrt{ ilde{D}_{ii} ilde{D}_{jj}}$ balances signals across dense hubs and sparse leaves.
Graph Attention Networks (GAT) & Over-Smoothing
GCN treats all neighbors equally according to graph degree. Veličković et al. (2017) introduced Graph Attention Networks (GAT), applying self-attention coefficients $lpha_{ij}$ to learn which neighbors are most important dynamically.
A fundamental disease in deep GNNs is Over-Smoothing: as layer depth increases ($K > 4$), repeatedly averaging neighbor features causes all node embeddings across the entire graph to converge toward the exact same uniform average vector, destroying discriminative power.
- Graph Attention ($lpha_{ij}$): Softmax-normalized attention scores weighting incoming neighbor messages.
- Over-Smoothing Mitigation: Jumping Knowledge networks, DropEdge regularization, and residual skip connections.
Level 5 Completed: Graph Neural Networks & Message-Passing Scientist
Conferred for advanced research mastery of MPNN message-passing frameworks, GCN spectral convolutions, GAT attention heads, and over-smoothing regularization.
The Limits of Baseline Vector RAG
Baseline vector RAG retrieves individual isolated text chunks based on semantic similarity. While effective for simple fact lookups ('What is the capital of France?'), it completely fails on global sensemaking queries ('What are the main themes across this entire 10,000-page dataset?').
Vector RAG suffers from fragmented context: it cannot connect the dots across multi-hop reasoning chains where entity A connects to B in chapter 1, and B connects to C in chapter 10. GraphRAG solves this by building an explicit knowledge graph over the entire corpus.
- Global Query Failure: Vector search cannot summarize themes that span millions of scattered chunks.
- Multi-Hop Disconnection: Inability to traverse associative chains across disparate documents.
Hierarchical Leiden Community Detection
Microsoft's GraphRAG pipeline extracts entities and relationships from raw text, building a dense knowledge graph. It then partitions this graph into hierarchical clusters using the Leiden community detection algorithm.
Leiden optimizes modularity while guaranteeing that all communities are well-connected without disconnected sub-fragments. Communities are structured in a multi-level hierarchy: Level 0 (fine-grained local clusters) $\to$ Level 1 (intermediate topics) $\to$ Level 2 (macro thematic domains).
- Leiden Algorithm: Fast community detection guaranteeing connected partitions with optimal modularity.
- Hierarchical Clustering: Organizing knowledge into nested multi-scale thematic communities.
GraphRAG Dual Search: Local vs Global
GraphRAG provides two complementary retrieval modes: 1) Local Search: for entity-specific queries, it retrieves the entity node, its immediate 1-hop neighbor subgraph, and associated raw text chunks.
2) Global Search: for thematic holistic queries, the LLM pre-generates community summaries for every cluster in the hierarchy. At query time, it evaluates all community summaries in parallel and synthesizes an exhaustive, evidence-backed global report.
- Local Search: Subgraph neighborhood traversal for pinpoint entity reasoning.
- Global Search: Map-Reduce over hierarchical community summaries for macro-thematic synthesis.
Level 6 Completed: GraphRAG & Hierarchical Community Systems Specialist
Conferred for advanced research mastery of corpus knowledge graph construction, Leiden community hierarchies, and GraphRAG dual search architectures.
Hypergraphs in Electronic Design Automation (EDA)
In standard graphs, an edge connects exactly two nodes. But in semiconductor circuit design, an electrical signal wire (a net) connects one output pin to dozens or hundreds of input gate pins simultaneously! This is a Hypergraph.
A Hypergraph $H = (V, E)$ consists of vertices $V$ (standard cell logic gates) and Hyperedges $E$, where each hyperedge is an arbitrary subset of vertices $e_i \subseteq V$. Standard graph algorithms fail on circuits without hypergraph modeling.
- Hyperedge: A connection spanning an arbitrary number of nodes ($|e| \ge 2$).
- Circuit Netlist: Verilog gate-level structural description represented as a directed hypergraph.
Hypergraph Partitioning & hMetis
Modern chips contain tens of billions of gates. To place and route them across multi-die chiplets or physical hierarchies, EDA engines must partition the hypergraph into $k$ balanced parts while minimizing the number of cut hyperedges (the Hypergraph Cut).
The hMetis algorithm achieves multilevel hypergraph partitioning: 1) Coarsening: collapsing hyperedges to reduce problem size by 100x, 2) Initial Partitioning: optimizing small core via Kernighan-Lin or Fiduccia-Mattheyses heuristics, and 3) Uncoarsening & Refinement.
- Hyperedge Cut Metric: $\text{Cut}(P) = \sum_{e \in E, |\text{parts}(e)| > 1} w(e)$.
- Multilevel Coarsening: Successively merging vertices to optimize global placement hierarchy.
Spectral Placement & Half-Perimeter Wirelength (HPWL)
Global placement calculates optimal $(x, y)$ coordinates for 50 billion gates to minimize Half-Perimeter Wirelength (HPWL): $\text{HPWL}(e) = (x_{\max} - x_{\min}) + (y_{\max} - y_{\min})$.
Because HPWL is non-differentiable, spectral and analytical placers (e.g. ePlace, DREAMPlace) use Poisson electrostatic analogies and the Hypergraph Laplacian to solve continuous optimization on GPU clusters in minutes.
- Half-Perimeter Wirelength (HPWL): Bounding-box perimeter estimating routing wire length.
- Electrostatic Analogy: Modeling gates as charged particles repelling each other to achieve uniform density.
Level 7 Completed: Distinguished Graph Systems & Topological Intelligence Fellow
Conferred for lifetime visionary leadership in graph mathematics: from spectral Laplacians and enterprise SPARQL knowledge graphs to Graph Neural Networks, hierarchical GraphRAG, and VLSI circuit hypergraph synthesis.