# Graphs Regular structures are subsets of graphs. Ex: images are grid graphs. ![[graphsvsstructures.jpg]] ## Neighborhood The neighborhood of a node is all nodes directly connected to it $ \mathcal{N}(i)=\{j:(i, j) \in \mathcal{E}\} $ The degree of the node is the number of neighbors: $d_{i}=|\mathcal{N}(i)|$ - The diagonal matrix $D$ contains all degrees per node. ## Attributes Node features $x$. $v \rightarrow \mathbb{R}^{d}, X=\left(x_{1}, \ldots, x_{n}\right)$ Edge features $e_{i j}: \varepsilon \rightarrow \mathbb{R}^{d^{\prime}}$ If $d^{\prime} \in \mathbb{R}$ we simply have a weighted graph ## Adjacency matrix An $n \times n$ matrix $A$, for $n$ nodes $A_{i j}=\left\{\begin{array}{l}1 . \mathrm{ff}(\mathrm{i}, \mathrm{j}) \in \mathcal{E} \\ 0 \mathrm{jf}(\mathrm{i}, \mathrm{j}) \notin \varepsilon\end{array}\right.$ When the edges have weights, so does the adjacency matrix. ## Graph Laplacian A matrix representation of a graph: $\Delta=(D-(A)$ Normalize to cancel out skewing by the degree matrix (because the ordering is arbitrary) $ \Delta=D^{-1}(D-A)=I-D^{-1} A $ Or for better symmetry $ \Delta=D^{-1 / 2}(D-A) D^{-1 / 2}=I-D^{-1 / 2} A D^{-1 / 2} $ ## Local difference operator The local difference operator $ (\Delta x)_{i}=\frac{1}{d_{i}} \sum_{j \in \mathcal{N}(i)} w_{i j}\left(x_{i}-x_{j}\right) $ A bit similar to a convolution. ## Dirichlet energy Measures the smoothness of the signal in the graph $ E(X)=\sum_{i \in V} \frac{1}{d_{i}} \sum_{j \in \mathcal{N}(i)} w_{i j}\left\|x_{i}-x_{j}\right\|^{2}=\operatorname{trace}\left(\mathrm{X} \Delta \mathrm{X}^{\mathrm{T}}\right) $ The bigger differences $\left(x_{i}-x_{j}\right)$ between all possible neighbors The bigger the 'energy' in our graph. ## Common Graph algorithms Great visualization/description resource: https://algorithms.discrete.ma.tum.de/ Connectivity - [[Union Find]] - Find if two components are connected or not in O(log n) time. Traversal - BFS - DFS (pre/in/post) - Topological Sort Shortest Path (weighted graphs) - Dijkstra: From a single source, find shortest path to all nodes - Bellman-Ford: Same as Dijkstra, but works for negative numbers and cheapest-flights-within-k-stops - Floyd-Warshall Algorithm - A* search Minimum Spanning Trees - Prim's algorithm - Kruskal's algorithm Matching - Hungarian Method Network flow (min/maximal) - Cycle-canceling algorithm - minimal flow - Ford-Fulkerson algorithm - maximal flow Routing - Hierholzer's Algorithm - Eulerian Path problem - Chinese Postman - Use each edge atleast once and return to start - Traveling Salesman Problem - mimum length tour of all nodes, return to start --- ## References 1. Lecture 7.2, UvA Deep learning course 2020