5. Graphs

Question 1

What is the goal of graph partitioning?

Answer 1

To find densely linked clusters in a graph that represent communities of some kind

Question 2

What makes a good graph partition?

Answer 2

1. Maximizes the number of within-group connections
2. Minimizes the number of between-group connections

Question 3

What is the equation for the cut of a graph?

Answer 3

When you split a graph into 2 subgraphs A and B, you sum the weights of edges which have one endpoint in A and the other in B

Question 4

What is the issue with splitting graphs by the minimal cut?

Answer 4

It only considers external cluster connections and not internal connectivity so our minimum cut may be uninteresting or sub-optimal

Question 5

What is the normalized cut?

Answer 5

Measures connectivity between groups in a graph relative to the density of each group

Question 6

What is the formula for normalized cut?

Answer 6

ncut(A,B) = (cut(A,B)/vol(A)) + (cut(A,B)/vol(B))

Question 7

What is the volume of a group in a graph?

Answer 7

The total weight of all edges with at least one endpoint within the group

Question 8

What are the 3 basic stages of spectral clustering?

Answer 8

1. Preprocessing: construct a matrix representation of the graph
2. Decomposition: compute eigenvalues and eigenvectors of the matrix and map each point to a lower-dimensional representation based on one or more eigenvectors
3. Grouping: Assign points to two or more clusters based on the new representation

Question 9

What is an adjacency matrix?

Answer 9

A matrix representation of a graph that has an entry for each node pair.
It is symmetric if unweighted and undirected.
If the nodes are connected their entry is 1 or the weight of the edge

Question 10

What is a degree matrix?

Answer 10

A matrix representation of a graph that has an entry for each node pair.
It is a diagonal matrix as we only fill out entries where a node intersects with itself
Each entry is the degree of the node

Question 11

How do we compute the Laplacian Matrix?

Answer 11

L = D - A
Where D is the degree matrix and A is the adjacency matrix

Question 12

How does the Laplacian matrix fit into spectral partitioning?

Answer 12

We build the Laplacian matrix of the graph, compute eigenvalues and eigenvectors of the matrix, and then group the points based on some criteria

Question 13

How do we decide where to split an eigenvector to cluster the nodes?

Answer 13

Naive approach is to split at 0 or median value
There are other complicated expensive approaches

Question 14

How can we partition a graph into k clusters instead of just 2?

Answer 14

1. Recursive bi-partitioning where we recurively apply bi-partitioning hierarchically and divisively
2. Cluster multiple eigenvectors and build a reduced space from them

Question 15

Why do we not use recursive bi-partitioning for k-way spectral clustering?

Answer 15

It is inefficient and unstable

Question 16

What is the issue with spectral clustering?

Answer 16

It cannot perform overlapping communities. It only shows disjoin communities and splits the nodes into their groups

Question 17

What is the trick to finding overlapping communities?

Answer 17

Overlapping communities tend to have higher edge density as they are linked to multiple groups

Question 18

What is the community-affiliation graph model?

Answer 18

Generative model to create graph representation of communities

B(V, C, M, {pc}) where V is the set of nodes, C is the set of communities, M is the set of community memberships for the nodes, pc is the set of probabilities for each community c

Question 19

For the AGM model when do we decide to link 2 nodes?

Answer 19

Each pair of nodes in a community are connected with the probability of that community

P(u,v) = 1 - Product(1-pc) for communities c shared by u and v

Question 20

What is the formula for probability of an edge between 2 nodes within a single community if community memberships can have strengths?

Answer 20

P(u, v) = 1 - exp(-FuA * FvA)

Where FuA is the strength of u’s membership to A from the Factor matrix F
FvA is the strength of v’s membership to A from the factor matrix F

Question 21

What is the formula for probability of an edge between 2 nodes for any community if community memberships can have strengths?

Answer 21

P(u, v) = 1 - exp(-Fu * Fv)

Where Fu is the vector of membership strengths for node u and Fv is the vector of membership strengths for node v.
Fv must be transposed in order to perform dot product correctly

Question 22

What is the advantage of AGM over spectral clustering?

Answer 22

AGM can express a variety of community structures including non-overlapping, overlapping, and nested

Question 23

How do we extend AGM to work for directed graphs?

Answer 23

Nodes can have outgoing memberships where the node sends an edge (outdegree) and incoming memberships where the node receives an edge (indegree).

We also use 2 factor matrices F and H. F is the outgoing community membership strengths and H is incoming

Question 24

What is the formula for probability of an edge between 2 nodes for any community if community memberships can have strengths and the graph is directed?

Answer 24

P(u, v) = 1 - exp(-Fu * Hv)
Where Fu is the vector of outgoing community membership strengths for node u and Hv is the vector of incoming community membership strengths for node v

Question 25

What is the purpose of graph trawling?

Answer 25

Finding small communities within a large web graph

Question 26

How do we perform trawling on a graph?

Answer 26

1. View each node i as a set of nodes i points to
2. For a given support threshold, we want to find sets of size t that occur in s sets to create a complete bipartite graph Ks,t