Topology and Geometry Through Graph ML

Graphs Are All Around Us

When first learning about graphs, one usually encounters something like the following:

A collection of nodes or vertices represented as dark green circles connected by edges or links which indicate some pairwise relationship between two nodes.

Graphs are incredibly simple yet flexible data structures. There is no notion of left, right, up, or down. Nodes and edges can be added or omitted as we please. We can also move, bend, and reorder the nodes without changing the underlying relational structure of the graph. That is, without changing the fundamental nature of the graph itself. For example, below I’ve moved some of the nodes of the graph around and switched node 3 and node 5.

Despite these modifications, the graph describes the same basic relational structure. We refer to this underlying structure as the graph’s connectivity or the topology of the graph. The graph’s topology is agnostic of where we position these nodes in space, or what we name individual nodes.

This also means graphs exist outside of Euclidean space where we have explicit notions of distance and direction. I have no way of telling if node 3 is closer to node 4 or node 5 even though they appear farther apart in the two examples above. Graphs like these, in their most basic form, do not model Euclid’s geometry. Perhaps there is a shorter road after all?

Adding Geometry to Graphs

For machines to learn on data, be it graph-structured or not, we must represent it in a way computers can digest. That is to say, we must encode the data into some n-dimensional Euclidean vector space where individual data points become vectors within that space.

Consider GPS telemetry data used to monitor the movement of a newly released California Condor.⁴

The data used to make that visualization might look something like this:

We want to represent each row in the table as a vector.⁵ However, the Latitude and Longitude coordinate system is part of a fundamentally different type of geometry: a non-Euclidean one native to the 3-dimensional ellipsoidal shape of the Earth. We can convert this non-Euclidean space to a 2-d Euclidean space in the traditional Cartesian coordinate system by using the Universal Transverse Mercator (UTM) map projection.⁶ The UTM projection gives us an \((easting, \ northing)\) point for each point in \((latitude, \ longitude)\) space.

After we have performed the mapping all of our data can be represented in a 5-d Euclidean vector space where each vector fully describes a row in our data.

\[ \begin{bmatrix} Time \\ Condor \\ Easting \\ Northing \\ Altitude \end{bmatrix} \in \mathbb{R}^5 \]

This process introduces a consistent geometry to our data. That is, we can now understand our data through its shape, size, distance, and relative position. Below, I visualize the Condor GPS Telemetry vector space, using some liberties to represent the Time and Condor dimensions as hue and point-shape, respectively.

Embedding our data into a vector space allows us to leverage Euclid’s Elements and everything built upon them. We can compare how similar two vectors are by using methods like cosine similarity or feed these vectors into machine learning models as features to learn upon.

When our data has an inherent graph structure, the process is no different. We simply associate feature vectors with their given nodes or edges. Let’s take our first graph and re-imagine it as a representation of a small social network where nodes are user-profiles and edges indicate friendships between them.

For each node we have added a feature vector which holds some information about those user-profiles such as how long they have been on the platform \(x_1\), when they last logged on \(x_2\), their geographic region \(x_3\), and so on.

Assigning feature vectors to the graph overlays a Euclidean geometry upon it. We can no longer move, bend, or switch nodes on the graph because each node now exists at a certain point in our feature-vector space. Moving the node would change its underlying meaning.

Making Use of Topology and Geometry

Graphs allow us to represent features alongside additional relationships and structure. Introducing a flexible topological structure in which Euclidean geometry can be embedded can help our models understand and generalize better.

Relational data is the most abundant type of data across industry, yet it is not often thought about in terms of its inherent graph structure.⁷ A simple database representation of our small social network below depicts the relational structure which can be explicitly embedded as the edges of a graph.

In this sense, all relational databases can be seen as graphs which allow for complex topologies through primary and foreign key relations like the one-to-many relationship we see above. The intuition behind adding this friendship-structure is that we can learn more about a user by also looking at who they are friends with and the attributes of those friends.

An extremely common modeling task on relational data of social networks is predicting user churn. We want to know which users are likely to drop off the platform and perhaps intervene. A tabular machine learning model might ingest the rows of the user table as features and learn to recognize patterns about certain types of users and their behavior which makes them likely to attrite.

This may work relatively well, however, it ignores the underlying topology of friendship such a user finds themselves within. Consequently, we lose the ability to answer questions like: if a user’s friends churn, are they more likely to churn themselves? The graph-based approach allows us to answer this question because we can capture, for each row in the data, additional information about relationships between rows.⁸ Cvitkovic (2020) shows incorporating the connectivity of relational data through graphs is especially useful when many tables and foreign key relationships belong to a relational database.⁹

Graphs unlock this capability by incorporating topological structure as an inductive bias alongside features rather than as an additional feature. Acknowledging the inherent topology of our data helps models better understand how to learn rather than expanding what to learn.

To Blog Is To Forget

Looking back over the past year, I’d be remiss to not speak on the effects of entering into the fold through my own journey developing large-scale document AI systems. Document AI is a field which uses AI to comprehend documents such as scanned invoices, webpages, legal filings, and in my experience: receipts.¹³ It is broad and touches a wide range of AI specialties: CV, NLP, and even more recently Graph ML.¹⁴

Once brought into the fold of Graph ML, it can be hard to stop seeing graphs everywhere you look and especially hard to not send your CV and NLP colleagues blogs about how CNNs and transformers are just special cases of graph neural networks. Yes, pretty much everything is a graph or can be molded into one but doing so isn’t always useful. Ignoring topology can help to not distract models (and the people who build them) when it lacks useful information. It also allows for highly optimized and parallelizable architectures rather than ones which are more flexible but must unfurl computation graphs dynamically.

Through sheer luck and an amazing group of colleagues and mentors, my past year led me to explore Graph ML and the Geometric Deep Learning paradigm to search for and uncover a hidden semantic topology within the documents we process. While I can’t say what this means for the future, I can say I have grown more than I could have imagined and I’m excited to see what 2023 holds.

As for Ptolemy, I’ve found another answer. The shortest road between two points isn’t always a straight line. . .