体系结构复习2
第2章 指令系统原理与示例1.指令集系统结构的分类：指令集系统的不同结构根据课件内容，指令集系统结构（Instruction Set Architecture, ISA） 的分类可以根据处理器内部数据的存储类型和操作数访问方式进行划分。
1. 根据处理器内部数据存储类型分类指令集系统结构的最根本区别在于处理器内部数据的存储类型，主要分为以下三类：
(1) 堆栈系统结构（Stack Architecture）
特点：
操作数隐含地位于栈顶，不需要显式指定。
操作数通过 push 和 pop 指令进行堆栈操作。
优点：
指令长度较短（因为操作数隐含）。
缺点：
数据操作效率较低，需要频繁的堆栈存取。
操作顺序受到栈顶限制（无法乱序操作）。
(2) 累加器系统结构（Accumulator Architecture）
特点：
一个操作数隐含在累加器中，另一个操作数需要显式指定。
计算结果存储在累加器中。
优点：
指令长度较短。
简单易实现，适用于早期计算机。
缺点：
累加器的内容需要频繁存取内存，导致效率低。
(3) 通用寄存器系统结构（General Purp ...
体系结构复习1
第1章 量化设计与分析基础1.计算机的分类类别 Flynn分类法（基于指令流和数据流数量）
SISD (Single Instruction Single Data)
单指令单数据流
适用于单处理器系统（Uniprocessors）。
MISD (Multiple Instruction Single Data)
多指令单数据流
特殊情况，通常不常见，具体实例较少（???）。
SIMD (Single Instruction Multiple Data)
单指令多数据流
适合并行处理，常用于向量处理器和图形处理。
示例：Illiac-IV、CM-2。
MIMD (Multiple Instruction Multiple Data)
多指令多数据流
常用于多核处理器和并行计算。
示例：SPARCCenter、T3D。
2.计算机系统结构定义和计算机的设计任务：指令集结构概念及要素计算机系统结构（现代定义）：是在满足功能、性能和价格目标的条件下，设计、选择和互连硬件部件构成计算机。
系统结构覆盖：
指令系统设计 ...
Partitioning Message Passing for Graph Fraud Detection
文献地址：PMP.pdf
代码仓库：Xtra-Computing/PMP
1.背景及创新点1. 问题背景与挑战在使用图神经网络进行图欺诈检测时，主要面临两个挑战：
标签不平衡（Label Imbalance）
图数据通常存在标签不平衡的问题，即欺诈和非欺诈的节点标签数量差异很大。例如，在一个社交网络中，可能大多数节点代表的是正常用户，只有少部分节点代表欺诈用户。这种不平衡的标签分布会导致模型对少数类（欺诈类）预测不准确，从而影响整体检测效果。
同质性-异质性混合（Homophily-Heterophily Mixture）
图数据中存在着同质性（Homophily）和异质性（Heterophily）的混合关系：
同质性指的是图中节点之间具有相似的属性或标签，通常是图神经网络的假设基础（例如，社交网络中的好友节点往往有相似的兴趣）。
异质性则指的是图中某些节点之间存在明显的差异，例如不同类别或标签的节点连接在一起。
传统的图神经网络模型倾向于利用同质性关系，忽略异质性节点的贡献，但在实际的图欺诈检测任务中，异质性节点的信息同样重要，因为欺诈节点往往和非欺诈节点之间有着不同的行为模式或 ...
贪心算法复习
贪心算法1. 贪心算法 (Greedy Algorithm)
基本思想：在每一步中选择“当前最优解”，即局部最优解，期望通过一系列局部最优选择达到全局最优。
局部最优与全局最优的关系：
贪心算法仅在某些特定问题中有效，即局部最优选择能导出全局最优解。
贪心算法通常简单且高效，但并不总是正确。
优点：算法简单、执行效率高。
缺点：可能产生错误结果或次优解。
1.1案例：区间调度问题 (Interval Scheduling)
问题描述：
给定 $n$ 个任务，每个任务有一个开始时间 $s_j$ 和结束时间 $f_j$。
两个任务相容当且仅当它们不重叠。
目标：选择最多数量的相容任务。
贪心策略：
按任务的结束时间 $f_j$ 升序排序。
每次选择当前最早结束且与已选任务不冲突的任务。
时间复杂度：
排序：$O(n \log n)$。
遍历：$O(n)$。
总时间复杂度：$O(n \log n)$。
以下是区间调度问题 (Interval Scheduling) 的贪心算法伪代码：
区间调度问题的伪代码123456789101112131415Algorithm Int ...
Rayleigh Quotient Graph Neural Networks for Graph-level Anomaly Detection Detection
Rayleigh Quotient Graph Neural Networks for Graph-level Anomaly Detection文献地址：Rayleigh Quotient Graph Neural Networks for Graph-level Anomaly Detection | OpenReview
代码仓库：xydong127/RQGNN
1 问题核心问题是：如何通过光谱特性有效地进行图级异常检测。
1.1 现有问题
光谱特性的忽视：
当前图异常检测方法多基于空间域的特征，例如节点属性和拓扑信息，未能充分利用图的光谱特性。
异常图和正常图在光谱能量分布上存在显著差异，但这一特性尚未被现有方法利用。
模型解释性不足：
许多现有方法框架复杂，设计上缺乏理论依据，难以解释异常检测的核心原理。
性能不足：
当前模型在异常检测任务中效果有限，特别是在数据不平衡的情况下难以有效捕捉异常模式。
1.2 文献中的解决方案针对上述问题，本文提出了一个创新性的解决方案：
通过研究Rayleigh商，揭示正常图和异常图的累积光谱能量分布存在统计学差异。
利用光谱 ...
Effective High-order Graph Representation Learning for Credit Card Fraud Detection
论文地址：Effective High-order Graph Representation Learning for Credit Card Fraud Detection
代码仓库：AI4Risk/antifraud: A repository for financial fraud detection
背景，动机，创新1 背景随着数字支付的普及，信用卡欺诈已成为全球金融系统中的重大问题，带来巨大的经济损失，并影响个人和企业的财务安全。报告预测未来十年全球信用卡欺诈损失将达数千亿美元，因此有效的欺诈检测技术对于维持金融系统的健康至关重要。
2 动机
现有的欺诈检测方法，包括基于规则和传统的机器学习方法，难以识别复杂的欺诈行为，特别是那些伪装性强的间接交易。在这种情况下，欺诈者会通过多个正常用户和合法交易掩盖其身份，绕过检测系统，使得欺诈交易看起来像普通的多跳间接交易。虽然近年来图神经网络（GNN）因其在捕捉节点间关系方面的优势而被应用于欺诈检测，但现有的GNN方法在识别这种伪装交易时效果有限。主要原因在于：
伪装欺诈的复杂性：欺诈者往往利用多跳间接交易来隐藏自己，使得直接邻居大多 ...
GADRA-Graph Anomaly Detection via Neighborhood Reconstruction
GAD-NR: Graph Anomaly Detection via Neighborhood Reconstruction论文地址：GAD-NR: Graph Anomaly Detection via Neighborhood Reconstruction
代码仓库：Graph-COM/GAD-NR: [WSDM 2024] GAD-NR : Graph Anomaly Detection via Neighborhood Reconstruction
关键词：Anomaly Detection, Graph Neural Network, Auto-Encoder
1.介绍1.1 背景现有的图自编码器（GAE）方法通过将图数据编码为节点表示，然后评估图的重建质量来检测异常。然而，现有的GAE模型主要优化的是直接连接的重建，导致在处理复杂结构的异常时效果较差，尤其是那些不符合簇型结构的异常节点。
为了解决这个问题，本文提出了一种新的方法——GAD-NR，即基于邻域重建的图异常检测方法。GAD-NR不仅重建节点之间的连接，还通过邻域重建来评估节点的异常性，考虑节点的局部结构、节点自 ...
DAGAD-Data Augmentation for Graph Anomaly Detection
文献地址：DAGAD: Data Augmentation for Graph Anomaly Detection | IEEE Conference Publication | IEEE Xplore
1 介绍1.1 问题文章研究了在图数据中检测异常节点的技术。现有方法面临两个主要问题：
异常样本稀缺：由于异常行为通常较为隐蔽，且缺少足够的背景知识，因此难以有效捕捉异常样本。
类别不平衡：现实中的图数据中，大部分对象是正常节点，异常节点数量极少，导致类别不平衡的问题。
为了解决这些问题，论文提出了一种基于数据增强的图异常检测框架，称为DAGAD（Data Augmentation-based Graph Anomaly Detection）。这个框架包括三个模块：
信息融合模块：利用图神经网络编码器学习节点的表示。
数据增强模块：通过生成额外的训练样本来扩充训练集。
不平衡学习模块：优化少数类别（异常类）和多数类别（正常类）之间的分布差异。
1.2 贡献本文在图异常检测领域的贡献包括以下几个方面：
所提出的图数据增强技术在嵌入空间中从原始训练集生成附加样本。通过两种分类器 ...
Denoising Diffusion Probabilistic Model
扩散模型的原理与可解释性扩散模型（Denoising Diffusion Probabilistic Model, DDPM）的原理可以从其背后的概率推断和去噪过程两个关键机制出发，结合模型的可解释性来进行更详细的说明。
1. 扩散模型的基本框架扩散模型的核心思想是通过两个过程：正向扩散过程和反向去噪过程来生成数据。这种生成机制具有较好的可解释性，因为它模拟了数据逐渐退化为噪声，再从噪声中逐步恢复的过程。
正向过程：逐步向数据中添加高斯噪声，将原始数据 x_0 扩散为接近高斯噪声的 x_T。
反向过程：从最终的噪声样本 x_T 开始，逐步去噪，生成接近真实数据的样本 x_0。
这个框架类似于一种“破坏-恢复”的流程，正向过程将数据“破坏”到完全随机的状态，反向过程则通过逆向步骤“恢复”到原始状态。这种逐步生成的过程在每个步骤都具有明确的物理和概率意义，因此具有良好的可解释性。
2. 正向过程（Forward Process）正向过程可以视为一个马尔可夫链，它通过逐步向数据添加噪声，导致数据逐渐变得混乱，最终接近完全随机的高斯噪声。具体地，每一步都执行如下操作：
q(x_t | x ...
Graph Anomaly Detection with Few Labels - AData-Centric Approach
文献地址：Graph Anomaly Detection with Few Labels: A Data-Centric Approach
介绍这篇论文针对静态图上的异常节点检测任务，提出了一种数据为中心的解决方案。
传统方法通常面临两个挑战：异常节点的稀缺性和高昂的标注成本，导致数据不平衡且难以通过少量标签进行有效学习。因此许多研究接受了这些以数据为中心的挑战，作为图异常检测的事实设置，并追求实现更复杂的图学习算法来检测具有少量标签的图异常。
我们将重点放在生成紧密复制原始图形分布的训练节点上。与以前的以模型为中心的策略不同，我们的方法是以数据为中心的，因为我们优先考虑合成数据的生成和利用，以应对数据稀缺的挑战。然而这种方法会引起两个基本问题：
第一，确保合成数据紧密复制图数据的复杂特征的挑战;
第二，合成数据是否有利于图异常检测。
为了解决这些问题，本文提出了一种基于去噪扩散模型的图生成方法，生成与原始图拓扑和属性分布相符合的辅助训练节点。通过这些生成的节点，现有的异常检测模型可以在少量标签条件下显著提升性能。
我们确定了去噪神经网络应该具备的两个原则：
第一，保留每个节点与其邻居 ...
Multitask Active Learning for Graph Anomaly Detection
文献地址：Multitask Active Learning for Graph Anomaly Detection
代码仓库：AhaChang/MITIGATE
文献介绍了一种名为 MITIGATE 的多任务主动学习框架，用于在图结构数据中进行异常检测。
介绍背景现有的图神经网络（GNN）在异常检测中面临的一个主要挑战是缺乏足够的标注数据，这导致模型性能不稳定。
现有问题
无监督方法通常依赖于数据的分布模式，但如果数据偏离假设的分布，其性能会明显下降。
图结构数据的复杂性以及手动标注正常节点和异常节点的高成本，限制了完全监督学习的应用。由于获取充足的标签非常昂贵，因此需要探索能够利用有限监督信号的学习范式。
MITIGATE框架该框架通过结合节点分类任务来检测异常，主要创新点包括：
多任务学习：MITIGATE 利用了节点分类任务的监督信号来帮助异常检测，特别是在没有已知异常的情况下，通过分类任务检测分布外的节点。
动态信息性度量：通过不同任务之间的置信度差异来度量节点的信息性，从而选择那些提供有用信息但不会过于复杂的样本进行训练。
掩码聚合机制：为了解决图结构中节点间的关系，M ...
数据集处理
YelpChi数据集：基于Yelp数据集上的一个行为图数据集，数据集中的数据以稀疏矩阵的形式存在。该数据集经常用于节点分类、欺诈检测、异常检测等的研究任务上。
Yelp垃圾评论数据集包括Yelp过滤(垃圾)和推荐(合法)的酒店和餐厅评论。Yelp-Fraud数据集上执行一个垃圾邮件审查检测任务，该任务是一个二元分类任务。YelpChi从SpEagle上提取了32个手工特性作为Yelp-Fraud的原始节点特性，基于前人研究发现意见欺假者在用户、产品、评论文本、时间等方面存在联系，将评论作为图中的节点，设计了三种关系:R-U-R:连接同一用户发布的评论;R-S-R:连接同一产品同一星级(1-5星)下的评论;R-T-R:连接同一个月发布的同一产品下的两个评论。
数据集预处理1234567891011121314151617# 设置数据文件的路径前缀prefix = 'data/'# 从 'YelpChi.mat' 文件中加载数据，返回一个包含数据的字典yelp = loadmat('data/YelpChi.mat')# 加载不同 ...