This happens a lot when the knives are more carbon steel vs. stainless steel. I have many Japanese knives, and this happens when I don't immediately wipe off the blade after washing, or when cutting up more acidic foods, and not wiping the knife off with a damp towel.
I use a Japanese rust eraser, and most if not all rust will come off, and it will not scratch the knife's surface if you run along the grain of the metal. These eraser are pretty inexpensive at your local japanese market, or you can get them on line. They have a small amount of abrasive on it.
In your case, it will be a bit difficult, as the grain of your knife is going up and down the knife. But if you don't care too much about a bit of scratching, then you could run the eraser length wise or side to side, along your knife.
Another alternative is to use a non scratching powdered cleanser, such as Bon Ami or Bar Keepers Friend and a cut potato or dai-kon (asian radish) to polish the blade. Try a small area first and then if it works, polish the whole blade. Wash and dry immediately.
To see a demonstration of this technique I would watch some youtube videos by, Jon Broida, at Japanese Knife Imports. He is a master knife sharpener and knife shop owner in Los Angeles.