The goal in this challenge is to find large quasi-cliques in the undirected graph representing the FlyWire connectome. A subgraph with k vertices is a δ-quasi-clique if it contains more than δ(k choose 2) edges - or in other words, if more than δ fraction of all possible edges exist between its vertices. The first participant who finds the largest 0.25-quasi-clique (δ = 0.25) will win.

Input and objective

You are given a simple graph (unweighted undirected) G = (V, E), where:

• nodes V represent individual neurons
• edges E represent synaptic connections between connected neurons

You need to find a subset of k vertices from V that contains strictly more than (k choose 2) / 4 edges. And your goal is to maximize k.

Relation to Motif Search

This problem is loosely related to motif search, a fundamental challenge in connectome network analysis. Existing motif search tools are optimized for finding small motifs, often struggling to scale efficiently to larger patterns. We hope that by optimizing algorithms for large dense subgraph detection, the techniques developed in this challenge may contribute to more scalable and practical motif search tools in the future.

Prerequisites

This is a data analysis / optimization challenge, and it is open to everyone. Participants do not have to know anything about the Drosophila brain or connectomics. Data processing and some algorithmic skills should suffice to compete.

Data

• Simple graph underlying the FlyWire connectome (download here)
• Benchmark solution (download here)

Here is a sample code in Python for verifying submissions:

# load data
edges = {(r[0], r[1]) for r in read_csv("edges.csv.gz")}
nodes = sorted([r[0] for r in read_csv("max_clique_submission_benchmark_162.csv.gz")])
# verify no duplicate nodes
assert len(nodes) == len(set(nodes)), "Duplicate nodes detected"
# verify that edge density is above 0.25
edge_count, pair_count = 0, 0
for i1, n1 in enumerate(nodes):
  for n2 in nodes[i + 1:]:
    pair_count += 1
    if (n1, n2) in edges:
      edge_count += 1
assert edge_count / pair_count > 0.25, "Insufficient density"


How to submit

• Email your solution to arie@princeton.edu, including:
  • Size k of the subgraph found
  • CSV / text file with k rows / lines, each containing a neuron id corresponding to one vertex in the found quasi-clique (like in the benchmark solution)
  • Short explanation of how the result was achieved (method / main idea)
  • Kindly introduce yourself and share how you came to learn about the challenge
  • Mention if it is ok to have your name displayed on the leaderboard
• Submissions will be verified and leaderboard updated periodically, until Jul 31, 2025 end of day (ET).
• There is no limit on number of submissions per participant / team. Only the best one will be shown.
• Winners of the challenge will receive a special plaque from the FlyWire team at Princeton University, and will be invited to give a short presentation (optional).

Notes

• The edge list contains sorted pairs of nodes only. But since the underlying graph is undirected, if for example (x,y) is the edge list, then (y,x) is also an edge even though it is omitted from the list for compactness.
• To not disadvantage early submissions, scores and solutions will be revealed after the challenge is complete.
• Only the best score is recorded on the leaderboard for each participating team.
• History of revisions
  - Original challenge (posted on March 7th) was about finding max cliques (complete subgraphs). As it turned out, it was not too difficult for the given connectome graph. The following participants all found maximal cliques of size 40 shortly after the challenge was posted: Wayne B Hayes, Justin Ellis-Joyce, Thiago Munhoz da Nóbrega, David A. Bader, Harinarayan Asoori Sriram, Srijith Chinthalapudi, Zhihui Du. In particular, Justin and Thiago enumerated all 252 maximal cliques of size 40.
  - On March 9 the challenge was modified from finding cliques to finding quasi-cliques with δ=0.5 (subgraphs where at least half of the pairs of vertices are connected). Within a few weeks progress on this version halted, and the following teams all found 0.5 quasi-cliques of size 175: Pedro José Correia Duarte, Christian Larsen, Rick Willemsen; David A. Bader, Harinarayan Asoori Sriram, Srijith Chinthalapudi, Zhihui Du; Thiago Munhoz da Nóbrega; Leo Versteegen; Xin Zheng, Zuoyu Zhang, Tatsuo Okubo. Furthermore, David A. Bader and team enumerated 568 quasi-cliques of size 175, containing all other submissions. After more than a month without progress we assume there are no larger 0.5 quasi-cliques, but have no formal proof obtained from any solver yet.
  - On Apr 30 the challenge was modified from finding 0.5 quasi-cliques to finding 0.25 quasi cliques.