Unsupervised Learning and Graphs
Graph problems that you solve routinely fall into one of the following categories:
Prediction with Partial Graphs: Given a graph that is partially observed, can you predict node property values on unobserved nodes? Can you predict if an unobserved pair of nodes are connected by an edge?
Graph Structure Inference from Node Signals: Given values or signals assigned to the nodes, can you infer the underlying graph structure? Here, you lack explicit examples of which nodes should be connected, and the challenge is to determine the connections that best explain the observed node signals.
So if you are like me, you are probably thinking that the second example is a candidate for unsupervised learning and I agree. The problem is that you will run into the problem of selecting a threshold value in your learning task. For example, if you choose to cluster nodes using the notion of similarity or distance, then you need to decide that nodes that are closer or more similar than a threshold value are connected. If you have access to domain knowledge or have a good understanding of the problem you are trying to solve, you can come up with reasonable solutions.
What I wanted to talk about in this post is that you can appeal to Graph Signal Processing for help too. I am not going into the details, rather, I am going to discuss the intuition and the motivation and point you to some references if you want to find out more. The ideas are from this paper (Dong et al. 2019). There is an excellent youtube talk that covers the ideas in this paper (Dong 2019).
Given observations on the nodes of a graph the paper (and talk) discuss three approaches to learning the associated graph.
- By choosing how smooth you want your signal to be. When a signal is observed on the nodes of a graph, the eigen decomposition of the laplacian of the graph tells us how smoothly the signal will vary over the nodes of the graph. We can control the smoothness with a regularization term, i.e., you pick a regularization term that makes the signal smooth enough for your particular problem. This is your choice as a modeler. Learning the graph laplacian translates to learning the graph. The graphical lasso (Friedman, Hastie, and Tibshirani 2008) is used to learn the laplacian.
- By selecting how a signal should diffuse through a graph. Diffusion on graphs, associated kernels is an extensive topic. If the diffusion perspective is right for your application, for example in disease modeling, then this might appeal to you.
- By assuming a causal structure. If you have a causal model associated with the variables of the graph, you can use this approach to learning the graph.
The smoothness idea appeals to me. If you are wondering “what did we actually solve, we just traded threshold selection for smoothness selection?”, here is connecting the dots. It turns out that the covariance matrix that we can compute from the data that we observe can be used to estimate the graph laplacian through the Graphical LASSO. You will need to select a regularization constant. Estimating this is not too difficult, for example if you are working with say temperature data recorded at physical locations, you can note the temperature readings at a set of cities and you can adjust the regularization constant so that the variation produced by the GLASSO model matches the actual observed variation. Tuning the regularization parameter to reduce the model error is a familiar task for a lot of modelers.
The olist geographical sales by cities in Sau Paulo for 2017 is a good candidate to explore the first approach. So I might try that.
References
Citation
@online{sambasivan2025,
author = {Sambasivan, Rajiv},
title = {Unsupervised {Learning} and {Graphs}},
date = {2025-08-06},
url = {https://rajivsam.github.io/r2ds-blog/posts/graph_learning},
langid = {en}
}