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 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} \neq 0 \forall i$ and
$λ_{i} \neq λ_{j}$ for all $i \neq 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} ℓ (f (A, X)_{i}, y_{i})$

where $ℓ (\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) = Φ_{H} (A, X)$ , a GNN with learnable parameters $H$ (this is the form of the function we defined in lecture 5)

Mentions

File
2025-02-12 graphs lecture 7