Latent Network Features and Overlapping Community Discovery via Boolean Intersection Representations

Son Hoang Dau, Olgica Milenković

TL;DR

This paper introduces Boolean intersection representations, a new combinatorial framework for modeling network connections using latent features. By requiring nodes to share features according to specific Boolean logic (like "Feature A AND Feature B"), the authors provide a more flexible way to discover overlapping communities that aren't restricted to simple cliques.

What Problem Does This Paper Address?

In network analysis, we often try to explain why two nodes are connected by looking for "latent features"—hidden attributes like shared hobbies or locations. Traditional combinatorial models, such as intersection graphs, assume two nodes are connected if they share at least one common feature.

While elegant, this "OR" logic is restrictive: it implies that every community must be a "clique" (where everyone is connected to everyone else). Real-world interactions are more nuanced. You might only connect with someone if you share a professional interest and live in the same city. The authors tackle the challenge of creating a deterministic, combinatorial model that can capture these complex, multi-conditional interactions and the overlapping communities they form.

Methods

The authors generalize the standard intersection model using Boolean functions. Their primary focus is the cointersection model, which uses "AND" logic:

  • The Rule: Two nodes $u$ and $v$ are connected if and only if they share at least one feature from set $A$ AND at least one feature from set $B$.
  • Theoretical Bounds: They use probabilistic methods (specifically the Lovász Local Lemma) to prove upper bounds on the "cointersection number"—the minimum number of features needed to represent a graph.
  • Algorithms:
    • Exact: They map the problem to a Boolean Satisfiability (SAT) instance, allowing off-the-shelf SAT solvers to find optimal feature assignments for small graphs.
  • Approximate: For larger, noisier real-world networks, they propose a Simulated Annealing algorithm that maximizes a "match score" between the model and the observed edges.

Datasets

The paper evaluates its approach on:

  1. Synthetic Graph Families: Star graphs, paths, cycles, and complete multipartite graphs to test theoretical tightness.
  2. Zachary’s Karate Club: A classic benchmark social network of 34 members. This is used to demonstrate how the model identifies "ground truth" community splits and finer sub-structures.

Key Insights and Ideas

  • Beyond the Clique: In standard models, a feature defines a clique. In the cointersection model, a feature defines a "community" that doesn't have to be a clique. An edge only appears at the intersection of two different types of communities. This is a much more realistic representation of social and biological clusters.
  • The Power of "AND": The cointersection number $\theta^c(G)$ is often much smaller than the standard intersection number. For graphs with a maximum degree $d$, the authors show the cointersection number grows as $O(\sqrt{n})$, whereas standard models often require many more features.
  • Geometric Connections: The authors uncover a fascinating link between optimal graph representations and finite geometry. Specifically, they show that finding the most efficient representation for certain multipartite graphs is equivalent to finding affine planes of a certain order.
  • DNF Generalization: While they focus on "AND," the framework extends to any Boolean function in Disjunctive Normal Form (DNF), allowing for incredibly complex connectivity rules (e.g., "Share A AND B, OR share C but NOT D").

Key Results

  • Theoretical Efficiency: The paper proves that for any graph $G$, the cointersection number $\theta^c(G)$ is at most $1 + \theta_1(G)$ (where $\theta_1$ is the standard intersection number).
  • Bounded Degree Graphs: For a graph with $n$ vertices and max degree $d$, they established that $\theta^c(G) \le 16d^{5/2}\sqrt{n}$.
  • Karate Club Success: Using $\alpha=\beta=2$ (only 4 total features), the simulated annealing algorithm perfectly recovered the famous faction split in Zachary’s Karate Club. It also identified overlapping sub-communities that provided deeper insight into the network's "fission" than simple binary clustering.

Limitations and Future Work

  • Computational Complexity: Determining the exact cointersection number is NP-complete, making the SAT-based approach unfeasible for very large networks.
  • Uniqueness: The authors note that many graphs do not have a unique optimal representation. This "non-uniqueness" can make it difficult to say which feature assignment is the "true" one without additional metadata.
  • Future Directions: The authors suggest exploring more complex Boolean functions (beyond simple AND/OR) and applying the model to biological datasets, such as protein-protein interaction or gene regulatory networks, where multi-conditional logic is biologically prevalent.

Summary updated

Abstract

We propose a new latent Boolean feature model for complex networks that captures different types of node interactions and network communities. The model is based on a new concept in graph theory, termed the Boolean intersection representation of a graph, which generalizes the notion of an intersection representation. We mostly focus on one form of Boolean intersection, termed <i>cointersection</i>, and describe how to use this representation to deduce node feature sets and their communities. We derive several general bounds on the minimum number of features used in cointersection representations and discuss graph families for which exact cointersection characterizations are possible. Our results also include algorithms for finding optimal and approximate cointersection representations of a graph.
BibTeX
@inproceedings{dau2017latent,
  author = {Son Hoang Dau and Olgica Milenković},
  title = {{Latent Network Features and Overlapping Community Discovery via Boolean Intersection Representations}},
  booktitle = {IEEE/ACM},
  year = {2017},
  doi = {10.1109/tnet.2017.2728638},
}

Loading related content...

Figure