node-level task

Data

subject:: Data Science Methods for Large Scale Graphs parent:: Graph Signals and Graph Signal Processing theme:: math notes

Node-Level tasks

Node-level tasks (sometimes called inductive learning or semi-supervised learning) have graph $G$ as the data support (ie, it is fixed). Here, we examine each node as a sample, ie we assume that the signal and observation at node $i$ is $x_i,y_i\sim p(x,y)$. ie, each node is treated as a sample.

We assume we only observe $y_i$ for a subset of the nodes $J\subset V$ and want to estimate $y_j,j\in V\setminus J$

Example

Consider the contextual SBM: $G=(V,E)$ undirected and $y\in \{-1,1{\}}^n$ (say $y_i$ represents the community of node $i$). The edges are random: $P(A_{ij})=P((i,j)\in E)=\{\begin{array}{l}\frac{a}{n},y_i=y_j\\ \frac{b}{n},\text{otherwise}\end{array}$ with node features/covariates $x_i=\sqrt{\frac{u}{n}}{y}_{i}u+z_i$ where $u\sim N(0,1),z\sim N(0,I_n)$

If $u=1$ then $x_i\sim N\left(0,\sqrt{\frac{1}{n}(1{)}^2+1}\right)$ and if $u=0$ then $x_i\sim N\left(0,\sqrt{\frac{1}{n}(-1{)}^2+1}\right)$

Goal: predict $y_i,i\in V\setminus J$ from $x_i\in V$ hypothesis class: the graph convolutions \cal{F}=$$\left\{ z=\sum_{k=0}^{K+1}h_{k}S^kx, h_{k}\in\mathbb{R} \right\}

Problem: Define a mask $M_f\in \{0,1{\}}^{|J|\times n}$. Then $M_f{1}_n=1_{|J|}$ and $1_{|J|}^T{M}_f=1_n^T$. Then we minimize: ${\min }_{h_k}\frac{1}{f}\ell \left(M_f\cdot y,M_f{\sum }_{k=0}^{K-1}{h}_k{S}^k(M_f)x\right)$ Application: infer node’s class/community/identity locally ie without needing communication, determining clustering techniques, which require eigenvectors (global graph information)

Mentions

TABLE
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link), 1, "") + choice(contains(author, this.file.link), 1, "") + choice(contains(director, this.file.link), 1, "") + choice(contains(source, this.file.link), 1, "") as direct_source
 
WHERE !direct_source