we can use GNNs to solve feature-aware semi-supervised learning problems

[[concept]]

Takeaway

We can use GNNs to solve the semi-supervised community detection node-level task on graphs.

Let $G$ be a graph with diagonalizable adjacency matrix $A$ and node features $X\in {\mathbb{R}}^{n\times d}$. Suppose we have $C$ communities that we want to assign to the nodes.

As long as $X$ satisfies the conditions for finding a convolutional graph filter, namely that

• ${\hat{x}}_i\ne 0\forall i$ and
• ${\lambda }_i\ne {\lambda }_j$ for all $i\ne j$

then there exists a graph convolution (or a 1-layer linear GNN) that approximates $y$. The optimization problem then is the same as before:

Community Detection Optimization Problem ${\min }_f{\sum }_{i\in J}\ell (f(A,X{)}_i,y_i)$ where $\ell (\cdot )$ is a surrogate of the 0-1 loss, each $y_i$ is the one-hot community vector of node $i$, and $f$ is some parametric function of $A$ and $X$

And we can choose our hypothesis class so that $f(A,X)={\Phi }_H(A,X)$, a GNN with learnable parameters $H$ (this is the form of the function we defined in lecture 5)

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