search

jwcalder / GraphLearning

Python package for graph-based clustering and semi-supervised learning
MIT License
85 stars 26 forks source link

Question about shift trick #2

Closed shwangtangjun closed 3 years ago

shwangtangjun commented 3 years ago

Thanks for your work! I find the shifting skill simple and interesting, however, it seems that the implementation in the code is different from what is in the paper.

Paper

1

Code https://github.com/jwcalder/GraphLearning/blob/a137e304e994562c77176f365892f55ee9d3f592/graphlearning/graphlearning.py#L2335-L2344

You subtract mean of output u, which is

2

I have tried subtracting the y_w described in the paper but can't get satisfying results ( accuracy below 15% for 1 labeled sample per class). Could you help explain the difference?

shwangtangjun commented 3 years ago

Also, could you provide some thought on the stopping condition ' v --> vinf '? I have no idea where it comes from. It seems that it's not mentioned in the paper. https://github.com/jwcalder/GraphLearning/blob/a137e304e994562c77176f365892f55ee9d3f592/graphlearning/graphlearning.py#L2562

jwcalder commented 3 years ago

Regarding the shift trick, we had an error in our code that always shifted by the mean value after shifting by y_w. We will correct this in the next journal version of the paper. Indeed, you need to shift by the mean and not y_w. The difference is possibly quite small, since y_w should be close to the mean of u, but the scoring function u is so flat that even a small difference can be significant. The arguments later in the paper connecting to Poisson learning are equally valid in both cases.

Regarding your second question, the stopping condition v -> vinf is the mixing time stopping condition described in our paper on the right side of page 6 near the bottom. It runs the Poisson learning iterations until the random walks have sufficiently mixed.

shwangtangjun commented 3 years ago

Yeah you are right about "a small difference can be significant". For example in one trial in MNIST with 10 labeled points:

y_w=[0.12175954 0.08535535 0.09380349 0.09859625 0.09878728 0.08385491 0.11197693 0.08958659 0.11030213 0.10597753]
mean=[0.17887512 0.05756588 0.0893375 0.09388537 0.08571841 0.05030871 0.11645314 0.07309792 0.13852043 0.1162375]

but 

u - y_w       acc=10.23% 
u - mean      acc=78.78%

And for the stopping condition, I missed that part earlier. Thanks for pointing out.