Uniquely Defining Importance Measures Through Formal Axioms

37 concepts27 papers2 proposals

When designing algorithms to rank web pages, evaluate social network influence, or explain a deep learning model's prediction, engineers typically begin with an intuitive formula. For instance, to measure a node's importance in a network, one might count its direct connections, calculate its shortest paths, or simulate a random walk.

This "algorithm-first" approach is highly empirical: a formula is proposed, tested on datasets, and tweaked based on performance. However, it leaves a fundamental question unanswered: Why this specific formula? Without a rigorous theoretical foundation, it is difficult to know what implicit assumptions an algorithm makes, how it will behave on unusual edge cases, or whether an alternative formula might be fundamentally better.

To solve this, a growing body of research across network science, explainable AI (XAI), and social choice theory flips the paradigm. Instead of starting with an algorithm, researchers start with axioms—a minimal set of mathematical rules or desirable properties that any valid solution must satisfy. By proving that a specific algorithm is the only one capable of satisfying these rules simultaneously, they establish an axiomatic characterization that provides an indisputable mathematical justification for the algorithm's design.


The Intuition: Axioms as Geometric Constraints

To understand why axiomatic characterization works, imagine trying to identify a hidden geometric shape. If you are told the shape has four sides, the space of possibilities is vast—it could be a trapezoid, a rectangle, or a kite. If you add the constraint that all four sides must be equal, the space shrinks to rhombuses and squares. Finally, if you demand that all internal angles must be 90 degrees, the space collapses to a single, unique solution: a square.

Axioms function exactly like these geometric constraints, but instead of filtering shapes, they filter mathematical functions.

Consider the challenge of defining network centrality. In An Axiomatization of the Eigenvector and Katz Centralities, Tomasz Was et al. point out that classic metrics are usually defined by how they are calculated rather than their structural behavior. By introducing a "rulebook" of graph properties—such as how a node's score should change when an edge is added elsewhere in the network—the authors isolate the exact structural assumptions that separate Eigenvector centrality from Katz centrality.

When a set of axioms is proven to admit exactly one solution, it provides a uniqueness theorem. This shifts the justification of an algorithm from popularity or empirical luck to logical necessity.


Uniqueness in Network Science

Network science is filled with heuristic centrality measures, making it a primary beneficiary of axiomatic analysis. Researchers use axioms to map out the "mathematical DNA" of algorithms, revealing exactly when and why they work.

Edge Rankings and Random Walks

While node centrality is widely studied, ranking the importance of connections (edges) is equally vital. In PageRank for Edges: Axiomatic Characterization, Natalia Kucharczuk et al. established the first axiomatic foundation for Edge PageRank. By defining six fundamental structural rules, they proved that Edge PageRank is the unique mathematical solution for edge importance, giving practitioners a rigorous justification for using it over ad-hoc alternatives.

Axioms also help fix predictable failures in existing metrics. For example, PageRank can behave erratically on disconnected graphs or be manipulated by "link spam." To address this, Tomasz Was et al. introduced Random Walk Decay Centrality. By enforcing axioms like locality (a node's rank shouldn't change due to modifications in a completely disconnected part of the graph) and sink merging, they mathematically guaranteed a metric that is robust against strategic manipulation and stable across diverse graph topologies.

Bridging Graph Structure and Game Theory

Axiomatic frameworks also allow researchers to unify completely different fields. Oskar Skibski et al. demonstrated in Axiomatic Characterization of Game-Theoretic Network Centralities that any network centrality measure can actually be represented as a cooperative game. This allowed them to systematically categorize traditional graph metrics against game-theoretic indices (like the Shapley value).

Later, Oskar Skibski used this connection in Vitality Indices are Equivalent to Induced Game-Theoretic Centralities to prove that "vitality indices"—metrics that measure a node's importance by deleting it and seeing how much the network degrades—are mathematically equivalent to a specific class of game-theoretic centralities, providing a formal foundation for a tool that had been used intuitively for decades.


Uniqueness in Explainable AI (XAI)

As machine learning models grow more complex, explaining why a model made a specific prediction has become a critical challenge. Axiomatic characterization ensures that explanations are mathematically sound and not just visual artifacts that look plausible to humans.

Feature Attribution and Integrated Gradients

A dominant method for explaining neural networks is feature attribution, which assigns an importance score to each input feature (e.g., pixels in an image). Integrated Gradients (IG) is a highly popular attribution method, but its status as the "best" choice was historically debated.

To resolve this, Daniel Lundstrom et al. provided Four Axiomatic Characterizations of the Integrated Gradients Attribution Method. They proved that IG is the unique method that satisfies core logical requirements like completeness (the attributions must sum up to the difference between the model's output and a baseline output) and linearity. If an engineer wants an explanation method that respects these fundamental properties, they mathematically must use Integrated Gradients.

Data-Driven Explanations

Other times, practitioners want to explain a model's behavior using only the dataset itself, without accessing the model's internal weights. Jakub Śliwiński et al. tackled this in An Axiomatic Approach to Linear Explanations in Data Classification. By defining six "must-have" mathematical properties—including shift invariance, monotonicity, and continuity—the authors derived a unique family of Monotone Influence Measures (MIM). Because these measures are derived axiomatically from the data, the resulting explanations are guaranteed to be stable and consistent, as further detailed by the authors in Axiomatic Characterization of Data-Driven Influence Measures for Classification.

+-----------------------------------------------------------------------+
|                           DESIRED AXIOMS                              |
|  [Completeness]  [Monotonicity]  [Shift Invariance]  [Continuity]...  |
+-----------------------------------------------------------------------+
                                   |
                                   v  (Mathematical Proof of Uniqueness)
+-----------------------------------------------------------------------+
|                       UNIQUE ALGORITHMIC FAMILY                       |
|             e.g., Monotone Influence Measures (MIM)                   |
+-----------------------------------------------------------------------+

When explanations move beyond individual features to feature interactions (e.g., how the words "not" and "bad" work together), the mathematical complexity skyrockets. Neel Patel et al. addressed this in High Dimensional Model Explanations: an Axiomatic Approach by leveraging the Banzhaf Interaction Index. They proved that a specific set of axioms uniquely defines a valid interaction measure, ensuring that high-dimensional explanations remain geometrically optimal and stable under feature transformations.


Mapping the Boundaries: Impossibility and Classification

Axiomatic frameworks do more than just pinpoint unique algorithms; they also map out what is mathematically impossible and organize entire fields into clear hierarchies.

The Power of Impossibility Results

Sometimes, the axioms we want are mutually exclusive. In these cases, the axiomatic method yields an impossibility theorem, proving that no single algorithm can ever satisfy every requirement.

A classic example occurs in search engine result diversification, where systems try to return links that are both highly relevant and distinct from one another. In An Axiomatic Framework for Result Diversification, Sreenivas Gollapudi et al. formulated eight natural properties that an ideal diversification algorithm should have (such as scale invariance and stability). They mathematically proved that no single function can satisfy all eight simultaneously.

This result completely changed how engineers approached the problem: instead of searching for a perfect, non-existent algorithm, developers now use the framework to explicitly choose which axioms they are willing to sacrifice based on their specific application.

Axiomatic Taxonomies

When a domain features dozens of competing algorithms, axioms provide a rigorous way to categorize them. In multiwinner voting theory (such as selecting a committee based on voter preferences), the sheer variety of scoring rules can be overwhelming.

Piotr Faliszewski et al. resolved this confusion in Committee Scoring Rules: Axiomatic Classification and Hierarchy by using axioms to build a structural hierarchy of voting rules. This allowed them to prove exactly where classic selection philosophies intersect and which rules are unique solutions to specific fairness criteria, a foundational mapping that was expanded by Piotr Skowron 0001 et al. in Axiomatic characterization of committee scoring rules.

Similarly, in social choice applications like resolving voting paradoxes, Wesley H. Holliday et al. demonstrated in An axiomatic characterization of Split Cycle that the "Split Cycle" voting rule is the unique mechanism that satisfies a specific set of intuitive fairness and consistency axioms when handling majority cycles.


Conclusion

The axiomatic method fundamentally changes how we evaluate algorithms. Whether applied to information retrieval functions as advocated by ChengXiang Zhai, link prediction scores analyzed by Sara Cohen et al., or distance-based network metrics classified by Oskar Skibski et al. in Axioms for Distance-Based Centralities, this framework replaces empirical guesswork with mathematical certainty.

By defining the boundaries of what is possible, proving uniqueness, and exposing hidden trade-offs, axiomatic characterization ensures that the tools we rely on to rank, explain, and select are built on a bedrock of unassailable logic.

Key Foundational Work

An Axiomatic Framework for Result Diversification (2009) — contributed 1 concept elements to this direction.
Axiomatic Analysis and Optimization of Information Retrieval Models (2011) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_axiomatic_characterization_axiomatic_cen_f55c714f,
  title = {axiomatic characterization (axiomatic centrality characterization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/axiomatic-characterization-axiomatic-centrality-characterization/rdr_f55c714f96aa4dca8c94a873d69c004c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_axiomatic_characterization_axiomatic_cen_f55c714f_v1,
  title = {axiomatic characterization (axiomatic centrality characterization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/axiomatic-characterization-axiomatic-centrality-characterization/rdr_f55c714f96aa4dca8c94a873d69c004c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake