1. 2023 GPT4Graph
进行实证研究，评估LLM在理解图数据方面的能力
提出一个集成LLM和图结构数据的框架
- 手工提示 Manual Prompt：生成图的图描述语言GDL，将用户查询的query与GDL结合起来形成LLM的输入
- 自提示 Self Prompt：LLM推理过程中的中间输出反馈回输入，如图的上下文解释、图格式描述
建立评判基准
- 结构理解任务
- Graph Size Detection
- Degree Detection
- Edge Detection
- Attribute Retrieval
- Diameter Computing
- Clustering Coefficient Computing 聚类系数计算
- 语义理解任务
- KG QA
- GQL Generation
- Node Classfication
- Graph Classfication
- 结构理解任务
对各种提示进行实验
结构理解任务-引文网络 obgn-arxiv、Aminer
- 输入设计对结果有重大影响
- 角色提示通常可以提高性能
- 示例对图理解有影响，样本和零样本在不同小问题上各有优劣
- 外部知识放在图输入之前性能更好
语义理解任务-知识图谱问答 Wiki、MetaQA
KGQA和GQL生成
SOTA更好，但是LLM也不赖
KGQA上zero-shot-cot+graph+change-order普遍更好
GQL生成上one-shot比zero-shot好
节点分类任务
2-hop上下文比1-hop更好
COT对这项任务不那么奏效
图分类任务
self-prompt的自格式解释和自总结很有效
相关工作和结论
理解图的两个路径：与图神经网络GNN、GCN结合，加入注意力机制GAT
未来可以侧重改进图形结构信息编码
2. 2023 ASE AutoDebloater
论文题目：AutoDebloater: Automated Android App Debloating
背景：Android程序越做越大，对特定用户而言很多功能特征是不需要的，而这些不需要的功能既可能存在安全漏洞，也占用了大量系统资源
目标：Remove unnecessary features from Android applications
方法：
用StoryDistiller生成App的活动转换图ATG
StoryDistiller输入一个App，输出ATG和每个Activity的截图
An activity is an application component that provides a screen with which users can interact to do something.
结合静态活动转换和动态活动转换（抓取组件间通信ICC数据）
识别要删除的活动方法
- 识别用户想要删除活动类中的方法
- 前向切片识别CG中仅受这些方法影响的其他相关方法
采用Soot框架消除待删除方法
- 不直接删除函数，而是将函数体清空，返回值设null或0
- 保留了各种依赖和调用关系，确保编译通过
验证：
- user study
- benchmark：
- 稳定性 stability，不崩溃
- 总体满意度 overall satisfaction，Debloating效果
- 结论：用户满意
- benchmark：
- 性能分析
- StoryDistiller比较慢，采用缓存方法
- Debloating的时间少于 20 秒
3. 2024 ICSE MiniMon
论文题目：MiniMon: Minimizing Android Applications with Intelligent Monitoring-Based Debloating
与第2篇工作AutoDebloater是同一个作者，两篇文章针对的问题背景是一致的，但是这篇不再依赖用户自己选择所需功能，而是通过监控用户的使用记录，从而更自动化的挖掘用户意图并Debloate App。同时Debloating的粒度从Activity变成了method
方法：
静态插桩监视执行情况
使用Soot的BodyTransformer类对应用程序进行静态插桩，在method的第一个指令前插入 方法签名、时间戳、应用程序名称
静态分析获取调用图Call Graph，CG
使用FlowDroid执行静态分析，生命周期方法和回调作为入口点
- 遍历显式方法调用
- 检测反射等隐式方法调用，识别所有传播的字符串常量
- 使用ICCBot检测组件间通信ICC
- 异步任务
MethodGeneralizer：给定CG和监控期间记录的methods，使用无监督技术识别所需功能特征的未见method
基于程序分析的技术
- 前向切片 Forward Slicing
- 反向切片 Backward Slicing
- 双向切片 BiDirection
基于图聚类的技术
- LCD，Louvain community detection algorithm
- LPA，Label propagation algorithm
基于图嵌入的技术
方法1
将图结构转换为序列，DFS生成静态执行路径
为每个序列的每种方法生成嵌入
LSTM
One-Hot
IDF，Inverse Document Frequency 逆文档频率
The intuition is if a method is commonly executed in the
static execution paths, then it should have a lower weight in the
embedding.
IDF-POS，添加位置权重
跨序列聚合（使用max-pooling）每种方法的嵌入，得到方法的最终嵌入
方法2：Node2Vec
得到向量表示后通过余弦相似度识别未见方法
删除无关方法
- 同上一篇工作
- 在删除的方法函数体中通知该方法已被删除
测试基准：
- 启发式方法：将同一活动中的小部件视为一组相似的用户行为
- 使用SARA记录测试用例
评估指标：
- 召回率 Recall
- Debloating Rate
- 加权调和平均值，赋予召回率更大的权重
4. 2023 资源独立工作流可满足性的最小增量模式回溯
论文题目：资源独立工作流可满足性的最小增量模式回溯
这篇文章针对高资源配比（资源数n显著大于步骤数k）的工作流可满足性问题（Workflow Satisfiability Problem, WSP)，在资源独立性约束下，改进原有的SOTA方法增量模式回溯法（Incremental Pattern Backtracking, IPB），提出最小增量模式回溯法MIPB，理论上降低了时间复杂度，并进行对比实验检验了算法运行时空性能
原理：子模式具有唯一增块，增块形成于父子模式的原子性差异，即二者只相差一个增元。论文利用这一最小差异，在计算模式完全指派图时，将增块的候选邻点验证代价降至O(1)，而邻点搜索范围的实际规模可在O(n)量级内极大收缩。据此完全指派图的增量计算时间从O(kn)降至O(n)
这篇文章全是各种定义和证明，感觉我好像缺少了不止一点前置知识，有种在看天书的感觉，除了整体脉络根本没看懂。。。。
