spectral embedding

[[concept]]

Spectral Embedding

Suppose we are given a diagonalizable adjacency matrix $A$ for a graph with nodes partitioned into $C$ classes. Suppose we know the assignments for some of the nodes $T \subset Vertices$ . Let $V_{c}$ be the top $C$ eigenvectors of $A$ .

Finding the spectral embedding amounts to solving the problem$$\min_{f} \sum_{i \in T} \mathbb{1}(f(A){i} = y)$$ where $f$ comes from our hypothesis class ${f : f (A) = σ (V_{c} W), W \in R^{C \times C}}$ and $σ$ is a predetermined pointwise nonlinearity.

Notes

This can be thought of as an FC-NN on the $C$ -dimensional embeddings $u_{1}, \dots, u_{n}$ of the nodes of the graph into feature space.

in practice, a surrogate is usually used for the 0-1 loss
to find the optimal $f$ ie the optimal $W$ , we solve using gradient descent methods
this is the semi-supervised version of spectral clustering (clustering assigns communities to all nodes, embedding assigns communities to nodes with unknown community)
^definition

Spectral Embedding Problem

$min_{f} \sum_{i \in T} 1 (f (A)_{i} = y_{i}), f \in {f (A) = σ (V_{c} W), W \in R^{C \times C}}$

^problem

References

const modules = await cJS()

const COLUMNS = [  
	{ id: "Name", value: page => page.$link },  
	{ id: "Last Modified", value: page => modules.dateTime.getLastMod(page) },
];  
  
return function View() {  
	const current = dc.useCurrentFile();
// Selecting `#game` pages, for example. 
	let queryString = `@page and linksto(${current.$link})`;
	let pages = dc.useQuery(queryString);
	
	// check types
	pages = pages.filter( (p) => !modules.typeCheck.checkAll(p, current) ).sort()
	
	
	return <dc.Table columns={COLUMNS} rows={pages} paging={20}/>;  
}

return function View() {
	const file = dc.useCurrentFile();
	const created = file.value("created");
	const modified = file.value("modified")
	
	let earliest;
	if (created) {
		earliest = moment(created.toString()).isBefore(moment(file.$ctime))
		? created.toString()
		: file.$ctime;
		} else {
		earliest = file.$ctime
	}
	
	let latest = (Array.isArray(modified) && modified.length > 0)
		? modified[-1]
		: file.$mtime;
	
	let earlyString = moment(earliest).format("YYYY-MM-DD");
	let lateString = moment(latest).format("YYYY-MM-DD")
	return <p class="dv-modified">Created {earlyString}     ֍     Last Modified {lateString}</p>
}

spectral embedding

References

See Also

Mentions