graph-level problem

Data

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

Graph-Level Problems

In graph-level problems, there are multiple graphs. Each graph $G$ represents a predictor associated with an observation $y\in Y$. We assume that $G,y\sim p(G,y)$ and want to regress $y$ on $G$.

Here, our hypothesis class is \cal{F}=$$\left\{ f(S) = \sum_{k=1}^{K-1} h_{k}S^k \mathbb{1} | h_{k} \in \mathbb{R} \right\}

$1$ as our constant signal!

Since there are no graph signal observations, we use the vector of all ones

And our minimization problem is given by ${\min }_{h_k}\frac{1}{m}{\sum }_{i=1}^M\ell \left({\sum }_{k=0}^{K-1}{h}_k{S}^{k}1,y\right)$

Example

Suppose we want to predict the number of triangles incident to each node for any graph

In this example, since our output is an integer, it mades sense to use the $0-1$ loss or a surrogate: ${\min }_{h_k}\frac{1}{m}{\sum }_{i=1}^M\ell \left({\sum }_{k=0}^{K-1}{h}_k{S}^{k}1,y\right)$ Application: automate triangle counting

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