OpenRaiser/Intern-Atlas huggingface dataset:
CAFIN: Centrality Aware Fairness inducing IN-processing for Unsupervised Representation Learning on Graphs
Venue: arXiv cs.LG 2024
Year: 2024

Unsupervised Representation Learning on graphs is gaining traction due to the increasing abundance of unlabelled network data and the compactness, richness, and usefulness of the representations generated. In this context, the need to consider fairness and bias constraints while generating the representations has been well-motivated and studied to some extent in prior works. One major limitation of most of the prior works in this setting is that they do not aim to address the bias generated due to connectivity patterns in the graphs, such as varied node centrality, which leads to a disproportionate performance across nodes. In our work, we aim to address this issue of mitigating bias due to inherent graph structure in an unsupervised setting. To this end, we propose CAFIN, a centrality-aware fairness-inducing framework that leverages the structural information of graphs to tune the representations generated by existing frameworks. We deploy it on GraphSAGE (a popular framework in this domain) and showcase its efficacy on two downstream tasks - Node Classification and Link Prediction. Empirically, CAFIN consistently reduces the performance disparity across popular datasets (varying from 18 to 80% reduction in performance disparity) from various domains while incurring only a minimal cost of fairness.
Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)
Venue: arXiv cs.DS 2024
Year: 2024

Given an $n$-vertex undirected graph $G=(V,E,w)$, and a parameter $k\geq1$, a path-reporting distance oracle (or PRDO) is a data structure of size $S(n,k)$, that given a query $(u,v)\in V^2$, returns an $f(k)$-approximate shortest $u-v$ path $P$ in $G$ within time $q(k)+O(|P|)$. Here $S(n,k)$, $f(k)$ and $q(k)$ are arbitrary functions. A landmark PRDO due to Thorup and Zwick, with an improvement of Wulff-Nilsen, has $S(n,k)=O(k\cdot n^{1+\frac{1}{k}})$, $f(k)=2k-1$ and $q(k)=O(\log k)$. The size of this oracle is $Ω(n\log n)$ for all $k$. Elkin and Pettie and Neiman and Shabat devised much sparser PRDOs, but their stretch was polynomially larger than the optimal $2k-1$. On the other hand, for non-path-reporting distance oracles, Chechik devised a result with $S(n,k)=O(n^{1+\frac{1}{k}})$, $f(k)=2k-1$ and $q(k)=O(1)$. In this paper we make a dramatic progress in bridging the gap between path-reporting and non-path-reporting distance oracles. We devise a PRDO with size $S(n,k)=O(\lceil\frac{k\log\log n}{\log n}\rceil\cdot n^{1+\frac{1}{k}})$, stretch $f(k)=O(k)$ and query time $q(k)=O(\log\lceil\frac{k\log\log n}{\log n}\rceil)$. We can also have size $O(n^{1+\frac{1}{k}})$, stretch $O(k\cdot\lceil\frac{k\log\log n}{\log n}\rceil)$ and query time $q(k)=O(\log\lceil\frac{k\log\log n}{\log n}\rceil)$. Our results on PRDOs are based on novel constructions of approximate distance preservers, that we devise in this paper. Specifically, we show that for any $ε>0$, any $k=1,2,...$, and any graph $G$ and a collection $\mathcal{P}$ of $p$ vertex pairs, there exists a $(1+ε)$-approximate preserver with $O(γ(ε,k)\cdot p+n\log k+n^{1+\frac{1}{k}})$ edges, where $γ(ε,k)=(\frac{\log k}ε)^{O(\log k)}$. These new preservers are significantly sparser than the previous state-of-the-art approximate preservers due to Kogan and Parter.
(Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow
Venue: arXiv cs.DS 2024
Year: 2024

The All-Pairs Max-Flow problem has gained significant popularity in the last two decades, and many results are known regarding its fine-grained complexity. Despite this, wide gaps remain in our understanding of the time complexity for several basic variants of the problem. In this paper, we aim to bridge these gaps by providing algorithms, conditional lower bounds, and non-reducibility results. Notably, we show that for most problem settings, deterministic reductions based on the Strong Exponential Time Hypothesis (SETH) cannot rule out $O(n^{4-\varepsilon})$ time algorithms for some small $\varepsilon>0$, under a hypothesis called NSETH. To obtain our result for the setting of undirected graphs with unit node-capacities, we design a new randomized Las Vegas $O(m^{2+o(1)})$ time combinatorial algorithm. This is our main technical result, improving over the recent $O(m^{11/5+o(1)})$ time Monte Carlo algorithm [Huang et al., STOC 2023] and matching their $m^{2-o(1)}$ lower bound (up to subpolynomial factors), thus essentially settling the time complexity for this setting of the problem.
Approaching Test Time Augmentation in the Context of Uncertainty Calibration for Deep Neural Networks
Venue: arXiv cs.CV 2024
Year: 2024

With the rise of Deep Neural Networks, machine learning systems are nowadays ubiquitous in a number of real-world applications, which bears the need for highly reliable models. This requires a thorough look not only at the accuracy of such systems, but also at their predictive uncertainty. Hence, we propose a novel technique (with two different variations, named M-ATTA and V-ATTA) based on test time augmentation, to improve the uncertainty calibration of deep models for image classification. By leveraging na adaptive weighting system, M/V-ATTA improves uncertainty calibration without affecting the model's accuracy. The performance of these techniques is evaluated by considering diverse metrics related to uncertainty calibration, demonstrating their robustness. Empirical results, obtained on CIFAR-10, CIFAR-100, Aerial Image Dataset, as well as in two different scenarios under distribution-shift, indicate that the proposed methods outperform several state-of-the-art post-hoc calibration techniques. Furthermore, the methods proposed also show improvements in terms of predictive entropy on out-of-distribution samples. Code for M/V-ATTA available at: https://github.com/pedrormconde/MV-ATTA
Improving Neural Radiance Fields with Depth-aware Optimization for Novel View Synthesis
Venue: arXiv cs.CV 2024
Year: 2024

With dense inputs, Neural Radiance Fields (NeRF) is able to render photo-realistic novel views under static conditions. Although the synthesis quality is excellent, existing NeRF-based methods fail to obtain moderate three-dimensional (3D) structures. The novel view synthesis quality drops dramatically given sparse input due to the implicitly reconstructed inaccurate 3D-scene structure. We propose SfMNeRF, a method to better synthesize novel views as well as reconstruct the 3D-scene geometry. SfMNeRF leverages the knowledge from the self-supervised depth estimation methods to constrain the 3D-scene geometry during view synthesis training. Specifically, SfMNeRF employs the epipolar, photometric consistency, depth smoothness, and position-of-matches constraints to explicitly reconstruct the 3D-scene structure. Through these explicit constraints and the implicit constraint from NeRF, our method improves the view synthesis as well as the 3D-scene geometry performance of NeRF at the same time. In addition, SfMNeRF synthesizes novel sub-pixels in which the ground truth is obtained by image interpolation. This strategy enables SfMNeRF to include more samples to improve generalization performance. Experiments on two public datasets demonstrate that SfMNeRF surpasses state-of-the-art approaches. Code is available at https://github.com/XTU-PR-LAB/SfMNeRF
A Third Information-Theoretic Approach to Finite de Finetti Theorems
Venue: arXiv cs.IT 2024
Year: 2024

A new finite form of de Finetti's representation theorem is established using elementary information-theoretic tools. The distribution of the first $k$ random variables in an exchangeable vector of $n\geq k$ random variables is close to a mixture of product distributions. Closeness is measured in terms of the relative entropy and an explicit bound is provided. This bound is tighter than those obtained via earlier information-theoretic proofs, and its utility extends to random variables taking values in general spaces. The core argument employed has its origins in the quantum information-theoretic literature.
GNNUERS: Fairness Explanation in GNNs for Recommendation via Counterfactual Reasoning
Venue: arXiv cs.IR 2024
Year: 2024

Nowadays, research into personalization has been focusing on explainability and fairness. Several approaches proposed in recent works are able to explain individual recommendations in a post-hoc manner or by explanation paths. However, explainability techniques applied to unfairness in recommendation have been limited to finding user/item features mostly related to biased recommendations. In this paper, we devised a novel algorithm that leverages counterfactuality methods to discover user unfairness explanations in the form of user-item interactions. In our counterfactual framework, interactions are represented as edges in a bipartite graph, with users and items as nodes. Our bipartite graph explainer perturbs the topological structure to find an altered version that minimizes the disparity in utility between the protected and unprotected demographic groups. Experiments on four real-world graphs coming from various domains showed that our method can systematically explain user unfairness on three state-of-the-art GNN-based recommendation models. Moreover, an empirical evaluation of the perturbed network uncovered relevant patterns that justify the nature of the unfairness discovered by the generated explanations. The source code and the preprocessed data sets are available at https://github.com/jackmedda/RS-BGExplainer.
When do homomorphism counts help in query algorithms?
Venue: arXiv cs.LO 2024
Year: 2024

A query algorithm based on homomorphism counts is a procedure for determining whether a given instance satisfies a property by counting homomorphisms between the given instance and finitely many predetermined instances. In a left query algorithm, we count homomorphisms from the predetermined instances to the given instance, while in a right query algorithm we count homomorphisms from the given instance to the predetermined instances. Homomorphisms are usually counted over the semiring N of non-negative integers; it is also meaningful, however, to count homomorphisms over the Boolean semiring B, in which case the homomorphism count indicates whether or not a homomorphism exists. We first characterize the properties that admit a left query algorithm over B by showing that these are precisely the properties that are both first-order definable and closed under homomorphic equivalence. After this, we turn attention to a comparison between left query algorithms over B and left query algorithms over N. In general, there are properties that admit a left query algorithm over N but not over B. The main result of this paper asserts that if a property is closed under homomorphic equivalence, then that property admits a left query algorithm over B if and only if it admits a left query algorithm over N. In other words and rather surprisingly, homomorphism counts over N do not help as regards properties that are closed under homomorphic equivalence. Finally, we characterize the properties that admit both a left query algorithm over B and a right query algorithm over B.
Characterising Modal Formulas with Examples
Venue: arXiv cs.LO 2024
Year: 2024

We study the existence of finite characterisations for modal formulas. A finite characterisation of a modal formula $φ$ is a finite collection of positive and negative examples that distinguishes $φ$ from every other, non-equivalent modal formula, where an example is a finite pointed Kripke structure. This definition can be restricted to specific frame classes and to fragments of the modal language: a modal fragment $L$ admits finite characterisations with respect to a frame class $F$ if every formula $φ\in L$ has a finite characterisation with respect to $L$ consting of examples that are based on frames in $F$. Finite characterisations are useful for illustration, interactive specification, and debugging of formal specifications, and their existence is a precondition for exact learnability with membership queries. We show that the full modal language admits finite characterisations with respect to a frame class $F$ only when the modal logic of $F$ is locally tabular. We then study which modal fragments, freely generated by some set of connectives, admit finite characterisations. Our main result is that the positive modal language without the truth-constants $\top$ and $\bot$ admits finite characterisations w.r.t. the class of all frames. This result is essentially optimal: finite characterizability fails when the language is extended with the truth constant $\top$ or $\bot$ or with all but very limited forms of negation.
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
Venue: arXiv cs.DS 2024
Year: 2024

We revisit Nisan's classical pseudorandom generator (PRG) for space-bounded computation (STOC 1990) and its applications in streaming algorithms. We describe a new generator, HashPRG, that can be thought of as a symmetric version of Nisan's generator over larger alphabets. Our generator allows a trade-off between seed length and the time needed to compute a given block of the generator's output. HashPRG can be used to obtain derandomizations with much better update time and \emph{without sacrificing space} for a large number of data stream algorithms, such as $F_p$ estimation in the parameter regimes $p > 2$ and $0 < p < 2$ and CountSketch with tight estimation guarantees as analyzed by Minton and Price (SODA 2014) which assumed access to a random oracle. We also show a recent analysis of Private CountSketch can be derandomized using our techniques. For a $d$-dimensional vector $x$ being updated in a turnstile stream, we show that $\|x\|_{\infty}$ can be estimated up to an additive error of $\varepsilon\|x\|_{2}$ using $O(\varepsilon^{-2}\log(1/\varepsilon)\log d)$ bits of space. Additionally, the update time of this algorithm is $O(\log 1/\varepsilon)$ in the Word RAM model. We show that the space complexity of this algorithm is optimal up to constant factors. However, for vectors $x$ with $\|x\|_{\infty} = Θ(\|x\|_{2})$, we show that the lower bound can be broken by giving an algorithm that uses $O(\varepsilon^{-2}\log d)$ bits of space which approximates $\|x\|_{\infty}$ up to an additive error of $\varepsilon\|x\|_{2}$. We use our aforementioned derandomization of the CountSketch data structure to obtain this algorithm, and using the time-space trade off of HashPRG, we show that the update time of this algorithm is also $O(\log 1/\varepsilon)$ in the Word RAM model.
Advancing Differential Privacy: Where We Are Now and Future Directions for Real-World Deployment
Venue: arXiv cs.CR 2024
Year: 2024

In this article, we present a detailed review of current practices and state-of-the-art methodologies in the field of differential privacy (DP), with a focus of advancing DP's deployment in real-world applications. Key points and high-level contents of the article were originated from the discussions from "Differential Privacy (DP): Challenges Towards the Next Frontier," a workshop held in July 2022 with experts from industry, academia, and the public sector seeking answers to broad questions pertaining to privacy and its implications in the design of industry-grade systems. This article aims to provide a reference point for the algorithmic and design decisions within the realm of privacy, highlighting important challenges and potential research directions. Covering a wide spectrum of topics, this article delves into the infrastructure needs for designing private systems, methods for achieving better privacy/utility trade-offs, performing privacy attacks and auditing, as well as communicating privacy with broader audiences and stakeholders.
SpChar: Characterizing the Sparse Puzzle via Decision Trees
Venue: arXiv cs.AR 2024
Year: 2024

Sparse matrix computation is crucial in various modern applications, including large-scale graph analytics, deep learning, and recommender systems. The performance of sparse kernels varies greatly depending on the structure of the input matrix, making it difficult to gain a comprehensive understanding of sparse computation and its relationship to inputs, algorithms, and target machine architecture. Despite extensive research on certain sparse kernels, such as Sparse Matrix-Vector Multiplication (SpMV), the overall family of sparse algorithms has yet to be investigated as a whole. This paper introduces SpChar, a workload characterization methodology for general sparse computation. SpChar employs tree-based models to identify the most relevant hardware and input characteristics, starting from hardware and input-related metrics gathered from Performance Monitoring Counters (PMCs) and matrices. Our analysis enables the creation of a characterization loop that facilitates the optimization of sparse computation by mapping the impact of architectural features to inputs and algorithmic choices. We apply SpChar to more than 600 matrices from the SuiteSparse Matrix collection and three state-of-the-art Arm CPUs to determine the critical hardware and software characteristics that affect sparse computation. In our analysis, we determine that the biggest limiting factors for high-performance sparse computation are (1) the latency of the memory system, (2) the pipeline flush overhead resulting from branch misprediction, and (3) the poor reuse of cached elements. Additionally, we propose software and hardware optimizations that designers can implement to create a platform suitable for sparse computation. We then investigate these optimizations using the gem5 simulator to achieve a significant speedup of up to 2.63x compared to a CPU where the optimizations are not applied.
Operations on Fixpoint Equation Systems
Venue: arXiv cs.LO 2024
Year: 2024

We study operations on fixpoint equation systems (FES) over arbitrary complete lattices. We investigate under which conditions these operations, such as substituting variables by their definition, and swapping the ordering of equations, preserve the solution of a FES. We provide rigorous, computer-checked proofs. Along the way, we list a number of known and new identities and inequalities on extremal fixpoints in complete lattices.
CollabCoder: A Lower-barrier, Rigorous Workflow for Inductive Collaborative Qualitative Analysis with Large Language Models
Venue: arXiv cs.HC 2024
Year: 2024

Collaborative Qualitative Analysis (CQA) can enhance qualitative analysis rigor and depth by incorporating varied viewpoints. Nevertheless, ensuring a rigorous CQA procedure itself can be both demanding and costly. To lower this bar, we take a theoretical perspective to design the CollabCoder workflow, that integrates Large Language Models (LLMs) into key inductive CQA stages: independent open coding, iterative discussions, and final codebook creation. In the open coding phase, CollabCoder offers AI-generated code suggestions and records decision-making data. During discussions, it promotes mutual understanding by sharing this data within the coding team and using quantitative metrics to identify coding (dis)agreements, aiding in consensus-building. In the code grouping stage, CollabCoder provides primary code group suggestions, lightening the cognitive load of finalizing the codebook. A 16-user evaluation confirmed the effectiveness of CollabCoder, demonstrating its advantages over existing software and providing empirical insights into the role of LLMs in the CQA practice.
Gradient-less Federated Gradient Boosting Trees with Learnable Learning Rates
Venue: arXiv cs.LG 2024
Year: 2024

The privacy-sensitive nature of decentralized datasets and the robustness of eXtreme Gradient Boosting (XGBoost) on tabular data raise the needs to train XGBoost in the context of federated learning (FL). Existing works on federated XGBoost in the horizontal setting rely on the sharing of gradients, which induce per-node level communication frequency and serious privacy concerns. To alleviate these problems, we develop an innovative framework for horizontal federated XGBoost which does not depend on the sharing of gradients and simultaneously boosts privacy and communication efficiency by making the learning rates of the aggregated tree ensembles learnable. We conduct extensive evaluations on various classification and regression datasets, showing our approach achieves performance comparable to the state-of-the-art method and effectively improves communication efficiency by lowering both communication rounds and communication overhead by factors ranging from 25x to 700x. Project Page: https://flower.ai/blog/2023-04-19-xgboost-with-flower/
About latent roles in forecasting players in team sports
Venue: arXiv cs.CV 2024
Year: 2024

Forecasting players in sports has grown in popularity due to the potential for a tactical advantage and the applicability of such research to multi-agent interaction systems. Team sports contain a significant social component that influences interactions between teammates and opponents. However, it still needs to be fully exploited. In this work, we hypothesize that each participant has a specific function in each action and that role-based interaction is critical for predicting players' future moves. We create RolFor, a novel end-to-end model for Role-based Forecasting. RolFor uses a new module we developed called Ordering Neural Networks (OrderNN) to permute the order of the players such that each player is assigned to a latent role. The latent role is then modeled with a RoleGCN. Thanks to its graph representation, it provides a fully learnable adjacency matrix that captures the relationships between roles and is subsequently used to forecast the players' future trajectories. Extensive experiments on a challenging NBA basketball dataset back up the importance of roles and justify our goal of modeling them using optimizable models. When an oracle provides roles, the proposed RolFor compares favorably to the current state-of-the-art (it ranks first in terms of ADE and second in terms of FDE errors). However, training the end-to-end RolFor incurs the issues of differentiability of permutation methods, which we experimentally review. Finally, this work restates differentiable ranking as a difficult open problem and its great potential in conjunction with graph-based interaction models. Project is available at: https://www.pinlab.org/aboutlatentroles