# 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]] Multiset, mset or bag A bag is a set in which duplicate elements are allowed. An ordered bag is a list that we use in programming. . 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
Pages: 22

# Structural Equivalence on Graph

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

# 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: 22

# 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: 22

# 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: 22

# 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: 22

# Graph Cuts

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

# Graph Convolution Operator

Published:
Category: { Graph }
Tags:
Summary: For a given graph $\mathcal G$, we have an attribute on each node, denoted as $f_v$. All the node attributes put together can be written as a list $\mathbf f\to (f_{v_1}, f_{v_2}, \cdots, f_{v_N})$. Convolution on graph is combining attributes on nodes with their neighbors’. 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 $\mathbf A$ applied on all node attributes $\mathbf f$ is such an operation, i.
Pages: 22