🤖 machine learning

Aitchison Embeddings for Learning Compositional Graph Representations

This paper proposes a novel graph embedding framework grounded in Aitchison geometry that represents nodes as simplex-valued compositions to achieve intrinsically interpretable, competitive performance in tasks like node classification and link prediction while enabling principled analysis of latent archetype trade-offs through subcompositional coherence.

Original authors: Nikolaos Nakis, Chrysoula Kosma, Panagiotis Promponas, Michail Chatzianastasis, Giannis Nikolentzos

Published 2026-05-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nikolaos Nakis, Chrysoula Kosma, Panagiotis Promponas, Michail Chatzianastasis, Giannis Nikolentzos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand a huge, complex party. In this party, every guest (a "node") is interacting with others. Traditional computer programs try to describe these guests by giving them a single, fixed label, like "The Jokester" or "The Quiet One." Or, they might give them a list of numbers on a standard graph, where the distance between two people just means "how far apart they are" in a vague, mathematical sense.

The problem is that real people (and nodes in a network) are rarely just one thing. A guest might be 40% "Jokester," 30% "Listener," and 30% "Dancer." They are a mixture of roles.

This paper introduces a new way to map these guests called AICoG (Aitchison Compositional Graph embeddings). Here is how it works, using simple analogies:

1. The "Recipe" vs. The "Shopping List"

Most old methods treat a person's role like a shopping list: "I have 5 apples, 10 oranges, and 2 bananas." If you double the list (10 apples, 20 oranges, 4 bananas), the computer thinks it's a totally different person because the numbers are bigger.

But in reality, what matters is the recipe or the ratio. If you have 5 apples and 10 oranges, you have a 1:2 ratio. If you have 10 apples and 20 oranges, you still have that same 1:2 ratio. You are essentially the same "flavor" of person, just with more energy.

The authors say: "Let's stop looking at the absolute numbers and start looking at the recipe." They treat every node as a mixture (like a smoothie) of different "archetypes" (pure roles like "Leader," "Follower," "Connector").

2. The Special Map (Aitchison Geometry)

If you try to plot these "recipes" on a normal map (Euclidean space), things get messy. The math doesn't respect the fact that only the proportions matter.

The authors use a special kind of map called Aitchison Geometry. Think of this as a compass that only cares about direction, not distance.

Normal Map: If you move 1 mile North, you are different from moving 2 miles North.
Aitchison Map: It only cares if you are moving "North-East" relative to "South-West." It ignores how much "stuff" you have and focuses entirely on the balance between the ingredients.

3. The Magic Translator (ILR)

Computers are great at doing math on normal maps, but they struggle with this special "recipe" map. To fix this, the paper uses a translator called ILR (Isometric Log-Ratio).

Imagine you have a smoothie recipe (the mixture). The ILR translator takes that recipe and converts it into a standard set of instructions (coordinates) that a normal computer can understand perfectly.

The Cool Part: This translation is perfect. It doesn't lose any information. It keeps the "recipe" logic intact while letting the computer use its standard, fast math tools.

4. Why This is Better (The "Explainable" Part)

In old methods, if a computer says two people are similar, it's hard to explain why. It might just say, "They are 0.5 units apart on the X-axis." That doesn't tell you much about their actual roles.

With AICoG, the explanation is built-in:

The Trade-Off: The system explains similarity by saying, "These two people are similar because they both balance their 'Leader' and 'Follower' traits in the exact same way."
The "Cut-and-Paste" Test: One of the coolest features is Subcompositional Coherence. Imagine you have a smoothie with 5 flavors. If you decide to ignore the "Mint" flavor and just look at the other 4, the math stays consistent. You can "remove" a role and re-balance the rest, and the computer still understands the relationship.
- Analogy: If you take a recipe for a 5-ingredient cake and remove the vanilla, you can still perfectly understand the balance of the remaining 4 ingredients. In old methods, removing a dimension (a flavor) often breaks the math or makes the results meaningless.

5. Did it Work?

The authors tested this on real-world networks (like citation networks where papers link to other papers, or social networks).

Performance: It worked just as well as the best existing methods at predicting links (who will connect to whom) and classifying nodes (figuring out what group a node belongs to).
The Win: It didn't just work; it gave clear reasons for its answers. Instead of a black box saying "These are similar," it says, "These are similar because their mix of roles has the same balance."

Summary

The paper proposes a new way to understand networks by treating every node not as a single point or a fixed label, but as a mixture of roles. By using a special mathematical geometry designed for mixtures (Aitchison) and a perfect translator (ILR), they created a system that is:

Accurate: It predicts connections as well as the best current tools.
Honest: It respects the fact that roles are about ratios, not absolute numbers.
Explainable: It allows us to see how roles trade off against each other and lets us safely remove parts of the model to see what matters, without breaking the math.

1. Problem Statement

Graph representation learning is fundamental to tasks like link prediction and node classification. However, existing methods face two primary limitations regarding interpretability and structural modeling:

Lack of Intrinsic Interpretability: Standard Euclidean embeddings (e.g., Node2Vec, GNNs) encode similarity geometrically but lack semantic meaning in their latent dimensions. Distances and directions are often arbitrary and sensitive to coordinate choices, requiring post-hoc analysis for explanation.
Inadequate Modeling of Role Structures: Many real-world networks exhibit role-mixture structures where nodes are not distinct entities but rather mixtures of latent archetypal factors (e.g., a user acting as both a "researcher" and a "student").
- Traditional role-based models (e.g., Stochastic Block Models) assume discrete, axis-aligned roles.
- Mixed-membership models allow overlap but often rely on discrete, identifiable axes that fail when roles are continuous, overlapping, or defined by relative trade-offs rather than absolute magnitudes.
- Standard Euclidean spaces do not naturally handle compositional data (data where only the ratios between components matter, not the absolute scale), leading to issues with scale invariance and subcompositional coherence.

2. Methodology: AICoG

The authors propose Aitchison Compositional Graph embeddings (AICoG), a framework grounded in Aitchison geometry, the canonical geometry for compositional data.

Core Concepts

Compositional Representation: Each node $i$ is represented as a composition $z_i$ on the $(K-1)$ -dimensional simplex $\Delta^{K-1}$ , where $K$ is the number of latent archetypal factors. The vector $z_i = (z_{i1}, \dots, z_{iK})$ represents the relative contribution of each archetype to the node.
Aitchison Geometry: Instead of Euclidean distance, similarity is measured using the Aitchison distance, which depends exclusively on the log-ratios between components. This ensures scale invariance (absolute activity levels do not affect similarity) and subcompositional coherence (removing a subset of components preserves the relative geometry).
Isometric Log-Ratio (ILR) Transformation: To enable optimization using standard Euclidean tools (like gradient descent) while preserving Aitchison geometry, the method maps compositions from the simplex to an unconstrained Euclidean space $\mathbb{R}^{K-1}$ via the ILR transformation:
$x_i = \text{ILR}(z_i) = \log(z_i)^\top V$
where $V$ is an orthonormal basis for the contrast space. This transformation is an isometry, meaning the Euclidean distance between $x_i$ and $x_j$ exactly equals the Aitchison distance between $z_i$ and $z_j$ .

Model Architecture

Parameterization: Node compositions $z_i$ are parameterized via unconstrained logits $\tilde{z}_i$ passed through a softmax function to ensure they lie on the simplex.
Edge Likelihood: The probability of an edge $(i, j)$ is modeled as a Bernoulli distribution where the log-odds $\eta_{ij}$ are a monotone decreasing function of the ILR distance:
$\eta_{ij} = -\|x_i - x_j\|^2 + \gamma_i + \gamma_j$
Here, $\gamma$ represents node-specific biases (e.g., degree heterogeneity).
Optimization: The model is trained by maximizing the Bernoulli log-likelihood over observed edges.
Basis Flexibility: The framework supports both fixed bases (e.g., Helmert basis) and learnable bases (trained jointly with embeddings) to optimize interpretability.

3. Key Contributions

AICoG Framework: Introduction of a graph embedding framework that models nodes as compositions over latent archetypes and compares them using Aitchison geometry.
Expressive Equivalence: Proof that embedding compositions via ILR coordinates yields a latent distance model expressively equivalent to standard unconstrained Euclidean latent distance models. This means AICoG gains interpretability without sacrificing the capacity to represent complex edge probability matrices.
Geometric Roles: A new definition of "roles" as regions in a compositional latent space characterized by stable relative trade-offs, rather than axis-aligned dimensions. This supports continuous and overlapping role structures.
Subcompositional Coherence: Demonstration that the framework allows for principled component restriction. Removing and renormalizing a subset of archetypal factors preserves a well-defined geometry, enabling analysis of how specific archetype groups influence predictions without retraining.
Intrinsic Explainability: The method provides explanations by construction. Similarity is explained via log-ratio balances (trade-offs) between archetypes, which are invariant to orthogonal reparameterizations of the coordinate system.

4. Experimental Results

The authors evaluated AICoG on various datasets (Citation networks: Cora, Citeseer; Co-authorship: DBLP, AstroPh, etc.; Social: LastFM) against strong baselines including Node2Vec, Role2Vec, MMSBM, and SLIM-RAA.

Link Prediction: AICoG achieved competitive or superior AUC-ROC scores compared to strong baselines. Notably, replacing Aitchison geometry with Euclidean geometry on the simplex (SIMPLEX-EUCLIDEAN) caused a significant performance drop, proving that the compositional geometry itself is critical, not just the simplex constraint.
Node Classification: AICoG achieved favorable Micro-F1 scores, comparable to Euclidean methods, while providing geometrically interpretable representations.
Subcompositional Evaluation: When components were removed (dimensionality reduction via subset selection), AICoG maintained performance significantly better than other simplex-based baselines (like MMSBM or HM-LDM). This confirms the stability of the representation under principled component restriction.
Interpretability Analysis: Visualizations showed that different ILR bases (Helmert, Learned, Varimax) yielded consistent label separations, confirming that the structure is invariant to the coordinate system. The method successfully identified interpretable "trade-off trajectories" between archetypes.

5. Significance and Impact

Bridging the Gap: AICoG bridges the gap between high predictive performance (typical of Euclidean embeddings) and high interpretability (typical of probabilistic role models).
New Paradigm for Roles: It shifts the paradigm from discrete, axis-aligned roles to continuous, relative trade-offs, which better reflects the nature of many real-world networks (e.g., social, biological, economic).
Principled Explainability: Unlike post-hoc explanation methods (e.g., GNNExplainer), AICoG's explanations are intrinsic to the model's geometry. It allows researchers to ask "how does the trade-off between Archetype A and B affect the node's position?" rather than "what is the weight of dimension X?".
Future Directions: The paper suggests that Aitchison geometry can serve as a foundation for extending compositional inductive biases to other architectures, such as message-passing neural networks operating on compositional node states.

In summary, AICoG offers a mathematically rigorous and practically effective approach to learning graph representations where the latent space semantics are explicitly aligned with the relative, compositional nature of node roles.