On Lexical Invariance on Multisets and Graphs

Muhan ZhangarXiv 2024 · DOI · arXiv

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.

Training and test performance comparison between DiffGIN and standard GIN on the PROTEINS dataset.

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.

Training and test performance comparison between DeepCount and standard DeepSet on the PROTEINS dataset.
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

Abstract

In this draft, we study a novel problem, called lexical invariance, using the medium of multisets and graphs. Traditionally in the NLP domain, lexical invariance indicates that the semantic meaning of a sentence should remain unchanged regardless of the specific lexical or word-based representation of the input. For example, ``The movie was extremely entertaining'' would have the same meaning as ``The film was very enjoyable''. In this paper, we study a more challenging setting, where the output of a function is invariant to any injective transformation applied to the input lexical space. For example, multiset {1,2,3,2} is equivalent to multiset {a,b,c,b} if we specify an injective transformation that maps 1 to a, 2 to b and 3 to c. We study the sufficient and necessary conditions for a most expressive lexical invariant (and permutation invariant) function on multisets and graphs, and proves that for multisets, the function must have a form that only takes the multiset of counts of the unique elements in the original multiset as input. For example, a most expressive lexical invariant function on {a,b,c,b} must have a form that only operates on {1,1,2} (meaning that there are 1, 1, 2 unique elements corresponding to a,c,b). For graphs, we prove that a most expressive lexical invariant and permutation invariant function must have a form that only takes the adjacency matrix and a difference matrix as input, where the (i,j)th element of the difference matrix is 1 if node i and node j have the same feature and 0 otherwise. We perform synthetic experiments on TU datasets to verify our theorems.
BibTeX
@misc{zhang2024lexical,
  author = {Muhan Zhang},
  title = {{On Lexical Invariance on Multisets and Graphs}},
  year = {2024},
  eprint = {2409.14179},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2409.14179},
}
Figure