Graph

A graph consists of nodes, edges, and keywords

Similarity

Nodes

• Shortest distance
• Random walk distance
  • Hitting time
    • Expected length of a random path, i.e. $\frac{\text{Sum of Distances}}{\text{Number of Paths}}$
  • Commute time
    • Sum of hitting time of round trip
    • Single trip time can be different if the graph is directional
  • Personalized PageRank
    • Initial value of $r$ in PageRank is personalized, e.g. ${\left(\begin{array}{ccc}0& 1& 0\end{array}\right)}^T$
    • After iteration, we get the probability of random walker walks from $x$ to $y,z,\dots$
    • Said probability is protectional to the similarity
• Vertex embedding distance
  • Embed distance into nodes, i.e. $(x_1,y_1,z_1)$
  • Similarity is calculated based on the euclidean distance

The shorter the distance, the more similar the nodes

Graphs

• Maximum Common Subgraph (MCS)
  • The largest subgraph with the two graphs
• Graph edit distance (GED)
  • We increment the distance when editing edge, keyword, or node
• Graph embedding distance (GED)
  • Same as above

Partitioning

The “cut” is based on the number of edges and/or the workload of each partition

Graph Neural Network (GNN)

Types

• Graph Attention Network (GAN)
  • Popular
  • Performs better than GCN
• Graph Convolution Network (GCN)
• GraphSAGE (Sample and aggregate)
  • Performs well in a very large graph
• Message Passing Neural Network (MPNN)
  • Basic GNN model used in the earlier years
• Recurrent Graph Neural Network (RecGNN)
  • Basic GNN model used in the earlier years

Tasks

• Node-level task (grouping nodes)
• Edge-level task (node correlation)
• Graph-level task (graph category)

Embedding

• Node embedding
• Edge embedding
• Graph embedding

Steps

1. Initialize each node with an embedding vector (feature vector or randomized vector)
2. Update the embedding vector layer by layer ($0,1,2,\dots ,l-1,l$)
   • The update is done by the aggregate $A^{(l)}$ and update $U^{(l)}$ operation ($U^{(l)}$ could be MAX, MIN, AVG, or NN)
     • $N(a)$ is the neighbors of $a$
     • $M(a,b)$ is the message from $b$ to $a$
     • ${\mathrm{agg}}_a^{(l)}=A^{(l)}(\{M^{(l)}(x_j^{(l-1)},x_a^{(l-1)}\mid j\in N(a))\})$
     • $x_a^{(l)}=U^{(l)}(x_a^{(l-1)},{\mathrm{agg}}_a^{(l)})$
3. Generate the graph embedding vector according to all node embedding vector
   • This is the readout operation (R), which could be MAX, MIN, AVG, or NN
   • $z_G=R(x_i^{(l)}\mid i\in \text{node})$