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 \text{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}1(f(A{)}_i=y_i)$ where $f$ comes from our hypothesis class $\{f:f(A)=\sigma (V_{c}W),W\in {\mathbb{R}}^{C\times C}\}$ and $\sigma$ is a predetermined pointwise nonlinearity.

Notes $C$-dimensional embeddings $u_1,\dots ,u_n$ of the nodes of the graph into feature space.

This can be thought of as an FC-NN on the

• 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)

Spectral Embedding Problem

${\min }_f{\sum }_{i\in T}1(f(A{)}_i=y_i),f\in \{f(A)=\sigma (V_{c}W),W\in {\mathbb{R}}^{C\times C}\}$

References

References

See Also

Mentions

Mentions

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>
}