Clones in Graphs

Stephan Doerfel, Tom Hanika, Gerd StummearXiv 2018 · DOI · arXiv

TL;DR

This paper investigates "clone items"—entities that are structurally interchangeable—within graph data using the framework of Formal Concept Analysis (FCA). While the authors provide new theoretical tools to efficiently identify these clones, their empirical study reveals that strict non-trivial clones are vanishingly rare in real-world social networks, prompting a proposal for a more flexible generalization based on higher-order permutations.

What Problem Does This Paper Address?

Identifying structural similarities in large graphs, such as social networks, is a fundamental task in data mining. It helps in grouping similar entities, discovering hidden patterns, and reducing data redundancy (factorization).

Traditionally, researchers might look for graph automorphisms (symmetries), but real-world data is usually too "messy" and irregular for these rigid mathematical properties to appear frequently. The authors turn to Formal Concept Analysis (FCA), specifically the notion of clone items. In a bipartite graph (like users and the events they attend), two items are "clones" if they are completely interchangeable within the family of the data's closed subsets. The paper aims to answer a long-standing open question: Are these clones actually present and useful in natural, real-world graph datasets?

Methods

The authors bridge graph theory and FCA by treating graphs as formal contexts $(G, M, I)$, where $G$ represents objects (e.g., users), $M$ represents attributes (e.g., social groups), and $I$ is the relationship between them.

Key methodological contributions include:

  • Characterization Theorem: The authors prove Theorem 3.1, which allows for the identification of clones directly from the context table by checking only "irreducible" elements. This is a significant improvement over checking every possible subset, making the search computationally feasible for large datasets.
  • Trivial vs. Non-Trivial Clones: They distinguish between trivial clones (items with identical neighborhoods, which are easy to find but less interesting) and non-trivial clones (items that are interchangeable due to more complex structural regularities).
  • Higher-Order Generalization: Recognizing the scarcity of simple clones, they introduce the concept of clone permutations. Instead of just swapping two items, they look for larger permutations of attributes that preserve the underlying closure system of the data.

Datasets

The authors conducted an extensive empirical investigation using a variety of public datasets, mostly from the UCI Machine Learning Repository:

  • Social Networks: facebooklike (forum users/topics), southern (women/events), club (executives/clubs), movies (composers/producers), jazz (musicians), dolphins, hightech, and wiki (Wikipedia voters).
  • Non-Social Data: zoo (animal attributes) and cancer (breast cancer diagnoses).
  • Randomized Contexts: They also generated randomized versions of these datasets to serve as a baseline for comparison.

Key Insights and Ideas

  • The Rarity of Clones: The most striking finding is that non-trivial clones are almost non-existent in real-world social networks. The strict structural requirements for two entities to be clones are simply too demanding for natural data.
  • The "Wiki" Exception: The wiki dataset showed a high number of clones (234), but further investigation revealed this was due to a specific sub-structure (nominal scales) representing single, unique votes rather than a deep structural regularity of the social network itself.
  • Triviality Dominates: While non-trivial clones are rare, trivial clones (identical copies) are quite common in some datasets (e.g., the cancer dataset had 236). These are useful for data compression but don't offer deep insights into network topology.
  • Visualizing Clones: Figure 1 illustrates how clones appear in a small social network. For instance, "Swimming" and "Hiking" are clones because they are shared by the same set of people in a way that preserves the network's concept lattice.
Figure 1. Example of a social network graph exhibting various clones itmes. Edges connect a person with his or her activity. Equivalence classes for attribute clones are {Swimming,Hiking},{Biking, Rafting, Jogging}.

Key Results

The empirical results are summarized in the table below (referenced as Figure 2 in this summary).

Table 1. Properties of the considered (social) networks and data sets and results for clone experiment. With G-t we denote trivial clones whereas clones denote non-trivial clones.
  • Social Networks: Most networks like southern, club, movies, and aplnm had zero non-trivial clones.
  • Data Reduction: The lack of non-trivial clones suggests that the standard FCA notion of clones is insufficient for significant data reduction in social network analysis.
  • Randomization: Randomized versions of the datasets yielded similar results, suggesting that the absence of clones is a robust feature of these data structures, not just a result of their density.

Limitations and Future Work

The primary limitation identified is that the definition of a clone is too rigid for real-world applications. The authors conclude that while the theory is sound, the practical utility of strict clones in social network analysis is limited.

Future Directions: 1. Clone Permutations: The authors propose moving toward "higher-order clones"—permutations that preserve the closure system. This could capture more subtle symmetries that strict two-item swaps miss. 2. Group Theory: They pose an open question regarding whether the set of valid clone permutations always forms a group, which could unlock new algebraic tools for graph analysis. 3. Algorithmic Development: New, sophisticated algorithms are needed to efficiently detect these higher-order permutations in large-scale relational data.

Summary updated

Abstract

Finding structural similarities in graph data, like social networks, is a far-ranging task in data mining and knowledge discovery. A (conceptually) simple reduction would be to compute the automorphism group of a graph. However, this approach is ineffective in data mining since real world data does not exhibit enough structural regularity. Here we step in with a novel approach based on mappings that preserve the maximal cliques. For this we exploit the well known correspondence between bipartite graphs and the data structure formal context $(G,M,I)$ from Formal Concept Analysis. From there we utilize the notion of clone items. The investigation of these is still an open problem to which we add new insights with this work. Furthermore, we produce a substantial experimental investigation of real world data. We conclude with demonstrating the generalization of clone items to permutations.
BibTeX
@misc{doerfel2018clones,
  author = {Stephan Doerfel and Tom Hanika and Gerd Stumme},
  title = {{Clones in Graphs}},
  year = {2018},
  eprint = {1802.07849},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.07849},
}
Figure