Restricted inference on graphs using learned low-dimensional manifolds

Learning Submanifolds for Subsequent Inference on Random Dot Product Graphs, Part 1: Theory

Machine Learning

Summary

The paper looks at how to make decisions based on data represented as graphs, where the underlying data points lie on some low-dimensional shape (manifold) that we don't know. The authors develop rules that learn this shape from extra related data and use it to make better decisions on the graphs. They use a method called Isomap to transform the graph data into a simpler, low-dimensional space while preserving distances. As they get more extra data, their decision methods get closer to an ideal rule that knows the true low-dimensional structure perfectly. The paper focuses on theory; examples and experiments are planned for a following study.

What this means in practice

  • For machine learning engineers: Design algorithms that incorporate learned low-dimensional structures from graph data for improved decision-making accuracy.
  • For network analysts: Analyze complex networks by embedding nodes in a low-dimensional space that reflects intrinsic data structures for enhanced pattern recognition.

A theory result. No direct application yet.

Authors

Michael W. Trosset, Carey E. Priebe

Abstract

We propose a framework for restricted inference on random dot product graphs whose latent positions lie on an unknown low-dimensional support manifold. For general decision problems, we propose semisupervised decision rules that use auxiliary data to learn the support manifold. Specifically, our rules use the Isomap manifold learning procedure to construct a low-dimensional Euclidean representation of the observed graph, in which space an isometrically invariant function maps configurations of points to actions. We study the behavior of the proposed rules as the quantity of auxiliary data sampled from the unknown support manifold increases. We show that, as the auxiliary sample size increases, the risk of the semisupervised rule converges to the risk of an oracle rule that relies on the maximal amount of low-dimensional Euclidean structure that can be extracted from the support manifold. Examples, applications, and simulation studies are deferred to a sequel.
View PDFOpen arXiv