Constructing Adjacency Arrays from Incidence Arrays
Hayden Jananthan Karia Dibert Jeremy Kepner

























































Constructing Adjacency Arrays from Incidence Arrays
    Hayden Jananthan^1,2    Karia Dibert^2,3    Jeremy Kepner^2,3,4 



^1Vanderbilt University Mathematics Department, ^2MIT Lincoln Laboratory Supercomputing Center, 

^3MIT Mathematics Department, ^4MIT Computer Science & AI Laboratory
    Received: date / Accepted: date
==============================================================================================================================================================================================================================================







Graph construction, a fundamental operation in a data processing pipeline, is typically done by multiplying the incidence array representations of a graph, 𝐄_in and 𝐄_out, to produce an adjacency array of the graph, 𝐀, that can be processed with a variety of algorithms.  This paper provides the mathematical criteria to determine if the product 𝐀 = 𝐄^ T_out𝐄_in will have the required structure of the adjacency array of the graph.  The values in the resulting adjacency array are determined by the corresponding addition ⊕ and multiplication ⊗ operations used to perform the array multiplication.  Illustrations of the various results possible from different  ⊕ and ⊗ operations are provided using a small collection of popular music metadata.




graph; incidence array; adjacency array; semiring


















§ INTRODUCTION

This material is based in part upon work supported by the NSF under grant number DMS-1312831.  Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

 The duality between the canonical representation of graphs as abstract collections of vertices and edges and a matrix representation has been a part of graph theory since its inception <cit.>.  Matrix algebra has been recognized as a useful tool in graph theory for nearly as long <cit.>.  The modern description of the duality between graph algorithms and matrix mathematics (or sparse linear algebra) has been extensively covered in the recent literature <cit.> and has further spawned the development of the GraphBLAS math library standard (GraphBLAS.org)<cit.> that has been developed in a series of proceedings <cit.> and implementations <cit.>.
  
  Adjacency arrays, typically denoted 𝐀, have much in common with adjacency matrices.  Likewise, incidence arrays or edge arrays, typically denoted 𝐄, have much in common with incidence matrices <cit.>, edge matrices <cit.>, adjacency lists <cit.>, and adjacency structures <cit.>.  The powerful link between adjacency arrays and incidence arrays via array multiplication is the focus of the first part of this paper.

Incidence arrays are often readily obtained from raw data. In many cases, an associative array representing a spreadsheet or database table is already in the form of an incidence array.  However, to analyze a graph, it is often convenient to represent the graph as an adjacency array.  

Constructing an adjacency array from data stored in an incidence array via array multiplication is one of the most common and important steps in a data processing system.

Given a graph G with vertex set K_out∪ K_in and edge set K, the construction of adjacency arrays for G relies on the assumption that 𝐄^ T_out𝐄_in is an adjacency array of G.  This assumption is certainly true in the most common case where the value set is composed of non-negative reals and the operations ⊕ and ⊗ are arithmetic plus (+) and arithmetic times (×) respectively. However, one hallmark of associative arrays is their ability to contain as values nontraditional data. For these value sets, ⊕ and ⊗ may be redefined to operate on non-numerical values.  For example, for the value of all alphanumeric strings, with

    ⊕   =   max() 
    ⊗   =   min()

it is not immediately apparent in this case whether 𝐄^ T_out𝐄_in is an adjacency array of the graph whose set of vertices is K_out∪ K_in. In the subsequent sections,  the criteria on the value set V and the operations ⊕ and ⊗ are presented so that

    𝐀 = 𝐄^ T_out𝐄_in

always produces an adjacency array <cit.>.





 §.§ Definitions


For a directed graph (from here onwards, just `graph') G, K_out will denote the set of vertices which are the sources of edges, K_in will denote the set of vertices which are the targets of edges, and K will denote the set of edges.  The vertex set of G will be assumed to be K_out∪ K_in. K_out, K_in, and K are assumed to be finite and totally-ordered.

V will denote the set of values that the data can take on, such as non-negative real numbers or the elements of an ordered set.  ⊕ and ⊗ are binary operations on V (in particular, V is closed under the operations ⊕ and ⊗), such as ⊕ = + and ⊗ = × or ⊕ = max and ⊗ = +.  ⊕ and ⊗ each have identity elements 0 and 1, respectively, i.e.

    v ⊕ 0     = 0⊕ v = v 
    
    v ⊗ 1     = 1⊗ v = v

for all v∈ V.  

For the purposes of understanding what algebraic properties are required for 𝐄^ T_out𝐄_in to be an adjacency array of a graph, ⊕ and ⊗ will not be assumed to be associative or commutative, and ⊗ does not necessarily distribute over ⊕, nor is 0 assumed to be an annihilator of ⊗.


An associative array is a map 𝐀: K_1× K_2 → V, where K_1 and K_2 are finite totally-ordered sets, referred to as key sets and whose elements are called keys, and V is the value set.



If 𝐀: K_1×K_2 → V is an associative array, then 𝐀^ T: K_2× K_1 → V is the associative array defined as

    𝐀^ T(k_2,k_1) = 𝐀(k_1,k_2)

where k_1∈ K_1 and k_2∈ K_2.


array!multiplication

Multiplication of associative arrays is defined as

    𝐂 = 𝐀⊕.⊗𝐁 = 𝐀𝐁

or more specifically 

    𝐂(k_1,k_2) =
        ⊕_k_3𝐀(k_1,k_3) ⊗𝐁(k_3,k_2)

where 𝐀, 𝐁, and 𝐂 are associative arrays

    𝐀 : K_1 × K_3 → V 
    𝐁 : K_3 × K_1 → V 
    𝐂 : K_1 × K_2 → V

and k_1 ∈ K_1, k_2 ∈ K_2, k_3 ∈ K_3.



If G is a graph with vertex set K_out∪ K_in and edge set K, then


  𝐄_out: K× K_out→ V is a source incidence array if 𝐄_out(k,a) ≠ 0 if and only if the edge k∈ K is directed outward from the vertex a∈ K_out

  𝐄_in: K× K_in→ V is a target incidence array if 𝐄_in(k,a) ≠ 0 if and only if the edge k∈ K is directed into the vertex a∈ K_in.




If G is a graph with vertex set K_out∪ K_in and edge set K, then 𝐀: K_out× K_in→ V is a adjacency array if 𝐀(a,b) ≠ 0 if and only if there is an edge with source a and target b.







§ ADJACENCY ARRAY CONSTRUCTION


If 𝐀 is an adjacency array for a graph G=(K_out∪ K_in,K), then 𝐀(a,b)≠ 0 if and only if there is an edge k with source a and target b, i.e. so that 𝐄_out(k,a) ≠ 0 and 𝐄_in(k,a)≠ 0.  In the case where the product of two non-zero values is non-zero, this can be subsumed to say that 𝐀(a,b) ≠ 0 if and only if 𝐄_out(k,a)𝐄_in(k,a).  Writing this as

    𝐄_out(k,a) 𝐄_in(k,a) = 𝐄^ T_out(a,k) 𝐄_in(k,a)

This latter expression looks like a term in the evaluation

    (𝐄_out^ T𝐄_in)(a,b) = ⊕_k∈ K𝐄^ T_out(a,k) 𝐄_in(k,b)

but the introduction of more terms means that more assumptions need to be made about the relationships between ⊕,⊗, and 0.



 
Let V be a set with closed binary operations ⊕,⊗ with identities 0,1∈ V.  Then the following are equivalent:


  * ⊕ and ⊗ satisfy the properties
	
		
  * Zero-Sum-Free: a⊕ b=0 if and only if a=b=0,
		
  * No Zero Divisors: a⊗ b = 0 if and only if a=0 or b=0, and 
		
  * 0 is Annihilator for ⊗: a⊗ 0 = 0⊗ a=0.
	

  * If G is a graph with out-vertex and in-vertex incidence arrays 𝐄_out:K× K_out→ V and 𝐄_in: K× K_out→ V, then 𝐄_out^ T𝐄_in is an adjacency array for G.




Let 𝐀 = 𝐄_out^ T𝐄_in.  

As above, for 𝐀 to be the adjacency array of G, the entry 𝐀(k_out,k_in) must be nonzero if and only if there is an edge from k_out to k_in, which is equivalent to saying that the entry must be nonzero if and only if there is a k ∈ K such that

    𝐄^ T_out(k_out,k) ≠ 0 
    𝐄_in(k,k_in) ≠ 0

Taken altogether, the above pair of equations imply

    ⊕_k ∈ K𝐄^ T_out(k_out,k) ⊗𝐄_in(k,k_in)  ≠ 0 
    ∃ k∈ K  so that 𝐄^ T_out(k_out,k) ≠ 0    and  𝐄_in(k,k_in) ≠ 0



First, the above condition can be restated in a form that more easily provides the zero-sum-freeness of ⊕, lack of zero-divisors for ⊗, and the fact that 0 annihilates under ⊗.
Equation <ref> is equivalent to 

    ⊕_k ∈ K𝐄_out(k,x) ⊗𝐄_in(k,y) = 0 
    ∄ k ∈ K   𝐄_out(k,x) ≠ 0  and 𝐄_in(k,y) ≠ 0

which in turn is equivalent to

    ⊕_k ∈ K𝐄_out(k,x) ⊗𝐄_in(k,y) = 0 
    ∀ k ∈ K, 𝐄_out(k,x) = 0  or 𝐄_in(k,y) = 0

This expression may be split up into two conditional statements

    ⊕_k ∈ K𝐄_out(k,x) ⊗𝐄_in(k,y) = 0 ⇒
    ∀ k ∈ K, 𝐄_out(k,x) = 0  or 𝐄_in(k,y) = 0

and

    ∀ k ∈ K, 𝐄_out(k,x) = 0   𝐄_in(k,y) = 0 ⇒
    ⊕_k ∈ K𝐄_out(k,x) ⊗𝐄_in(k,y) = 0



 
Equation <ref> implies that V is zero-sum-free.



Suppose there exist nonzero v,w ∈ V such that v ⊕ w = 0, or that nontrivial additive inverses exist.  Then it is possible to choose a graph G to have edge set {k_1,k_2} and vertex set {a,b}, where both k_1,k_2 start from a and end at b.  Then defining 

    𝐄_out(k_1,a)=v 
    𝐄_out(k_2,a)=w 
    𝐄_in(k_i,b)=1

provides proper out-vertex and in-vertex incidence arrays for G.  Moreover, it is the case that

    𝐄^ T_out𝐄_in(b,a)=(v⊗ 1)⊕ (w⊗ 1)=v⊕ w=0

which contradicts Equation <ref>.  Therefore, no such nonzero v and w may be present in V, meaning it is necessary that V be zero-sum-free.



 
Equation <ref> implies that V has no zero-divisors.


Suppose v⊗ w = 0. Define the graph G to have edge set {k} and vertex set {a} with a single self-loop given by k.  Then define

    𝐄_out(k,a)=v 
    𝐄_in(k,a)=w

to obtain out-vertex and in-vertex incidence arrays for G.  Then

    𝐄^ T_out𝐄_in(a,a)=𝐄_out(k,a)⊗𝐄_in(k,a)=v⊗ w= 0

Thus, Equation <ref> implies that v=w=0, and hence V has no zero-divisors.



 
Equation <ref> implies that 0 annihilates V under ⊗.


Suppose v∈ V. Define the graph G to have edge set {k_1,k_2} and vertex set {a,b}, with self-loops at a and b given by k_1 and k_2, respectively.  Define

    𝐄_out(k_1,a)=v=𝐄_in(k_1,a)

and

    𝐄_out(k_2,b) = v = 𝐄_in(k_2,b)

(and all other entries in 𝐄_out and 𝐄_in equal to 0) 
results in out-vertex and in-vertex incidence arrays of G.  Moreover, it is true that

    0    =   𝐄^ T_out𝐄_in(a,b) 
       =   𝐄_out(k_1,a)⊗𝐄_in(k_1,b)⊕𝐄_out(k_2,a) ⊗𝐄_in(k_2,b) 
       =   (v⊗ 0) ⊕ (0⊗ v)

By Lemma <ref>, V is zero-sum-free so it follows that v⊗ 0 = 0⊗ v = 0.  Thus, 0 is an annihilator for ⊗.





Now Theorem <ref>(i) is shown to be sufficient for Theorem <ref>(ii) to hold. Assume that zero is an annihilator, V is zero-sum-free, and V has no zero-divisors.  Zero-sum-freeness and the nonexistence of zero divisors give

    ∃ k ∈ K  so that 𝐄_out(k,x) ≠ 0  and 𝐄_in(k,y) ≠ 0 ⇒
    ⊕_k ∈ K𝐄_out(k,x) ⊗𝐄_in(k,y) ≠ 0

which is the contrapositive of Equation <ref>. And, that zero is an annihilator gives

    ∀ k ∈ K, 𝐄_out(e,x) = 0  or 𝐄_in(e,y) = 0 ⇒
    ⊕_k ∈𝐄_out(k,x) ⊗𝐄_in(k,y) = 0

which is (<ref>). 
As Equation <ref> and Equation <ref> combine to form Equation <ref>, it is established that the conditions are sufficient for Equation <ref>.





§ ADJACENCY ARRAY OF REVERSE GRAPH




The remaining product of the incidence arrays that is defined is 𝐄^ T_in𝐄_out. The above requirements will now be shown to be necessary and sufficient for the remaining product to be the adjacency array of the reverse of the graph. Recall that the reverse of G is the graph G̅ in which all the arrows in G have been reversed. Let G be a graph with incidence matrices 𝐄_out and 𝐄_in.

Condition (i) in Theorem <ref> are necessary and sufficient so that 𝐄^ T_in𝐄_out is an adjacency matrix of the reverse of G.



Let G̅ denote the reverse of G, and let 𝐄̅_out and 𝐄̅_in be out-vertex and in-vertex incidence arrays for G̅, respectively.  Recall that G̅ is defined to have the same edge and vertex sets as G but changes the directions of the edges, in other words, if an edge k leaves a vertex a in G, then it enters a in G̅, and vice versa.  As such, 𝐄_out(k,a) ≠ 0 if and only if 𝐄̅_in(k,a) ≠ 0, and likewise 𝐄_in(k,a)≠ 0 if and only if 𝐄̅_out(k,a) ≠ 0.  As such, choosing 𝐄_out=𝐄̅_in and 𝐄_in=𝐄̅_out gives valid in-vertex and out-vertex incidence matrices for G̅, respectively.    Then by Theorem <ref> it can be shown that

    𝐄̅^ T_out𝐄̅_in=𝐄^ T_in𝐄_out



It is now straightforward to identify algebraic structures that comply with the established criteria. Notably, all zero-sum-free semirings with no zero-divisors comply, such as ℕ or ℝ_≥ 0 with the standard addition and multiplication.  In addition, any linearly ordered set with ⊕ and ⊗ given by max and min, respectively.  Some non-examples, however, include the max-plus algebra or non-trivial Boolean algebras, which do not satisfy the zero-product property, or rings, which except for the zero ring are not zero-sum-free.  Furthermore, the value sets of associative arrays need not be defined exclusively as semirings, as several semiring-like structures satisfy the criteria. These structures may lack the properties of additive or multiplicative commutativity, additive or multiplicative associativity, or distributivity of multiplication over addition, which are not necessary to ensure that the product of incidence arrays yields an adjacency array.

The criteria guarantee an accurate adjacency array for any dataset that satisfies them, regardless of value distribution in the incidence arrays. However, if the incidence arrays are known to possess a certain structure, it is possible to circumvent some of the conditions and still always produce adjacency arrays.  For example, if each key set of an undirected incidence array 𝐄 is a list of documents and the array entries are sets of words shared by documents, then it is necessary that a word in 𝐄(i,j) and 𝐄(m,n) has to be in 𝐄(i,n) and 𝐄(m,j). This structure means that when multiplying 𝐄^ T𝐄 using ⊕ = ∪ and ⊗ = ∩, a nonempty set will never be “multiplied” by (intersected with) a disjoint nonempty set. This eliminates the need for the zero-product property to be satisfied, as every multiplication of nonempty sets is already guaranteed to produce a nonempty set. The array produced will contain as entries a list of words shared by those two documents.

Though the criteria ensure that the product of incidence arrays will be an adjacency array, they do not ensure that certain matrix properties hold. For example, the property (𝐀𝐁)^ T=𝐁^ T𝐀^ T may be violated under these criteria, as (𝐄^ T_out𝐄^ T_in) is not necessarily equal to 𝐄^ T_in𝐄_out. (For this matrix transpose property to always hold, the operation ⊗ would have to be commutative.)










§ GRAPH CONSTRUCTION WITH DIFFERENT SEMIRINGS


   The ability to change ⊕ and ⊗ operations allows different graph adjacency arrays to be constructed using the same element-wise addition, element-wise multiplication, and array multiplication syntax.  Specific pairs of operations are best suited for constructing certain types of adjacency arrays.  The  pattern of edges resulting from array multiplication of incidence arrays is generally preserved for various semirings.  However, the non-zero values assigned to the edges can be very different and enable the construction different graphs.

For example, constructing an adjacency array of the graph of music writers connected to music genres from Figure <ref> begins with selecting the incidence sub-arrays 𝐄_1 and 𝐄_2 as shown in Figure <ref>.  Array multiplication of 𝐄_1^ T with 𝐄_2 produces the desired adjacency array of the graph.   Figure <ref> illustrates this array multiplication for different operator pairs ⊕ and ⊗.






The pattern of edges among vertices in the adjacency arrays shown Figure <ref> are the same for the different operator pairs, but the edge weights differ.  All the non-zero values in 𝐄_1 and 𝐄_2 are 1. All the ⊗ operators in Figure <ref> have the property

    0 ⊗ 1 = 1 ⊗ 0 = 0

for their respective values of zero be it 0, -∞, or ∞.  Likewise, all the ⊗ operators in Figure <ref> also have the property

    1 ⊗ 1 = 1

except where ⊗ = +, in which case

    1 ⊗ 1 = 2

The differences in the adjacency array weights are less pronounced then if the values of 𝐄_1 and 𝐄_2 were more diverse.  The most apparent difference is between the +.× semiring and the other semirings in Figure <ref>.  In the case of +.× semiring, the ⊕ operation + aggregates values from all the edges between two vertices. Additional positive edges will increase the overall weight in the adjacency array.  In the other pairs of operations, the ⊕ operator is either max or min, which effectively selects only one edge weight to use for assigning the overall weight.  Additional edges will only impact the edge weight in the adjacency array if the new edge is an appropriate maximum or minimum value.  Thus, +.× constructs adjacency arrays that aggregate all the edges.  The sother emirings construct adjacency arrays that select extremal edges.  Each can be useful for construction graph adjacency arrays in appropriate context.



The impact of different semirings on the graph adjacency array weights are more pronounced if the values of 𝐄_1 and 𝐄_2 are more diverse.  Figure <ref> modifies 𝐄_1 so that a value of 2 is given to the non-zero values in the column Genre|Pop and a values of 3 is given to the non-zero values in the column Genre|Rock.



Figure <ref> shows the results of constructing adjacency arrays with 𝐄_1 and 𝐄_2 using different semirings.  The impact of changing the values in  𝐄_1 can be seen by comparing Figure <ref> with Figure <ref>.  For the +.× semiring, the values in the adjacency array rows Genre|Pop and Genre|Rock are multiplied by 2 and 3.  The increased adjacency array values for these rows are a result of the ⊗ operator being arithmetic multiplication × so that

    2 ⊗ 1 = 2 × 1 = 2 
    
      3 ⊗ 1 = 3 × 1 = 3

For the max.+ and min.+ semirings, the values in the adjacency array rows Genre|Pop and Genre|Rock  are larger by and 1 and 2.  The larger values in the adjacency array of these rows is due to the ⊗ operator being arithmetic addition + resulting in

    2 ⊗ 1 = 2 + 1 = 3 
    
      3 ⊗ 1 = 3 + 1 = 4

For the max.min semiring, Figure <ref> and Figure <ref> have the same adjacency array because 𝐄_2 is unchanged. The ⊗ operator corresponding to the minimum value function continues to select the smaller non-zero values from 𝐄_2

    2 ⊗ 1 = min(2,1) = 1 
    
      3 ⊗ 1 = min(3,1) = 1

In contrast, for the min.max semiring, the values in the adjacency array rows Genre|Pop and Genre|Rock are larger by and 1 and 2.  The increase in adjacency array values for these rows are a result of the ⊗ operator selecting the larger non-zero values from 𝐄_1

    2 ⊗ 1 = max(2,1) = 2 
    
      3 ⊗ 1 = max(3,1) = 3

Finally, for the max.× and min.× semirings, the values in the adjacency array rows Genre|Pop and Genre|Rock are increased by and 1 and 2.  Similar to the +.× semiring, the larger adjacency array values for these rows are a result of the ⊗ operator being arithmetic multiplication × resulting in

    2 ⊗ 1 = 2 × 1 = 2 
    
      3 ⊗ 1 = 3 × 1 = 3






Figures <ref> and <ref> show that a wide range of graph adjacency arrays can be constructed via array multiplication of incidence arrays over different semirings.  A synopsis of the graph constructions illustrated in Figures <ref> and <ref> is as follows


  +.× sum of products of edge weights connecting two vertices; computes the strength of all connections between two connected vertices.

  max.×   maximum of products edge weights connecting two vertices; selects the edge with largest weighted product of all the edges connecting two vertices.

  min.×   minimum of products edge weights connecting two vertices; selects the edge with smallest weighted product of all the edges connecting two vertices.

  max.+   maximum of sum of edge weights connecting two vertices; selects the edge with largest weighted sum of all the edges connecting two vertices.

  min.+   minimum of sum of edge weights connecting two vertices; selects the edge with smallest weighted sum of all the edges connecting two vertices.

  max.min     maximum of the minimum of weights connecting two vertices; selects the largest of all the shortest connections between two vertices.

  min.max     minimum of the maximum of weights connecting two vertices; selects the smallest of all the largest connections between two vertices.




























































































§ CONCLUSION


Graph construction, a fundamental operation in a data processing pipeline, is typically done by multiplying the incidence array representations of a graph, 𝐄_in and 𝐄_out, to produce an adjacency array of the graph, 𝐀.  The mathematical criteria to determine if 𝐀 will have the required structure of the adjacency array of the graph over are as follows.  Let V be a set with closed binary operations ⊕,⊗ with identities 0,1∈ V.  Then the following are equivalent:


  * ⊕ and ⊗ satisfy the properties
	
		
  * Zero-Sum-Free: a⊕ b=0 if and only if a=b=0,
		
  * No Zero Divisors: a⊗ b = 0 if and only if a=0 or b=0, and 
		
  * 0 is Annihilator for ⊗: a⊗ 0 = 0⊗ a=0.
	

  * If G is a graph with out-vertex and in-vertex incidence arrays 𝐄_out:K× K_out→ V and 𝐄_in: K× K_out→ V, then 𝐄_out^ T𝐄_in is an adjacency array for G.

The values in the resulting adjacency array are determined by the corresponding addition ⊕ and multiplication ⊗ operations used to perform the array multiplication.







§ ACKNOWLEDGMENT


The authors would like to thank Paul Burkhardt, Alan Edelman, Sterling Foster, Vijay Gadepally, Sam Madden, Dave Martinez, Tom Mattson, Albert Reuther, Victor Roytburd, and Michael Stonebraker.























99

[Anderson et al 2016]Anderson2016 M. Anderson, N. Sundaram, N. Satish, M. Patwary, T. L. Willke, & P. Dubey, GraphPad: Optimized Graph Primitives for Parallel and Distributed Platforms, submitted

[Bodin & Kursh 1979]BodinKursh1979
L. Bodin & S. Kursh, A detailed description of a computer system for the routing and scheduling of street sweepers, Computers & Operations Research, 6(4), 181-198, 1979

[Brualdi 1967]Brualdi1967  
R.A. Brualdi, Kronecker products of fully indecomposable matrices and of ultrastrong digraphs, Journal of Combinatorial Theory, 2:135-139, 1967

[Bruck & Ryser 1949]BruckRyser1949
R. Bruck & H. Ryser, The nonexistence of certain finite projective planes, Canadian Journal of Mathematics, 1, 88-93, 1949

[Buluç & Gilbert 2011]BulucGilbert2011
A. Buluç & J. Gilbert, The Combinatorial BLAS: Design, implementation, and applications . International Journal of High Performance Computing Applications (IJHPCA), 2011

[Buluç 2015]Buluc2015  A. Buluç, GraphBLAS Special Session, IEEE HPEC 2015, Waltham, MA

[Dibert et al 2015]Dibert2015
K. Dibert, H. Jansen & J. Kepner, Algebraic Conditions for Generating Accurate Adjacency Arrays, IEEE MIT Undergraduate Research Technology Conference, 2015

[Dobrjanskyj & Freudenstein 1967]DobrjanskyjFreudenstein1967
L. Dobrjanskyj & F. Freudenstein, Some applications of graph theory to the structural analysis of mechanisms, Journal of Engineering for Industry, 89(1), 153-158, 1967

[Ekanadham et al 2014]Ekanadham2014 K. Ekanadham, B. Horn, J. Jann, M. Kumar, J. Moreira, P. Pattnaik, M. Serrano, G. Tanase, H. Yu, Graph Programming Interface: Rationale and Specification, IBM Research Report, RC25508 (WAT1411-052) November 19, 2014

[Fisher & Wing 1965]FisherWing1965
G. Fisher & O. Wing, Computer recognition and extraction of planar graphs from the incidence matrix, IEEE Transactions on Circuit Theory, 13(2), 154-163, 1966

[Ford & Fulkerson 1962]FordFulkerson1962
L. Ford & D. Fulkerson, Flows in networks, Princeton university press, 1962

[Fulkerson & Gross 1965]FulkersonGross1965
D. Fulkerson & O. Gross, Incidence matrices and interval graphs, Pacific journal of mathematics, 15(3), 835-855, 1965

[Harary & Tauth 1964]HararyTauth1966
F. Harary & C.A. Tauth, Connectedness of products of two directed graphs, SIAM Journal on Applied Mathamatics, 14:250-254, 1966

[Harary 1969]Harary1969
F. Harary, Graph Theory, Reading:Addison-Wesley, 1969

[Hutchison et al 2015]Hutchison2015
D. Hutchison, J. Kepner, V. Gadepally, & A. Fuchs, Graphulo implementation of server-side sparse matrix multiply in the Accumulo database, IEEE High Performance Extreme Computing (HPEC) Conference, Walham, MA, September 2015.

[Kepner & Gilbert 2011]KepnerGilbert2011
J. Kepner & J. Gilbert (editors), Graph Algorithms in the Language of Linear Algebra, SIAM Press, Philadelphia, 2011

[Kepner et al 2012]Kepner2012 J. Kepner, W. Arcand, W. Bergeron, N. Bliss, R. Bond, C. Byun, G. Condon, K. Gregson, M. Hubbell, J. Kurz, A. McCabe, P. Michaleas, A. Prout, A. Reuther, A. Rosa & C. Yee, �Dynamic Distributed Dimensional Data Model (D4M) Database and Computation System,� ICASSP (International Conference on Accoustics, Speech, and Signal Processing), 2012, Kyoto, Japan

[Konig 1931]Konig1931
D. Konig, Graphen und Matrizen (Graphs and Matrices), Matematikai Lapok, 38:116-119, 1931. 

[Konig 1936]Konig1936
D. Konig, Theorie der endlichen und unendlichen graphen (Theory of finite and infinite graphs), Leipzig:Akademie Verlag M.B.H., 1936; see Richard McCourt (Birkhauser 1990) for an english translation of this classic work

[Mattson et al 2013]Mattson2013
T. Mattson, D. Bader, J. Berry, A. Buluç, J. Dongarra, C. Faloutsos, J. Feo, J. Gilbert, J. Gonzalez, B. Hendrickson, J. Kepner, C. Leiserson, A. Lumsdaine, D. Padua, S. Poole, S. Reinhardt, M. Stonebraker, S. Wallach, & A. Yoo, Standards for Graph Algorithms Primitives, IEEE HPEC 2013, Waltham, MA

[Mattson 2014a]Mattson2014a
T. Mattson, Workshop on Graph Algorithms Building Blocks, IPDPS 2014, Pheoniz, AZ

[Mattson 2014b]Mattson2014b
T. Mattson, GraphBLAS Special Session, IEEE HPEC 2014, Waltham, MA

[Mattson 2015]Mattson2015
T. Mattson, �Workshop on Graph Algorithms Building Blocks,� IPDPS 2015, Hyderabad, India

[Mattson 2016]Mattson2016
T. Mattson, �Workshop on Graph Algorithms Building Blocks,� IPDPS 2016, Chicago, IL

[McAndrew 1963]McAndrew1963  
M.H. McAndrew, On the product of directed graphs, Proceedings of the American Mathematical Society, 14:600-606, 1963

[McAndrew 1965]McAndrew1965  
M.H. McAndrew, On the polynomial of a directed graph, Proceedings of the American Mathematical Society, 16:303-309, 1965

[Sabadusi 1960]Sabadusi1960  
G. Sabadusi, Graph multiplication, Mathematische Zeitschrift, 72:446-457, 1960

[Tarjan 1972]Tarjan1972
R. Tarjan, Depth-first search and linear graph algorithms, SIAM journal on computing, 1(2), 146-160, 1972

[Teh & Yap 1964]TehYap1964  
H.H. Teh & H.D. Yap, Some construction problems of homogeneous graphs, Bulletin of the Mathematical Society of Nanying University, 164-196, 1964

[Weischel 1962]Weischel1962
P.M. Weischel. The Kronecker product of graphs.
Proceedings of the American Mathematical Society, 13(1):47–52, 1962

[Zhang et al 2016]Zhang2016 P. Zhang, M. Zalewski, A. Lumsdaine, S. Misurda, & S. McMillan,  GBTL-CUDA: Graph Algorithms and Primitives for GPUs, GABB workshop at IPDPS 2016







