Graph Neural Networks (GNNs) with equivariant properties have achieved significant success in modeling complex dynamic systems and molecular properties. However, their expressiveness ability is limited by: (1) Existing methods often overlook the over-smoothing issue caused by traditional GNN models, as well as the gradient explosion or vanishing problems in deep GNNs. (2) Most models operate on first-order information, neglecting that the real world often consists of second-order systems, which further limits the model’s representation capabilities. To address these issues, we propose the Dual Second-order Equivariant Graph Ordinary (DuSEGO) Differential Equation for equivariant representation. Specifically, DuSEGO applies the dual second-order equivariant graph ordinary differential equations (Graph ODEs) to both graph embeddings and node coordinates simultaneously. Theoretically, we first prove that DuSEGO maintains the equivariant property. Furthermore, we provide theoretical insights showing that DuSEGO effectively alleviates the over-smoothing problem in both feature representation and coordinate update. Additionally, we demonstrate that the proposed DuSEGO mitigates the exploding and vanishing gradients problem, facilitating the training of deep multi-layer GNNs. Extensive experiments on benchmark datasets validate the superiority of the proposed DuSEGO compared to baselines.

Graph classification is a pivotal challenge in machine learning, especially within the realm of graph-based data, given its importance in numerous real-world applications such as social network analysis, recommendation systems, and bioinformatics. Despite its significance, graph classification faces several hurdles, including adapting to diverse prediction tasks, training across multiple target domains, and handling small-sample prediction scenarios. Current methods often tackle these challenges individually, leading to fragmented solutions that lack a holistic approach to the overarching problem. In this paper, we propose an algorithm aimed at addressing the aforementioned challenges. By incorporating insights from various types of tasks, our method aims to enhance adaptability, scalability, and generalizability in graph classification. Motivated by the recognition that the underlying subgraph plays a crucial role in GNN prediction, while the remainder is task-irrelevant, we introduce the Core Knowledge Learning (CKL) framework for graph adaptation and scalability learning. CKL comprises several key modules, including the core subgraph knowledge submodule, graph domain adaptation module, and few-shot learning module for downstream tasks. Each module is tailored to tackle specific challenges in graph classification, such as domain shift, label inconsistencies, and data scarcity. By learning the core subgraph of the entire graph, we focus on the most pertinent features for task relevance. Consequently, our method offers benefits such as improved model performance, increased domain adaptability, and enhanced robustness to domain variations. Experimental results demonstrate significant performance enhancements achieved by our method compared to state-of-the-art approaches. Specifically, our method achieves notable improvements in accuracy and generalization across various datasets and evaluation metrics, underscoring its effectiveness in addressing the challenges of graph classification.

Graph neural networks (GNNs) have achieved impressive impressions for graph-related tasks. However, most GNNs are primarily studied under the cases of signal domain with supervised training, which requires abundant task-specific labels and is difficult to transfer to other domains. There are few works focused on domain adaptation for graph node classification. They mainly focused on aligning the feature space of the source and target domains, without considering the feature alignment between different categories, which may lead to confusion of classification in the target domain. However, due to the scarcity of labels of the target domain, we cannot directly perform effective alignment of categories from different domains, which makes the problem more challenging. In this paper, we present the Spectral Augmentation for Graph Domain Adaptation (SA-GDA) for graph node classification. First, we observe that nodes with the same category in different domains exhibit similar characteristics in the spectral domain, while different classes are quite different. Following the observation, we align the category feature space of different domains in the spectral domain instead of aligning the whole features space, and we theoretical proof the stability of proposed SA-GDA. Then, we develop a dual graph convolutional network to jointly exploits local and global consistency for feature aggregation. Last, we utilize a domain classifier with an adversarial learning submodule to facilitate knowledge transfer between different domain graphs. Experimental results on a variety of publicly available datasets reveal the effectiveness of our SA-GDA.

Data is becoming the world's most valuable asset and the ultimate renewable resource. This phenomenon has led to online personal data markets where data owners and collectors engage in the data sale and purchase. From the collector's standpoint, a key question is how to set a proper pricing rule that brings profitable tradings. One feasible solution is to set the price slightly above the owner's data cost. Nonetheless, data cost is generally unknown by the collector as being the owner's private information. To bridge this gap, we propose a novel learning algorithm, modified stochastic gradient descent (MSGD) that infers the owner's cost model from her interactions with the collector. To protect owners’ data privacy during trading, we employ the framework of local differential privacy (LDP) that allows owners to perturb their genuine data and trading behaviors. The vital challenge is how the collector can derive the accurate cost model from noisy knowledge gathered from owners. For this, MSGD relies on auxiliary parameters to correct biased gradients caused by noise. We formally prove that the proposed MSGD algorithm produces a sublinear regret of$\mathcal {O}(T^{\frac{5}{6}}\sqrt{\log (T^{\frac{1}{3}})})$. The effectiveness of our design is further validated via a series of in-person experiments that involve 30 volunteers.

Mobile crowdsourcing has emerged as a promising paradigm that applies the principle of crowdsourcing to perform tasks of mobility requirement. Due to the openness of mobile crowdsourcing, workers may yield low-quality task answers. To alleviate this problem, substantial efforts have been devoted to elicit truthful data from workers. On the other hand, to facilitate task assignment, workers are required to upload the platform their profiles, such as locations and expertise. Therefore, task assignment outcomes and thus mobile crowdsourcing service accuracy is subject to the quality of workers’ self-reported profiles. In this paper, we leverage incentive design to motivate workers to honestly reveal both task answers and their profiles. The challenge is to design one incentive payment for truth elicitation in two kinds of submissions. For this, we first derive the sufficient and necessary conditions for answer truthfulness and profile truthfulness separately. We then construct an incentive optimization problem that incorporates these conditions as constraints. Its optimal solution lists the payment to each worker that elicits answers and profiles jointly. Our proposed mechanism, with a formally proved bounded approximation ratio, ensures that truth-telling is a Bayesian Nash equilibrium. We prototype the mechanism and conduct a series of experiments that involve 30 volunteers to validate the efficacy and efficiency of the proposed mechanism.

In the wake of the Web 2.0, crowdsourcing has emerged as a promising approach to maintain a flexible workforce for human intelligence tasks. To stimulate worker participation, many reverse auction-based incentive mechanisms have been proposed. Designing auctions that discourage workers from cheating and instead encouraging them to reveal their true cost information has drawn significant attention. However, the existing efforts have been focusing on tackling individual cheating misbehaviors, while the scenarios that workers strategically form collusion coalitions and rig their bids together to manipulate auction outcomes have received little attention. To fill this gap, in this work we develop a$(t,p)$-collusion resistant scheme that ensures no coalition ofweighted cardinality$t$can improve its group utility by coordinating the bids at a probability of$p$. This paper takes into account the unique features of crowdsourcing, such as diverse worker types and reputations, in the design. The proposed scheme can suppress a broad spectrum of collusion strategies. Besides, desirable properties, including$p$-truthfulness and$p$-individual rationality, are also achieved. To provide a comprehensive evaluation, we first analytically prove our scheme's collusion resistance and then experimentally verify our analytical conclusion using a real-world dataset. Our experimental results show that the baseline scheme, where none of the critical properties is guaranteed, costs up to 20.1 times the optimal payment in an ideal case where no collusion exists, while our final scheme is merely 4.9 times the optimal payment.

Mobile crowd sensing (MCS) arises as a promising data collection paradigm that leverages the power of ubiquitous mobile devices to acquire rich information regarding their surrounding environment. In many location-based sensing tasks, workers are required to associate their sensing reports with corresponding geographic coordinates. Such information leaves a trail of worker's historical location record which thus poses a severe threat to their location privacy. On the other hand, individual workers may perceive location privacy differently. Instead of following conventional solutions that aim to perfectly hide user privacy, this paper adopts a novel alternative approach. Auser-centriclocationprivacytrading framework, called ULPT, is constructed to facilitate location privacy trading between workers and the platform. Each worker can decide how much location privacy to disclose to the platform in an MCS task based on its own location privacy leakage budget$\xi$. The higher$\xi$is, the more privacy its reported location discloses. Accordingly, it receives higher payment from the platform as compensation. Besides, ULPT enables the platform to select a suitable set of winning workers to achieve desirable MCS service accuracy while taking into account of its budget limit and worker privacy requirements. For this purpose, a heuristic algorithm is devised with a bounded optimality gap. As formally proved in this manuscript, ULPT guarantees a series of nice properties, including$\xi$-privacy,$(\alpha, \beta)$-accuracy,budget feasibility. Moreover, both rigorous theoretical analysis and extensive simulations are conducted to evaluate tradeoffs among these three.

Blockchain, an emerging decentralized but trusted system, has been applied in many applications, such as the Internet of Things (IoT), supply chains, and smart grid. However, due to the large amount of computing and storage resources blockchain typically demands, its wide deployment is faced with the sustainability issue. To resolve this issue, a viable solution is to empower the IoT system with fog computing that can offload the computation-demanding tasks. Due to varieties of mining tasks and heterogeneous resource capabilities at fog nodes (FNs), it is not an easy task to schedule mining tasks and manages resource allocation among FNs of conflicting interests and independent IoT devices in a distributed manner. In this article, under the framework of matching theory, we design a distributed matching mechanism to maximize the social welfare of resource-restricted FNs while guaranteeing various mining requirements of FNs. Besides, we also provide formal proof regarding the convergence and computational complexity of a distributed matching algorithm (DMA). Finally, we verify that DMA not only improves the social welfare of FNs but also reduces the mining latency compared with the existing algorithms through extensive simulations.

Mobile crowd sensing (MCS) is a technique where sensing tasks are outsourced to a crowd of mobile users. Since most of sensing tasks are location-dependent, workers are required to embed their locations into sensing reports, which incurs location privacy vulnerabilities. Realizing that workers perceive their location privacy differently, in this work we construct an auction-based trading market, facilitating location privacy trading between workers and the platform. Each worker can decide how much location privacy to disclose to the platform based on its own location privacy leakage budget $\xi$. The higher $\xi$ is, the less secrecy its reported location preserves. As a result, it receives higher payment from the platform as a compensation to its privacy loss. Besides, our mechanism enables the platform to select a suitable set of winning workers to achieve desirable service accuracy. For this purpose, a heuristic algorithm is devised, with polynomial-time complexity and bounded optimality gap. As formally proved in this manuscript, our proposed mechanism guarantees a series of nice properties, including $\xi$-privacy, $(\alpha,\beta)$accuracy, and budget feasibility.