论文地址：
MathGraph：A Knowledge Graph for Automatically Solving Mathematical Exercises
贡献：
设计了一个数学知识图MathGraph，包括实体和关系
设计几个算法，将数学习题与MathGraph对齐，用对齐后的子图解决习题
设计一种方法在语义解析器semantic parser的帮助下识别习题中的实体与关系
特点：与其他数学知识图谱基于广泛语义语料库（维基百科）不同，它使用的语料库来自于四本国内高中数学习题集。
一些概念
实体
数学对象和实例：
数学对象是一种抽象的对象，它有定义，有一些属性，可以作为一些操作或推导的目标。(注意，数学对象可以用其他对象来定义。满足数学对象定义的具体对象称为实例）
举例：
—定义：复数是一种形式为a + bi的数，其中a和b都是实数，i是虚数单位，满足 i 2 = − 1 i^2 =−1 i2=−1。
—属性示例：虚部是复数的一个属性。复数a + bi的虚部是b。
—推导示例：如果 ( a 1 + b 1 i ) (a_1 + b_1i) (a1+b1i)和 ( a 2 + b 2 i ) (a_2 + b_2i) (a2+b2i)共轭，则 a 1 = a 2 , b 1 + b 2 = 0 a_1 = a_2, b_1 + b_2 = 0 a1=a2,b1+b2=0。
2 + 3i和(i + 1)(i−3)是复数的实例。
在MathGraph中，不同的数学对象应该被描述为不同的结构。因此，在MathGraph中，一个数学对象是用一个关键属性元组(p1, p2，···，pn)表示的，如图1
数学对象的关键属性是那些组合在一起可以形成并描述该对象实例的所有信息的属性。表1显示了一些数学对象的关键属性示例。
当且仅当一个数学对象的所有关键属性都相同时，两个实例是等价的。
运算：
一般来说，运算是一个动作或过程，给定一个或多个数学对象作为输入(称为运算数)，产生一个新对象。简单的运算比如加法、减法、乘法、除法和求幂。此外，计算复数的实部、函数的导数、三角形的面积等其他运算过程也可视为运算。
约束:
约束是关于一个或多个实例的描述或条件，其中至少有一个是未知实例。
约束有四种类型：
描述性约束(例如复数x和y是共轭的)、等式约束(例如a + 2 = b)、不等式约束(例如 a 2 ≤ 5 a_2≤5 a2≤5)和集合约束(例如a∈N)。
The Structure of MathGraph
MathGraph是一个有向图G = <V, E>，其中每个节点v∈V表示一个数学对象、一个运算或一个约束，每条边e∈E是两个节点之间的关系。
节点
对象节点
v o = ( t , P , C ) v_o = (t, P, C) vo=(t,P,C)表示一个数学对象，其中t表示该数学对象的实例模板；P = (P1, P2，····，Pn)是表示数学对象关键属性的元组;C是一组约束，根据定义或一些定理，这个数学对象必须满足这些约束。表2显示了一个将“triangle”作为对象节点的示例。我们可以看到三角形的性质和定理包含在约束集中。
运算节点
v p = ( X 1 , X 2 , ⋅ ⋅ ⋅ , X k , Y , f ) v_p = (X_1, X_2, · · · , X_k, Y , f) vp=(X1,X2,⋅⋅⋅,Xk,Y,f)表示一个k元操作/运算， X i 和 Y X_i和Y Xi和Y是对象节点，分别表示第i个操作数 x i x_i xi的定义域和操作y的结果，f是实现运算的函数。
例如：【求一个复数的模长】是一元运算，其中 X 1 ∈ < C o m p l e x N u m b e r > a n d Y ∈ < R e a l N u m b e r > X_1∈<Complex Number> and \quad Y∈ <Real Number> X1∈<ComplexNumber>andY∈<RealNumber>，f 可以通过以下符号执行过程实现:
(1)求x1的实部;(2)求x1的虚部;(3)返回(1)平方和(2)平方的平方根，将其赋值给Y
约束节点
v c = ( d , X 1 , X 2 , ⋅ ⋅ ⋅ , X k , f ) v_c = (d, X_1, X_2, · · · , X_k, f) vc=(d,X1,X2,⋅⋅⋅,Xk,f)表示k个实例的描述性约束条件，其中d是约束的描述， X i X_i Xi是对象节点，表示每个实例运算数 x i x_i xi的定义域。f是一个函数，它把这个描述约束映射成几个等式约束，不等式约束和集合约束。
例如：有一个约束节点【 x 1 和 x 2 x_1和x_2 x1和x2是共轭对】，其中 x 1 = x 2 ∈ < C o m p l e x N u m b e r > x_1=x_2∈<Complex Number> x1=x2∈<ComplexNumber>，f 可以通过以下过程实现:
(1)设 x 1 x_1 x1的实部为 a 1 a_1 a1;(2)设 x 2 x_2 x2的实部为 a 2 a_2 a2;(3)设 x 1 x_1 x1的虚部为 b 1 b_1 b1;(4)设 x 2 x_2 x2的虚部为 b 2 b_2 b2;(5)返回两个等式约束: a 1 = a 2 和 b 1 + b 2 = 0 a_1 = a_2和b_1 + b_2 = 0 a1=a2和b1+b2=0
边
MathGraph有两种类型的边：推导边和流向边。
推导边
对于两个对象节点X和Y，有一条边 e d e r i v e = ( X , Y , f ) e_{derive} = (X, Y, f) ederive=(X,Y,f)揭示了X与Y之间的一般特殊情况。
例如：三角形和等腰三角形，If X derive → Y X\underrightarrow{\text{derive}}Y XderiveY，则在满足某些条件下实例X可以reassign成实例Y。这些条件被封装成函数 f ： X → { T r u e ， F a l s e } f：X\rightarrow\{True，False\} f：X→{True，False}：如果关键属性或约束的值显示原实例的两个角或两条边的长度相等；否则返回False。
流向边
e f l o w = ( X , Y ) e_{flow} = (X, Y) eflow=(X,Y)表示习题求解过程中实例的流向，可能存在于从【对象节点】到【运算节点】，从【运算节点】到【对象节点】，从【对象节点】到【约束节点】。
【对象节点】和【运算节点】之间的流向边表示操作前传递参数的过程和操作后返回新实例的过程。
如图2所示：从对象节点Complex Number到运算节点addition有两条流向边，反过来有一条流向边，意味着addition运算以两个复数实例的实数作为输入，运算结束后返回一个新的复数实例。
用MathGraph解数学题
首先使用一个基于规则的语义解析器将数学习题文本（图3）映射成实例、运算和约束。
语义解析器
实例的映射
语义解析器从文本中映射出一组实例 I = { ( x 1 , X 1 ) , ⋅ ⋅ ⋅ , ( x k , X k ) } I = \{(x_1, X_1), · · · , (x_k, X_k)\} I={(x1,X1),⋅⋅⋅,(xk,Xk)}
其中， x i x_i xi表示实例， X i X_i Xi表示对应的对象节点。
实例被分为已知实例和未知实例，取决于习题是否指明了它们的特定值或表达式。
对于由文本生成的未知实例，具有未知值的关键属性应为作为实例生成，因为它们可能在本练习的操作和约束中使用。
如上图所示：x和y都是对象节点：复数的未知实例。因此，我们需要生成 a x 、 b x 、 a y 和 b y a_x、b_x、a_y和b_y ax、bx、ay和by作为对象节点：实数的四个未知实例，其中 a x 和 b x a_x和b_x ax和bx代表x的两个关键属性：实部和虚部， a y 和 b y a_y 和b_y ay和by代表y的关键属性：实部和虚部。
运算的映射
语义解析器还可以从文本中解析出一组运算。其中的每一个运算 ( o ， ( x 1 , X 1 ) ， ⋅ ⋅ ⋅ ⋅ ， ( x n , X n ) ) (o， (x_1, X_1)，····，(x_n, X_n)) (o，(x1,X1)，⋅⋅⋅⋅，(xn,Xn))都将其运算数对齐到MathGraph o中对应的运算节点，触发运算节点中的函数f，最后生成一个新的实例作为该运算的输出。
映射的约束。
对于习题中的每个描述性约束 ( c ， ( x 1 , X 1 ) ， ⋅ ⋅ ⋅ ， ( x n , X n ) ) (c， (x_1, X_1)，···，(x_n, X_n)) (c，(x1,X1)，⋅⋅⋅，(xn,Xn))，语义解析器可以将其映射到对应的约束节点c，其中一些涉及实例，触发节点中的函数，并将其转换为若干等式约束/不等式约束/集合约束。
另外请注意，在生成未知实例时，还可能根据对应的对象节点的约束集生成一些约束。在此之后，我们将习题中的所有约束收集为一个集合，以供进一步使用。
求解未知实例和约束条件
在解析习题中的所有实例和运算之后，习题的答案已经作为实例生成了(从文本中或通过运算)。如果这个实例是某个已知实例，我们可以直接返回这个实例的值作为答案；否则，我们必须处理这些未知实例，并解决习题中的约束条件，以更新它们的值，最终检索出习题的答案。
求解未知实例
首先，我们需要检查每个未知实例是否可以通过推导边重新分配给MathGraph中更特定的对象节点。对于一个分配给对象节点 v o v_o vo的未知实例 i，我们要检查 v o v_o vo的每一条输出的推导边，如果边e的函数返回true，那么我们将i重新分配给e所指向的对象节点，并将该节点中的所有约束添加到约束集中。
例如：现在有一个未知的实例△ABC，在约束集中有一个约束条件∠B =∠C，那么从三角形到等腰三角形的推导边应返回true。因此实例△ABC应该重新分配给等腰三角形，并在约束集中添加一个新的约束AB = AC。
组织未知实例
注意，对于α和β两个未知的实例，它们之间可能存在依赖关系，比如由于α是运算节点的输入之一，β是输出，或者α是β的关键属性之一。
因此使用一个图 G I = < V I , E I > G_I = <V_I, E_I> GI=<VI,EI>来描述所有未知实例之间的依赖关系。
设 S I = { v ∣ v ∈ V I ∧ ∀ u ∈ V I ， ( u , v ) / ∈ E I } S_I = \{v|v∈VI∧∀u∈V_I， (u, v) /∈E_I\} SI={v∣v∈VI∧∀u∈VI，(u,v)/∈EI}表示 G I G_I GI中包含所有无入边节点（叶子节点）的集合。很明显，如果 S I S_I SI中的所有节点都可以转化为已知的实例，那么就可以推导出答案所需实例的值了，如下图4
例如，图4显示了图3中习题的 G I G_I GI，x和y是否已知——取决于它们各自的关键属性，z = x+y取决于它的两个运算数（= +）。在这种情况下， S I = a x , b x , a y , b y S_I = {a_x, b_x, a_y, b_y} SI=ax,bx,ay,by，与答案对应的实例是z。
组织和求解约束
在最后一步之后，我们现在有了一组约束条件。首先，我们需要确保每个约束中的每个变量都属于 S I S_I SI。如果不是，则需要使用其关键属性作为变量来重写该约束。
例如：对于图3中的练习，约束的集合为 { x + y = 6 , x y = 10 , a x = a y , b x + b y = 0 } \{x + y = 6, x y = 1 0, a_x = a_y, b_x + b_y = 0\} {x+y=6,xy=10,ax=ay,bx+by=0}。又因为x, y不属于 S I S_I SI，前两个约束条件将改写为 a x + b x i + a y + b y i = 6 a_x+b_xi+a_y+b_yi = 6 ax+bxi+ay+byi=6和 ( a x + b x i ) ( a y + b y i ) = 10 (a_x+b_xi)(a_y+b_yi) = 10 (ax+bxi)(ay+byi)=10 。
到目前为止的约束集包含并形式化了习题中的所有约束。因此，我们可以应用符号执行库或近似算法去自动求解这些方程或不等式。
最后，我们将得到 S I S_I SI中每个实例的值(或值的范围)。
更新未知实例和检索答案
在求解出习题中的所有约束之后，我们需要更新 G I G_I GI中其余实例的值。既然我们现在知道 S I S_I SI中实例的值，我们就可以按照拓扑排序的方法顺序遍历 G I G_I GI中的每个实例，并依次更新它们的值。最后，返回与答案对应的实例的值。
实验部分
我们收集了四本中国高中数学习题的真实数据集，即复数、三角形、二次曲线和立体。习题以纯文本形式存储，数学表达式以LaTeX格式存储。
复数：这个数据集包含了1526个与复数计算和推导相关的数学习题，包括基本代数运算、复数的求模长和求共轭复数、复数平面、极坐标表示等。
三角形：这个数据集包含782个与求解三角形相关的数学习题(使用正弦和余弦定律)，包括寻找缺失的边和角，周长，面积，外接圆的半径等。
二次曲线：这个数据集包含1196个与二次曲线相关的习题，包括椭圆、双曲线和抛物线的计算和推导。
立体：此数据集包含653个与立体几何相关的练习，涉及三维欧几里得空间中的各种几何，包括金字塔、棱镜等。
四个数据集中的习题根据难度(根据众多高中生的标准进行分类)分为三个级别(即简单、中等和困难)，表3显示了数据集中不同难度级别的练习数量：
在此实验中，使用Neo4j作为图形数据库平台来构建和索引MathGraph。对于数据集，我们手动构建的知识图谱，仅涉及这些练习中可能存在的实例、运算和约束。
