[Question] Does Poisson learning require symmetric graphs?

[shekkizh]

Hi, I was wondering how important is it that the input graphs are symmetric for Poisson/PoissonMBO learning algorithms? I read the paper and skimmed through the proofs and found that the symmetric nature is used only for the variational interpretation theorem-proof but the algorithm itself seems to not depend on this property. Am I missing something?

Regards, Sarath

[jwcalder]

Hi Sarath,

Thanks for your question. Poisson learning does indeed work on directed graphs, but we did not describe this in our paper. The only change that is needed is to work with the Laplacian L=D-W^T instead of L=D-W in the main equation (2.3) in our paper. Also, the fancy stopping condition we used based on mixing times does not seem to work so well on directed graphs.

You are correct that the variational interpretation requires symmetry. The random walk interpretation given in Section 2.1 in our paper works for directed graphs and leads to the L=D-W^T Laplacian if you follow the arguments carefully without assuming symmetry.

I just updated the code now so you can choose for the weight matrix not to be symmetrized (with symmetrize=False or the -z flag). Previously the weight matrix was automatically symmetrized in the code. I also added a demo script "directedgraphs_demo.py" showing how to run Poisson learning on a non-symmetric k-nearest neighbor graph.

Only Poisson and PoissonMBO will work on directed graphs, and all other algorithms may be unpredictable since they were coded for symmetric graphs.

We have in mind to work on applying Poisson learning to problems on directed graphs at some point. It's a great project for a grad student to work on.

Best, Jeff

[shekkizh]

Hi Jeff, Thanks for the reply and the code update. Poisson learning presents an interesting way to cope with the shortcomings of label propagation when very few labels are available. I primarily work on graph learning and a thing to note is that most of the graphs constructed on data are generally directed by nature (including standard K-nearest neighbor). It would be interesting to see how poisson learning performs with various graph learning methods.

Thanks again for the resposne and for open-sourcing the code. Regards, Sarath