Subgraph matching seeks all the occurrences of a query graph inside another graph. As it reduces to subgraph isomorphism, it is NP-hard. Current methods reduce the computation by filtering the candidates on which they run subgraph isomorphism. Nevertheless, when the query is large, the number of candidates grows rapidly, rendering current methods largely ineffective in pruning and incapable to answer even within one hour. A primary reason for this ineffectiveness is their inability to effectively consider the query graph structure in the computation. In this paper, we propose Pilos,a novel matching algorithm that substantially improves the filtering phase of a typical matching algorithm and computes up to 60% fewer candidates for verification. Pilosuses ($i$) an offline light-weight index-based phase, which leverages the top graph Laplacian eigenvalues of query and data node neighborhoods to reduce candidates via neighborhood filtering and (ii) an online phase, which further prunes candidates stored in an auxiliary data structure; both phases apply the interlacing theorem on graph Laplacian spectra. Our thorough experimental study shows that, on average, Pilosresolves queries in 19% less time and leaves 23% fewer unresolved queries after a lapse of 10 minutes than the best previous work.

Several applications call to align the nodes of two graphs in a way that minimizes a distance function.In practicality, the graphs to be aligned often have unequal orders (i.e., numbers of vertices) and no auxiliary labels or attributes; we refer to this problem as partial unlabeled graph alignment.Some proposals to address this problem add dummy nodes to the smaller graph to even the orders and align the ensuing graphs or employ embeddings such as GNNs, which yield ad hoc node representations.Unfortunately, as we show, an optimal solution to equal-order graph alignment using dummy nodes does not imply an optimal solution to partial graph alignment.To address this deficiency, in this paper, we propose Alpine, a Partial Unlabeled Graph Alignment algorithm that solely peruses the graphs' adjacency matrices, guided by a tailored objective function inspired by best-of-breed shape matching techniques and a state-ofthe-art optimization method.Extensive experiments demonstrate that Alpine consistently surpasses state-of-the-art graph alignment methods in solution quality across all benchmark datasets.

The graph alignment problem calls for finding a matching between the nodes of one graph and those of another graph, in a way that they correspond to each other by some fitness measure. Over the last years, several graph alignment algorithms have been proposed and evaluated on diverse datasets and quality measures. Typically, a newly proposed algorithm is compared to previously proposed ones on some specific datasets, types of noise, and quality measures where the new proposal achieves superiority over the previous ones. However, no systematic comparison of the proposed algorithms has been attempted on the same benchmarks. This paper fills this gap by conducting an extensive, thorough, and commensurable evaluation of state-ofthe- art graph alignment algorithms. Our results highlight the value of overlooked solutions and an unprecedented effect of graph density on performance, hence call for further work.

What is the best way to match the nodes of two graphs? This graph alignment problem generalizes graph isomorphism and arises in applications from social network analysis to bioinformatics. Some solutions assume that auxiliary information on known matches or node or edge attributes is available, or utilize arbitrary graph features. Such methods fare poorly in the pure form of the problem, in which only graph structures are given. Other proposals translate the problem to one of aligning node embeddings, yet, by doing so, provide only a single-scale view of the graph. In this article, we transfer the shape-analysis concept of functional maps from the continuous to the discrete case, and treat the graph alignment problem as a special case of the problem of finding a mapping between functions on graphs. We present GRASP, a method that first establishes a correspondence between functions derived from Laplacian matrix eigenvectors, which capture multiscale structural characteristics, and then exploits this correspondence to align nodes. We enhance the basic form of GRASP by altering two of its components, namely the embedding method and the assignment procedure it employs, leveraging its modular, hence adaptable design. Our experimental study, featuring noise levels higher than anything used in previous studies, shows that the enhanced form of GRASP outperforms scalable state-of-the-art methods for graph alignment across noise levels and graph types, and performs competitively with respect to the best non-scalable ones. We include in our study another modular graph alignment algorithm, CONE, which is also adaptable thanks to its modular nature, and show it can manage graphs with skewed power-law degree distributions.

Can we solve finite-horizon Markov decision processes (FHMDPs) while raising low memory requirements? Such models find application in many cases where a decision-making agent needs to act in a probabilistic environment, from resource management to medicine to service provisioning. However, computing optimal policies such an agent should follow by dynamic programming value iteration raises either prohibitive space complexity, or, in reverse, non-scalable time complexity requirements. This scalability question has been largely neglected. In this paper, we propose SIFTER (Space Efficient Finite Horizon MDPs), a suite of algorithms that achieve a golden middle between space and time requirements. Our former algorithm raises space complexity growing with the square root of the horizon's length without a time-complexity overhead, while the latter's space requirements depend only logarithmically in horizon length with a corresponding logarithmic time complexity overhead. A thorough experimental study under diverse settings confirms that SIFTER algorithms achieve the predicted gains, while approximation techniques do not achieve the same combination of time efficiency, space efficiency, and result quality.