# Weisfeiler-Lehman Kernel

Published:
Category: { Graph }
Tags:
Summary: The Weisfeiler-Lehman kernel is an iterative integration of neighborhood information. We initialize the labels for each node using its own node degree. At each step, we take the neighboring node degrees to form a multiset. At step $K$, we have the multisets for each node. Those multisets at each node can be processed to form an representation of the graph which is in turn used to calculate statistics of the graph. Iterate $k$ steps This iteration can be used to test if two graphs are isomorphism1. Shervashidze2011 Shervashidze N, Schweitzer P, van Leeuwen EJ, Mehlhorn K, Borgwardt KM.
Pages: 20

# Structural Equivalence on Graph

Published:
Category: { Graph }
Tags:
Summary: Structural Equivalence means that nodes with similar neighborhood structures will share similar attributes.
Pages: 20

# Node Degree

Published:
Category: { Graph }
Tags:
Summary: Node degree of a node $u$ $$d_u = \sum_{v\in \mathcal V} A[u,v],$$ where $A$ is the adjacency matrix.
Pages: 20

# Local Variant of Clustering Coefficient

Published:
Category: { Graph }
Tags:
Summary: $$c_u = \frac{ \lvert (v_1,v_2)\in \mathcal E: v_1, v_2 \in \mathcal N(u) \rvert}{ \color{red}{d_n \choose 2} },$$ where $\color{red}{d_n \choose 2}$ means all the possible combinations of neighbor nodes, and $\mathcal N(u)$ is the set of nodes that are neighbor to $u$. Ego Graph If $c_u=1$, the ego graph of $u$ is fully connected; If $c_u=0$, the ego graph of $u$ is a star.
Pages: 20

# Homophily on Graph

Published:
Category: { Graph }
Tags:
Summary: Homophily is the principle that a contact between similar people occurs at ahigher rate than among dissimilar people – McPherson20011 McPherson2001 McPherson M, Smith-Lovin L, Cook JM. Birds of a Feather: Homophily in Social Networks. Annu Rev Sociol. 2001;27: 415–444. doi:10.1146/annurev.soc.27.1.415  ↩︎
Pages: 20

# Heterophily on Graph

Published:
Category: { Graph }
Tags:
Summary: Heterophily is the tendency to differ from others. Heterophily on a graph is the tendency to connect to nodes that are different from itself, e.g., nodes with different attributes have higher probability of edge.
Pages: 20

# Graph Laplacians

Published:
Category: { Graph }
Tags:
Summary: Laplacian is a useful representation of graphs. The unnormalized Laplacian is $$\mathbf L = \mathbf D - \mathbf A,$$ where $\mathbf A$ is the adjacency matrix Graph Adjacency Matrix A graph $\mathcal G$ can be represented with an adjacency matrix $\mathbf A$. There are some nice and clear examples on wikipedia1, for example, $$\begin{pmatrix} 2 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}$$ for the graph Public Domain, Link and $\mathbf D$ is the degree matrix, i.
Pages: 20

# Graph Cuts

Published:
Category: { Graph }
Tags:
Pages: 20