Large-scale map construction is foundational for critical applications such as autonomous driving and navigation systems. Traditional large-scale map construction approaches mainly rely on costly and inefficient special data collection vehicles and labor-intensive annotation processes. While existing satellite-based methods have demonstrated promising potential in enhancing the efficiency and coverage of map construction, they exhibit two major limitations: (1) inherent drawbacks of satellite data (e.g., occlusions, outdatedness) and (2) inefficient vectorization from perception-based methods, resulting in discontinuous and rough roads that require extensive post-processing. This paper presents a novel generative framework, UniMapGen, for large-scale map construction, offering three key innovations: (1) representing lane lines as discrete sequence and establishing an iterative strategy to generate more complete and smooth map vectors than traditional perception-based methods. (2) proposing a flexible architecture that supports multi-modal inputs, enabling dynamic selection among BEV, PV, and text prompt, to overcome the drawbacks of satellite data. (3) developing a state update strategy for global continuity and consistency of the constructed large-scale map. UniMapGen achieves state-of-the-art performance on the OpenSatMap dataset. Furthermore, UniMapGen can infer occluded roads and predict roads missing from dataset annotations.

For complex networks such as the Web, the Network Dismantling (ND) problem, which asks for the minimum-cost removal of nodes that destroys the giant connected component in the network, is significant in system robustness and misinformation containment. In this paper, we propose a heuristic algorithm, IG+, which is based on reverse dismantling and incorporates novel optimizations. Besides, we design two dynamic algorithms, CCRT-ins and CCRT-rem, employing tree-like indexes to update dismantling results efficiently. Experiments show that our methods outperform state-of-the-art approaches in both effectiveness and efficiency, and can dismantle 10-million-scale networks at arbitrary granularity in a few minutes.

Modern large-scale graph processing faces a critical challenge: conventional adjacency lists incur excessive L3 cache misses due to irregular memory access. We introduce GraphTwin, a hybrid graph representation system combining: (1) Cache-optimized k -bit vectors (termed GT-vectors, 64 bits per vertex), where each bit indicates vertex membership in a precomputed independent set; and (2) Memory-resident adjacency lists for exact verification of queries unresolved by GT-vectors. This dual-component design enables 95% of negative edge queries, which are dominant in sparse graphs, to be resolved in 1 CPU cycle via in-cache bitwise-AND operations, reducing latency from 54ns (adjacency list) to 18ns per query. Unresolved queries delegate to adjacency lists, guaranteeing zero false positives/negatives. Crucially, GT-vectors scales linearly with vertex count ( k|V| bits ), decoupling the space overhead from edge density and minimizing cache dependency. For example, GT-vectors for a graph with |V|=10 7 vertices occupy 80MB, fitting entirely within modern CPU caches (e.g., AMD Ryzen 7 9800X3D's 96MB L3). We formalize the GT-vectors construction as an NP-hard and submodular optimization problem and introduce GTWICE, a linear-time heuristic algorithm that iteratively extracts diversified maximal independent sets to maximize non-edge coverage. Experiments on 15 graphs show that GraphTwin reduces L3 cache misses by 63% on average, achieves 6.2× speedup for edge queries and accelerates triangle counting and set inclusion by 1.7× and 5.4×, respectively. By optimizing cache residency and accelerating foundational primitives, GraphTwin addresses cache inefficiencies in graph processing, enabling fast graph queries without sacrificing exactness.

Image caption evaluation is a crucial task, which involves the semantic perception and matching of image and text. Good evaluation metrics aim to be fair, comprehensive, and consistent with human judge intentions. When humans evaluate a caption, they usually consider multiple aspects, such as whether it is related to the target image without distortion, how much image gist it conveys, as well as how fluent and beautiful the language and wording is. The above three different evaluation orientations can be summarized as fidelity, adequacy, and fluency. The former two rely on the image content, while fluency is purely related to linguistics and more subjective. Inspired by human judges, we propose a learning-based metric named FAIEr to ensure evaluating the fidelity and adequacy of the captions. Since image captioning involves two different modalities, we employ the scene graph as a bridge between them to represent both images and captions. FAIEr mainly regards the visual scene graph as the criterion to measure the fidelity. Then for evaluating the adequacy of the candidate caption, it high-lights the image gist on the visual scene graph under the guidance of the reference captions. Comprehensive experimental results show that FAIEr has high consistency with human judgment as well as high stability, low reference dependency, and the capability of reference-free evaluation.

Image-text retrieval of natural scenes has been a popular research topic. Since image and text are heterogeneous cross-modal data, one of the key challenges is how to learn comprehensive yet unified representations to express the multi-modal data. A natural scene image mainly involves two kinds of visual concepts, objects and their relationships, which are equally essential to image-text retrieval. Therefore, a good representation should account for both of them. In the light of recent success of scene graph in many CV and NLP tasks for describing complex natural scenes, we propose to represent image and text with two kinds of scene graphs: visual scene graph (VSG) and textual scene graph (TSG), each of which is exploited to jointly characterize objects and relationships in the corresponding modality. The image-text retrieval task is then naturally formulated as cross-modal scene graph matching. Specifically, we design two particular scene graph encoders in our model for VSG and TSG, which can refine the representation of each node on the graph by aggregating neighborhood information. As a result, both object-level and relationship-level cross-modal features can be obtained, which favorably enables us to evaluate the similarity of image and text in the two levels in a more plausible way. We achieve state-of-the-art results on Flickr30k and MS COCO, which verifies the advantages of our graph matching based approach for image-text retrieval.