Graph ML

graph_ml.md

Properties of relation

• Reflexive $x R x$, irreflexive, neither reflecive nor irreflexive (Sometimes reflexive, sometimes not depends on $x$)
• Symmetricity $a R b \implies b R a$

Graph

Metrics

• Average length
• Cluster factor (How well connected are neighbors of $n_i$)

Motifs

1. Breakdown to subgraph types (3 nodes 13 types)
2. Draw over/underrepresented chart of all types

Graph cut

Dense community with few connections between them are interesting

Def

• Minimize $n_cut/\min(|A|,|B|)$
• NP hard

Approx: Spectral cluster

• Requirements
  • $A$: Adj matrix
  • $D$: Degree matrix
  • Laplacian matrix: $L=D-A$
• Calc
  • Eigen-

Graph Embedding

Ingredients

• Simmilarity function between nodes
• Encode function

TransE

• $h + l \approx t$
• Loss $[\gamma+d(h+l,t)-d(h'+l,t')]_+$
  • Why $d(h'+l,t')$
    1. King rules country
    2. People rule country
    3. King is close to people
  • Why $\gamma$

    • A--→B
      |\
      | \
      ↓  ↘
      D   C
      

    • A, B, C, D are in unit circle
• Weakness arxiv

GraphNN

GraphSAGE ↓

• Aggregation function

Graph Attention

• Not every neighbor is equally important

Recommendation with graph

GraphConv

• Spectral decomposition?
• This weakness