Triad
Accurate overlapping community detection as a tri-dimensional quadratic optimization — the predecessor that motivated Highway.
The problem
Overlapping community detection lets a node belong to several communities at once. Most existing methods are heuristics that lean on only part of the available structure — nodes, or edges, or community-level signal — rather than all three together. That partial view produces unstable assignments and structural degeneracies.
Two failure modes recur: mass collapse, where a single community swallows almost every node, and uniform fuzziness, where every node ends up with a similar, blurred membership. Both can post high numeric scores while recovering no coherent overlapping structure — so a good objective value is not enough.
Core idea — three structural dimensions, one optimization
Triad casts OCD as a single quadratic constrained program (QCP) over continuous memberships, using all three structural signals and penalizing degeneracy in each — no ad-hoc heuristics.
Node memberships
Continuous membership variables let a node belong to several communities, while node-dominance effects that would let one node or community take over are penalized.
Edge consistency
Connected nodes should share memberships; abrupt, discrete affiliation transitions across an edge are penalized, keeping assignments coherent along the graph.
Community regularization
Community-level terms reward internal mass (shared membership across edges) while penalizing empty or collapsed communities — directly countering mass collapse.
All three enter one QCP with only linear and quadratic terms, so standard solvers optimize it directly. Triad also runs built-in degeneration diagnostics that flag solutions which are numerically feasible but structurally degenerate — for example uniform fuzziness — an internal consistency check that objectives like overlapping modularity cannot see.
Key results
Partial-signal methods (e.g. k-clique, SLPA) swing widely between benchmarks, and demon / conga degrade sharply as noise grows — Triad holds a high Fuzzy Rand Index and stable overlapping modularity across both generators.
Why it matters — and the road to Highway
Triad shows that treating OCD as a single, multi-dimensional optimization — rather than a patchwork of heuristics — yields structurally reliable overlapping communities. Its limitation is intrinsic: a quadratic constrained program does not scale to large networks. That bottleneck is exactly what motivated Highway, which keeps Triad's structural insight but infers communities on a sparse backbone — trading exact optimization for scale to 1.13M nodes.
Triad will be made open-source to support future research.