Canada

In this paper, we present an approximate distance oracle for fault-tolerant Euclidean spanners. An $f$-fault-tolerant Euclidean $t$-spanner for a point set $V \subset \mathbb{R}^d$ is a graph $G=(V,E)$ where, for any two points $p$ and $q$ in $V$ and a set $F$ of $f$ vertices of $V$, the distance between $p$ and $q$ in $G-F$ is at most $t$ times their Euclidean distance. Given an $f$-fault-tolerant 
Euclidean $t$-spanner $G$ and a constant $\varepsilon$ for constants $t$ and $f$,
we can construct a data structure of size $O(m\log n)$ in $O(m\log^2 n)$ time so that an $(1+\varepsilon)$-approximate distance in $G-F$ between $s$ and $s&#39;$ can be computed in constant time for any two vertices $s$ and $s&#39;$ and a set $F$ of $f$ failed vertices. Additionally, we can construct a data structure of size $O(m\log n\log\log n)$ in $O(m^2\log^2 n)$ so that an $(1+\varepsilon)$-approximate shortest path in $G-F$ between $s$ and $s&#39;$ can be compute in $O(\log^2 n\log\log n)$ time for any two vertices $s$ and $s&#39;$ and a set $F$ of failed vertices.

AAAI 2024

Approximate Distance Oracle for Fault-Tolerant Geometric Spanners

and scheduling (prs) -> prs: routing

routing

planning

In this paper, we present an approximate distance oracle for fault-tolerant Euclidean spanners. An $f$-fault-tolerant Euclidean $t$-spanner for a point set $V \subset \mathbb{R}^d$ is a graph $G=(V,E)$ where, for any two points $p$ and $q$ in $V$ and a set $F$ of $f$ vertices of $V$, the distance between $p$ and $q$ in $G-F$ is at most $t$ times their Euclidean distance. Given an $f$-fault-tolerant 
Euclidean $t$-spanner $G$ and a constant $\varepsilon$ for constants $t$ and $f$,
we can construct a data structure of size $O(m\log n)$ in $O(m\log^2 n)$ time so that an $(1+\varepsilon)$-approximate distance in $G-F$ between $s$ and $s'$ can be computed in constant time for any two vertices $s$ and $s'$ and a set $F$ of $f$ failed vertices. Additionally, we can construct a data structure of size $O(m\log n\log\log n)$ in $O(m^2\log^2 n)$ so that an $(1+\varepsilon)$-approximate shortest path in $G-F$ between $s$ and $s'$ can be compute in $O(\log^2 n\log\log n)$ time for any two vertices $s$ and $s'$ and a set $F$ of failed vertices.

technical paper

We are pleased to announce the Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24), which will be held in Vancouver, British Columbia at the Vancouver Convention Centre – West Building from 20-27 February, 2024.

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-24 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

We expect for AAAI-24 to be an in-person conference – one author of all accepted papers will be expected to present work in person unless there are exceptional circumstances that prevent this.<br><br><br><br>

In order to access the AAAI-24 event page you need to register [here](https://aaai.org/aaai-conference/registration/)

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. 

The ability of model quantization with arbitrary bit-width to dynamically meet diverse bit-width requirements during runtime has attracted significant attention. Recent research has focused on optimizing large-scale training methods to achieve robust bit-width adaptation, which is a time-consuming process requiring hundreds of GPU hours. Furthermore, converting bit-widths requires recalculating statistical parameters of the norm layers, thereby impeding real-time switching of the bit-width. To overcome these challenges, we propose an efficient Post-Training Multi-bit Quantization (PTMQ) scheme that requires only a small amount of calibration data to perform block-wise reconstruction of multi-bit quantization errors. It eliminates the influence of statistical parameters by fusing norm layers, and supports real-time switching bit-widths in uniform quantization and mixed-precision quantization. To improve quantization accuracy and robustness, we propose a Multi-bit Feature Mixer technique (MFM) for fusing features of different bit-widths to enhance robustness across varying bit-widths. Moreover, we introduced the Group-wise Distillation Loss (GD-Loss) to enhance the correlation between different bit-width groups and further improve the overall performance of PTMQ. Extensive experiments demonstrate that PTMQ achieves comparable performance to existing state-of-the-art post-training quantization methods, while optimizing it speeds up by 100$\times$ compared to recent multi-bit quantization works. Code can be available at https://github.com/xuke225/PTMQ.

PTMQ: Post-training Multi-Bit Quantization of Neural Networks

Deep learning models have the ability to extract empirical knowledge from large-scale datasets. However, the sharing of data has become increasingly challenging due to concerns regarding data copyright and privacy. Consequently, this hampers the effective transfer of knowledge from existing data to novel downstream tasks and concepts. Zero-shot learning (ZSL) approaches aim to recognize unseen classes by transferring semantic knowledge learned from seen classes. However, traditional ZSL methods often require access to real images from seen classes and rely on manually annotated attributes, which presents challenges in terms of data restrictions and model scalability. To this end, this paper tackles a challenging and practical problem dubbed as data-free zero-shot learning, where only the CLIP-based seen classes data pre-trained classifier is available for zero-shot classification. Specifically, we propose a generic framework for data-free zero-shot learning, which consists of three main components. Firstly, to recover the virtual features of the seen data, we model the CLIP features of seen class images as samples from a von Mises-Fisher (vMF) distribution based on the pre-trained classifier. Secondly, eliminates the need for manual attribute annotations, we leverage the text features of CLIP as low-cost semantic information and propose
a feature-language prompt tuning method to further align the virtual image features and textual features. Thirdly, we train a conditional generative model using the well-aligned virtual image features and corresponding semantic text features, which enables us to generate features for unseen classes and achieve zero-shot classification. Our framework has been evaluated on five commonly used benchmarks for zero-shot learning, as well as 11 benchmarks for the base-to-new generalization. The results demonstrate the superiority and effectiveness of our approach.

Data-Free Generalized Zero-Shot Learning | VIDEO

Recently, many carefully designed graph representation learning methods have achieved impressive performance on either strong heterophilic or homophilic graphs, but not both. Therefore, they are incapable of generalizing well across real-world graphs with different levels of homophily. This is attributed to their neglect of homophily in heterophilic graphs, and vice versa. In this paper, we propose a two-fold filtering mechanism to mine homophily in heterophilic graphs, and vice versa. In particular, we extend the graph heat equation to perform heterophilic aggregation of global information from a long distance. The resultant filter can be exactly approximated by the Possion-Charlier (PC) polynomials. To further exploit information at multiple orders, we introduce a powerful graph convolution PC-Conv and its instantiation PCNet for the node classification task. 
Compared to the state-of-the-art GNNs, PCNet shows competitive performance on well-known homophilic and heterophilic graphs.

PC-Conv: Unifying Homophily and Heterophily with Two-Fold Filtering

The goal of 3D mesh watermarking is to embed the message in 3D meshes that can withstand various attacks imperceptibly and reconstruct the message accurately from watermarked meshes. The watermarking algorithm is supposed to withstand multiple attacks, and the complexity should not grow significantly with the mesh size. Unfortunately, previous methods are less robust against attacks and lack of adaptability. In this paper, we propose a robust and adaptable deep 3D mesh watermarking Deep3DMark that leverages attention-based convolutions in watermarking tasks to embed binary messages in vertex distributions without texture assistance. Furthermore, our Deep3DMark exploits the property that simplified meshes inherit similar relations from the original ones, where the relation is the offset vector directed from one vertex to its neighbor. By doing so, our method can be trained on simplified meshes but remains effective on large size meshes (size adaptable) and unseen categories of meshes (geometry adaptable). Extensive experiments demonstrate our method remains efficient and effective even if the mesh size is 190× increased. Under mesh attacks, Deep3DMark achieves 10%∼50% higher accuracy than traditional methods, and 2× higher SNR and 8% higher accuracy than previous DNN-based methods.

Rethinking Mesh Watermark: Towards Highly Robust and Adaptable Deep 3D Mesh Watermarking

Image registration plays a crucial role in histological image analysis, encompassing tasks like multi-modality fusion and disease grading. 
Traditional registration methods optimize objective functions for each image pair, yielding reliable accuracy but demanding heavy inference burdens.
Recently, learning-based registration methods utilize networks to learn the optimization process during training and apply a one-step forward process during testing. 
While these methods offer promising registration performance with reduced inference time, they remain sensitive to appearance variances and local structure changes commonly encountered in histological image registration scenarios.
In this paper, for the first time, we propose a novel test-time adaptation method for histological image registration, aiming to improve the generalization ability of learning-based methods. 
Specifically, we design two operations, style guidance and shape guidance, for the test-time adaptation process. 
The former leverages style representations encoded by feature statistics to address the issue of appearance variances, while the latter incorporates shape representations encoded by HOG features to improve registration accuracy in regions with structural changes.
Furthermore, we consider the continuity of the model during the test-time adaptation process.
Different from the previous methods initialized by a given trained model, we introduce a smoothing strategy to leverage historical models for better generalization. 
We conduct experiments with several representative learning-based backbones on the public histological dataset, demonstrating the superior registration performance of our test-time adaptation method.

Test-Time Adaptation via Style and Structure Guidance for Histological Image Registration

In recent years, following the success of text guided image generation, text guided 3D generation has gained increasing attention among researchers. Dreamfusion is a notable approach that enhances generation quality by utilizing 2D text guided diffusion models and introducing SDS loss, a technique for distilling 2D diffusion model information to train 3D models. However, the SDS loss has two major limitations that hinder its effectiveness. Firstly, when given a text prompt, the SDS loss struggles to produce diverse content. Secondly, during training, SDS loss may cause the generated content to overfit and collapse, limiting the model's ability to learn intricate texture details. To overcome these challenges, we propose a novel approach called Noise Recalibration algorithm. By incorporating this technique, we can generate 3D content with significantly greater diversity and stunning details. Our approach offers a promising solution to the limitations of SDS loss.

Diverse and Stable 2D Diffusion Guided Text to 3D Generation with Noise Recalibration

Open-vocabulary video visual relationship detection aims to extend video visual relationship detection beyond annotated categories by detecting unseen relationships between objects in videos. 
Recent progresses in open-vocabulary perception, primarily driven by large-scale image-text pre-trained models like CLIP, have shown remarkable success in recognizing novel objects and semantic categories. 
However, directly applying CLIP-like models  to video visual relationship detection encounters significant challenges due to the substantial gap between images and video object relationships.
To address this challenge, we propose a multi-modal prompting method that adapts CLIP well to open-vocabulary video visual relationship detection by prompt-tuning on both visual representation and language input.
Specifically, we enhance the image encoder of CLIP by using spatio-temporal visual prompting to capture spatio-temporal contexts, thereby making it suitable for object-level relationship representation in videos.
Furthermore, we propose visual-guided language prompting to leverage CLIP's comprehensive semantic knowledge for discovering unseen relationship categories, thus facilitating recognizing novel video relationships.
Extensive experiments on two public datasets,  VidVRD and  VidOR, demonstrate the effectiveness of our method, especially achieving a significant gain of nearly 10\% in mAP on novel relationship categories on the VidVRD dataset.

Multi-Modal Prompting for Open-Vocabulary Video Visual Relationship Detection

Fraud detection on multi-relation graphs aims to identify fraudsters in graphs. Graph Neural Network (GNN) models leverage graph structures to pass messages from neighbors to the target nodes, thereby enriching the representations of those target nodes. However, feature and structural inconsistency in the graph, owing to fraudsters' camouflage behaviors, diminish the suspiciousness of fraud nodes which hinders the effectiveness of GNN-based models. In this work, we propose DiG-In-GNN, Discriminative Feature Guided GNN against Inconsistency, to dig into graphs for fraudsters. Specifically, we use multi-scale contrastive learning from the perspective of the neighborhood subgraph where the target node is located to generate guidance nodes to cope with the feature inconsistency. Then, guided by the guidance nodes, we conduct fine-grained neighbor selection through reinforcement learning for each neighbor node to precisely filter nodes that can enhance the message passing and therefore alleviate structural inconsistency. Finally, the two modules are integrated together to obtain discriminable representations of the nodes. Experiments on three fraud detection datasets demonstrate the superiority of the proposed method DiG-In-GNN, which obtains up to 20.73% improvement over previous state-of-the-art methods. Our code can be found at https://github.com/GraphBerry/DiG-In-GNN.

DiG-In-GNN: Discriminative Feature Guided GNN-based Fraud Detector against Inconsistencies in Multi-Relation Fraud Graph

Identifying speakers of quotations in narratives is an important task in literary analysis, with challenging scenarios including the out-of-domain inference for unseen speakers, and non-explicit cases where there are no speaker mentions in surrounding context. 
In this work, we propose a simple and effective approach SIG, a generation-based method that verbalizes the task and quotation input based on designed prompt templates, which also enables easy integration of other auxiliary tasks that further bolster the speaker identification performance. The prediction can either come from direct generation by the model, or be determined by the highest generation probability of each speaker candidate. Based on our approach design, SIG supports out-of-domain evaluation, and achieves open-world classification paradigm that is able to accept any forms of candidate input. We perform both cross-domain evaluation and in-domain evaluation on PDNC, the largest dataset of this task, where empirical results suggest that SIG outperforms previous baselines of complicated designs, as well as the zero-shot ChatGPT, especially excelling at those hard non-explicit scenarios by up to 17% improvement. Additional experiments on another dataset WP further corroborate the efficacy of SIG.

SIG: Speaker Identification in Literature via Prompt-Based Generation

Multistream classification poses significant challenges due to the necessity for rapid adaptation in dynamic streaming processes with concept drift. Despite the growing research outcomes in this area, there has been a notable oversight regarding the temporal dynamic relationships between these streams, leading to the issue of negative transfer arising from irrelevant data. In this paper, we propose a novel Online Boosting Adaptive Learning (OBAL) method that effectively addresses this limitation by adaptively learning the dynamic correlation among different streams. Specifically, OBAL operates in a dual-phase mechanism, in the first of which we design an Adaptive COvariate Shift Adaptation (AdaCOSA) algorithm to construct an initialized ensemble model using archived data from various source streams, thus mitigating the covariate shift while learning the dynamic correlations via an adaptive re-weighting strategy. During the online process, we employ a Gaussian Mixture Model-based weighting mechanism, which is seamlessly integrated with the acquired correlations via AdaCOSA to effectively handle asynchronous drift. This approach significantly improves the predictive performance and stability of the target stream. We conduct comprehensive experiments on several synthetic and real-world data streams, encompassing various drifting scenarios and types. The results clearly demonstrate that OBAL achieves remarkable advancements in addressing multistream classification problems by effectively leveraging positive knowledge derived from multiple sources.

Approximate Distance Oracle for Fault-Tolerant Geometric Spanners

Downloads

Next from AAAI 2024

PTMQ: Post-training Multi-Bit Quantization of Neural Networks

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Approximate Distance Oracle for Fault-Tolerant Geometric Spanners

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAAI 2024

PTMQ: Post-training Multi-Bit Quantization of Neural Networks

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES

Downloads