Introduction
In many real-world machine learning applications, data features such as user IDs, addresses, or product names are anonymized using hashing functions before being processed. While hashing preserves the "equality" relationship—ensuring that identical original strings result in identical hashes—the resulting strings carry no inherent semantic meaning. This paper introduces the concept of lexical invariance, the principle that a model's output should remain identical even if input features are swapped or hashed into arbitrary strings. By formalizing this property, the author provides a theoretical foundation for models that generalize significantly better when dealing with anonymized or structured data.
The Problem of Anonymized Data
Standard machine learning models often attempt to "memorize" specific feature labels. In an anonymized setting, this leads to poor generalization because the specific hash strings used in training may not appear in the test set, or different datasets might employ varying hashing schemes. The core challenge addressed here is: How can we design a model that is mathematically guaranteed to ignore specific "labels" and focus exclusively on the underlying patterns of equality and structure?
Theoretical Foundations
Lexical invariance is defined as a property where a function $f$ is invariant to any injective (one-to-one) transformation applied to the input space. The paper explores this through two primary lenses:
Multisets
The author proves that for a function to be "most expressive" and lexically invariant on a multiset, it must operate solely on the multiset of counts of unique elements. For example, the multiset {apple, orange, apple, banana} is treated as {2, 1, 1}. The specific names are irrelevant; only the distribution of their frequencies matters.
Graphs
For graphs, a lexically and permutation-invariant function must depend on the adjacency matrix $A$ and a difference matrix $D$. In matrix $D$, the entry $(i, j)$ is $1$ if node $i$ and node $j$ have the same feature, and $0$ otherwise. This matrix captures the relational structure of features without needing the features themselves.
Proposed Architectures
Based on these theories, two models are proposed:
- DeepCount: A version of the DeepSet architecture that takes the multiset of counts as input.
- DiffGIN: A modified Graph Isomorphism Network (GIN) that uses the adjacency matrix and the difference matrix $D$ to perform convolutions, effectively ignoring the literal content of node features.
Experimental Results
The researchers evaluated these models using standard graph classification datasets (MUTAG, PROTEINS, and PTC_MR). To simulate a lexically invariant environment, node features were modified by applying a SHA256 hash to the concatenation of the original feature and a random vector unique to each graph.
As shown in the performance curves, standard models (like GIN and DeepSet) often achieve very low training loss by memorizing specific hashes, but their test performance suffers as a result. In contrast, the lexically invariant models (DiffGIN and DeepCount) show much more stable training and significantly higher test accuracy.
| Dataset | Model | Train Acc | Test Acc |
|---|---|---|---|
| MUTAG | GIN (Standard) | 94.67% | 71.58% |
| DiffGIN (Proposed) | 89.11% | 83.16% | |
| PROTEINS | GIN (Standard) | 89.42% | 65.41% |
| DiffGIN (Proposed) | 76.15% | 71.89% |
Conclusion and Future Work
The experiments confirm that respecting lexical invariance is a powerful inductive bias for anonymized data. While the proposed models are bounded by the inherent expressive power of their base architectures (e.g., the 1-WL test for GIN), they provide a robust framework for handling meaningless identifiers. Future work will explore the computational complexity of constructing difference matrices for large-scale graphs and testing these principles on real-world datasets with naturally occurring anonymized IDs.
Summary updated