In this paper, we introduce Edges , a novel deep architecture that aims at predicting the Graph Edit Distance (GED). Edges reformulates the quadratic assignment problem (QAP) associated to the GED problem as an edge prediction task within a GED instance graph constructed from the input graph pair. It uses a 3-Weisfeiler-Lehman expressive GNN, enabling to embed structural information at the edge level on this GED instance graph . It bypasses the need for costly matching solvers by directly predicting a soft assignment matrix through an end-to-end architecture. Extensive experiments on benchmark datasets demonstrate that the method enhances prediction accuracy through structural awareness while maintaining computational efficiency.

Since the advent of Graph Neural Networks (GNNs), many works have computed distances between graphs by embedding them in vector spaces using Message Passing GNNs (MPNNs).However, MPNNs are known for their lack of expressiveness as they are bounded by the firstorder Weisfeiler-Lehman test.In this paper, we use higher-order GNNs to tackle the metric learning problem and show on benchmark datasets how they can improve performance by using a node-level strategy and the Wasserstein distance. IntroductionA key challenge in modeling structured information with graphs lies in computing the distances between them.The Graph Edit Distance(GED)[4] is a state-ofthe-art method for this purpose; however, it suffers from NP-hard complexity.Recently, several architectures have been proposed to address this limitation [9,7,8,11,12] in a learning framework.These architectures generally consist of two main components.The first is an embedding block that uses siamese Graph Neural Networks(GNNs) to embed graphs either at the graph level or at the node level.The second component is a metric block that takes the embeddings generated by the first block as input and computes the distance between graphs, taking into account the embedding level.The rationale behind these architectures is that the embedding block learns an optimal representation to facilitate the computations in the metric block.To the best of our knowledge, existing embedding blocks in the literature rely on simple yet effective Message Passing Neural Networks(MPNNs), such as GCN [3] or GIN [2].Consequently, they suffer from the well-known limitations of MPNNs, including over-smoothing, over-squashing, and limited expressive power.This last limitation is particularly significant for metric learning, as it affects the ability to generate distinct embeddings for different graphs.Yet, GCN and GIN models have been shown to be at most equivalent to the firstorder Weisfeiler-Lehman(WL) test in the WL hierarchy [1].Recently, more expressive GNNs such as PPGN [5] and G 2 N 2 [6] have been introduced in the literature, achieving a 3-WL expressivity level.To attain this level of expressivity, these architectures naturally incorporate edge embeddings, adding valuable information to the traditional node-and graph-level representations.These recent developments raise two research questions: how can 3-WL GNNs be integrated into a metric learning framework, and do they enable improved performance?283

This paper presents Grammar Reinforcement Learning (GRL), a reinforcement learning algorithm that uses Monte Carlo Tree Search (MCTS) and a transformer architecture that models a Pushdown Automaton (PDA) within a context-free grammar (CFG) framework. Taking as use case the problem of efficiently counting paths and cycles in graphs, a key challenge in network analysis, computer science, biology, and social sciences, GRL discovers new matrix-based formulas for path/cycle counting that improve computational efficiency by factors of two to six w.r.t state-of-the-art approaches. Our contributions include: (i) a framework for generating transformers that operate within a CFG, (ii) the development of GRL for optimizing formulas within grammatical structures, and (iii) the discovery of novel formulas for graph substructure counting, leading to significant computational improvements.

This paper introduces a framework for formally establishing a connection between a portion of an algebraic language and a Graph Neural Network (GNN). The framework leverages Context-Free Grammars (CFG) to organize algebraic operations into generative rules that can be translated into a GNN layer model. As CFGs derived directly from a language tend to contain redundancies in their rules and variables, we present a grammar reduction scheme. By applying this strategy, we define a CFG that conforms to the third-order Weisfeiler-Lehman (3-WL) test using the matricial language MATLANG. From this 3-WL CFG, we derive a GNN model, named G$^2$N$^2$, which is provably 3-WL compliant. Through various experiments, we demonstrate the superior efficiency of G$^2$N$^2$ compared to other 3-WL GNNs across numerous downstream tasks. Specifically, one experiment highlights the benefits of grammar reduction within our framework.

Since the Message Passing (Graph) Neural Networks (MPNNs) have a linear complexity with respect to the number of nodes when applied to sparse graphs, they have been widely implemented and still raise a lot of interest even though their theoretical expressive power is limited to the first order Weisfeiler-Lehman test (1-WL). In this paper, we show that if the graph convolution supports are designed in spectral-domain by a non-linear custom function of eigenvalues and masked with an arbitrary large receptive field, the MPNN is theoretically more powerful than the 1-WL test and experimentally as powerful as a 3-WL existing models, while remaining spatially localized. Moreover, by designing custom filter functions, outputs can have various frequency components that allow the convolution process to learn different relationships between a given input graph signal and its associated properties. So far, the best 3-WL equivalent graph neural networks have a computational complexity in $\mathcal{O}(n^3)$ with memory usage in $\mathcal{O}(n^2)$, consider non-local update mechanism and do not provide the spectral richness of output profile. The proposed method overcomes all these aforementioned problems and reaches state-of-the-art results in many downstream tasks.

In this paper, we present an evaluative study of pixel-labeling methods using the HBA 1.0 dataset for historical book analysis. This study is held in the context of the 2nd historical book analysis (HBA2019) competition and in conjunction with the 15th IAPR international conference on document analysis and recognition (ICDAR2019). The HBA2019 competition provides a large experimental corpus and a thorough evaluation protocol to ensure an objective performance benchmarking of pixel-labeling document image methods. Two nested challenges are evaluated in the HBA2019 competition: Challenge 1 and Challenge 2. Challenge 1 evaluates how image analysis methods could discriminate the textual content from the graphical ones at pixel level. Challenge 2 assesses the capabilities of pixel-labeling methods to separate the textual content according to different text fonts (e.g. lowercase, uppercase, italic, etc.) at pixel level. During the competition, we received 52 and 38 different teams' registrations for Challenge 1 and Challenge 2, respectively and finally 5 of them submitted their results in each challenge. Qualitative and numerical results of the participating methods in both challenges are reported and discussed in this paper in order to provide a baseline for future evaluation studies in historical document image analysis. The evaluation shows that the method submitted by the NLPR-CASIA team achieves the highest performance in both challenges.

Developing smart ways of interacting with scanners is one of the emerging needs identified by numerous digitization professionals. To achieve better interaction with scanners, the research community in historical document image analysis is particularly interested in providing reliable tools for computer-aided indexing and retrieval of historical document images. Thus, we propose in this article a method able to retrieve from a digitized historical book, pages having layout and/or content which meet the user-defined query. Amongst the user-defined queries we focus on the transition pages (e.g. title pages of chapter, end-of-chapter and end-of-act) and pages containing a particular content component or a group of patterns (e.g. ornaments, illustrations and drop caps) in our work. The method adopted in this work is firstly based on using low-level features (texture, shape and geometric descriptors) to represent each page in the form of a graph-based signature. Then, a set of costs is estimated using an error-tolerant subgraph isomorphism algorithm in order to measure the similarity between the user-defined query formulated in terms of a pattern graph and the different subgraphs of the book page signatures and to find book pages similar to the user-defined query. To illustrate the effectiveness of the proposed method, a thorough experimental study has been conducted with quantitative observations obtained from a large number of queries having different contents and structures.

In this paper, a new binary linear programming formulation for computing the exact Graph Edit Distance (GED) between two graphs is proposed. A fundamental strength of the formulations lies in their genericity since the GED can be computed between directed or undirected fully attributed graphs. Moreover, a continuous relaxation of the domain constraints in the formulation provides an efficient lower bound approximation of the GED. A complete experimental study that compares the proposed formulations with six state-of-the-art algorithms is provided. By considering both the accuracy of the proposed solution and the efficiency of the algorithms as performance criteria, the results show that none of the compared methods dominate the others in the Pareto sense. In general, our formulation converges faster to optimality while being able to scale up to match the largest graphs in our experiments. The relaxed formulation leads to an accurate approach that is 12% more accurate than the best approximate method of our benchmark.

This paper presents an approach for spotting textual fields in commercial and administrative colored forms. We proceed by locating these fields thanks to their neighboring context which is modeled with a structural representation. First, informative zones are extracted. Second, forms are represented by graphs. In these graphs, nodes represent colored rectangular shapes while edges represent neighboring relations. Finally, the neighboring context of the queried region of interest is modeled as a graph. Subgraph isomorphism is applied in order to locate this ROI in the structural representation of a whole document. Evaluated on a 130-document image dataset, experimental results show up that our approach is efficient and that the requested information is found even if its position is changed.

This article tackles some important issues relating to the analysis of a particular case of complex ancient graphic images, called “lettrines”, “drop caps”, or “ornamental letters”. Our contribution focuses on proposing generic solutions for lettrine recognition and classification. Firstly, we propose a bottom-up segmentation method, based on texture, ensuring the separation of the letter from the elements of the background in an ornamental letter. Secondly, a structural representation is proposed for characterizing a lettrine. This structural representation is based on filtering automatically relevant information by extracting representative homogeneous regions from a lettrine to generate a graph-based signature. The proposed signature provides a rich and holistic description of the lettrine style by integrating varying low-level features (e.g. texture). Then, to categorize and classify lettrines with similar style, structure (i.e. ornamental background) and content (i.e. letter), a graph-matching paradigm has been carried out to compare and classify the resulting graph-based signatures. Finally, to demonstrate the robustness of the proposed solutions and provide additional insights into their accuracies, an experimental evaluation has been conducted using a relevant set of lettrine images. In addition, we compare the results achieved with those obtained using the state-of-the-art methods to illustrate the effectiveness of the proposed solutions.

The work conducted in this article presents a structural signature based on texture for the characterization and categorization of digitized historical book pages. The proposed signature does not assume a priori knowledge regarding page layout and content, and hence, it is applicable to a large variety of ancient books. By integrating varying low-level features (e.g. texture) characterizing the different page components (i.e. different text fonts, or graphic regions) on the one hand, and structural information describing the page layout on the other hand, the proposed signature provides a rich and holistic description of the layout and content of the analyzed book pages. More precisely, the signature-based characterization approach consists of two stages. The first stage is extracting automatically homogeneous regions. Then, the second one is proposing a graph-based page signature, which is based on the extracted homogeneous regions, reflecting its layout and content. This signature ensures the implementation of numerous applications for managing effectively a corpus or collections of books (e.g. information retrieval in digital libraries according to several criteria, or page categorization). To illustrate the effectiveness of the proposed page signature, a detailed experimental evaluation has been conducted in this article for assessing two possible categorization applications, unsupervised page classification and page stream segmentation.

For the segmentation of ancient digitized document images, it has been shown that texture feature analysis is a consistent choice for meeting the need to segment a page layout under significant and various degradations. In addition, it has been proven that the texture-based approaches work effectively without hypothesis on the document structure, neither on the document model nor the typographical parameters. Thus, by investigating the use of texture as a tool for automatically segmenting images, we propose to search homogeneous and similar content regions by analyzing texture features based on a multiresolution analysis. The preliminary results show the effectiveness of the texture features extracted from the autocorrelation function, the Grey Level Co-occurrence Matrix (GLCM), and the Gabor filters. In order to assess the robustness of the proposed texture-based approaches, images under numerous degradation models are generated and two image enhancement algorithms (non-local means filtering and superpixel techniques) are evaluated by several accuracy metrics. This study shows the robustness of texture feature extraction for segmentation in the case of noise and the uselessness of a demising step.

Recently, texture-based features have been used for digitized historical document image segmentation. It has been proven that these methods work effectively with no a priori knowledge. Moreover, it has been shown that they are robust when they are applied on degraded documents under different noise levels and types. In this paper an approach of evaluating texture-based feature sets for segmenting historical documents is presented in order to compare them. We aim at determining which texture features could be more adequate for segmenting graphical regions from textual ones on the one hand and for discriminating text in a variety of situations of different fonts and scales on the other hand. For this purpose, six well-known and widely used texture-based feature sets (autocorrelation function, Grey Level Co occurrence Matrix, Gabor filters, 3-level Haar wavelet transform, 3-level wavelet transform using 3-tap Daubechies filter and 3-level wavelet transform using 4-tap Daubechies filter) are evaluated and compared on a large corpus of historical documents. An additional insight into the computation time and complexity of each texture-based feature set is given. Qualitative and numerical experiments are also given to demonstrate each texture-based feature set performance.

International audience

In the context of historical collection conservation and worldwide diffusion, this paper presents an automatic approach of historical book page layout segmentation. In this article, we propose to search the homogeneous regions from the content of historical digitized books with little a priori knowledge by extracting and analyzing texture features. The novelty of this work lies in the unsupervised clustering of the extracted texture descriptors to find homogeneous regions, i.e. graphic and textual regions, by performing the clustering approach on an entire book instead of processing each page individually. We propose firstly to characterize the content of an entire book by extracting the texture information of each page, as our goal is to compare and index the content of digitized books. The extraction of texture features, computed without any hypothesis on the document structure, is based on two non-parametric tools: the autocorrelation function and multiresolution analysis. Secondly, we perform an unsupervised clustering approach on the extracted features in order to classify automatically the homogeneous regions of book pages. The clustering results are assessed by internal and external accuracy measures. The overall results are quite satisfying. Such analysis would help to construct a computer-aided categorization tool of pages.

In this paper, we tackle the problem of localizing graphical symbols on complex technical document images by using an original approach to solve the subgraph isomorphism problem. In the proposed system, document and symbol images are represented by vector-attributed Region Adjacency Graphs (RAG) which are extracted by a segmentation process and feature extractors. Vertices representing regions are labeled with shape descriptors whereas edges are labeled with feature vector representing topological relations between the regions. Then, in order to search the instances of a model graph describing a particular symbol in a large graph corresponding to a whole document, we model the subgraph isomorphism problem as an Integer Linear Program (ILP) which enables to be error-tolerant on vectorial labels. The problem is then solved using a free efficient solver called SYMPHONY. The whole system is evaluated on a set of synthetic documents.

In this article we present a new approach for the classification of structured data using graphs. We suggest to solve the problem of complexity in measuring the distance between graphs by using a new graph signature. We present an extension of the vector representation based on pattern frequency, which integrates labeling information. In this paper, we compare the results achieved on public graph databases for the classification of symbols and letters using this graph signature with those obtained using the graph edit distance.

Performance evaluation for document image analysis and understanding is a recurring problem. Many ground- truthed document image databases are now used to evaluate algorithms, but these databases are less useful for the design of a complete system in a precise context. This paper proposes an approach for the automatic generation of synthesised document images and associated ground-truth information based on a derivation of publishing tools. An implementation of this approach illustrates the richness of the produced information.

Document image classification is an important step in document image analysis. Based on classification results we can tackle other tasks such as indexation, understanding or navigation in document collections. Using a document representation and an unsupervised classification method, we may group documents that from the user point of view constitute valid clusters. The semantic gap between a domain independent document representation and the user implicit representation can lead to unsatisfactory results. In this paper, we describe document images based on frequent occurring symbols. This document description is created in an unsupervised manner and can be related to the domain knowledge. Using data mining techniques applied to a graph based document representation we find frequent and maximal subgraphs. For each document image, we construct a bag containing the frequent subgraphs found in it. This bag of "symbols" represents the description of a document. We present results obtained on a corpus of 60 graphical document images.

We present three classifiers used in automatic forms class identification. The first category of classifier includes the k-nearest neighbours (kNN) and the multilayer perceptron (MLP) classifiers. The second category corresponds to a new structural classifier based on tree comparison. The low level information based on a pyramidal decomposition of the document image is used by the kNN and the MLP classifiers, while the high level information represents the form content with a hierarchical structure used by the new structural classifier. Experimental results are presented. Some strategies of classifier co-operation are proposed.