Years ago I wrote macro code to do something like this. Open this diagram in the desktop app (not Visio for the web) and look at the Shape Data for several of the connectors -- you'll notice that there isn't any. Then run the macro called GetFlowchartConnections that's in the document and look at the connectors again. You'll notice that each one now includes a From and a To data field with the text from the adjoining shapes.
Does this help? If so, from here you could use the Visio report wizard (Review>Shape Reports) to export the data to Excel.
This may not be exactly what you had in mind but let me know if it's heading in the right direction.
On a related note: Do you have Visio Plan 2? If so, have you experimented with the Export to Word feature on the Process tab? It doesn't export the data in the way you're asking about but it does break a process map down into sections that specifically show the preceding and following steps for each step in the process. Here's an example: