Topics

Persistence Diagram of a Graph

Kowshik Thopalli
 

Hi,
If I have a graph with nodes and edges and I know the edge weights, how to think about getting a filtration and hence persistent homology/persistence diagram of this graph. 
Is it doable in Dionysus?

nchristianson@...
 

So it depends - how would you like to filter your graph? Do you want to add edges by increasing weight (e.g., say you have positive integer weights, and so you add all edges of weight 1 as the first step in the filtration, and then in the second step you also include all edges of weight 2, etc.)? If so, then if you have the weighted adjacency matrix of the graph, this weighted adjacency matrix can also act as a distance matrix for creating a Vietoris-Rips filtration, which will give you the persistent homology of this graph filtration. If W is your weighted adjacency matrix, then the code for this would be:

import dionysus as d
from scipy.spatial.distance import squareform

sq_dist = squareform(W)
f = d.fill_rips(sq_dist, k, np.max(W)) # creates the k-skeleton of the Vietoris-Rips filtration (edge weight filtration) of the graph
m = d.homology_persistence(f) # calculates persistent homology

and from here, there are some examples on the site for how to plot the barcode, extract cycles, etc. If you want to build a different filtration, this is also possible by manipulating the values of the distance matrix so certain edges are introduced before others.

Kowshik Thopalli
 

Thank you very much for your inputs. 
I will follow those steps.
I have the following two questions.
1. when I don't have an edge between two nodes, in my adjacency matrix I will represent it as 0 or +inf?(+ inf- because as you said I have to treat it as a distance mattix right)

2. This is a follow-up question.
Now what if I have a feature vector of D dimensions at each node. In that case can you suggest me some ways of thinking about filtration. This is a common occurrence in modern deep learning applications on graphs such as graph convolutional networks.

nchristianson@...
 

To answer your first question, you should represent the lack of an edge as +inf (because the filtration is being represented as a distance matrix, and so an infinite distance means that an edge between those nodes will never be introduced).

With regard to your second question, it sort of depends; what do these feature vectors represent? I can think of two possibilities of getting a filtration from these: (1) if you can pick some ordering on the feature vectors (say, for example, lexicographic ordering, where (x_1, ..., x_n) < (y_1, ..., y_n) if x_1 < y_1,  or if x_j = y_j for all j from 1 to (i - 1) and x_i < y_i), and then create a filtration by introducing nodes by their feature vector order - in this node-ordered case, at each step you would introduce the next node in the ordering and all of its connections to previous nodes.

(2) You might think about introducing edges based off of cosine similarity between the feature vectors of the nodes on either side of that edge; then you could filter by values of the similarity (i.e., introducing edges which connect nodes with very similar feature vectors first, and gradually decreasing the required threshold of similarity).

Hope this helps.