diff --git a/src/applications/project/query/PhabricatorProjectQuery.php b/src/applications/project/query/PhabricatorProjectQuery.php
--- a/src/applications/project/query/PhabricatorProjectQuery.php
+++ b/src/applications/project/query/PhabricatorProjectQuery.php
@@ -271,6 +271,25 @@
 
     $all_graph = $this->getAllReachableAncestors($projects);
 
+    // See T13484. If the graph is damaged (and contains a cycle or an edge
+    // pointing at a project which has been destroyed), some of the nodes we
+    // started with may be filtered out by reachability tests. If any of the
+    // projects we are linking up don't have available ancestors, filter them
+    // out.
+
+    foreach ($projects as $key => $project) {
+      $project_phid = $project->getPHID();
+      if (!isset($all_graph[$project_phid])) {
+        $this->didRejectResult($project);
+        unset($projects[$key]);
+        continue;
+      }
+    }
+
+    if (!$projects) {
+      return array();
+    }
+
     // NOTE: Although we may not need much information about ancestors, we
     // always need to test if the viewer is a member, because we will return
     // ancestor projects to the policy filter via ExtendedPolicy calls. If
diff --git a/src/infrastructure/edges/query/PhabricatorEdgeQuery.php b/src/infrastructure/edges/query/PhabricatorEdgeQuery.php
--- a/src/infrastructure/edges/query/PhabricatorEdgeQuery.php
+++ b/src/infrastructure/edges/query/PhabricatorEdgeQuery.php
@@ -46,6 +46,13 @@
    * @task config
    */
   public function withSourcePHIDs(array $source_phids) {
+    if (!$source_phids) {
+      throw new Exception(
+        pht(
+          'Edge list passed to "withSourcePHIDs(...)" is empty, but it must '.
+          'be nonempty.'));
+    }
+
     $this->sourcePHIDs = $source_phids;
     return $this;
   }
@@ -158,11 +165,10 @@
    * @task exec
    */
   public function execute() {
-    if (!$this->sourcePHIDs) {
+    if ($this->sourcePHIDs === null) {
       throw new Exception(
         pht(
-          'You must use %s to query edges.',
-          'withSourcePHIDs()'));
+          'You must use "withSourcePHIDs()" to query edges.'));
     }
 
     $sources = phid_group_by_type($this->sourcePHIDs);