Stanford CS224W: Machine Learning with Graphs

By Nishka Kacheria, Alexandra Kim, and Kyleen Liao as part of the Stanford CS 224W Final Project


代码下载：https://t.zsxq.com/8jOlp

请索引第40个项目


Fraud detection using Graph Neural Networks with PyTorch Geometric


介绍


区分人类编写的代码和LLM生成的代码是计算机科学教育中日益重要且具有挑战性的问题。检测LLM生成的代码对于维护学术诚信、理解学生如何学习和应用编程概念以及评估人工智能辅助编程对教育的更广泛影响尤为重要。我们的目标是帮助人工智能教育者准确区分人类生成的代码和人工智能编写的代码，并维护学术诚信。


虽然像 Xu 等人 (2024) 这样的先前研究已经探讨了区分人类生成代码和人工智能生成代码的方法，但据我们所知，我们的工作是首次使用图神经网络 (GNN) 来分析和刻画这两种代码来源之间的结构差异。我们研究了如何将代码建模为最佳的图模型，并对使用对比学习训练的 GraphSAGE、GCN 和 GIN 的性能进行了比较。


数据集


我们使用了 Xu 等人 (2024) 的 HMCorp 数据集，其中包含 28.8 万个由人类和人工智能生成的 Python 程序代码对。该数据集非常合适，因为它比较新，包含了后期模型的 ChatGPT 代码，而且代码也相当标准化：函数名和参数都比较相似。这意味着该模型可以合理地近似模拟计算机科学作业，在两种类型的代码中，函数名或创建函数的动机等要素都保持一致。出于隐私原因，我们无法使用学生的实际作业，但这已经是一个相当接近的近似。


我们通过将所有代码对转换为抽象语法树（AST）生成了本项目数据集。节点特征和边的选择方式如下：


节点特性：


每个 AST 节点都会变成一个图节点，其特征向量源自：


  • AST 节点类型标记（例如，For、Assign、Call、Name、If、Return）

  • 在分词后的抽象语法树词汇表上，使用 Word2Vec 学习得到的 128 维词嵌入

  • 块级结构嵌入（例如，对应于函数体、循环等）


这样就为每个节点生成了一个稠密向量，该向量描述了该节点的语义角色。


边结构


对于每个节点，我们构建它们之间的显式边：


  • 一个节点及其父节点（AST 父子关系）

  • 它通过共同的父母与兄弟姐妹联系在一起。

  • 为了保证消息传递的稳定性，设计了一个自循环。边是双向的，生成了一个大小为（max_nodes × max_nodes）的无向邻接矩阵。


因此，一个节点的邻居与其 AST 父节点和子节点完全对应，反映了词汇结构和代码嵌套。


边特征


此外，我们还使用与邻接矩阵对应的整数边类型矩阵来编码边的语义角色。边标签包括：


  • '主体'（例如，代码块内的语句）

  • '测试'（If/While 条件）

  • 'iter'（循环迭代器）

  • '目标'（任务目标）

  • 否则（替代从句）

  • “子女”（泛指父母与子女的关系）

  • 'self'（自循环）


每种边类型都映射到一个唯一的索引，这使得 GNN 能够区分不同的结构依赖关系（例如，循环的条件与其主体）。


在了解每个抽象语法树 (AST) 如何表示一段代码后，我们使用各种 AST 进行了消融测试，以找到效果最佳的 AST。我们创建了以下数据集来评估我们的性能：


  • 包含完整图但不包含嵌入（无节点或边标签）的数据集

  • 包含完整图和节点嵌入的数据集

  • 包含完整图以及节点和边嵌入的数据集


在确定节点嵌入达到最高模型准确率后，我们注意到即使对于相对较短的程序，完整的抽象语法树（AST）表示也非常复杂。因此，我们利用 Wu 等人 (2022) 提出的 AST 简化方法创建了一个数据集。该方法移除冗余或语义价值较低的 AST 节点（例如修饰符或标点符号类型的属性节点），同时保留语义价值较高的节点，通常是声明和语句。移除的节点会通过简单的规则进行过滤，这些规则检查节点是否包含声明或语句信息。过滤后，每个被移除节点的子节点会直接重新连接到其父节点，从而保留原始的层级关系并维持树的连通性。该简化过程通过递归遍历实现，只需一次遍历即可检查每个节点，应用过滤条件，并更新父子链接。


这促使我们也对……进行了测试。


  • 具有简化图和节点嵌入的数据集

  • 我们使用不同样本量（100 个数据点和 5000 个数据点）的数据集，以检验我们的 GIN 模型扩展性如何，以及模型的相对排名是否发生变化。


最后，我们确定使用具有简化图和节点嵌入的数据集是合理的，因为它们速度更快、准确率更高。


简化图表与完整图表：消融研究详解


为了探究AST代码中哪些因素会影响准确率，我们尝试移除和包含图的不同特征。在本研究中，我们使用不同的消融数据集训练GIN模型，并比较了结果。我们之所以选择GIN进行消融测试，是因为我们认为它最具表达力。


我们首先构建了一个完整的图，其中所有节点都使用不同的独热编码表示，如左侧的图所示。为了清晰起见，每个节点都被分配了一个唯一的 ID 和一个表示其功能的字符串。此外，我们还合并了源自相同变量的“相同”节点。在代码中


while (i < 5):
  i += 1



图中会有一个代表变量“i”的节点，以及一条指向“i”的链接，这条链接既来自while循环的测试（i < 5），也来自变量的更新（i += 1）。这使得我们的准确率达到了86.66%。正如我们所观察到的，所有相关变量都对应着大量的节点，并且由于图的连接方式（图的图像最多只能显示50个节点），机器可解释性有限。

每个节点都被赋予一个包含节点最基本数据的 ID 表示，由于我们将其编码为独热向量表示，因此只有基本的节点嵌入，不包含任何来自实际代码的节点信息。每个节点只是被赋予了一个不同的初始化值。这些 ID 的生成方式如下：


defget_node_id(child):
# Ensure the ID is always a string
  child_node_id = defn_token(child) + "_" + str(id(child))

# For variable nodes (e.g., Name nodes), assign global unique IDs
ifisinstance(child, ast.Name):
    variable_name = child.id
if variable_name notin variable_ids:
# Assign a new global unique ID for each variable name
      variable_ids[variable_name] = str(len(variable_ids))  # Can be any unique ID
    child_node_id = variable_ids[variable_name]

# Ensure the node is added to the dictionary only once
if unique_nodes:
    node_id_offsets[child_node_id] += 1
    child_node_id += "_" + str(node_id_offsets[child_node_id])
    node_label_dict[child_node_id] = ASTNode(child, child_node_id)    
elif child_node_id notin node_label_dict:
    node_label_dict[child_node_id] = ASTNode(child, child_node_id)

return child_node_id


为了提高准确率，我们做了一些改动：我们将图结构改为树状结构，这导致变量之间的连接丢失（现在，i < 5 和 i += 1 对应的节点是不同的）。因此，为了简化节点嵌入，我们引入了节点类型。这些节点具有相同的用途——例如，'AugAssign' 代表 '+='，'FunctionDef' 代表不同的函数名称。这使得准确率提升至 95.38%，这是一个显著的进步，这很可能是由于有效的节点嵌入和树状结构的简化所致。

在这种情况下，我们的节点被分类，并被赋予一个更重要、更有用的节点嵌入，这是通过删除相关的 ID 并将节点特征排序到桶中得到的。


接下来，我们尝试将这棵树变成异构的，我们通过引入依赖于节点之间 AST 连接的边类型来实现这一点。

这些边类型按如下方式编码：


for field, value in ast.iter_fields(self.node):
ifisinstance(value, list):
for item in value:
ifisinstance(item, ast.AST) and item in children:
        result.append((ASTNode(item), field))
        mapped_ast_nodes.add(id(item)
elifisinstance(value, ast.AST) and value in children:
        result.append((ASTNode(value), field))
        mapped_ast_nodes.add(id(value))



之后，运行 GIN 算法使我们获得了大致相同的准确度：

5005、5003、5000

我们继续阅读相关资料，找到一篇讨论如何将代码转换为抽象语法树的论文。他们提出了一种名为“SimAST”（简化抽象语法树）的概念，这种抽象语法树并不包含完整的图，而只包含其中的一部分。我们按照示例实现了这一概念，例如，只使用while循环的“test”分支，而不是同时使用“test”和“body”循环。


defadd_children(self):
ifself.is_str:
return []

  children = list(ast.iter_child_nodes(self.node))

# Python-specific control flow handling
ifself.token in ['FunctionDef', 'AsyncFunctionDef']:
# Return only the body, skip decorators, args, returns
return [ASTNode(child) for child inself.node.body]
elifself.token in ['If']:
# Return only the test condition
return [ASTNode(self.node.test)]
elifself.token in ['While']:
return [ASTNode(self.node.test)]
elifself.token == 'For':
# Return target and iter, skip body
    result = []
ifhasattr(self.node, 'target'):
        result.append(ASTNode(self.node.target))
ifhasattr(self.node, 'iter'):
        result.append(ASTNode(self.node.iter))
return result
else:
return [ASTNode(child) for child in children]


运行此程序后，我们获得了最佳测试 F1 成绩 96.00%。


5002

我们注意到这几乎与我们完整的图表相同。我们最初的推测是，这是因为我们拥有大量的样本，使得模型能够得出强有力的结论。因此，我们用100个样本（样本量小得多）测试了这项工作。然而，结果基本保持不变。



这似乎表明，包含节点和边嵌入的完整图与仅包含节点嵌入的完整图表现大致相同。这也表明，简化图在样本较少的情况下表现不佳，这可能是由于数据集较小所致，但仍然与完整图的结果非常接近。即使是我们数据集中最简化的版本也具有足够强的信号，因此所有模型都表现得相当不错！


我们的工作将在 5000 数据集上运行，在该数据集上，简化的图不仅性能优于完整图，而且训练速度也快得多。正是这种设置使我们获得了最佳测试 F1 值 96.00%，因此我们使用带有节点嵌入的简化图来比较所有三个模型（GIN、GCN 和 GraphSAGE），结果将在结果部分展示。


从GIN的性能来看，我们可以确定GPT生成的代码和人类生成的代码之间可能存在一些结构差异，这使得模型能够轻松区分这两类代码。这令人振奋，也是我们的关键发现之一！人们可能会认为变量名或调用/使用的具体函数等信息是区分人类编写代码和GPT编写代码的主要特征。然而，我们使用的数据集具有标准化的函数名和变量名，并且抽象语法树（AST）表示主要强调结构而非字符串。即使存在这种限制，我们的模型仍然能够凭借主要的结构信息达到非常高的准确率（96.00%）！因此，人工智能生成的代码和人类生成的代码之间存在显著的结构差异。这对于检测CS 106A等课程作业中的人工智能代码也非常有用，因为在这些课程中，函数名和变量名可能会提前提供给学生。


模型训练


我们决定采用对比学习，因为 Xu 等人 (2024) 已证明该方法在 HMCorp 数据集上具有优异的性能。我们采用孪生网络架构进行对比学习，其中两个权重相同的 GNN 编码器并行处理成对的代码样本。与孤立地对代码进行分类不同，该方法通过比较人类编写的代码和 LLM 生成的代码之间的结构模式来学习判别性特征。


架构


共享编码器：两个代码样本都通过同一个 GNN 编码器（GIN、GraphSAGE 或 GCN），生成图级嵌入，维度为 hidden_dim × num_layers（对于我们的 5 层、256 层隐藏层网络，维度为 1,280）。


连接与分类：将两个嵌入连接起来（2,560 维），并通过两层 MLP 分类器进行分类。


多尺度表示


GNN 的每个层都捕捉不同抽象层次的模式。通过连接所有 5 层的表征，该模型既利用了局部语法细节（早期层），也利用了全局程序结构（深层）。这种多尺度方法至关重要，因为人类代码和 LLM 代码在各个层面上都可能存在差异——从变量命名到整体组织结构。


训练


该模型使用交叉熵损失函数在二分类任务（人类 vs. LLM）上进行训练。孪生架构学习嵌入向量，其中相似的代码样本（同一类别）产生相似的表示，而不相似的样本（不同类别）则可以区分。这种关系学习方法通过捕捉编码模式的根本差异而非记忆绝对特征，从而实现更好的泛化能力。


GNN架构

图同构网络（GIN）


我们的主要模型基于 Xu 等人 (2019) 提出的图同构网络 (GIN) 结构，该结构已被证明在图分类任务中具有极强的表达能力。GIN 框架尤其适用于代码分析，因为它能够捕捉抽象语法树 (AST) 中区分人类代码和语言学习模型 (LLM) 生成代码的细微差异。


GIN 层实现了更新规则：

我们的实施方案包含以下组件：


节点聚合：对于每个节点，我们聚合抽象语法树（AST）中所有相邻节点的特征。这既能捕捉局部结构模式（例如父子关系），也能捕捉更广泛的代码结构。


自循环处理： ε 项使网络能够学习如何平衡节点自身特征与其邻居聚合特征之间的权重。我们将 ε 实现为一个可学习参数，初始值为 0。


多层感知器：每个 GIN 层使用一个两层 MLP，并采用批量归一化和 ReLU 激活函数：

MLP: Linear(input_dim → hidden_dim) → BatchNorm → ReLU 
     → Linear(hidden_dim → output_dim) → BatchNorm → ReLU


网络架构


我们的 GIN 网络由以下部分组成：


  • 嵌入层：使用在语料库上预训练的 Word2Vec 将 AST 标记转换为 128 维向量（词汇量：507）。

  • 5 个 GIN 层：每个层有 256 个隐藏维度和可学习的 ε 参数，通过邻域聚合转换节点特征。

  • 读出：对所有 5 层节点求和，连接表示以捕获多尺度结构模式（总共 1,280 个维度）。


以下是定义 GIN 类的代码片段：

import torch
import torch.nn as nn
import torch.nn.functional as F

classGINLayer(nn.Module):
def__init__(self, input_dim, hidden_dim, output_dim, eps_learnable=True):
super(GINLayer, self).__init__()

self.mlp = nn.Sequential(
      nn.Linear(input_dim, hidden_dim),
      nn.BatchNorm1d(hidden_dim),
      nn.ReLU(),
      nn.Linear(hidden_dim, output_dim),
      nn.BatchNorm1d(output_dim),
      nn.ReLU()
    )

if eps_learnable:
self.eps = nn.Parameter(torch.zeros(1))
else:
self.register_buffer('eps', torch.zeros(1))

defforward(self, x, adj):
    batch_size, num_nodes, feature_dim = x.size()

    neighbor_sum = torch.bmm(adj, x)

    eye = torch.eye(num_nodes, device=adj.device).unsqueeze(0).expand(batch_size, -1, -1)
    self_features = torch.bmm(eye, x)
    neighbor_sum = neighbor_sum - self_features

    out = (1 + self.eps) * x + neighbor_sum
    out = out.view(batch_size * num_nodes, feature_dim)
    out = self.mlp(out)
    out = out.view(batch_size, num_nodes, -1)

return out


classSiameseGNN(nn.Module):
def__init__(self, vocab_size, embedding_dim, hidden_dim, num_layers,
               num_classes=2, dropout=0.3, pretrained_embeddings=None):
super(SiameseGNN, self).__init__()

self.gnn = GINNetwork(...)
self.classifier = nn.Sequential(
      nn.Linear(hidden_dim * num_layers * 2, hidden_dim),
      nn.ReLU(),
      nn.Dropout(dropout),
      nn.Linear(hidden_dim, num_classes)
    )


GraphSAGE


Hamilton 等人 (2018) 提出的 GraphSAGE（图采样与聚合）是一种图神经网络，它通过对节点局部邻域的信息进行采样和聚合来生成节点嵌入，而不是使用整个图。我们的实现包含以下组件：


邻域聚合：对于每个节点，我们计算其直接邻居节点特征的平均值。这可以捕捉局部结构模式和周围节点的上下文信息。


自节点连接：将节点自身的特征与聚合的邻居特征连接起来，以保留有关节点自身的信息，同时融入邻域上下文。


线性变换与非线性：特征拼接后，进行线性变换，然后进行批量归一化和 ReLU 激活，将组合后的特征投影到所需的维度。最后应用 Dropout 进行正则化。


网络架构


  • 嵌入层：使用在语料库上预训练的 Word2Vec 将 AST 标记转换为 128 维向量（词汇表大小：507）。

  • GraphSAGE 层：5 层，每层有 256 个隐藏维度，使用均值聚合来结合节点和邻居信息，然后进行批量归一化和 ReLU 激活。

  • 读出：对所有 5 层节点求和，连接逐层输出以捕获多尺度结构模式（总共 1,280 个维度）。

classGraphSAGELayer(nn.Module):

def__init__(self, input_dim, output_dim, dropout=0.3):
super(GraphSAGELayer, self).__init__()

self.dropout = dropout
self.linear = nn.Linear(input_dim * 2, output_dim)
self.batch_norm = nn.BatchNorm1d(output_dim)

defforward(self, x, adj):
    batch_size, num_nodes, feature_dim = x.size()

    neighbor_sum = torch.bmm(adj, x)

    deg = adj.sum(dim=-1, keepdim=True)  
    deg = deg.clamp(min=1)

    neighbor_mean = neighbor_sum / deg  

    h_cat = torch.cat([x, neighbor_mean], dim=-1)

    h = self.linear(h_cat)
    h = h.view(batch_size * num_nodes, -1)
    h = self.batch_norm(h)
    h = F.relu(h)
    h = h.view(batch_size, num_nodes, -1)

return h


GCN


我们的实施方案包含以下组件：


基于归一化邻接关系的图卷积：对于每个节点，模型将其特征向量与归一化邻接矩阵相乘。

它将信息分发到各个相连的节点。此操作以度归一化的方式将节点的特征与其邻居的特征混合，从而实现结构信息在图中的有效传播。


线性变换和批量归一化：聚合后的节点表示经过学习到的线性变换，映射到一个新的特征空间。然后应用批量归一化来稳定训练过程，之后应用 ReLU 非线性激活函数。Dropout 提供正则化以减少过拟合。


层堆叠：多个 GCN 层堆叠在一起，使信息能够在图中进一步传播。每一层都基于逐渐扩大的邻域更新节点表示，从而捕捉更高阶的结构模式。


网络架构


  • 嵌入层：使用学习到的嵌入矩阵或可选的预训练向量，将来自抽象语法树（AST）节点的词元索引映射到 128 维嵌入。这会将离散的代码词元转换为适合图学习的连续表示。

  • 图卷积网络层：依次应用 5 个图卷积网络层，每个层具有 256 个隐藏维度。在每一层中，图卷积通过归一化邻接关系融合邻居信息，然后进行 ReLU 激活和 dropout 处理。这生成了编码局部和多跳结构信息的深度节点特征。

  • 读取：在处理完所有 5 层之后，每一层的节点嵌入都根据实际节点数进行掩码处理，然后将所有节点的嵌入值相加，得到图级表示。所有层的图嵌入被连接起来，最终得到一个 1280 维的最终表示，该表示能够捕捉代码图的多尺度结构特性。

import torch
import torch.nn as nn
import torch.nn.functional as F

classGCNLayer(nn.Module):
def__init__(self, input_dim, output_dim, use_bias=True):
super(GCNLayer, self).__init__()

self.linear = nn.Linear(input_dim, output_dim, bias=use_bias)
self.batch_norm = nn.BatchNorm1d(output_dim)

defnormalize_adjacency(self, adj):
    batch_size, num_nodes, _ = adj.size()

    eye = torch.eye(num_nodes, device=adj.device).unsqueeze(0).expand(batch_size, -1, -1)
    adj_with_self_loops = adj + eye

    degree = adj_with_self_loops.sum(dim=2)  

    degree_inv_sqrt = degree.pow(-0.5)
    degree_inv_sqrt[degree_inv_sqrt == float('inf')] = 0

    D_inv_sqrt = torch.zeros_like(adj_with_self_loops)
for i inrange(batch_size):
      D_inv_sqrt[i] = torch.diag(degree_inv_sqrt[i])

    normalized_adj = torch.bmm(torch.bmm(D_inv_sqrt, adj_with_self_loops), D_inv_sqrt)

return normalized_adj

defforward(self, x, adj):
    batch_size, num_nodes, feature_dim = x.size()
    adj_normalized = self.normalize_adjacency(adj)

    out = torch.bmm(adj_normalized, x)  
    out = out.view(batch_size * num_nodes, feature_dim)
    out = self.linear(out)
    out = self.batch_norm(out)
    out = out.view(batch_size, num_nodes, -1)

return out


洞察与成果

GraphSAGE



GCNConv

GIN


讨论


我们的实验结果表明，在区分人类生成的代码和人工智能生成的代码时，GIN 在所有测试指标上均优于 GraphSAGE 和 GCN。这一结果为我们深入了解这两种代码来源之间的区别特征以及模型表达能力在捕捉这些特征中的作用提供了重要见解。


GIN 的优势可归因于其理论特性，它是所有测试架构中最具表现力的架构。这意味着，即使 AST 子结构包含相同的节点类型和特征，但拓扑结构不同，GIN 也能区分出在表现力较弱的模型中看起来相同的子结构。


GIN 的优异性能表明，抽象语法树 (AST) 中的结构模式，而非仅仅是局部节点级特征，才是区分人类代码和 AI 生成代码的主要特征。如果分类任务主要依赖于节点特征（例如特定运算符或变量类型的出现频率），我们预期三种架构的性能会更加接近。然而，GIN 将细微的结构差异编码为不同的嵌入的能力，对于有效区分至关重要。


虽然我们的结果强烈表明结构模式是关键的区分因素，但仍需进一步分析以确定GIN学习识别的具体结构基序或拓扑特征。未来的工作可以包括分析学习到的嵌入，以确定哪些AST子结构对类别分离贡献最大。


结论


本文首次对用于区分人类生成代码和人工智能生成代码的图神经网络（GNN）架构进行了深入比较。我们的研究发现，简化的抽象语法树（AST）的性能与完整的AST相近。使用GIN模型区分人类生成代码和人工智能生成代码的最佳结果达到了94.12%的准确率。我们发现GIN的性能优于GCN和GraphSAGE，这可能是因为GIN模型的表达能力更强，并且人类生成代码和人工智能生成代码之间存在结构差异。


参考文献

  • Bingting Wu, Bin Liang, and Xiaofang Zhang. 2022. Turn tree into graph: Automatic code review via simplified AST driven graph convolutional network. Knowledge-Based Systems 252 (2022), 109450. doi:10.1016/j.knosys.2022.109450

  • Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks? arXiv preprint arXiv:1810.00826. https://arxiv.org/abs/1810.00826

  • Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. arXiv preprint arXiv:1609.02907. https://arxiv.org/abs/1609.02907

  • William L. Hamilton, Rex Ying, and Jure Leskovec. 2018. Inductive Representation Learning on Large Graphs. arXiv preprint arXiv:1706.02216. https://arxiv.org/abs/1706.02216

  • Xiaodan Xu, Chao Ni, Xinrong Guo, Shaoxuan Liu, Xiaoya Wang, Kui Liu, and Xiaohu Yang. 2025. Distinguishing LLM-Generated from Human-Written Code by Contrastive Learning. ACM Trans. Softw. Eng. Methodol. 34, 4, Article 91 (April 2025), 31 pages. doi:10.1145/3705300

微信群

内容中包含的图片若涉及版权问题，请及时与我们联系删除