论文检索

Yanxuan Wu, Haihan Duan, Xitong Li, Xiping Hu

Recent advances in Artificial Intelligence (AI) have introduced a popular paradigm in Machine Learning (ML) model development: pre-training and domain adaptation. As both closed-source developers and open-source community lead in pre-training foundation models, domain deployers face the dilemma about whether to use closed-source models via API access or to host open-source models on proprietary hardware. Using closed-source models incurs recurring costs, while hosting open-source models requires substantial hardware investments and may lead to potentially lagging advancements. This paper presents a game-theoretical model to examine the economic incentives behind the deployment choice and the impact of open-source engagement strategies on technological innovation. We find that deployers consistently opt for closed-source APIs when the open-source community engages reactively by maintaining a fixed performance ratio relative to closed-source advancements. However, open-source models can become preferable when a proactive open-source community produces high-performance models independently. Furthermore, we identify conditions under which the engagement and competitiveness of the open-source community can either foster or inhibit technological progress. These insights offer valuable implications for market regulation and the future of technology innovation.

Serena Wang 0001, Michael I. Jordan, Katrina Ligett, R. Preston McAfee

Online platforms and regulators face a continuing problem of designing effective evaluation metrics. While tools for collecting and processing data continue to progress, this has not addressed the problem of unknown unknowns, or fundamental informational limitations on part of the evaluator. To guide the choice of metrics in the face of this informational problem, we turn to the evaluated agents themselves, who may have more information about how to measure their own outcomes. We model this interaction as an agency game, where we ask: When does an agent have an incentive to reveal the observability of a metric to their evaluator? We show that an agent will prefer to reveal metrics that differentiate the most difficult tasks from the rest, and conceal metrics that differentiate the easiest. We further show that the agent can prefer to reveal a metric *garbled* with noise over both fully concealing and fully revealing. This indicates an economic value to privacy that yields Pareto improvement for both the agent and evaluator. We demonstrate these findings on data from online rideshare platforms.

Qiyuan Wang, Ruiling Xu, Shibo He, Randall Berry, Meng Zhang 0013

While federated learning enables intelligent services and personalized user experiences, it raises privacy concerns due to regulatory requirements and user demands for data protection. Federated unlearning offers a potential solution to these issues. However, despite increasing demand for its practical implementation driven by right-to-be-forgotten regulations, the economic implications of federated unlearning on user behavior and platform profitability remain underexplored, potentially hindering its adoption. In this paper, we formulate a set of contract design problems for both unlearning-disabled and unlearning-enabled scenarios. Challenges arise when the unlearning-enabled platform jointly designs compensation for both learning and unlearning to incentivize users' sequential decisions to balance the expected revenue and unlearning cost. We first conduct a questionnaire survey that reveals that federated unlearning increases users' willingness to participate in federated learning. We then provide a necessary condition for maximizing the surplus of an unlearning-enabled platform, enabling the point-wise decomposition for the optimal contract design problem, based on which we minimize the incentive cost and maximize the surplus for the platform. Our further analysis reveals that i) the incentive effects of unlearning grow quadratically with users' privacy sensitivity, and ii) enabling unlearning may even profit more than disabling it when the training cost increases at a faster rate than the probability of privacy leakage as effort levels rise. Our numerical results show that the platform's profitability is primarily influenced by users' privacy sensitivity. When users have a relatively high privacy sensitivity, enabling unlearning can significantly improve profitability.

Yongkang Guo, Yuqing Kong, Jialiang Liu

Rating aggregation plays a crucial role in various fields, such as product recommendations, hotel rankings, and teaching evaluations. However, traditional averaging methods can be affected by participation bias, where some raters do not participate in the rating process, leading to potential distortions. In this paper, we consider a robust rating aggregation task under the participation bias. We assume that raters may not reveal their ratings with a certain probability depending on their individual ratings, resulting in partially observed samples. Our goal is to minimize the expected squared loss between the aggregated ratings and the average of all underlying ratings (possibly unobserved) in the worst-case scenario. We focus on two settings based on whether the sample size (i.e. the number of raters) is known. In the first setting, where the sample size is known, we propose an aggregator, named as the Balanced Extremes Aggregator. It estimates unrevealed ratings with a balanced combination of extreme ratings. When the sample size is unknown, we derive another aggregator, the Polarizing-Averaging Aggregator, which becomes optimal as the sample size grows to infinity. Numerical results demonstrate the superiority of our proposed aggregators in mitigating participation bias, compared to simple averaging and the spectral method. Furthermore, we validate the effectiveness of our aggregators on a real-world dataset.

Yuqi Pan, Zhiwei Steven Wu, Haifeng Xu, Shuran Zheng

The tension between persuasion and privacy preservation is common in real-world settings. Online platforms should protect the privacy of web users whose data they collect, even as they seek to disclose information about these data (e.g., to advertisers). Similarly, hospitals may share patient data to attract research investments with the obligation to preserve patients' privacy. To address these issues, we study Bayesian persuasion under differential privacy constraints, where the sender must design an optimal signaling scheme for persuasion while guaranteeing the privacy of each agent's private information in the database. To understand how privacy constraints affect information disclosure, we explore two perspectives within Bayesian persuasion: one views the mechanism as releasing a posterior about the private data, while the other views it as sending an action recommendation. The posterior-based formulation leads to privacy-utility tradeoffs, quantifying how the tightness of privacy constraints impacts the sender's optimal utility. For any instance in a common utility function family and a wide range of privacy levels, a significant constant gap in the sender's optimal utility can be found between any two of the three conditions: ε-differential privacy constraint, relaxation (ε,δ)-differential privacy constraint, and no privacy constraint. We further geometrically characterize optimal signaling schemes under popular privacy constraints (ε-differential privacy, (ε,δ)-differential privacy and Rényi differential privacy), which turns out to be equivalent to finding concave hulls in constrained posterior regions. Finally, we develop polynomial-time algorithms for computing optimal differentially private signaling schemes.

Yukun Cheng, Xiaotie Deng, Yunxuan Ma

In the digital age, resources such as open-source software and publicly accessible databases form a crucial category of digital public goods, providing extensive benefits for Internet. However, these public goods' inherent non-exclusivity and non-competitiveness frequently result in under-provision, a dilemma exacerbated by individuals' tendency to free-ride. This scenario fosters both cooperation and competition among users, leading to the public goods games. This paper investigates networked public goods games involving heterogeneous players and convex costs, focusing on the characterization of Nash Equilibrium (NE). In these games, each player can choose her effort level, representing her contributions to public goods. Network structures are employed to model the interactions among participants. Each player's utility consists of a concave value component, influenced by the collective efforts of all players, and a convex cost component, determined solely by the individual's own effort. To the best of our knowledge, this study is the first to explore the networked public goods game with convex costs. Our research begins by examining welfare solutions aimed at maximizing social welfare and ensuring the convergence of pseudo-gradient ascent dynamics. We establish the presence of NE in this model and provide an in-depth analysis of the conditions under which NE is unique. We also delve into comparative statics, an essential tool in economics, to evaluate how slight modifications in the model--interpreted as monetary redistribution--affect player utilities. In addition, we analyze a particular scenario with a predefined game structure, illustrating the practical relevance of our theoretical insights. Overall, our research enhances the broader understanding of strategic interactions and structural dynamics in networked public goods games, with significant implications for policy design in internet economic and social networks.

Gagan Aggarwal, Giannis Fikioris, Mingfei Zhao

Advertisers are increasingly using automated bidding to optimize their ad campaigns on online advertising platforms. Autobidding allows an advertiser to optimize her objective subject to various constraints. In this paper, we design online autobidding algorithms to optimize value subject to ROI and budget constraints. We consider an item is being auctioned in each of T rounds. We focus on one buyer with budget and ROI constraints in the stochastic setting: her value and highest competing bid faced are drawn i.i.d. from some unknown (joint) distribution in each round. We design low-regret bidding algorithms that bid on behalf of this buyer. Our main result is an algorithm with full information feedback (i.e., the highest competing bid is revealed after each round) that guarantees a near-optimal ~O(√T) regret with respect to the best Lipschitz function that maps values to bids. The class of Lipschitz bidding functions is rich enough to best respond to many correlation structures between value and highest competing bid, e.g., positive or negative correlation. Our result applies to a wide range of auctions, most notably any mixture of first- and second-price auctions. In addition, our result holds for both value-maximizing buyers and quasi-linear utility-maximizing buyers. We also study the bandit setting, where one only observes whether the auction is won or not. Here, we show an Ω(T2/3 ) regret lower bound for first-price auctions, showing a significant disparity between the full information and bandit settings. We also design an algorithm with a regret bound of ~O(T3/4 ) when the value distribution is known and is independent of the highest competing bid.

Martino Banchio, Kshipra Bhawalkar, Christopher Liaw, Aranyak Mehta, Andrés Perlroth

In this paper, we initiate the study of autobidding where the signals for each bidder can be noisy and correlated. Our first set of results showcases the failure of traditional auctions such as the second-price auction (SPA) and the first-price auction (FPA). In particular, uniform bidding is not an optimal bidding strategy for SPA and both SPA and FPA can have arbitrarily poor efficiency. To circumvent this, we propose the Contextual Second Price Auction (CSPA), a novel mechanism which mitigates the aforementioned adverse effects by leveraging multiple signals to adjust the allocation of SPA. We show that uniform bidding is an optimal bidding strategy in CSPA and we prove a tight bound on the price for anarchy for CSPA of 2, thus recovering the well-established results in the independent setting. Finally, we show that CSPA always achieves at least half the welfare of SPA; moreover this is also tight.

Xiaodong Liu, Xiao Lin 0002, Yiming Ding, Changcheng Li, Peng Jiang 0002, Weiran Shen

Online advertising serves as the primary revenue source for numerous Internet companies, which typically sell advertising slots through auctions. Conventional online ad auctions assume constant click-through rates (CTRs) and conversion rates (CVRs) for ads during the auction process. However, this paper studies a new scenario where advertisers can offer coupons to users, thereby influencing both CTRs and CVRs and consequently, the platform's revenue. We study how to recommend user coupons to advertisers in truthful auction systems. We model the interaction between the platform and the advertisers as an extensive-form game, where advertisers first report coupon bids to the platform to receive coupon recommendations, and then participate in auctions by reporting their auction bids. Our research identifies a sufficient condition under which the advertisers' optimal strategy is to report their valuations truthfully in both the recommendation and auction stages. We construct two mechanisms based on these findings. The first mechanism is a distribution-free mechanism, which is easily implementable in industrial systems; and the second is a revenue-optimal mechanism that offers simpler implementation compared to existing work Liu et al. Both synthetic and industrial experiments show that our mechanisms improve the platform's revenue. Notably, our revenue-optimal mechanism achieves the same outcome compared to existing work by Liu et al., while offering a simpler implementation.

Juwei Yue, Haikuo Li, Jiawei Sheng, Yihan Guo, Xinghua Zhang 0001, Chuan Zhou 0001, Tingwen Liu, Li Guo 0001

该来源暂未提供摘要。

Kun Xie 0010, Renchi Yang, Sibo Wang 0001

Clustering over a graph seeks to partition the nodes therein into disjoint groups such that nodes within the same cluster are tightly-knit, while those across clusters are distant from each other. In practice, graphs are often attended with rich attributes, which are termed attributed graphs. By leveraging the complementary nature of graph topology and node attributes in such graphs, graph neural networks (GNNs) have obtained encouraging performance in graph clustering. However, existing GNN-based approaches strongly rely on the homophilic assumption of the input graph, and thus, largely fail on heterophilic graphs and others embodying numerous missing or noisy links, which are widely present in real life. To bridge this gap, this paper presents DGAC, an effective graph-agnostic solution for graph clustering. Particularly, DGAC overcomes the limitations of prior works by exploiting the high-order connectivity of nodes within not only the input graph G but also the affinity graph H underlying the attribute data. To achieve this goal, we first unify the embedding and clustering generations into a coherent framework optimizing the Dirichlet Energy on both G and H. Based thereon, theoretically-grounded solvers are developed for efficient constructions of the embeddings and clusters via graph diffusion operations, which aggregate features from specific neighbors, enabling the capture of high-order semantics from G or H. On top of that, DGAC includes three training loss functions that facilitate effective feature extraction and clustering. Extensive experiments, comparing DGAC against 12 baselines over 12 homophilic or heterophilic graph datasets, showcase that DGAC consistently and considerably outperforms all competitors in terms of clustering quality measured against ground truth labels.

Dongyuan Li, Satoshi Kosugi, Ying Zhang 0065, Manabu Okumura, Feng Xia 0001, Renhe Jiang

Dynamic graph clustering aims to detect and track time-varying clusters in dynamic graphs, revealing the evolutionary mechanisms of complex real-world dynamic systems. Matrix factorization-based methods are promising approaches for this task; however, these methods often struggle with scalability and can be time-consuming when applied to large-scale dynamic graphs. Moreover, they tend to lack robustness and are vulnerable to real-world noisy data. To address these issues, we make three key contributions. First, to improve scalability, we propose temporal separated matrix factorization, where a single matrix is divided into multiple smaller matrices for independent factorization, resulting in faster computation. Second, to improve robustness, we introduce bi-clustering regularization, which jointly optimizes graph embedding and clustering, thereby filtering out noisy features from the graph embeddings. Third, to further enhance effectiveness and efficiency, we propose selective embedding updating, where we update only the embeddings of dynamic nodes while the embeddings of static nodes are fixed among different timestamps. Experimental results on six synthetic and five real-world benchmarks demonstrate the scalability, robustness and effectiveness of our proposed method. Source code is available at https://github.com/Clearloveyuan/DyG-MF.

Yubo Sun, Haoxin Sun, Zhongzhi Zhang

Centrality measures are essential for identifying important nodes and edges in networks. In this paper, we focus on two forest-based centrality measures on undirected graphs: forest node centrality (FNC) and forest edge centrality (FEC), which capture the influence of nodes and edges through their participation in spanning forests. Both centrality measures can be represented using entries of the forest matrix. To address the challenge of computing the two measures on large networks, we propose two scalable algorithms from different perspectives. The first algorithm IFGN combines two variance reduction techniques to approximate the entries of the forest matrix, applicable to both FNC and FEC.The second algorithm FECE incorporates a new physical interpretation of FEC, allowing for a better overall estimation. We provide error guarantees for both algorithms and demonstrate their efficiency and effectiveness through extensive experiments on various real-world networks.

Xiaowei Lv, Xiaojia Xu, Yongcai Wang, Haoyu Liu, Deying Li 0001

The Budget Limited Coreness Maximization (BLCM) problem aims to enhance average user engagement by activating a limited number of connections, i.e., inserting up to b edges to maximize the coreness gain of all vertices in a graph. Due to the cascading feature, we prove the BLCM is NP-hard, APX-hard, and not submodular, meaning greedy sequential edge insertion fails to deliver satisfactory results. As a result, solving BLCM requires combinatorial edge insertion and must face the combinatorial exploration difficulty. This paper proposes the first effective and polynomial-time approach to BLCM. It embeds local combinatorial optimization into global greedy search to boost the benefits of combinatorial optimization while restricting its complexity. Specifically, we propose efficient methods to evaluate the cascaded coreness improvements of two local combinatorial strategies, i.e., when a leader or a group of nodes increase their coreness values via local edge insertion. Note that the key difficulty lies in evaluating the cascading effects. Based on these, we propose three efficient combinatorial edge insertion strategies: (1) Leader-Centric Greedy Insertion (LCGI), (2) Group-Centric Greedy Insertion (GCGI), and (3) a Leader-Group Balance (LGB) insertion. LCGI greedily finds the most influential leader that can produce the highest coreness gain together with its followers. GCGI finds the most influential group that can promote the most coreness gain. LGB combines the two strategies to select edge combinations adaptively. We prove the low complexity of LCGI, GCGI and LGB. Experiments conducted on 13 real-world datasets highlight their practical utility and superiority over existing approaches.

Xin Wang 0128, Jiawei Jiang 0001, Xiao Yan 0002, Qiang Huang 0009

Dynamic graph neural networks (DGNNs) are designed to capture the dynamic evolution of graph node interactions. However, existing DGNNs mainly consider homogeneous graphs, neglecting the rich heterogeneity in node and edge types, which is prevalent for real-world graphs and essential for modeling complex dynamic interactions. In this work, we propose the TrajEctory and Semantic-Aware dynamic heterogeneous graph neural network (TeSa), which integrates trajectory-based evolution and semantic-aware aggregation to capture both the evolving dynamics and heterogeneous semantics entailed in continuous-time dynamic heterogeneous graphs. In particular, trajectory-based evolution treats the interactions received by each node (called node trajectory) as a sequence and employs a temporal point process to learn the dynamic evolution in these interactions. Semantic-aware aggregation separates edges of different types when aggregating messages for each node from its neighbors. Edges of the same type are processed at first (i.e., intra-semantic aggregation), and then edges of different types are handled (i.e., inter-semantic fusion), to offer a comprehensive view of the heterogeneous semantics. We compare TeSa with 7 state-of-the-art DGNN models, and the results show that TeSa improves the best-performing baseline by an average of 5.11% and 5.74% in accuracy for transductive and inductive tasks.

Zhenhua Huang 0002, Wenhao Zhou, Yufeng Li, Xiuyang Wu, Chengpei Xu, Junfeng Fang, Zhaohong Jia, Linyuan Lü, Feng Xia 0001

Heterogeneous Graph Neural Networks (HGNNs) are extensively applied in modeling web-based applications that involve heterogeneous graph structures. Explanation models for HGNNs aim to address their ''black box'' nature. Enhancing the interpretability of HGNNs leads to a better understanding and can potentially improve predictive performance. However, existing post-hoc HGNN explanation methods cannot impact the HGNN's predictions. Self-explainable homogeneous models also perform poorly on heterogeneous graphs. To address these challenges, we present a Self-Explainable Heterogeneous Graph Neural Network (SEHG), a novel architecture that integrates explanation generation into the learning process of HGNN through two alternative stages. The first stage focuses on producing high-quality explanations while providing predictions alongside. The second stage enhances prediction accuracy by a contrastive learning strategy. Unlike the current methods that rely on manually defined metapaths for structural explanations, SEHG generates important structure and feature explanations by learnable heterogeneous masks. To ensure high-quality and sparsity explanation, these masks are regulated by a uniquely designed range-based penalty during training. Moreover, we introduce HetBA, a collection of synthetic heterogeneous datasets designed to quantify and visualize explanations or heterogeneous graphs. Extensive experiments demonstrate the effectiveness of SEHG, which surpasses strong baselines in real-world node classification tasks by notable margins of up to 3.91%. SEHG also achieves state-of-the-art performance on synthetic datasets with improvement of up to 9.44%, and records the highest fidelity scores in explanation tasks, improving by up to 46.57%. To our knowledge, SEHG is a pioneering self-explainable HGNN framework that achieves state-of-the-art performance on both heterogeneous graph explanation and prediction tasks.

Yifan Wang, Gonzalo R. Arce, Guangmo Tong

Hypergraph neural networks have been promising tools for handling learning tasks involving higher-order data, with notable applications in web graphs, such as modeling multi-way hyperlink structures and complex user interactions. Yet, their generalization abilities in theory are less clear to us. In this paper, we seek to develop margin-based generalization bounds for four representative classes of hypergraph neural networks, including convolutional-based methods (UniGCN), set-based aggregation (AllDeepSets), invariant and equivariant transformations (M-IGN), and tensor-based approaches (T-MPHN). Through the PAC-Bayes framework, our results reveal the manner in which hypergraph structure and spectral norms of the learned weights can affect the generalization bounds, where the key technical challenge lies in developing new perturbation analysis for hypergraph neural networks, which offers a rigorous understanding of how variations in the model's weights and hypergraph structure impact its generalization behavior. Our empirical study examines the relationship between the practical performance and theoretical bounds of the models over synthetic and real-world datasets. One of our primary observations is the strong correlation between the theoretical bounds and empirical loss, with statistically significant consistency in most cases.

Minyoung Choe, Jihoon Ko, Taehyung Kwon, Kijung Shin, Christos Faloutsos

Do real-world hypergraphs obey any patterns? Are power laws fundamental in hypergraphs as they are in real-world graphs? What generator can reproduce these patterns? A hypergraph is a generalization of a conventional graph, and it consists of nodes and hyperedges, with each hyperedge joining any number of nodes. Hypergraphs are adept at representing group interactions where two or more entities interact simultaneously, such as collaborative research and group discussions. In a wide range of real-world hypergraphs, we discover power-law or log-logistic distributions in eight structural properties. To simulate these observed patterns, we introduce HyRec, a tractable and realistic generative model leveraging the Kronecker product. We mathematically demonstrate that HyRec accurately reproduces both the patterns we observed and typical evolutionary trends found in real-world hypergraphs. To fit the parameters of HyRec to large-scale hypergraphs, we design SingFit, a fast and space-efficient algorithm successfully applied to eleven real-world hypergraphs with up to one million nodes and hyperedges. This paper makes the following contributions: (a) Discoveries: we identify multiple patterns that real-world hypergraphs obey, (b) Model: we propose HyRec, a tractable and realistic model capable of reproducing real-world hypergraphs efficiently (spec., with fewer than 1,000 parameters) with the support of SingFit, and (c) Proofs: we prove that HyRec adheres to these patterns.

Zheng Gong 0001, Shuheng Shen, Changhua Meng, Ying Sun 0006

Hypergraph neural networks (HyperGNNs) show promise in modeling online networks with high-order correlations. Despite notable progress, training these models on large-scale raw hypergraphs entails substantial computational and storage costs, thereby increasing the need of hypergraph size reduction. However, existing size reduction methods primarily capture pairwise association pattern within conventional graphs, making them challenging to adapt to hypergraphs with high-order correlations. To fill this gap, we introduce a novel hypergraph condensation framework, HG-Cond, designed to distill large-scale hypergraphs into compact, synthetic versions while maintaining comparable HyperGNN performance. Within this framework, we develop a Neural Hyperedge Linker to capture the high-order connectivity pattern through variational inference, achieving linear complexity with respect to the number of nodes. Moreover, We propose a multi-aspectual amelioration strategy including a Gradient-Parameter Synergistic Matching objective to holistically refine synthetic hypergraphs by coordinating improvements in node attributes, high-order connectivity, and label distributions. Extensive experiments demonstrate the efficacy of HG-Cond in hypergraph condensation, notably outperforming the original test accuracy on the 20News dataset while concurrently reducing the hypergraph size to a mere 5% of its initial scale. Furthermore, the condensed hypergraphs demonstrate robust cross-architectural generalizability and potential for expediting neural architecture search.

Yuanhao Ding, Yang Liu 0200, Yugang Ji, Weigao Wen, Qing He 0003, Xiang Ao 0001

Graph Neural Networks (GNNs) are vulnerable to backdoor attacks, where adversaries implant malicious triggers to manipulate model predictions. Existing graph backdoor attacks are susceptible to defense mechanisms or robust classifiers because they rely on subgraph injection or structural perturbations, e.g., creating additional edges to attach backdoor triggers to the original graph. To enhance the stealthiness of graph backdoors, we propose SPEAR, a novel structure-preserving graph backdoor attack that avoids modifying the graph's topology. SPEAR operates within a limited attack budget by selectively perturbing node attributes while ensuring the triggers exert significant influence through a global importance-driven feature selection strategy. Additionally, a neighborhood-aware trigger generator is employed to underpin a high attack success rate by utilizing semantic information from the neighborhood. SPEAR amplifies effectiveness and stealthiness by combining subtle yet impactful attribute manipulation with a refined trigger generation mechanism. Extensive experiments demonstrate that SPEAR achieves state-of-the-art effectiveness in bypassing defenses on real-world datasets, establishing it as a potent and stealthy backdoor attack for graph-based tasks. Code is available at https://github.com/yhDing/SPEAR.