Archaeological reconstruction of fragmented artifacts presents a complex computational challenge that requires both algorithmic sophistication and expert domain knowledge. We present an immersive Virtual Reality interface that bridges our reconstruction solver with public engagement and expert annotation. Built within the RePAIR project, our system enables users to interact with high-fidelity 3D scans of 2000-year-old fresco fragments from Pompeii’s House of the Painters, attempting manual reconstruction while leveraging AI assistance. Deployed at the Italian Pavilion during EXPO 2025, the system demonstrated both the intrinsic difficulty of archaeological reconstruction (low completion rates) and the potential for human-AI collaboration. Beyond public engagement, our interface serves potentially as a research platform for collecting expert annotations, benchmarking solver performance under varied initial conditions, and generating training data for future reinforcement learning approaches. Our work demonstrates how gamification and immersive technologies can simultaneously democratize cultural heritage and advance research methodologies.

• Dominant Set Multi-View Pooling to integrate topology, coarser graphs, and features. • Develop a dominant set pooling using edge weights to identify all potential clusters. • Design a fusion view attention layer to fuse coarser graphs, topology, and features. • Experimental results show DSMVPool outperforms state-of-the-art on eight benchmarks. Graph pooling is a fundamental operation in Graph Neural Networks (GNNs), designed to simplify graphs by reducing the number of nodes and edges while preserving essential structural information for classification tasks. However, most existing pooling methods tend to overlook edge weights and rely on a single-view pooling strategy that focuses either on local or global topological information, failing to capture the full structural context of the graph. To address these limitations, this study introduces a novel Dominant Set Multi-View Pooling (DSMVPool) method featuring two main contributions. First, we propose a dominant-set cluster pooling approach that analyzes the overall graph architecture and connectivity patterns, identifies potential clusters using edge weight information, and generates a coarser graph view. In addition, we create two complementary pooled views by selecting the most representative nodes based on local topology and node features. Second, we design a fusion-view attention layer that integrates the coarser graph structure with the pooled graph views, enabling our method to simultaneously capture and combine global and local structural information and node features. Extensive experiments on four graph classification benchmarks, covering computer vision, chemical, biological, and social networks, demonstrate that DSMVPool achieves superior performance compared to state-of-the-art methods.

This article introduces the maximum coverage of shortest paths under limited cost (MCLC) problem, a novel optimization task focused on deploying nodes to cover the maximum number of shortest paths within a network under a strict budget. While crucial in many real-world scenarios, this problem is computationally challenging. We propose a novel hybrid greedy (HG) algorithm, which integrates two novel greedy operations—coverage-first and contribution-first—with new refinement techniques. We prove that the proposed HG algorithm achieves a worst case approximation ratio that doubles the state-of-the-art lower bound, a significant theoretical improvement for large-scale networks. To guide practical application, we analyze the tradeoff between coverage and cost-efficiency. We derive a new Pearson correlation-based criterion that accurately predicts when and why our proposed HG approach will outperform other methods, providing a valuable guideline for algorithm selection. Extensive experiments on both synthetic and real-world networks validate our theoretical findings and confirm the practical superiority of our approach.

Sponge examples are test-time inputs optimized to increase energy consumption and prediction latency of deep networks deployed on hardware accelerators. By increasing the fraction of neurons activated during classification, these attacks reduce sparsity in network activation patterns, worsening the performance of hardware accelerators. In this work, we present a novel training-time attack, named sponge poisoning , which aims to worsen energy consumption and prediction latency of neural networks on any test input without affecting classification accuracy. To stage this attack, we assume that the attacker can control only a few model updates during training — a likely scenario, e.g., when model training is outsourced to an untrusted third party or distributed via federated learning. Our extensive experiments on image classification tasks show that sponge poisoning is effective, and that fine-tuning poisoned models to repair them poses prohibitive costs for most users, highlighting that tackling sponge poisoning remains an open issue. • We propose the first poisoning attack to increase energy consumption in DNNs while preserving their prediction accuracy. • We formulate a novel objective function to target energy consumption in Hardware ASIC accelerators. • We inspect the model activations of the models to detect the most vulnerable layers against sponge poisoning attacks. • We show that the proposed attack can be adapted to avoid violating specific energy consumption requirements. • We show how to repair models targeted by sponge attacks, revealing an alternative path toward building energy-saving DNNs.

Despite explainable AI (XAI) has recently become a hot topic and several different approaches have been developed, there is still a widespread belief that it lacks a convincing unifying foundation. On the other hand, over the past centuries, the very concept of explanation has been the subject of extensive philosophical analysis in an attempt to address the fundamental question of “why” in the context of scientific law. However, this discussion has rarely been connected with XAI. This paper tries to fill in this gap and aims to explore the concept of explanation in AI through an epistemological lens. By comparing the historical development of both the philosophy of science and AI, an intriguing picture emerges. Specifically, we show that a gradual progression has independently occurred in both domains from logical-deductive to statistical models of explanation, thereby experiencing in both cases a paradigm shift from deterministic to nondeterministic and probabilistic causality. Interestingly, we also notice that similar concepts have independently emerged in both realms such as, for example, the relation between explanation and understanding and the importance of pragmatic factors. Our study aims to be the first step towards understanding the philosophical underpinnings of the notion of explanation in AI, and we hope that our findings will shed some fresh light on the elusive nature of XAI.

This paper proposes the RePAIR dataset that represents a challenging benchmark to test modern computational and data driven methods for puzzle-solving and reassembly tasks. Our dataset has unique properties that are uncommon to current benchmarks for 2D and 3D puzzle solving. The fragments and fractures are realistic, caused by a collapse of a fresco during a World War II bombing at the Pompeii archaeological park. The fragments are also eroded and have missing pieces with irregular shapes and different dimensions, challenging further the reassembly algorithms. The dataset is multi-modal providing high resolution images with characteristic pictorial elements, detailed 3D scans of the fragments and meta-data annotated by the archaeologists. Ground truth has been generated through several years of unceasing fieldwork, including the excavation and cleaning of each fragment, followed by manual puzzle solving by archaeologists of a subset of approx. 1000 pieces among the 16000 available. After digitizing all the fragments in 3D, a benchmark was prepared to challenge current reassembly and puzzle-solving methods that often solve more simplistic synthetic scenarios. The tested baselines show that there clearly exists a gap to fill in solving this computationally complex problem.

Handwriting Text Recognition (HTR) is a fast-moving research topic in computer vision and machine learning domains. Many models have been introduced over the years, one of the most well-established ones being the Convolutional Recurrent Neural Network (CRNN), which combines convolutional feature extraction with recurrent processing of the visual embeddings. Such a model, however, presents some limitations such as a limited capability to account for contextual information. To counter this problem, we propose a new learning module built on top of the convolutional part of a classical CRNN model, derived from the relaxation labeling processes, which is able to exploit the global context reducing the local ambiguities and increasing the global consistency of the prediction. Experiments performed on three well-known handwritten recognition datasets demonstrate that the relaxation labeling procedures improve the overall transcription accuracy at both character and word levels.

Deep metric learning has yielded impressive results in tasks such as clustering and image retrieval by leveraging neural networks to obtain highly discriminative feature embeddings, which can be used to group samples into different classes. Much research has been devoted to the design of smart loss functions or data mining strategies for training such networks. Most methods consider only pairs or triplets of samples within a mini-batch to compute the loss function, which is commonly based on the distance between embeddings. We propose Group Loss, a loss function based on a differentiable label-propagation method that enforces embedding similarity across all samples of a group while promoting, at the same time, low-density regions amongst data points belonging to different groups. Guided by the smoothness assumption that "similar objects should belong to the same group", the proposed loss trains the neural network for a classification task, enforcing a consistent labelling amongst samples within a class. We design a set of inference strategies tailored towards our algorithm, named Group Loss++ that further improve the results of our model. We show state-of-the-art results on clustering and image retrieval on four retrieval datasets, and present competitive results on two person re-identification datasets, providing a unified framework for retrieval and re-identification.

Recent methods for inductive reasoning on Knowledge Graphs (KGs) transform the link prediction problem into a graph classification task. They first extract a subgraph around each target link based on the k-hop neighborhood of the target entities, encode the subgraphs using a Graph Neural Network (GNN), then learn a function that maps subgraph structural patterns to link existence. Although these methods have witnessed great successes, increasing k often leads to an exponential expansion of the neighborhood, thereby degrading the GNN expressivity due to oversmoothing. In this paper, we formulate the subgraph extraction as a local clustering procedure that aims at sampling tightly-related subgraphs around the target links, based on a personalized PageRank (PPR) approach. Empirically, on three real-world KGs, we show that reasoning over subgraphs extracted by PPR-based local clustering can lead to a more accurate link prediction model than relying on neighbors within fixed hop distances. Furthermore, we investigate graph properties such as average clustering coefficient and node degree, and show that there is a relation between these and the performance of subgraph-based link prediction.

In he past decade, object detection has achieved significant progress in natural images but not in aerial images, due to the massive variations in the scale and orientation of objects caused by the bird's-eye view of aerial images. More importantly, the lack of large-scale benchmarks has become a major obstacle to the development of object detection in aerial images (ODAI). In this paper, we present a large-scale Dataset of Object deTection in Aerial images (DOTA) and comprehensive baselines for ODAI. The proposed DOTA dataset contains 1,793,658 object instances of 18 categories of oriented-bounding-box annotations collected from 11,268 aerial images. Based on this large-scale and well-annotated dataset, we build baselines covering 10 state-of-the-art algorithms with over 70 configurations, where the speed and accuracy performances of each model have been evaluated. Furthermore, we provide a code library for ODAI and build a website for evaluating different algorithms. Previous challenges run on DOTA have attracted more than 1300 teams worldwide. We believe that the expanded large-scale DOTA dataset, the extensive baselines, the code library and the challenges can facilitate the designs of robust algorithms and reproducible research on the problem of object detection in aerial images.

Given two multitemporal aerial images, semantic change detection (SCD) aims to locate the land-cover variations and identify their change types with pixelwise boundaries. This problem is vital in many earth vision-related tasks, such as precise urban planning and natural resource management. Existing state-of-the-art algorithms mainly identify the changed pixels by applying homogeneous operations on each input image and comparing the extracted features. However, in changed regions, totally different land-cover distributions often require heterogeneous feature extraction procedures for images acquired at different times. In this article, we present an asymmetric Siamese network (ASN) to locate and identify semantic changes through feature pairs obtained from modules of widely different structures, which involves areas of various sizes and applies different quantities of parameters to factor in the discrepancy across land-cover distributions during different times. To better train and evaluate our model, we create a large-scale well-annotated SEmantic Change detectiON Dataset (SECOND), while an adaptive threshold learning (ATL) module and a separated kappa (SeK) coefficient are proposed to alleviate the influences of label imbalance in model training and evaluation. The experimental results demonstrate that the proposed model can stably outperform the state-of-the-art algorithms with different encoder backbones.

One of the most concerning threats for modern AI systems is data poisoning, where the attacker injects maliciously crafted training data to corrupt the system's behavior at test time. Availability poisoning is a particularly worrisome subset of poisoning attacks where the attacker aims to cause a Denial-of-Service (DoS) attack. However, the state-of-the-art algorithms are computationally expensive because they try to solve a complex bi-level optimization problem (the “hammer”). We observed that in particular conditions, namely, where the target model is linear (the “nut”), the usage of computationally costly procedures can be avoided. We propose a counter-intuitive but efficient heuristic that allows contaminating the training set such that the target system's performance is highly compromised. We further suggest a re-parameterization trick to decrease the number of variables to be optimized. Finally, we demonstrate that, under the considered settings, our framework achieves comparable, or even better, performances in terms of the attacker's objective while being significantly more computationally efficient.

Verb Sense Disambiguation is a well-known task in NLP, the aim is to find the correct sense of a verb in a sentence. Recently, this problem has been extended in a multimodal scenario, by exploiting both textual and visual features of ambiguous verbs leading to a new problem, the Visual Verb Sense Disambiguation (VVSD). Here, the sense of a verb is assigned considering the content of an image paired with it rather than a sentence in which the verb appears. Annotating a dataset for this task is more complex than textual disambiguation, because assigning the correct sense to a pair ofrequires both non-trivial linguistic and visual skills. In this work, differently from the literature, the VVSD task will be performed in a transductive semi-supervised learning (SSL) setting, in which only a small amount of labeled information is required, reducing tremendously the need for annotated data. The disambiguation process is based on a graph-based label propagation method which takes into account mono or multimodal representations forpairs. Experiments have been carried out on the recently published dataset VerSe, the only available dataset for this task. The achieved results outperform the current state-of-the-art by a large margin while using only a small fraction of labeled samples per sense1.

The training of autoencoder (AE) focuses on the selection of connection weights via a minimization of both the training error and a regularized term. However, the ultimate goal of AE training is to autoencode future unseen samples correctly (i.e., good generalization). Minimizing the training error with different regularized terms only indirectly minimizes the generalization error. Moreover, the trained model may not be robust to small perturbations of inputs which may lead to a poor generalization capability. In this paper, we propose a localized stochastic sensitive AE (LiSSA) to enhance the robustness of AE with respect to input perturbations. With the local stochastic sensitivity regularization, LiSSA reduces sensitivity to unseen samples with small differences (perturbations) from training samples. Meanwhile, LiSSA preserves the local connectivity from the original input space to the representation space that learns a more robustness features (intermediate representation) for unseen samples. The classifier using these learned features yields a better generalization capability. Extensive experimental results on 36 benchmarking datasets indicate that LiSSA outperforms several classical and recent AE training methods significantly on classification tasks.

Graph matching is an important and persistent problem in computer vision and pattern recognition for finding node-to-node correspondence between graphs. However, graph matching that incorporates pairwise constraints can be formulated as a quadratic assignment problem (QAP), which is NP-complete and results in intrinsic computational difficulties. This paper presents a functional representation for graph matching (FRGM) that aims to provide more geometric insights on the problem and reduce the space and time complexities. To achieve these goals, we represent each graph by a linear function space equipped with a functional such as inner product or metric, that has an explicit geometric meaning. Consequently, the correspondence matrix between graphs can be represented as a linear representation map. Furthermore, this map can be reformulated as a new parameterization for matching graphs in Euclidean space such that it is consistent with graphs under rigid or nonrigid deformations. This allows us to estimate the correspondence matrix and geometric deformations simultaneously. We use the representation of edge-attributes rather than the affinity matrix to reduce the space complexity and propose an efficient optimization strategy to reduce the time complexity. The experimental results on both synthetic and real-world datasets show that the FRGM can achieve state-of-the-art performance.

In this work, we propose an end-to-end constrained clustering scheme to tackle the person re-identification (re-id) problem. Deep neural networks (DNN) have recently proven to be effective on person re-identification task. In particular, rather than leveraging solely a probe-gallery similarity, diffusing the similarities among the gallery images in an end-to-end manner has proven to be effective in yielding a robust probe-gallery affinity. However, existing methods do not apply probe image as a constraint, and are prone to noise propagation during the similarity diffusion process. To overcome this, we propose an intriguing scheme which treats person-image retrieval problem as a constrained clustering optimization problem, called deep constrained dominant sets (DCDS). Given a probe and gallery images, we re-formulate person re-id problem as finding a constrained cluster, where the probe image is taken as a constraint (seed) and each cluster corresponds to a set of images corresponding to the same person. By optimizing the constrained clustering in an end-to-end manner, we naturally leverage the contextual knowledge of a set of images corresponding to the given person-images. We further enhance the performance by integrating an auxiliary net alongside DCDS, which employs a multi-scale ResNet. To validate the effectiveness of our method we present experiments on several benchmark datasets and show that the proposed method can outperform state-of-the-art methods.

Unsupervised domain adaptation (UDA) amounts to assigning class labels to the unlabeled instances of a dataset from a target domain, using labeled instances of a dataset from a related source domain. In this paper we propose to cast this problem in a game-theoretic setting as a non-cooperative game and introduce a fully automatized iterative algorithm for UDA based on graph transduction games (GTG). The main advantages of this approach are its principled foundation, guaranteed termination of the iterative algorithms to a Nash equilibrium (which corresponds to a consistent labeling condition) and soft labels quantifying uncertainty of the label assignment process. We also investigate the beneficial effect of using pseudo-labels from linear classifiers to initialize the iterative process. The performance of the resulting methods is assessed on publicly available object recognition benchmark datasets involving both shallow and deep features. Results of experiments demonstrate the suitability of the proposed game-theoretic approach for solving UDA tasks.

Image segmentation has come a long way since the early days of computer vision, and still remains a challenging task. Modern variations of the classical (purely bottom-up) approach, involve, e.g., some form of user assistance (interactive segmentation) or ask for the simultaneous segmentation of two or more images (co-segmentation). At an abstract level, all these variants can be thought of as "constrained" versions of the original formulation, whereby the segmentation process is guided by some external source of information. In this paper, we propose a new approach to tackle this kind of problems in a unified way. Our work is based on some properties of a family of quadratic optimization problems related to dominant sets, a graph-theoretic notion of a cluster which generalizes the concept of a maximal clique to edge-weighted graphs. In particular, we show that by properly controlling a regularization parameter which determines the structure and the scale of the underlying problem, we are in a position to extract groups of dominant-set clusters that are constrained to contain predefined elements. In particular, we shall focus on interactive segmentation and co-segmentation (in both the unsupervised and the interactive versions). The proposed algorithm can deal naturally with several types of constraints and input modalities, including scribbles, sloppy contours and bounding boxes, and is able to robustly handle noisy annotations on the part of the user. Experiments on standard benchmark datasets show the effectiveness of our approach as compared to state-of-the-art algorithms on a variety of natural images under several input conditions and constraints.

This paper presents a new approach for the challenging problem of geo-localization using image matching in a structured database of city-wide reference images with known GPS coordinates. We cast the geo-localization as a clustering problem of local image features. Akin to existing approaches to the problem, our framework builds on low-level features which allow local matching between images. For each local feature in the query image, we find its approximate nearest neighbors in the reference set. Next, we cluster the features from reference images using Dominant Set clustering, which affords several advantages over existing approaches. First, it permits variable number of nodes in the cluster, which we use to dynamically select the number of nearest neighbors for each query feature based on its discrimination value. Second, this approach is several orders of magnitude faster than existing approaches. Thus, we obtain multiple clusters (different local maximizers) and obtain a robust final solution to the problem using multiple weak solutions through constrained Dominant Set clustering on global image features, where we enforce the constraint that the query image must be included in the cluster. This second level of clustering also bypasses heuristic approaches to voting and selecting the reference image that matches to the query. We evaluate the proposed framework on an existing dataset of 102k street view images as well as a new larger dataset of 300k images, and show that it outperforms the state-of-the-art by 20 and 7 percent, respectively, on the two datasets.

Object detection is an important and challenging problem in computer vision. Although the past decade has witnessed major advances in object detection in natural scenes, such successes have been slow to aerial imagery, not only because of the huge variation in the scale, orientation and shape of the object instances on the earth's surface, but also due to the scarcity of well-annotated datasets of objects in aerial scenes. To advance object detection research in Earth Vision, also known as Earth Observation and Remote Sensing, we introduce a large-scale Dataset for Object deTection in Aerial images (DOTA). To this end, we collect 2806 aerial images from different sensors and platforms. Each image is of the size about 4000 × 4000 pixels and contains objects exhibiting a wide variety of scales, orientations, and shapes. These DOTA images are then annotated by experts in aerial image interpretation using 15 common object categories. The fully annotated DOTA images contains 188, 282 instances, each of which is labeled by an arbitrary (8 d.o.f.) quadrilateral. To build a baseline for object detection in Earth Vision, we evaluate state-of-the-art object detection algorithms on DOTA. Experiments demonstrate that DOTA well represents real Earth Vision applications and are quite challenging.

Object detection in aerial images plays a significant role in intelligent interpretation of aerial images. Hence many effective methods, especially the new-generation data-driven methods, have been developed for this task. Here, we hold the ODAI, a new contest that focused on object detection in aerial images, based on a new large-scale aerial image dataset called DOTA [1]. This contest contains over 3000 large-size images ( 4k×4k pixels), which cover 211,581 instances divided into 15 categories. Each instance is labeled by an arbitrary (8 d.o.f.) quadrilateral. Besides, we propose two tasks for this contest, named object detection with the horizontal bounding box (OD-HBB) and object detection with the oriented bounding box (OD-OBB). The contest was opened on February 7, 2018, and ended on April 30, 2018. A website is open to the public, which provides links to download data and evaluation server. We have totally received 60 registrations. There are 8 teams that have successfully submitted results on the OD-HBB task with the top mAP as 0.719, and 9 teams that have successfully submitted results on the OD-OBB task with the top mAP as 0.705. Through the contest, we hope to draw extensive attention from a wide range of communities and call for more future research and efforts for the task of object detection in aerial images.

A major impediment to the application of deep learning to real-world problems is the scarcity of labeled data. Small training sets are in fact of no use to deep networks as, due to the large number of trainable parameters, they will very likely be subject to overfitting phenomena. On the other hand, the increment of the training set size through further manual or semi-automatic labellings can be costly, if not possible at times. Thus, the standard techniques to address this issue are transfer learning and data augmentation, which consists of applying some sort of “transformation” to existing labeled instances to let the training set grow in size. Although this approach works well in applications such as image classification, where it is relatively simple to design suitable transformation operators, it is not obvious how to apply it in more structured scenarios. Motivated by the observation that in virtually all application domains it is easy to obtain unlabeled data, in this paper we take a different perspective and propose a label augmentation approach. We start from a small, curated labeled dataset and let the labels propagate through a larger set of unlabeled data using graph transduction techniques. This allows us to naturally use (second-order) similarity information which resides in the data, a source of information which is typically neglected by standard augmentation techniques. In particular, we show that by using known game theoretic transductive processes we can create larger and accurate enough labeled datasets which use results in better trained neural networks. Preliminary experiments are reported which demonstrate a consistent improvement over standard image classification datasets.

Speaker clustering is the task of forming speaker-specific groups based on a set of utterances. In this paper, we address this task by using Dominant Sets (DS). DS is a graph-based clustering algorithm with interesting properties that fits well to our problem and has never been applied before to speaker clustering. We report on a comprehensive set of experiments on the TIMIT dataset against standard clustering techniques and specific speaker clustering methods. Moreover, we compare performances under different features by using ones learned via deep neural network directly on TIMIT and other ones extracted from a pre-trained VGGVox net. To asses the stability, we perform a sensitivity analysis on the free parameters of our method, showing that performance is stable under parameter changes. The extensive experimentation carried out confirms the validity of the proposed method, reporting state-of-the-art results under three different standard metrics. We also report reference baseline results for speaker clustering on the entire TIMIT dataset for the first time.

Feature matching is aimed to establish the correspondences between features of two sets. Aside from the well-known graph matching, hyper-graph matching is receiving increasing interests due to its ability to encode more invariance information. Existing hyper-graph matching algorithms are usually based on the maximization of matching score between correspondences. In this paper we treat the candidate matches as pure strategies and formulate the hyper-graph matching problem as a non-cooperative multi-player clustering game. Specifically, we calculate the higher-order similarity as the payoff of players in selecting the corresponding triplet of pure strategies, and find that the subset of consistent matches can be extracted by optimizing a polynomial function with a higher-order replicator dynamics over the standard simplex. With the Baum-Eagon inequality, we arrive at the equilibrium of the game and obtain a subset of consistent matches as the final matching result. Our approach is especially useful in dealing with the case that some features in the model image have no correspondences in the test image. In addition, with our approach each match is assigned a weight which reflects the relationship with other matches and can be used to enforce the one-to-one constraint. Experiments on both synthetic datasets and real images demonstrate the effectiveness of our approach.

We present the DeepScores dataset with the goal of advancing the state-of-the-art in small object recognition by placing the question of object recognition in the context of scene understanding. DeepScores contains high quality images of musical scores, partitioned into 300, 000 sheets of written music that contain symbols of different shapes and sizes. With close to a hundred million small objects, this makes our dataset not only unique, but also the largest public dataset. DeepScores comes with ground truth for object classification, detection and semantic segmentation. DeepScores thus poses a relevant challenge for computer vision in general, and optical music recognition (OMR) research in particular. We present a detailed statistical analysis of the dataset, comparing it with other computer vision datasets like PASCAL VOC, SUN, SVHN, ImageNet, MS-COCO, as well as with other OMR datasets. Finally, we provide baseline performances for object classification, intuition for the inherent difficulty that DeepScores poses to state-of-the-art object detectors like YOLO or R-CNN, and give pointers to future research based on this dataset.

This article presents a new model for word sense disambiguation formulated in terms of evolutionary game theory, where each word to be disambiguated is represented as a node on a graph whose edges represent word relations and senses are represented as classes. The words simultaneously update their class membership preferences according to the senses that neighboring words are likely to choose. We use distributional information to weigh the influence that each word has on the decisions of the others and semantic similarity information to measure the strength of compatibility among the choices. With this information we can formulate the word sense disambiguation problem as a constraint satisfaction problem and solve it using tools derived from game theory, maintaining the textual coherence. The model is based on two ideas: Similar words should be assigned to similar classes and the meaning of a word does not depend on all the words in a text but just on some of them. The article provides an in-depth motivation of the idea of modeling the word sense disambiguation problem in terms of game theory, which is illustrated by an example. The conclusion presents an extensive analysis on the combination of similarity measures to use in the framework and a comparison with state-of-the-art systems. The results show that our model outperforms state-of-the-art algorithms and can be applied to different tasks and in different scenarios.

In spam and malware detection, attackers exploit randomization to obfuscate malicious data and increase their chances of evading detection at test time, e.g., malware code is typically obfuscated using random strings or byte sequences to hide known exploits. Interestingly, randomization has also been proposed to improve security of learning algorithms against evasion attacks, as it results in hiding information about the classifier to the attacker. Recent work has proposed game-theoretical formulations to learn secure classifiers, by simulating different evasion attacks and modifying the classification function accordingly. However, both the classification function and the simulated data manipulations have been modeled in a deterministic manner, without accounting for any form of randomization. In this paper, we overcome this limitation by proposing a randomized prediction game, namely, a noncooperative game-theoretic formulation in which the classifier and the attacker make randomized strategy selections according to some probability distribution defined over the respective strategy set. We show that our approach allows one to improve the tradeoff between attack detection and false alarms with respect to the state-of-the-art secure classifiers, even against attacks that are different from those hypothesized during design, on application examples including handwritten digit recognition, spam, and malware detection.In spam and malware detection, attackers exploit randomization to obfuscate malicious data and increase their chances of evading detection at test time, e.g., malware code is typically obfuscated using random strings or byte sequences to hide known exploits. Interestingly, randomization has also been proposed to improve security of learning algorithms against evasion attacks, as it results in hiding information about the classifier to the attacker. Recent work has proposed game-theoretical formulations to learn secure classifiers, by simulating different evasion attacks and modifying the classification function accordingly. However, both the classification function and the simulated data manipulations have been modeled in a deterministic manner, without accounting for any form of randomization. In this paper, we overcome this limitation by proposing a randomized prediction game, namely, a noncooperative game-theoretic formulation in which the classifier and the attacker make randomized strategy selections according to some probability distribution defined over the respective strategy set. We show that our approach allows one to improve the tradeoff between attack detection and false alarms with respect to the state-of-the-art secure classifiers, even against attacks that are different from those hypothesized during design, on application examples including handwritten digit recognition, spam, and malware detection.

The clustering algorithm by fast search and find of density peaks is shown to be a promising clustering approach. However, this algorithm involves manual selection of cluster centers, which is not convenient in practical applications. In this paper we discuss the correlation between density peaks and cluster centers. As a result, we present a new local density estimation method to highlight the uniqueness of cluster centers by making use of the farthest ones in nearest neighbors of data. Furthermore, we propose to use density normalization to deal with the density difference among clusters. Given the number of clusters, our algorithm is able to accomplish the clustering process without human intervention and improve the clustering results. In experiments on several datasets, our algorithm is shown to outperform the original one with both cutoff and Gaussian kernels evidently.

In this article we propose a method to refine the clustering results obtained with the nonnegative matrix factorization (NMF) technique, imposing consistency constraints on the final labeling of the data. The research community focused its effort on the initialization and on the optimization part of this method, without paying attention to the final cluster assignments. We propose a game theoretic framework in which each object to be clustered is represented as a player, which has to choose its cluster membership. The information obtained with NMF is used to initialize the strategy space of the players and a weighted graph is used to model the interactions among the players. These interactions allow the players to choose a cluster which is coherent with the clusters chosen by similar players, a property which is not guaranteed by NMF, since it produces a soft clustering of the data. The results on common benchmarks show that our model is able to improve the performances of many NMF formulations.

Learning new global relations based on an initial affinity of the database objects has shown significant improvements in similarity retrievals. Locally constrained diffusion process is one of the recent effective tools in learning the intrinsic manifold structure of a given data. Existing methods, which constrain the diffusion process locally, have problems - manual choice of optimal local neighborhood size, do not allow for intrinsic relation among the neighbors, fix initialization vector to extract dense neighbor - which negatively affect the affinity propagation. We propose a new approach, which alleviate these issues, based on some properties of a family of quadratic optimization problems related to dominant sets, a well-known graph-theoretic notion of a cluster which generalizes the concept of a maximal clique to edge-weighted graphs. In particular, we show that by properly controlling a regularization parameter which determines the structure and the scale of the underlying problem, we are in a position to extract dominant set cluster which is constrained to contain user-provided query. Experimental results on standard benchmark datasets show the effectiveness of the proposed approach.

We present a unified approach for simultaneous clustering and outlier detection in data. We utilize some properties of a family of quadratic optimization problems related to dominant sets, a well-known graph-theoretic notion of a cluster which generalizes the concept of a maximal clique to edge-weighted graphs. Unlike most (all) of the previous techniques, in our framework the number of clusters arises intuitively and outliers are obliterated automatically. The resulting algorithm discovers both parameters from the data. Experiments on real and on large scale synthetic dataset demonstrate the effectiveness of our approach and the utility of carrying out both clustering and outlier detection in a concurrent manner.

In this article we propose a new model for document clustering, based on game theoretic principles. Each document to be clustered is represented as a player, in the game theoretic sense, and each cluster as a strategy that the players have to choose in order to maximize their payoff. The geometry of the data is modeled as a graph, which encodes the pairwise similarity among each document and the games are played among similar players. In each game the players update their strategies, according to what strategy has been effective in previous games. The Dominant Set clustering algorithm is used to find the prototypical elements of each cluster. This information is used in order to divide the players in two disjoint sets, one collecting labeled players, which always play a definite strategy and the other one collecting unlabeled players, which update their strategy at each iteration of the games. The evaluation of the system was conducted on 13 document datasets and shows that the proposed method performs well compared to different document clustering algorithms.

Multi‐object tracking is an interesting but challenging task in the field of computer vision. Most previous works based on data association techniques merely take into account the relationship between detection responses in a locally limited temporal domain, which makes them inherently prone to identity switches and difficulties in handling long‐term occlusions. In this study, a dominant set clustering based tracker is proposed, which formulates the tracking task as a problem of finding dominant sets in an auxiliary edge weighted graph. Unlike most techniques which are limited in temporal locality (i.e. few frames are considered), the authors utilised a pairwise relationships (in appearance and position) between different detections across the whole temporal span of the video for data association in a global manner. Meanwhile, temporal sliding window technique is utilised to find tracklets and perform further merging on them. The authors’ robust tracklet merging step renders the tracker to long term occlusions with more robustness. The authors present results on three different challenging datasets (i.e. PETS2009‐S2L1, TUD‐standemitte and ETH dataset (‘sunny day’ sequence)), and show significant improvements compared with several state‐of‐art methods.

Traditional machine learning and pattern recognition techniques are intimately linked to the notion of feature spaces. Adopting this view, each object is described in terms of a vector of numerical attributes and is, therefore, mapped to a point in a Euclidean (geometric) vector space, so that the distances between the points reflect the observed (dis)similarities between the respective objects. This kind of representation is attractive because geometric spaces offer powerful analytical as well as computational tools that are simply not available in other representations. Indeed, classical machine learning methods are tightly related to geometrical concepts, and numerous powerful tools have been developed during the last few decades, starting from the maximal likelihood method in the 1920s to perceptrons in the 1960s and, more recently, to kernel machines and deep learning architectures.

We address the problem of encoding a graph of order n into a graph of order k <; n in a way to minimize reconstruction error. We characterize this encoding in terms of a particular factorization of the adjacency matrix of the original graph. The factorization is determined as the solution of a discrete optimization problem, which is for convenience relaxed into a continuous, but equivalent, one. We propose a new multiplicative update rule for the optimization task. Experiments are conducted to assess the effectiveness of the proposed approach.

Ensembles of randomized decision trees, known as Random Forests, have become a valuable machine learning tool for addressing many computer vision problems. Despite their popularity, few works have tried to exploit contextual and structural information in random forests in order to improve their performance. In this paper, we propose a simple and effective way to integrate contextual information in random forests, which is typically reflected in the structured output space of complex problems like semantic image labelling. Our paper has several contributions: We show how random forests can be augmented with structured label information and be used to deliver structured low-level predictions. The learning task is carried out by employing a novel split function evaluation criterion that exploits the joint distribution observed in the structured label space. This allows the forest to learn typical label transitions between object classes and avoid locally implausible label configurations. We provide two approaches for integrating the structured output predictions obtained at a local level from the forest into a concise, global, semantic labelling. We integrate our new ideas also in the Hough-forest framework with the view of exploiting contextual information at the classification level to improve the performance on the task of object detection. Finally, we provide experimental evidence for the effectiveness of our approach on different tasks: Semantic image labelling on the challenging MSRCv2 and CamVid databases, reconstruction of occluded handwritten Chinese characters on the Kaist database and pedestrian detection on the TU Darmstadt databases.

Hypergraph clustering refers to the process of extracting maximally coherent groups from a set of objects using high-order (rather than pairwise) similarities. Traditional approaches to this problem are based on the idea of partitioning the input data into a predetermined number of classes, thereby obtaining the clusters as a by-product of the partitioning process. In this paper, we offer a radically different view of the problem. In contrast to the classical approach, we attempt to provide a meaningful formalization of the very notion of a cluster and we show that game theory offers an attractive and unexplored perspective that serves our purpose well. To this end, we formulate the hypergraph clustering problem in terms of a noncooperative multiplayer "clustering game," and show that a natural notion of a cluster turns out to be equivalent to a classical (evolutionary) game-theoretic equilibrium concept. We prove that the problem of finding the equilibria of our clustering game is equivalent to locally optimizing a polynomial function over the standard simplex, and we provide a discrete-time high-order replicator dynamics to perform this optimization, based on the Baum-Eagon inequality. Experiments over synthetic as well as real-world data are presented which show the superiority of our approach over the state of the art.

In this paper we introduce Structured Local Predictors (SLP) — A new formulation that considers the image labelling problem from a structured learning point of view. SLP are locally operating models, which provide a per-pixel labelling by exploiting contextual relations, learned from complex interactions between labels and a customizable intermediate representation of the image data. Our first key contribution is to handle flexible configurations of pairwise interactions between image pixels while allowing them to be made arbitrarily dependent on the image data. Moreover, we pose the parameter learning process as a convex, structured-learning problem, which can be efficiently solved in a globally optimal way due to the introduction of a continuous, structured output space. Finally, we provide an interface to our model by means of a quantization space, allowing to define task-specific intermediate representations for the input data. In our experiments we demonstrate the broad applicability of our model for tasks like inpainting and semantic labelling.

In this paper we introduce Context-Sensitive Decision Forests - A new perspective to exploit contextual information in the popular decision forest framework for the object detection problem. They are tree-structured classifiers with the ability to access intermediate prediction (here: classification and regression) information during training and inference time. This intermediate prediction is available to each sample, which allows us to develop context-based decision criteria, used for refining the prediction process. In addition, we introduce a novel split criterion which in combination with a priority based way of constructing the trees, allows more accurate regression mode selection and hence improves the current context information. In our experiments, we demonstrate improved results for the task of pedestrian detection on the challenging TUD data set when compared to state-of-the-art methods.

Graph transduction is a popular class of semisupervised learning techniques that aims to estimate a classification function defined over a graph of labeled and unlabeled data points. The general idea is to propagate the provided label information to unlabeled nodes in a consistent way. In contrast to the traditional view, in which the process of label propagation is defined as a graph Laplacian regularization, this article proposes a radically different perspective, based on game-theoretic notions. Within the proposed framework, the transduction problem is formulated in terms of a noncooperative multiplayer game whereby equilibria correspond to consistent labelings of the data. An attractive feature of this formulation is that it is inherently a multiclass approach and imposes no constraint whatsoever on the structure of the pairwise similarity matrix, being able to naturally deal with asymmetric and negative similarities alike. Experiments on a number of real-world problems demonstrate that the proposed approach performs well compared with state-of-the-art algorithms, and it can deal effectively with various types of similarity relations.

In this work we introduce a novel solution to the semantic image labelling problem, i.e. the task of assigning semantic object class labels to individual pixels in a test image.Conventional methods are typically relying on random fields for modelling interactions between neighboring pixels and obtaining smooth labelling results using unary and pairwise cost functions.Instead, we consider the labelling problem as a puzzle game, where the final labelling is obtained by assembling discriminatively learned candidate sets of label puzzle pieces, each representing a topological and semantically plausible label configuration.The puzzle game is set up by means of a modified random forest classifier, designed to learn the local, topological label-structure and hence the local context associated to the training data.To solve the puzzle game we propose an iterative optimization technique that maximizes an agreement function by alternatingly seeking for the best label puzzle piece per pixel and the resulting semantic labelling per image.We provide both, theoretical properties of our puzzle solver algorithm as well as experimental results on the challenging MSRC and CamVid databases.In a direct comparison with a conditional random field we obtain superior results, indicating the practicability of our proposed method.

In this paper we propose a simple and effective way to integrate structural information in random forests for semantic image labelling. By structural information we refer to the inherently available, topological distribution of object classes in a given image. Different object class labels will not be randomly distributed over an image but usually form coherently labelled regions. In this work we provide a way to incorporate this topological information in the popular random forest framework for performing low-level, unary classification. Our paper has several contributions: First, we show how random forests can be augmented with structured label information. In the second part, we introduce a novel data splitting function that exploits the joint distributions observed in the structured label space for learning typical label transitions between object classes. Finally, we provide two possibilities for integrating the structured output predictions into concise, semantic labellings. In our experiments on the challenging MSRC and CamVid databases, we compare our method to standard random forest and conditional random field classification results.

The paper introduces a framework for clustering data objects in a similarity-based context. The aim is to cluster objects into a given number of classes without imposing a hard partition, but allowing for a soft assignment of objects to clusters. Our approach uses the assumption that similarities reflect the likelihood of the objects to be in a same class in order to derive a probabilistic model for estimating the unknown cluster assignments. This leads to a polynomial optimization in probability domain, which is tackled by means of a result due to Baum and Eagon. Experiments on both synthetic and real standard datasets show the effectiveness of our approach.

With this paper we offer a game-theoretic perspective for the all-pervasive matching problem in computer vision. Specifically, we formulate the matching problem as a (population) non-cooperative game where the potential associations between the items to be matched correspond to (pure) strategies, while payoffs reflect the degree of compatibility between competing hypotheses. Within this formulation, the solutions of the matching problem correspond to evolutionary stable states (ESS's), a robust population-based generalization of the notion of a Nash equilibrium. In order to find ESS's of our matching game, we propose using a novel, fast evolutionary game dynamics motivated by Darwinian selection processes, which let the pure strategies play against each other until an equilibrium is reached. A distinguishing feature of the proposed framework is that it allows one to naturally deal with general many-to-many matching problems even in the presence of asymmetric compatibilities. The potential of the proposed approach is demonstrated via two sets of image matching experiments, both of which show that our results outperform those obtained using well-known domain-specific algorithms.

Hypergraph clustering refers to the process of extracting maximally coherent groups from a set of objects using high-order (rather than pairwise) similarities. Traditional approaches to this problem are based on the idea of partitioning the input data into a user-defined number of classes, thereby obtaining the clusters as a by-product of the partitioning process. In this paper, we provide a radically different perspective to the problem. In contrast to the classical approach, we attempt to provide a meaningful formalization of the very notion of a cluster and we show that game theory offers an attractive and unexplored perspective that serves well our purpose. Specifically, we show that the hypergraph clustering problem can be naturally cast into a non-cooperative multi-player ``clustering game, whereby the notion of a cluster is equivalent to a classical game-theoretic equilibrium concept. From the computational viewpoint, we show that the problem of finding the equilibria of our clustering game is equivalent to locally optimizing a polynomial function over the standard simplex, and we provide a discrete-time dynamics to perform this optimization. Experiments are presented which show the superiority of our approach over state-of-the-art hypergraph clustering techniques.

A problem commonly encountered in Computer Vision is the recovery of the transformation parameters between two affinely distorted images. In this paper, we propose a novel feature-based approach that casts the matching problem to the search of a maximum clique over an auxiliary hypergraph. We also introduce a continuous-based characterization of cliques in hypergraphs that allows us to handle the hard combinatorial problem using tools from the continuous domain. Finally, we present experimental result and comparisons with a state-of-the-art algorithm.

The field of pairwise clustering is currently dominated by the idea of dividing a set of objects into disjoints classes, thereby giving rise to (hard) partitions of the input data. However, in many computer vision and pattern recognition problems this approach is too restrictive as objects might reasonably belong to more than one class. In this paper, we adopt a game-theoretic perspective to the iterative extraction of possibly overlapping clusters: Game dynamics are used to locate individual groups, and after each extraction the similarity matrix is transformed in such a way as to make the located cluster unstable under the dynamics, without affecting the remaining groups.

We develop a new graph-theoretic approach for pairwise data clustering which is motivated by the analogies between the intuitive concept of a cluster and that of a dominant set of vertices, a notion introduced here which generalizes that of a maximal complete subgraph to edge-weighted graphs. We establish a correspondence between dominant sets and the extrema of a quadratic form over the standard simplex, thereby allowing the use of straightforward and easily implementable continuous optimization techniques from evolutionary game theory. Numerical examples on various point-set and image segmentation problems confirm the potential of the proposed approach.

Pairwise grouping and clustering approaches have traditionally worked under the assumption that the similarities or compatibilities between the elements to be grouped are symmetric. However, asymmetric compatibilities arise naturally in many areas of computer vision and pattern recognition. Hence, there is a need for a new generic approach to clustering and grouping that can deal with asymmetries in the compatibilities. In this paper, we present a generic framework for grouping and clustering derived from a game-theoretic formalization of the competition between the hypotheses of group membership, and apply it to perceptual grouping. In the proposed approach groups correspond to evolutionary stable strategies, a classic notion in evolutionary game theory. We also provide a combinatorial characterization of the stable strategies, and, hence, of the elements that belong to a group. Experiments show that our approach outperforms both state-of-the-art clustering-based perceptual grouping approacheswith symmetric compatibilities, and other approaches explicitly designed to make use of asymmetric compatibilities.

Evolutionary game-theoretic models and, in particular, the so-called replicator equations have recently proven to be remarkably effective at approximately solving the maximum clique and related problems. The approach is centered around a classic result from graph theory that formulates the maximum clique problem as a standard (continuous) quadratic program and exploits the dynamical properties of these models, which, under a certain symmetry assumption, possess a Lyapunov function. In this letter, we generalize previous work along these lines in several respects. We introduce a wide family of game-dynamic equations known as payoff-monotonic dynamics, of which replicator dynamics are a special instance, and show that they enjoy precisely the same dynamical properties as standard replicator equations. These properties make any member of this family a potential heuristic for solving standard quadratic programs and, in particular, the maximum clique problem. Extensive simulations, performed on random as well as DIMACS benchmark graphs, show that this class contains dynamics that are considerably faster than and at least as accurate as replicator equations. One problem associated with these models, however, relates to their inability to escape from poor local solutions. To overcome this drawback, we focus on a particular subclass of payoff-monotonic dynamics used to model the evolution of behavior via imitation processes and study the stability of their equilibria when a regularization parameter is allowed to take on negative values. A detailed analysis of these properties suggests a whole class of annealed imitation heuristics for the maximum clique problem, which are based on the idea of varying the parameter during the imitation optimization process in a principled way, so as to avoid unwanted inefficient solutions. Experiments show that the proposed annealing procedure does help to avoid poor local optima by initially driving the dynamics toward promising regions in state space. Furthermore, the models outperform state-of-the-art neural network algorithms for maximum clique, such as mean field annealing, and compare well with powerful continuous-based heuristics.

We address the problem of comparing attributed trees and propose four novel distance measures centered around the notion of a maximal similarity common subtree. The proposed measures are general and defined on trees endowed with either symbolic or continuous-valued attributes and can be applied to rooted as well as unrooted trees. We prove that our measures satisfy the metric constraints and provide a polynomial-time algorithm to compute them. This is a remarkable and attractive property, since the computation of traditional edit-distance-based metrics is, in general, NP-complete, at least in the unordered case. We experimentally validate the usefulness of our metrics on shape matching tasks and compare them with (an approximation of) edit-distance.

Dominant sets are a new graph-theoretic concept that has proven to be relevant in pairwise data clustering problems, such as image seg- mentation. They generalize the notion of a maximal clique to edge- weighted graphs and have intriguing, non-trivial connections to continu- ous quadratic optimization and spectral-based grouping. We address the problem of grouping out-of-sample examples after the clustering process has taken place. This may serve either to drastically reduce the compu- tational burden associated to the processing of very large data sets, or to efficiently deal with dynamic situations whereby data sets need to be updated continually. We show that the very notion of a dominant set of- fers a simple and efficient way of doing this. Numerical experiments on various grouping problems show the effectiveness of the approach.

When matching regions from "similar" images, one typically has the problem of missing counterparts due to local or even global variations of segmentation fineness. Matching segmentation hierarchies, however, not only increases the chances of finding counterparts, but also allows us to exploit the manifold constraints coming from the topological relations between any two regions in a hierarchy. To define the topological relations we represent a plane image ℐ by a plane attributed graph G and derive a finite topology [Formula: see text] from G. In particular, segmenting ℐ corresponds to taking a topological minor of G which, in turn, is equivalent to coarsening [Formula: see text]. Moreover, each finite topology involved is a coarsening of the standard topology on ℝ2. Then, we construct a weighted association graph GA, the nodes of which represent potential matches and the edges of which indicate topological consistency with respect to [Formula: see text]. Specifically, a maximal weight clique of GAcorresponds to a topologically consistent mapping with maximal total similarity. To find "heavy" cliques, we extend a greedy pivoting-based heuristic to the weighted case. Experiments on pairs of stereo images, on a video sequence of a cluttered outdoor scene, and on a sequence of panoramic images demonstrate the effectiveness of our method.

Two distance measures for attributed graphs are presented that are based on the maximal similarity common subgraph of two graphs. They are generalizations of two existing distance measures based on the maximal common subgraph. The new measures are superior to the well-known measures based on elementary edit transformations in that no particular edit operations (together with their costs) need to be defined. Moreover, they can deal not only with structural distortions, but also with perturbations of attributes. It is shown that the new distance measures are metrics.

ENERGY minimization techniques are central to many methods in computer vision and pattern recognition. Stated simply, if a task can be posed as the minimization of an energy measure, which may, for instance, be the negative logarithm of a probability or an entropy, then a variety of optimization methods may be applied to locate the solution. The solution may be a vector of parameters representing the shapes of a curve, a surface, or a volume, it may be a set of symbolic labels representing the semantic or syntactic content of a signal, or it may be a graph representing arrangement or structure. The optimization methods that can be applied to the cost function to recover the solution include gradient descent, simulated annealing, mean-field annealing, evolutionary search, and tabu search, to mention just a few. Many of the classical methods in the fields of computer vision and pattern recognitionmake use of energyminimization techniques. Familiar examples include relaxation labeling, regularization, active contours, and Markov models. More recent examples include the use of graph-cuts, spectral graph theory, and semidefinite programming. Energy minimization techniques have also been pivotal in the development of algorithms for learning, inference, and classification. One of the characteristics of this field is that it draws strongly on recent developments in other disciplines such as mathematics, statistics, operations research, biology, and economics. Moreover, the basic methodology is being developed at a great rate in these related disciplines. In this respect, energy minimization is different from other widely used techniques such as geometry or probability, where the basic methods have been available in the mathematics literature for well over 100 years. It is probably fair to say that the problems of optimization and, in particular, combinatorial optimization, are ones of a computational nature and have hence only emerged over the past few decades. Our own involvement in this field has been, in part, through a biennial series of workshops (EMMVCPR) that commenced in 1997 and which have been aimed at providing a focus for research in this area. From the interest shown in these workshops and the number of papers on the topic appearing in the main conferences (CVPR, ECCV, ICCV), it seemed to us that a special edition of IEEE Transactions on Pattern Analysis and Machine Intelligence would be both timely and valuable to the community. The call for papers was issued in mid-2001 and we received 50 papers by the deadline on 1 May 2002. Each paper was reviewed by at least three reviewers according to the standard TPAMI reviewing procedure. This meant that we needed the assistance of some 150 reviewers. By late October 2002, we had first reviews for all of the papers and met in Venice to make initial decisions. Based on the reviews, and giving authors the chance to revise their papers in the light of reviewers comments, we selected the six papers that appear in the current special section, together with three papers that will appear in a subsequent special section. The papers span a diverse set of methods and applications. The techniques covered include semidefinite programming, Markov models, and simulated annealing, while the problems addressed include deformable models, shape-from-shading, and clustering. The first regular paper in this special section is “Binary Partitioning, Perceptual Grouping, and Restoration with Semidefinite Programming” by J. Keuchel, C. Schnorr, C. Schellewald, and D. Cremers. The authors describe a new optimization method based on semidefinite programming relaxations. The method is applied to the computer vision problems of unsupervised partitioning, figure-ground discrimination, and binary restoration. The interesting feature of the proposed method is that it does not require any parameter tuning. Moreover, apart from the symmetry condition, no assumptions aremade concerning the objective criterion. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 25, NO. 11, NOVEMBER 2003 1361

We develop a framework for the image segmentation problem based on a new graph-theoretic formulation of clustering. The approach is motivated by the analogies between the intuitive concept of a cluster and that of a dominant set of vertices, a notion that generalizes that of a maximal complete subgraph to edge-weighted graphs. We also establish a correspondence between dominant sets and the extrema of a quadratic form over the standard simplex, thereby allowing us the use of continuous optimization techniques such as replicator dynamics from evolutionary game theory. Such systems are attractive as they can be coded in a few lines of any high-level programming language, can easily be implemented in a parallel network of locally interacting units, and offer the advantage of biological plausibility. We present experimental results on real-world images which show the effectiveness of the proposed approach.

Dominant sets are a new graph-theoretic concept that has proven to be relevant in partitional (flat) clustering as well as image segmentation problems. However, in many computer vision applications, such as the organization of an image database, it is important to provide the data to be clustered with a hierarchical organization, and it is not clear how to do this within the dominant set framework. We address precisely this problem, and present a simple and elegant solution to it. To this end, we consider a family of (continuous) quadratic programs, which contain a parameterized regularization term that controls the global shape of the energy landscape. When the regularization parameter is zero the local solutions are known to be in one-to-one correspondence with dominant sets, but when it is positive an interesting picture emerges. We determine bounds for the regularization parameter that allow us to exclude from the set of local solutions those inducing clusters of size smaller than a prescribed threshold. This suggests a new (divisive) hierarchical approach to clustering, which is based on the idea of properly varying the regularization parameter during the clustering process. Straightforward dynamics from evolutionary game theory are used to locate the solutions of the quadratic programs at each level of the hierarchy. We apply the proposed framework to the problem of organizing a shape database. Experiments with three different similarity matrices (and databases) reported in the literature have been conducted, and the results confirm the effectiveness of our approach.

We propose a new class of heuristics for the maximum clique problem (MCP) whose basic ingredients are: (1) a parameterized continuous formulation of MCP, (2) an instability analysis of equilibria of imitation dynamics from evolutionary game theory, and (3) a principled way of varying a regularization parameter during the evolution process so as to avoid inefficient solutions. The resulting annealed imitation" class is shown to contain algorithms that are dramatically faster than and as accurate as state-of-the-art neural network heuristics for maximum clique.

Motivated by our recent work on rooted tree matching, in this paper we provide a solution to the problem of matching two free (i.e., unrooted) trees by constructing an association graph whose maximal cliques are in one-to-one correspondence with maximal common subtrees. We then solve the problem using simple payoff-monotonic dynamics from evolutionary game theory. We illustrate the power of the approach by matching articulated and deformed shapes described by shape-axis trees. Experiments on hundreds of larger, uniformly random trees are also presented. The results are impressive: despite the inherent inability of these simple dynamics to escape from local optima, they always returned a globally optimal solution.

Motivated by our recent work on rooted tree matching, in this paper we provide a solution to the problem of matching two free (i.e., unrooted) trees by constructing an association graph whose maximal cliques are in one-to-one correspondence with maximal common subtrees. We then solve the problem using simple replicator dynamics from evolutionary game theory. Experiments on hundreds of uniformly random trees are presented. The results are impressive: despite the inherent inability of these simple dynamics to escape from local optima, they always returned a globally optimal solution.

N a letter to C. Huygens of 1679, G.W. Leibniz expressed his dissatisfaction with the standard coordinate treatment of geometric figures and maintained that we need yet another kind of analysis, geometric or linear, which deals directly with position, as algebra deals with magnitude (1). In fact, Leibniz initiated the study of the so-called geometry of positions (geometria situs) which, as L. Euler clearly put it in his famous 1736 Konigsberg bridges paper which had to mark the beginning of graph theory, concerned only with the determination of position, and its properties; it does not involve measurements nor calculations made with them (2). After about two centuries, this study developed into two of the richest branches of modern mathematics: graph theory and combinatorial topology. Mutatis mutandis, an analogous discontent is nowadays being felt among many researchers working in computer vision, a field that is currently dominated by purely geometric methods, who are increasingly making use of sophisticated graph-theoretic concepts, results, and algorithms. Indeed, graphs have long been an important tool in computer vision, especially because of their representational power and flexibility. However, there is now a renewed and growing interest toward explicitly formulating computer vision problems as graph problems. This is particularly advanta- geous because it allows vision problems to be cast in a pure, abstract setting with solid theoretical underpinnings and also permits access to the full arsenal of graph algorithms developed in computer science and operations research. Graph-theoretic problems which have proven to be relevant to computer vision include maximum flow, minimum spanning tree, maximum clique, shortest path, maximal common subtree/subgraph, etc. In addition, a number of fundamental techniques that were designed in the graph algorithms community have recently been applied to computer vision problems. Examples include spectral

The matching of hierarchical relational structures is of significant interest in computer vision and pattern recognition. We have recently introduced a new solution to this problem, based on a maximum clique formulation in an (derived) "association graph". This allows us to exploit the full arsenal of clique finding algorithms developed in the algorithm community. However, thus far we have only focussed on one-to-one correspondences (isomorphisms), which appears to be too strict a requirement for many vision problems. In this paper we provide a generalization of the association graph framework to handle many-to-one correspondences. We define a notion of an /spl epsiv/-homomorphism (a many-to-one mapping) between attributed trees, and provide a method of constructing a weighted association graph where maximal weight cliques are in one-to-one correspondence with maximal similarity subtree homomorphisms. We then solve the problem by using replicator dynamical systems from the evolutionary game theory.

We propose a new heuristic for approximating the maximum clique problem based on a recently introduced deterministic annealing algorithm which generalizes Waugh and Westewelt's cluster-competitive net. The approach is centered around a fundamental result proved by Motzkin and Straus in the mid-1960s, and recently expanded in various ways, which allows us to formulate the maximum clique problem in terms of a linearly constrained quadratic program. Preliminary experiments on random as well as standard benchmark graphs are presented which demonstrate the validity of the approach.

Given an undirected graph with weights on the vertices, the maximum weight clique problem (MWCP) is to find a subset of mutually adjacent vertices (i.e., a clique) having the largest total weight. This is a generalization of the classical problem of finding the maximum cardinality clique of an unweighted graph, which arises as a special case of the MWCP when all the weights associated to the vertices are equal. The problem is known to be NP-hard for arbitrary graphs and, according to recent theoretical results, so is the problem of approximating it within a constant factor. Although there has recently been much interest around neural-network algorithms for the unweighted maximum clique problem, no effort has been directed so far toward its weighted counterpart. In this paper, we present a parallel, distributed heuristic for approximating the MWCP based on dynamics principles developed and studied in various branches of mathematical biology. The proposed framework centers around a recently introduced continuous characterization of the MWCP which generalizes an earlier remarkable result by Motzkin and Straus. This allows us to formulate the MWCP (a purely combinatorial problem) in terms of a continuous quadratic programming problem. One drawback associated with this formulation, however, is the presence of "spurious" solutions, and we present characterizations of these solutions. To avoid them we introduce a new regularized continuous formulation of the MWCP inspired by previous works on the unweighted problem, and show how this approach completely solves the problem. The continuous formulation of the MWCP naturally maps onto a parallel, distributed computational network whose dynamical behavior is governed by the so-called replicator equations. These are dynamical systems introduced in evolutionary game theory and population genetics to model evolutionary processes on a macroscopic scale.We present theoretical results which guarantee that the solutions provided by our clique finding replicator network are actually the ones being sought. Extensive experiments on both randomly generated and standard benchmark graphs have been conducted, and the results obtained confirm the effectiveness of the proposed approach.

We present a new energy-minimization framework for the graph isomorphism problem that is based on an equivalent maximum clique formulation. The approach is centered around a fundamental result proved by Motzkin and Straus in the mid-1960s, and recently expanded in various ways, which allows us to formulate the maximum clique problem in terms of a standard quadratic program. The attractive feature of this formulation is that a clear one-to-one correspondence exists between the solutions of the quadratic program and those in the original, combinatorial problem. To solve the program we use the so-called replicator equations--a class of straightforward continuous- and discrete-time dynamical systems developed in various branches of theoretical biology. We show how, despite their inherent inability to escape from local solutions, they nevertheless provide experimental results that are competitive with those obtained using more elaborate mean-field annealing heuristics.

It is well-known that the problem of matching two relational structures can be posed as an equivalent problem of finding a maximal clique in a (derived) "association graph." However, it is not clear how to apply this approach to computer vision problems where the graphs are hierarchically organized, i.e., are trees, since maximal cliques are not constrained to preserve the partial order. We provide a solution to the problem of matching two trees by constructing the association graph using the graph-theoretic concept of connectivity. We prove that, in the new formulation, there is a one-to-one correspondence between maximal cliques and maximal subtree isomorphisms. This allows us to cast the tree matching problem as an indefinite quadratic program using the Motzkin-Straus theorem, and we use "replicator" dynamical systems developed in theoretical biology to solve it. Such continuous solutions to discrete problems are attractive because they can motivate analog and biological implementations. The framework is also extended to the matching of attributed trees by using weighted association graphs. We illustrate the power of the approach by matching articulated and deformed shapes described by shock trees.

The matching of relational structures is a problem that pervades computer vision and pattern recognition research. During the past few decades, two radically distinct approaches have been pursued to tackle it. The first views the matching problem as one of explicit search in state-space. The most popular method within this class consists of transforming it in the equivalent problem of finding a large maximal clique in a derived "association graph." In the second approach, the relational matching problem is viewed as one of energy minimization. In this paper we provide a unifying framework for relational structure matching which does unify the two existing approaches. The work is centered around a remarkable result proved by Motzkin and Straus (1965) which allows us to formulate the maximum clique problem in terms of a continuous optimization problem. We present a class of continuous- and discrete-time "replicator" dynamical systems developed in evolutionary game theory and show how they can naturally be employed to solve our relational matching problem. Experiments are presented which demonstrate the effectiveness of the proposed approach.

The problem of determining the proper size of an artificial neural network is recognized to be crucial, especially for its practical implications in such important issues as learning and generalization. One popular approach for tackling this problem is commonly known as pruning and it consists of training a larger than necessary network and then removing unnecessary weights/nodes. In this paper, a new pruning method is developed, based on the idea of iteratively eliminating units and adjusting the remaining weights in such a way that the network performance does not worsen over the entire training set. The pruning problem is formulated in terms of solving a system of linear equations, and a very efficient conjugate gradient algorithm is used for solving it, in the least-squares sense. The algorithm also provides a simple criterion for choosing the units to be removed, which has proved to work well in practice. The results obtained over various test problems demonstrate the effectiveness of the proposed approach.

The exponential correlation associative memory (ECAM) is a recurrent neural network model which has large storage capacity. Our aim in this paper is to show how the ECAM model can be entirely derived within a Bayesian framework, thereby providing more insight into the behaviour of this algorithm. The framework for our study is a novel relaxation method, which involves direct probabilistic modelling of the pattern corruption mechanism. The parameter of this model is the memoryless probability of error on nodes of the network. This bit-error probability is not only important for the interpretation of the ECAM model, but also allows us to understand some more general properties of Bayesian pattern reconstruction by relaxation. To study the dynamical behaviour of our relaxation model, we use the Hamming distance picture of Kanerva which allows us to understand how the bit-error probability evolves during the relaxation process. We also derive a parameter-free expression for the storage capacity of the model which, like a previous result of Chiueh and Goodman, scales exponentially with the number of nodes in the network.

We address the problem of training relaxation labeling processes, a popular class of parallel iterative procedures widely employed in pattern recognition and computer vision. The approach discussed here is based on a theory of consistency developed by Hummel and Zucker (1983) and contrasts with a previously introduced learning strategy which can be regarded as heteroassociative, i.e. what is actually learned is the association between patterns rather than the patterns themselves. The proposed learning model is instead autoassociative and involves making a set of training patterns consistent in the sense rigorously defined by Hummel and Zucker; this implies that they become local attractors of the relaxation labeling dynamical system. The learning problem is formulated in terms of solving a system of linear inequalities, and a straightforward iterative algorithm is presented to accomplish this. The learning model described here allows one to view the relaxation labeling process as a kind of asymmetric associative memory, the effectiveness of which is demonstrated experimentally.

Presents some new results which demonstrate that, despite its heuristic and simple-minded derivation, the familiar nonlinear relaxation labeling algorithm of Rosenfeld et al. (1976) is in fact intimately related with a well-established theory of constraint satisfaction developed by Hummel and Zucker (1983). In particular, it is shown that, when a certain symmetry condition is met, the algorithm possesses a Liapunov function which turns out to be (the negative of) a well-known consistency measure. This follows almost immediately from a powerful result of Baum and Eagon (1967) developed in the context of Markov chain theory. These properties are also shown to naturally generalize to higher-order relaxation schemes. Some applications of the results presented here are finally outlined.

Relaxation labeling processes have been widely used in many different domains including image processing, pattern recognition, and artificial intelligence. They are iterative procedures that aim at reducing local ambiguities and achieving global consistency through a parallel exploitation of contextual information, which is quantitatively expressed in terms of a set of "compatibility coefficients." The problem of determining compatibility coefficients has received a considerable attention in the past and many heuristic, statistical-based methods have been suggested. In this paper, the authors propose a rather different viewpoint to solve this problem: they derive them attempting to optimize the performance of the relaxation algorithm over a sample of training data; no statistical interpretation is given: compatibility coefficients are simply interpreted as real numbers, for which performance is optimal. Experimental results over a novel application of relaxation are given, which prove the effectiveness of the proposed approach.>

The problem of determining compatibility coefficients for relaxation labeling processes has received considerable attention and a number of different methods have been suggested. The authors propose a method developed within an optimization framework. After formulating the problem of determining the coefficients as a nonlinear programming problem, they develop a gradient-descent algorithm for solving it. Results on an application of relaxation processes are given.>