Kemeny's constant is a single number that summarizes how long it takes a random walker to travel between nodes in a network, averaging over all starting and ending points. A lower value means the network is easier to navigate. Researchers have previously noticed a counterintuitive phenomenon called Braess' paradox: adding a new connection to a network can actually make navigation worse on average, increasing Kemeny's constant. A connection that causes this problem is called a Braess edge.
This paper extends that idea from single edges to cliques. A clique is a set of nodes that are all connected to each other. The authors define a "Braess clique" as a fully connected group of nodes that, when inserted into an existing network by linking all members of some independent set of nodes to one another, causes Kemeny's constant to rise. An independent set is simply a collection of nodes that currently share no connections, so inserting a clique among them adds many new edges at once. A Braess edge is then just the smallest possible case of this, involving only two nodes.
The authors construct concrete examples of networks where adding a clique of three or more nodes increases Kemeny's constant, and they show that this behavior is actually very common: almost every connected planar network (the kind you could draw on paper without edges crossing) contains such a problematic clique for any chosen size. The paper also examines how Braess edges and Braess cliques relate to each other, exploring whether the presence of one implies or rules out the other. The broader takeaway is that the paradox of adding connections making a network worse is not a rare curiosity but a widespread structural feature of networks.