Abstract We propose a new approach to abduction, i.e., nondeductive inference to find a hypothesis H for an observation O such that H, KB ? O where KB is background knowledge. We reformulate it linear algebraically in vector spaces to abduce relations, not logical formulas, to realize approximate but scalable abduction that can deal with web-scale knowledge bases. More specifically we consider the problem of abducing relations for Datalog programs with binary predicates. We treat two cases, the non-recursive case and the recursive case. In the non-recursive case, given r1 (X,Y ) and r3 (X, Z), we abduce r2 (Y, Z) so that r3 (X, Z) ? ?Y r1 (X,Y )? r2 (Y, Z) approximately holds, by computing a matrix R2 that approximately satisfies a matrix equation R3 = min1 (R1 R2 ) containing a nonlinear function min1 (x). Here R1 , R2 and R3 encode as adjacency matrix r1 (X,Y ), r2 (Y, Z) and r3 (Y, Z) respectively. We apply this matrix-based abduction to rule discovery and relation discovery in a knowledge graph. The recursive case is mathematically more involved and computationally more difficult but solvable by deriving a recursive matrix equation and solving it. We illustrate concrete recursive cases including a transitive closure relation.