  When searching for interesting structures in graphs, it is often important to
take into account not only the graph connectivity, but also the metadata
available, such as node and edge labels, or temporal information. In this paper
we are interested in settings where such metadata is used to define a
similarity between edges. We consider the problem of finding subgraphs that are
dense and whose edges are similar to each other with respect to a given
similarity function. Depending on the application, this function can be, for
example, the Jaccard similarity between the edge label sets, or the temporal
correlation of the edge occurrences in a temporal graph. We formulate a
Lagrangian relaxation-based optimization problem to search for dense subgraphs
with high pairwise edge similarity. We design a novel algorithm to solve the
problem through parametric MinCut, and provide an efficient search scheme to
iterate through the values of the Lagrangian multipliers. Our study is
complemented by an evaluation on real-world datasets, which demonstrates the
usefulness and efficiency of the proposed approach.
