Tangle-Based Heuristics for Subgraph Matching in Large Networks

Co-Supervised by: Kalvin Dobler

If you are interested in this topic or have further questions, do not hesitate to contact kalvin.dobler@unibe.ch.

Background / Context

Traditional subgraph isomorphism methods (e.g., VF2, Ullmann’s) suffer in large networks due to global combinatorial explosion. Many real-world networks (biological, social, infrastructure) exhibit modularity and local structure, which can be exploited using tangle theory.

Tangle theory, from graph minor theory (developed by Robertson and Seymour), offers a way to capture “highly connected regions” of a graph without explicitly identifying the structure — focusing instead on consistent orientations of low-order separations. This provides a way to reason about complex graph connectivity abstractly.

The idea is to implement a framework for subgraph matching in large and complex networks by leveraging tangle-based decomposition. The core idea is to restrict matching operations to highly connected regions identified via tangles in order to improve both efficiency and interpretability.

Research Question(s) / Goals

  • Goal 1: Literature Review (graph minor theory, tangle theory, algorithmic frameworks)
  • Goal 2: Implement or adapt existing algorithms (e.g., based on branch decompositions or separators) to compute tangle decompositions of graphs.
  • Goal 3: Implement or adapt existing for subgraph isomorphisms tools
  • Goal 4: Integrate the tangle decomposition to restrict matching attempts to meaningful, highly connected regions.
  • Goal 5: Apply it to large real-world datasets

Approach / Methods

Tangle-based decomposition.

  • Implement or adapt tree or branch decomposition algorithms to approximate tangle structures
  • Identify high-connectivity regions (“proto-tangles”) by analyzing separator sizes, density, and internal cut resistance.

Tangle clustering extraction

  • Extract tangle clusters from the decomposition: subgraphs that correspond to dense, hard-to-separate regions.
  • Allow overlapping clusters to preserve border nodes that participate in multiple regions
  • Measure intra-cluster and inter-cluster connectivity to guide matching prioritization

Expected Contributions / Outcomes

  • Novel framework.
  • Algorithmic innovation.
  • Theoretical understanding and contribution.

Required Skills / Prerequisites

  • Good programming skills.
  • Interest in theoretical and applied work.

Further Reading / Starting Literature

  • Diestel R. Graph Theory. Springer.
  • Diestel R. Tangles: A Structural Approach to Artificial Intelligence in the Empirical Sciences. Cambridge University Press; 2024
  • Klepper et al. Clustering with Tangles: Algorithmic Framework and Theoretical Guarantees