DM6 - Spectral Theory and Clustering Flashcards

Question 1

What is the primary goal of graph mining?

Accepted Answer

To extract meaningful patterns, structures, and insights from data represented as networks of interconnected nodes.

Question 2

How is a graph formally defined in mathematics?

Accepted Answer

As a pair $G=(V,E)$, where $V$ is a set of vertices (or nodes) and $E$ is a set of edges connecting pairs of vertices.

Question 3

What is an Adjacency Matrix ($A$)?

Accepted Answer

An $n 	imes n$ matrix where the entry $a_{ij} = 1$ if there is an edge between vertex $i$ and vertex $j$, and $0$ otherwise.

Question 4

What does multiplying an Adjacency Matrix by a feature vector ($Ax$) intuitively represent?

Accepted Answer

It represents the aggregation or propagation of a signal, where each node receives the sum of the values from its immediate neighbors.

Question 5

For an undirected graph, what important mathematical property does the Adjacency Matrix possess?

Accepted Answer

It is a symmetric matrix, meaning its eigenvalues are real numbers and its eigenvectors are orthogonal.

Question 6

What is the Degree Matrix ($\Delta$ or $D$)?

Accepted Answer

A diagonal matrix where each diagonal entry $\Delta_{ii}$ represents the total degree (number of connections) of node $i$.

Question 7

What is the mathematical definition of the Unnormalized Laplacian Matrix ($L$)?

Accepted Answer

$L = \Delta - A$

Question 8

What is the mathematical definition of the Normalized Symmetric Laplacian ($L^{sym}$)?

Accepted Answer

$L^{sym} = I - \Delta^{-1/2} A \Delta^{-1/2}$

Question 9

What is the Random Walk Laplacian ($L^{rw}$)?

Accepted Answer

$L^{rw} = I - \Delta^{-1} A$

Question 10

What does the quadratic form $x^{	op}Lx$ calculate in the context of graphs?

Accepted Answer

It calculates the sum of squared differences between the values of connected nodes: $\sum_{(i,j) \in E} (x_i - x_j)^2$.

Question 11

What is the trivial eigenvector and corresponding eigenvalue for any Graph Laplacian?

Accepted Answer

The vector of all ones ($1$) is an eigenvector with an eigenvalue of $0$.

Question 12

What is the objective of the Minimum Cut (MinCut) problem?

Accepted Answer

To partition the nodes of a graph into two disjoint sets such that the total weight (or number) of edges crossing between the sets is minimized.

Question 13

Why is the Normalized Cut often preferred over the standard Minimum Cut?

Accepted Answer

Because the standard Minimum Cut often results in unbalanced partitions (like isolating a single node);Normalized Cut penalizes these unbalanced splits.

Question 14

What is the Rayleigh Quotient?

Accepted Answer

The mathematical expression $\frac{x^{	op}Lx}{x^{	op}x}$, which is minimized to find the optimal relaxed partition for a graph.

Question 15

What is the Fiedler Vector?

Accepted Answer

The eigenvector corresponding to the second smallest eigenvalue of the Laplacian matrix, used to optimally bi-partition a graph.

Question 16

What are the three core phases of the Spectral Clustering algorithm?

Accepted Answer

1. Preprocessing (building the Laplacian), 2. Decomposition (computing eigenvectors), and 3. Grouping (running $k$-means on the lower-dimensional eigenvector space).

Question 17

How is $k$-way spectral clustering performed?

Accepted Answer

By computing the first $k$ eigenvectors of the Laplacian, arranging them into a matrix to embed the nodes into $k$ dimensions, and then applying a standard clustering algorithm like $k$-means.

Question 18

What is a major advantage of Spectral Clustering over standard $k$-means?

Accepted Answer

It can identify clusters of highly complex, non-convex, or intertwined shapes, relying on connectivity rather than pure spatial distance.

Question 19

What is the main computational bottleneck or disadvantage of Spectral Clustering?

Accepted Answer

It requires computing the eigenvalue decomposition of an $n 	imes n$ matrix, which has a worst-case time complexity of $\mathcal{O}(n^3)$ and scales poorly on large, dense graphs.

DM6 - Spectral Theory and Clustering

Card Preview

Related Flashcard Sets

Classical Mechanics - Newtonian Laws & Energy Conservation

General Pharmacology - Pharmacodynamics & Pharmacokinetics

Neuroscience Fundamentals - Brain Anatomy & Neurotransmitters

Cell Biology - Cellular Structure & Function