GenAI4ELab/papercli-papers huggingface dataset:
How Does Message Passing Improve Collaborative Filtering?
Authors: Mingxuan Ju; William Shiao; Zhichun Guo; Yanfang Ye; Yozen Liu; Neil Shah; Tong Zhao
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Collaborative filtering (CF) has exhibited prominent results for recommender systems and been broadly utilized for real-world applications.
A branch of research enhances CF methods by message passing (MP) used in graph neural networks, due to its strong capabilities of extracting knowledge from graph-structured data, like user-item bipartite graphs that naturally exist in CF. They assume that MP helps CF methods in a manner akin to its benefits for graph-based learning tasks in general (e.g., node classification). However, even though MP empirically improves CF, whether or not this assumption is correct still needs verification. To address this gap, we formally investigate why MP helps CF from multiple perspectives and show that many assumptions made by previous works are not entirely accurate. With our curated ablation studies and theoretical analyses, we discover that (i) MP improves the CF performance primarily by additional representations passed from neighbors during the forward pass instead of additional gradient updates to neighbor representations during the model back-propagation and (ii) MP usually helps low-degree nodes more than high-degree nodes.}Utilizing these novel findings, we present Test-time Aggregation for Collaborative Filtering, namely TAG-CF, a test-time augmentation framework that only conducts MP once at inference time. The key novelty of TAG-CF is that it effectively utilizes graph knowledge while circumventing most of notorious computational overheads of MP. Besides, TAG-CF is extremely versatile can be used as a plug-and-play module to enhance representations trained by different CF supervision signals. Evaluated on six datasets (i.e., five academic benchmarks and one real-world industrial dataset), TAG-CF consistently improves the recommendation performance of CF methods without graph by up to 39.2% on cold users and 31.7% on all users, with little to no extra computational overheads. Furthermore, compared with trending graph-enhanced CF methods, TAG-CF delivers comparable or even better performance with less than 1% of their total training times. Our code is publicly available at https://github.com/snap-research/Test-time-Aggregation-for-CF.
Learning Plaintext-Ciphertext Cryptographic Problems via ANF-based SAT Instance Representation
Authors: Xinhao Zheng; Yang Li; Cunxin Fan; Huaijin Wu; Xinhao Song; Junchi Yan
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Cryptographic problems, operating within binary variable spaces, can be routinely transformed into Boolean Satisfiability (SAT) problems regarding specific cryptographic conditions like plaintext-ciphertext matching. With the fast development of learning for discrete data, this SAT representation also facilitates the utilization of machine-learning approaches with the hope of automatically capturing patterns and strategies inherent in cryptographic structures in a data-driven manner. Existing neural SAT solvers consistently adopt conjunctive normal form (CNF) for instance representation, which in the cryptographic context can lead to scale explosion and a loss of high-level semantics. In particular, extensively used XOR operations in cryptographic problems can incur an exponential number of clauses. In this paper, we propose a graph structure based on Arithmetic Normal Form (ANF) to efficiently handle the XOR operation bottleneck. Additionally, we design an encoding method for AND operations in these ANF-based graphs, demonstrating improved efficiency over alternative general graph forms for SAT. We then propose CryptoANFNet, a graph learning approach that trains a classifier based on a message-passing scheme to predict plaintext-ciphertext satisfiability. 
Using ANF-based SAT instances, CryptoANFNet demonstrates superior scalability and can naturally capture higher-order operational information. Empirically, CryptoANFNet achieves a 50x speedup over heuristic solvers and outperforms SOTA learning-based SAT solver NeuroSAT, with 96\% vs. 91\% accuracy on small-scale and 72\% vs. 55\% on large-scale datasets from real encryption algorithms. We also introduce a key-solving algorithm that simplifies ANF-based SAT instances from plaintext and ciphertext, enhancing key decryption accuracy from 76.5\% to 82\% and from 72\% to 75\% for datasets generated from two real encryption algorithms.
Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolfe Line Search
Authors: Qiujiang Jin; Ruichen Jiang; Aryan Mokhtari
Venue: NeurIPS 2024 (NeurIPS 2024 spotlight)

Abstract: In this paper, we present the first explicit and non-asymptotic global convergence rates of the BFGS method when implemented with an inexact line search scheme satisfying the Armijo-Wolfe conditions. We show that BFGS achieves a global linear convergence rate of $(1 - \frac{1}{\kappa})^t$ for $\mu$-strongly convex functions with $L$-Lipschitz gradients, where $\kappa = \frac{L}{\mu}$ represents the condition number. Additionally, if the objective function's Hessian is Lipschitz, BFGS with the Armijo-Wolfe line search achieves a linear convergence rate that depends solely on the line search parameters, independent of the condition number. We also establish a global superlinear convergence rate of $\mathcal{O}((\frac{1}{t})^t)$. These global bounds are all valid for any starting point $x_0$ and any symmetric positive definite initial Hessian approximation matrix $B_0$, though the choice of $B_0$ impacts the number of iterations needed to achieve these rates. By synthesizing these results, we outline the first global complexity characterization of BFGS with the Armijo-Wolfe line search. Additionally, we clearly define a mechanism for selecting the step size to satisfy the Armijo-Wolfe conditions and characterize its overall complexity.
Newton Informed Neural Operator for Solving Nonlinear Partial Differential Equations
Authors: Wenrui Hao; Xinliang Liu; Yahong Yang
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Solving nonlinear partial differential equations (PDEs) with multiple solutions is essential in various fields, including physics, biology, and engineering. However, traditional numerical methods, such as finite element and finite difference methods, often face challenges when dealing with nonlinear solvers, particularly in the presence of multiple solutions. These methods can become computationally expensive, especially when relying on solvers like Newton's method, which may struggle with ill-posedness near bifurcation points.
In this paper, we propose a novel approach, the Newton Informed Neural Operator, which learns the Newton solver for nonlinear PDEs. Our method integrates traditional numerical techniques with the Newton nonlinear solver, efficiently learning the nonlinear mapping at each iteration. This approach allows us to compute multiple solutions in a single learning process while requiring fewer supervised data points than existing neural network methods.
On scalable oversight with weak LLMs judging strong LLMs
Authors: Zachary Kenton; Noah Yamamoto Siegel; Janos Kramar; Jonah Brown-Cohen; Samuel Albanie; Jannis Bulian; Rishabh Agarwal; David Lindner; Yunhao Tang; Noah Goodman; Rohin Shah
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Scalable oversight protocols aim to enable humans to accurately supervise superhuman AI. 
In this paper we study debate, where two AI's compete to convince a judge; consultancy, 
where a single AI tries to convince a judge that asks questions;
and compare to a baseline of direct question-answering, where the judge just answers outright without the AI.
We use large language models (LLMs) as both AI agents and as stand-ins for human judges, taking the judge models to be weaker than agent models. 
We benchmark on a diverse range of asymmetries between judges and agents, extending previous work on a single extractive QA task with information asymmetry, to also include mathematics, coding, logic and multimodal reasoning asymmetries. 
We find that debate outperforms consultancy across all tasks when the consultant is randomly assigned to argue for the correct/incorrect answer. Comparing debate to direct question answering, the results depend on the type of task: in extractive QA tasks with information asymmetry debate outperforms direct question answering, but in other tasks without information asymmetry the results are mixed.
Previous work assigned debaters/consultants an answer to argue for. When we allow them to instead choose which answer to argue for, we find judges are less frequently convinced by the wrong answer in debate than in consultancy.
Further, we find that stronger debater models increase judge accuracy, though more modestly than in previous studies.
Learning with Fitzpatrick Losses
Authors: Seta Rakotomandimby; Jean-Philippe Chancelier; Michel De Lara; Mathieu Blondel
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Fenchel-Young losses are a family of loss functions, encompassing the squared,
logistic and sparsemax losses, among others. They are convex w.r.t. the model
output and the target, separately. Each Fenchel-Young loss is implicitly associated
with a link function, that maps model outputs to predictions. For instance, the
logistic loss is associated with the soft argmax link function. Can we build new
loss functions associated with the same link function as Fenchel-Young losses?
In this paper, we introduce Fitzpatrick losses, a new family of separately convex
loss functions based on the Fitzpatrick function. A well-known theoretical tool in
maximal monotone operator theory, the Fitzpatrick function naturally leads to a
refined Fenchel-Young inequality, making Fitzpatrick losses tighter than Fenchel-
Young losses, while maintaining the same link function for prediction. As an
example, we introduce the Fitzpatrick logistic loss and the Fitzpatrick sparsemax
loss, counterparts of the logistic and the sparsemax losses. This yields two new
tighter losses associated with the soft argmax and the sparse argmax, two of the
most ubiquitous output layers used in machine learning. We study in details the
properties of Fitzpatrick losses and, in particular, we show that they can be seen as
Fenchel-Young losses using a modified, target-dependent generating function. We
demonstrate the effectiveness of Fitzpatrick losses for label proportion estimation.
Vision Mamba Mender
Authors: Jiacong Hu; Anda Cao; Zunlei Feng; Shengxuming Zhang; Yi Wang; Lingxiang Jia; Mingli Song
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Mamba, a state-space model with selective mechanisms and hardware-aware architecture, has demonstrated outstanding performance in long sequence modeling tasks, particularly garnering widespread exploration and application in the field of computer vision. While existing works have mixed opinions of its application in visual tasks, the exploration of its internal workings and the optimization of its performance remain urgent and worthy research questions given its status as a novel model. Existing optimizations of the Mamba model, especially when applied in the visual domain, have primarily relied on predefined methods such as improving scanning mechanisms or integrating other architectures, often requiring strong priors and extensive trial and error. In contrast to these approaches, this paper proposes the Vision Mamba Mender, a systematic approach for understanding the workings of Mamba, identifying flaws within, and subsequently optimizing model performance. Specifically, we present methods for predictive correlation analysis of Mamba's hidden states from both internal and external perspectives, along with corresponding definitions of correlation scores, aimed at understanding the workings of Mamba in visual recognition tasks and identifying flaws therein. Additionally, tailored repair methods are proposed for identified external and internal state flaws to eliminate them and optimize model performance. Extensive experiments validate the efficacy of the proposed methods on prevalent Mamba architectures, significantly enhancing Mamba's performance.
A Global Depth-Range-Free Multi-View Stereo Transformer Network with Pose Embedding
Authors: Yitong Dong; Yijin Li; Zhaoyang Huang; Weikang Bian; Jingbo Liu; Hujun Bao; Zhaopeng Cui; Hongsheng Li; Guofeng Zhang
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: In this paper, we propose a novel multi-view stereo (MVS) framework that gets rid of the depth range prior. Unlike recent prior-free MVS methods that work in a pair-wise manner, our method simultaneously considers all the source images. Specifically, we introduce a Multi-view Disparity Attention (MDA) module to aggregate long-range context information within and across multi-view images.  Considering the asymmetry of the epipolar disparity flow, the key to our method lies in accurately modeling multi-view geometric constraints. We integrate pose embedding to encapsulate information such as multi-view camera poses, providing implicit geometric constraints for multi-view disparity feature fusion dominated by attention. Additionally, we construct corresponding hidden states for each source image due to significant differences in the observation quality of the same pixel in the reference frame across multiple source frames. We explicitly estimate the quality of the current pixel corresponding to sampled points on the epipolar line of the source image and dynamically update hidden states through the uncertainty estimation module. Extensive results on the DTU dataset and Tanks\&Temple benchmark demonstrate the effectiveness of our method.
Chain of Preference Optimization: Improving Chain-of-Thought Reasoning in LLMs
Authors: Xuan Zhang; Chao Du; Tianyu Pang; Qian Liu; Wei Gao; Min Lin
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: The recent development of chain-of-thought (CoT) decoding has enabled large language models (LLMs) to generate explicit logical reasoning paths for complex problem-solving. However, research indicates that these paths are not always deliberate and optimal. The tree-of-thought (ToT) method employs tree-searching to extensively explore the reasoning space and find better reasoning paths that CoT decoding might overlook. This deliberation, however, comes at the cost of significantly increased inference complexity. In this work, we demonstrate that fine-tuning LLMs leveraging the search tree constructed by ToT allows CoT to achieve similar or better performance, thereby avoiding the substantial inference burden. This is achieved through \emph{Chain of Preference Optimization} (CPO), where LLMs are fine-tuned to align each step of the CoT reasoning paths with those of ToT using the inherent preference information in the tree-search process. Extensive experimental results show that CPO significantly improves LLM performance in solving a variety of complex problems, including question answering, fact verification, and arithmetic reasoning, demonstrating its effectiveness. 
Our code is available at [https://github.com/sail-sg/CPO](https://github.com/sail-sg/CPO).
Safe LoRA: The Silver Lining of Reducing Safety Risks when Finetuning Large Language Models
Authors: Chia-Yi Hsu; Yu-Lin Tsai; Chih-Hsun Lin; Pin-Yu Chen; Chia-Mu Yu; Chun-Ying Huang
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: While large language models (LLMs) such as Llama-2 or GPT-4 have shown impressive zero-shot performance, fine-tuning is still necessary to enhance their performance for customized datasets, domain-specific tasks, or other private needs. However, fine-tuning all parameters of LLMs requires significant hardware resources, which can be impractical for typical users. Therefore, parameter-efficient fine-tuning such as LoRA have emerged, allowing users to fine-tune LLMs without the need for considerable computing resources, with little performance degradation compared to fine-tuning all parameters. Unfortunately, recent studies indicate that fine-tuning can increase the risk to the safety of LLMs, even when data does not contain malicious content. To address this challenge, we propose $\textsf{Safe LoRA}$, a simple one-liner patch to the original LoRA implementation by introducing the projection of LoRA weights from selected layers to the safety-aligned subspace, effectively reducing the safety risks in LLM fine-tuning while maintaining utility. It is worth noting that $\textsf{Safe LoRA}$ is a training-free and data-free approach, as it only requires the knowledge of the weights from the base and aligned LLMs. Our extensive experiments demonstrate that when fine-tuning on purely malicious data, $\textsf{Safe LoRA}$ retains similar safety performance as the original aligned model. Moreover, when the fine-tuning dataset contains a mixture of both benign and malicious data,  $\textsf{Safe LoRA}$ mitigates the negative effect made by malicious data while preserving performance on downstream tasks.  Our codes are available at https://github.com/IBM/SafeLoRA.
Space-Time Continuous PDE Forecasting using Equivariant Neural Fields
Authors: David M Knigge; David Wessels; Riccardo Valperga; Samuele Papa; Jan-Jakob Sonke; Erik J Bekkers; Stratis Gavves
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Recently, Conditional Neural Fields (NeFs) have emerged as a powerful modelling paradigm for PDEs, by learning solutions as flows in the latent space of the Conditional NeF. Although benefiting from favourable properties of NeFs such as grid-agnosticity and space-time-continuous dynamics modelling, this approach limits the ability to impose known constraints of the PDE on the solutions -- such as symmetries or boundary conditions -- in favour of modelling flexibility. Instead, we propose a  space-time continuous NeF-based solving framework that - by preserving geometric information in the latent space of the Conditional NeF - preserves known symmetries of the PDE. We show that modelling solutions as flows of pointclouds over the group of interest $G$ improves generalization and data-efficiency. Furthermore, we validate that our framework readily generalizes to unseen spatial and temporal locations, as well as geometric transformations of the initial conditions - where other NeF-based PDE forecasting methods fail -, and improve over baselines in a number of challenging geometries.
Identify Then Recommend: Towards Unsupervised Group Recommendation
Authors: Yue Liu; Shihao Zhu; Tianyuan Yang; Jian Ma; Wenliang Zhong
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Group Recommendation (GR), which aims to recommend items to groups of users, has become a promising and practical direction for recommendation systems. This paper points out two issues of the state-of-the-art GR models. (1) The pre-defined and fixed number of user groups is inadequate for real-time industrial recommendation systems, where the group distribution can shift dynamically. (2) The training schema of existing GR methods is supervised, necessitating expensive user-group and group-item labels, leading to significant annotation costs. To this end, we present a novel unsupervised group recommendation framework named $\underline{\text{I}}$dentify $\underline{\text{T}}$hen $\underline{\text{R}}$ecommend ($\underline{\text{ITR}}$), where it first identifies the user groups in an unsupervised manner even without the pre-defined number of groups, and then two pre-text tasks are designed to conduct self-supervised group recommendation. Concretely, at the group identification stage, we first estimate the adaptive density of each user point, where areas with higher densities are more likely to be recognized as group centers. Then, a heuristic merge-and-split strategy is designed to discover the user groups and decision boundaries. Subsequently, at the self-supervised learning stage, the pull-and-repulsion pre-text task is proposed to optimize the user-group distribution. Besides, the pseudo group recommendation pre-text task is designed to assist the recommendations. Extensive experiments demonstrate the superiority and effectiveness of ITR on both user recommendation (e.g., 22.22\% NDCG@5 $\uparrow$) and group recommendation (e.g., 22.95\% NDCG@5 $\uparrow$). Furthermore, we deploy ITR on the industrial recommender and achieve promising results.
Fast yet Safe: Early-Exiting with Risk Control
Authors: Metod Jazbec; Alexander Timans; Tin Hadži Veljković; Kaspar Sakmann; Dan Zhang; Christian A. Naesseth; Eric Nalisnick
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: Scaling machine learning models significantly improves their performance.  However, such gains come at the cost of inference being slow and resource-intensive.  Early-exit neural networks (EENNs) offer a promising solution: they accelerate inference by allowing intermediate layers to exit and produce a prediction early.  Yet a fundamental issue with EENNs is how to determine when to exit without severely degrading performance.  In other words, when is it 'safe' for an EENN to go 'fast'?  To address this issue, we investigate how to adapt frameworks of risk control to EENNs. Risk control offers a distribution-free, post-hoc solution that tunes the EENN's exiting mechanism so that exits only occur when the output is of sufficient quality.  We empirically validate our insights on a range of vision and language tasks, demonstrating that risk control can produce substantial computational savings, all the while preserving user-specified performance goals.
Contextual Decision-Making with Knapsacks Beyond the Worst Case
Authors: Zhaohua Chen; Rui Ai; Mingwei Yang; Yuqi Pan; Chang Wang; Xiaotie Deng
Venue: NeurIPS 2024 (NeurIPS 2024 poster)

Abstract: We study the framework of a dynamic decision-making scenario with resource constraints.
In this framework, an agent, whose target is to maximize the total reward under the initial inventory, selects an action in each round upon observing a random request, leading to a reward and resource consumptions that are further associated with an unknown random external factor.
While previous research has already established an $\widetilde{O}(\sqrt{T})$ worst-case regret for this problem, this work offers two results that go beyond the worst-case perspective: one for the worst-case gap between benchmarks and another for logarithmic regret rates.
We first show that an $\Omega(\sqrt{T})$ distance between the commonly used fluid benchmark and the online optimum is unavoidable when the former has a degenerate optimal solution.
On the algorithmic side, we merge the re-solving heuristic with distribution estimation skills and propose an algorithm that achieves an $\widetilde{O}(1)$ regret as long as the fluid LP has a unique and non-degenerate solution.
Furthermore, we prove that our algorithm maintains a near-optimal $\widetilde{O}(\sqrt{T})$ regret even in the worst cases and extend these results to the setting where the request and external factor are continuous.
Regarding information structure, our regret results are obtained under two feedback models, respectively, where the algorithm accesses the external factor at the end of each round and at the end of a round only when a non-null action is executed.