Author name cluster

Alessio Conte

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

2 author rows

AAAI Conference 2023 Conference Paper

Generalizing Downsampling from Regular Data to Graphs

Davide Bacciu
Alessio Conte
Francesco Landolfi

Downsampling produces coarsened, multi-resolution representations of data and it is used, for example, to produce lossy compression and visualization of large images, reduce computational costs, and boost deep neural representation learning. Unfortunately, due to their lack of a regular structure, there is still no consensus on how downsampling should apply to graphs and linked data. Indeed reductions in graph data are still needed for the goals described above, but reduction mechanisms do not have the same focus on preserving topological structures and properties, while allowing for resolution-tuning, as is the case in regular data downsampling. In this paper, we take a step in this direction, introducing a unifying interpretation of downsampling in regular and graph data. In particular, we define a graph coarsening mechanism which is a graph-structured counterpart of controllable equispaced coarsening mechanisms in regular data. We prove theoretical guarantees for distortion bounds on path lengths, as well as the ability to preserve key topological properties in the coarsened graphs. We leverage these concepts to define a graph pooling mechanism that we empirically assess in graph classification tasks, providing a greedy algorithm that allows efficient parallel implementation on GPUs, and showing that it compares favorably against pooling methods in literature.

PDF Details DOI

TCS Journal 2022 Journal Article

On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms

Alessio Conte
Etsuji Tomita

We revisit the maximal clique enumeration algorithm cliques by Tomita et al. that appeared in Theoretical Computer Science in 2006. It is known to work in O ( 3 n / 3 ) -time in the worst-case for an n-vertex graph. This is worst-case optimal with respect to the input size, but there is little knowledge about its performance with respect to the output. In this paper, we extend the time-complexity analysis with respect to the maximum size and the number of maximal cliques, and to its delay, solving issues that were left as open problems since the original paper. In particular, we prove that cliques has Ω ( 3 n / 6 ) delay and that, even if we allow to change the pivoting strategy, a variant having polynomial delay cannot be designed unless P = N P. These same results apply to the related Bron-Kerbosch algorithm. On the positive side, we show that the complexity of cliques and Bron-Kerbosch is amortized polynomial on graphs with logarithmic clique number. As these algorithms are widely used and regarded as fast “in practice”, we are interested in observing their practical behavior: we run an evaluation of cliques and three Bron-Kerbosch variants on over 130 real-world and synthetic graphs, observing how the clique number almost always satisfies our logarithmic constraint, and that their performance seems far from its theoretical worst-case behavior in terms of both total time and delay. 1

Details DOI

TCS Journal 2020 Journal Article

Efficient enumeration of maximal k-degenerate induced subgraphs of a chordal graph

Alessio Conte
Mamadou Moustapha Kanté
Yota Otachi
Takeaki Uno
Kunihiro Wasa

In this paper we consider the problem of listing the maximal k-degenerate induced subgraphs of a chordal graph, and propose an output-sensitive algorithm using delay O ( m ⋅ ω ( G ) ) for any n-vertex chordal graph with m edges, where ω ( G ) ≤ n is the maximum size of a clique in G. Degeneracy is a well known sparsity measure, and k-degenerate subgraphs are a notion of sparse subgraphs, which generalizes other problems such as independent sets (0-degenerate subgraphs) and forests (1-degenerate subgraphs). Many efficient enumeration algorithms are designed by solving the so-called Extension problem, which asks whether there exists a maximal solution containing a given set of nodes, but no node from a forbidden set. We show that solving this problem is np-complete for maximal k-degenerate induced subgraphs, motivating the need for additional techniques.

Details DOI

MFCS Conference 2020 Conference Paper

Enumeration of s-d Separators in DAGs with Application to Reliability Analysis in Temporal Graphs

Alessio Conte
Pierluigi Crescenzi
Andrea Marino 0001
Giulia Punzi

Temporal graphs are graphs in which arcs have temporal labels, specifying at which time they can be traversed. Motivated by recent results concerning the reliability analysis of a temporal graph through the enumeration of minimal cutsets in the corresponding line graph, in this paper we attack the problem of enumerating minimal s-d separators in s-d directed acyclic graphs (in short, s-d DAGs), also known as 2-terminal DAGs or s-t digraphs. Our main result is an algorithm for enumerating all the minimal s-d separators in a DAG with O(nm) delay, where n and m are respectively the number of nodes and arcs, and the delay is the time between the output of two consecutive solutions. To this aim, we give a characterization of the minimal s-d separators in a DAG through vertex cuts of an expanded version of the DAG itself. As a consequence of our main result, we provide an algorithm for enumerating all the minimal s-d cutsets in a temporal graph with delay O(m³), where m is the number of temporal arcs.

Details

I&C Journal 2020 Journal Article

Large-scale clique cover of real-world networks

Alessio Conte
Roberto Grossi
Andrea Marino

The edge clique cover (ecc ) problem deals with discovering a set of (possibly overlapping) cliques in a given graph that covers each of the graph's edges. This problem finds applications ranging from social networks to compiler optimization and stringology. We consider several variants of the ecc problem, using classical quality measures (like the number of cliques) and new ones. We describe efficient heuristic algorithms, the fastest one taking O ( m d G ) time for a graph with m edges, degeneracy d G (also known as k-core number). For large real-world networks with millions of nodes, like social networks, an algorithm should have (almost) linear running time to be practical: Our algorithm for finding eccs of large networks has linear-time performance in practice because d G is small, as our experiments show, on real-world networks with thousands to several million nodes.

Details DOI

MFCS Conference 2019 Conference Paper

Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs

Alessio Conte
Roberto Grossi
Mamadou Moustapha Kanté
Andrea Marino 0001
Takeaki Uno
Kunihiro Wasa

This paper investigates induced Steiner subgraphs as a variant of the classical Steiner trees, so as to compactly represent the (exponentially many) Steiner trees sharing the same underlying induced subgraph. We prove that the enumeration of all (inclusion-minimal) induced Steiner subgraphs is harder than the well-known Hypergraph Transversal enumeration problem if the number of terminals is not fixed. When the number of terminals is fixed, we propose a polynomial delay algorithm for listing all induced Steiner subgraphs of minimum size. We also propose a polynomial delay algorithm for listing the set of minimal induced Steiner subgraphs when the number of terminals is 3.

Details

STOC Conference 2019 Conference Paper

New polynomial delay bounds for maximal subgraph enumeration by proximity search

Alessio Conte
Takeaki Uno

In this paper we propose polynomial delay algorithms for several maximal subgraph listing problems, by means of a seemingly novel technique which we call proximity search. Our result involves modeling the space of solutions as an implicit directed graph called “solution graph”, a method common to other enumeration paradigms such as reverse search. Such methods, however, can become inefficient due to this graph having vertices with high (potentially exponential) degree. The novelty of our algorithm consists in providing a technique for generating better solution graphs, reducing the out-degree of its vertices with respect to existing approaches, and proving that it remains strongly connected. Applying this technique, we obtain polynomial delay listing algorithms for several problems for which output-sensitive results were, to the best of our knowledge, not known. These include Maximal Bipartite Subgraphs, Maximal k -Degenerate Subgraphs (for bounded k ), Maximal Induced Chordal Subgraphs, and Maximal Induced Trees. We present these algorithms, and give insight on how this general technique can be applied to other problems.

Details

MFCS Conference 2018 Conference Paper

Listing Subgraphs by Cartesian Decomposition

Alessio Conte
Roberto Grossi
Andrea Marino 0001
Romeo Rizzi
Luca Versari

We investigate a decomposition technique for listing problems in graphs and set systems. It is based on the Cartesian product of some iterators, which list the solutions of simpler problems. Our ideas applies to several problems, and we illustrate one of them in depth, namely, listing all minimum spanning trees of a weighted graph G. Here iterators over the spanning trees for unweighted graphs can be obtained by a suitable modification of the listing algorithm by [Shioura et al. , SICOMP 1997], and the decomposition of G is obtained by suitably partitioning its edges according to their weights. By combining these iterators in a Cartesian product scheme that employs Gray coding, we give the first algorithm which lists all minimum spanning trees of G in constant delay, where the delay is the time elapsed between any two consecutive outputs. Our solution requires polynomial preprocessing time and uses polynomial space.

Details