Graph learning · 2020
Why graph walks work for semi-supervised learning
A short note on the intuition behind random walk methods for node classification and why the graph structure matters more than the labels.
The core insight behind our WSDM 2020 and ICDM 2019 work is simple but easy to overlook: in a network where similar nodes connect to similar nodes, the structure itself is a signal.
Most semi-supervised approaches treat the graph as a constraint — a regularizer that discourages nearby nodes from having very different labels. We treated it differently. A walk that starts at an unlabeled node and wanders through the network tells you something about that node's community, its role, its typical neighbours. If you aggregate those walks carefully, you can learn a classification policy from very few labelled examples.
The learned walk policy (trained with policy gradient) selects which neighbours to visit at each step. This is different from a fixed random walk: the agent learns that certain link types are informative for a given task and others are noise. The result is a representation that is shaped by the task, not just by the graph topology.
What I find most useful about this framing is that it scales naturally to heterogeneous graphs — graphs with multiple node types and edge types — because the walk policy can learn to navigate across types. That was the direction we pushed in the ICDM follow-up.